"I would rather have today's algorithms on yesterday's computers than vice versa." -- Philippe Toint
Effiziente Algorithmen sind das mächtigste und vielfältigste Werkzeug der Informatik. Es gibt viele Möglichkeiten, um ein gegebenes Problem zu lösen und die Suche nach einer geeigneten Lösungsidee erfordert Kreativität und eine strukturierte Herangehensweise. Die Mühe lohnt sich, denn eine gute algorithmische Idee und deren effiziente Implementierung ist oftmals viel mehr Wert als pure Rechenkraft.
In dieser Vorlesungen geht es um die Grundlagen des algorithmischen Denkens, insbesondere Algorithmendesign und -analyse. Wir werden uns dabei verschiedene algorithmische Fragestellungen ansehen und effiziente Algorithmen zu deren Lösung entwerfen und analysieren.
Dieser Kurs gibt dabei einen Überblick über das Thema "Algorithm Engineering" und bereitet auch optimal auf vertiefende Vorlesungen in diesem Bereich vor.
Auf einer abstrakten Ebene ist das Ziel des Kurses, Fähigkeiten in den folgenden Bereichen zu entwickeln:
- Algorithmenanalyse;
- Algorithmendesign;
- Formalisierung von Problemstellungen.
Konkret beschäftigen wir uns mit den folgenden Themen:
- Techniken des Algorithmendesign (Greedy, Brute Force, Divide and Conquer, Dynamic Programming,...);
- Techniken der Algorithmenanalyse (Laufzeitbestimmung, amortisierte Analyse, Korrektheitsbeweise, Schleifeninvarianten,...);
- Datenstrukturen (für Graphen, Suchbäume, Prioritätswarteschlagen, Mengenverwaltung,...).
- Analyse der Komplexität von Problemen (NP-Schwere, Polynomialzeitreduktionen,...)
- Umgang mit schweren Problemen (Approximationsalgorithmen, spezielle Instanzklassen,...)
