授業の目的 【日本語】
Goals of the Course(JPN) | | | 離散数学特論では，グラフをはじめとする組合せ的対象に対する固定パラメータアルゴリズムおよびパラメータ化計算量の理論について学ぶ．離散数学特論2では特に，木幅などの構造的グラフパラメータを用いたパラメータ化アルゴリズム設計について学ぶ． |
|
|
授業の目的 【英語】
Goals of the Course | | | In the course of Discrete Mathematics, we learn the theory of fixed-parameter algorithms and parameterized complexity on combinatorial objects such as graphs. In the course of Discrete Mathematics 2, we particularly learn the design of parameterized algorithms using structural graph parameters such as treewidth. |
|
|
到達目標 【日本語】
Objectives of the Course(JPN) | | | グラフなどの離散的対象上で定義される問題に対して効率的な解法を設計する際，対象がもつ「よい」構造を利用して一般の場合に対する困難性を回避することが重要となる．そのために必要な，固定パラメータ容易性の理論を身につけることを目標とする． |
|
|
到達目標 【英語】
Objectives of the Course | | |
|
授業の内容や構成
Course Content / Plan | | 離散数学特論では，グラフをはじめとする組合せ的対象に対する固定パラメータアルゴリズムおよびパラメータ化計算量の理論について解説する．離散数学特論2では特に，木幅などの構造的グラフパラメータを用いたパラメータ化アルゴリズム設計について取り上げる．ガイダンスの後，以下の内容について講義する．
・パラメータ化計算量
・木に対するアルゴリズム
・木幅について
・木幅に基づくアルゴリズム
・アルゴリズム的メタ定理
・その他の構造的グラフパラメータ: 特殊化
・その他の構造的グラフパラメータ: 一般化
・その他のトピック | |
|
|
履修条件・関連する科目
Course Prerequisites and Related Courses | | 離散数学特論1で扱うレベルの固定パラメータ計算量の基礎を理解していること．
学部レベルの理論計算機科学の基礎（アルゴリズムとデータ構造，グラフ理論の基礎，計算量理論の基礎）を理解していること． | |
|
|
成績評価の方法と基準
Course Evaluation Method and Criteria | | | 期末試験（またはレポート課題）を100点満点で評価し，60点以上を合格とする． | |
|
|
教科書・参考書
Textbook/Reference book | | |
|
課外学習等（授業時間外学習の指示）
Study Load(Self-directed Learning Outside Course Hours) | | | 講義資料および講義中に示す参考資料を用い，毎回の講義の復習をすることが望ましい． | |
|
|
授業開講形態等
Lecture format, etc. | | |
|
遠隔授業（オンデマンド型）で行う場合の追加措置
Additional measures for remote class (on-demand class) | | |
|