Theoretische Informatik (Kernfach)
(251-0402-00 Theoretische Informatik-K, 3V2U, 8 Kreditpunkte, Sommer 2006)
| Dozenten: |
Jiří Matoušek (CAB G32.1),
Emo Welzl (CAB G15.2)
|
| Chefassistenten: |
Leo Rüst (CAB G33.3), Philipp Zumstein (CAB G17) |
| Termine: |
Montag 9:15-10:00, Donnerstag 14:15-16:00, IFW A36, Vorlesungsbeginn: Montag, 3. April 2006 |
| 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 Reading Assignments Basics of Probabilistic Analysis for the TI-Lecture sind elektronisch verfügbar. 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
Die Zusammenfassungs-Folie für den Beweis des Baby-PCP Theorems findet man hier.
|
Prüfungen
- Semesterzwischenprüfung:
Freitag, 12. Mai 2006. Schriftliche Prüfung, keine Hilfsmittel (weder schriftlicher noch elektronischer Art) erlaubt.
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, 20. September 2006, 14:00-17:00 im ML D 28. 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 (Kapitel 1.7), Testing Perfect Matchings in General Graphs (Kapitel 5.4) und dem Beweis von Lemma 6.4.2. Die Prüfung vom letzten Jahr finden Sie hier. Beachten Sie, dass die diesjährige Prüfung keineswegs ähnlich zur letzten sein muss.
- Prüfungseinsicht:
Die Prüfung kann eingesehen werden im Zeitraum vom 26. Oktober bis 3. November auf dem Sekretariat CAB G 19.1.
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 gelten neu, in Absprache mit dem Studiensekretariat,
die selben Regelungen wie für die Studenten aus D-INFK. Insbesondere
sind die Prüfungen schriftlich zu den angekündigten Terminen abzulegen, eine
Möglichkeit zur mündlichen Prüfung besteht nicht mehr. Für die Endprüfung
müssen Sie sich wie gewohnt (d.h. zusammen mit Ihrer Prüfungsanmeldung für die
Schlussdiplomprüfung Teil B) beim Mathematik Studiensekretariat anmelden.
-
Für Studenten die an der Semesterzwischenprüfung aus wichtigem Grund verhindert sind (Militärdienst, etc.), folgt 2 Wochen später die Gelegenheit diese nachzuholen (gemischt schrifltich / mündlich).
-
Auswärtige Studenten: Nehmen an der Semesterzwischenprü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, 7. April 2006.
| Nr |
Gestellt am |
Abgabe am |
Aufgabenstellung |
Musterlösung
4 Seiten pro Blatt |
Musterlösung
2 Seiten pro Blatt |
| 0 |
06. April |
- |
Präsenzaufgaben für die erste Übungsstunde |
Musterlösung0 |
Musterlösung0 |
| 1 |
03. April |
13. April |
Übung1 |
Musterlösung1 |
Musterlösung1 |
| 2 |
13. April |
20. April |
In den Unterlagen zu Random(ized) Search Trees Aufgaben 1.15, 1.17, 1.19, 1.26 und 1.30 |
Musterlösung2 |
Musterlösung2 |
| 3 |
20. April |
27. April |
In den Unterlagen zu Random(ized) Search Trees Aufgaben 1.29, 1.36, 1.37, 1.38 und 1.41 |
Musterlösung3 |
Musterlösung3 |
| 4 |
27. April |
04. Mai |
In den Unterlagen zu Point Location Aufgaben 2.1, 2.2, 2.3, 2.4 und 2.5 |
Musterlösung4 |
Musterlösung4 |
| 5 |
04. Mai |
11. Mai |
In den Unterlagen zu Point Location Aufgaben 2.9, 2.11, 2.12, 2.15, und 2.16 |
Musterlösung5 |
Musterlösung5 |
| 6 |
11. Mai |
18. Mai |
Übung6 |
Musterlösung6 |
Musterlösung6 |
| 7 |
18. Mai |
01. Juni |
Übung7 |
Musterlösung7 |
Musterlösung7 |
| 8 |
01. Juni |
08. Juni |
Übung8 |
Musterlösung8 |
Musterlösung8 |
| 9 |
08. Juni |
15. Juni |
Übung9 |
Musterlösung9 |
Musterlösung9 |
| 10 |
15. Juni |
22. Juni |
Übung10 |
Musterlösung10 |
Musterlösung10 |
| 11 |
22. Juni |
29. Juni |
Übung11 |
Musterlösung11 |
Musterlösung11 |
| 12 |
29. Juni |
06. Juli |
Übung12 |
Musterlösung12 |
Musterlösung12 |
Übungsgruppen
Hinweis
Der Traffic dieser Site wird durch die Dozenten und Assistenten der Vorlesung statistisch ausgewertet. Es erfolgt keine Weitergabe der Daten an Drittpersonen.
Inhalt
Die Inhalte im Einzelnen:
- Random(ized) Search Trees (Emo Welzl)
- MO, 3. April
Introduction and definitions.
- DO, 6. April
Depth of the smallest key. Overall depth. Expected height.
- MO, 10. April
Expected height (continued).
- DO, 13. April
Depth of individual keys. Quicksort. Treaps.
- MO, 17. April
Ostermontag, Vorlesung fällt aus.
- DO, 20. April
Treaps (continued). Random real numbers. Range trees.
- Point Location (Emo Welzl)
- MO, 24. April
Introduction. Point/Line relative to a convex polygon.
- DO, 27. April
Line relative to point set (reporting, duality).
- MO, 1. Mai
Tag der Arbeit, Vorlesung fällt aus.
- DO, 4. Mai
Planar point location - more examples. Trapezoidal decomposition.
- Maximum Flow (Jiří Matoušek)
- MO, 8. Mai
Introduction and definitions.
- DO, 11. Mai (Emo Welzl)
Proof of the main theorem.
- MO, 15. Mai (Emo Welzl)
The Ford-Fulkerson algorithm. Capacity scaling.
- DO, 18. Mai (Emo Welzl)
Shortest augmenting paths. Dinits algorithm.
- MO, 22. Mai
A glance of other maxflow algorithms. Bipartite matchings (definition).
- DO, 25. Mai
Auffahrt, Vorlesung fällt aus.
- MO, 29. Mai
Hall's theorem and consequences.
- Minimum Cut (Jiří Matoušek)
- DO, 1. Juni (Emo Welzl)
Definitions and preliminaries. Random contractions (BasicMinCut).
- MO, 5. Juni
Pfingstmontag, Vorlesung fällt aus.
- DO, 8. Juni
Bootstrapping.
- Randomized Algebraic Algorithms (Jiří Matoušek)
- DO, 8. Juni
Introduction. Checking matrix multiplication.
- MO, 12. Juni
Is a polynomial identically zero? Schwartz-Zippel theorem.
- DO, 15. Juni
Testing perfect matchings in bipartite and general graphs (sketch).
- Introduction to PCP (Jiří Matoušek)
- DO, 15. Juni
Introduction to complexity theory (preparation for PCP).
- MO, 19. Juni
Approximation algorithms.
- DO, 22. Juni
Inapproximability (approximation version of PCP theorem). Probabilistically checkable proofs (proof-checking version of PCP theorem).
- MO, 26. Juni
Equivalence of the two versions of the PCP theorem.
- DO, 29. Juni
Preparation for baby PCP (linearity test, safe evaluation).
- MO, 3. Juli
Proof of the baby PCP theorem.
- DO, 6. Juli
Proof of the baby PCP theorem (continued). Visual cryptography (appetizer).
Mistake in the notes: In the consistency test we have also to test for "l(a_0 = 1, a_ij = 0) = 1?" and take care of this test in the point (R2).
