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


授業の目的　【日本語】
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)