| 年度 | 2010 |
|---|---|
| 科目名 | 計算の理論 |
| 教員名 | 松原 康夫 |
| 授業概要 | コンピュータ・サイエンスの中で、計算の理論は重要な位置を占める。この授業では計算できるということが何を意味するかについて、いくつかのモデルを考え、結局はそれがある一つのモデルと等価であることを示す。また、計算の手間の問題など、関連のある話題を取り上げる。 |
| 授業計画 | 計算モデル Nプログラム whileプログラム 原始機能的関数 帰納的関数 Turingマシン 手続きとアルゴリズム 万能Turingマシン 停止問題 計算の複雑さ 多項式時間 指数関数時間 NP問題 |
| 評価方法 | 基本的に期末試験の成績による。期末試験では、以下の様なポイントを見る。①各計算モデルが理解できているか、②具体的な計算が実行できるか、③計算できるということはどのようなことか、④計算できない問題が存在すること、⑤現実的な意味で計算できるということは何か。 |
| 教科書 | |
| 参考書 | |
| メッセージ | 計算できるということはどういうことだろう？手続きとアルゴリズムの違いは何か？また、原理的に計算できることと、現実的に計算できることの違いを知ろう。 コンピュータの理論的な分野は、高校までの数学とはまったく別世界である。情報科学のエッセンスを味わってみよう。 |