【授業の目的】
問題の「機械的計算」による解法（アルゴリズム）の「効率性」を評価するための数学的理論（計算量理論）について学ぶ。
計算機の理論的モデルであるチューリングマシンの仕組みを通して「計算の効率性」についての数学的な取り扱いについて学ぶ。
【授業の到達目標】
決定性および非決定性チューリングマシン、多項式時間計算量（class P）、非決定性多項式時間計算量（class NP）、NP-困難性の概念について、その理論と仕組みを理解し、併せて典型的なNP完全問題群について理解すること。
【授業概要（キーワード）】
チューリングマシン、非決定性チューリングマシン、判定可能性、計算量、クラスP、クラスNP、NP完全性、多項式時間還元
【科目の位置付け】
発展科目
【授業計画】
・授業の方法
機械的計算によって解ける（アルゴリズムが存在する）問題群の中には、「効率的に解ける」ものと、「効率的には解けそうに無い」ものが存在する。このように、問題の難しさを「アルゴリズムの『効率性』」の尺度を用いて見積もるための数学的方法論（計算量理論）について丁寧に解説する。
・日程
第１回：チューリングマシン入門（記法・時点表示・遷移図）
第２回：様々なチューリングマシンの等価性
第３回：決定性チューリングマシンとクラスＰ
第４回：多項式時間で解ける問題
第５回：非決定性チューリングマシンとクラスＮＰ
第６回：クラスＮＰに属する問題
第７回：多項式時間還元
第８回：ＮＰ完全問題とは何か？（言葉の定義）
第９回：充足可能性問題（ＳＡＴ）
第１０回：ＳＡＴ問題のＮＰ完全性
第１１回：制限された形の充足可能性問題（ＣＳＡＴ・３ＳＡＴのＮＰ完全性）
第１２回：独立集合問題と頂点被覆問題
第１３回：（有向・無向）ハミルトン閉路問題
第１４回：クラスＮＰの補集合とＮＰ完全性
第１５回：多項式領域で解ける問題（クラスＰＳ）
【学習の方法】
・受講のあり方
基本的に講義形式なので、理解出来ないところを残さないようにする。授業中の質問についても、積極的に行って頂いて構わない。
・授業時間外学習へのアドバイス
基本的に講義形式なので、理解出来ないところを残さないようにする。授業中の質問についても、積極的に行って頂いて構わない。
理論の理解と併せてその具体的な応用例、問題を解くことによって実際的に学ぶ。
分からないことをそのままにしない。
【成績の評価】
・基準
期末試験と授業中に実施する演習の得点を合算して評価得点を算出し，それをもとに評価を決定します．
・方法
期末試験 60％
授業中に実施する演習 40%
【テキスト・参考書】
授業の初日と、その後の進展に沿って数種類の本を紹介する。
参考書：J.ホップクロフト,R.モトワニ,J.ウルマン 著「オートマトン 言語理論 計算論II(第２版)」サイエンス社
参考書：マイケル・シプサ 著『計算理論の基礎』、渡辺 治 他訳、共立出版
参考書：松原・大島・藤田 他著「IT Text 離散数学」オーム社 など
【その他】
・オフィス・アワー
前期 木曜日 14時40分以降
後期 水曜日 16時20分以降
|