| 授業は，初回の２時間のみ，教員側で説明を行なうが，それ以外は原則として，次回の授業で習得すべき |
|
| 内容を教員が示し，それについて各学生が調査・予習を行なった内容を発表する，という形式で進める。 |
4 |
| 1. 正規言語と有限オートマトン |
|
| 1.1 準備 |
6 |
| ・計算とアルゴリズムとは ・集合と写像 ・アルファベット ・語と言語 |
|
| 1.2 正規言語と有限オートマトン |
|
| ・正規表現と正規言語 ・有限オートマトン ・有限オートマトンによる言語表現 |
|
| ・決定性オートマトンと非決定性オートマトンの定義および動作，変換 |
2 |
| 2. 文脈自由文法とプッシュダウンオートマトン |
|
| 2.1 文脈自由文法 |
4 |
| ・文脈自由文法 ・解析木 ・あいまい性 |
|
| 2.2 プッシュダウンオートマトン |
|
| ・プッシュダウンオートマトン（PDA）の定義と動作 ・文脈自由文法からPDAへの変換 |
|
| ・決定性PDAと非決定性PDA |
2 |
| 3. チューリング機械 |
|
| 3.1 チューリング機械 |
2 |
| ・チューリング機械の定義と動作 |
|
| 3.2 チューリング機械と言語 |
|
| ・チューリング機械で受理される言語 ・チョムスキーによる言語の階層 |
6 |
| 4. 計算可能性 |
|
| 4.1 チューリング機械と計算可能性 |
|
| ・チューリング機械による計算 ・多テープチューリング機械 |
|
| ・２次元テープチューリング機械 ・ランダムアクセス機械 |
|
| ・チャーチ=チューリングの提唱 ・チューリング機械の停止問題 |
2 |
| ・チューリング計算可能性の概念 |
|
| 4.2 決定不能性 |
2 |
| ・決定可能問題 ・決定不能問題 ・クラスP ・クラスNP ・NP完全性 |
|
| 5. まとめ |
|
|
|
