理工学研究科Graduate School of Science and Engineering
PRI500X3（情報学基礎 / Principles of informatics 500）理論計算機科学特論１Theoretical Computer Science 1
和佐 州洋Kunihiro WASA
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 理工学研究科Graduate School of Science and Engineering |
| 添付ファイル名Attached documents | |
| 年度Year | 2023 |
| 授業コードClass code | YB002 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 春学期授業/Spring |
| 曜日・時限Day/Period | 水2/Wed.2 |
| 科目種別Class Type | |
| キャンパスCampus | 小金井 |
| 教室名称Classroom name | 各学部・研究科等の時間割等で確認 |
| 配当年次Grade | |
| 単位数Credit(s) | 2 |
| 備考（履修条件等）Notes | |
| 実務経験のある教員による授業科目Class taught by instructors with practical experience | |
| カテゴリーCategory | 応用情報工学専攻 |
すべて開くShow all
すべて閉じるHide All
Outline (in English)
Developing efficient algorithms that work in polynomial time is one of the important goals in theoretical computer science. On the other hand, if it is difficult to find such an algorithm, can we do nothing but give up? In this course, from the viewpoint of exact exponential time algorithms, we learn how to design better running time algorithms.
By the end of this lecture, students should be able to do the following: Students can explain several important definitions introduced in the lecture, can explain the basic strategies for designing exact exponential time algorithms, and can prove several basic problems in the field.
Before/after each class meeting, students will be expected to spend four hours to understand the course content.
Your overall grade in the class will be decided based on the following MId-term report: 40%, and Term-end report: 60%.
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
多項式時間で動作するような効率良いアルゴリズムを発見することは理論計算機科学における重要な問いの一つである．一方で，もしこのようなアルゴリズムを発見することが難しい場合，諦めるしかないのだろうか？本講義では，それでもなお厳密指数時間アルゴリズムという枠組みで，出来うる限り諦めない方法について紹介する．
到達目標Goal
本講義の到達目標は，厳密指数時間アルゴリズムを設計する手法の基本を知ることである．したがって，具体的には，下記の項目を達成目標とする．
(1) 講義で導入されたいくつかの重要な定義を説明できる．
(2) 厳密指数時間アルゴリズムを設計するための基本戦略を説明できる．
(3) この分野で紹介される幾つかの定理について，自ら証明できる．
この授業を履修することで学部等のディプロマポリシーに示されたどの能力を習得することができるか（該当授業科目と学位授与方針に明示された学習成果との関連）Which item of the diploma policy will be obtained by taking this class?
ディプロマポリシーのうち、「DP1」「DP2」「DP3」に関連
授業で使用する言語Default language used in class
日本語 / Japanese
授業の進め方と方法Method(s)（学期の途中で変更になる場合には、別途提示します。 /If the Method(s) is changed, we will announce the details of any changes. ）
本講義は，一つ一つの概念に関して丁寧に定義などともに説明すると同時に，実際に学生自ら手を動かして証明等を再構成できるように講義をすすめていく．また，受講者数が少ない場合には，輪講形式とする場合がある．
アクティブラーニング（グループディスカッション、ディベート等）の実施Active learning in class (Group discussion, Debate.etc.)
なし / No
フィールドワーク（学外での実習等）の実施Fieldwork in class
なし / No
授業計画Schedule
授業形態/methods of teaching：対面/face to face
※各回の授業形態は予定です。教員の指示に従ってください。
第1回[対面/face to face]：導入
講義概要，簡単なアルゴリズムの紹介
第2回[対面/face to face]：分枝限定法
k-SAT, 独立集合
第3回[対面/face to face]：動的計画法
いくつかの簡単な例と TSP
第4回[対面/face to face]：包除原理 (1)
包除原理の基本と簡単な例
第5回[対面/face to face]：包除原理 (2)
被覆問題や分割問題に対する具体的な例
第6回[対面/face to face]：木幅 (1)
木幅の定義と木幅を用いた動的計画法
第7回[対面/face to face]：木幅 (2)
準同型なグラフの数え上げ
第8回[対面/face to face]：測度統治法 (1)
測度統治法の基本，独立集合およびフィードバック頂点集合に対するアルゴリズム
第9回[対面/face to face]：測度統治法 (2)
支配集合に対するアルゴリズム，測度統治法の下界
第10回[対面/face to face]：集合の畳み込み
高速ゼータ変換，高速な集合の畳み込み
第11回[オンライン/online]：局所探索と SAT
ハミング空間とハミング距離を用いたアルゴリズム
第12回[対面/face to face]：Split and List
問題の分割と統合を用いた高速なアルゴリズム
第13回[対面/face to face]：時間計算量と空間計算量
時間計算量と空間計算量のトレードオフ
第14回[対面/face to face]：まとめ
講義全体のまとめと関連する話題の紹介
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
【本授業の準備・復習時間は、各４時間を標準とします。】
テキスト（教科書）Textbooks
本講義は，下記の書籍を土台に構成している．ただし，購入する必要はない．
Fedor V. Fomin and Dieter Kratsch, "Exact Exponential Algorithms," Springer, 2010.
参考書References
テキストに関連する文献情報が多数掲載されているため，それを参考にすること．
https://link.springer.com/book/10.1007/978-3-642-16533-7
成績評価の方法と基準Grading criteria
中間レポート 40 %，及び期末レポート 60% で成績を評価する．到達目標に対して60%以上の評価を得た場合合格となる．
学生の意見等からの気づきChanges following student comments
昨年度は輪講形式で行った．今年度も学生の理解度・事前知識に応じて柔軟に対応する．
学生が準備すべき機器他Equipment student needs to prepare
PDF を閲覧できる機器