In dieser Vorlesungen geht es um die Grundlagen des algorithmischen Denkens, insbesondere Algorithmendesign und -analyse. Wir werden uns dabei verschiedene algorithmische Fragestellungen ansehen, wie zum Beispiel das Finden kürzester Wege durch eine Stadt oder das Berechnen von Ähnlichkeitswerten für verschiedene Spezies anhand von DNA-Sequenzen. Es geht dabei immer um das Entwickeln effizienter Algorithmen.
Dieser Kurs gibt dabei einen Überblick über das Thema "Algorithm Engeneering" und bereitet auch optimal auf vertiefende Vorlesungen in diesem Bereich vor.
Auf einer abstrakten Ebene sind die Ziele 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ätslisten...).
Dabei werden wir klassische Probleme und ihre Lösungen kennenlernen; insbesondere befassen wir uns mit Problemen auf den folgenden Strukturen:
- Arrays (Sortieren, Suche...);
- Graphen (DFS/BFS, MST, Dijkstra, Eulerpfad...);
- Sequenzen (Edit-Distance, LCS...);
- Punktwolken (Sweeplinealgorithmen...).
