初等的な計算モデルとしてオートマトンやそれに付随する概念について述べる。決定性・非決定性の違い,正規言語との同等性,ポンプ補題を紹介する。割と容易に理解できる単純なモデルだが重要度が低いわけではない。バックトラックを必要とせずに高速に実行できる計算クラスを与える。
計算モデルとしてチューリング機械を導入する。後半の講義で述べる計算複雑性はチューリング機械をベースに定式化される。計算可能・計算不可能性,停止性問題の計算不可能性,帰着について述べる。計算の概念を数学的に定式化する方法にはいろいろあるが,チューリング機械は最も多用されるものである。
計算複雑性の種々のクラスを導入しその性質を調べる。複雑性には時間によるものと空間によるものがある。時間に関する複雑性にはクラスPやNP等がある。空間に関してはPSPACE等がある。P=NP問題の定式化,多項式時間還元,NP完全問題,Savitchの定理,PSPACE完全問題について述べる。時間があれば階層定理,オラクルによる相対化,確率チューリング機械,クラスBPP・IPについて述べる。