計算理論の単元（2単元）
- 1
オートマトンと正規言語
DFA・NFA・部分集合構成・正規表現・反復補題
- 2
計算可能性と NP 完全性
チューリング機械・停止問題・P と NP・多項式時間帰着
計算理論の院試での出題
院試hubが分類した年度別解説の大問のうち、この科目の単元に対応するテーマ。数字は出題した大学数と大問数。
情報の他の科目
- アルゴリズムとデータ構造4単元
- 情報理論2単元
計算理論の要点定義・定理・計算例を単元ごとに
有限オートマトン（DFA・NFA）と正規表現が同じ言語のクラスを表すことから始め、反復補題で正規でない言語を示す方法を学ぶ。次にチューリング機械で計算可能性を定義し、停止問題が決定不能であることと帰着による証明を扱う。最後に多項式時間で解ける問題のクラス P、検証できる問題のクラス NP、多項式時間帰着と NP 完全性を扱う。