前書き

Incipit prologus in libro alghoarismi de practica arismetrice.

――Ioannis Hispalensis [John of Seville?], Liber algorismi de pratica arismetrice (c.1135)

友人であるあなたに、それを理解する方法を教えましょう。

それについての本を書くといい。

――Henry Home, Lord Kames (1696–1782), Sir Gilbert Elliot への手紙

個人は常に間違っている。彼は多くのものをデザインし、他人を助手として引き込み、そのいくらかあるいは全てと口論し、大きく失敗し、そして何かを成す。全体としてみれば多少の進歩があるが、その個人は常に間違っている。彼が幾分新しいことをしていたとしても、それが彼の意図通りであることはほとんどない。

――Ralph Waldo Emerson, "Experience", Essays, Second Series (1844)

以上がこの本の概要となる。ただし、本の基本計画の実現しつつ詳細を詰めるのはおそらく不可能だ。私が書いたのはこの本の暫定版の 2 番目か 3 番目の下書きに過ぎない。

――Michael Spivak, Differential Geometry, Volume I の第一版への前書き (1970)

この本について

この本はアルゴリズムの講義のために私が作成した講義ノートがもとになっています。私はイリノイ大学アーバナ・シャンペーン校でアルゴリズムの講義を 1999 年の 1 月から年に一つ程度担当しました。講義ノートは学部の理論カリキュラムの変更を受けて 2016 年に大幅に改訂されており、改訂された講義ノートから最も基礎的な部分を集めたのがこの本です。内容の多くは学部生向けの新しい必修の理論講義で触れるアルゴリズムに関する話題です。

前提知識

私がイリノイ大学で担当しているアルゴリズムの講義には、離散数学とデータ構造という二つの重要な前提講義があります。そのため多くの学生にとって、この教科書はデータ構造とアルゴリズムに関する最初の講義としては適していないでしょう。具体的には、私は次の事項に関する最低限の知識を仮定します:

本の中でこれらの前提知識が出てきたときには軽く触れますが、それ以降の内容に関する導入として触れることが多いです。詳細な内容については、無料で入手できる次の参考文献を強くお勧めします:

参考文献

この本や他の参考文献一つだけを見るということをしないでください。どんな知的対象を観察するときにも、著者と読者には自身の視座が存在します。全ての生徒と「馬が合う」教師は存在しませんし、特にできる生徒に限ったとしてもそのような教師は存在しません。自身の頭の中の直観を、あなたの頭に最も効率良くコピーできる著者を探すのは簡単なことではありませんが、長い目で見ればこの苦労は大きな価値を持ちます。

次にあげる参考文献には特に価値のある直観、例、練習問題、そして発想の源が含まれています。これで全てというわけではありません。

練習問題について

各章には練習問題がついています。ほとんどは宿題や試験、ゼミで少なくとも一度使ったものです。練習問題は難易度の順ではなく、テクニックやテーマに沿って並んでいます。一部の問題に付いているマークの意味は次の通りです:

練習問題は学習の機会として設けてあります。練習問題が必要だからとりあえず入れたというわけではありません。練習問題の目標はその特定の問題を解くことではなく、問題に関するテクニックを習得し、同じ種類の問題を全て解けるようになることです。こうした理由から、私は練習問題の解答をつけていません。解答は重要ではないからです。また「教師のためのマニュアル」もありません。もしあなたが自分で解けないなら、その問題を学生に解かせるべきではないでしょう。とは言っても、このセメスターに私が宿題として課した問題の解答は講義のウェブページで見つけることができますし、あなたが教師のためのマニュアルを作ることは何も問題ありません。

この本を盗もう！

この本1は Creative Commons Licence で公開されているので、オリジナルの入手場所を記載する限り、あなたは私の許可を得ることなく、この本を再配布したり、組み合わせたり、改変したりできます。この本の完全な電子版は次の場所から無料で入手できます:

この本のウェブページには本の内容に関連したより高度なトピックに関する追加の講義ノートが数百ページあります。加えてこれまでの宿題や試験、ゼミで使った問題のほぼ完全なアーカイブもあります。私はアルゴリズムの講義を担当するたびに指導資料を改訂、更新、ときには削除するので、ウェブサイトに行けば私が現在担当している講義についての最新版の講義ノートが手に入るかもしれません。

あなたが生徒であれ教師であれ、この教科書や他の講義ノートをあなたの授業で使うのは大歓迎です。私に許可を得る必要はありません ---そのために資料をウェブにおいているのですから！ ただし、この本を参考文献としてあげるようにしてください。名前でも 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



本の著者は自身の本に含まれる全ての欠陥に対する責任を受け入れることで懐の大きさを示すのが伝統になっているが、私はそうしない。この本に関する全ての間違い、不備、問題は誰か別の人物の責任である。しかしそれでもその報告は感謝して受け入れる。誰に責任があるのかを追及するためである。

――Steven S. Skiena, The Algorithm Design Manual (1997)

なぜイケてないかを説明した注釈付きの教科書リストがこの文章の後に続くことは間違いない。

――Adam Contini, MetaFilter, January 4, 2010

  1. 訳注: 英語版のこと。[return]

広告
このページの文章はテキストゆれないくんを使って校正されました。