なんとなくアルゴリズム系の読み物読んでみたかったので読んだ。
この本は、著者が3つの基準で選んだ「偉大なアルゴリズム」について、エンジニアでなくても分かるような簡単な言葉を使って紹介してくれる本である。以下のようなアルゴリズムについて紹介している。
話題がかなり身近なものであり、説明が本当にわかりやすいため、とりあえずアルゴリズムを学ぶ前の読み物として非常におすすめ。個人的には検索エンジンやページランク、パターン認識あたりが興味深かった。この本を読んで、興味を持った部分について、さらに深く学習をしていくと良いかもと思った。
読書メモ
## 検索エンジンのインデクシング
- 検索エンジンの仕事の中で特に大きなものは、マッチングとランキングの2つ 324
- インデックスにページ番号と、ページ内の位置も保存している 411
- これによりフレーズ検索もできる
## ページランク
- ページランクのランダムサーファーのシミュレーション 769
## パターン認識
- 最近傍法、決定木、ニューラルネットワーク 1649
- 標準的なアプローチは、パターン認識を「分類」の問題として扱うもの 1663
- 基本戦略は、大量の「分類ラベル付きデータ」をコンピュータに与えること 1691
- 最近傍法とは言葉通りに訓練データの中から最も近いものを探し、その分類を予測値とすること 1720
- 最も近いk個を使う、k最近傍法もある
- 数字の文字認識なら、数字の間の空間的距離ではなく、数字のイメージの違いを計測するなどの方法がある 1743
- 決定木を訓練データを用いて作り上げる方法がある 1802
- ニューロンの性質 1845
- 入力信号の合計が強ければ活性化する
- 入力には「興奮性」のものと「抑制性」のものの二種類がある
- ニューロンの性質のようなネットワークを作ることをニューラルネットワークと呼ぶ 1869
- 重み付き信号 1901
## データ圧縮
- ロスレス圧縮
- 前と同じトリック 2118
- より短いシンボル 2158
- ロスあり圧縮 除外トリック 2250
- JPEGの除外トリック 2307
## データベース
- 先行書き込みログ(べき等になるように記述されている)を最初に作り、それを順に実行していくモデルにより、クラッシュしてもデータが不整合にならないようになっている 2551
- ロールバックは先行書き込みログを逆順に実行すればいい 2551 2666
- 2段階コミットプロトコル 2719
## デジタル署名
- べき乗を使ったデジタル署名 3134
