【授業の目的】
計算機で解決が求められる様々な問題について，その問題が計算機にとって本質的に「難しい」のか「簡単」なのかを，計算時間やメモリ領域といった評価尺度に基づいて理論的に解析する計算理論について講義する．
【授業の到達目標】
(1) PやNPを始めとする，様々な計算量クラスの定義と意味を理解する．
(2) P vs. NP予想に代表される，計算量クラスに係る数学的命題や予想の意味を理解する．
【授業概要（キーワード）】
チューリング機械，論理回路，計算時間
【科目の位置付け】
本科目は「計算理論」を基礎とする・
【授業計画】
・授業の方法
講義形式で行うが，演習も随時実施する．
・日程
第1回:イントロダクション
第2回:チューリング機械と計算
第3回:クラスP,EXP
第4回:クラスNP
第5回:帰着とNP完全
第6回:様々なNP完全問題
第7回:P vs. NP
第8回:回路計算量1
第9回:回路計算量2
第10回:クラスcoNP, Sigma_2,Pi_2,NEXP
第11回:領域計算量とクラスPSPACE
第12回:クラスL,NL
第13回:PSPACE = NPSPACE
第14回:乱択アルゴリズムとクラスBPP
第15回:数え上げ問題とクラス#P,#P完全
上記は予定であり，変更もありうる．
【学習の方法】
・受講のあり方
分からない部分がある時は，納得するまで積極的に質問すること．
・授業時間外学習へのアドバイス
公開される講義資料をもとに復習を行うこと．
【成績の評価】
・基準
様々な計算量クラスの定義と意味をきちんと理解していること，またそれらに関わる数学的命題をきちんと理解していることを合格の基準とする．
・方法
小テストと期末レポートにより，評価する．
【テキスト・参考書】
特に使用しない．
【その他】
・オフィス・アワー
金曜 16:00 ～ 17:00
|