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