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!