計算理論

授業科目名 （英文名） 計算理論 （社会情報・専門科目） (T heory of Computation) 科目区分 対象学生 ※ 単位数 2.00 開講年次・ 学期 ３年次・後期 担当教員 玉置 卓 所属 社会情報科学部 ｵﾌｨｽｱﾜｰ・場所 ※ 連絡先 ※ 講義目的及び到達目標 計算理論では「計算」を厳密に定義し、計算可能性や計算効率を調べる枠組みを提供 する。 本講義では、計算理論の基本的な話題である「オートマトンと言語の理論」、「計算 可能性の理論」、「計算複雑さの理論」に親しむ。 具体的には 1. 種々の計算モデル (有限オートマトン、チューリング機械) 2. 計算可能性 3. 効率の良い計算、P対NP問題 について基本的な知識を習得する。 講義内容・授業計画 1. 計算理論への導入 (1) 2. 計算理論への導入 (2) 3. オートマトン (1) 4. オートマトン (2) 5. オートマトン (3) 6. Turing機械 (1) 7. Turing機械 (2) 8. 中間試験 9. Turing機械 (3) 10. 計算(不)可能性 (1) 11. 計算(不)可能性 (2) 12. 効率のよい計算 13. クラスNPとNP完全性 (1) 14. クラスNPとNP完全性 (2) 15. まとめ 16. 期末試験 テキスト 資料を配布する 参考文献 Michael Sipser (著), 太田和夫, 田中圭介 (監訳)『計算理論の基礎 [原著第2版]』共立出版 (1∼3巻) 成績評価の基準・方法 基準 基礎概念を理解できていること 理論的、数学的な話題に対して厳密な理解や説明ができること 方法 中間試験と期末試験による。それぞれを60点満点とし min｛100, 中間試験の素点+期末試験の素点｝ を成績とする 履修上の注意・履修要件 データ構造とアルゴリズム (もしくはそれらに相当する科目) を履修していること。 当授業は、原則全ての授業を対面で実施する予定ですが、履修者人数によっては、新 型コロナウィルス感染症対策として、履修者を複数の教室に分けて教室間をオンライ ンで繋ぐ方法や、対面授業と自宅でのオンライン授業を実施する方法とする場合があ り、自宅等でオンライン授業の受講を視聴できる通信環境（PC・タブレット等の端末 やWi-Fi環境）が必要となる場合があります。最終的な授業方法は履修登録後に決定・ 連絡します。 実践的教育 該当しない 備考 講義の進度により内容を変更することがある