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 ÜberarbeitungNächste Überarbeitung | Vorherige Überarbeitung | ||
pruefungen:hauptstudium:ls12:rand_2023 [04.08.2023 10:21] – jononus | pruefungen:hauptstudium:ls12:rand_2023 [04.08.2023 10:26] (aktuell) – jononus | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | ====== Randomisierte Algorithmen SS 2023 ====== | + | ====== Randomisierte Algorithmen SS 2023 (04.08.23) |
{{indexmenu>: | {{indexmenu>: | ||
===== Anmerkungen ===== | ===== Anmerkungen ===== | ||
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 == | ||