Transcript
Pr¨ufungsstoff Randomisierte Algorithmen Vorlesung von Wolfgang Merkle im Sommersemester 2015, Im Sommersemester2015 fallen folgende Themen weg: Kap 11: Local Lemma, Kap. 12: Kargers Algorithmus mit Verzweigungsprozessen, Kap. 14: Tschebyscheffsche Ungleichung.
Kapitel 1
Introduction
Randomisierte und deterministische Variante von Quicksort, One-time-pad-Verschl¨ usselung, Eigenschaften der Parit¨atsfunktion.
Kapitel 2
Some facts from probability theory
Diskrete Wahrscheinlichkeitsverteilungen und Zufallsvariablen. Indikatorvariablen. Gemeinsame Verteilung, stochastische, paarweise und k-fache Unabh¨angigkeit, Erwartungswert und dessen Eigenschaften. Bedingte Wahrscheinlichkeitsverteilungen. Erwartete Anzahl der Fixpunkte einer zuf¨allig und gleichverteilt gew¨ahlten Permutation.
Pr¨ufungsstoff Randomisierte Algorithmen Kapitel 5
The probabilistic method
Summenfreie Teilmengen.
Kapitel 6
The Byzantine agreement problem
¨ Bedingungen, Regeln und Ziel der Byzantinischen Ubereinkunft. Protokoll Byzantine-Agreement und dessen Verifikation. Bedeutung der verschiedenen Schwellenwerte f¨ ur das Protokoll und seine Verifikation.
Kapitel 7
Stable marriages
Unzufriedene Paare und stabile Heiraten, Heiratssatz. Terminierung und Korrektheit des Algorithmus Proposal und obere Schranke O(n log n) f¨ ur die Durchschnittskomplexit¨at. Anwendung des Prinzips der verz¨ ogerten Entscheidung, ¨ ged¨achtnislose Version, Aquivalenz zum Spielerbildersammeln.
Pr¨ufungsstoff Randomisierte Algorithmen Kapitel 3
The tenure game
Determiniertheit endlicher Zweipersonenspiele mit perfekter Information. Randomisierte Strategie mit Erfolgswahrscheinlichkeit echt gr¨oßer 0 impliziert deterministische PStrategie. 1 Bedeutung der Potentialfunktion m i 2di im Tenure-Spiel.
Kapitel 4
Basic derandomization techniques
Algorithmus Cut und das erwartete Gewicht m/2 des ausgegebenen Schnitts. Derandomisierung mittels bedingter Erwartungswerte. Algorithmus Cutα und die Komplexit¨a des Vergleichs der beiden Erwartungswerte im derandomisierten Algorithmus. Derandomisierung mittels paarweiser unabh¨angiger Zufallsvariablen, Konstruktion solcher Zufallsvariablen in einem kleinen Wahrscheinlichkeitsraum.
Pr¨ufungsstoff Randomisierte Algorithmen Kapitel 8
Yao’s Minimax Principle
Erwartete Kosten von Las-Vegas-Algorithmen im schlimmsten Fall. Las-Vegas-Algorithmen mit Black-Box-Zugriff auf die Eingabe als Wahrscheinlichkeitsverteilungen. Das Minimax-Prinzip von Yao. ¨ Untere und obere Schranken f¨ ur das randomisierte Uberpr¨ ufen von Matrizen auf leere Spalten. Optimale Strategien f¨ ur Matrixspiele und zugeh¨orige Auszahlungen, Gleichgewichtspunkte. Minimax-Theorem von von Neumann, dessen Variante und der Zusammenhang mit dem Minimax-Prinzip von Yao.
Kapitel 9
The complexity of randomized sorting
Untere und obere Schranken f¨ ur randomisiertes Sortieren. Beweisskizze f¨ ur die obere Schranke.
Pr¨ufungsstoff Randomisierte Algorithmen
Pr¨ufungsstoff Randomisierte Algorithmen Kapitel 12
Kapitel 10
Checking and correctinge
Vergleich von Dateien mittels Fingerabdr¨ ucken und Absch¨atzung der Fehlerwahrscheinlichkeit. Finden von Teilw¨ ortern. Algorithmen Multiplication-Check und Multiplication-Correction und deren Analyse.
Kapitel 11
The Lovasz Local Lemma
Zufallsvariablen, die nur von einer Menge anderer Zufallsvariablen abh¨angig sind. Die Grundform des Local-Lemmas von Lovasz und deren Anwendung auf Formel in konjunktiver Normalform.
Pr¨ufungsstoff Randomisierte Algorithmen Kapitel 15
Erfolgswahrscheinlichkeit f¨ ur die Grundform des Algorithmus. Erfolgswahrscheinlichkeit der Variante mit Aufspaltung in unabh¨angige Teilprozesse und Zusammenhang mit ¨ Uberlebenswahrscheinlichkeiten in Verzweigungsprozesses.
Kapitel 13
PAC-Learning and VC-Dimension
PAC-Lernen und das Lernen von achsenparallelen Rechtecken. Definition von VC-Dimension und Beispiele. VC-Dimension und Zusammenhang mit PAC-Lernen.
Kapitel 14
Tail bounds and probability amplification
Markov- und Chebyshev-Ungleichungen. Chernov-Hoeffding-Schranke mit oberer Schranke f¨ ur die betrachtete Zufallsvariable (Teil a). Anwendung der Chernov-Hoeffding Schranke auf die Wahrscheinlichkeitsverst¨arkung.
Pr¨ufungsstoff Randomisierte Algorithmen
Satisfiability and randomized local search
Grundidee der lokalen Suche von erf¨ ullenden Belegungen. Absch¨atzung der Wahrscheinlichkeit, dass eine gleichverteilt gew¨ahlte Belegung Abstand j zu einer gegebenen Belegung hat. Irrfahrten und die Wahrscheinlichkeit f¨ ur das Erreichen des Ursprungs im unendlichen und endlichen Fall. Erfolgswahrscheinlichkeit der randomisierten lokalen Suche und Analyse der iterierten randomisierten lokalen Suchen.
Kapitel 16
Karger’s algorithm for minimum cuts
Satisfiability and exhaustive local search
Ersch¨opfende lokale Suche: Analyse und optimaler Radius. Analyse der Ersch¨ opfende lokale Suche mit zuf¨alligem Startpunkt. Beweisskizze f¨ ur die Existenz von u ¨berdeckenden Kodes. Derandomisierung des randomisierten Algorithmus mit ersch¨opfender lokaler Suche. ¨ Algorithmus f¨ ur Minimale-Mengen-Uberdeckung und dessen garantierte G¨ ute.
Kapitel 17
Cryptography
Symmetrische, ¨offentliche und private Schl¨ ussel. Zyklische Gruppen, Restklassen und diskreter Logarithmus. Informelle H¨arteannahme f¨ ur das Problem des diskreten Logarithmus. Diffie-Hellman-Verfahren f¨ ur die Vereinbarung eines Schl¨ ussels. ElGamal-Verfahren f¨ ur die Vereinbarung eines Schl¨ ussels. ElGamal-Verfahren f¨ ur die Verschl¨ usselung mit ¨offentlichem Schl¨ ussel.
Kapitel 18
Zeroknowledge-Protokolle
Zeroknowledge-Eigenschaft und Protokoll Coloring.
