| 年度 | 2006 |
|---|---|
| 科目名 | 計算の理論 |
| 教員名 | 松原 康夫 |
| 授業概要 | コンピュータ・サイエンスの中で、計算の理論は重要な位置を占める。この授業では、計算できるということが何を意味するかについて、いくつかのモデルを考え、結局はそれがある一つのモデルと等価であることを示す。また計算の手間の問題など、関連のある面白そうな話題を取り上げる。 |
| 授業計画 | ゲーデルの定理 計算モデル 帰納的関数 λカルキュラス Turingマシン 万能Turingマシン 手続きとアルゴリズム 停止問題 計算量の問題 多項式時間と指数時間 NP完全性 具体的な問題 その他の話題 セルオートマトン プログラムの理論 |
| 評価方法 | 基本的には期末試験の成績で評価するが、授業中のクイズや提出物等も考慮する。 |
| 教科書 | |
| 参考書 | |
| メッセージ | 計算できるということはどんなことだろう？コンピュータに関する理論は、高校までの数学とはまったく異なる世界である。情報科学のエッセンスを味わってみよう。 |