FSI-Zimmer: offen
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 | Letzte ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
| pruefungen:hauptstudium:ls12:rand_2023 [04.08.2023 10:21] – jononus | pruefungen:hauptstudium:ls12:rand_2023 [04.08.2023 10:24] – jononus | ||
|---|---|---|---|
| Zeile 25: | Zeile 25: | ||
| - Analyse: Was ist d? Erwartungswert für Größe des IS herleiten + angeben | - Analyse: Was ist d? Erwartungswert für Größe des IS herleiten + angeben | ||
| == SAT == | == 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) | + | - 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) | - 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 == | == Ende, gute 30 Minuten um == | ||