Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 12 » Randomisierte Algorithmen SS 2023 (04.08.23)
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung | Nächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:hauptstudium:ls12:rand_2023 [04.08.2023 09:44] – jononus | pruefungen:hauptstudium:ls12:rand_2023 [04.08.2023 10:21] – jononus | ||
---|---|---|---|
Zeile 2: | Zeile 2: | ||
{{indexmenu>: | {{indexmenu>: | ||
===== Anmerkungen ===== | ===== Anmerkungen ===== | ||
- | * Meine Vorbereitung bestand aus dem lernen des Skripts in einer Tiefe, | + | * Meine Vorbereitung bestand aus dem lernen des Skripts in einer Tiefe, |
- | * Die Atmosphäre bei Prof. Wanka war wie gewohnt entspannt und recht angenehm. Er saß entspannt | + | |
+ | * 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. | ||
===== Prüfungsfragen===== | ===== Prüfungsfragen===== | ||
+ | == Einleitung: Wir haben uns 2 Bsp. zum warmwerden angesehen, eines davon MinCut. ====== | ||
+ | (hat viel Zeit gekostet, gefühlt 15 Minuten, also sehr tief gegangen!) | ||
+ | - Was ist das MinCut Problem? Komplexität? | ||
+ | - Wie sieht der Algorithmus aus? | ||
+ | - Analyse Beginn? (Referenzschnitt K, Wkt, dass keine Kante aus K Kontrahiert wird) | ||
+ | - Wie kommt man von dem Produkt auf 2/n*(n-1)? | ||
+ | - 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: | ||
+ | - 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) | ||
+ | == MaxCut und IS == | ||
+ | - zugrundeliegende Methodik erklären (A: probabilistische Mehtode) | ||
+ | - MaxCut Algorithmus erklären, was ist die erwartete Größe des ausgegebenen Schnitts? | ||
+ | - Analyse dazu: (A: wann überlebt Kante, Wkt dafür, Summe über alle Kanten) | ||
+ | - Wkt für Schnitt ist ja u.U. recht klein, wie bekommen wir einen raus? (A: aus MC einen Las Vegas Algorithmus, | ||
+ | - 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) | ||
+ | - IS nochmal das Gleiche: | ||
+ | - Algorithmus | ||
+ | - Analyse: Was ist d? Erwartungswert für Größe des IS herleiten + angeben | ||
+ | == SAT == | ||
+ | - 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) | ||
+ | - 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) | ||
+ | == Ende, gute 30 Minuten um == | ||
+ | |||
+ |