授業の目的 【日本語】
Goals of the Course(JPN) | | | 離散数学特論では，グラフをはじめとする組合せ的対象に対するアルゴリズム設計について学ぶ．組合せ最適化問題は多くの場合多項式時間アルゴリズム設計が困難であることが知られている．離散数学特論2では特に，そのような問題に対する低次の指数時間アルゴリズム，固定パラメータアルゴリズム設計について学ぶ． |
|
|
授業の目的 【英語】
Goals of the Course | | | In the course of Discrete Mathematics, we learn the design of algorithms on combinatorial objects such as graphs. Combinatorial optimization problems are known to be hard to design polynomial-time algorithms. In the course of Discrete Mathematics 2, we particularly learn the design of fast exact exponential algorithms and fixed parameter algorithms for computationally hard problems. |
|
|
到達目標 【日本語】
Objectives of the Course(JPN) | | | 離散的に存在する考察対象から有益な情報を取り出そうとするとき，それらを単なる物の集まりとしてではなく 離散系として捉え理解することが第⼀歩であり，さらに分析し解析するためには，離散系に対する数学的基礎理論 を修得していることが非常に重要である。 このような数学的な思考法を⾝に着けることを目標とする。 |
|
|
到達目標 【英語】
Objectives of the Course | | |
|
授業の内容や構成
Course Content / Plan | | 離散数学特論では，グラフをはじめとする組合せ的対象に対するアルゴリズム設計について解説する。 離散数学特論2では特に，そのような問題に対する低次の指数時間アルゴリズム，固定パラメータアルゴリズム設計について学ぶ．ガイダンスの後，以下のトピックについて講義する．
・ 計算困難性
・パラメータ化アルゴリズムの概念
・頂点被覆問題に対するアルゴリズム
・動的計画法
・分枝アルゴリズム
・カーネル化
・木幅に基づく
・その他のトピック | |
|
|
履修条件・関連する科目
Course Prerequisites and Related Courses | | | 学部レベルの理論計算機科学の基礎（アルゴリズムとデータ構造，グラフ理論の基礎，計算量理論の基礎）を理解していること． | |
|
|
成績評価の方法と基準
Course Evaluation Method and Criteria | | | レポート課題への解答を１００点満点で評価し，６０点以上を合格とする。 | |
|
|
教科書・参考書
Textbook/Reference book | | |
|
課外学習等（授業時間外学習の指示）
Study Load(Self-directed Learning Outside Course Hours) | | 毎回レポート課題を課す。
また，講義で完全に証明し切れなかった部分を⾃ら補うことが望ましい。 | |
|
|
授業開講形態等
Lecture format, etc. | | |
|
遠隔授業（オンデマンド型）で行う場合の追加措置
Additional measures for remote class (on-demand class) | | |
|