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講時 |