timAlgo
松島先生主催のメカニズムデザイン勉強会で、 Stanford CS DepartmentのTim Roughgardenによる講義"A Second Course in Algorithms"のレクチャーノートを読むので、その成果物を挙げていきます。講義に出てきたアルゴリズムをちまちま実装していけたらなあ、と思っています。
"Chxx.ipynb"というファイルが、第xx回の講義に対応したノートになっています。
作ったものたち
- Chapter 01 BFS, A Naive Greedy algorithm, Ford-Fulkerson algorithm
- Chapter 02 Edmonds-Karp algorithm, Dinic's algorithm(未実装)
- Chapter 03 Push-Relabel algorithm
- Chapter 04 Bipartite Matching
- Chapter 05 The Hungarian Algorithm(とりあえず、簡単な例で動くことは確認)
- Chapter 06 PuLPというpythonの線形計画問題用ライブラリを動かしてみた
使用言語とか環境とか
Python 3系 + Jupyter Notebook を主に使います。 ノートを編集するには、Pythonやその周りの諸々を導入する必要があります。 導入は、Anacondaを用いると良いと思います。尾山ゼミのgithubページに解説があります。pyenv + anacondaだとなおよいです。
グラフ系のアルゴリズムを実装する際には、NetworkXを用います。
Pythonの練習
もし、Pythonを使ったことがないor不慣れな場合は以下のサイトが参考になると思います。
GoogleによるPythonの入門講義。サクッとPythonの文法を学ぶことができます。
2. Problem Solving with Algorithms and Data Structures using Python
Pythonの文法の解説（1にはないclassの解説がわかりやすいです）に加えて、基本的なアルゴリズムについて学ぶことができます。レベル的にも、"A Second Course in Algorithms"のprerequisiteに近いと思われます。
参考になりそうな文献
レクチャーノートを読んでいる中でわからないものが出てきた際に、参考にできそうな文献を挙げておきます。
データ構造とアルゴリズムの入門書です。薄いのでさらっと読めます。これでprerequisiteとして指定されている内容の 大部分はカバーできると思います。
分厚い。邦訳あり。
応用例などが豊富で、読んでいて楽しそう。特に、2章「アルゴリズム解析の基礎事項」と8章「NPと計算困難性」は参考になりそう。
これも分厚い。邦訳あり。
昔から定評のある教科書らしいです。（多分アルゴリズム版マスコレルみたいな感じです）CLRSと略されてたりします。
グラフ理論についての教科書。2章がレクチャーノート前半部分の内容を一部カバーしています。
単体法の解説がわかりやすいです。
東大の計数工の先生などによる最適化理論の本。
昔、東大計数工学科の最適化の授業（数理計画法）で教科書になってました。内点法について参考にしました。