情報数学
准教授・蓮沼 徹
2単位
目的
計算機科学の基礎理論である，オートマトン，言語理論，計算論についての理解を深めることを目的とする．
概要
オートマトン，正則表現，文脈自由文法，プッシュダウン·オートマトン，Turing機械，判定不能問題，NP完全性
キーワード
オートマトン，言語，計算
目標
| 1. | 有限オートマトンの基本的事項(決定性，非決定性，正則表現，状態数最小化を理解する． |
| 2. | 文脈自由文法とプッシュダウンオートマトンの関係について理解する． |
| 3. | Turing機械，決定不能性，NP完全性を理解する． |
計画
| 1. | 有限オートマトン(1) |
| 2. | 有限オートマトン(2) |
| 3. | 決定性，非決定性 |
| 4. | 正則表現 |
| 5. | 非正則言語 |
| 6. | 状態数最小化 |
| 7. | 文脈自由文法 |
| 8. | プッシュダウン·オートマトン |
| 9. | 言語とオートマトン |
| 10. | Turing 機械 |
| 11. | Turing 可算言語 |
| 12. | 決定不能問題 |
| 13. | 計算量クラス |
| 14. | 還元可能性 |
| 15. | NP完全性 |
| 16. | 期末試験 |
評価
期末テスト，レポート課題，授業への取り組み等により総合的に評価する．
再評価
行う．
教科書
参考書: 計算論の基礎，Michael Sipser 著，渡辺・太田 監訳 共立出版
連絡先
蓮沼(088-656-7216, hasunuma@ias.tokushima-u.ac(no-spam).jp)
- オフィスアワー: 金曜日 9·10講時