情報理工学III（計算と情報の理論）

• 2018年度 秋学期 木曜 1時限（9:15〜10:45）
• 12号館 402講義室
• 登録コードSIC20501

計算理論 第1回（11月22日）

• 計算の理論を学ぶ意義
• オートマトンと正規言語（講義版，完全版）
  • オートマタの例（1, 2, 3, 4）

計算理論 第2回（11月29日）

• 非決定性有限オートマトンと正規表現（講義版，完全版）
  • 本日の講義で，非決定性有限オートマトンの状態遷移図の使い方の説明を間違えてしまいました．文字列εで移動する場合には元の状態にも残ります．完全版のスライドには状態の遷移のトレースのページを加えました．

計算理論 第3回（12月6日）

• 非正規言語とTuring機械（完全版）
  • 8ページ目の1行目，「決定的」→「決定性」
  • 24ページ，「simbol」→「symbol」
  • 前回の非決定性有限オートマトンの14ページ，28から32ページ，34ページ以降を説明した後で，今回の説明をします．

計算理論 第4回（12月13日）

• アルゴリズムと停止問題（完全版）
  • 8ページ，17世紀→19世紀
  • 14ページ，「板書で図示する」→「後述する」
  • 「非正規言語とTuring機械」の16ページから説明します．

計算理論 第5回（12月20日）

• 「アルゴリズムと停止問題」の7ページから話します．
  • Turing機械に関するいい感じのページ（Turing機械をExcelで実現，Turing機械を物理的に実現，Turing機械を木製機械で実現)

レポート課題1（予定）

計算理論 第6回（1月10日）

• PとNP

計算理論 第7回（1月17日）

• NP-完全，NP-困難