Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 12 » Randomisierte Algorithmen, 2014 (Übersicht)
no way to compare when less than two revisions
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
— | pruefungen:hauptstudium:ls12:rand_2014 [24.07.2016 11:24] (aktuell) – angelegt Nyx | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
+ | ====== Randomisierte Algorithmen, | ||
+ | |||
+ | * Was ist denn ein randomisierter Algorithmus? | ||
+ | * 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, | ||
+ | * 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, | ||
+ | * Was ist ein Monte Carlo-Algorithmus? | ||
+ | * 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 # | ||
+ | * 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, | ||