計算量理論  月曜日2時限

         担当: 竹田正幸(大学院システム情報科学研究院)



講義予定と講義資料(変更することがあります)
2017.04.10第1回 イントロダクション  
2017.04.17第2回 準備  
2017.04.24第3回 複雑さの測定
2017.05.08第4回 線形圧縮定理, 線形加速定理
2017.05.15第5回 RAMモデル
2017.05.22第6回 クラスP
2017.05.29第7回 クラスNP
2017.06.05第8回 NPに属する問題  
2017.06.12第9回 NPに属する問題(演習)  
2017.06.19第10回 NP完全性  
2017.06.26第11回 NP完全性の証明  
2017.07.03休講  
2017.07.10第12回 NP完全性の証明(つづき)  
2017.07.13第13回 Cook-Levinの定理  
2017.07.24第14回 まとめ