2011年度 総合科学部 自然システム学科 数理·情報コース 数理科学サブコース 学士課程 — 2年(前期), 3年(前期)

2011年度 総合科学部 自然システム学科 数理·情報コース 情報科学サブコース 学士課程 — 2年(前期), 3年(前期)

情報数学

准教授・蓮沼 徹

2単位

目的

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

概要

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

キーワード

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

目標

1.有限オートマトンの基本的事項(決定性,非決定性,正則表現,状態数最小化を理解する.
2.文脈自由文法とプッシュダウンオートマトンの関係について理解する.
3.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)
オフィスアワー: 金曜日 9·10講時