世界でもっとも強力な9のアルゴリズム

著者 : ジョン・マコーミック 長尾高弘

• 日経BP (2012年7月19日発売)

感想・レビュー・書評

[haru2012さんの感想 · 2014年1月19日]

コンピュータ科学という大きな世界。プログラムの知識がなくても、アルゴリズムは説明できるし理解できる。いつも使っているコンピュータ、ブラックボックスを覗いて、驚きや満足を感じられるようになろう。

必要性と存在意義、そして日常的に恩恵を受けていることを改めて感じます。コンピュータ科学、すごい。

[kashiさんの感想 · 2014年1月4日]

http://kashiwabaray.com/blog/index.php?itemid=355

厳選した9つのアルゴリズムについて、分かりやすくイメージを説明しています。どちらかというと、初心者向けの1冊となりますので、専門知識を持っている人には少し物足りない内容だと思います。文系の方でも十分読める内容となっています。

■オープンな場で「共有された秘密」を作る方法
この方法を「ディフィー＝ヘルマン鍵交換」と呼んでいるが、私たちは「絵具混合トリック」と呼ぶことにしよう。
－絵具混合トリック
ステップ１　あなたとアーノルドは、「秘密の色」と呼ぶ。
ステップ２　あなたかアーノルドが、これらとは異なる色の作り方を公表する。この色を「公開色」と呼ぶことにする。
ステップ３　あなたとアーノルドは、それぞれ公開色1壺と秘密色1壺を混ぜた絵具を作る。こうすると、「公開秘密混合色」が作られる。
ステップ４　部屋の中央からアーノルドの公開秘密混合色の絵具を手に入れて自分の秘密スペースに持ち帰る。
その絵具に自分の秘密色の壺を1つ混ぜる。一方、アーノルドはあなたの公開秘密混合色を自分の秘密スペースに持ち帰り、自分の秘密色の絵具を1壺それに混ぜる。

―数値による絵具混合
ステップ１　あなたとアーノルドは、それぞれ「秘密の色」の代わりに「秘密の数値」を選ぶ。
ステップ２　2人のどちらかが「公開の数値」（絵具混合トリックのときの公開色の代わり）を公表する。
ステップ３　秘密の数値（４）と公開の数値（７）を掛け合わせて、「公開秘密混合値」の28を得る。アーノルドも、自分の秘密の数値について同じことを行う。6×7で42という公開秘密混合値を発表する。
ステップ４　アーノルドの公開秘密混合値の42を取り、それに自分の秘密の数値である4を掛け、「共有された秘密値」である168を得る。
一方、アーノルドはあなたの公開秘密混合値の28を取り、自分の秘密の数値の6を掛け、28×6=168で、驚くべきことに同じ「共有された秘密値」を得る。

実際に使われている絵具混合
完全なものにするためには、簡単に実行できて（絵具を混ぜ合わせるように）、取り消しが実質的に不可能な（絵具の分解のように）数学処理が必要である。コンピュータで実際にこれを行うとき、混合処理は「離散べき乗」、分解処理は「離散対数」と呼ばれる。
通鍵暗号方式における鍵の受け渡しを安全に行うために提案されたDiffie-Hellman鍵共有。絵具混合という方法によってわかりやすく説明されている。イメージがつかみやすい説明で一度イメージを掴めば忘れないだろう。

■誤り検出と誤り訂正のニーズ
コンピュータには、基本的な仕事が3つある。もっとも重要な仕事は、計算を実行することだ。コンピュータが実行するほかの２つの非常に重要な仕事がなければ、答えを計算できる能力があっても何の役にも立たないだろう。その２つとは、データを保存する仕事とデータを伝送する仕事だ。
20Mバイトのプログラムをダウンロードしたときに、システムが100万字に1つずつ解釈を誤ったとすると、ダウンロードしたプログラムには20個を超える誤りが含まれることになる。これらの誤りは、どれも予想外のタイミングでシステムをクラッシュさせる要因になり得る。
誤り検出、誤り訂正は大学でも学んだ分野。こちらも誰でもイメージが掴めるように説明をしている。もう少し深く知りたいと思う分野であったため、内容は少し物足りないものだったが、概要を思い出すには十分であった。

