Randomisierte Algorithmen SS 2023 (04.08.23)

• Meine Vorbereitung bestand aus dem lernen des Skripts in einer Tiefe, sodass ich alle Laufzeiten/ Wahrscheinlichkeiten der besprochenen Algorithmen kannte und so deren Analyse reproduzieren konnte
• Die Atmosphäre bei Prof. Wanka war wie gewohnt entspannt und recht angenehm. Er saß entspannt zurückgelehnt in seinem Stuhl und stellte seine die Prüfung strukturierenden Fragen. Ein Themengebiet wurde immer in mindestens 4 Fragen unterteilt, teilweise mehr.
• Im Folgenden sind hauptsächlich die nacheinander gestellten Fragen aufgezeigt, Antworten finden sich im Skript.
• Prof. Wanka wollte gerne das Ergebnis der Analyse wissen und dann Fragen: Wie kommt man darauf? Ich hätte es andersum einfacher gefunden, dann hätte man sich das Ergebnis herleiten können.

(hat viel Zeit gekostet, gefühlt 15 Minuten, also sehr tief gegangen!)

1. Was ist das MinCut Problem? Komplexität? (A: In P, aber großes Polynom)
2. Wie sieht der Algorithmus aus?
3. Analyse Beginn? (Referenzschnitt K, Wkt, dass keine Kante aus K Kontrahiert wird)
4. Wie kommt man von dem Produkt auf 2/n*(n-1)?
5. Wie oft haben wir den Algorithmus wiederholt? (Er wollte auf Wahrscheinlichkeitsverstärkung raus, stand im Skript im Bonusteil, S.12, an VL habe ich mich nicht mehr/falsch erinnert? Wusste nichts, er hat probiert mich hinzuführen:)
6. Form (1-1/i)^i lässt sich als? (A:e^-1) abschätzen. Wkt dafür, keinen Schnitt zu finden ist höchstens n^-c (+ Wie kommt man drauf? A: Kp), also (A: mit hoher Wahrscheinlichkeit)

1. zugrundeliegende Methodik erklären (A: probabilistische Mehtode)
2. MaxCut Algorithmus erklären, was ist die erwartete Größe des ausgegebenen Schnitts?
3. Analyse dazu: (A: wann überlebt Kante, Wkt dafür, Summe über alle Kanten)
4. Wkt für Schnitt ist ja u.U. recht klein, wie bekommen wir einen raus? (A: aus MC einen Las Vegas Algorithmus, diesen erklärt.)
5. Analyse? Laufzeit? (er wollte glaube ich nur die Antwort: Geometrische Verteilung, 1/p und p = 2/m+2. Wusste ich nicht mehr, habe dann die Rechnung erklärt und ihn irgendwann nach dem Wert von p gefragt, weil ich nicht ausmultiplizieren und die Ungleichung umstellen wollte)
6. IS nochmal das Gleiche:
7. Algorithmus
8. Analyse: Was ist d? Erwartungswert für Größe des IS herleiten + angeben

1. 2-SAT, Random Walk: (A: Analyse, pessimistische Abschätzung von >= 1/2 als =1/2, dadurch bekommt man Markov-Kette. Hitting Time hj, d.h. starte mit j richtigen Belegungen, n+1 Gleichungen mit n+1 Variablen hj ⇒ eindeutig lösbar, Lösung)
2. Was passiert bei 3-SAT mit dieser Methode? (A: Wkten gehen auf >= 1/3 fürs besser werden und ⇐2/3 fürs schlechter werden, 2^n)