アルゴリズム設計論 (130004) Advanced Algorithm Design (130004)
 
◇ 担当教員 Instructor : 大下 福仁(Fukuhito Ooshita / おおした ふくひと)、 井上 美智子(Michiko Inoue / いのうえ みちこ)
◇ 単位数 Credits : 1単位 ◇ 選択・必修 Required/Elective : 選択 ◇ 講義室 Room : L2
◇ 講義スタイル Style : 講義/公開
◇ 開講時期 Quarter : Ⅱ期 金曜1限

◇ 授業目的 Course goals : 現実に直面する組合せ最適化問題には、実用的な時間で最適解を求められそうにないものが多いことが知られている。本講義では、そのような計算困難問題に対する現実的なアルゴリズムの設計手法を学習する。また、計算困難さを計る尺度として重要な概念であるNP完全性についても学習する。

We face many combinatorial optimization problems in daily life, but it is known that most of them cannot be solved in practical time. In this lecture, we study several techniques to design practical algorithms for such hard problems. In addition, we study the theory of NP-completeness to understand hardness of problems.
◇ 授業内容 Course description : 1. クラスPと多項式時間アルゴリズム (Class P and Polynomial-Time Algorithms)
2. クラスNPとNP完全 (Class NP and NP-Completeness)
3. 厳密アルゴリズム1 (Exact Algorithms I)
4. 厳密アルゴリズム2 (Exact Algorithms II)
5. 近似アルゴリズム1 (Approximation Algorithms I)
6. 近似アルゴリズム2 (Approximation Algorithms II)
7. 乱択アルゴリズム (Randomized Algorithms)
8. まとめと試験 (Conclusions and Examination)

◇ 教科書 Textbook : 特に指定しない。本ページで資料を配布する。
No designated textbook. The handouts are available from this page.
◇ 参考書 Reference materials : 1. J. Hromkovic, Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics (2nd Edition), Springer Berlin Heidelberg, 2010.
(訳本:和田,増澤,元木,計算困難問題に対するアルゴリズム理論,丸善出版,2012.)
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms (3rd Edition), The MIT Press, 2009.
(訳本:浅野,岩野,梅尾,山下,和田,アルゴリズムイントロダクション第3版,近代科学社,2013.)
3. D. P. Williamson, D. B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011.
(訳本:浅野,近似アルゴリズムデザイン,共立出版,2015.)

◇ 履修条件 Prerequisites : アルゴリズムとデータ構造、グラフに関する基礎知識があることが望ましい。
Students are desired to have basic knowledge on algorithms, data structures, and graphs.
◇ 成績評価 Grading : 試験(60%)およびレポート(40%)により評価する。
Students are evaluated by examinations (60%) and reports (40%).
◇ オフィスアワー Office Hours : 金曜日 16:50 - 18:20 (オフィス B412(2)室)。その他、アポイントを取ればいつでも。
Every Friday of the second semester 16:50 - 18:20 at Rooms B412(2), or anytime if appointed.
◇ 配布資料 Handouts : 現在、配布資料はありません。