アルゴリズム・サイエンス:出口からの超入門

書籍情報
シリーズ名アルゴリズム・サイエンスシリーズ 全16巻 超入門編 【2】巻
ISBN978-4-320-12168-3
判型A5 
ページ数198ページ
発行年月2006年10月
本体価格2,400円
アルゴリズム・サイエンス:出口からの超入門 書影
アルゴリズム・サイエンス:出口からの超入門

 『出口からの超入門』というタイトルを頂戴したときに,ちょっとした戸惑いのあとで,みごとなネーミングであり,かつよくできた企画だと思うに至った。あるテーマ(たとえば量子計算,じつは量子計算は筆者の研究テーマのひとつでもある)を勉強するときに,基礎的事項(量子計算の場合は線形代数や初歩的量子力学など)を押さえておかないといけないのはもちろんであって,それが伝統的な「入口からの超入門」なのであろう。それを終了してから,順番に発展した内容に進んでいくことになる。しかし,そういった入口の勉強はしばしば忍耐を要求される。実際,線形代数が楽しいという人は,少なくとも筆者の周辺ではそれほど多くない。量子計算とどのように関連しているのかもよくわからないかもしれない。こうして辛抱ができずに,そのテーマ本来の部分に入る前に挫折してしまうというケースも多々あるのではなかろうか。
 そのような不幸を避けるために,もし量子計算の最先端の姿や古典計算よりも高速になる原理などの勉強が,上の入口からの勉強と同時進行的にできるなら,たいへん結構である。これがまさに出口からの超入門であろう。ただ,入口のほうがまだほとんど進んでいない読者を対象にするのであるから,注意深い記述が必要になることは明らかである。もちろん,一応の専門書であるからして,一般向けの解説書のように単に「雰囲気」のみを伝えるだけでは不十分であって,しっかりとした数学的な裏付けのある説明が要求されるのである。そんなことが可能なのであろうか。可能なのである。
 本書のテーマは,アルゴリズムである。比較的新しい学問ではあるが,それでも数十年の歴史があって,その基礎として勉強しなければならない事項はかなり整理されてきている。さまざまなデータ構造やアルゴリズムの基本テクニックの勉強がそれであって,本シリーズでも世界的権威である浅野哲夫先生が『入口からの超入門』として執筆されている。経験をつまれたプロの先生であるから,上で述べたような「忍耐」は必要ないと思われるが,それでもやはり,この『出口からの超入門』を,同時に(あるいは,むしろ先に)読んでいただけるなら勉強の楽しさが倍加すると信じている。
 計算機が誕生してからしばらくのあいだは,計算機の役割は「単純な」計算を「高速に」実行することに限定されていたといっても過言ではない。代表例が各種の表計算であり,そこで重要な役割を演じたのがソーティングである。でたらめに並んだ数を昇順に並べ替えるというのはきわめて単純な作業ではあるが,そのアルゴリズムに関しては優に1冊の本が書けるほどの研究が進んでいる。しかし,より「高度な」問題,たとえば将棋の対局とか,LSIの設計,列車ダイヤの作成といった問題に対しては,計算機は長いあいだほとんど無力であった。人間による「経験と勘の世界」が計算機を寄せつけなかったのである。
 1980年代から90年代にかけてこのような傾向は大きく変化してきた。従来,入り込めなかった分野にも計算機がどんどん進出してきたのである。その原因としては,もちろんハードウェア的進歩が大きい。しかし,そのハードウェアをどのように使うかというソフトウェアの進歩のほうが,より大きく貢献しているといわれているのである。さらには,そのソフトウェアの大きな部分を占めているのが,どのような手順で計算を進めればよいかを与えるアルゴリズムなのである(ハードウェアの進歩にしても,一般によくいわれる計算速度やファイルアクセス能力の進歩よりも,価格やサイズの低下に伴って誰でも自由に計算機が使えるようになったという面での進歩のほうが,よほど重要であると筆者は感じている)。
 本書では,そのように最近大きく変貌してきたアルゴリズムが,どのような局面でどのような役割を演じるのかを,いくつかの例題を通して見ていくことにする。くり返すが,本書は超入門なのであって,高校レベルの簡単な計算は出てくるかもしれないが,特別な知識はいっさい必要ない。また,読み進んでいただくとわかると思うが,上で言ったような計算機を利用するために必要であるという雰囲気があまり出てこないかもしれない。じつは,現代版のアルゴリズムは一昔前のせまい意味でのアルゴリズムとはちょっとちがっていて,要するにわれわれの生活に現れるさまざまなしくみに対して,「アルゴリズム的思考」によって解決策を提供するためのものなのである。このアルゴリズム的思考を言葉で説明するのは至難なのであるが,本書によってそれを身体で感じ取っていただければさいわいであり,それがまた本書の最大の目的でもある。
 いくつかの例題をとりあげると言ったが,その例題が少し「現実離れ」をしていると感じられるかもしれない。こんな問題がいったい何の役に立つのかと不審を抱いた読者の方がおられたとすれば,それはひとえに筆者の力不足以外の何物でもない。ただ,言い訳になるかもしれないが,本書はあくまで「考え方」のための本である。考え方をわかりやすく説明するためには単純なモデルを使用するのがもっとも早道であることは論を待たない。映画の原理を説明するために,少しずつ姿勢のちがった人の写真をパラパラと見せるようなものだと理解してほしい。
 本書を学部あるいは大学院の講義に使用していただける場面としては,以下の2つが典型的であろう。(i)情報・計算機系学科において,基本的データ構造などの入門講義のあとで多種多様なアルゴリズムの姿を勉強してもらう。(ii)非専門的学科(たとえば文系)でのアルゴリズムに関する講義に準備なしで用いる。(i)の場合はもちろん何の問題もない。(ii)の場合には,インストラクターの方に若干のお願いがある。最初の90分授業2回程度で,計算機のプログラムとはどんなものなのかを,簡単な例題(たとえばソーティング)を通して説明してほしい。プログラムとは何かがつかめれば,本書は何とかなる。難解な部分があったとしても,それは誰が悪いのでもない。ひたすら筆者の説明が悪いのである。ただ,さいわいなことに各章が完全に独立しているので,理解できない部分があれば単にスキップしてしまうことをお勧めしたい。また,時間数が足りない場合も,インストラクターの好みで自由に取捨選択していただければよい。
 もちろん,独学者の方も大歓迎である(というよりも,筆者の本意は数学好きの人が本書を寝転んで読んでアルゴリズムとは何なのかを知っていただき,アルゴリズム大好き人間になっていただくことなのである)。この場合も,難解な部分があれば,単にスキップしてほしい。そして,筆者に一言(怒りの)メールでもいただければさいわいである。その際に,こう書き直せばよりわかりやすいという指摘をいただければたいへんありがたい。
