世界でもっとも強力な9のアルゴリズム
日経BP社
著者：ジョン・マコーミック
訳者：長尾高弘
はじめに
目次
第１章 イントロダクション──コンピュータが日常的 に使っているすごいアイデアはどんなものか
1.1 アルゴリズム──コンピュータが指先の天才になるための材料
1.2 どんなアルゴリズムが偉大なのか
1.3 偉大なアルゴリズムを意識しなければならない理由
第２章 検索エンジンのインデクシング──世界最大の藁山から針を探す
2.1 マッチングとランキング
2.2 Altavista──最初のウェブ規模のマッチングアルゴリズム
2.3 古き時代のインデクシング
2.4 単語の位置情報のトリック
2.5 ランキングと近接性
2.6 メタワードトリック
2.7 インデクシングとマッチングのトリックはまだ序の口である
第３章 ページランク──グーグルを起ち上げたテクノロジー
3. 1 ハイパーリンクトリック
3.2 オーソリティトリック
3.3 ランダムサーファートリック
3.4 実際のページランク
第４章 公開鍵暗号法──葉書で機密情報を書き送る
4.1 「共有された秘密」による暗号化
4.2 オープンな場で「共有された秘密」を作る方法
4.3 実際の公開鍵暗号法
第５章 誤り訂正符号──自分で誤りを訂正するシステム
5.1 誤り検出と誤り訂正のニーズ
5.2 反復トリック
5.3 冗長性トリック
5.4 チェックサムトリック
5.5 ピンポイントトリック
5.6 実際の誤り検出、誤り訂正
第6章 パターン認識－経験から学ぶ
6.1 問題は何か
6.2 最近傍法
6.3 決定木－20の質問トリック
6.4 ニューラルネットワーク
6.5 パターン認識の過去、現在、未来
第7章 データ圧縮－無から有を生み出す
7.1 ロスなし圧縮－究極のフリーランチ
7.2 ロスあり圧縮－フリーランチではないがとても割安な食事
7.3 圧縮ある語ズムの起源
第8章 データベース－一貫性の追求
8.1 トランザクションとto-doリストトリック
8.2 レプリケートされるデータベースのための「準備してからコミット」トリック
8.3 リレーショナルデータベースと仮想テーブルトリック
8.3 データベースの人間サイド
第9章 デジタル署名－このソフトウェアを本当に書いたのは誰か
9.1 デジタル署名は実際には何のために使われているのか
9.2 紙に書く署名
9.3 南京錠つきの署名
9.4 掛け算南京錠による署名
9.5 指数南京錠による署名
9.6 デジタル署名の実際
9.7 パラドックスの解決
第10章 決定不在性とはなにか
10.1 バグ、クラッシュ、ソフトウェアの信頼性
10.2 あることが真ではないことの証明
10.3 他のプログラムを分析するプログラム
10.4 存在し得ないプログラム
10.5 クラッシュ検出プログラムの不可能性
10.6 不可能なプログラムにはどのような意味があるのか
第11章 まとめ－指先の天才はもっと賢くなるか
いくつかの偉大になる可能性のあるアルゴリズム
偉大なアルゴリズムが消えていくことはあるのか
私たちは何を学んだのか
終点から私たちの度の目的を振り返る
謝辞
参考資料