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