- 23.07.2015: Die Nachprüfung findet statt am Dienstag, den 06.10.2015,
ab 15 Uhr. Die
Anmeldung ist ab sofort im KVV möglich.
Die Anmeldung endet eine Woche vor dem Prüfungstermin.
- 03.07.2015: Die Anmeldung für die mündliche
Prüfung ist ab sofort im KVV möglich.
- 30.06.2015: Das zwölfte Aufgabenblatt ist verfügbar.
- 08.06.2015: Das Tutorium von Montag, den 6.7., wird auf Freitag, den 3.7., von 8–10 Uhr
in SR 055 verlegt (Beginn ist 8:45 Uhr).
- 26.06.2015: Das zwölfte und letzte Aufgabenblatt wird am Dienstag
veröffentlicht.
- 19.06.2015: Das elfte Aufgabenblatt ist verfügbar.
- 17.06.2015: Die Vorlesung am Freitag, den 19.06., fällt
aus. Die Vorlesung wird nachgeholt, ein Ersatztermin wird noch vereinbart.
- 12.06.2015: Das zehnte Aufgabenblatt ist verfügbar.
- 08.06.2015: Das Tutorium am Montag, den 22.06., fällt
aus.
- 08.06.2015: Die Vorlesung von Dienstag, den 16.6., wird auf Montag, den 15.6., von 8–10 Uhr
in SR 055 verlegt.
- 05.06.2015: Das neunte Aufgabenblatt ist verfügbar.
- 29.05.2015: Das achte Aufgabenblatt ist verfügbar.
- 21.05.2015: Das siebte Aufgabenblatt ist verfügbar.
- 21.05.2015: Das Tutorium am Freitag, den 22.05., fällt
aus.
- 15.05.2015: Das sechste Aufgabenblatt ist verfügbar.
- 08.05.2015: Am Donnerstag, den 28.5., von 10–12 Uhr
findet ein Ersatztutorium im SR 055 statt.
- 08.05.2015: Das fünfte Aufgabenblatt ist verfügbar.
- 29.04.2015: Das vierte Aufgabenblatt ist verfügbar.
- 24.04.2015: Das dritte Aufgabenblatt ist verfügbar.
- 17.04.2015: Das zweite Aufgabenblatt ist verfügbar.
- 02.04.2015: Das erste Aufgabenblatt ist verfügbar.
- 02.04.2015: Die Website ist online. Die erste Vorlesung
findet statt am 14.04.2015. Das erste Tutorium ist am 20.04.2015.
Die Übungszettel werden ausschließlich online erscheinen
und zwar hier auf dieser Seite.
- Probabilistische Algorithmen
- String Algorithmen
- Arithmetische Algorithmen
- Approximationsalgorithmen
- Lineares Programmieren
- Parametrische Suche
- Hashing
- Fortgeschrittene Komplexitätstheorie und untere Schranken
- 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
- 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
- Freitag, den 19. 06. 2015
- Dienstag, den 23. 06. 2015 (vertreten durch Helmut Alt)
- Freitag, den 26. 06. 2015 (vertreten durch Helmut Alt)
- 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
- Freitag, den 17. 07. 2015
- Dienstag, den 21. 07. 2015
- Dienstag, den 06. 10. 2015
Empfohlene Vorkenntnisse
- Kenntnis grundlegender diskreter Mathematik und
Wahrscheinlichkeitstheorie
- "Höhere Algorithmik", "ALP 3" oder
vergleichbare Veranstaltung
- Vier erfolgreiche Semester im BSc-Studiengang.
Für den Scheinerhalt muss man
- regelmäßig an dem Tutorium teilnehmen
- mindestens 60% der Punkte auf den Übungszetteln erreichen und
mindestens zweimal im Tutorium vorrechnen; und
- die Abschlussprüfung bestehen.
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.
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.
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. | Ausgabe | Abgabe |
pdf | tex | Bemerkungen |
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 |
|
|
|
Im Anschluss an die Veranstaltung können
Bachelor– und Masterarbeiten vergeben werden.