科目名 計算量理論特論
単位数 2.0
担当者 知能工学専攻 准教授 内田 智之
履修時期 前期
履修対象 1、2年生
概要 計算モデルである多テープチューリング機械に基づく計算量理論の概念およびその主要結果を扱っている教科書を、計算可能性について講義した後、それ以降について学生毎に担当する箇所を決定し、学生が自分の担当する箇所を解説しながら読み進める輪講形式で行う。輪講では、多テープチューリング機械の定義から始め、領域圧縮や階層定理、Savitchの定理などの計算量に関する基礎となる定理について扱う。さらに、計算量のクラスであるNPやPSPACEなどに関する結果についても扱う。
科目の到達目標 システム設計者および教育に従事する者にとって必要不可欠である論理的思考力および他者への説明能力を身につける。
受講要件 特になし。
事前・事後学修の内容 自分が担当する箇所を解説するために必要な資料の作成を行うことで、教科書、参考書、インターネットを活用した関連知識の事前学修を行い、講義ノードと講義資料の整理を行うことで事後学修を行う。
講義内容 1  計算量理論とは(ガイダンスと計算量とは)
2  計算量理論の基礎(有限オートマトン)
3  計算量理論の基礎(Turing機械)
4  計算量理論の基礎(Turing機械による関数の計算)
5  計算量理論の基礎(万能Turing機械とChurchの提唱)
6  計算量理論の基礎(決定問題と可解・非可解)
7  多テープTuring機械と計算量(諸定義)
8  多テープTuring機械と計算量(時間量と領域量)
9  領域圧縮と加速
10 階層定理
11 Savitchの定理
12 計算量のクラスの概念
13 還元可能性
14 クラスNP
15 NP完全な問題
評価方法 輪講における解説状況および講義や輪講での議論の参加状況などを総合して評価を行う。特に、評価においては、意欲的に講義・輪講に参加したか否かを重視する。
教科書等 教科書:有川節夫・宮野悟共著「オートマトンと計算可能性」(培風館)
担当者プロフィール 内田智之:グラフアルゴリズムと機械学習に基づくデータマイニング手法に関する研究に従事。
講義内容・資料作成等に関する個別学習相談は随時受け付けています。
備考 中学校・高等学校教諭 専修免許状(数学)の選択科目です。
解析学及び幾何学の理論的な応用等についての教育の方法及び技術の習得および教授法の習得を目指します。