Stand: 29 von 29 Vorlesungen sind vorüber
| Nr. | Datum | Stoff |
| 1 | 12.10.04 | Einleitende Worte zur Vorlesung, Prinzipien randomisierter Algorithmen, grundlegende Begriffe definiert: Zufallsvariable (ZV), Erwartungswert, Linearität des Erwartungswerts, Beispiele, wo diese die Analyse erleichtert: 40 Matrosen und 40 Kajüten. Wie groß ist die Wahrscheinlichkeit, dass ein Ereignis ungerade oft eintritt? Ein einfacher randomisierter Algorithmus für Independent Set, Analyse davon. In der "aktuellen" Skriptversion sind das die Seiten bis Seite 5 Mitte. |
| 2 | 13.10.04 | Randomisiertes Quicksort mit Hilfe der Linearität des Erwartungswerts analysiert. Markovsche Ungleichung. Ungleichung von Tschebyscheff, Jensensche Ungleichung. Las-Vegas-Algorithmen und Monte-Carlo-Algorithmen definiert. Definition der erwarteten Laufzeit präzisiert. Beispiele für das Berechnen dieser bei einem Münzwurf"algorithmus". Algorithmus für das Auswürfeln von Lottozahlen hingeschrieben, Analyse in der nächsten Vorlesung. In der "aktuellen" Skriptversion sind das die Seiten 5 Mitte bis 10 unten. |
| 3 | 19.10.04 | Die Analyse des einfachen Lottoalgorithmus beendet. Komplexitätsklassen P, ZPP, RP, BPP und PP definiert. Amplifikation bei RP-Algorithmen und PP-Algorithmen (majority vote) analysiert. Begonnen mit einer "Warnung", dass man bei der Klassifikation von Optimierungsproblemen ein wenig vorsichtig sein muss. In der "aktuellen" Skriptversion sind das die Seiten 10 unten bis 14 oben. |
| 4 | 20.10.04 | Die Warnung beendet, dass man bei der Klassifikation von Optimierungsproblemen in die probabilistischen Klassen aufpassen muss. Randomisierte Schaltkreise vorgestellt. "Satz von Adleman:" Man kann probabilistische Schaltkreise (mit einseitigem Fehler) durch deterministische Schaltkreise simulieren. Hidden-Line-Elimination: Binäre planare (Auto)partitionen definiert. Algorithmus PAINTERS vorgestellt. Algorithmus RAND-binary-planar-Partition vorgestellt und mit der Analyse begonnen. In der "aktuellen" Skriptversion sind das die Seiten 14 bis 21 oben. |
| 5 | 26.10.04 | Den Beweis beendet, dass bei RAND-binary-planar-Partition im Erwartungswert O(n log n) Blätter entstehen. Spielbaumauswertung: Was ist ein Spielbaum, wie wird er ausgewertet, vorgeführt, wie man beim Auswerten Laufzeit sparen kann. Randomisierten Spielbaumauswerter vorgestellt, nachgewiesen, dass dieser im Erwartungswert O(n^0.79...) Blätter liest. Begonnen mit der unteren Schranke für randomisierte Spielbaumauswerter, also: Zwei-Personen-Nullsummenspiele mit Darstellung durch Auszahlungsmatrix. Beispiel Papier-Stein-Schere. Im aktuellen Skript: Seite 21 oben bis Seite 25 Mitte. |
| 6 | 27.10.04 | "Reine" Strategien: V_R und V_C definiert, die beiden Zahlen, die angeben, was die beiden Spieler sich jeweils sichern können. Gezeigt, dass V_R <= V_C. Übergang zu gemischten Strategien: Erklärt, was man nun unter der erwarteten Auszahlung versteht. Wie errechnen sich V_R und V_C *nun*? Theorem von von Neumann und von Loomis erläutert. Uminterpretation von randomisierten Algorithmen als Wahrscheinlichkeitsverteilung über deterministische Algorithmen. Yaos Minimaxprinzip erklärt. Begonnen mit der Anwendung von Yaos Minimaxprinzip auf Spielbaumauswerter: Wie kann man Spielbaumauswerter sehen, wieso gibt es nur endlich viele deterministische Spielbaumauswerter, Darstellung des Spielbaums als Baum mit NOR-Gattern. Wahl der Inputverteilung erklärt, gezeigt, dass es eine feste Wahrscheinlichkeit p^* gibt, so dass an jedem Gatter mit Wahrscheinlichkeit p^* eine 1 berechnet wird. Im aktuellen Skript: Seite 25 Mitte bis Seite 29 unten. |
| 7 | 02.11.04 | Den besten deterministischen Spielbaumauswerter depth-first-pruning analysiert. Mit Yaos Minimaxprinzip daraus Aussage für randomisierte Spielbaumauswerter gefolgert. Maxcut: Approximation mit Güte 2, Verbesserung mit Hilfe von Matchings vorgestellt. Mincut: Kontraktionen, Algorithmus "Randomisierte Kontraktion", einfache Eigenschaften bei Kontraktion und mincut-Wert k analysiert. Begonnen mit der Analyse des Algorithmus. Im aktuellen Skript: Seite 30 oben bis 34 unten. |
| 8 | 03.11.04 | Analyse des Algorithmus "Randomisierte Kontraktion" beendet. Algorithmus Fastcut vorgestellt, Laufzeit und Erfolgswahrscheinlichkeit analysiert. Beispiel, dass nun nicht mehr *jeder* minimale Schnitt mit Wahrscheinlichkeit Omega(1/log n) ausgegeben wird. Begonnen mit der Definition des Problems "Selektion des k-t-größten Elements". Im aktuellen Skript: Seite 34 unten bis Seite 38 Mitte. |
| 9 | 09.11.04 | Randomisierte Selektion. Algorithmus vorgestellt und analysiert. Anschließend mit dem Kapitel "Allgemeine Techniken und Prinzipien" begonnen: "Eine probabilistische Rekurrenz". Im aktuellen Skript: Seite 38 Mitte bis Seite 41 Mitte. |
| 10 | 10.11.04 | Die Analyse der probabilistischen Rekurrenz beendet. "Anwendungen" dazu: die erwartete Rekursionstiefe eines FIND-Algorithmus, Graphfärbbarkeit. Begonnen mit "Momenten und Abweichungen": Linearität der Varianz bei paarweise Unabhängigkeit. Im aktuellen Skript: Seite 41 Mitte bis Seite 46 oben. |
| 11 | 16.11.04 | Boxen und Bälle: Coupon-Collector-Problem, erwartete Anzahl an Ballwürfen, bis in jeder Box ein Ball, maximale Füllhöhe, Geburtstagsparadoxon, 2-Point-Sampling, begonnen mit Anwendung von 2-Point-Sampling: Amplifikation von RP-Algorithmen. Geendet bei der Berechnung der Varianz. Im aktuellen Skript: S. 46 oben bis Seite 49 unten. (Allerdings in anderer Reihenfolge. Die letzten 4 Zeilen von S. 47 wurden noch nicht gemacht.) |
| -- | 17.11.04 | Keine Vorlesung wegen FVV. |
| 12 | 23.11.04 | Amplifikation beendet. Prinzip der verzögerten Entscheidung: Anhand von Kartenspiel und dessen Analyse veranschaulicht. Stabile Heiraten: Problem definiert, Beispiele. Algorithmus Proposal beschrieben. Korrektheit/Laufzeit bewiesen. Average-Case-Analyse zurückgeführt auf Coupon-Collector-Problem. Zum Coupon-Collector-Problem zurückgekehrt: Analyse mit Tschebyscheff begonnen. Im aktuellen Skript: S. 47 unten und 48 oben, S. 49 unten bis S.52 unten. |
| 13 | 24.11.04 | Analyse mit Tschebyscheff bei Coupon-Collector-Problem beendet. Anschließend die präzise Limesaussage über die Anzahl an Ballwürfen gezeigt. Begonnen mit den Chernoff-Schranken. Im aktuellen Skript: S. 52 unten bis 56 Mitte. |
| 14 | 30.11.04 | Beweis der Chernoffschranken beendet. "Anwendungsbeispiel" für eine Chernoffschranke. Hoeffdingsche Schranke erwähnt. Chernoffschranke mit den anderen verglichen. Anwendungsbeispiel "Set Balancing" vorgestellt. Kapitelwechsel: "OPRAs" - Routingalgorithmen auf Parallelrechnern definiert. Das Permutation Routing Problem definiert. Die untere Schranke, die für deterministische OPRAs gilt, aufgelistet. Netzwerktopologie "boolescher Hyperwürfel" erklärt. Im aktuellen Skript: S. 56 Mitte bis S. 61 unten. |
| 15 | 01.12.04 | Algorithmus "Bit Fixing" definiert. Beispiel. Gezeigt, dass es Permutationen gibt, auf denen Bit Fixing lange zum Routen benötigt. Einen randomisierten OPRA vorgestellt. Begonnen mit dessen Analyse: Analyse über die "Lag-Werte". H(i,j) definiert, T(e) definiert. Im aktuellen Skript: S. 61 unten bis S. 63 Mitte/unten. |
| 16 | 07.12.04 | Die Analyse für den randomisierten OPRA beendet. Verdrahtungsproblem: Modellierung mit booleschen Variablen, Formulierung als lineares Programm. Definition von randomisiertem Runden und deterministischem Runden. Begonnen mit der Analyse, welche Güte die von randomisiertem Runden produzierten Lösungen für das Verdrahtungsproblem haben. Im aktuellen Skript: S.63 Mitte bis S. 67 oben. |
| 17 | 08.12.04 | Analyse der Güte für das Verdrahtungsproblem beendet. Deterministisches Runden analysiert. Begonnen mit MAXSAT: Analyse des Randomisierten Rundens mit (1/2,...,1/2). Formulierung als lineares Programm. Beispiele für die Formulierung als lineares Programm. Das "Klausellemma" angegeben und bewiesen. Im aktuellen Skript: S. 67 oben bis S. 70 unten. |
| 18 | 14.12.04 | Beweis Klausellemma beendet. Bewiesen, dass man daraus Algorithmus mit Güte (1-1/e) erhält. Algorithmus MIX beschrieben und analysiert. Problem Hitting Set: Definition und Algorithmus beschrieben, der auf randomisiertem Runden basiert. Greedyalgorithmus für Hitting Set gegenübergestellt und analysiert. MAXCUT mit Semidefiniter Programmierung übersprungen (also nicht prüfungsrelevant) und dann mit der probabilistischen Methode fortgesetzt. Mit Existenzbeweis für OR-Konzentratoren begonnen. Im aktuellen Skript: S. 70 unten bis S. 74 oben. Und S. 81 Mitte bis S. 82 Mitte. |
| 19 | 15.12.04 | Existenzbeweis OR-Konzentratoren beendet. Weitere Expanderart vorgestellt. Gezeigt, wie man diese zur Wahrscheinlichkeitsamplifikation verwenden kann. Sichtweise von randomisierten OPRAs als Wahrscheinlichkeitsverteilung über deterministische OPRAs. Untere Schranke für Routingzeiten, wenn man k Zufallsbits verwenden darf. Begonnen mit dem Beweis, dass es eine Auswahl von "wenigen" deterministischen OPRAs gibt, so dass für jede Permutation sehr viele gute OPRAs dabei sind. Im aktuellen Skript: S. 82 Mitte bis S. 86 oben. |
| 20 | 04.01.05 | Gezeigt, dass es eine Auswahl von "wenigen" deterministischen OPRAs gibt, so dass für jede Permutation sehr viele gute OPRAs dabei sind. Derandomisierung: Methode der Potenzialfunktionen vorgestellt, Spezialfälle "Methode der bedingten Erwartungswerte", "Methode des pessimistischen Schätzers". Beispiele dazu: Unabhängige Menge, MAXCUT, mit MAXSAT begonnen. Im aktuellen Skript: S. 86 oben bis S. 89 unten. |
| 21 | 05.01.05 | Weitere Beispiele zur Derandomisierung: MAXSAT, "kuriose Derandomisierung" bei MAXSAT und Güte 2. Derandomisierung bei Set Balancing. Weitere Methode: Reduktion des Wahrscheinlichkeitsraums: Definition k-fache Unabhängigkeit, Definition "Wahrscheinlichkeitsraum", Satz angegeben, der die Konstruktion von k-fach unabhängigen Zufallsvariablen gestattet. Begonnen mit der Konstruktion: Matrix A mit Zeilen=Polynome und Spalten=Körperelemente, Eintrag an Stelle p,x ist p(x). Im aktuellen Skript: S. 89 unten bis S. 93 Mitte. |
| 22 | 11.01.05 | Aus Matrix A die Matrix B konstruiert. Nachgewiesen, dass diese einen k-fach unabhängigen Wahrscheinlichkeitsraum darstellt. Zwei Beispiele vorgeführt. Begonnen mit Random Walks und Markovketten. Eine einfache Markovkette vorgestellt und die erwartete Laufzeit darauf analysiert. Grundlegende Begriffe bei Markovketten definiert. Fundamentales Theorem zu Markovketten angegeben, aber nicht bewiesen. Im aktuellen Skript: S. 93 Mitte bis S. 97 unten. |
| 23 | 12.01.05 | Markovkette mit doppelt stochastischer Matrix hat Gleichverteilung als stat. Verteilung. Random Walks auf ungerichteten Graphen definiert. Stationäre Verteilung für ungerichtete Graphen berechnet. Commute-Zeit definiert und für durch Kante verbundene Knoten u,v durch 2|E| abgeschätzt. Elektrische Netzwerke eingeführt. Effektiven Widerstand definiert. Am Beispiel berechnet. Satz: Commute-Zeit kann mit effektivem Widerstand abgeschätzt werden. Begonnen mit dem Beweis. Im aktuellen Skript: S. 97 unten bis S. 102 oben. |
| 24 | 18.01.05 | Beweis zur Commutezeit beendet. Abschätzung des Widerstands über die minimale Distanz. Allgemeine Abschätzung der Commutezeit durch n hoch 3. Überdeckungszeit definiert und durch 2|E|(n-1) abgeschätzt. Lollipop-Graph definiert und analysiert. Überdeckungszeit für den vollständigen Graphen analysiert. Widerstand eines Graphen definiert und für den vollständigen Graphen ausgerechnet. Satz angegeben, der die Überdeckungszeit durch den Widerstand des Graphen abschätzt. Begonnen mit dem Beweis. Im aktuellen Skript: S. 102 oben bis S. 106 unten, obere Schranke dabei aber ausgelassen. |
| 25 | 19.01.05 | Obere Schranke nachgeholt, Rayleighs Kurzschlussprinzip, begonnen mit 2SAT- und 3SAT-Algorithmen. Entropie definiert und Binomialkoeffizienten mit Hilfe dieser abgeschätzt. Den entscheidenden Satz über die Erfolgswahrscheinlichkeit bei 3SAT angegeben, aber noch nicht bewiesen. Im aktuellen Skript: S. 106 unten bis S. 110 oben. |
| 26 | 25.01.05 | Den Satz über die Erfolswahrscheinlichkeit bewiesen. Anschließend unabhängige Klauseln definiert und analysiert, wie sich die Wahrscheinlichkeit bei besserer Initialisierung verbessert. Algorithmen: RW, RED2, MIX. Problem USTCON definiert und Platzbedarf einfacher Algorithmen diskutiert. Im aktuellen Skript: S. 110 oben bis 114 Mitte. |
| 27 | 26.01.05 | Klasse RLP definiert. USTCON in RLP gezeigt. Universelle Durchlaufsequenzen definiert und Existenz von solchen bestimmter Länge bewiesen. Schranke für d-reguläre Graphen diskutiert. Problem STCON und Algorithmus dafür angegeben. Laufzeit und Erfolgswahrscheinlichkeit analysiert. Begonnen mit "Fingerprinting". Gezeigt, wie man das Ergebnis einer Matrizenmultiplikation einfach randomisiert verifizieren kann. Im aktuellen Skript: 114 Mitte bis 118 unten. |
| 28 | 01.02.05 | Weitere Beispiele für Verifikation: Multiplikation zweier Polynome. Vandermondesche Matrix. Satz von Schwartz-Zippel. Wie entscheidet man, ob ein bipartiter Graph ein perfektes Matching enthält? Edmonds Theorem. Gleichheitstest von Strings via Fingerprinting. Im aktuellen Skript: S. 118 unten bis 122 Mitte. |
| 29 | 02.02.05 | Randomisiertes Pattern Matching. Äquivalenztest bei FBDDs. Im aktuellen Skript: S. 122 Mitte bis 125 unten. |