2007年度 総合科学部 自然システム学科 数理·情報コース 数理科学サブコース 学部課程 — 3年(前期)
2007年度 総合科学部 自然システム学科 数理·情報コース 情報科学サブコース 学部課程 — 3年(前期) |
| EDB |
| 情報数学 |
| 准教授・蓮沼 徹 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. | 期末試験 |
|
| 成績評価の方法 |
| 期末テスト，レポート課題，授業への取り組み等により総合的に評価する． |
| 教科書 |
| 参考書:計算論への入門，エフィーム·キンバー カール·スミス著，ピアソン·エデュケーション |
| WEBページ |
| →コンテンツサーバ (EDB/CMS) |
| 連絡先 |
蓮沼(088-656-7216, hasunuma@ias.tokushima-u.ac(no-spam).jp)
オフィスアワー:
金曜日 9·10講時 |