- 17.02.2017:
Der Termin für die mündliche Nachprüfung ist Mittwoch, der
19. April 2017, 9–12 Uhr in Raum 112. Falls Sie teilnehmen
möchten, melden Sie sich bitte bis eine Woche vor dem Prüfungstermin im
KVV unter Sign-up an.
Unten, unter "Tatsächlicher Inhalt", habe ich Quellenangaben zu
den einzelnen Vorlesungen ergänzt.
- 27.01.2017: Das vierzehnte Aufgabenblatt ist verfügbar. Dies
ist das letzte Aufgabenblatt.
- 20.01.2017: Das dreizehnte Aufgabenblatt ist verfügbar.
- 13.01.2017: Das zwölfte Aufgabenblatt ist verfügbar.
- 06.01.2017: Frohes neues Jahr! Das elfte Aufgabenblatt ist verfügbar.
- 16.12.2016: Das zehnte Aufgabenblatt ist verfügbar.
- 09.12.2016: Das neunte Aufgabenblatt ist verfügbar.
- 02.12.2016: Das achte Aufgabenblatt ist verfügbar.
- 25.11.2016: In der nächsten Woche werden die Vorlesung
am Freitag und das Tutorium am Mittwoch getauscht. Die Vorlesung
ist also am Mittwoch, 30.11., 14–16 Uhr im SR 025/26 der Arnimallee 6,
das Tutorium am Freitag, 2.12., 10–12 Uhr im SR 053 der Takustraße
9.
- 25.11.2016: Das siebte Aufgabenblatt ist verfügbar.
- 18.11.2016: Das sechste Aufgabenblatt ist verfügbar.
- 13.11.2016: Bei der zweiten Aufgabe auf dem vierten Aufgabenblatt
hat sich ein Fehler eingeschlichen. Die Aufgabe wurde korrigiert und
die Abgabe bis Mittwoch verlängert.
- 11.11.2016: Das fünfte Aufgabenblatt ist verfügbar.
- 04.11.2016: Das vierte Aufgabenblatt ist verfügbar.
- 28.10.2016: Das dritte Aufgabenblatt ist verfügbar.
- 21.10.2016: Das zweite Aufgabenblatt ist verfügbar.
Die Abgabe ist am Mittwoch, den 2. November 2016.
- 21.10.2016: Der Abgabetermin des ersten Aufgabenblatts wurde auf
Freitag, den 28.10.2016 verschoben.
- 01.10.2016: Die Website ist online. Die erste Vorlesung findet
statt am Dienstag, den 18.10.2016 um 14 Uhr ct.
In der ersten Woche finden drei Vorlesungen statt.
In den darauffolgenden Wochen findet
die Vorlesung am Dienstag statt, und es gibt zwei Übungen, eine am Mittwoch
und eine am Freitag. Danach findet Vorlesung am Dienstag und am Freitag statt, dieÜbung am Mittwoch.
Die Übungszettel werden ausschließlich online erscheinen
und zwar hier auf dieser Seite.
- grundlegende Algorithmen:
- Lineares Programmieren,
- Optimierung,
- LP Rounding,
- Erfüllbarkeit,
- Routing,
- konstruktives Lokal Lemma,
- Suche in Zeichenketten.
- randomisierte geometrische Algorithmen:
- engstes Paar
- kleinster umschließender Kreis,
- Volumenapproximation.
- Johnson-Lindenstrauss,
- Epsilon Netze und VC Dimension.
- Reisen nach Kryptofantasia :
- differential privacy,
- homomorphic encryption,
- indistinguishability obfuscation.
- Datenstrukturen:
- Treaps,
- Hashtabellen
- universell,
- Kuckuck,
- Tabulation,
- Two-Choice,
- Robin-Hood.
- Bloom Filter und Bloomier Filter,
- Nächste Nachbarn in hohen Dimensionen,
- Bereichssuche.
- Werkzeuge:
- Konzentrationsungleichungen
- Markov,
- Tschebyscheff,
- Chernoff,
- Martingale,
- Lovasz-Lokal-Lemma.
- Markov-Ketten,
- Kuppeltechnik,
- Fingerprinting,
- Expander-Graphen,
- Entropie,
- Rückwärtsanalyse.
- Dienstag, den 18.10.2016
- Administrativa
- Einleitung (Quelle: [MU, Kapitel 1])
- Randomisierter Algorithmus: Algorithmus
mit Zufallsgenerator.
Zufallsgenerator: Funktion random(n),
die zufällig, gleichverteilt und unabhängig
von den anderen Aufrufen eine
Zahl zwischen 1 und n liefert.
- Oft einfacher und schneller als deterministische
Algorithmen.
- Aber: aufwändiger
zu analysieren; nur probabilistische Garantien;
Existenz eines echten Zufallsgenerators
kontrovers.
- Engstes Paar: Gegeben n Punkte in der Ebene, finde
Punktpaar, das euklidischen Abstand minimiert
(Quelle: [KT, Kapitel 13.7], [Originalarbeit])
- Lösung mit Datenstruktur: i-tes Standardgitter:
Unterteilung der Ebene in quadratische Zellen mit Durchmesser
2i. Zellenwörterbuch: füge Punkte
ein, finde alle Punkte in gegebener Zelle.
- Algorithmus, falls Abstand des engsten Paares bekannt:
Füge Punkte in Zellenwörterbuch
geeigneter Zellenbreite ein. Für jeden Punkt:
suche engstes Paar in benachbarten Zellen.
- O(n) Operationen auf dem Zellenwörterbuch
und O(n) zusätzliche Zeit. Problem:
Kennen Abstand des engsten Paares nicht.
- Mittwoch, den 19.10.2016
- Engstes Paar
- Inkrementeller Ansatz. Füge Punkte nacheinander
in ein Gitterwörterbuch ein, dessen Gitterbreite
dem engsten Paar der bisherigen Punkte entspricht.
Wenn sich die notwendige Gitterbreite ändert, werden alle Punkte neu
eingefügt.
- Worst-case: quadratische Laufzeit.
- Zufällige Einfügereihenfolge ergibt
erwartete Laufzeit O(n). Die Wahrscheinlichkeit eines
Gitterneubaus im k-ten Einfügeschritt ist genau 2/k:
ein Neubau geschieht genau dann, wenn ein Punkt des engsten Paares
zuletzt eingefügt wird.
- Min-Cut (Quelle: [KT, Kapitel 13.2], [MU, Kapitel 1.4],
[MR, Kapitel 1.1 und 10.2])
- Gegeben: Graph G = (V, E), einfach, zusammenhängend, ungerichtet,
ungewichtet. Min-Cut: Partition der Knotenmenge, so dass
Anzahl der geschnittenen Kanten minimal ist.
- Lässt sich deterministisch durch Netzwerkflüsse finden.
Hohe polynomielle Laufzeit.
- Freitag den 21.10.2016
- Kargers Min-Cut-Algorithmus
- Wäle eine zufällige Kante im Graphen und
kontrahiere sie. Lösche alle entstandenen Schleifen,
aber behalte die Mehrfachkanten. Wiederhole, bis zwei
Knoten übrig sind. Gib verbleibende Kanten aus.
- Eine Iteration des Algorithmus lässt sich in O(n)
Zeit implementieren.
- Sei C ein fester Min/Cut. Die Wahrscheinlichkeit, dass
der Algorithmus C ausgibt ist mindestens 2/n(n-1)n.
Entscheidendes Einsicht: Wenn |C| = k, dann hat der Graph
mindestens k|V|/2 Kanten.
- Wiederhole Algorithmus O(n2 log n) mal, gibt
besten Schnitt aus. Findet Min/Cut mit Wkeit mindestens 1-1/n.
- Laufzeit: O(n4 log n).
- Dienstag den 25.10.2016
- Verbesserung der Laufzeit in Kargers Algorithmus (Karger-Stein Algorithmus)
- Hybrider Ansatz: wechsle nach t Iterationen zu
deterministischem Algorithmus. Dadurch wird Erfolgswahrscheinlichkeit
erhöht. Bei Verwendung von Orlins Flussalgorithmus:
O(n8/3 log n) Laufzeit bei hoher Erfolgswahrscheinlichkeit.
- Rekursiver Ansatz: Wiederhole, solange wie Erfolgswahrscheinlichkeit
1/2 ist. Rekurriere. Führe in jedem rekursiven Aufruf zwei
unabhängige Zufallsdurchläufe aus.
Laufzeit O(n2 log2 n) mit hoher Erfolgswahrscheinlichkeit.
- Dienstag den 01.11.2016 (vertreten von Bahareh Banyassady)
- 2-SAT (Quelle: [MU, Kapitel 7.1.1 und 11])
- Lösbar in linearer Zeit durch graphentheoretische
Interpretation
- Einfacher randomisierter Algorithmus: beginne mit
beliebiger Belegung. Wähle beliebige nicht erfüllte
Klausel. Wähle zufälliges Literal der Klausel und
ändere Belegung. Wiederhole genügend oft.
- Satz: Falls Formel erfüllbar ist, benötigt
man O(n2) Schritte im Erwartungswert, um
eine erfüllende Belegung zu finden.
- Interpretiere den Algorithmus als Markovkette
- Freitag, den 04.11.2016 (vertreten von Bahareh Banyassady)
- Markovkette: Zufallsprozess, bei denen der die Verteilung des
nächsten Zustands
nur durch den aktuellen Zustand bestimmt wird.
- 2-SAT Algorithmus entspricht Random Walk auf Pfad. Aktueller
Zustand: Hamming-Abstand zwischen aktueller und erfüllender
Belegung. Mit Wkeit mindestens 1/2 verringert sich der Hamming-Abstand,
mit Wkheit höchstens 1/2 erhöht er sich.
- Stelle durch Coupling (Kuppeln) Zusammenhang mit der Markov-Kette auf
Pfad her, bei der die Übergangswahrscheinlichkeiten genau
1/2 sind.
- Analysiere Markov-Kette durch geeignete Rekursion.
- Dienstag, den 08.11.2016
- Freitag, den 11.11.2016
- Zählprobleme (Quelle: [MR, Kapitel 11.1, 11.2]
[MU, Kapitel 10.2]): Komplexitätsklasse #P:
Menge von Funktionen, welche die Anzahl von Zertifikaten
eines NP-Problems zählen.
- Vollständige Problem: Anzahl Hamiltonpfade in
einem Graphen, Anzahl perfekter Matchings in einem bipartiten
Graphen, Anzahl erfüllender Belegungen für eine
DNF-Formel. Beachte: Bei manchen #P-vollständigen Problemen
ist das Entscheidungsproblem in P.
- FPRAS (fully polynomial randomized approximation scheme):
bestimme eine relative eps-Approximation mit Wahrscheinlichkeit
mindestens 1-1/d in Zeit, die polynomiell ist in der
Eingabegröße, 1/eps, log(1/delta).
- Monte-Carlo-Methode. Bestimme Größe einer
Teilmenge anhand einer geeigneten Stichprobe
- Schätzungssatz gibt Auskunft über die nötige
Größe der Stichprobe
- Dienstag, den 15.11.2016
- FPRAS für DNF-Counting via Importance Sampling.
- Verringere Größe des Universums, aus dem
das Sample genommen wird. Wichtig: müssen noch
effizient Samplen können.
- Zählen von Graphenfärbungen: Von FPAUS zu FPRAS
(Quelle: [MU, Kapitel 10.3, 10.4, 11.5])
- Das Problem des Zählens von Graphenfärbungen
ist selbstreduzierbar: la¨sst sich auf
samplen einer zufälligen Färbung für einen
einfacheren Graphen reduzieren
- FPAUS (fully polynomial approximately uniform sampler):
randomisierter Algorithmus, der fast gleichverteilte
Färbungen eines Graphen erzeugt.
- Freitag, den 18.11.2016
- Zählen von Graphenfärbungen: vom FPAUS zum FPRAS
- Wir können ein FPAUS für Graphenfärbungen verwenden,
um ein FPRAS zu erhalten.
- Dienstag, den 22.11.2016
- Zählen von Graphenfärbungen: Gewinnung eines
FPAUS durch Markov-Chain-Sampling, schnelles Mischen durch die
Kuppeltechnik
- Freitag, den 25.11.2016
- Lovász-Local-Lemma: Formulierung und Beweis (Quelle: [MU, Kapitel 6.7], [MR, Kapitel 5.5])
- Dienstag, den 29.11.2016
- Konstruktives Lovász-Local-Lemma: Mosers FixIt-Algorithmus
(Quelle: [Übersichtsartikel,
Abschnitt 3.8])
- Mittwoch, den 30.11.2016
- Abschluss FixIt-Algortihmus
- Chans randomisierte Optimierungstechnik
(Quelle: [Originalarbeit,
Abschnitt 1–3])
- Dienstag, den 6.12.2016
- Chans randomisierte Optimierungstechnik
- Range Spaces und VC Dimension (Quelle: [M, Kapitel 10.2])
- Freitag, den 9.12.2016
- Sauers Lemma
- Epsilon-Netze und PAC-Learning
- Dienstag, den 13.12.2016
- Beweis des Epsilon-Netz Theorems
- Freitag, den 16.12.2016
- Epsilon-Netze und Approximationsalgorithmen für geometrische
Hitting Sets
- kleine Epsilon-Netze für Kreisscheiben
(Quelle: [Originalarbeit,
Abschnitt 3])
- Dienstag, den 03.01.2017
- kleine Epsilon-Netze für Kreisscheiben
- Freitag, den 06.01.2017
- kleine Epsilon-Netze für Kreisscheiben
- Chazelle-Fredman Schranke
- Dienstag, den 10.01.2017
- Chazelle-Fredman Schranke
- Bedingte Erwartungswerte (Quelle: [MU, Kapitel 2.3])
- Freitag, den 13.01.2017
- Martingale (Quelle: [MU, Kapitel 12.1, 12.4, 12.5]):
Definition, Beispiele, einfache
Eigenschaften
- Dienstag, den 17.01.2017
- Martingale: Azuma-Ungleichung, die Methode
der beschränkten Differenzen
- Freitag, den 20.01.2017
- Random Walks auf regulären Graphen (Quelle: [AB, Kapitel 21.1])
- Dienstag, den 24.01.2017
- Random Walks auf regulären Graphen: Eigenwertlücke und Mixing Time
- Freitag, den 27.01.2017
- Eigenwertlücke von einfachen Graphen
- st-Path in randomisiertem Logspace
- Expander-Graphen: Definition und Beispiele (Quelle: [AB, Kapitel 21.2])
- Dienstag, den 31.01.2017
- Expander-Graphen und die Verringerung der Fehlerwahrscheinlichkeit
von RP-Algorithmen mit wenigen Zufallsbits
- Freitag, den 03.02.2017
- Mehr über Expander-Graphen
- Dienstag, den 07.02.2017 (vertreten von Max Willert)
- Freitag, den 10.02.2017 (vertreten von Max Willert)
- Dienstag, den 14.02.2017
- Die Methode der multiplikativen Gewichte
(Quelle: [Übersichtsartikel, Abschnitt 1 und 2])
- Freitag, den 17.02.2017 (09–12 Uhr, Zimmer 112)
- Mittwoch, den 19.04.2017 (09–10 Uhr, Zimmer 112)
Literatur
- [CLRS] T. H. Cormen, C. Leiserson, R. Rivest, C. Stein.
Introduction to Algorithms, MIT Press 2009
Enthält wertvolle Grundlagen zur probabilistischen
Analyse von Algorithmen und viele Beispiele für einfache
randomisierte Algorithmen.
- [KT] J. Kleinberg, E. Tardos. Algorithm Design, Addison-Wesley 2005.
Gut als Alternative zur CLRS.
- [MR] R. Motwani, P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995
Der Klassiker zum Thema. Beschreibt alle wichtigen Techniken und Anwendungsgebiete.
Mittlerweile etwas angestaubt.
- [MU] M. Mitzenmacher, E. Upfal. Probability and Computing:
Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005
Modernere Variante von Motwani-Raghavan. Starker Fokus auf Markov-Ketten und
Hashing.
- [M] J. Matoušek. Lectures in Discrete Geometry.
Springer Verlag, 2002
- [AB] S. Arora, B. Barak. Computational Complexity Theory. A Modern Approach.
Cambridge University Press, 2009
Empfohlene Vorkenntnisse
- Kenntnis grundlegender diskreter Mathematik und
Wahrscheinlichkeitstheorie
- "Höhere Algorithmik", "Algorithmen, Datenstrukturen und Datenabstraktion" oder
vergleichbare Veranstaltung
- Vier erfolgreiche Semester im BSc-Studiengang.
Für den Scheinerhalt muss man
-
regelmäßig an dem Tutorium teilnehmen (bei mindestens 80% der
Termine);
-
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 sind 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 051 und
Freitags von 10–12 Uhr im SR 053 statt, die Übung
Mittwochs von 14–16 Uhr im SR 025/26 in der Arnimallee 6.
Die Tutorien werden betreut von Max Willert.
Sprechzeit des Dozenten: Dienstag 16–17 Uhr in Zimmer 114 und
nach Vereinbarung.
Die Übungszettel werden jede Woche hier verlinkt. Sie werden
ausschließlich online erscheinen.
Die normale Bearbeitungszeit ist von Freitag zum Montag
10 Tage später. Die Zettel sind vor 12 Uhr
in den Briefkasten neben Raum 111, Takustraße 9, einzuwerfen.
Die Bearbeitung erfolgt in Zweiergruppen.
Übungszettel, die nach dem angegebenen Termin
abgegeben werden, zählen als nicht bearbeitet.
| Nr. | Ausgabe | Abgabe |
pdf | tex | Bemerkungen |
| 1 |
01.10.2016 |
28.10.2016 |
|
|
Abgabedatum wurde gändert |
| 2 |
21.10.2016 |
02.11.2016 |
|
|
Beachten Sie das Abgabedatum |
| 3 |
28.10.2016 |
07.11.2016 |
|
|
|
| 4 |
04.11.2016 |
14.11.2016 |
|
|
Aufgabe 2 wurde nochmals korrigiert.
Die Abgabe wurde verlängert. |
| 5 |
11.11.2016 |
21.11.2016 |
|
|
|
| 6 |
18.11.2016 |
28.11.2016 |
|
|
Aufgabe 2 wurde aktualisiert. Statt W muss es B heißen. |
| 7 |
25.11.2016 |
05.12.2016 |
|
|
Ergänzungen in Aufgabe 1. |
| 8 |
02.12.2016 |
12.12.2016 |
|
|
|
| 9 |
09.12.2016 |
03.01.2017 |
|
|
Weihnachtszettel |
| 10 |
16.12.2016 |
09.01.2017 |
|
|
|
| 11 |
06.01.2017 |
16.01.2017 |
|
|
|
| 12 |
13.01.2017 |
23.01.2017 |
|
|
|
| 13 |
20.01.2017 |
30.01.2017 |
|
|
|
| 14 |
27.01.2017 |
06.02.2017 |
|
|
letztes Aufgabenblatt |