Computational Complexity
2011 年度計算量特論

科目紹介

現代の計算機科学の基本となる理論である計算理論，計算量理論について概説する． まず計算理論を理解するために不可欠な知識である証明について厳密に学習する． そして計算とは何かを理解するために種々のオートマトンについて学習する．

本授業により計算機技術を支えている基礎理論の本質に関する理解の向上を図る．

時限，教室

金曜 1 限，6A-117 教室

授業スケジュール

1. ガイダンス (4/15), 授業概要・目標等の説明 授業の目標，範囲等について解説する(p.2, l.12 まで)
2. オートマトン理論 (4/22), オートマトン理論を学習する意味，計算量理論との関係について説明する (p.5 l.18 まで)
3. 形式的証明(1) (5/6), 演繹的証明について説明する (p.9 l.32 まで)
4. 形式的証明(2) (5/13), その他の形式的証明について説明する (p.14 l.24 まで)
5. 証明技法 (5/20), 対偶，背理法，反例について説明する (p.18 l.7 まで)
6. 帰納的証明(1) (5/27), 帰納的証明について説明する (p.22 l.3 まで)
7. 帰納的証明(2)(6/3), 一般的な帰納的証明，構造的帰納法について説明する (p.23 l.8 まで)
8. 帰納的証明(3)，オートマトン理論 (6/10), 相互帰納法についての説明と，用語の定義を説明する (p.28 l.19 まで)
9. 決定性有限オートマトン(1) (6/17) 決定性有限オートマトンの概略説明を行う． (p.33 まで)
10. 決定性有限オートマトン(2) (6/24), 決定性有限オートマトンを用いたプロトコルの検証について説明する (p.45 l.17 まで)
11. 決定性有限オートマトン(3) (7/1), 決定性有限オートマトンの受理する言語について説明する (p.50 l.16 まで)
12. 非決定性有限オートマトン(1) (7/8), 非決定性有限オートマトンについて説明する (p.57 まで)
13. 非決定性有限オートマトン(2) (7/15), 非決定性有限オートマトンの定義と受理する言語について説明する (p.64 l.19 まで)
14. 授業と同じ6A-117 教室にて期末試験，試験範囲は2.3.5節まで (7/22)

ただし，受講生の理解度によりスケジュールが変化する可能性がある

成績判定

授業中に出題する課題をすべて提出した者を対象に，試験の点数により評価する

教科書

“Automata Theory, Languages, and Computation,” J. H. Hopcroft et al., Addison Wesley ISBN 0-321-45536-3