  シラバス参照
|
| 科目一覧へ戻る | 2019/01/02 現在 |
| 科目名（和文） ／Course |
計算量特論 |
|---|---|
| 科目名（英文） ／Course |
Complexity Theory |
| 時間割コード ／Registration Code |
81A14101 |
| 学部（研究科） ／Faculty |
情報系工学研究科 博士後期課程 |
| 学科（専攻） ／Department |
システム工学専攻 |
| 担当教員（○：代表教員）
／Principle Instructor （○） and Instructors |
○小野 孝男 |
| オフィスアワー ／Office Hour |
小野 孝男(火曜日 ５限, 2608室) |
| 開講年度 ／Year of the Course |
2018年度 |
| 開講期間 ／Term |
前期 |
| 対象学生 ／Eligible Students |
1年,2年,3年 |
| 単位数 ／Credits |
2.0 |
| 更新日 ／Date of renewal |
2018/03/16 |
|---|---|
| 使用言語 ／Language of Instruction |
日本語 |
| オムニバス ／Omnibus |
該当なし |
| 授業概略と目的 ／Cource Description and Objectives |
コンピューターで問題を処理するためには, まず「処理の方法」である「アルゴリズム」を理解しなければならない. 一般的には 1つの問題に対しても複数のアルゴリズムが存在し, そのうちのどれを利用するかはアルゴリズム自身の性質と直面している問題に応じて選択することになる. 本講義ではアルゴリズムを選択する際の指標の 1つである計算量を取り扱い, その考え方と計算量によって定義される問題のクラスについて理解する. また, 複数のクラスの間の関係についても理解するとともに, 40年以上にわたって重要な問題となっている「P=NP?」問題についても概要とその重要性を認識することを目的とする. |
| 履修に必要な知識?能力?キーワード ／Prerequisites and Keywords |
本講義はアルゴリズムの理論的な解析を扱うため, 計算モデル (オートマトン) とアルゴリズムの記述方法についてはあらかじめ理解しておくこと. また, 極限を含めた解析学の手法と確率論も簡単ではあるが現れるため, これらについても確認しておくことが望ましい. キーワード: アルゴリズム, 計算量, 対話型証明 |
| 履修上の注意 ／Notes |
各回の最後には次回の内容について簡単に概要を説明するので, 各自であらかじめ調べておくこと. |
| 教科書 ／Textbook(s) |
なし. 毎回資料を配布する. |
| 参考文献等 ／References |
計算量理論における古典的な名著として Michael Garey, David Johnson: Computers and Intractability: A Guide to the Theory of Np-Completeness が挙げられる. また, アルゴリズムとその解析については例えば Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms が参考になるだろう. |
| 自主学習ガイド ／Expected Study Guide outside Coursework/Self-Directed Learning Other Than Coursework |
講義では簡単な概要しか説明できないこともあるので, 興味を持った事項について自ら調査してほしい. |
| 資格等に関する事項 ／Attention Relating to Professional License |
|
| 備考 ／Notes |
| No. | 単元（授業回数） ／Unit (Lesson Number) |
単元タイトルと概要 ／Unit Title and Unit Description |
時間外学習 ／Preparation and Review |
配布資料 ／Handouts |
|---|---|---|---|---|
| 1 | 1 | [計算量とは] アルゴリズムの評価尺度の 1つである計算量について簡単に説明する. |
||
| 2 | 2 | [オーダー記法] 計算量の評価で用いる「オーダー」の概念を学ぶ. |
||
| 3 | 3 | [計算量クラス(1): P と NP] 計算量によって問題をクラスに分類できることを説明し, 最も基本的なクラスである P と NP について理解する. |
||
| 4 | 4 | [計算量クラス(2)] PSPACE] 使用するメモリ量に基づくクラス PSPACE について概観する. |
||
| 5 | 5 | [計算量クラス(3): EXP など] 計算時間や使用メモリ量に基づくその他のクラスについて学ぶ. |
||
| 6 | 6 | [問題の変換] 問題間の難易度を考える指標として, 与えられた問題を異なる問題に置き換えて解くという手法が使えることを理解する. |
||
| 7 | 7 | [計算量クラス間の関係] 問題の変換を通じて各種の計算量クラスの間の包含関係を知る. |
||
| 8 | 8 | [オラクル計算] 一種のサブルーチンである「オラクル」について理解し, オラクルによって計算モデルを拡張する. |
||
| 9 | 9 | [多項式階層] オラクル計算によって計算量クラスを定義し, そのような計算量クラス全体を概観する. |
||
| 10 | 10 | [最適化問題と計算量クラス] 計算量クラスを考えるときには一般に判定問題を用いるが, 身近な問題としては最適化問題が多い. そこで, 最適化問題に対して計算量クラスを考える. |
||
| 11 | 11 | [確率的計算に基づく計算量クラス] 「常に正しく答える」アルゴリズム以外に「ある程度以上の確率で正しい答えを返す」アルゴリズムを考えることができる. そのようなアルゴリズムに基づいて計算量クラスを定義する. |
||
| 12 | 12 | [計算量クラス PCP] 確率的計算におけるもっとも基本的な計算量クラスである PCP について理解する. |
||
| 13 | 13 | [計算量クラス IP, MIP] 「対話型証明」の概念を説明し, それを用いた計算量クラス IP, MIP を理解する. |
||
| 14 | 14 | [「P=NP?」問題] 2つの計算量クラス P, NP が等しいかどうかは理論的に興味があるだけでなく現実的にも重要な問題である. この問題に対する歴史と現在の到達点について学ぶ. |
||
| 15 | 15 | [講義のまとめ] 本講義で行った内容を振り返ってまとめを行う. |
| No. |
到達目標 ／Learning Goal |
知識?理解 ／Knowledge & Undestanding |
技能?表現 ／Skills & Expressions |
思考?判断 ／Thoughts & Decisions |
伝達?コミュニケーション ／Communication |
協働 ／Cooperative Attitude |
||
|---|---|---|---|---|---|---|---|---|
| 1 | 計算量の概念を理解し具体的なアルゴリズムに対して算出できるようにする | ○ | ○ | ○ | ||||
| 2 | 計算量クラス間の関係を理解する | ○ | ○ | |||||
| 3 | 多様な計算モデルを理解する | ○ | ○ |
| No. |
到達目標 ／Learning Goal |
定期試験 ／Exam. |
中間レポート | ||||
|---|---|---|---|---|---|---|---|
| 1 | 計算量の概念を理解し具体的なアルゴリズムに対して算出できるようにする | ○ | ○ | ||||
| 2 | 計算量クラス間の関係を理解する | ○ | |||||
| 3 | 多様な計算モデルを理解する | ○ | |||||
|
評価割合（％） ／Allocation of Marks |
70 | 30 | |||||