情報理工学III（計算と情報の理論）
- 2018年度 秋学期 木曜 1時限（9:15〜10:45）
- 12号館 402講義室
- 登録コードSIC20501
計算理論 第3回（12月6日）
計算理論 第3回（12月6日）
- 非正規言語とTuring機械（完全版）
- 8ページ目の1行目，「決定的」→「決定性」
- 24ページ，「simbol」→「symbol」
- 前回の非決定性有限オートマトンの14ページ，28から32ページ，34ページ以降を説明した後で，今回の説明をします．
計算理論 第4回（12月13日）
計算理論 第4回（12月13日）
- アルゴリズムと停止問題（完全版）
- 8ページ，17世紀→19世紀
- 14ページ，「板書で図示する」→「後述する」
- 15ページ，∈と∉が逆
- 「非正規言語とTuring機械」の16ページから説明します．
計算理論 第5回（12月20日）
計算理論 第5回（12月20日）
- 「アルゴリズムと停止問題」の7ページから話します．
- Turing機械に関するいい感じのページ（Turing機械をExcelで実現，Turing機械を物理的に実現，Turing機械を木製機械で実現)
計算理論 第6回（1月10日）
計算理論 第6回（1月10日）
- PとNP（完全版）
- 多項式とそれより上の計算時間の違いが挿入された講義資料
- 講義時と表が異なりますがご容赦ください．スライド1枚に収めるためです．（しかもリンクが間違っておりました．1/23日の深夜に修正しました．期末試験には影響ないものと思います．）
- 多項式とそれより上の計算時間の違いが挿入された講義資料
計算理論 第7回（1月17日）
計算理論 第7回（1月17日）
- NP-完全，NP-困難（完全版）
- 17ページの定義，「あらゆる判定問題を……」→「あらゆるNP問題を……」
- 今回は「PとNP」の31ページから説明します．