システム最適化_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, BellmanFord Algorithm, Knapsack Problem, Dynamic Programming) Lecture 3: NPCompleteness and Complexity Classes (Decision Problem, Class P, Class NP, NPcompleteness, NPhardness, Polynomialtime Reduction, Karp's 21 NPcomplete 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. 