授業の目的 【日本語】 Goals of the Course(JPN) | | 離散数学特論では,グラフをはじめとする組合せ的対象に対する固定パラメータアルゴリズムおよびパラメータ化計算量の理論について学ぶ.離散数学特論1では特に,固定パラメータ容易性の基礎やカーネル化などについて学ぶ. |
|
|
授業の目的 【英語】 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 1, we particularly learn the fundamental of fixed-parameter tractability and kernelization. |
|
|
到達目標 【日本語】 Objectives of the Course(JPN) | | グラフなどの離散的対象上で定義される問題に対して効率的な解法を設計する際,対象がもつ「よい」構造を利用して一般の場合に対する困難性を回避することが重要となる.そのために必要な,固定パラメータ容易性の理論を身につけることを目標とする. |
|
|
到達目標 【英語】 Objectives of the Course | | |
|
授業の内容や構成 Course Content / Plan | | 離散数学特論では,グラフをはじめとする組合せ的対象に対する固定パラメータアルゴリズムおよびパラメータ化計算量の理論について解説する.離散数学特論1では特に,固定パラメータ容易性の基礎やカーネル化などについて取り上げる.ガイダンスの後,以下の内容について講義する.
・計算量理論の基礎
・固定パラメータ容易性
・カーネル化の理論
・探索木の解析
・逐次圧縮法
・乱択手法の適用
・固定パラメータ困難性
・その他のトピック | |
|
|
履修条件・関連する科目 Course Prerequisites and Related Courses | | 学部レベルの理論計算機科学の基礎(アルゴリズムとデータ構造,グラフ理論の基礎,計算量理論の基礎)を理解していること. | |
|
|
成績評価の方法と基準 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) | | |
|