科目名 Course Title	計算量理論［26C5181］ Computational Complexity
授業言語 Language	Japanese
科目区分・科目種	情報科学科	クラス	情報科学科
コンピテンシー	◎批判的思考力，◎問題解決力	ｶﾗｰｺｰﾄﾞ
単位数	2.0単位	履修年次	3〜4年

担当教員	長尾　篤樹
学期	後期
曜日・時限・教室	金曜 3 〜 4 限 共3-408【情報科学講義室2】

受講条件・その他注意
授業スライドを用いた講義を行う．スライド上には演習問題をいくつか用意しているが，解答は提供していない．演習問題の答案を提示すれば採点・講評を添えて返事を行うが，これらは必須事項ではない．授業録画・オンライン併用の講義を行う予定である．

授業の形態
講義

教科書・参考文献
参考書：Michael Sipser著『Introduction to the Theory of Computation』ISBN:978-1133187790 参考書：Michael Sipser著『計算理論の基礎 [原著第2版] 2.計算可能性の理論』ISBN:978-4320122086（上述参考書の和訳版） 参考書：Michael Sipser著『計算理論の基礎 [原著第2版] 3.複雑さの理論』ISBN:978-4320122093（上述参考書の和訳版） いずれも購入の必要はない． 英語原著はPDFファイルがインターネット上に公開されている．

ＡＬＨ区分
ＡＬＨを実施しない

アクティブラーニングの技法
復習テスト，間違い探し

評価方法・評価割合
期末試験=期末試験60%，小論文（レポート）=第1回レポート=20%, 第2回レポート=20%

主題と目標
『言語理論とオートマトン』で確認した計算モデルを拡張することで，我々が普段利用しているプログラミングと同じ計算能力を持つチューリング機械を定義し，それが計算可能な範囲の限界（つまりは，我々が計算できる範囲の限界）を確認する． また，計算可能な範囲を「決定性」「非決定性」の違いや計算時間で区分し， その区分の下で展開される「P≠NP予想」がどのような問題であるのかを把握する． 全15回の授業を予定し、各種レポートと期末試験を課す予定である。

授業計画
第1回	ガイダンス，計算モデルの復習．
第2回	決定性チューリング機械
第3回	決定性チューリング機械の変種とその必要性
第4回	対角線論法
第5回	「計算できない」問題
第6回	「計算量」とは
第7回	決定性チューリング機械と計算量クラスP
第8回	検証機と計算量クラスNP
第9回	P vs. NP 問題とNP完全性
第10回	NP完全性の証明
第11回	さまざまなNP完全問題
第12回	PやNP周辺の計算クラス
第13回	複雑さの階層
第14回	NP完全問題な問題に対するアプローチ
第15回	計算量理論まとめ

時間外学習
授業スライドの予習，スライド上の演習問題への取り組みを期待する．また，参考書を各自で読み進めることでより深く広い理解を得られるため，こちらも推奨する．

学生へのメッセージ
言語理論とオートマトンで触れた計算モデルを拡張することで，我々が実際に扱うプログラミングの限界を確認することができます．また，その限界の範囲内で扱える問題とそうでない問題との区別を行えるようになることで，現実の問題へのアプローチも変わってきます。本講義を通して，「この問題にはどうアプローチすべきか」を肌感覚で身に付けられれば幸いです。

学生の問い合わせ先
基本的にはSlack（Ochat）上での授業チャンネルやDMで連絡をとること． メール：a-nagao@is.ocha.ac.jp 居室：理学部3号館401室