情報理工学III(計算と情報の理論)

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

計算理論 第1回(11月22日)

計算理論 第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日)

レポート課題1(予定)

計算理論 第6回(1月10日)

  • PとNP

計算理論 第7回(1月17日)

  • NP-完全,NP-困難