Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 12 » Randomisierte Algorithmen, 2014
Randomisierte Algorithmen, 2014
- Was ist denn ein randomisierter Algorithmus? → Algorithmus, der mit Zufall(szahlen) arbeitet
- Wir hatten uns am Anfang zwei Beispiele zum warm Werden angeschaut, eins davon war der Randomisierte Quicksort. Erklären Sie mal, was daran randomisiert ist und wie wir den analysiert hatten → Allgemein erstmal Quicksort erklären (verschiedene Strategien zur Pivot-Wahl). Randomisierte Quicksort: Pivot-Element wird zufällig gewählt. Dann die Analyse mit der Indikatorvariable im Detail erklären. (Man sollte das Endergebnis auswendig können, 2 * n * ln(n))
- Was ist die Probabilistische Methode? → Man möchte wissen, ob es ein Objekt mit Eigenschaft E gibt. Also würfelt man ein zufälliges Objekt A und zeigt, dass die Wahrscheinlichkeit, dass A diese Eigenschaft E besitzt < 1 ist ⇒ es gibt ein solches Objekt.
- Wir haben uns dazu Max-Cut und Independet Set angesehen. Was ist denn ein Independet Set? → Definition
- Und was haben wir da mit der probabilistischen Methode gemacht? → Algorithmus erklären und vorrechnen.
- Wie kann ich denn jetzt sicherstellen, dass ich auf jeden Fall ein richtiges Ergebnis bekomme, bisher haben wir ja nur den Erwartungswert. → Las Vegas-Algorithmus
- Was ist ein Monte Carlo-Algorithmus? → Stichprobe auf Universum übertragen, Uniformer Generator, Beantworter, Zähl-Probleme
- Was besagt denn das Estimator Theorem? → Erklären und ihm war sehr wichtig, dass T von der Expansion abhängt.
- Wie hatten wir denn beim #DNF-Problem das clevere Universum gewählt? → Algorithmus samt Wahrscheinlichkeiten erklären
- Und dann hatten wir ja noch das #COL_k -Problem… → Den kompletten Algorithmus erklären und zeigen, was davon Monte-Carlo ist und was Markov. Wichtig: Markov arbeitet hier als UG, weil der Färbungsgraph, den Markov erstellt, regulär ist!