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