JUNのブログ

JUNのブログ

活動記録や技術メモ

「世界でもっとも強力な9のアルゴリズム」を読んだ

「世界でもっとも強力な9のアルゴリズム」という本を読んだので感想.

この本はアルゴリズムについての本だが, アルゴリズムやデータ構造についての教科書という感じではなく, 現代のコンピュータ及びインターネット上で頻繁に使われている(ただしその存在は表から感じさせない)アルゴリズムについて非プログラマーでもわかるように説明した本である.

数式やコードは一切でず, 大まかな概念と考え方, 歴史的な経緯が少しというような内容である. 実際, この本を読めば本書に書いてあるアルゴリズムを実装できるというものではなく, この本を入り口とし, そこから興味のあるアルゴリズムを深堀りして実装するというのが良いのでは無いだろうか. また, 非プログラマーの人が読んでもコンピュータの裏側でどのようなことが起きているか, 現代のコンピュータやインターネットがどのようにして成り立っているのかを知れる良い読み物になると思う.

この本の中で説明されていたアルゴリズムは以下のものがある.

以下各トピックについて軽く感想を書く.

検索エンジンのインデクシング, ページランク

検索エンジンのインデクシング及びページランクアルゴリズムでは実際に検索エンジンが検索ワードに対してどのように検索結果を返しているのかというのが知れて面白かった. また章内で紹介されていたGoogle創業者が発表した論文"The Anatomy of a Large-Scale Hypertextual Web Search Engine"の存在は知らなかった. 調べてみると普通に公開されていたので今度読んでみたい.

infolab.stanford.edu

公開鍵暗号, デジタル著名

公開鍵暗号, デジタル著名に関してはセキュアに情報を交換,伝送したり, ソフトウェアやウェブサイトの作成元を保証したりする時に使われるアルゴリズムを学んだ. プログラミングは他の分野の工学(電気工学, 制御工学, etc)に比べて数学が直接的に必要になる場面というのは少ないと思っているが, それは偉大な数学者が数学及び暗号学に基づく素晴らしい暗号化方法などを編み出し, 誰かが実装してくれているからなんだなぁと思った. この当たりの話はある程度の数学の知識が無いと理解できないはずだが, 本書では簡単な例で核となる考え方を説明してくれていて自分のような人間でも簡単に核となる考え方や仕組みを理解することが出来た.

誤り訂正符号

誤り訂正符号についてはTCP/IP関連の勉強でチェックサムなどについて知っていたが, 歴史的にどのようにそのような仕組みが生まれたかなどは知らなかったので面白かった.

データ圧縮

データ圧縮に関してはロスあり/なし圧縮があり, それらの違いと大まかな考え方について知れた. ただ, 詳細は書かれていないのでこの当たりはまた調べたいと思った.

データベース

データベースは一般的には利用者側からは見えないがとても大事な仕組みである. ただ, このあたりの話は前から知っているものであり, 自分にとって特段目新しいということはなかった.

パターン認識

パターン認識についても同様で, 自分は昔この当たりの勉強をしていたので自分にとって新しい情報というのは無かった(昔勉強していたため). ただ, 勉強したことない人にとってはわかりやすい説明だろうなとは思った.

決定不可能性

最後の決定不可能性については, 少しむずかしかった. 昔計算理論の本を読んだのである程度はわかっていたが, この章では背理法を用いて "プログラムの全てのバグを検出プログラム" を作れないというのを証明した. 正直この章だけは なるほどな? という感じで読んだ. 背理法とういうのはそういうものなのだろうが, こう一発で決定するわけではなく, 「真と仮定した時に他の真であるはずの事象が偽になるからこれは真ではないよね 」みたいな感じですこし回り道をして証明しているような感じで証明して自分には少し合わないかな.