【授業の目的】
有限オートマトン、チューリング機械の仕組みとその性質について学ぶことにより、計算機を効果的に用いて情報処理を行うために必要となる計算論的な物の見方・考え方を身に付けること、さらに計算機で解決することが求められる課題の本質的な難しさを体系的に取り扱う枠組みについて、基礎的な知識を得ることを目的とする。
【授業の到達目標】
この講義を履修した学生は、
a) 有限オートマトンの設計、動作確認が行える
b) チューリング機械の設計、動作確認が行える。
c) アルゴリズムの計算時間を評価できる。
d) クラスPとクラスNPの定義、及びその違いを説明できる。
【授業概要（キーワード）】
オートマトン、アルゴリズム、計算、計算量クラス、チューリング機械、NP、P
【科目の位置付け】
本科目は，情報・エレクトロニクス学科のカリキュラムポリシーの１（２）に記載されている，情報科学，または電気通信工学の応用力を養うための講義となる．また情報数学入門，情報数学Iを基礎とし，さらに計算理論，自然言語処理の基礎となる．
【SDGs（持続可能な開発目標）】
04.質の高い教育をみんなに
09.産業と技術革新の基盤をつくろう
【授業計画】
・授業の方法
講義を中心に行う。さらに毎回の講義内容の理解を促す小テストを課す。
・日程
第１週 講義の概要と基礎知識
第２週 有限オートマトン
第３週 有限オートマトンの限界
第４週 チューリング機械に導入
第５週 チューリング機械に慣れよう
第６週 万能チューリング機械
第７週 計算不可能な問題
第８週 計算時間とオーダ表記
第９週 クラス P とその解釈
題１０週 クラス P に慣れよう
第１１週 クラス NP とその解釈
第１２週 P vs. NP 問題
第１３週 多項式時間帰着
第１４週 充足可能性判定問題と様々なNP完全問題
第１５週 期末テストとまとめ
※これらは予定であり、受講者の理解の状況によって変更の可能性がある。
【学習の方法・準備学修に必要な学修時間の目安】
・受講のあり方
講義中に出された小テストによって，理解できていない部分を把握し，復習に努めること．
・授業時間外学習（予習・復習）のアドバイス
毎回行われる小テスト，および講義実施後に公開される資料をもとに復習を行うこと．
【成績の評価】
・基準
授業の到達目標(a)，(b)，(c)，(d) それぞれについて，本質的な理解の誤りがないことを合格の基準とする．
・方法
小テスト（20点），期末テスト（80点）を合計し，100点満点で判定する．60点以上を合格とする．
【テキスト・参考書】
テキスト：
・丸岡 章，計算理論とオートマトン言語理論，サイエンス社（２００５）
参考書：
・J. ホップクロフト, J. ウルマン, R. モトワニ，オートマトン言語理論 計算論〈1〉第２版，サイエンス社（２００３）
・岩間一雄，オートマトン・言語と計算理論，電子情報通信学会編（２００３）
【その他】
・学生へのメッセージ
講義時間内で理解できない点は，資料をもとに必ず復習を行うこと．特に，定理の意味，定理の証明それぞれについて，自分が理解できているかを確認しながら学習を進めるとよい．
・オフィス・アワー
曜日：金曜日
時間：16:00-17:00
場所：8号館2階 225室
|