Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 12 » Randomisierte Algorithmen, 2017 (Übersicht)
Randomisierte Algorithmen, 2017
- Wir hatten uns am Anfang zwei Beispiele zum warm Werden angeschaut, eins davon war der Randomisierte Quicksort. Erklären, was daran randomisiert ist und wie wir den analysiert hatten
- Allgemein erstmal Quicksort erklären (verschiedene Strategien zur Pivot-Wahl, Eingabe).
- Laufzeit in Anzahl Schlüsselvergleiche (was ist ein Schlüssel? Index ist Position im sortierten Array) → Worst Case n^2, aber sehr unwahrscheinlich
- Randomisierte Quicksort: Pivot-Element wird zufällig gewählt.
- warum reicht es den Bereich i bis j zu betrachten?
- Analyse mit der Indikatorvariable im Detail erklären. (Man sollte das Endergebnis und die Rechnung über die Doppelsumme mit H(n) auswendig können, 2*n*ln(n))
- SAT-Algorithmus erklären
- Eingabe, Anzahl Iterationen, Ausgabe (wichtig: ggf. auch falsch, Monte-Carlo-Algorithmus)
- Analyse erklären (wichtig: Eingabe muss erfüllbar sein, sonst gibt es kein S)
- Wahrscheinlichkeiten erklären, für Markov-Modell Ungleichung auflösen → höchstens schlechter
- Markov-Modell zeichnen, Gleichungssystem aufstellen, Lösung des Gleichungssystem als EW = n^2 + i^2 (Lösen geht, da n Gleichungen für n Unbekannte, nicht abhängig, h für hitting)
- Abschätzung des EW mit Markov-Ungleichung und Wahrscheinlichkeitsverstärkung c
- Was ändert sich bei 3SAT im Markov-Modell/Gleichungssystem?
- Algo tendiert zu 0, zufällige Startbelegung binomialverteilt, was bringt das?
- Erwartungswert jetzt schlechter als 2^n
- Was macht Schöning? Neustart nach 3n Iterationen (Rechnung war nicht wichtig)
- Schönings Algo läuft in O(4/3^n)
- Wo hatten wir noch Markov-Ketten? → Cover-Time und als UG für MCMC
- Anzahl der Schritte h_i,i = 1/pi = …
- Anzahl der Schritte h_i,j < 2*|E|, Abschätzung über Summe erklären (wichtig: i und j sind Nachbarn)
- Wie haben wir dann Cover-Time abgeschätzt? → Spannbaum und Euler-Tour 4*|V|*|E|
- Wo haben wir das benutzt: s-t-Connectivity (wichtig: langsamer als Tiefensuche aber deutlich weniger Speicher)
- Wie viele Iterationen macht Algorithmus? → Cover-Time über vollständigen Graphen abschätzen, insgesamt |V|^3