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

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!