学部後期課程
過去（2013年度）の授業の情報です
学内のオンライン授業の情報漏洩防止のため，URLやアカウント、教室の記載は削除しております。
最終更新日：2025年4月21日
授業計画や教室は変更となる可能性があるため、必ずUTASで最新の情報を確認して下さい。
UTASにアクセスできない方は、担当教員または部局教務へお問い合わせ下さい。
最終更新日：2025年4月21日
授業計画や教室は変更となる可能性があるため、必ずUTASで最新の情報を確認して下さい。
UTASにアクセスできない方は、担当教員または部局教務へお問い合わせ下さい。
計算量理論
問題をコンピュータで計算によって解くときの本質的な計算量について、大規模問題でもそれなりに多項式時間アルゴリズムを有する問題クラスと、最悪どのようなアルゴリズムを考えても指数時間かかるであろう問題クラスの差を軸として、講究する。
0. 計算量基礎、ソーティング計算量下限、行列乗算
1. 計算量、時間計算量、多項式時間vs.指数時間
2. Turing機械、時間計算量、クラスP、領域計算量、クラスPSPACE
3. 非決定性Turing機械、クラスNP、多項式時間還元
4. Cook-Levin定理、NP完全性
5. Karp還元、3SAT, VCのNP完全性
6. NP完全性による計算問題解析、数問題、動的計画法
7. 擬多項式時間アルゴリズム、強NP完全
8. 近似アルゴリズム、近似値比
9. ビンパッキング問題、巡回商人問題
10. ナップザック問題、PTAS、FPTAS
11. 加法的近似、近似不可能性、
12. co-NP、3典型問題、多項式階層、PSPACE完全、LOGSPACE
13. 対話証明概説
14. 計算量理論まとめ
0. 計算量基礎、ソーティング計算量下限、行列乗算
1. 計算量、時間計算量、多項式時間vs.指数時間
2. Turing機械、時間計算量、クラスP、領域計算量、クラスPSPACE
3. 非決定性Turing機械、クラスNP、多項式時間還元
4. Cook-Levin定理、NP完全性
5. Karp還元、3SAT, VCのNP完全性
6. NP完全性による計算問題解析、数問題、動的計画法
7. 擬多項式時間アルゴリズム、強NP完全
8. 近似アルゴリズム、近似値比
9. ビンパッキング問題、巡回商人問題
10. ナップザック問題、PTAS、FPTAS
11. 加法的近似、近似不可能性、
12. co-NP、3典型問題、多項式階層、PSPACE完全、LOGSPACE
13. 対話証明概説
14. 計算量理論まとめ
時間割／共通科目コード
コース名
教員
学期
時限
0510021
計算量理論
今井 浩
火曜2限
マイリストに追加
マイリストから削除
講義使用言語
日本語
単位
2
実務経験のある教員による授業科目
NO
他学部履修
可
開講所属
理学部
授業の方法
講義形式
成績評価方法
試験およびレポート課題によって評価を行う。
試験を基本とし、レポート提出がある場合はそれを加味する。
履修上の注意
本講義は合併科目であるため、工学部・理学部学生については、
それぞれの所属学部の科目で履修登録すること。
工学部・理学部以外の学生については、理学部科目として履修登録すること。
