開講情報
時間: 水曜2限 (10:40〜12:10)
場所: 情報科学研究棟201講義室
担当: 玉置 卓
オフィスアワー
随時受付
Microsoft Teams
23後_計算理論
チャット
メール
アポイントメントによる
対面 (情報科学研究棟)
ビデオ会議 (Teams, Zoom)
お知らせ
10/04 本ウェブページを公開しました
講義目的・到達目標 (シラバスより)
計算理論では「計算」を厳密に定義し, 計算可能性や計算効率を調べる枠組みを提供する
本講義では, 計算理論の基本的な話題である「オートマトンと言語の理論」、「計算可能性の理論」、「計算複雑さの理論」に親しむ
具体的には
種々の計算モデル (有限オートマトン、チューリング機械)
計算可能性
効率の良い計算、P対NP問題
について基本的な知識を習得する
講義スケジュールと資料
10/04 計算理論への導入 (1)
スライド (pdf)
10/11 計算理論への導入 (2)
スライド (pdf)
10/18 オートマトン (1)
スライド (pdf)
10/25 オートマトン (2)
スライド (pdf)
11/01 オートマトン (3)
スライド (pdf)
11/08 Turing機械 (1)
スライド (pdf)
11/15 Turing機械 (2)
スライド (pdf)
11/22 Turing機械 (3)
スライド (pdf)
11/29 中間試験 (レポート出題)
スライド (pdf)
12/06 計算(不)可能性 (1)
スライド (pdf)
12/13 (休講)
12/20 計算(不)可能性 (2)
スライド (pdf)
01/10 効率のよい計算
スライド (pdf)
01/17 クラスNPとNP完全性 (1)
スライド (pdf)
01/24 クラスNPとNP完全性 (2)
スライド (pdf)
02/07 期末試験 (+ 任意提出のレポート)
教科書
資料を配布する
参考書
Michael Sipser (著), 田中圭介, 藤岡淳 (監訳)『計算理論の基礎 [原著第3版]』共立出版 (1〜3巻) 目次
岩間 一雄『オートマトン・言語と計算理論』コロナ社
岩間 一雄『アルゴリズム理論入門』朝倉書店
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman『オートマトン言語理論 計算論』サイエンス社 (1〜2巻)
守屋悦朗『計算量理論 (電子版)』サイエンス社 (1〜2巻)
川添 愛『白と黒のとびら』東京大学出版会
川添 愛『精霊の箱』東京大学出版会 (上下巻)
成績評価 (シラバスより)
基準
基礎概念を理解できていること
理論的、数学的な話題に対して厳密な理解や説明ができること
方法 (対面で試験を行えない場合は変更する)
中間試験と期末試験による. それぞれを60点満点とし
min{100, 中間試験の素点+期末試験の素点}
を成績とする
リンク集
オートマトンと言語理論 (平田先生@九工大, スライド)
グラフとオートマトン (上原先生@JAIST, スライド)
計算論 (上原先生@JAIST, スライド)
計算量理論 演習問題 (河村先生@京大, 資料)
計算量理論入門――「複雑さ」をとらえる (河村先生@京大, スライド)
計算理論 (岡本先生@電通大, スライド)
CS101x (渡辺先生@東工大, 動画)
Tomoyuki Yamakami (山上先生@福井大, 動画)
Theory of Computation (Sipser先生@MIT, スライド&動画)
Automata, Computability, and Complexity Theory (Williams先生@MIT, スライド)
Stanford Automata (Ullman先生@Stanford, 動画)
Introduction to Theoretical Computer Science (Barak先生@Harvard, 資料)
CS251 Spring 2022 (Ada先生@CMU, 動画)
Undergrad Complexity Theory (O'Donnell先生@CMU, 動画)