Höhere Algorithmik II Sommersemester 2015

Wolfgang Mulzer, Lena Schlipf, Yannik Stein

Aktuelles

Allgemein

Die Übungszettel werden ausschließlich online erscheinen und zwar hier auf dieser Seite.

Themenübersicht

  • Probabilistische Algorithmen
  • String Algorithmen
  • Arithmetische Algorithmen
  • Approximationsalgorithmen
  • Lineares Programmieren
  • Parametrische Suche
  • Hashing
  • Fortgeschrittene Komplexitätstheorie und untere Schranken

Tatsächlicher Inhalt

  • Dienstag, den 14. 04. 2015
    • Administrativa
    • Einleitung
    • Probabilistische Algorithmen:
      • Motivation
      • Randomisierte Mediansuche
        • Geschichte des deterministischen Problems: obere und untere Schranken
        • Quickselect von Hoare: benötigt h&oum:chstens 4n Vergleiche im Erwartungswert
        • Der Algorithmus von Floyd und Rivest: Einleitung
  • Freitag, den 17. 04. 2015
    • Der Algorithmus von Floyd und Rivest: Details und Analyse
    • Die Chernoff-Schranke
  • Dienstag, den 21. 04. 2015
    • Beweis der Chernoff-Schranke
    • der Algorithmus von Klein-Karger-Tarjan zur Berechnung eines minimalen aufspannenden Baumes in erwarteter linearer Zeit:
      • der Algorithmus von Borůvka
      • MST-Verifikation
  • Freitag, den 24. 04. 2015
    • KKT-Algorithmus: Analyse
  • Dienstag, den 28. 04. 2015
    • Analyse von Kuckucks-Hashing.
  • Freitag, den 01. 05. 2015
    • keine Vorlesung (erster Mai)
  • Dienstag, den 05. 05. 2015
    • Suche in Zeichenketten: Definition und naiver Algorithmus
    • Der Algorithmus von Knuth-Morris-Pratt: Einführung
  • Freitag, den 08. 05. 2015
    • Der Algorithmus von Knuth-Morris-Pratt: Vorverarbeitung und Analyse
    • Suffix-Bäume: Einführung
  • Montag, den 11. 05. 2015
    • Suffix-Bäume: Algorithmus von Ukkonen
  • Freitag, den 15. 05. 2015
    • Suffix-Bäume: Algorithmus von Ukkonen
    • LCA-Anfragen in Bäumen
  • Montag, den 18. 05. 2015
    • Approximationsalgorithmen
      • Vertex Cover
      • gewichtetes Set Cover
  • Dienstag, den 19. 05. 2015
    • Approximationsalgorithmen für das Traveling Salesperson Problem I: metrisches TSP
      • MST-Heuristik
      • Christofides Heuristik
  • Dienstag, den 26. 05. 2015
    • Approximationsalgorithmen für das Traveling Salesperson Problem II: euklidisches TSP
      • Aroras PTAS für euklidisches TSP
  • Freitag, den 29. 05. 2015
    • Aroras PTAS für euklidisches TSP
  • Dienstag, den 02. 06. 2015
    • Abschluss Aroras PTAS
    • Einführung Lineares Programmieren
  • Freitag, den 05. 06. 2015
    • Lineares Programmieren: Dualität
  • Dienstag, den 09. 06. 2015
    • Lineares Programmieren: Fourier-Motzkin Elimination und Farkas Lemma
  • Freitag, den 12. 06. 2015
    • starke Dualität
    • Anwendungen der Dualität: Spieltheorie und Minimax-Theorem
  • Montag, den 15. 06. 2015
    • Simplex-Algorithmus
  • Freitag, den 19. 06. 2015
    • keine Vorlesung
  • Dienstag, den 23. 06. 2015 (vertreten durch Helmut Alt)
    • Ellipsoid-Algorithmus
  • Freitag, den 26. 06. 2015 (vertreten durch Helmut Alt)
    • Ellipsoid-Algorithmus
  • Dienstag, den 30. 06. 2015
    • Fine-Grained Complexity: SETH und OV
  • Freitag, den 03. 07. 2015
    • Fine-Grained Complexity: diskreter Fréchet Abstand
  • Dienstag, den 07. 07. 2015 (vertreten durch Paul Seiferth)
    • diskreter Fréchet Abstand, Abschluss
    • 3-SUM
  • Freitag, den 10. 07. 2015
    • subquadratischer Entscheidungsbaum für 3-SUM
  • Dienstag, den 14. 07. 2015
    • Algorithmen für 3-SAT
  • Freitag, den 17. 07. 2015
    • keine Vorlesung
  • Dienstag, den 21. 07. 2015
    • Prüfung
  • Dienstag, den 06. 10. 2015
    • Nachprüfung

Empfohlene Vorkenntnisse

Schein/Klausur

Für den Scheinerhalt muss man

Die erfolgreiche Teilnahme am Übungsbetrieb und das Bestehen der Abschlussprüfung unabhängige Leistungen. Die Scheine sind benotet. Die Note beruht nur auf dem Ergebnis der Abschlussprüfung. Die genauen Prüfungsmodalitäten werden noch bekannt gegeben.

Termin/Tutorium

Die Vorlesung findet Dienstags von 14–16 Uhr im SR 053 und Freitags von 12–14 Uhr im SR 055 statt, die Übung Montags von 10–12 Uhr im SR 051.

Übungszettel

Es wird jede Woche ein neuer Übungszettel veröffentlicht. Die Übungszettel werden ausschließlich online erscheinen. Die normale Bearbeitungszeit ist von Freitag bis zum Dienstag 11 Tage später.

Nr.AusgabeAbgabe pdftexBemerkungen
1 01.04.2015 21.04.2015  
2 17.04.2015 28.04.2015  
3 24.04.2015 05.05.2015  
4 29.04.2015 12.05.2015  
5 08.05.2015 19.05.2015  
6 15.05.2015 26.05.2015  
7 21.05.2015 02.06.2015  
8 29.05.2015 09.06.2015  
9 05.06.2015 16.06.2015  
10 11.06.2015 23.06.2015  
11 19.06.2015 30.06.2015  
12 30.06.2015 10.07.2015  

Perspektiven

Im Anschluss an die Veranstaltung können Bachelor– und Masterarbeiten vergeben werden.

Impressum