(「まえがき」より)

目次

第1章 ウォームアップ,その1
1.1 人事部長の悩み
1.2 増加部分列と減少部分列
1.3 最長の増加部分列を求めるアルゴリズム
1.4 まとめと出典

第2章 ウォームアップ,その2
2.1 共通テストの順位計算
2.2 平均点も計算しよう
2.3 まとめと出典

第3章 情報を漏らさない
3.1 情報を漏らさないで投票する
3.2 情報を漏らさないで証明する
3.3 電話でじゃんけんをする
3.4 まとめと出典

第4章 通信量を減らそう
4.1 通信複雑さ
4.2 中央値の計算
4.3 グラフ問題の計算
4.4 まとめと出典

第5章 乱数を利用する
5.1 グラフの塗り分け問題
5.2 グラフの支配集合
5.3 グラフの最大カット
5.4 平均からのずれ
5.5 まとめと出典

第6章 オンラインアルゴリズム
6.1 競合比解析
6.2 線形リストの探索
6.3 CNN問題
6.4 まとめと出典

第7章 近似アルゴリズム
7.1 ビン詰問題
7.2 集合被覆問題
7.3 分割問題
7.4 まとめと出典

第8章 厳密アルゴリズム
8.1 探索空間の矮小化
8.2 3SATに対する局所探索法
8.3 固定パラメータ容易性
8.4 まとめと出典

第9章 幾何の計算
9.1 コンビニの出店
9.2 博物館の監視員
9.3 まとめと出典

第10章 分散アルゴリズム
10.1 リーダー選挙
10.2 ウサギと猟師のゲーム
10.3 まとめと出典

第11章 オークション
11.1 正直なオークションと競合比
11.2 競合比有界なアルゴリズム
11.3 まとめと出典

第12章 ウェブクラブ
12.1 PageRank
12.2 確率行列
12.3 PageRankの計算
12.4 まとめと出典

第13章 利己的ルーティング
13.1 プライスのパラドックス
13.2 競合比の計算
13.3 線形の遅れ関数
13.4 まとめと出典

第14章 あとがきに代えて
14.1 弾力性のあるアルゴリズム
14.2 ネットワークコーディング
14.3 まとめと出典