| Beschreibung |
Die diskrete und kombinatorische Optimierung ist ein Fachgebiet an der Schnittstelle zwischen Mathematik und Informatik. Anwendungen für derartige Optimierungsprobleme finden sich in unterschiedlichsten Bereichen. Im Mittelpunkt stehen Probleme der diskreten Optimierung, die häufig nicht effizient lösbar sind (z. B. NP-harte Probleme). Es werden sowohl exakte Verfahren (wie die lineare Programmierung und Backtracking) als auch Heuristiken und Metaheuristiken behandelt. Zudem wird untersucht, wie sich Baumzerlegungen zur Entwicklung effizienter Algorithmen nutzen lassen. |
| engl. Beschreibung/ Kurzkommentar |
Discrete Optimization
Discrete / combinatorial optimization is an area at the borderline of mathematics and computer science. Applications for such optimization problems can be found in the most varied areas.
Consideration is given to discrete optimization problems, which are efficiently solvable (e.g. shortest paths, flow problems), as well as NP-hard problems. For the latter, both exact methods (greedy algorithms on matroids, branch-and-bound methods), as well as heuristics and metaheuristics, are introduced.
|
| Literatur |
J. Kleinberg, E. Tardos, Algorithm Design, Addison Wesley, 2005.
C. H. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Books on Computer Science, 2000 |
