計算理論I　　 Theory of Computation I

---

◇ 担当教員：伊藤　実（いとう　みのる）　安本　慶一（やすもと　けいいち）
◇ 単位数：２　◇　開講時期：�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

◇ 受講要件：
アルゴリズムとデータ構造（アルゴリズム概論）
ブール代数（計算機構造概論）
◇ 成績評価：
試験により成績を評価する。