Das Modul behandelt grundlegende und klassische Themen aus dem Bereich der effizienten Algorithmen. Dabei werden zentrale Techniken des Algorithmenentwurfs und der Analyse studiert. Konkret behandelt das Modul die Methoden Divide-and-Conquer, dynamische Programmierung, Randomisierung, Greedy-Verfahren sowie amortisierte Analyse. Diese Techniken werden angewandt, um grundlegende algorithmische Probleme zu lösen.
Divide and Conquer: Einführung: deterministischer Quicksort. Geometrisches Divide-and-Conquer: Problem des dichtesten Punktepaars; Schnitt von Liniensegmenten; Voronoi-Diagramme. Schnelle Fourier-Transformation (FFT).
Randomisierte Algorithmen: Las-Vegas und Monte-Carlo-Algorithmen. Randomisierter Quicksort. Randomisierter Primzahltest mit Anwendungen in Public-Key-Verschlüsselungsverfahren. Verifikation von Matrixmultiplikationen.
Datenstrukturen: Treaps – randomisierte Suchbäume. Suffixbäume.
Amortisierte Analyse: Dynamische Tabellen. Fibonacci-Heaps.
Greedy-Algorithmen: Einführung. Ablaufplanung von Zeitintervallen (Intervall-Scheduling). Planung mit dem Ziel der Minimierung von Verspätungen. Kürzeste Wege in Graphen.
Dynamische Programming: Einführung. Gewichtetes Intervall-Scheduling. Matrixkettenprodukt. Konstruktion von optimalen Suchbäumen. Segmentierung von Datenpunkten. Teilsummen- und Rucksackprobleme.
Graphenalgorithmen: Berechnung von minimalen Schnitten.
Komplexität: PSPACE – eine Klasse von Problemen oberhalb NP. Relaxierte Komplexitätsmaße.
Weitere Themen: Medianberechnung. Die probabilistische Methode.