理工学研究科Graduate School of Science and Engineering
MAT500X4（数学 / Mathematics 500）オペレーションズ・リサーチ特論２Operations Research 2
千葉 英史Eishi CHIBA
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 理工学研究科Graduate School of Science and Engineering |
| 添付ファイル名Attached documents | |
| 年度Year | 2023 |
| 授業コードClass code | YC509 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 秋学期授業/Fall |
| 曜日・時限Day/Period | 月3/Mon.3 |
| 科目種別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)
Generally, a number of different algorithms can be considered for any computational problem, and we can derive most of such algorithms from certain design techniques. In this course, we study principal algorithm design techniques: divide-and-conquer, greedy algorithm, prune-and-search, dynamic programming, matrix searching, scaling algorithm, etc. Moreover, we learn how to analyze time complexity in order to evaluate the efficiency of algorithms. Students taking this course will come to understand that known algorithms are based on scientific methodologies, not just ideas.
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
1つの問題に対して様々なアルゴリズムが考えられるが，その多くはある種の設計技法から導くことが出来る．そこで本授業では，代表的な設計技法として，分割統治法，貪欲法，枝刈探索法，動的計画法，行列探索法，スケーリング法などを学ぶ．また，アルゴリズムの効率を評価するために，計算量解析のやり方を学ぶ．以上の内容を通して，既存のアルゴリズムが，単なる思いつきのものではなく，科学的な方法論に基づいたものであることを理解する．
到達目標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. ）
板書スタイル．必要に応じて，演習やCプログラミングを行う．
アクティブラーニング（グループディスカッション、ディベート等）の実施Active learning in class (Group discussion, Debate.etc.)
なし / No
フィールドワーク（学外での実習等）の実施Fieldwork in class
なし / No
授業計画Schedule
授業形態/methods of teaching：対面/face to face
※各回の授業形態は予定です。教員の指示に従ってください。
第1回[対面/face to face]：アルゴリズム設計の基礎（1）
再帰，分割統治法，動的計画法
第2回[対面/face to face]：アルゴリズム設計の基礎（2）
区間の探索，凸包
第3回[対面/face to face]：アルゴリズム設計の基礎（3）
連結リスト，データ構造，逆数の計算
第4回[対面/face to face]：分割統治法
マージソート，中央値の計算，凸包の計算
第5回[対面/face to face]：貪欲法
最小全域木，ナップサック問題，最短経路問題
第6回[対面/face to face]：枝刈探索法
2変数の線形計画問題
第7回[対面/face to face]：線形計画法
線形分離可能性問題，整数計画問題，充足可能性問題
第8回[対面/face to face]：動的計画法（1）
最長共通部分列，全点対間最短経路問題
第9回[対面/face to face]：動的計画法（2）
最適2分探索木，三角形分割
第10回[対面/face to face]：動的計画法（3）
連鎖行列積，ナップサック問題，巡回セールスマン問題
第11回[対面/face to face]：行列探索法
単調な行列，完全単調な行列
第12回[対面/face to face]：スケーリング法
最短経路問題
第13回[対面/face to face]：乱択アルゴリズム
モンテカルロアルゴリズム，ラスベガスアルゴリズム
第14回[対面/face to face]：近似アルゴリズム
ナップサック問題，PTAS，FPTAS
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
【本授業の準備・復習時間は、各４時間を標準とします。】
アルゴリズムやプログラムに関する基本的な内容を仮定して，授業は進められる．そのため必要に応じて，自ら勉強する必要がある．
テキスト（教科書）Textbooks
特になし．
参考書References
浅野 他，アルゴリズムイントロダクション第3版，近代科学社，2013．
浅野哲夫，計算幾何学，朝倉書店，1990.
成績評価の方法と基準Grading criteria
レポートから評価する．
学生の意見等からの気づきChanges following student comments
特に無し．