2011年度 総合科学部 総合理数学科 数理科学コース 学士課程 — [選択] 2年(前期)

情報数学

准教授・蓮沼 徹

2単位

目的

計算機科学の基礎理論である,オートマトン,言語理論,計算論についての理解を深めることを目的とする.

概要

オートマトン,正則表現,文脈自由文法,プッシュダウン·オートマトン,Turing機械,判定不能問題,NP完全性

キーワード

オートマトン,言語,計算

目標

1.有限オートマトンの基本的事項(決定性,非決定性,正則表現),文脈自由文法とプッシュダウンオートマトンの関係,Turing機械,決定不能性,NP完全性を理解する.

計画

1.有限オートマトン
2.決定性,非決定性
3.正則表現
4.非正則言語
5.状態数最小化
6.文脈自由文法
7.プッシュダウン·オートマトン
8.言語とオートマトン
9.Turing 機械
10.Turing 可算言語
11.決定不能問題
12.計算量クラス
13.還元可能性
14.NP完全性
15.総括授業

評価

期末テスト,レポート課題,授業への取り組み等により総合的に評価する.

再評価

行う.

参考資料

参考書: 計算論の基礎,Michael Sipser 著,渡辺・太田 監訳 共立出版

連絡先

蓮沼(088-656-7216, hasunuma@ias.tokushima-u.ac(no-spam).jp)