計算量理論 - 理学部 - 東京大学授業カタログ

計算量理論

問題をコンピュータで計算によって解くときの本質的な計算量について、大規模問題でもそれなりに多項式時間アルゴリズムを有する問題クラスと、最悪どのようなアルゴリズムを考えても指数時間かかるであろう問題クラスの差を軸として、講究する。また、近年発展している量子計算に関しても解説する。

MIMA Search

授業計画

0. 計算量基礎、ソーティング計算量下限、行列乗算 1. 計算量、時間計算量、多項式時間vs.指数時間 2. Turing機械、時間計算量、クラスP、領域計算量、クラスPSPACE 3. 非決定性Turing機械、クラスNP、多項式時間還元 4. NP完全性による計算問題解析、数問題、動的計画法 5. 近似アルゴリズム、近似値比 6. ビンパッキング問題、巡回商人問題 7. ナップザック問題、PTAS、FPTAS 8. 加法的近似、近似不可能性、 9. co-NP、3典型問題、多項式階層、PSPACE完全、LOGSPACE 10. 量子計算モデル 11. 量子計算基礎：量子回路 12. 量子アルゴリズム 13. 量子計算量理論 14. 計算量理論まとめ

授業の方法

講義形式

成績評価方法

レポート課題によって評価を行う。追加のレポート提出がある場合はそれを加味する。

教科書

※

参考書

M. R. Garey and D. S. Johnson: Computers and Intractability --- A Guide to the Theory of NP-completeness. W. H. Freeman & Co., 1979. S. Arora and B. Barak: Computational Complexity: A Modern Approach. Cambridge University Press, 2009.

履修上の注意

本講義は合併科目であるため、工学部・理学部学生については、それぞれの所属学部の科目で履修登録すること。工学部・理学部以外の学生については、理学部科目として履修登録すること。