まえがき（pdf）

(1)

まえがき

『出口からの超入門』というタイトルを頂戴したときに，ちょっとした戸惑いのあとで，みごとなネーミングであり，かつよくできた企画だと思うに至った．あるテーマ（たとえば量子計算，じつは量子計算は筆者の研究テーマのひとつでもある）を勉強するときに，基礎的事項（量子計算の場合は線形代数や初歩的量子力学など）を押さえておかないといけないのはもちろんであって，それが伝統的な「入口からの超入門」なのであろう．それを終了してから，順番に発展した内容に進んでいくことになる．しかし，そういった入口の勉強はしばしば忍耐を要求される．実際，線形代数が楽しいという人は，少なくとも筆者の周辺ではそれほど多くない．量子計算とどのように関連しているのかもよくわからないかもしれない．こうして辛抱ができずに，そのテーマ本来の部分に入る前に挫折してしまうというケースも多々あるのではなかろうか．そのような不幸を避けるために，もし量子計算の最先端の姿や古典計算よりも高速になる原理などの勉強が，上の入口からの勉強と同時進行的にできるなら，たいへん結構である．これがまさに出口からの超入門であろう．ただ，入口のほうがまだほとんど進んでいない読者を対象にするのであるから，注意深い記述が必要になることは明らかである．もちろん，一応の専門書であるからして，一般向けの解説書のように単に「雰囲気」のみを伝えるだけでは不十分であって，しっかりとした数学的な裏付けのある説明が要求されるのである．そんなことが可能なのであろうか．可能なのである．本書のテーマは，アルゴリズムである．比較的新しい学問ではあるが，それでも数十年の歴史があって，その基礎として勉強しなければならない事項はかなり整理されてきている．さまざまなデータ構造やアルゴリズムの基本テクニックの勉強がそれであって，本シリーズでも世界的権威である浅野哲夫先生

(2)

vi ——まえがきが『入口からの超入門』として執筆されている．経験をつまれたプロの先生であるから，上で述べたような「忍耐」は必要ないと思われるが，それでもやはり，この『出口からの超入門』を，同時に（あるいは，むしろ先に）読んでいただけるなら勉強の楽しさが倍加すると信じている．計算機が誕生してからしばらくのあいだは，計算機の役割は「単純な」計算を「高速に」実行することに限定されていたといっても過言ではない．代表例が各種の表計算であり，そこで重要な役割を演じたのがソーティングである．でたらめに並んだ数を昇順に並べ替えるというのはきわめて単純な作業ではあるが，そのアルゴリズムに関しては優に1冊の本が書けるほどの研究が進んでいる．しかし，より「高度な」問題，たとえば将棋の対局とか，LSIの設計，列車ダイヤの作成といった問題に対しては，計算機は長いあいだほとんど無力であった．人間による「経験と勘の世界」が計算機を寄せつけなかったのである． 1980年代から90年代にかけてこのような傾向は大きく変化してきた．従来，入り込めなかった分野にも計算機がどんどん進出してきたのである．その原因としては，もちろんハードウェア的進歩が大きい．しかし，そのハードウェアをどのように使うかというソフトウェアの進歩のほうが，より大きく貢献しているといわれているのである．さらには，そのソフトウェアの大きな部分を占めているのが，どのような手順で計算を進めればよいかを与えるアルゴリズムなのである（ハードウェアの進歩にしても，一般によくいわれる計算速度やファイルアクセス能力の進歩よりも，価格やサイズの低下に伴って誰でも自由に計算機が使えるようになったという面での進歩のほうが，よほど重要であると筆者は感じている）．本書では，そのように最近大きく変貌してきたアルゴリズムが，どのような局面でどのような役割を演じるのかを，いくつかの例題を通して見ていくことにする．くり返すが，本書は超入門なのであって，高校レベルの簡単な計算は出てくるかもしれないが，特別な知識はいっさい必要ない．また，読み進んでいただくとわかると思うが，上で言ったような計算機を利用するために必要であるという雰囲気があまり出てこないかもしれない．じつは，現代版のアルゴリズムは一昔前のせまい意味でのアルゴリズムとはちょっとちがっていて，要するにわれわれの生活に現れるさまざまなしくみに対して，「アルゴリズム的

