• In diesem Semester fand sowohl die Vorlesung als auch die Übung statt. Vorbereitet habe ich mich durch Lernen des Skripts und mittels Durchgehen der Übungen und vorhandenen Braindumps. Die meisten Beweise habe ich sehr genau gelernt, nur bei Themen wie Chernoff, Farbenzählen und (komplexer) SAT probalistischen Methode habe ich die Beweise nur so gelernt, dass ich sie erklären kann.
• Die Atmossphere war im allgemeinen sehr entspannt. Prof. Wanka hat gerne mal bei einigen Annahmen/Ergebnissen in Beweisen genauer nachgefragt (Warum ist hier in der Quicksort Abschätzung ein *2 zu finden und kein *1.3…? Warum ist die erwartete Anzahl von Schritten bei ein Ereignis mit Wahrscheinlichkeit 1/n eintritt n?). Er hilft aber auch gerne weiter wenn man mal feststeckt. Die Fragen waren ebenfalls sehr human. Es wurde Papier zum eigenem Nutzen bereit gestellt.

Wie immer, keine Garantie auf Korrektheit im Protokoll. ; )

Quicksort, aber das Pivotelement wird uniform zufällig ausgewählt.

(Habe angefangen mit dem worst case, nach Prof. Wanka ist der aber geschenkt.) Analyse des randomisierten Quicksorts im Detail erklären:

• Welche Zufallsvariablen werden gewählt? Wichtig: i und j bezeichnen das i-te und j-te Element der sortierten Liste, es gilt o.B.d.A. i < j.
• Wie werden diese Zufallsvariablen aufsummiert und wie kommt man auf den Erwartungswert dieser Summe? (X_i^j sind Indikatorvariablen → Pr[X_i^j = 1] = E[X_i^j])
• Wie kommen wir auf Pr[X_i^j = 1]? Hier wichtig: Warum reicht es nur S = (i, …, j) zu anzuschauen → Betrachte die möglichen Pivotelemente die ausgwählt werden können (Links/ Rechts von S, i, j oder etwas zwischen i und j).
• Welche Variablensubstitutionen werden gemacht und wie wird die harmonische Reihe abgeschätzt?
• Zum Schluss: Warum steht da eine *2 und kein mal *1,3… wie man es häufig sieht → Aufspaltung von ln(n) in log2(n)/log2(e).

Las Vegas Algorithmus, da das Ergebnis immer korrekt ist aber die Laufzeit vom Zufall abhängt.

Man beweist, dass ein Objekt E existiert, indem man zeigt, dass die Wahrscheinlichkeit, dass E zustande kommt > 0 ist.

Knoten eines Graphen werden in zwei disjunkte Mengen aufgeteilt ⇒ Anzahl Kanten die von Menge A nach Menge B gehen = Z. Was ist der maximale Wert von Z, wenn A und B passend gewählt werden?

Dieses Problem ist NP-vollständig. MinCut hingegen (Was ist der minimale Wert von Z?) ist in Polynomzeit lösbar.

Es existiert immer ein Schnitt der Größe mindestens m/2, wobei m die Zahl der Kanten ist.

Um das zu zeigen, baut man einen Algorithmus, welcher mit Chance jeweils 1/2 jeden Knoten in entweder A oder B packt.

Es gilt für dann eine Kante e=(v1, v2):

Pr[“e geht über den Schnitt”]

= Pr[“(v1 in A and v2 in B) or (v1 in B and v2 in A)”]

= 1/2 * 1/2 + 1/2 * 1/2 = 1/2

Und damit für den Erwartungswert der über den Schnitt gehenden Kanten E=m/2 ⇒ Mit p>0 existiert ein Schnitt >= m/2

Führe den oben genannten Algorithmus so lange aus, bis wir einen Schnitt >= m/2 bekommen.

Spalte den oberen Erwartungswert in einen Teil >= m/2 und einen Teil < m/2 auf. Nutze diese Aufteilung um die Wahrscheinlichkeit p abzuschätzen, dass eine Iteration einen Cut >= m/2 ausgibt. 1/p ist dann die erwartete Anzahl an Schritten (Geometrische Verteilung).

Fange mit irgendeiner Belegung an (Welche spielt keine Rolle, erst im Schöning wird auswürfeln gefordert).

Wiederhole n mal: Wähle eine Klausel C aus die nicht erfüllt ist, wähle aus ihr uniform eine Variable aus und tausche ihren Wert.

Sollte die KNF erfüllt werden bricht der Algorithmus direkt ab und gibt TRUE aus.

Ansonsten gibt er FALSE aus.

Fordere, dass die KNF erfüllbar ist, sei S eine erfüllende Belegung.

Definiere X_j := „Es stimmen j Variablen mit S überein“. Dann gilt (X_j → X_i bezeichnet den Übergang von X_j nach X_i):

Pr[X_n → X_n] = 1 (Da hier der Algorithmus spätestens abbricht) Pr[X_n → X_{n-1}] = 0 (“”)

Pr[X_0 → X_1] = 1 (Da definitiv eine Variable richtig gemacht wird)

Pr[X_i → X_{i+1}] >= 1/2 (Da mindestens eine Variable in C falsch ist)

Pr[X_i → X_{i-1}] ⇐ 1/2 (Da maximal eine Variable in C richtig ist)

Resultierende Markov-Kette beschreiben und zeichnen. Daraus ergibt sich für h_j := „Erwartete Anzahl Schritte um von X_j nach X_0 zu kommen“:

h_0 = 1 + h_{1} h_j = 1 + 1/2 h_{j-1} + 1/2 h_{j+1} h_n = 0

n+1 Gleichungen n Variablen ⇒ LGS. Lösung: n^2-j^2 ⇒ n^2 Schritte erwartet bis der Algorithmus eine Lösung findet.

Pr[X_i → X_{i+1}] >= 1/3 (Da mindestens eine Variable in C falsch ist)

Pr[X_i → X_{i-1}] ⇐ 2/3 (Da maximal zwei Variablen in C richtig sind)

Markov-Kette ändert sich, damit auch das LGS:

h_0 = 1 + h_{1} h_j = 1 + 2/3 h_{j-1} + 1/3 h_{j+1} h_n = 0

Lösung: poly(n, j)*2^n ⇒ poly(n)*2^n Schritte erwartet bis der Algorithmus eine Lösung findet, sogar schlechter als Bruteforce.