計算基礎論[22C5042]

科目名
Course Title
計算基礎論[22C5042]
Theory of Computation
授業言語
Language
Japanese
科目区分・科目種 情報科学科 クラス 情報科学科
CCBM キャリアデザイン  
単位数 2.0単位 履修年次 34

担当教員 長尾 篤樹
学期 後期
曜日・時限・教室
金曜 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ファイルがインターネット上に公開されている.

ALH区分
通常授業として実施(11・12限等)

評価方法・評価割合
期末試験=中間試験25%,中間試験=期末試験25%,小論文(レポート)=中間レポート25%,ALH(アクティブ・ラーニング・アワー)=期末レポート相当25%

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

授業計画
第1回
ガイダンス,計算モデルの復習.
第2回
決定性チューリング機械
第3回
チャーチ・チューリングの提唱
第4回
判定可能性
第5回
「計算できない」問題
第6回
中間試験
第7回
計算の複雑さを定義するために
第8回
決定性チューリング機械と計算量クラスP
第9回
非決定性チューリング機械と計算量クラスNP
第10回
P vs. NP 問題とNP完全性
第11回
時間ではなく領域に着目する
第12回
複雑さの階層
第13回
NP完全問題な問題に対するアプローチ

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

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

学生の問い合わせ先
メール:a-nagao@is.ocha.ac.jp
居室:理学部3号館401室