Sie befinden sich hier: Termine » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 12 » Randomisierte Algorithmen, 2017   (Übersicht)

Randomisierte Algorithmen, 2017

  1. 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))
  2. 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
  3. 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)
  4. 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