Randomisierte Algorithmen (10.10.2023)

* Randomisierte Algorithmen (7.5ECTS) im SS23

* Datum: 10.10.2023

* Prüfer: Professor Wanka und Matthias Kergaßner

* Evaluation:

• Die Atmosphäre war entspannt. Wir waren mit Professor Wanka und Matthias in einem Büro an einem kleinen Rundtisch. Ich erinnere mich an eine Klausur im Jahr 2020 bei Professor Wanka, die mir stressiger erschien. Das könnte möglicherweise auch Corona geschuldet gewesen sein.
• Ich habe mich bemüht, langsamer zu sprechen (da ich normalerweise sehr schnell spreche) und alles detailliert zu erläutern. Das schien hilfreich zu sein, und die Zeit verging rasch.
• Die Untersuchung der ersten Algorithmen, insbesondere die zugrundeliegenden Konzepte, wurden detailliert abgefragt. Der Fokus lag weniger auf Arithmetik, sondern eher darauf, wie man beispielsweise bestimmte Wahrscheinlichkeit abschätzen kann.
• Die späteren Algorithmen wurden bei mir nicht abgefragt. Bei den anderen Prüfungsprotokollen hatte ich aber das Gefühl, dass dort die genauen Berechnungen weniger wichtig werden und es mehr um die Ideen geht.

Ich beschreib hier größtenteils nur die Fragen, da die meisten Antworten im Skript stehen

* Was ist das MinCut Problem?

* Wie schnell wäre der deterministische Algorithmus

• Hier hat gereicht dass er polynomiell und recht kompliziert ist
• Anscheinend kennt Wanka mittlerweile einen einfacheren deterministischen MinCut Algorithmus, den er bei EffKombAlg vorstellen will

* Wie funktioniert der randomisierte Algorithmus?

* Warum wählen wir die Kanten uniformly at random?

* Wie haben wir den analysiert (Referenzschnitt genommen, etc., Wahrscheinlichkeit dass Referenzschnitt genommen wird ist untere Schranke für Korrektheit)

* Ist die Größe eines minimalen Schnitts im verkleinerten Graphen gleich?

* Was bringt es uns, |K|/|E_i| durch ⇐ 2/|V_i| (In der Abschätzung kommt |K|, das wir nicht kennen, nicht mehr vor)

* Wie oft müssen wir erwartet wiederholen (1/p, geometrische Verteilung, Wahrscheinlichkeitsverstärkung)

* Wie nennt man das dann?

• Mit Hoher Wahrscheinlichkeit
• Man kann die Fehlerwahrscheinlichkeit über das c beliebig drücken.
• c geht linear in die Anzahl Versuche aber exponentiell in die Wahrscheinlichkeit

* Was ist das MaxCut Problem?

• Unterteilen von V in disjunkte A und B
• Entscheidungsproblem ist NP-Vollständig
• Wir können aber mit probablistischer Methode zeigen, dass A und B mit c(A, B) >= |E|/2 existieren

* Worüber iteriert der Algorithmus?

* Warum iteriert der Algorithmus über die Knoten, nicht die Kanten?

• Weil wir dann für manche Kanten gar nicht mehr würfeln könnten, das wäre dann kein Schnitt

* Wie analysieren wir den MaxCut Algorithmus?

* Wie kommen wir auf die Erfolgswahrscheinlichkeit? (per Erwartungswert)

* Was ist die erwartete Anzahl Wiederholungen?