シラバス参照

授業情報／Course information

科目一覧へ戻る 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 [講義のまとめ]
本講義で行った内容を振り返ってまとめを行う.
授業評価詳細情報
到達目標及び観点／Learning Goal and Specific Behavioral Viewpoints
No. 到達目標
／Learning Goal		 知識?理解
／Knowledge & Undestanding		 技能?表現
／Skills & Expressions		 思考?判断
／Thoughts & Decisions		 伝達?コミュニケーション
／Communication		 協働
／Cooperative Attitude
1 計算量の概念を理解し具体的なアルゴリズムに対して算出できるようにする ○ ○ ○
2 計算量クラス間の関係を理解する ○ ○
3 多様な計算モデルを理解する ○ ○
成績評価方法と基準／Evaluation of Achievement
※出席は2/3以上で評価対象となります。
No. 到達目標
／Learning Goal		 定期試験
／Exam.		 中間レポート
1 計算量の概念を理解し具体的なアルゴリズムに対して算出できるようにする ○ ○
2 計算量クラス間の関係を理解する ○
3 多様な計算モデルを理解する ○
評価割合（％）
／Allocation of Marks		 70 30

科目一覧へ戻る