科目名	計算量理論特論
単位数	2.0
担当者	知能工学専攻　教授　内田　智之 知能工学専攻　講師　鈴木　祐介
履修時期	前期
履修対象	１、２年次
講義形態	講義
講義の目的	有限オートマトン、Turing機械及び計算可能性についての定理や結果について講義形式で詳しく学び、教科書、参考書、インターネットを活用して割り当てられた計算量理論に関するテーマについてのさらなる知識の習得を行い、かつプレゼンテーションによる他者への説明を経験することにより、計算量理論に関する知識に加え、高い論理的思考力及びコミュニケーション力を身につける。
到達目標	計算量理論に関する定理及び結果について理解し、関連研究について自学できる。【知識2、技能1】 課題の解決に向けて協働して取り組めるよう、他者へ自分の考えを論理的に説明できるようになる。【主体性、協働性】 システム設計者および教育に従事する者にとって必要不可欠であるコミュニケーション力を身につける。【思考力・判断力、表現力】
受講要件	特になし。
履修取消の可否	可
履修取消不可の理由
事前・事後学修	自分が担当する箇所を解説するために必要な資料の作成を行うことで、教科書、参考書、インターネットを活用した関連知識の事前学修を行い、講義ノードと講義資料の整理を行うことで事後学修を行う。
講義内容	１　　計算量理論とは（ガイダンスと計算量とは） ２　　計算量理論の基礎（有限オートマトン） ３　　計算量理論の基礎（Turing機械） ４　　計算量理論の基礎（Turing機械による関数の計算） ５　　計算量理論の基礎（万能Turing機械とChurchの提唱） ６　　計算量理論の基礎（決定問題と可解・非可解） ７　　多テープTuring機械と計算量（諸定義） ８　　多テープTuring機械と計算量（時間量と領域量） ９　　領域圧縮と加速 １０　階層定理 １１　Savitchの定理 １２　計算量のクラスの概念 １３　還元可能性 １４　クラスNP １５　NP完全な問題 ※授業の順序は変更することがある。
期末試験実施の有無	実施しない
評価方法・基準	輪講における説明能力及び理解度（７０％）および講義や輪講での議論の積極的参加度等（３０％）を総合して評価を行う。
教科書等	参考書：有川節夫・宮野悟共著「オートマトンと計算可能性」(培風館) 参考書：Michael Sipser, Introduction to the theory of computation (3rd edition), Cengage Learning, 2012 参考書：足立暁生・西野哲朗共著「計算量理論概説」(朝倉書店)
担当者プロフィール	内田 智之： 　グラフアルゴリズムと機械学習に基づくデータマイニング手法に関する研究に従事。 　研究室：情報科学部棟別館5階 502研究室 鈴木 祐介： 　機械学習とデータマイニングへの応用に関する研究に従事。 　研究室：情報科学部棟別館5階 503研究室
講義に関連する実務経験
課題や試験に対するフィードバック	演習・課題は、授業で模範解答を用いた解説を行う。
アクティブ・ラーニング	プレゼンテーション
キーワード	有限オートマトン、Turing機械、多テープTuring機械、計算可能性、NP完全
備考	【教職】高専修（数学）: 解析学及び幾何学の理論的な応用等についての教育の方法及び技術の習得および教授法の習得を目指します。 講義内容・資料作成等に関する個別学習相談は随時受け付けています。