LTI
LTI

Höhere Algorithmik

Vorlesung

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. Max-Fluss-Problem.

Weitere Themen: Medianberechnung. Die probabilistische Methode.


Folien
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.

ESA/ALGO 2019 wird von Susanne Albers und ihrer Gruppe organisiert.

Dezember 2017: Susanne Albers hält Festvortrag am Tag der Informatik, Absolventenfest der RWTH Aachen.

April 2017: Neues DFG Graduiertenkolleg AdONE.

Susanne Albers erhaelt ERC Advanced Grant. Pressemitteilung Bayerisches Staatsministerium f. Bildung u. Kultus, Wissenschaft u. Kunst.

August 2016: Susanne Albers hält einen Plenarvortrag auf Euro-Par 2016, Grenoble.

Susanne Albers, Nicole Megow und Andreas S. Schulz organisieren MAPSP 2017.

Juni 2016: Susanne Albers hält einen eingeladenen Vortrag in der Akademie der Wissenschaften und der Literatur, Mainz.

September 2015: Susanne Albers ist eingeladene Sprecherin auf dem MPI-INF – 25th Anniversary. Vortragende im Programm sind mehrere Turing-Preisträger, Leibniz-Preisträger, Humboldt-Preisträger und Gewinner von ERC Grants.

Juni 2015: Susanne Albers hält einen Plenarvortrag auf dem 31st International Symposium on Computational Geometry (SOCG15), Eindhoven.

Juni 2015: Susanne Albers ist eingeladene Sprecherin des Tutorials Network Creation Games: How Does the Internet Form?, organisiert von Erik D. Demaine (MIT) und MohammadTaghi Hajiaghayi (University of Maryland). 16th Conference on Electronic Commerce (EC15), Portland, Oregon.

Lehrstuhl für Algorithmen und Komplexität
Prof. Dr. Susanne Albers

Boltzmannstr. 3
85748 Garching bei München

Tel +89.289.17706
Fax +89.289.17707

E-Mail
Aktuelles