科目詳細情報 / Course Syllabus
| 科目分類 / Subject Categories | |||||||
|---|---|---|---|---|---|---|---|
| 学部等 / Faculty | 工芸科学部 / School of Science and Technology | 今年度開講 / Availability | 有 / Available | ||||
| 学域等 / Field | 設計工学域 / Academic Field of Engineering Design | 年次 / Year | ３年次 / 3rd Year | ||||
| 課程等 / Program | 機械工学課程・課程専門科目 / Specialized Subjects for Undergraduate Program of Mechanical Engineering | 学期 / Semester | 後学期 / Second term | ||||
| 分類 / Category | - / - | 曜日時限 / Day & Period | 火2 / Tue 2nd | ||||
| 科目情報 / Course Information | |||||
|---|---|---|---|---|---|
| 時間割番号 / Timetable Number | 12322201 | ||||
| 科目番号 / Course Number | 12360046 | ||||
| 単位数 / Credits | 2 | ||||
| 授業形態 / Course Type | 講義 / Lecture | ||||
| クラス / Class | - / - | ||||
| 授業科目名 / Course Title | 計画工学 / Optimization | ||||
|
担当教員名 Instructor(s) |
軽野 義行 | ||||
| KARUNO Yoshiyuki | |||||
| その他 / Other | インターンシップ実施科目 Internship |
国際科学技術コース提供科目 IGP |
PBL実施科目 Project Based Learning |
実務経験のある教員による科目 Practical Teacher |
|
| - | - | - | - | ||
| DX活用科目 ICT Usage in Learning |
- | - | - | ||
| - | - | - | - | ||
| 科目ナンバリング / Numbering Code | - | ||||
| 授業の目的・概要 Objectives and Outline of the Course |
|---|
| 所期の目標を最善の方法で達成するという最適化の概念は，科学の広い分野において欠かせないものである．本講義では，基本的な計画問題の中から，資源配分問題，最小全域木問題およびスケジューリング問題を取り上げる．それらの意義や解法を通して，（特に離散的な）最適化に必要な基礎事項を学べるようにする． |
| In this course, optimization problems and algorithmic solution approaches to the problems are treated. Resource allocation, minimum spanning tree and shop scheduling are selected as examples of more established (combinatorial) optimization problems. The course objective is to understand the importance of mathematical descriptions of optimization problems and fundamentals of the algorithm design and analysis through the selected examples. |
| 学習の到達目標 Learning Objectives |
|---|
| 1．関数のオーダー記法を理解する． 2．バブルソート，ヒープソート，クイックソートを理解する． 3．基本的な計画問題の定式化ができる． 4．基本的な計画問題に対するアルゴリズムを理解する． 5．基本的な計画問題の変形に対して妥当なアルゴリズムを構築することができる． |
| 1．To understand the big O notation. 2．To understand bubble sort, heap sort and quick sort algorithms. 3．To formulate optimization problems in terms of mathematical terminologies and notations. 4．To understand fundamental techniques in the algorithm design. 5．To solve optimization problems by applying algorithm design techniques. |
| 授業計画項目 / Course Plan | |||
|---|---|---|---|
| No. | 項目 Topics |
内容 Content |
オンライン授業 online class |
| 1. | 最適化入門 | 計画問題の具体例，履修上の注意． | |
| Introduction | Course guidance, Illustrations of optimization problems. | ||
| 2. | 計算手間の評価（１） | 計算とアルゴリズム，問題と問題例，関数のオーダー記法． | |
| Computational Complexity (1) | Algorithms, Data structures, Programming, Problems, Problem Instances, Order notations, Polynomial time complexity. | ||
| 3. | 計算手間の評価（２） | 同 上 （続き） | |
| Computational Complexity (2) | Ditto | ||
| 4. | 基本的なデータ構造 | リスト，根つき木，ヒープ． | |
| Elementary Data Structures | List, Rooted tree, Binary heap. | ||
| 5. | 整列のアルゴリズム（１） | バブルソート，ヒープソート，クイックソート，計算手間の下界． | |
| Sorting (1) | Bubble sort, Heap sort, Quick sort, Upper and lower bounds on the time complexity of sorting. | ||
| 6. | 整列のアルゴリズム（２） | 同 上 （続き） | |
| Sorting (2) | Ditto | ||
| 7. | 整列のアルゴリズム（３） | 同 上 （続き） | |
| Sorting (3) | Ditto | ||
| 8. | 整列のアルゴリズム（４） | 同 上 （続き） | |
| Sorting (4) | Ditto | ||
| 9. | 資源配分問題（１） | 限られた資源をいくつかの活動に配分するとき，経費や損失を最小化したい．資源管理の一例として，この問題を定式化するとともに，増分法の考え方に基づくアルゴリズムを説明する． | |
| Resource Allocation Problem (1) | Feasible solutions, Optimal solutions, Integer programming, Greedy algorithms, Practical applications. | ||
| 10. | 資源配分問題（２） | 同 上 （続き） | |
| Resource Allocation Problem (2) | Ditto | ||
| 11. | 最小全域木問題（１） | 連結な無向グラフの各辺に正の重みが付随するネットワークにおいて，すべての点を連結にする部分グラフのうちで，辺の重み和が最小になるものを求めたい．よく知られている多項式時間アルゴリズムの動作を説明する． | |
| Minimum Spanning Tree (1) | Undirected graphs, Edge cost function, Spanning tree, Polynomial time algorithms. | ||
| 12. | 最小全域木問題（２） | 同 上 （続き） | |
| Minimum Spanning Tree (2) | Ditto | ||
| 13. | スケジューリング（１） | CIM/FMS/FAなど，生産システム・物流システムの最適化におけるスケジューリングの意義を述べる．また，ショップ・スケジューリングの基本モデルと代表的なアルゴリズムを説明する． | |
| Scheduling Problems (1) | Shop scheduling, Gantt chart, Polynomially solvable problems, NP-hard problems, Flexible manufacturing systems, Material handling systems. | ||
| 14. | スケジューリング（２） | 同 上 （続き） | |
| Scheduling Problems (2) | Ditto | ||
| 15. | 関連する話題 | 以上の項目で取り上げられなかった話題を時間の許す限り紹介したい． | |
| Related Topics | Shortest paths, Vehicle scheduling, Subset sum. | ||
| 履修条件 Prerequisite(s) |
|---|
| プログラミングの経験を要求はしないが，あれば理解の助けになる． |
| Experience in programming is not required, but it is advantageous. |
|
授業時間外学習（予習・復習等） Required study time, Preparation and review |
|---|
| 本講義に対しては，67.5時間以上の予復習に充てる自己学習時間が必要である． |
| For the preparation and review of self-education, students are encouraged to spend at least 67.5 hours. |
| 教科書／参考書 Textbooks/Reference Books |
|---|
| 教科書「Cによるアルゴリズムとデータ構造 改訂2版」（茨木俊秀著，オーム社）および必要に応じてプリント配布/参考書「生産マネジメント」（徳山・曹・熊本著，朝倉書店） |
| Toshihide Ibaraki, Algorithms and Data Structures in C, 2nd Edition (in Japanese), 2019, Ohmsha, Tokyo / Hiroyuki Tokuyama, Hiroaki Matsukawa, and Kazuhiro Kumamoto, Production Management (in Japanese), 2002, Asakura Publishing, Tokyo. |
| 成績評価の方法及び基準 Grading Policy |
|---|
| 学期末試験50%および復習ノート50%の合計100%で評価し，60%以上の得点を合格とする．整列と基本的な計画問題に対するアルゴリズムについて，それらの動作と正当性を理解していると判定できれば，少なくとも合格に必要な点数は与えられる． |
| Review report 50% + End-of-term exam 50% = Total 100%. Credit is granted when the achievement is no less than 60%. |
| 留意事項等 Point to consider |
|---|
| (i) 学習・教育目標B(3)(a)に対応する科目であり，達成度評価の対象である．(ii) 授業開始後の入室を原則的に認めていない．(iii) スケジューリングの項目では，定規を持参しておくと便利である． |
| This is one of the courses in B(3)(a) of our accredited education program. |
| 評価基準 / Evaluation Standards | ||
|---|---|---|
| 科目の達成目標 Course Goals |
||
| 1．関数のオーダー記法を理解する． 2．バブルソート，ヒープソート，クイックソートを理解する． 3．基本的な計画問題の定式化ができる． 4．基本的な計画問題に対するアルゴリズムを理解する． 5．基本的な計画問題の変形に対して妥当なアルゴリズムを構築することができる． |
||
| 1．To understand the big O notation. 2．To understand bubble sort, heap sort and quick sort algorithms. 3．To formulate optimization problems in terms of mathematical terminologies and notations. 4．To understand fundamental techniques in the algorithm design. 5．To solve optimization problems by applying algorithm design techniques. |
||
| 目標の達成度の評価基準 / Fullfillment of Course Goals | ||
| 1. | 目標レベルを大きく下回る Significantly lower than target level |
整列のアルゴリズム（バブルソート，ヒープソート，クイックソート）を理解できない． |
| No understanding of sorting algorithms (Bubble sort, Heap sort, Quick sort). | ||
| 2. | 目標レベルを僅かに下回る Slightly lower than target level |
整列のアルゴリズムを理解しているが，基本的な計画問題に対するアルゴリズムを理解できない． |
| Understanding of sorting algorithms, but lack of understanding of fundamentals in the algorithm design. | ||
| 3. | 目標レベルに到達 Achieved target level |
整列のアルゴリズムおよび基本的な計画問題に対するアルゴリズムを理解している． |
| Understanding of sorting algorithms and fundamentals in the algorithm design. | ||
| 4. | 目標レベルを上回る Above target level |
整列のアルゴリズムと基本的な計画問題に対するアルゴリズムについて理解が十分であり，基本的な計画問題の変形に対して妥当と思われるアルゴリズムを構築できる． |
| Sufficient understanding of sorting algorithms and fundamentals in the algorithm design, and applicability. | ||