アルゴリズム
|
作成日：1999-12-07
最終更新日：
|
アルゴリズムについての本の紹介です。これから少しずつ追加します。
D.E.Knuth:The Art of Computer Programming, Vol.1, Addison-Wesley
D.E.Knuth:The Art of Computer Programming, Vol.2, Addison-Wesley
D.E.Knuth:The Art of Computer Programming, Vol.3, Addison-Wesley
これらは持っているだけでいいはずだ。必要になったら調べることにしているが、
必要な時はまだ来ない。私が死ぬまで来ないのではないか。
浅野孝夫、今井浩：計算とアルゴリズム、オーム社
上記コルメンの教科書がいかにも合衆国的な何でもありの本であるとすれば、
こちらは要点のみを記述したいかにも日本的な本となっている。
オーム社文庫という、小さくて薄い本だが、密度の濃さは一級だった。
現在は、この本を拡充させた同じ題名の本が通常の版形で出ているが、こちらは未見である。
R.Sedgewick:Algorithms in C, Addison-Wesley
R.Sedgewick:Algorithms in C++, Addison-Wesley
上記二つはほぼ同等の内容。C++だからといっても、
クラスに特別意を払っているわけではない。
浅く、広く学ぶにはいい本だと思う。邦訳も近代科学社から出ている。
奥村晴彦:C言語による最新アルゴリズム事典, 技術評論社(1991)
実務面で非常に役に立っている。
小生が共著者として書いた論文の中で、この本を参考文献として挙げたほどだ。
この本は 1991 年の出版であるため、
残念ながら本の題名のうち「最新」が褪せつつある。
事実、インターネットの紹介ページでは誤って
「C言語によるアルゴリズム事典」としてある例も多い。
それはそれとして、
多くのアルゴリズムを参考文献と合わせてこれだけ紹介している本は貴重である。
文句などあろうはずもないのだが、それでも気になるところがいくつかある。
ただこれらの感想は、著者に向けるべきものというよりは、
読者自身（つまり私）が解決すべき課題である。
-
「グラフ」の項では、計算機でグラフを表すデータ構造の例として隣接行列が紹介されている。
隣接行列は、グラフが密である場合には都合がいいが、疎である場合はメモリの無駄遣いになる。
そこで、グラフが疎である場合に適したデータ構造の例が載せてあるとさらによかった。
そして、縦型探索や横型探索の項で、こうしたデータ構造による説明があるとありがたい。
-
「黄金分割法」と「 Fibonacci 探索」（フィボナッチ探索）は、
ともに一変数関数f(x)の最適化法であることが示されているとよかった。
なお、どちらも探索の収束のオーダーは同程度である。
対象の一変数関数が２階微分可能であれば、
微分した関数f'(x)に関してニュートン法が適用でき、収束が速い。
-
「ポリトープ法」では、解説の最後に
「もっとも、このような連続な偏導関数を持つ問題にはもっと収束の速い方法がある」
と解説されている。この方法についての言及がないのは寂しい。
私から補足すれば次の通りである。
このような非線形関数について最大値や最小値を探索する方法は、
非線形最適化と呼ばれる分野での成果がある。
連続な偏導関数を持つ問題では、共役勾配法や準ニュートン法が有名である。
特に、最小二乗法の形で表される解を求める問題では、
ニュートン法が使える。
なお、説明文に、「γが反値幅」とあるが、正しくは「γは半値幅」である。
-
アルゴリズムは本来、ライブラリとしての強度をもっているべきである。
すなわち、他のシステムから使われることを想定して、
実装すべきである。
しかし、記述例ではあまりこのようなライブラリ化は考慮されていない。
たとえば、「回帰分析」ではQR分解を用いる方式が提示されている。
これは数値的に安定なアルゴリズムなので望ましいことである。しかし、
この例では別の個所で例示されている「QR分解」のコードをライブラリとして呼び出していない。
もったいないことである。
同様の例は「スプライン補間」にも見られる。スプライン補間の係数を求めるときには、
３重対角な連立方程式を経由する。従って、スプライン補間のアルゴリズムで、
３重対角な連立方程式の関数（メソッド）を呼び出すようにしてもよかったのではないか。
この本は、奥村晴彦氏の著書「C による最新アルゴリズム事典」の改訂版にあたる。
今回は時代を反映してか、Java による記述に改められた。また、
扱いが多岐に渡ることによるからだろうか、著者が奥村氏を含め８人となった。
実際に使えるアルゴリズムをこれだけ集めた著書は、他にはないだろう。
手元において確認するのに、こんな便利な本はない。
おまけに、
この本のサポートページから、
プログラムがダウンロードできる。
Java 版になって増補された項目には、多倍長演算、暗号化、符号化などがある。
また、グラフィクスはJavaのライブラリ用に書き直されている。
この本については、
絶賛文(www.pas-net.jp)がある。
私の意見と全く同じである。
なお、この本の序には、「本文掲載ソースコードは（中略）ブラックボックスとして使うための
bullet-proof なライブラリではない」
とある。bullet-proof とは防弾の意味である。
仙波一郎:組み合わせアルゴリズム, サイエンス社
中身は面白い。再帰構造と再帰呼び出しを駆使した、
他では見かけないアルゴリズムが楽しめる。
David E. Goldberg:Genetic Algorithms in Search, Optimization, and Machine Learning,
Addison-Wesley
遺伝的アルゴリズムの元祖の本である。
藤重悟 編:離散構造とアルゴリズムI, 近代科学社
藤重悟 編:離散構造とアルゴリズムII, 近代科学社
室田一雄 編:離散構造とアルゴリズムIII, 近代科学社
室田一雄 編:離散構造とアルゴリズムIV, 近代科学社
藤重悟 編:離散構造とアルゴリズムV, 近代科学社
藤重悟 編:離散構造とアルゴリズムVI, 近代科学社
藤重悟 編:離散構造とアルゴリズムVII, 近代科学社
これらは学者の研究する第一線の学問であり、私ごときには手が出せない。
敬して遠ざけておく。
アルゴリズムの基礎がわかりやすく書かれている。記述が丁寧なのがありがたい。
記述のプログラム言語には PASCAL を使っている。これは教育用だからだろう。
付録には C 言語やLISPによるプログラムもあるが、
プログラミングのスタイルとしてはあまりよろしくない。
コメントを加えたりして実用に耐えるものにするのは読者の義務だ、ということだろうと理解した。
余談
最近、「勝利の方程式」とか「成功の方程式」という雑誌の見出しをよく見かける。
しかし、方程式を立てただけでは解が求められない。だから、本当は
「勝利のアルゴリズム」とか「成功のアルゴリズム」とすべきではないかと思う。
なお、googleで調べたところ、「勝利のアルゴリズム」、「成功のアルゴリズム」ともに、
１ページのみあった。このページが登録されるころには、
それぞれ２ページになるだろう。
まりんきょ学問所 ＞
コンピュータの本 ＞
アルゴリズム
MARUYAMA Satosi
