情報科学特論
 Advanced Lectures on Information Science
 担当教員:中西 正樹(NAKANISHI Masaki)
 担当教員の所属:地域教育文化学部地域教育文化学科児童教育コース
 開講学年:1年  開講学期:後期  単位数:2単位  開講形態:講義
 開講対象:理工学研究科(理学系)博士前期課程  科目区分:分野専門科目(データサイエンス分野) 
【授業の目的】
コンピュータの数学的モデルであるチューリング機械の基礎を学んだ上で,決定不能性,計算量のクラスについて理解を深める.コンピュータが効率的に問題を解ける(解けない/解けないと予想される)ということについて数学的な説明ができるようになることを目的とする.

【授業の到達目標】
チューリング機械と計算量のクラスに関する内容を学び,以下の点について修得することを目標とする.
1. コンピュータの数学的モデルであるチューリング機械の動作について説明できる.
2. コンピュータが解けない問題があることを説明できる.
3. PやNPといった計算量のクラスを説明できる.
4. 問題の困難さについて理解し,そのことを数学的に証明ができるようになる.

【科目の位置付け】
この授業は計算理論に関する高度な専門知識の習得を目的とするものである(理工学研究科(理学系)カリキュラムポリシー 1-2-2).

【授業計画】
・授業の方法
適宜演習を交えながら講義を行う.
・日程
第1回 コンピュータで解けない問題
第2回 チューリング機械
第3回 チューリング機械のプログラム技法
第4回 様々なチューリング機械
第5回 制限されたチューリング機械
第6回 総合演習(チューリング機械の設計)
第7回 対角線言語
第8回 帰納的言語,万能言語
第9回 決定不能問題
第10回 ポストの対応問題
第11回 クラスPとクラスNP
第12回 NP完全性
第13回 NP完全性の証明の例(3SAT等)
第14回 NP完全性の証明の例(独立集合問題等)
第15回 総合演習(NP完全性の証明)

【学習の方法】
・受講のあり方
各トピックの習得にはそれ以前のトピックを理解していることが不可欠である.疑問が生じた際にはできるだけ早く解決するように努めること.
・授業時間外学習へのアドバイス
授業中に解いた演習問題を中心に,単に「解き方」だけでなく「内容の理解」に努めること.

【成績の評価】
・基準
以下の点についての理解度を基準に評価する.
・チューリング機械の動作を説明できる.
・決定不能性について説明できる.
・計算量クラスについて説明できる.
・問題の複雑さに関する定理を証明できる.
・方法
レポートにより評価する.(100%)

【テキスト・参考書】
テキスト:J.ホップクロフト,R.モトワニ,J.ウルマン 著,野崎昭弘,高橋正子,町田元,山崎秀記 共訳,オートマトン 言語理論 計算論 II 第2版,サイエンス社

【その他】
・オフィス・アワー
質問は随時受け付けるが,あらかじめ連絡をすることが望ましい.

31963030-2017-13-37697