兵庫県立大学 社会情報科学部 専門教育科目「計算理論」講義ページ（2021年度）


開講情報

  • 時間: 水曜2限 (10:40〜12:10)

  • 場所: C棟 (教育棟II) 202講義室

  • 担当: 玉置 卓

  • オフィスアワー

    • 随時受付

      • Teams「21後_計算理論」

        • チャンネル「一般」質問用スレッド

        • チャット

      • メール

    • アポイントメントによる

      • 対面 (情報科学研究棟)

      • ビデオ会議 (Teams, WebEx, Zoom)


お知らせ

  • 10/05 本ウェブページを公開しました


講義目的・到達目標 (シラバスより)

計算理論では「計算」を厳密に定義し, 計算可能性や計算効率を調べる枠組みを提供する

本講義では, 計算理論の基本的な話題である「オートマトンと言語の理論」、「計算可能性の理論」、「計算複雑さの理論」に親しむ

具体的には

  1. 種々の計算モデル (有限オートマトン、チューリング機械)

  2. 計算可能性

  3. 効率の良い計算、P対NP問題

について基本的な知識を習得する


講義スケジュールと資料

  1. 10/06 計算理論への導入 (1)

  2. 10/13 計算理論への導入 (2)

  3. 10/20 オートマトン (1)

  4. 10/27 オートマトン (2)

  5. 11/03 オートマトン (3)

  6. 11/10 Turing機械 (1)

  7. 11/17 Turing機械 (2)

  8. 11/24 中間試験

  9. 12/01 Turing機械 (3)

  10. 12/08 計算(不)可能性 (1)

  11. 12/15 計算(不)可能性 (2)

  12. 12/22 効率のよい計算

  13. 01/05 クラスNPとNP完全性 (1)

  14. 01/12 クラスNPとNP完全性 (2)

  15. 01/19 まとめ

  16. 01/26 (金曜日の振替授業日)

  17. 02/02 期末試験


教科書

資料を配布する


参考書

  • Michael Sipser (著), 太田和夫, 田中圭介 (監訳)『計算理論の基礎 [原著第2版]』共立出版 (1〜3巻)

  • 岩間 一雄『オートマトン・言語と計算理論』コロナ社

  • 岩間 一雄『アルゴリズム理論入門』朝倉書店

  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman『オートマトン言語理論 計算論』サイエンス社 (1〜2巻)

  • 守屋悦朗『計算量理論 (電子版)』サイエンス社 (1〜2巻)

  • 川添 愛『白と黒のとびら』東京大学出版会

  • 川添 愛『精霊の箱』東京大学出版会 (上下巻)


成績評価 (シラバスより)

基準

  • 基礎概念を理解できていること

  • 理論的、数学的な話題に対して厳密な理解や説明ができること

方法 (対面で試験を行えない場合は変更する)

中間試験と期末試験による. それぞれを60点満点とし

min{100, 中間試験の素点+期末試験の素点}

を成績とする


リンク集