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