(3)

まえがき—— vii 思考」によって解決策を提供するためのものなのである．このアルゴリズム的思考を言葉で説明するのは至難なのであるが，本書によってそれを身体で感じ取っていただければさいわいであり，それがまた本書の最大の目的でもある．いくつかの例題をとりあげると言ったが，その例題が少し「現実離れ」をしていると感じられるかもしれない．こんな問題がいったい何の役に立つのかと不審を抱いた読者の方がおられたとすれば，それはひとえに筆者の力不足以外の何物でもない．ただ，言い訳になるかもしれないが，本書はあくまで「考え方」のための本である．考え方をわかりやすく説明するためには単純なモデルを使用するのがもっとも早道であることは論を待たない．映画の原理を説明するために，少しずつ姿勢のちがった人の写真をパラパラと見せるようなものだと理解してほしい．本書を学部あるいは大学院の講義に使用していただける場面としては，以下の2つが典型的であろう．(i)情報・計算機系学科において，基本的データ構造などの入門講義のあとで多種多様なアルゴリズムの姿を勉強してもらう．(ii) 非専門的学科（たとえば文系）でのアルゴリズムに関する講義に準備なしで用いる．(i)の場合はもちろん何の問題もない．(ii)の場合には，インストラクターの方に若干のお願いがある．最初の90分授業2回程度で，計算機のプログラムとはどんなものなのかを，簡単な例題（たとえばソーティング）を通して説明してほしい．プログラムとは何かがつかめれば，本書は何とかなる．難解な部分があったとしても，それは誰が悪いのでもない．ひたすら筆者の説明が悪いのである．ただ，さいわいなことに各章が完全に独立しているので，理解できない部分があれば単にスキップしてしまうことをお勧めしたい．また，時間数が足りない場合も，インストラクターの好みで自由に取捨選択していただければよい．もちろん，独学者の方も大歓迎である（というよりも，筆者の本意は数学好きの人が本書を寝転んで読んでアルゴリズムとは何なのかを知っていただき，アルゴリズム大好き人間になっていただくことなのである）．この場合も，難解な部分があれば，単にスキップしてほしい．そして，筆者に一言（怒りの）メールでもいただければさいわいである．その際に，こう書き直せばよりわかりやすいという指摘をいただければたいへんありがたい．

(4)

viii ——まえがき本書の出発点は，2004年に文部科学省科学研究費特定領域研究「新世代の計算限界−その解明と打破−」プロジェクトがスタートしたことである．いくつかの行動計画の中で，アルゴリズム全般を網羅するシリーズを刊行するという話が持ち上がり，共立出版の小山透氏の全面的支援を得ることができた．しかし，実現までの道程は平坦ではなく，いくつかの試練があった．粘り強い努力を重ね，各種調整に多くの時間を割いてくださった小山氏ならびに編集委員の皆様に衷心より感謝申し上げる次第である．筆者が京都大学大学院情報学研究科発足以来行っている「離散アルゴリズム理論」の講義ノートが本書の基になった．情報学研究科は文系から数学まで幅広い学生を受け入れているので，代表的項目に関して「基礎科目」というジャンルを設けており，本講義はそのひとつである．ほとんどが書き下しであるが， 2.1節，6.2節，8.3節，13.1節，14.1節，14.2節の内容は筆者がすでに発表している学会誌の解説記事や教科書の内容を含んでいる．しかし，いずれも改訂増強を行っていることを明記したい．最後になってしまったが，本書の草稿の段階で，九州産業大学の朝廣雄一博士と京都大学の西村治道博士に読んでいただいた．筆者の乱暴な記述にもかかわらず，ていねいに読んでいただき，心もこもった多くのご意見を頂戴した．心から感謝したい． 2006年初夏岩間一雄