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)
    • Ein schneller Algorithmus für Subset Sum (Quelle: [Originalarbeit])
  • Freitag, den 10.02.2017 (vertreten von Max Willert)
    • Subset Sum
  • 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)
    • Mündliche Prüfung
  • Mittwoch, den 19.04.2017 (09–10 Uhr, Zimmer 112)
    • Mündliche Nachprüfung

Literatur

Empfohlene Vorkenntnisse

Für den Scheinerhalt muss man

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.AusgabeAbgabe pdftexBemerkungen
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
Impressum