■ロスなし圧縮　―　究極のフリーランチ
コンピュータは、「ロスなし」と「ロスあり」の２つの大きく異なるタイプの圧縮を使っていることをまず覚えておこう。ロスなし圧縮アルゴリズムは、データファイルを受け付けると、もとのサイズの数分の1に圧縮する。そして、圧縮を解除するとまったく同じものが復元される。ロスあり圧縮は、圧縮を解除したあと、もとのファイルとは少し違うものになってしまう。
ロスなし圧縮を見ていこう。基本的なアイデアは、互いに同じになっている部分を見つけ、何らかのトリックを使ってその部分をもっと効率よく記述するということだ。データに反復が含まれているときには、このような圧縮は特に簡単である。このトリックをRLEと呼んでいる。反復する一続きの部分（run）に反復の長さ（length）を添えて符号化（encoding）しているという意味だ。
RLEの最大の問題点は、データ内の反復箇所が隣り合っていなければならないことである。そこで、コンピュータ科学たちは、基本的な発想をそのまま使いつつ、反復が隣り合っていなくてもうまく機能するより高度なトリックをいくつも考え出した。「前と同じ」、「より短いシンボル」の2つだけを見ていく。

―「より短いシンボル」のトリック
よく使われる文字については短いコードを使うようにしてみよう。一部のコードを長くするのである。
ステップ１　「前と同じ」のトリックを使ってもとの圧縮されていないファイルを変換する。
ステップ２　変換後のファイルを解析して、頻繁に登場するシンボルを見つける。頻繁に使われるシンボルには短い数値コード、あまり使われないシンボルには長い数値コードを与える。
ステップ３　ステップ２で作った数値コードを使ってファイルを変換する。
圧縮も興味深い分野の１つ。こちらもイメージを掴めるように、とても分かりやすく説明されている。これももう少し深くまで入っていきたい分野だったので、もう少し他の専門書で学んでみたいと思う。

【1読書1アウトプット】
イメージを大事にする

[michi66fさんの感想 · 2014年1月4日]

実際にプログラミングするための技術書ではない。しかし、（社会的に影響力のある各種）アルゴリズムの「妙」を平易な言葉でうまく伝えている。そこに美学を感じられるかどうかは人それぞれだろう。自分は十分共感するので星五つ。
どの章もわかりやすく面白いが、一風変わった（ゲーデルの不完全性定理とも絡んでいると思われる）「実現不可能なプログラムの存在証明」の章が一番印象的。

[eweyunさんの感想 · 2014年1月3日]

アルゴリズム勉強中の身。一般人。
この本は気に入ったので購入

[kazuhiroyanagiさんの感想 · 2013年9月1日]

・普通のコンピュータユーザーが毎日使っている。
・現実の世界の具体的な問題を解決する。
・CPUやネットワークなどのハードウェアではなくコンピュータ科学理論に関係がある。
　この３つの基準を満たすという条件で、世界でもっとも強力なアルゴリズムを９つ選んでいる。タイトルの原文は"Nine Algorithms that Changed the Future"となっている。原文どおり”未来を変えた”と言った方が何が基準であるかがわかりやすいかもしれない。
　9つは次の通りで読者は専門家でない一般のコンピュータユーザを対象としている。

1. 検索エンジンのインデクシング
2. ページランク
3. 公開鍵暗号法
4. 誤り訂正符号
5. パターン認識
6. データ圧縮
7. データベース
8. デジタル署名
9. 決定不能性

　難しい前提知識は必要なく、一般的な知識と論理だけで説明されていて非常にわかりやすい。公開鍵暗号法では素因数分解と言ってしまえば分かる人が多いと思うが、それは使わず”混ぜた絵具”で説明しているということでもそれがわかる。
　この本ではアルゴリズムの中心となる部分を”トリック”とよんでいる。そのため、話の展開が手品の種明かしのように進み、より話に惹きつけられる。

　基本的にはコンピュータを仕事としている者として知っていて当たり前な内容だ。しかし、恥かしながら、成程と思うところが多数あった。検索エンジンのインデクシングではフレーズ（句）の検索のトリックは知らなかった。当然であるが、フレーズそのものがインデックスと登録されているというトリックではなかった。
　一番興味深かったのはパターン認識の部分である。ニューラルネットワークを使い決定木を解くというアルゴリズムを初めて理解した。　

