理工学研究科Graduate School of Science and Engineering
PRI500X3（情報学基礎 / Principles of informatics 500）理論計算機科学特論２Theoretical Computer Science 2
和佐 州洋Kunihiro WASA
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 理工学研究科Graduate School of Science and Engineering |
| 添付ファイル名Attached documents | |
| 年度Year | 2022 |
| 授業コードClass code | YB003 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 秋学期授業/Fall |
| 曜日・時限Day/Period | 木2/Thu.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)
We often encounter intractable problems in our daily life. In this course, students learn how we deal with such problems. In particular, we learn how to develop efficient algorithms with respect to the parameters of problems. The aim of this course is that students understand the basics of parameterized algorithms.
By the end of this course, students should be able to do the following:
Students can explain basic techniques for developing parameterized algorithms.
Students can explain the definition of treewidth.
Students can explain the definition of the intractability of parameterized problems.
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
Term-end report: 60%、Mid-term exam: 40%.
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
理論計算機科学を学び始めてすぐに，自然な問題の多くはNP困難であることに気が付く．このような問題に対して，我々は何もできないのだろうか．一見すると容易に解くことができないように見える問題も，問題に潜むある種の特徴に着目すると，限定された状況においては効率よいアルゴリズムが存在することを示すことができる．本講義では，このようなアルゴリズムの構築技法に関して，パラメータという観点からその基礎を学ぶ．
到達目標Goal
固定パラメータ容易性に関する基礎的な概念の習得を目指す．具体的には，Kernelization や Bounded search tree，Iterative compression などの技法を用いたアルゴリズムの構成方法を説明できること，木幅の定義と木幅を用いたアルゴリズムの構成方法を説明できること，固定パラメータの下での困難性の定義を説明できることを目標とする．
この授業を履修することで学部等のディプロマポリシーに示されたどの能力を習得することができるか（該当授業科目と学位授与方針に明示された学習成果との関連）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]：Kernlization (1)
定義，簡単なカーネルの導入
第3回[対面/face to face]：Kernlization (2)
Crown decomposition, expansion lemma
第4回[対面/face to face]：Bounded search trees (1)
Bounded search tree に関する基本的な考え方，頂点被覆に対するアルゴリズム
第5回[対面/face to face]：Bounded search trees (2
Feedback vertex set, closest string に対するアルゴリズム
第6回[対面/face to face]：Iterative compression (1)
Iterative compression に対する基本的な考え方，Feedback vertes set に対するアルゴリズム (1)
第7回[対面/face to face]：Iterative compression (2)
Feedback vertes set に対するアルゴリズム (2), Odd cycle transversal に対するアルゴリズム
第8回[対面/face to face]：中間試験
前半の内容に関する試験
第9回[対面/face to face]：Dynamic programming
Set Cover, Steiner tree, Inclusion-exclusion principle を用いたアルゴリズム
第10回[対面/face to face]：Treewidth (1)
木幅の定義, Weighted independent set と Steiner tree に対するアルゴリズム
第11回[対面/face to face]：Treewidth (2)
Courcelle の定理
第12回[対面/face to face]：Treewidth (3)
Grid theorem, Bidimentionality
第13回[対面/face to face]：The W-hierarchy
定義，Parameteized reduction，W[1]完全な問題
第14回[対面/face to face]：The Exponential-Time Hypothesis
ETH と SETH の定義，古典的な結果との関係
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
【本授業の準備・復習時間は、各４時間を標準とします。】
テキスト（教科書）Textbooks
教科書は指定しない．
参考書References
本講義は次の図書を参考にして授業を組み立てている．
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms, Springer International Publishing, 2015.
成績評価の方法と基準Grading criteria
レポート (60%) と 中間試験 (40%) で評価する．到達目標に対して，60% 以上の評価を獲得した学生を合格とする．
学生の意見等からの気づきChanges following student comments
本年度授業担当者変更によりフィードバックできません