| 授業科目名（和文） ［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., 2. 計算量の定義と基本的な導出手法 3.～ 5. 古典的な計算量クラス：P, NP, PSPACE 6., 7. 問題の変換 8.～10. 計算量クラス間の関係 11., 12. 最適化問題に対する計算量 13.～15. その他の計算量クラス：PCP, APなど |
| 成績評価方法と基準 ［Grading policy (Evaluation)］ |
レポートを中心に，総合的に評価する。 |
| 教科書 ［Textbook］ |
適宜資料を配布する。 |
| 自主学習ガイド及び キーワード ［Self learning］ |
関連する論文や資料を適宜紹介するので各自で参考とすること。 |
| 開講年度 ［Year of the course］ |
24 |