　知識が定着していない若手IT技術者に是非薦めたい。
写真: 【世界でもっとも強力な９つのアルゴリズム】・普通のコンピュータユーザーが毎日使っている。・現実の世界の具体的な問題を解決する。・CPUやネットワークなどのハードウェアではなくコンピュータ科学理論に関係がある。　この３つの基準を満たすという条件で、世界でもっとも強力なアルゴリズムを９つ選んでいる。タイトルの原文は"Nine Algorithms that Changed the Future"となっている。原文どおり”未来を変えた”と言った方が何が基準であるかがわかりやすいかもしれない。　9つは次の通りで読者は専門家でない一般のコンピュータユーザを対象としている。 1. 検索エンジンのインデクシング 2. ページランク 3. 公開鍵暗号法 4. 誤り訂正符号 5. パターン認識 6. データ圧縮 7. データベース 8. デジタル署名 9. 決定不能性 　難しい前提知識は必要なく、一般的な知識と論理だけで説明されていて非常にわかりやすい。公開鍵暗号法では素因数分解と言ってしまえば分かる人が多いと思うが、それは使わず”混ぜた絵具”で説明しているということでもそれがわかる。　この本ではアルゴリズムの中心となる部分を”トリック”とよんでいる。そのため、話の展開が手品の種明かしのように進み、より話に惹きつけられる。 　基本的にはコンピュータを仕事としている者として知っていて当たり前な内容だ。しかし、恥かしながら、成程と思うところが多数あった。検索エンジンのインデクシングではフレーズ（句）の検索のトリックは知らなかった。当然であるが、フレーズそのものがインデックスと登録されているというトリックではなかった。　一番興味深かったのはパターン認識の部分である。ニューラルネットワークを使い決定木を解くというアルゴリズムを初めて理解した。　 　知識が定着していない若手IT技術者に是非薦めたい。

[fishtrinityさんの感想 · 2013年6月10日]

ページランキングｎ説明は面白かったが、公開鍵暗号についてはサイモン・シンの「暗号解読」の方が分かりやすかった。事実により近い説明は本書なんだろうけど。

[tantanさんの感想 · 2013年6月2日]

ページランク、公開鍵暗号、２フェーズコミットなどIT系の人間にはある程度常識となっている著名なアルゴリズムを平易に解説している本。数式や抽象的な記述を極力排除した平易な解説が特徴なのだが、それが逆に少々まどろっこしいという印象もある。数式嫌いの人にはとても良い本だと思います。

個人的には第十章、決定不能性の章がおもしろかった。存在し得ないプログラム、を具体例を通して解説されておりとてもわかりやすい。全てのプログラムを対象としたクラッシュ検出プログラムというのが実現不能であることを具体例を通じてわかりやすく証明しています。チューリングなどが研究していた内容。要するに、”全てのプログラム”を対象とすると、プログラムには自分自身も含まれ、自己言及が発生するとおかしくなる、というのが肝だと思います。ゲーデルの不完全性定理などと通じるないようですね。ただ筆者も述べているように、”決定不能性がコンピュータの利用に及ぼす実際の影響はない”。あくまでも理論的な限界の追求ですね。なのであまり応用的な面では重要ではないのでしょうが、コンピュータ科学の理論としてはおもしろいと思います。

[voltekkuさんの感想 · 2013年5月19日]

所々に英訳が変な部分を感じた。英語特有の言い回しを感じた。
a.普通のコンピュータユーザーが毎日使っているアルゴリズム
b.現実の世界の具体的な問題を解決するアルゴリズム
c.コンピュータ科学理論に関係のあるアルゴリズム
の３つの基準で
１．検索エンジンのインデクシング、
２．ページランク、
３．公開鍵暗号法、
４．誤り訂正符号、
５．パターン認識、
６．データ圧縮、
７．データベース、
８．デジタル署名、
９．決定不可性
の９つを取り上げています。

[controlshotさんの感想 · 2013年3月16日]

良書です。普段意識することなく使っている「検索インデクシング」「ページランク」「公開鍵暗号」といったものが、いかによく考えられて作られたものかが分かりやすく説明されています。ここで紹介されているアルゴリズムが内含する論理一貫性やキメの細かさには、美しさが感じられるほどです。Kindleで発売されるのを待っていたのですが、待ちきれず書籍版を買って読んで正解でした。

[Togoさんの感想 · 2013年3月6日]

アルゴリズムの紹介が詳細で秀逸。知的好奇心が刺激される良書。