前書き
Incipit prologus in libro alghoarismi de practica arismetrice.
友人であるあなたに、それを理解する方法を教えましょう。
それについての本を書くといい。
個人は常に間違っている。彼は多くのものをデザインし、他人を助手として引き込み、そのいくらかあるいは全てと口論し、大きく失敗し、そして何かを成す。全体としてみれば多少の進歩があるが、その個人は常に間違っている。彼が幾分新しいことをしていたとしても、それが彼の意図通りであることはほとんどない。
以上がこの本の概要となる。ただし、本の基本計画の実現しつつ詳細を詰めるのはおそらく不可能だ。私が書いたのはこの本の暫定版の 2 番目か 3 番目の下書きに過ぎない。
この本について
この本はアルゴリズムの講義のために私が作成した講義ノートがもとになっています。私はイリノイ大学アーバナ・シャンペーン校でアルゴリズムの講義を 1999 年の 1 月から年に一つ程度担当しました。講義ノートは学部の理論カリキュラムの変更を受けて 2016 年に大幅に改訂されており、改訂された講義ノートから最も基礎的な部分を集めたのがこの本です。内容の多くは学部生向けの新しい必修の理論講義で触れるアルゴリズムに関する話題です。
前提知識
私がイリノイ大学で担当しているアルゴリズムの講義には、離散数学とデータ構造という二つの重要な前提講義があります。そのため多くの学生にとって、この教科書はデータ構造とアルゴリズムに関する最初の講義としては適していないでしょう。具体的には、私は次の事項に関する最低限の知識を仮定します:
-
離散数学: 高校レベルの代数、対数の公式、 初等的な集合の理論、ブール代数、一階の命題論理、集合、関数、同値関係、半順序、モジュロ算術、再帰関数、(データ構造ではなく、抽象的な物としての) 木、(頂点と辺を持つ、関数をプロットしたものではない方の) グラフ。
-
証明技法: 直接、間接、背理法、場合分け、帰納法 (特に "強く" て "構造的" な帰納法)。第 0 章は帰納法を使います。そして第 \(n - 1\) 章が帰納法を使うならば第 \(n\) 章も帰納法を使います。
-
手続き的なプログラミングの概念: 変数、条件文、ループ、レコード、間接参照 (アドレス、ポインタ、参照)、サブルーチン、再帰。特定のプログラミング言語を前提とすることはしませんが、間接参照と再帰をサポートする言語を少なくとも一つ使ったことがあると仮定します。
-
基礎的な抽象データ型: スカラー、配列、ベクタ、集合、スタック、キュー、マップ/辞書、順序付きマップ/辞書、優先度付きキュー。
-
基礎的な抽象データ構造: 配列、連結リスト (型方向/双方向および線形/環状)、二分探索木、少なくとも一つのバランスの取れた木 (AVL 木、赤黒木、treap、スキップリスト、スプレー木)、ハッシュテーブル、バイナリヒープ、そして一番重要なのが、ここであげた事項と一つ前にあげた事項の違いが理解できること。
-
基礎的な計算問題: 初等算術、ソート、探索、枚挙、木の走査 (行きがけ順、通り掛け順、帰りがけ順、高さ順など)。
-
基礎的なアルゴリズム: 初等的なアルゴリズム、線形探索、二分探索、ソート (選択、挿入、マージ、ヒープ、クイック、基数など)、幅および深さ優先の (少なくとも二分) 木の探索、そして一番重要なのが、ここであげた事項と一つ前にあげた事項の違いが理解できること。
-
初等的なアルゴリズムの解析: 漸近的な記法 (\(o, O, \Theta, \Omega, \omega\))、ループと累積和および再帰と反復の間の変換、単純な和と再帰の計算。
-
数学への慣れ: 抽象的で形式的な定義と証明 (特に再帰的な定義と帰納的な証明) を理解できること。数学的な議論を読み書きできること。構文的、意味論的、論理的に間違った文章を見つけ、自分では書かないようにすること。
本の中でこれらの前提知識が出てきたときには軽く触れますが、それ以降の内容に関する導入として触れることが多いです。詳細な内容については、無料で入手できる次の参考文献を強くお勧めします:
- Margaret M. Fleck. Building Blocks for Theoretical Computer Science. Version 1.3 (2013 年 1 月)。最新版は http://mfleck.cs.illinois.edu/building-blocks/ から入手できます。
- Eric Lehman, F. Thomson Leighton, and Albert R. Meyer. Mathematics for Computer Science, unpublished lecture notes, 最新の (パブリックな) 更新は 2018 年 6 月。https://courses.csail.mit.edu/6.042/spring18/ から入手できます (一番新しいバージョンを検索するようにしてください)。
- Pat Morin. Open Data Structures, 最新の更新は 2016 年 1 月 (edition 0.1G\(\beta\))。 Pat が管理し、定期的に更新する自由でオープンな教科書。http://opendatastructures.org/ から入手できます。
- Don Sheehy, A course in Data Structures and Object-Oriented Design. 最新の更新は 2019 年 2 月。https://donsheehy.github.io/datastructures/ から入手できます。
参考文献
この本や他の参考文献一つだけを見るということをしないでください。どんな知的対象を観察するときにも、著者と読者には自身の視座が存在します。全ての生徒と「馬が合う」教師は存在しませんし、特にできる生徒に限ったとしてもそのような教師は存在しません。自身の頭の中の直観を、あなたの頭に最も効率良くコピーできる著者を探すのは簡単なことではありませんが、長い目で見ればこの苦労は大きな価値を持ちます。
次にあげる参考文献には特に価値のある直観、例、練習問題、そして発想の源が含まれています。これで全てというわけではありません。
- Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. (私はライス大学の学部生としてこの教科書を使い、その後カリフォルニア大学アーバイン校の修士生としてもう一度使いました)
- Boaz Barak, Introduction to Theoretical Computer Science. Textbook draft, 最新の更新は 2019 年 6 月. (大昔の CS の教科書ではありません。新しいだけ内容が優れており、無料である点も素晴らしいです)
- Thomas Cormen, Charles Leiserson, Ron Rivest, and Cliff Stein. Introduction to Algorithms, third edition. MIT Press/McGraw-Hill, 2009. (カリフォルニア大学バークレー校で補助資料として使いました)
- Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani. Algorithms. McGraw-Hill, 2006. (おそらくこの本に一番近い内容ですが、説明がより簡潔です)
- Jeff Edmonds. How to Think about Algorithms. Cambridge University Press, 2008.
- Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
- Michael T. Goodrich and Roberto Tamassia. Algorithm Design: Foundations, Analysis, and Internet Examples. John Wiley & Sons, 2002.
- Jon Kleinberg and Éva Tardos. Algorithm Design. Addison-Wesley, 2005. (可能ならば図書館から借りましょう)
- Donald Knuth. The Art of Computer Programming, volumes 1–4A. AddisonWesley, 1997 and 2011. (両親が 14 才のクリスマスにこの本を買ってくれましたが、読んだのはずっと後になってからでした)
- Udi Manber. Introduction to Algorithms: A Creative Approach. AddisonWesley, 1989. (カリフォルニア大学バークレー校で補助資料として使いました)
- Ian Parberry. Problems on Algorithms. Prentice-Hall, 1995 (絶版). (https://larc.unt.edu/ian/books/free/license.html から入手可能ですが、チャリティーへ少額を寄付することに同意が必要です。同意は守りましょう)
- Robert Sedgewick and Kevin Wayne. Algorithms. Addison-Wesley, 2011.
- Robert Endre Tarjan. Data Structures and Network Algorithms. SIAM, 1983.
- カリフォルニア大学バークレー校での私が受け持った講義の講義ノート。特に Dick Karp と Raimund Seidel が担当した部分。
- 世界中の数えられない数の仲間によって作られた、ウェブで無料で入手できる講義ノート、スライド、宿題、試験、ビデオ講義、研究論文、ブログ記事、StackExchange の質問と回答、ポッドキャスト、そして本格的な MOOC。
練習問題について
各章には練習問題がついています。ほとんどは宿題や試験、ゼミで少なくとも一度使ったものです。練習問題は難易度の順ではなく、テクニックやテーマに沿って並んでいます。一部の問題に付いているマークの意味は次の通りです:
-
❤ 赤いハートは、問題が特に難しいものであることを示します。イリノイ大学における Ph.D. の適正試験で使われたものも多くあります。少数の極端に難しい問題は大きな赤いハート❤が付いています。
-
♦ 青いダイアモンドは、問題を解くのに以降の章の内容が必要になることを示します。テーマを考えるとその場所にあるのが適しているということです。一方で、以前の章の内容が必要になる問題にはマークがついていません。本は、人生と同じで、積み重なっていくものだからです。
-
♣ 緑色のクラブは、問題を解くのにこの本に含まれない内容に関する知識が必要になることを示します。例えば有限状態機械や線形代数、確率論、平面グラフといったトピックに関する知識です。このマークが登場するのは稀です。
-
♠ 黒いスペードは、問題を解いたりプログラムを書いたりするのに長い時間と大きな労力が必要になることを示します。このマークが登場するのは稀です。
-
★ オレンジ色の星を見つけたら、あなたは 1998 年以前に製造された Lucky Charms を食べているということです。おえっ。
練習問題は学習の機会として設けてあります。練習問題が必要だからとりあえず入れたというわけではありません。練習問題の目標はその特定の問題を解くことではなく、問題に関するテクニックを習得し、同じ種類の問題を全て解けるようになることです。こうした理由から、私は練習問題の解答をつけていません。解答は重要ではないからです。また「教師のためのマニュアル」もありません。もしあなたが自分で解けないなら、その問題を学生に解かせるべきではないでしょう。とは言っても、このセメスターに私が宿題として課した問題の解答は講義のウェブページで見つけることができますし、あなたが教師のためのマニュアルを作ることは何も問題ありません。
この本を盗もう!
この本1は Creative Commons Licence で公開されているので、オリジナルの入手場所を記載する限り、あなたは私の許可を得ることなく、この本を再配布したり、組み合わせたり、改変したりできます。この本の完全な電子版は次の場所から無料で入手できます:
- 本のウェブサイト http://jeffe.cs.illinois.edu/teaching/algorithms/
- 短縮 URL http://algorithms.wtf/
- バグ報告ページ https://github.com/jeffgerickson/algorithms
- Internet Archive https://archive.org/details/Algorithms-Je-Erickson
この本のウェブページには本の内容に関連したより高度なトピックに関する追加の講義ノートが数百ページあります。加えてこれまでの宿題や試験、ゼミで使った問題のほぼ完全なアーカイブもあります。私はアルゴリズムの講義を担当するたびに指導資料を改訂、更新、ときには削除するので、ウェブサイトに行けば私が現在担当している講義についての最新版の講義ノートが手に入るかもしれません。
あなたが生徒であれ教師であれ、この教科書や他の講義ノートをあなたの授業で使うのは大歓迎です。私に許可を得る必要はありません ---そのために資料をウェブにおいているのですから! ただし、この本を参考文献としてあげるようにしてください。名前でも http://algorithms.wtf/ へのリンクでもいいです。あなたが学生で、課題を解くのにこの本を使った場合、これはとても重要です (教師に確認を取るのも忘れないでください)。
一方であなたが教師なら、自分で書いた資料とともにこの本を使うことを強く勧めます。自分で資料を書けば講義内容に対する理解が深まり、講義のプレゼンテーションの質が向上し、結果的にあなたの生徒の理解が向上します。それにこの本の気に入らない部分も読まずに済みます。全ての教科書は クソ 不完全であり、この本も例外ではありません。
最後に、ぜひあなたの著作物をオープンなウェブで自由に、簡単に、世界中から利用可能にしてください。教育管理システムやペイウォールの後ろに隠さないでください。あなたのユニークな洞察を、他の学生や教師が得られるようにするためです。特に、もしこの教科書を補完する資料、例えばスライドや動画、解答マニュアルを書いた場合にはぜひ私に知らせてください。本のウェブサイトにあなたの資料へのリンクを載せます。
謝辞
この教科書はアルゴリズムの講義に関わった多くの学生、教師、研究者からの多大な貢献を受けています。特に、イリノイ大学でこの講義ノートを第一の参考文献として利用した 3000 人を超える学生には大きな謝辞を送ります。彼らは有用な (ときには手痛い) 批評を提供し、初期のひどい下書きに耐えてくれました。これらの講義ノートを自身の講義で利用し、有用なフィードバックやバグレポートを提供してくれた世界中の研究者や学生にも感謝します。
次にあげる素晴らしい TA からのフィードバックとコントリビューション (中でも練習問題に関するもの) に特に感謝します:
Aditya Ramani, Akash Gautam, Alex Steiger, Alina Ene, Amir Nayyeri, Asha Seetharam, Ashish Vulimiri, Ben Moseley, Brad Sturt, Brian Ensink, Chao Xu, Charlie Carlson, Chris Neihengen, Connor Clark, Dan Bullok, Dan Cranston, Daniel Khashabi, David Morrison, Ekta Manaktala, Erin Wolf Chambers, Gail Steitz, Gio Kao, Grant Czajkowski, Hsien-Chih Chang, Igor Gammer, Jacob Laurel, John Lee, Johnathon Fischer, Junqing Deng, Kent Quanrud, Kevin Milans, Kevin Small, Konstantinos Koiliaris, Kyle Fox, Kyle Jao, Lan Chen, Mark Idleman, Michael Bond, Mitch Harris, Naveen Arivazhagen, Nick Bachmair, Nick Hurlburt, Nirman Kumar, Nitish Korula, Patrick Lin, Phillip Shih, Rachit Agarwal, Reza Zamani-Nasab, Rishi Talreja, Rob McCann, Sahand Mozaffari, Shalan Naqvi, Shripad Thite, Spencer Gordon, Srihita Vatsavaya, Subhro Roy, Tana Wattanawaroon, Umang Mathur, Vipul Goyal, Yasu Furakawa, and Yipu Wang.
イリノイ大学の同じ学部の研究者との議論にも大きく助けられました: Alexandra Kolla, Cinda Heeren, Edgar Ramos, Herbert Edelsbrunner, Jason Zych, Kim Whittlesey, Lenny Pitt, Madhu Parasarathy, Mahesh Viswanathan, Margaret Fleck, Shang-Hua Teng, Steve LaValle, and especially Chandra Chekuri, Ed Reingold, and Sariel Har-Peled.
最初に行った講義の全体構成と講義ノートを書き残しておくというアイデアは Herbert Edelsbrunner を参考にしました。講義ノートを本にするというアイデアは Steve LaValle から、本のいくつかの部分についてのデザインは Robert Ghrist からのものです。
読者への注意
もちろん、この本のどんなミスもこれらの人物の責任ではありません。改定や編集を何度も経ているものの、この本にはいくらかの間違いやバグ、失礼な文章、省略、混乱を招く文章、誤植、数学的な間違い、文法上の間違い、論理的な間違い、ぼーっとしながら書いた文章、間違ったデザイン、歴史的な不正確さ、時代錯誤、矛盾、誇張、優柔不断、たわごと、曲解、行き過ぎた単純化、冗長な文章、無駄口、無意味な文章、ひどい文章、あからさまなウソ、が含まれています。一つ残らず全て Steve Skiena の責任です。
https://github.com/jeffgerickson/algorithms でイシュートラッカーを管理しています。本に関するバグ報告、機能の要望、一般的なフィードバックはここで行ってください。間違いを見つけたらぜひ知らせてください。数学的間違い、文法的間違い、歴史的間違い、誤植、文化的間違い、何でもいいです。本文についてでも、練習問題に関するものでも、ほかの講義ノートに関するものでも構いません。もちろん、ほかのフィードバックも歓迎します。
Enjoy!
— Jeff
献辞
For Kay, Kate, and Hannah
with love and admiration
And for Erin
with thanks
for breaking her promise
本の著者は自身の本に含まれる全ての欠陥に対する責任を受け入れることで懐の大きさを示すのが伝統になっているが、私はそうしない。この本に関する全ての間違い、不備、問題は誰か別の人物の責任である。しかしそれでもその報告は感謝して受け入れる。誰に責任があるのかを追及するためである。
なぜイケてないかを説明した注釈付きの教科書リストがこの文章の後に続くことは間違いない。
-
訳注: 英語版のこと。[return]