2024年度学院等開講科目情報理工学院数理・計算科学系

計算の理論

開講元: 数理・計算科学系
担当教員: 田中圭介 / 安永憲司
授業形態: 講義 (対面型)
メディア利用科目: -
曜日・時限 (講義室): 火3-4 (W8E-308(W834)) / 金3-4 (W8E-308(W834))
クラス: -
科目コード: MCS.T323
単位数: 200
開講時期: 2024年度
開講クォーター: 3Q
シラバス更新日: 2025年3月14日
使用言語: 日本語

シラバス

授業の目的（ねらい）、概要

オートマトンと数理言語論の延長として、基礎的な計算モデルであるTuring機械に関する計算可能性ならびに計算複雑さを学びます。これを通して、計算機のハードウェア、ソフトウェアに関する基本的な数学的性質である計算可能性の概念を学び、計算問題の複雑さを表す計算量クラスやNP完全性などの概念を学びます。具体的には、Turing機械、Church-Turingの提唱、Turing機械の変型、判定可能性、対角線論法、停止問題、帰着可能性、時間計算量、クラスPとNP、NP完全性、領域計算量を扱います。

到達目標

本講義を履修することによって以下を理解する。
1) 計算可能性の概念
2) Turing機械モデルとその変型
3) 計算可能性に関する証明手法
4) 計算複雑さの概念
5) クラスPとNP，NP完全性

キーワード

計算可能性、Turing機械、Church-Turingの提唱、判定可能性、対角線論法、停止問題、計算の複雑さ、クラスPとNP、NP完全性、回路計算量、乱択計算

学生が身につける力

専門力
教養力
コミュニケーション力
展開力 (探究力又は設定力)
展開力 (実践力又は解決力)

授業の進め方

授業では毎回、その回の内容、または、それ以前の回の内容について小テストを出します。
授業は通常の講義の他に演習形式の講義を行うことがあります。そこでは、通常の講義中に扱えなかった内容や小テストについて説明します。

授業計画・課題

	授業計画	課題
第1回	講義全体の概要、講義の位置付け、Turing機械	Turing機械の概念を理解する。
第2回	Church-Turingの提唱、Turing機械の変型	Church-Turingの提唱を理解する。
第3回	判定可能性	判定可能性の証明手法について理解する。
第4回	対角線論法、停止問題	対角線論法の適用方法を理解する。
第5回	帰着可能性	帰着可能性の概念を理解する。
第6回	写像帰着可能性	写像帰着可能性の概念を理解する。
第7回	再帰定理	証明手法を理解する。
第8回	時間計算量とクラスP	時間計算量の概念を理解する。
第9回	クラスNPとP対NP問題	計算量クラスNPを理解する。
第10回	NP完全性	NP完全性の概念を理解する。
第11回	領域計算量	領域計算量の概念を理解する。
第12回	階層定理と相対化	階層定理ならびに相対化の概念を理解する。
第13回	回路計算量	回路計算量の概念を理解する。
第14回	乱択計算	確率的Turing機械の概念を理解する。

準備学修(事前学修・復習)等についての指示

学修効果を上げるため教科書や配布資料等の該当箇所を参照し「毎授業」授業内容に関する予習と復習（課題含む）をそれぞれ概ね100分を目安に行うこと。

教科書

計算理論の基礎 [原著第3版] 2 計算可能性の理論, Michael Sipser 著・田中圭介監訳・藤岡淳監訳・阿部正幸訳・植田広樹訳・太田和夫訳・渡辺治訳, 共立出版, 2023 年, ISBN 9784320125629.
計算理論の基礎 [原著第3版] 3 複雑さの理論, Michael Sipser 著・田中圭介監訳・藤岡淳監訳・阿部正幸訳・植田広樹訳・太田和夫訳・渡辺治訳, 共立出版, 2023 年, ISBN 9784320125636.
(原著: Introduction to the Theory of Computation, Third Edition, Michael Sipser, Course Technology, 2012, ISBN 9781133187790.)

参考書、講義資料等

初回の講義でお知らせします。

成績評価の方法及び基準

授業中に行う小テスト (60%) と最終試験 (40%) で評価を行います。

履修の条件・注意事項

アルゴリズムとデータ構造、および、オートマトンと数理言語論の知識があることが望ましい。