理工学研究科Graduate School of Science and Engineering
MAT500X4（数学 / Mathematics 500）離散最適化特論１Discrete Optimization１
髙澤 兼二郎Kenjiro TAKAZAWA
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 理工学研究科Graduate School of Science and Engineering |
| 添付ファイル名Attached documents | |
| 年度Year | 2022 |
| 授業コードClass code | YC519 |
| 旧授業コード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 the basis of algorithm design for discrete optimization problems.
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
離散最適化アルゴリズムの基本的な設計手法を学ぶ。
到達目標Goal
離散最適化アルゴリズムの設計手法を習得する。自分が解きたい問題に対し、アルゴリズム的思考によって望ましい解を計算できるようになる。
この授業を履修することで学部等のディプロマポリシーに示されたどの能力を習得することができるか（該当授業科目と学位授与方針に明示された学習成果との関連）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.)
なし / No
フィールドワーク（学外での実習等）の実施Fieldwork in class
なし / No
授業計画Schedule
授業形態/methods of teaching：対面/face to face
※各回の授業形態は予定です。教員の指示に従ってください。
1[対面/face to face]：イントロダクション
本授業で取り扱う内容についての概説、および、授業の進め方についてのガイダンス
2[対面/face to face]：計算量とオーダー記法
アルゴリズム性能の重要な指標である計算量とその表記方法
3[対面/face to face]：全探索
あらゆるアルゴリズムの基礎となる全探索アルゴリズムの設計
4[対面/face to face]：分割統治法
再帰を活用した分割統治法によるアルゴリズム設計
5[対面/face to face]：動的計画法
動的計画法による実践的なアルゴリズム設計
6[対面/face to face]：二分探索
二分探索を用いた様々な問題に対する効率的なアルゴリズム設計
7[対面/face to face]：貪欲法
貪欲法によるアルゴリズム設計とその性能
8[対面/face to face]：これまでのまとめ
これまでの内容の復習
9[対面/face to face]：データ構造 (1)
配列，連結リスト，ハッシュテーブル
10[対面/face to face]：データ構造 (2)
スタックとキュー
11[対面/face to face]：データ構造 (3)
グラフと木
12[対面/face to face]：データ構造 (4)
Union-Find
13[対面/face to face]：ソート
様々なソートアルゴリズム
14[対面/face to face]：まとめ
全体の復習
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
【本授業の準備・復習時間は、各４時間を標準とします。】授業で扱ったアルゴリズムを自分で実装することを推奨する。
テキスト（教科書）Textbooks
大槻兼資(著)，秋葉拓哉(監修)，アルゴリズムとデータ構造，講談社，2020．
参考書References
米田優峻，問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本，技術評論社，2021．
成績評価の方法と基準Grading criteria
レポート (100%) によって評価する。
学生の意見等からの気づきChanges following student comments
授業内容の習熟度を向上させるため、問題演習や質疑応答の時間を十分にとる。