「チューリングの計算理論入門」を読んだ。 チューリングマシンってどんなだっけ？と思って、手に取った本。 シャノンの情報理論入門の著者と同じで、本の位置付けも入門で同じ。 チューリングについて語る前に、その頃の時代背景の説明や関係しそうなしなさそうな人物の紹介などについて述べて、その後チューリングの話に入るという展開。 チューリングマシンというものは、そもそも物理的な機械でなくて、数学的な理論の実装機械というものであり、その説明のために時代背景やチューリングが達成したかった数学的課題を説明している。そして、チューリングマシンは数学的な基礎だけでなく、現代のコンピュータの基礎としての位置付けとなった。

チューリングマシンとは、無限長のテープ（記憶装置）と状態を持った機械であり、状態遷移とテープの読み書きのルールを定義することであらゆるアルゴリズムを実行できるものです。

「シャノンの情報理論入門」を読んだ。

学生時代の教科書として使っていたもっと堅い情報理論の本を読み返しているのだけれども、よく理解できないところがあったので、違う本も読んでみて理解を深めようと思って手にした本です。 情報理論というのは、情報というのをどのように伝達するのが効率良いのかとか意味のある情報とは何かとかそういうものを定義するものです。ある通信路を通して情報を一方から他方へ伝える場合の符号化の方法として何が最適かということを考える学問です。

堅い方の本で特によくわからなかったのは情報エントロピーでした。シャノンの情報理論入門では、エントロピーを期待値と説明していましたが、あぁ、なるほどと理解が深まりました。

本書はなるべく平易な表現で大まかに理解することを目指したものなので、タイトル通り、入門に良いと感じました。

「なっとく！アルゴリズム」を読んだ。

イラストを多く使って分かりやすくしているのがウリのアルゴリズム本とのこと。 しかし、読んでみるとなんとなくわかりづらかった。何がわかりづらいのか考えてみると、おそらく定義が無いか曖昧か後に出てくるのが原因だろうと思う。問題点の説明はできているので、問題の共有は読者との間にできていると思うが、アルゴリズムの定義がやや曖昧で、なるほどと納得するのに時間が掛かった。また、Pythonでアルゴリズムを表現しているが、全体のコードが後に出てくるため、全体を把握してから読み進めるというよりは、小さな部品から初めて完成させるというボトムアップ型の作りになっているのも関係しているかもしれない。

ただ内容については、「初めてのコンピュータサイエンス」に記載のなかったダイクストラ法等もあって幅広いアルゴリズムについて触れている。そこに惹かれたのが、本書を読んだ理由の一つでもある。

以下に、言及のあったアルゴリズムを挙げる。キーワードの紹介だけのものも含む。

• 二分探索

• 分割統治

• クイックソート

• 幅優先探索（グラフ）

  • ダイクストラ法 : 正の重みを考慮した重み付きグラフの最短経路に利用
  • ベルマンフォード法 : 負の重みを考慮した重み付きグラフの最短経路に利用

• 貪欲法

• 動的計画法

• k近傍法

• B 木

• 赤黒木

• スプレー木

• 転置インデックス

• フーリエ変換

• ブルームフィルタ

• HyperLogLog

• Simhash

「初めてのコンピュータサイエンス」を読んだ。 最近、Googleの入社エントリが話題になったが、やはりコンピュータサイエンスの基礎はきちんとしておかねばならないと再認識する良いきっかけになった。 大学の講義の教科書として使っていた本を読もうかと思ったが、手元になかったので図書館で何か良いものはないかと探して選んだのがこの本。 Pythonを使って説明する内容となっているためにPythonの説明から始まるが、アルゴリズムの説明などは多言語にも応用の利くように記載されていてPython以外の言語を書く人に対しても有効な記載ぶりである。 大学の講義を思い出すような内容であったが、プログラミングスタイルなどにも触れてられていて、大学の講義にはなかった内容もあって有意義であった。

今後しばらくはコンピュータサイエンス系の本を中心に読もうと思う。 次はアルゴリズム系として以下の本を読む予定。