【授業概要】
・テーマ
理論計算機科学の基礎である，計算理論について講義する．効率的に計算できる問題や，できない問題があるという考え方を学び，問題の本質的な難しさを体系的に取り扱う枠組みを理解する．
・到達目標
計算理論の基礎的な用語・概念を理解し，適切に説明できるようになる．
・キーワード
アルゴリズム，計算，計算量クラス，チューリング機械，NP，P
【科目の位置付け】
この科目はアルゴリズム論やオートマトン理論と同じく，理論計算機科学の基礎となる科目である．本科目は，「オートマトンと言語理論」や「データ構造とアルゴリズム」を基礎とする．
【授業計画】
・授業の方法
講義を中心に行い，概ね毎回小テストを課す．
・日程
第１週 イントロダクション
第２週 集合と言語，問題
第３週 チューリング機械
第４週 万能チューリング機械
第５週 決定可能と決定不能
第６週 クラスP
第７週 多項式時間アルゴリズム
第８週 クラスNP
第９週 非決定性の解釈
第１０週 NPの重要性
第１１週 多項式時間帰着
第１２週 NP困難とNP完全
第１３週 様々なNP完全問題
第１４週 NP完全問題へのアプローチ
第１５週 期末テストとまとめ
（理解度などに応じて，講義内容を変更することもある．）
【学習の方法】
・受講のあり方
分からない部分がある時は，納得するまで積極的に質問すること．
・授業時間外学習へのアドバイス
復習により，疑問点を洗い出すこと．また，参考書を用いた自主学習も推奨する．
【成績の評価】
・基準
計算理論の基礎的な事項について説明できることを，合格の基準とする．
・方法
小テスト（30点），期末試験（70点）を合計し，100点満点で判定する．60点以上を合格とする．
【テキスト・参考書】
・テキスト：特に指定しない．
・参考書：
- 丸岡 章 著，計算理論とオートマトン言語理論 ―コンピュータの原理を明かす，サイエンス社
- M. Sipser 著 太田和夫・田中圭介 監訳 阿部正幸・植田広樹・藤岡淳・渡辺治 訳，計算理論の基礎 ［原著第2版］2. 計算可能性の理論，共立出版
- M. Sipser 著 太田和夫・田中圭介 監訳 阿部正幸・植田広樹・藤岡淳・渡辺治 訳，計算理論の基礎 ［原著第2版］3. 複雑さの理論，共立出版
【その他】
・学生へのメッセージ
本科目の基礎となる科目に「オートマトンと言語理論」と「データ構造とアルゴリズム」があるが，これらの授業で学ぶ予備知識がなくても理解できるように，基本的な事項から解説する．
・オフィス・アワー
金曜日 16:00-17:00 (8-225)
|