謎犬の耳

「世界でもっとも強力な９のアルゴリズム」ジョン・マコーミック（長尾高弘訳）（日経BP社）

大変面白く読みました。そっちの分野に進んだ娘にも読ませようかと思う。読んでくれるかどうかはわからないけど渡してみよう・・・。

P37 「検索エンジンのインデクシング」から。「人間は『NEAR』を使った検索をまず使わないが、検索エンジンはランキングの精度を上げるために、近接性情報を絶えず活用している。そして、検索エンジンが近接性情報を効率よく手に入れられるのは、単語の位置情報トリックを使っているからである。」この位置情報「トリック」というのは本書の中だけで有効な言葉だと思うが、彼は難しいアルゴリズムの本質を上手な比喩で説明する。それが「トリック」だ。

P56 「ページランク」から。「ランダムサーファートリックは、ハイパーリンクトリックとオーソリティートリックの使いたい特徴を組み合わせられるが、ハイパーリンクに循環情報が含まれていても機能するのだ。」P65からも以下を引用しておこう。「（実際の）検索エンジンは、ランダムサーファーをシミュレートしてページランク値を計算したりはしない。計算コストを大幅に下げつつ、ランダムサーファーシミュレーションと同じ結果が得られるように、数学的なテクニックを駆使した方法を使っている。ここでサーファーシミュレーションテクニックを学んだのは、直観的な魅力があるからであり、検索エンジンが何を計算しているのか（それをどのように計算しているかではなく）がよくわかるからである。」

P73 「公開鍵暗号方法」から。NHKの某番組でも量子暗号の放送時に同様の説明をしていたが、こちらの内容の方が数段わかりやすかった。「オープンな場で共有された秘密を作る方法」がここで比喩を持って説明される。「コンピュータ科学者たちはこの方法を『ディフィー＝ヘルマン鍵変換』と呼んでいるが、私たちは『絵具混合トリック』と呼ぶことにしよう。」内容は本書を読みましょう。

P85 絵具混合トリックを理解した上で、本書の中ではかけ算はわかるが割り算がわからない「世界」でそれを実現する方法が説明される。その上で・・・「コンピュータで実際にこれを行うとき、混合処理は『離散べき乗』、分解処理は『離散対数』と呼ばれる。そして、コンピュータが離散対数を効率よく計算する方法は見つかっていないので・・・」と続く。

P107 「誤り訂正符号」から。これなんかもこれまであんまり意識していなかった、コンピュータ内部のデータ伝送のお話だけど、わかりやすい事例で「冗長性トリック」を理解させてくれた。「数学者たちはこれよりもずっと冗長性が低く、しかも誤りの検出では非常に高い処理能力を示す符号語を編み出している。」

P138 「パターン認識」から。流行りの機械学習なんかともすごく関係する章だ。このページでは「決定木」＝「20の質問ゲーム」と導入がなされ、効率の良い「決定木」を作る方針が説明される。また決定木の説明で使った「雨傘問題」がニューラルネットワークではどのように表現されるのかがP146で示される。ここ、とてもわかりやすかった。

P172 「データ圧縮」から。ここは言葉では表現しにくいけれど「より短いシンボル」トリックは素晴らしいアイデアだと思う。

P197 「データベース」から。コンピュータ科学者たちが「ログ先行書き込み」と呼ぶ技術を「to-doリストトリック」として明快に解説される。

P243 「デジタル署名」から。ここは公開鍵暗号に似ているが、「信頼できる銀行」の存在が加わり、少し複雑だ。「掛け算鍵の問題点は、南京錠（非公開）から鍵（公開）を生成するトリック（基本的にユークリッドのアルゴリズム）を使って逆も完璧に生成できてしまうことである。」

P258 ここから始まる「決定不能性とはなにか」は、読み応えがあった。チャーチ＝チューリングのテーゼや停止性問題に関する内容だったが、今まで読んだ説明の中で一番丁寧な説明だったような気がする。P270に面白い例がある。「コンピュータプログラムがコンピュータのディスクにファイルとして格納されていること」からどんなプログラムも「自分自身を入力として実行できる」。その例として、WordでWinword.exeそのものを開いた場合の画面がP270に掲載されている。そんなことやってみようとも思わなかったので、目鱗だったし、それによって、以下の部分の理解がさらに進んだわけだ。

P284 「AntiYesOnSelf.exeはイエスノープログラムとして定義されている。つまり、必ず最後には『イエス』または『ノー』のどちらかの出力を生成するプログラムである。しかし、私たちは、特定の入力を与えると、AntiYesOnSelf.exeがどちらの出力も成績できないことを証明した。このような矛盾が起きるのは、私たちの最初の仮定が間違っていたのである。つまり、AntiYesOnSelf.exeのように動作するイエスノープログラムを書くことは『できない』。」

P285 ここから始まる「クラッシュ検出プログラムの不可能性」は、AntiYesOnSelf.exeの応用であり、AntiCrashOnSelf.exeという特殊なプログラムが存在し得ないことを示し、そのプログラムがあれば容易にプログラミングできるCanCrash.exe、すなわち「入力のプログラムがクラッシュを起こすものならばyesを出力」し、「入力プログラムが決してクラッシュを起こさないものならばnoを出力」するようなプログラムが存在できないことを証明している。さらに著者は、p290で、この「クラッシング問題」がチューリングの「停止性問題」とほとんど同じだと述べる。

P292 「私たちは、どんなコンピュータプログラムでも、すべてのプログラムのすべてのバグを見つけ出すことはできないということを精密に証明してみせた。しかし、私たちはほとんどのタイプのプログラムに含まれるほとんどのバグを見つけようとして、クラッシュ検出プログラムを書き続けることができる。実際、これはコンピュータ科学のなかでも積極的に研究が進められている分野である。」

​
世界でもっとも強力な9のアルゴリズム [ ジョン・マコーミック ]​