理工学研究科Graduate School of Science and Engineering
MAT500X4（数学 / Mathematics 500）離散最適化特論２Discrete Optimization2
髙澤 兼二郎Kenjiro TAKAZAWA
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 理工学研究科Graduate School of Science and Engineering |
| 添付ファイル名Attached documents | |
| 年度Year | 2023 |
| 授業コードClass code | YC520 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 秋学期授業/Fall |
| 曜日・時限Day/Period | 月4/Mon.4 |
| 科目種別Class Type | |
| キャンパスCampus | 小金井 |
| 教室名称Classroom name | 各学部・研究科等の時間割等で確認 |
| 配当年次Grade | |
| 単位数Credit(s) | 2 |
| 備考（履修条件等）Notes | |
| 実務経験のある教員による授業科目Class taught by instructors with practical experience | |
| カテゴリーCategory | システム理工学専攻 |
すべて開くShow all
すべて閉じるHide All
Outline (in English)
Learn practical approaches to discrete optimization problems for which exact solutions are hard to find.
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
厳密解を求めるのが困難な離散最適化問題に対する実践的な手法を学ぶ．
到達目標Goal
実用上現れるNP 困難な離散最適化問題に対する，近似アルゴリズムをはじめとする解決手法を理論的に理解する．
この授業を履修することで学部等のディプロマポリシーに示されたどの能力を習得することができるか（該当授業科目と学位授与方針に明示された学習成果との関連）Which item of the diploma policy will be obtained by taking this class?
ディプロマポリシーのうち、「DP1」「DP2」「DP3」に関連
授業で使用する言語Default language used in class
日本語 / Japanese
授業の進め方と方法Method(s)（学期の途中で変更になる場合には、別途提示します。 /If the Method(s) is changed, we will announce the details of any changes. ）
講義形式で行う．必要に応じて，質疑応答，問題演習，および演習問題の解説の時間をとる．
アクティブラーニング（グループディスカッション、ディベート等）の実施Active learning in class (Group discussion, Debate.etc.)
あり / Yes
フィールドワーク（学外での実習等）の実施Fieldwork in class
なし / No
授業計画Schedule
授業形態/methods of teaching：対面/face to face
※各回の授業形態は予定です。教員の指示に従ってください。
1[対面/face to face]：イントロダクション
本授業の内容の概説
2[対面/face to face]：基礎
近似アルゴリズムの基礎
3[対面/face to face]：クラス PTAS
クラス PTAS の定義と問題例
4[対面/face to face]：クラス FPTAS
クラス FPTAS の定義と問題例
5[対面/face to face]：クラス log-APX とクラス poly-APX
クラス log-APX とクラス poly-APX の定義と問題例
6[対面/face to face]：線形計画による近似アルゴリズム設計
緩和解の整数ラウンディング
7[対面/face to face]：これまでのおさらい
これまでの講義内容のおさらい
8[対面/face to face]：施設配置問題
施設配置問題に対する近似アルゴリズム
9[対面/face to face]：k-センター問題
k-センター問題に対する近似アルゴリズム
10[対面/face to face]：k-メディアン問題
k-メディアン問題に対する近似アルゴリズム
11[対面/face to face]：シュタイナー森問題
シュタイナー森問題に対する近似アルゴリズム
12[対面/face to face]：最大充足化問題
最大充足化問題に対する近似アルゴリズム
13[対面/face to face]：半正定値計画問題
半正定値計画問題を用いた整数ラウンディングアルゴリズム
14[対面/face to face]：講義全体のまとめ
講義全体の内容の復習
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
【本授業の準備・復習時間は、各４時間を標準とします。】
離散数学や線形計画法について，適宜復習する．
テキスト（教科書）Textbooks
浅野孝夫: 近似アルゴリズム, 共立出版, 2019.
参考書References
D.P. Williamson, D.B.Shmoys (著), 浅野孝夫 (訳): 近似アルゴリズムデザイン, 共立出版, 2015.
V.V. Vazirani (著), 浅野孝夫 (訳): 近似アルゴリズム, 丸善出版, 2012.
D.P. Williamson, D.B.Shmoys: The Design of Approximation Algorithms, Cambridge University Press, 2011.
V.V. Vazirani: Approximation Algorithms, Springer, 2001.
成績評価の方法と基準Grading criteria
レポート（100%）によって評価する。平常点を加味することがある。
学生の意見等からの気づきChanges following student comments
具体的な例を示しながら講義することや，授業内に問題演習の時間を設けることを心がける．