Datenstrukturen & Algorithmen

Abstract

Der Kurs vermittelt die Grundlagen für den Entwurf und die Analyse von Algorithmen.Anhand klassischer Probleme werden gängige Datenstrukturen, Algorithmen und Paradigmen für den Algorithmenentwurf diskutiert.Der Kurs umfasst auch eine Einführung in die parallele und nebenläufige Programmierung und das Programmiermodell von C++ wird eingehend diskutiert.

Objective

Verständnis des Entwurfs und der Analyse grundlegender Algorithmen und Datenstrukturen. Wissen um die Chancen, Probleme und Grenzen der parallelen und nebenläufigen Programmierung. Vertiefter Einblick in ein modernes Programmiermodell anhand der Prorgammiersprache C++.

Content

Datenstrukturen und Algorithmen: Mathematische Tools für die Analyse von Algorithmen (asymptotisches Funktionenwachstum, Rekursionsgleichungen, Rekursionsbäume), informelle Beweise für die Korrektheit von Algorithmen (Invarianten und Codetransformation), Entwurfsparadigmen für die Entwicklung von Algorithmen (Induktion, Divide-and-Conquer, Sweep-Line-Methode, Backtracking und dynamische Programmierung), klassische algorithmische Probleme (Suche, Auswahl und Sortierung), Datenstrukturen für verschiedene Zwecke (verkettete Listen, Hash-Tabellen, balancierte Suchbäume, Quad-Trees, Heaps, Union-Find), weitere Tools für die Laufzeitanalyse (z.B. amortisierte Analyse). Die Beziehung und enge Kopplung zwischen Algorithmen und Datenstrukturen wird anhand von geometrischen Problemen (konvexe Hülle, Linienschnitte, dichteste Punktepaare) und Graphenalgorithmen (Traversierungen, topologische Sortierung, transitive Hülle, kürzeste Pfade, minimale Spannbäume, maximaler Fluss) illustriert. Programmiermodell von C++: korrekte und effiziente Speicherbehandlung, generische Programmierung mit Templates, funktionale Ansätze mit Funktoren und Lambda-Ausdrücken. Parallele Programmierung: Konzepte der parallelen Programmierung (Amdahl/Gustavson, Task/Daten-Parallelität, Scheduling), Probleme der Nebenläufigkeit (data races, bad interleavings, memory reordering), Prozess-Synchronisation und Kommunikation in einem Shared-Memory-System (Mutual Exclusion, Semaphoren, Monitore, Condition-Variablen), Fortschrittsbedingungen (Deadlock-Freiheit, Starvation). Die im Kurs vermittelten Konzepte werden mit praktisch relevanten Algorithmen und Anwendungen motiviert und illustriert. Die Übungen werden in Code-Expert, einer Online-IDE und einem Übungsmanagementsystem, durchgeführt. Alle benötigten mathematischen Tools ausserhalb des Schulwissens werden im Kurs behandelt, einschliesslich einer Einführung zur Graphentheorie.

Resources