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!