Theoretische Informatik (Kernfach)
(37-402 Theoretische Informatik-K, 3V2U, 8 Kreditpunkte)
Sommer 2004
Dozenten:
Jiří Matoušek (IFW B 48.1),
Emo Welzl (IFW B 49.2)
Chefassistent: Ingo Schurr / Robert Berke (IFW B 43)
Termine: Montag 9:00-10:00, Donnerstag 14:00-16:00, IFW A 36
Inhalte: Fortgeschrittene Entwurfs- und Analysemethoden für Algorithmen und Datenstrukturen;
Komplexitätstheorie.
(Die Vorlesung wird im Vergleich zu den Vorjahren inhaltlich neu konzipiert.)
Sprache: Deutsch und englisch.
News: Unterlagen zur Vorlesung Komplexitätstheorie online erhätlich (kein Prüfungsstoff)
Inhalt
Die Inhalte im Einzelnen:
- Random(ized) Search Trees (Emo Welzl)
- Mo., 29. März:
Definitions. Depth of the smallest key.
- Do., 1. April
Depth of smallest key (cont'd). Overall depth. Height.
- Mo., 5. April
Depth of individual keys. Quicksort.
- Mo, 26. April
Treaps.
- Do., 29. April
Choosing the priorities in a treap. Range Search Trees.
- Network Flows (Jiří Matoušek)
- Do., 8. April
Definitions (network, flow, cut), max-flow-min-cut theorem
- Do., 15. April
Ford-Fulkerson algorithm, capacity scaling, residual network, Dinitz algorithm
- Mo., 19. April
Dinitz alg. (cont'd). Historical remarks. LP-formulation.
- Do., 22. April
Bipartite matchings. Hall's Marriage Theorem.
- Minimum Cut (Jiří Matoušek)
- Do., 22. April
Introduction.
- Do., 29. April
Karger's min-cut-algorithm.
- Mo., 3. Mai
Algorithm by Karger and Stein.
- Do., 6. Mai
Algorithm by Karger and Stein (cont'd).
- Randomized Algebraic Algorithms (Jiří Matoušek)
- Do., 6. Mai
Checking matrix multiplication. Checking if polynomial is identically zero.
- Mo., 10. Mai
Perfect bipartite matching. The permanent.
- Do., 13. Mai
Perfect bipartite matching (cont'd). Tutte matrix.
- Randomized Rounding (Jiří Matoušek)
- Mo., 17. Mai
Linear and Integer Linear Programming. Maximum Matching.
- Mo., 24. Mai
Maximum independent set. Linear relaxation. Concentration for sums of ind. variables.
- Do., 27. Mai
Concentration for sums of ind. variables (cont'd). Central Limit Theorem. Approximate Packing.
- Do., 3. Juni
Approximate Packing (cont'd).
- Point Location (Emo Welzl)
- Do., 3. Juni
Point/Line Relative to a Convex Polygon. Line Relative to Point Set
- Mo., 7. Juni
Line Relative to Point Set (Reporting).
- Do., 10. Juni
Line Relative to Point Set (Counting). Planar Point Location (Point in Polytope).
- Mo., 14. Juni
Planar Point Location (Counting Points Below Plane, Post Office Problem). Randomized Incremental Constructions, History Graph.
- Do., 17. Juni
Trapezoidal Decomposition.
- Visual Cryptography (Jiří Matoušek)
- Do., 17. Juni
Introduction. 2 out of 2 schemes
- Mo., 21. Juni
n out of n schemes. 2 out of n schemes.
- Mo., 28. Juni
2 out of n schemes (cont'd). Hadamard matrices.
- Complexity Theory (Markus Bläser)
Zu einzelnen Themen werden Unterlagen in der Vorlesung ausgegeben.
Kopien der Unterlagen sind erhältlich in der Vorlesung oder bei Ingo Schurr / Robert Berke, IFW B43.
Bisher ausgegebene Unterlagen:
- Random(ized) Search Trees (Seiten 1-19 am 29.03., Seiten 19-23 am 05.04., Seiten 23-30 am 26.04.)
- Network Flows (Seiten 1-8 am 08.04., Seiten 8-17 am 15.04.)
- Minimum Cut (Seiten 17-24 am 29.04.)
- Randomized Algebraic Algorithms (Seiten 25-32 am 06.05.)
- Randomized Rounding (Seiten 33-36 am 13.05.)
- Point Location (Seiten 1-8 am 03.06., Seiten 9-12 am 07.06 und Seiten 13-16 am 10.06, Seiten, 16-25 am 01.07.)
- Visual Cryptography (Seiten 42-51 am 24.06.)
- Musterlösungen zu Aufgaben 1.4 - 1.7, 1.12, 1.14 (05.04.) 1.15-1.19, 1.23, 1.26, 1.27, 1.29 (19.04.); 3 - 5,
Set 3 und zu Set 4 (29.04.); Set 5 (06.05.); Set 6 und Set 7 (03.06.); Set 8 (10.06.); Set 9 und Set 10 (17.06.); Set 11, Set 12 und Set 13 (01.07.);
Literatur: Die Vorlesung folgt keinem Lehrbuch. Das im Vorlesungsverzeichnis genannte Buch
Introduction to Algorithms von T. H. Cormen, C. E. Leiserson, R. L. Rivest deckt weder alle Themen der
Vorlesung ab noch deckt die Vorlesung alle Themen des Buches ab.
Das Buch Randomized Algorithms von R. Motwani und P. Raghavan
liefert eine gute Übersicht ueber randomisierte Verfahren.
Computational Geometry -- Algorithms and Applications
von M. de Berg, M. van Kreveld, M. Overmars und O. Schwarzkopf
behandelt Themen aus der algorithmischen Geometrie, wie sie
im Kapitel über Point Location vorgestellt wurden.
Errata:
-
Random(ized) Search Trees, Seite 16, Fussnote 8:
E[X+Y] = E[X] + E[Y] (statt E[X+Y]=E[X+Y])
-
Random(ized) Search Trees, Seite 18, Aufgabe 1.26 (1):
D(i)n (statt Di)
-
Random(ized) Search Trees, Seite 25, zweite Zeile:
if Q = ∅ (statt S = ∅)
-
Random(ized) Search Trees, Seite 27, letzte Zeile:
1/(j-k+1))=1 - 1/j (statt "1/(j-k+1))1 - 1/j" )
-
Network Flows, Seite 4,viertletzte Zeile:
val(f) (statt val(S))
-
Network Flows, Seite 5, letzte Zeile:
f'(e) (statt f')
-
Network Flows, Seite 6, 3. Zeile:
∑f'(s,x)-∑f'(x,s) (statt ∑f'(z,x)-∑f'(x,z))
-
Network Flows, Seite 6, Beweis der Proposition 1.9, Linie 5 vor Ende des Beweises:
be reached by a non-saturated path (statt: be reached by a saturated path)
-
Network Flows, Seite 7, 1. Zeile unter Bild:
algorithm needs 2000 steps! (statt: 1000 steps)
-
Network Flows, Seite 16, Bild:
I statt A, X statt B.
-
Network Flows, Seite 17, Bild:
I statt A, X statt B.
-
Network Flows, Seite 17, vorletzte Zeile des Beweises:
|I|-|J|+|NJ|≥|I| (statt |I|-|J|-|NJ|≥|I|)
-
Minimum Cut, Seite 20, Alg. GuessMinCut:
downto 3 (statt downto 2).
-
Minimum Cut, Seite 22, Alg. Cotract:
downto t+1 (statt downto t).
-
Minimum Cut, Seite 23
Ersetze 9 durch 16.
-
Point Location, Seite 2, Zeile 5:
that this a is not unique (statt that this x is not unique).
-
Point Location, Seite 8, Zeile 13:
ni := |Si| (statt ni := |Si+1|).
-
Point Location, Seite 4, Fussnote
See exercise 2.4 (statt See exercise 2.3).
-
Point Location, Seite 10, Zeile unter Bild
Figure 2.3: Three points and two lines (statt Figure 2.3: Two points and three lines).
-
Visual Cryptography:
Chapter 5 (statt Chapter 4).
Übungen
Die Übungsaufgaben werden in der Regel Donnerstags in der Vorlesung bekanntgegeben.
Lösungsvorschläge sind in der darauffolgenden Woche in der Vorlesung am Donnerstag abzugeben.
- Gestellt am 29.03., Abgabe: 01.04. (!)
In den Unterlagen zu Random(ized) Search Trees Aufgaben 1.4, 1.5, 1.7 und 1.14
- Gestellt am 01.04., Abgabe: 08.04.
In den Unterlagen zu Random(ized) Search Trees Aufgaben 1.15, 1.17, 1.19 und 1.29
- Gestellt am 08.04., Abgabe: 15.04.: Aufgaben-Blatt (PDF)
- Gestellt am 15.04., Abgabe: 22.04.: Aufgaben-Blatt (PDF)
- Gestellt am 22.04., Abgabe: 29.04.: Aufgaben-Blatt (PDF)
- Gestellt am 29.04., Abgabe: 06.05.: Aufgaben-Blatt (PDF)
- Gestellt am 06.05., Abgabe: 13.05.: Aufgaben-Blatt (PDF)
- Gestellt am 13.05., Abgabe: 27.05.: Aufgaben-Blatt (PDF)
- Gestellt am 27.05., Abgabe: 03.06.: Aufgaben-Blatt (PDF)
- Gestellt am 03.06., Abgabe: 10.06.: Aufgaben-Blatt (PDF)
- Gestellt am 10.06., Abgabe: 17.06.:
In den Unterlagen zu Point Location Aufgaben 2.5, 2.11, 2.12 und 2.9
- Gestellt am 17.06., Abgabe: 24.06.: Aufgaben-Blatt (PDF)
- Gestellt am 24.06., Abgabe: 01.07.: Aufgaben-Blatt (PDF)
Organisatorisches
Prüfungen
- Semesterzwischenprüfung:
Freitag, 30. April in den Übungen. Schriftliche Prüfung, 1 Stunde.
- Endprüfung:
Herbst, in der Prüfungssession. Schriftliche Prüfung, 3 Stunden.
-
In beiden Prüfungen sind keine Hilfsmittel (weder schriftlicher noch elektronischer Art) erlaubt!
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 Semesterzwischenprüfung als Testatsbedingung.
Übungsgruppen
Eine rege und regelmässige Teilnahme an den Übungsgruppen
sowie eigenständige Bearbeitung der Übungen wird empfohlen!
Folgende Übungsgruppen werden angeboten:
Die Übungen von Robert Berke und Ingo Schurr werden in der ersten Hälfte des Semesters
von Ingo Schurr und in der zweiten Hälfte von Robert Berke betreut.
Die Übung von Yoshio Okamoto wird auf englisch abgehalten.