Approximationsalgorithmen | Das Universitätsnetzwerk

Beschreibung

Viele reale algorithmische Probleme können mit herkömmlichen algorithmischen Werkzeugen nicht effizient gelöst werden, beispielsweise weil die Probleme NP-schwer sind. Ziel dieses Kurses ist es, sich mit wichtigen algorithmischen Konzepten und Techniken vertraut zu machen, die zur effektiven Bewältigung solcher Probleme erforderlich sind. Diese Techniken werden angewendet, wenn wir nicht die optimale Lösung für bestimmte Probleme benötigen, sondern eine Annäherung, die der optimalen Lösung nahe kommt. Wir werden sehen, wie solche Annäherungen effizient gefunden werden können.

Voraussetzungen:
Um diesen Kurs erfolgreich absolvieren zu können, sollten Sie bereits über Grundkenntnisse in Algorithmen und Mathematik verfügen. Hier ist eine kurze Liste dessen, was Sie wissen sollten:
- O-Notation, Ω-Notation, Θ-Notation; wie man Algorithmen analysiert
- Grundrechnung: Manipulieren von Summationen, Lösen von Wiederholungen, Arbeiten mit Logarithmen usw.
- Grundlegende Wahrscheinlichkeitstheorie: Ereignisse, Wahrscheinlichkeitsverteilungen, Zufallsvariablen, Erwartungswerte usw.
- Grundlegende Datenstrukturen: verknüpfte Listen, Stapel, Warteschlangen, Haufen
- (ausgeglichene) binäre Suchbäume
- Grundlegende Sortieralgorithmen, zum Beispiel MergeSort, InsertionSort, QuickSort
- Graphenterminologie, Darstellungen von Graphen (Adjazenzlisten und Adjazenzmatrix), grundlegende Graphalgorithmen (BFS, DFS, topologische Sortierung, kürzeste Wege)

Das Material für diesen Kurs basiert auf den Kursnotizen, die Sie auf der Registerkarte Ressourcen finden. Wir werden nicht alles aus den Kursnotizen behandeln. Die Kursnotizen sind sowohl für Studenten gedacht, die die Vorlesungen nicht vollständig verstanden haben, als auch für Studenten, die tiefer in die Themen eintauchen möchten.

Die Videovorträge enthalten einige sehr kleine Fehler. Eine Liste dieser Fehler finden Sie unter Ressourcen (im Dokument „Errata“). Wenn Sie glauben, einen Fehler gefunden zu haben, melden Sie ein Problem, indem Sie auf die quadratische Flagge unten in der Vorlesung oder im Quiz klicken, in der Sie den Fehler gefunden haben.