| 年度 | 2008 |
|---|---|
| 科目名 | アルゴリズム特論 |
| 教員名 | 松原 康夫 |
| 授業概要 | 命題論理および、述語論理を主なテーマとして取り上げる。命題論理は表現能力が小さいが決定可能性が高く、述語論理は表現能力が高いが決定できない問題があることを解説する。その過程でTuringマシンの概念と停止問題の決定不可能性を示し、計算の複雑さの概念にも触れる。以上のように理論的内容を解説するとともにJava言語を用いて、オブジェクト指向プログラミングの考え方を学ぶ。具体的には、命題論理を題材として、ポインタを使った高度なデータ構造を使ったプログラミングを経験する。 |
| 授業計画 | 記号論理 命題論理と真理値表 命題論理と真理の木の方法 述語論理 ドメインと解釈 真理の木の方法 等号を含む述語論理 関数記号を含む述語論理 個数表現 Turingマシン 万能Turingマシン 停止問題の決定不可能性 2pdマシンとTuringマシン 述語論理による2pdマシンのシミュレーション 述語論理における非妥当性の決定不可能性 計算の複雑さ Javaとオブジェクト指向プログラミング ポインタによるデータ構造 命題論理における真理の木のプログラム |
| 評価方法 | 概念を理解するだけでなく、それをプログラムとして具体化できるかどうかによって評価を行う。 |
| 教科書 | |
| 参考書 | |
| メッセージ | 情報学研究科の院生であれば、知っておいたほうがよい内容である。オブジェクト指向プログラミングの考え方も知っておいてほしい。 |