Theoretische Informatik (Kernfach)
(251-0402-00 Theoretische Informatik-K, 3V2U, 8 Kreditpunkte, Sommer 2005)
Dozenten: |
Jiří Matoušek,
Emo Welzl (CAB G15.2)
|
Chefassistenten: |
Robert Berke (CAB G37.2),
Leo Rüst (CAB G33.3) |
Termine: |
Montag 9:15-10:00, Donnerstag 14:15-16:00, IFW A36 |
Sprache: |
Deutsch und Englisch |
Inhalte: |
Fortgeschrittene Entwurfs- und Analysemethoden für Algorithmen und Datenstrukturen: Random(ized) Search Trees, Point Location, Network Flows, Minimum Cut, Randomized Algebraic Algorithms. Zudem eine Einführung in das PCP Theorem. |
Literatur: |
Zu einzelnen Themen werden Unterlagen in der Vorlesung ausgegeben. Die folgenden Standardwerke decken weder alle Themen der Vorlesung ab noch deckt die Vorlesung alle Themen dieser Bücher ab.
-
Introduction to Algorithms von T. H. Cormen, C. E. Leiserson, R. L. Rivest
-
Randomized Algorithms von R. Motwani und P. Raghavan
-
Computational Geometry -- Algorithms and Applications von M. de Berg, M. van Kreveld, M. Overmars und O. Schwarzkopf
|
Prüfungen
- Semesterzwischenprüfung:
Freitag, 13. Mai 2005. Schriftliche Prüfung, keine Hilfsmittel (weder schriftlicher noch elektronischer Art) erlaubt.
Übungsgruppen 1-4 von 9:00-10:00 Uhr, Übungsgruppen 5-6 von 10:00-11:00 Uhr. Bitte schreiben Sie sich unbedingt in eine Übungsgruppe ein damit Sie wissen wo und wann Sie die Prüfung schreiben werden.
Die Semesterzwischenprüfung der letztjährigen Vorlesung finden Sie hier, diejenige der diesjährigen Vorlesung hier. Beachten Sie, dass die Prüfung in der Prüfungssession keineswegs ähnlich (in Bezug auf Inhalt und Schwierigkeit) zur Zwischenprüfung sein muss.
- Endprüfung:
Mittwoch,
21. September 2005, 14:00-17:00 Uhr, ETF C1/E1. Schriftliche Prüfung, keine Hilfsmittel (weder schriftlicher noch elektronischer Art) erlaubt. Prüfungsstoff ist alles, das in der Vorlesung besprochen wurde. D.h. alles im Skript ausser Range Trees und die Beweise von Lemmas 6.4.2 und 6.5.2. Die Prüfung vom letzten Jahr finden Sie hier. Beachten Sie, dass die diesjährige Prüfung keineswegs ähnlich zur letzten sein muss.
Die Endnote setzt sich zu 25% aus der Note der Semesterzwischenprüfung und zu 75% aus der Note der Endprüfung zusammen.
-
Für Mathematiker gilt die Teilnahme an der Semesterzwischenprüfung als Testatsbedingung (die Prüfung zählt nicht zur Note).
Alternativ besteht die Möglichkeit, die Endprüfung nach Absprache mit dem Studiensekretariat des Mathematikdepartements im Herbst 2005 zu schreiben. In diesem Fall zählt die Zwischenprüfung für die Endnote.
-
Für Studenten die an der Semesterprüfung aus wichtigem Grund verhindert sind (Militädienst, etc.), folgt 2 Wochen später die Gelegenheit diese nachzuholen (gemischt schrifltich / mündlich).
-
Auswärtige Studenten: Nehmen an der Semesterprüfung teil. Wenn Sie die Endprüfung in der Prüfungssession nicht wahrnehmen können, wird in der letzten oder vorletzten Semesterwoche eine Prüfung angeboten (gemischt schriftlich/mündlich).
-
ETH Studenten die im Herbst wegen Studium an Universitäten im (fernen) Ausland verhindert sind: Gemäss Reglement müssen Sie eine schriftliche Prüfung ablegen. Sie legen die Prüfung an ihrer Universität unter Aufsicht vor Ort zeitgleich mit der Prüfung an der ETH ab.
In allen Fällen müssen Sie am Anfang des Semesters einen Chefassistenten entsprechend informieren.
Übungen
Die wöchentlichen Übungsserien sind in der Regel Donnerstags online verfügbar.
Lösungsvorschläge sind in der darauffolgenden Woche in der Vorlesung am
Donnerstag abzugeben. Eine rege und regelmässige Teilnahme in den Übungsgruppen
sowie eigenständige Bearbeitung der Übungen wird empfohlen!
Erste Übung ist am Freitag, 1. April 2005.
Auf diesen Termin müssen noch keine Übungsaufgaben gelöst werden.
Nr |
Gestellt am |
Abgabe am |
Aufgabenstellung |
Musterlösung 4 Seiten pro Blatt |
Musterlösung 2 Seiten pro Blatt |
1 |
31. März |
7. April |
Übung1 |
Musterlösung1 |
Musterlösung1 |
2 |
7. April |
14. April |
In den Unterlagen zu Random(ized) Search Trees Aufgaben 1.15, 1.17, 1.19 und 1.29 |
Musterlösung2 |
Musterlösung2 |
3 |
14. April |
21. April |
In den Unterlagen zu Random(ized) Search Trees Aufgaben 1.26, 1.36, 1.37, 1.38 und 1.41 |
Musterlösung3 |
Musterlösung3 |
4 |
21. April |
28. April |
In den Unterlagen zu Point Location Aufgaben 2.1, 2.3, 2.4 und 2.5 |
Musterlösung4 |
Musterlösung4 |
5 |
28. April |
12. Mai |
In den Unterlagen zu Point Location Aufgaben 2.9, 2.11, 2.12, 2.15, 2.16 und 2.17 |
Musterlösung5 |
Musterlösung5 |
6 |
19. Mai |
26. Mai |
Übung6 |
Musterlösung6 |
Musterlösung6 |
7 |
26. Mai |
2. Juni |
Übung7 |
Musterlösung7 |
Musterlösung7 |
8 |
2. Juni |
9. Juni |
Übung8 |
Musterlösung8 |
Musterlösung8 |
9 |
9. Juni |
16. Juni |
Übung9 |
Musterlösung9 |
Musterlösung9 |
10 |
16. Juni |
23. Juni |
Übung10 |
Musterlösung10 |
Musterlösung10 |
11 |
23. Juni |
30. Juni |
Übung11 |
Musterlösung11 |
Musterlösung11 |
Übungsgruppen
Hier können Sie sich in eine der folgenden
Übungsgruppen eintragen. Achtung: Der Zugriff auf den Link funktioniert aus
Sicherheitsgründen nur innerhalb des ETH-Netzwerks (oder wenn eine VPN Verbindung
mit dem ETH-Netzwerk besteht). Bei Problemen wenden Sie sich an
Leo Rüst.
Übungsgruppe 5 wird abwechselnd von Birgitta Weber bzw. Marc Nunkesser betreut.
Inhalt
Die Inhalte im Einzelnen:
- Random(ized) Search Trees (Emo Welzl)
- DO, 31. März
Definitions. Depth of the smallest key. Overall depth.
- MO, 4. April (Bernd Gärtner)
Overall depth (continued). Height.
- DO, 7. April
Height (continued). Depth of individual keys. Quicksort.
- MO, 11. April
Treaps.
- DO, 14. April
Treaps (continued). Random real numbers. Range trees.
- Point Location (Emo Welzl)
- MO, 18. April
Introduction. Point/Line relative to a convex polygon.
- DO, 21. April
Line relative to point set (reporting, duality).
- MO, 25. April (Bernd Gärtner)
Line relative to point set (continued). Planar point location - more examples.
- DO, 28. April
Point location - Examples (continued). Trapezoidal decomposition.
- MO, 2. Mai
Trapezoidal decomposition (continued).
- Maximum Flow (Jiří Matoušek)
- MO, 2. Mai (Emo Welzl)
Introduction.
- MO, 9. Mai (Emo Welzl)
Introduction (continued) and definitions.
- DO, 12. Mai
Proof of the main Theorem. The Ford-Fulkerson algorithm.
- DO, 19. Mai
Capacity scaling. Shortest augmenting paths. Dinits algorithm.
- MO, 23. Mai
Dinits algorithm (summary). A glance of other maxflow algorithms. Bipartite matchings (definition).
- DO, 26. Mai
Hall's theorem and consequences.
- Minimum Cut (Jiří Matoušek)
- DO, 26. Mai
Definitions. Preliminaries. BasicMinCut.
- MO, 30. Mai
Random contractions. KargerMinCut.
- DO, 2. Juni
Bootstrapping.
- Randomized Algebraic Algorithms (Jiří Matoušek)
- DO, 2. Juni
Introduction. Checking matrix multiplication.
- MO, 6. Juni
Checking matrix multiplication (continued). Is a polynomial identically zero?
- DO, 9. Juni
Is a polynomial identically zero (Schwartz-Zippel Theorem). Testing perfect matchings in bipartite/general Graphs.
- MO, 13. Juni
Testing perfect matchings in bipartite/general Graphs (continued).
- Introduction to PCP (Jiří Matoušek)
- MO, 13. Juni
Introduction to complexity theory (preparation for PCP).
- DO, 16. Juni
Hardness of approximation. PCP theorem (approximation version).
- MO, 20. Juni
Probabilistically checkable proofs. PCP theorem (proof-checking version).
- DO, 23. Juni
Equivalence of inapproximability and PCP. Preparation for baby PCP: Linearity test.
- MO, 27. Juni
Linearity test (continued). Safe evaluation.
- DO, 30. Juni
Proof of the baby PCP theorem.