|
システム最適化_E
|
|
| Instructor(s) |
Takahito Kuno, Yoshio Sano
|
| T. Kuno: takahito (at) cs.tsukuba.ac.jp, Y. Sano: sano (at) cs.tsukuba.ac.jp | |
| URL | https://manaba.tsukuba.ac.jp |
| Office hours | F932 (T. Kuno), F834 (Y. Sano), A/N (appointment necessary) |
| Cource# | 01CH109 |
| Area | Information Mathematics and Modeling |
| Basic/Advanced | 基礎科目 |
| Course style | Lecture |
| Term | SprA |
| Period | Tue3,4 |
| Room# | 3B311 |
| Keywords | Mathematical Optimization, Algorithms, Computational Complexity |
| Prerequisites | Linear Algebra, Calculus |
| relation degree program competence | Knowledge Utilization Skills, Management Skills, International Skills, Research Skills, Expert Knowledge |
| Goal | |
| Outline | This course treats selected topics in mathematical optimization and computational complexity. |
| Course plan |
Lecure 1: Introduction to Mathematical Optimization (Optimization Problem, Linear Programming, Integer Programming, Combinatorial Optimization, Traveling Salesman Problem, Shortest Path Problem, Algorithm, Computational Complexity) Lecture 2: Algorithms and Computational Complexity (Shortest Path Problem, Bellman-Ford Algorithm, Knapsack Problem, Dynamic Programming) Lecture 3: NP-Completeness and Complexity Classes (Decision Problem, Class P, Class NP, NP-completeness, NP-hardness, Polynomial-time Reduction, Karp's 21 NP-complete problems, Cook's Theorem) Lecture 4: Efficient Algorithms and Mathematical Structure (Maximum Spanning Tree Problem, Matroid, Independent Set, Base, Rank Function, Circuit, Greedy Algorithm, Characterization) Lecture 5: Algorithm Design for Hard Optimization Problems (Knapsack Problem, Heuristics, Approximation Algorithm, Enumeration, Branch and Bound) |
| Textbook | Class materials are distributed via web. |
| References |
[1] B. Korte and J. Vygen: Combinatorial Optimization: Theory and Algorithms, Sixth Edition (Algorithms and Combinatorics 21), Springer (2018) [2] J. Kleinberg and E. Tardos: Algorithm Design, Pearson (2005) [3] A. Schrijver: Combinatorial Optimization: Polyhedra and Efficiency (Algorithms and Combinatorics 24), Springer (2003) |
| Evaluation |
Evaluate based on reports. Evaluation criteria: A passing score is 60% of the total score. Scores A+ to C are based on this score. |
| TF / TA | |
| Misc. | |