back to search

Computational Complexity in Optimization

MA5222Elective Modules5 ECTSEnglishUnregelmäßigDepartment Mathematics
AI-edited module sheet. Based on the TUMonline module description, edited for readability.Original in TUMonline

What it is about

You learn the fundamentals of complexity theory with a focus on optimization problems: formal models, classes such as P and NP, NP-completeness and typical NP-hard optimization tasks. In the end you will be able to assess the difficulty of optimization problems, apply appropriate modeling guidelines, and analyze practical examples.

What you will be able to do

  • Understanding of alphabets, languages and problems
  • Knowledge of Turing machines as well as the classes P and NP
  • Explanation and application of NP-completeness (including Cook's theorem)
  • Analysis of typical NP-hard optimization problems (SAT, ILP, Hamilton cycles, partitioning, norm maximization, feasible subsystems)
  • Application of modeling and analysis techniques to practical problems

What the module consists of

  • VorlesungTransmission of theoretical foundations and demonstrative examples
  • Übung/Practice sessionsWorking on problem sheets and deepening the methods; self-check through solutions
  • Hausaufgabenpractical application and practice of the relevant techniques

Teaching method

  • Lehrvortrag (teacher-centered)Presentation of the contents with examples for introduction and motivation
  • Übungen mit Hands-on-ArbeitIndependent deepening, application of the methods and checking learning progress
No dates in the current semester
There are no course dates for this module this semester, or they haven't been matched yet.

Module ratings

No ratings for this module yet.

Rate this module

Only fill in the categories you can judge – for each one, either stars and text together or nothing at all.

Lecture
Tutorial
Exam

Reviews are automatically checked before they are published.

Official page in TUMonline · Details are not binding.