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

本講義ではまず，最も基本的な言語クラスである正則言語に話題を絞り，形式言語理論のエッセンスを解説する．次に「計算機で解けない問題があるのだろうか」といった，計算機の能力の限界に関する疑問に答えていく． １. 正則言語 ・有限オートマトン（定義，決定性モデルと非決定性モデルの等価性） ・正則表現（定義， 有限オートマトンとの等価性） ・有限オートマトンの簡単化 ２. 計算可能性 ・チューリング機械（定義， 能力を限定／拡張したモデル） ・決定不能性（対角線論法， 還元による証明法）

エフィーム・キンバー，カール・スミス著，筧・杉原訳 ： 計算論への入門，ピアソン・エデュケーション，2002.

１.Efim Kinber, Carl Smith：Theory of Computing : A Gentle Introduction， Prentice Hall，2000（本講義の教科書の原典） ２.J.E.Hopcroft and J.D.Ullman：Introduction to Automata Theory，Languages， and Computation，Addison-Wesley，1979 ３.富田悦次・横森貴著 : オートマトン・言語理論， 森北出版 （基本となる概念を丁寧に説明したテキスト）

（必ずしも先修条件ではない） アルゴリズムとデータ構造 （アルゴリズム概論 ） ブール代数（計算機構造概論）

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

１回目あるいは２回目の授業の際に，受講希望者は受講の登録をして下さい。