学部・大学院区分
Undergraduate / Graduate		情報・博前
時間割コード
Registration Code		2510020
科目区分
Course Category
主専攻科目
科目名　【日本語】
Course Title		離散数学特論2
科目名　【英語】
Course Title		Discrete Mathematics 2
コースナンバリングコード
Course Numbering Code		GSI116020J
担当教員　【日本語】
Instructor		大舘 陽太 ○ 佐藤 潤也 柳浦 睦憲 小野 廣隆
担当教員　【英語】
Instructor		OTACHI Yota ○ SATOH Junya YAGIURA Mutsunori ONO Hirotaka
単位数
Credits		1
開講期・開講時間帯
Term / Day / Period		春２期 木曜日 ３時限
Spring2 Thu 3
対象学年
Year		１年
1
授業形態
Course style
開講系（学部）・開講専攻（大学院）
Subject
数理情報学専攻
必修・選択
Required / Selected


授業の目的　【日本語】
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 learn in particular the design of parameterized algorithms using advanced methods such as randomization and integer programming.
到達目標　【日本語】
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)