◇ 担当教員：伊藤　実（いとう　みのる）　安本　慶一（やすもと　けいいち）

◇ 単位数：２　◇　開講時期：�T期　月曜１時限・木曜２時限 ◇　講義室：L1

◇ 講義目的：

計算理論は、情報科学において多くの重要な方法論と結果をもたらした。本講義では、情報科学の多くの分野で必須の知識となっている有限オートマトンに関す
る基礎的な事柄に加え、現在の計算機と同等の能力を持つモデルであるチューリング機械を用いて、計算機で解ける問題および解けない問題のクラスについて理
解することを目的とする。

◇　講義内容：

１．正則言語

・有限オートマトン（定義、決定性モデルと非決定性モデルの等価性）

・正則表現（定義、有限オートマトンとの等価性）

・有限オートマトンの簡単化

２．計算可能性　　　 

・チューリング機械（定義、能力を限定／拡張したモデル）

・決定不能性（対角線論法、還元による証明法）





◇ 教科書　：

エフィーム・キンバー、カール・スミス著、筧・杉原訳 ： 

計算論への入門、ピアソン・エデュケーション、2002

◇ 参考書　：

１．J.E.Hopcroft, R.Motwani and J.D.Ullman: Introduction to Automata
Theory, Languages, and Computation second edition, Addison-Wesley, 2000

２．富田悦次・横森貴著：オートマトン・言語理論、森北出版 

３．岩間一雄：アルゴリズム理論入門、昭晃堂、2001



◇ 受講要件：

アルゴリズムとデータ構造（アルゴリズム概論）

ブール代数（計算機構造概論）

◇ 成績評価：

試験により成績を評価する。