Höhere Algorithmik

• Dozent:
  Prof. Dr. Susanne Albers
• Modul: IN2360, TUMonline
• Bereich:
  3+2 SWS Vorlesung + Übung im Bereich Informatik III (Theoretische Informatik)
  Wahlpflichtvorlesung im Gebiet Algorithmen
• Zeit und Ort:
  Dienstag, 12:00–14:00, 8120.EG.001, Hörsaal im Galileo
  Donnerstag, 12:00–14:00, 8120.EG.001, Hörsaal im Galileo
• Übung: 
  Dienstag, 14:00–16:00, in 02.04.011 
  Donnerstag, 14:00–16:00, in 01.07.023 
  Tutorien: Tobias Forner 
  Weitere Informationen werden auf Moodle veröffentlicht.
• Hörerkreis:
  Studierende im Hauptstudium der Informatik
  Studierende mit Nebenfach Informatik
• ECTS: 6 Punkte
• Voraussetzungen:
  Stoff des Informatik Grundstudiums
• Klausurtermin:
  Präsenzprüfung, Termin wird noch bekannt gegeben

Inhalt

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.

Literatur

• Th. Cormen, C. Leiserson, R. Rivest and C. Stein. Introduction to Algorithms. Third Edition, MIT Press, 2009.
• J. Kleinberg and E. Tardos. Algorithm Design. Pearson. Addison Wesley, 2006.
• M. Mitzenmacher and E. Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Second Edition, Cambridge University Press, 2017.
• Th. Ottmann und P. Widmayer. Algorithmen und Datenstrukturen. 6. Auflage, Springer Verlag, 2017.