diadia

興味があることをやってみる。自分のメモを残しておきます。

みんなのコンピュータサイエンスを読んでみたときのメモ

**通読2回目 一回目では何を言っているのかほとんど理解できなかった。したがって読書で調べたこと、メモを残しておく。

第1章

「プールが温かければ、私は泳ぐ」の意味は、私は温水でしか泳がない、を示すわけではない。「冷たいプール」に関しては何も保証していません。
両条件を表現するには、双条件(biconditional)を使います。A↔B:プールが温かい場合にのみ、私は泳ぐ

2章 計算量

時間計算量とはなにか。
計算量の増加を記法 O記法で表現する。
計算量指数関数的に増加するアルゴリズムを避ける。

時間計算量:

時間計算量はT(n)と表現され、大きさがnの対象を処理するときにアルゴリズムが要する演算数を示します。

WladstonFerreiraFilho. みんなのコンピュータサイエンス (Japanese Edition) (Kindle の位置No.667-668). Kindle 版.

計算量は、書いたコードがどれだけ計算することになるかを計算すればよい。 で、計算する対象が大きくなるとどれだけ時間がかかるかは、T(n)を使って計算する。N/Mみたいな形で計算し、前提となる対象と比べて増えた計算対象がどれだけ時間がかかるか見積もることができるようになる。

計算にかかる時間について

多くのアルゴリズムでは、対象の大きさが増加すると、演算の数が急増します。たとえば、私たちのカードソートのアルゴリズムでは、ちょっとした演算で26枚のカードをソートできますが、2倍の52枚のカードではソートに4倍の演算が必要です。

WladstonFerreiraFilho. みんなのコンピュータサイエンス (Japanese Edition) (Kindle の位置No.656-659). Kindle 版.

時間計算量はT(n)で表される。

ある計算を行う際に計算対象によっては計算の時間が変わることがある。 計算の対象は最善、最悪、平均の場合に分けられ、最悪の対象(サンプル)を用いると常に信頼できる基準が得られる。

大きさnの対象に対して、要する演算数をカウントすることで、アルゴリズムの時間計算量を調べることができます。

WladstonFerreiraFilho. みんなのコンピュータサイエンス (Japanese Edition) (Kindle の位置No.686-687). Kindle 版.

本書では選択ソートを用いてアルゴリズムの時間計算量を調べる方法を説明している。
自分は選択ソートを知らないのでこれが何なのかわからなかった。

選択ソートに関する説明:

選択ソート(基本選択法)とは - IT用語辞典 e-Words

選択ソート : アルゴリズム

選択ソート(Selectionsort)を丁寧に 解説してみた by Python - アメリカの大学で奮闘中

選択ソートをpythonで表現する

def selectionsort(l):
    n = len(l)
    for index in range(n-1):
        least = index
        for x in range(index + 1, n):
            if l[x] < l[least]:
                least = x
        tmp = l[index]
        l[index] = l[least]
        l[least] = tmp
    return l

if __name__ == '__main__':
    from random import shuffle
    l = list(range(0, 15))
    lcopy = l[:]
    shuffle(l)
    print('Unsorted')
    print(l)
    assert l != lcopy
    print('Sorted')
    print(selectionsort(l))
    assert l == lcopy
コードの説明

最初のforでリストのインデックスを定める。そのインデックスに未修正のリストから探しだした最小値を配置していく。こうすると、左から順番に最小値が並べられていく。

計算量の計算について

読んでも直感的にわかることはなかった。ここについては他の資料を探して以後理解に務めることにする。

戦略

アルゴリズム設計の戦略について考える章である。

  1. 反復処理
  2. 再帰処理
  3. 総当り攻撃
  4. バックトラック
  5. 発見的解法
  6. 分割統治法

反復処理による戦略は、条件が満たされるまで、たとえば、for、whileを使って処理を繰り返すことにあります。繰り返しの各処理は反復と呼ばれます。対象の最初から最後まで各要素に対して同じ演算を行うときに最適です

WladstonFerreiraFilho. みんなのコンピュータサイエンス (Japanese Edition) (Kindle の位置No.872-874). Kindle 版.

用語メモ:べき集合

参考: 有限集合の例でべき集合を求めるよ | 数学の星

べき集合とは部分集合の全体の集合のこと。例えば、{1,2,3}という集合があれば部分集合は以下になる。 {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}。
そして冪集合は{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}である。

べき集合を生成するスクリプトの書き方

Python 3.x - 冪集合の作成(Python3)|teratail

再帰処理

再帰処理を使う場合にはメモリを消費することになる。また直感的にわかりにくい。しかし高速に処理することができる。

総当たり攻撃

4章 データ構造について

重要な用語として抽象データ型(abstract data type, adt)とデータの構成(structure data)があることが分かった。

抽象データ型(AbstractDataType:ADT)は、所定のデータ型に対して意味をなす操作群の仕様に相当します。ADTは所定の型のデータを格納した変数に対して機能するインターフェイスとして定義され、これらによってデータがメモリ上にどのように配置されているか、どのように操作されているかという詳細はすべて隠されます。

WladstonFerreiraFilho. みんなのコンピュータサイエンス (Japanese Edition) (Kindle の位置No.1491-1494). Kindle 版.

おそらくこの文章はデータ型(文字列型、ブーリアン型、数値型)に対して操作する際に使われるインターフェースのことを抽象データ型と呼んでいると思われる。この抽象データ型があるおかげで、各データ型のデータ操作は一定の名前(操作名)でラッピングすることができるといったところか? データ型に対して抽象データ型が一対一対応していると思ったけど、この認識は誤りか??そもそも再利用するってどういう事??

抽象データ型の例

  • 基本データ型
  • スタック
  • キュー
  • 優先度付きキュー
  • リスト
  • ソート済みリスト
  • マップ(辞書)
  • 集合

データ構造(data structure)は、データ処理モジュールでのADTの実装手段を提供します。