Effiziente Algorithmen
| Inhalt: |
| In dieser Vorlesung werden das Design und die Analyse effizienter Algorithmen unter Berücksichtigung der verwendeten Datenstrukturen behandelt. Die Themen sind unter anderem polynomielle exakte Algorithmen für Graphen- oder Satisfiabilityprobleme sowie Approximationsalgorithmen für einige Graphenparameter wie chromatische Zahl und Cliquenzahl und ihre Analyse, wobei sowohl deterministische als auch randomisierte Algorithmen und damit zusammenhängende Derandomisierungstechniken vorgestellt werden. Weiter werden die Themen semidefinite Programmierung, Online-Algorithmen (z.B. für das Ski Rental Problem), die Maximierung von Flüssen in Netzwerken und ihre Anwendungen sowie andere Optimierungsheuristiken betrachtet und die Laufzeit und Güte des jeweils verwendeten Algorithmus analysiert. |
| Literatur: |
|
| Teilnehmer: |
| Studierende der Informatik, Mathematik und ggf. weiterer Fachrichtungen |
| Übungen: |
