| 授業科目名（和文） ［Course］ |
計算量特論 |
| 授業科目名（英文） ［Course］ |
Complexity Theory |
| 学部（研究科） ［Faculty］ |
情報系工学研究科 |
| 学科（専攻） ［Department］ |
システム工学専攻 |
| 担当教員（○：代表教員） [Principle Instructor(○) and Instructors] |
○小野 孝男 自室番号（2608）、電子メール（onotakao**c.oka-pu.ac.jp） ※利用の際は,** を @に置き換えてください |
| 単位数 ［Point(Credit)］ |
後期 2単位 |
| 対象学生 ［Eligible students］ |
1?2?3年次生 |
| 授業概略と目標 ［Course description and Objects］ |
大規模な問題を計算機で解くためにはアルゴリズムやデータ構造を適切に選択する必要がある．これらを選択する基準の 1つが計算量であり，本科目では計算量の評価方法を学ぶとともに計算量同士の関係について理解することを目的とする． |
| 到達目標 ［Learning Goal］ |
1. 計算量の意義と具体的な導出方法を理解する。 2. 計算量クラスの間の関係を学ぶ。 |
| 授業計画とスケジュール ［Course schedule］ |
1. 計算量とは ?アルゴリズムの評価尺度の 1つである計算量について簡単に説明する． 2. オーダー記法 ?計算量の評価で用いる「オーダー」の考え方を学ぶ． 3. 計算量クラス (1): P と NP ?多項式時間で解くことのできる問題のクラス P と，多項式時間で「検証」できる問題のクラス NP を理解する． 4. 計算量クラス (2): PSPACE ?使用するメモリ量に基づく計算量クラス PSPACE について概観する． 5. 計算量クラス (3): EXP など ?時間計算量や空間計算量に基づくその他のクラスについて学ぶ． 6. 問題の変換 ?ある問題を解くときに，その問題を直接解くのではなく他の問題に変換してから解くことがある．そのときの問題間の難易度について考える． 7. 計算量クラス間の関係 ?計算量クラスの間の包含関係について学ぶ． 8. オラクル付きチューリング機械 ?オラクル (サブルーチン) によって拡張した計算モデルを知る． 9. 多項式階層 ?オラクルを用いて様々な計算量クラスが定義できることを示し，その全体像を概観する． 10. 最適化問題と計算量クラス ?計算量クラスを考えるときは判定問題を用いることが多いが，最適化問題に対しても計算量クラスを考えることができる．その際の，判定問題に対する計算量クラスとの比較を行う． 11. その他の計算量クラス (1): 確率的な計算量クラス ?問題によっては，「確率的に」解くアルゴリズムを考えることもある．そのような計算量クラスの概要を知る． 12., 13. その他の計算量クラス (2): PCP，IP，MIP ?確率的な計算量クラスのうち，非常に興味深いクラスとして PCP が挙げられる．この PCP と関連するクラスである IP および MIP について論じる． 14. P=NP? ?計算機科学において長年の重要事項となっている「P=NP?」問題について概観する． 15. まとめ ?本科目の概略をまとめる． |
| 成績評価方法と基準 ［Grading policy (Evaluation)］ |
レポートを中心に，総合的に評価する。 |
| 教科書 ［Textbook］ |
教科書：指定しない．毎回資料を配布する。 |
| 自主学習ガイド及び キーワード ［Self learning］ |
関連する論文や資料を適宜紹介するので各自で参考とすること。 |
| 開講年度 ［Year of the course］ |
28 |