Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 12 » Approximationsalgorithmen, 2012-07-31   (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

pruefungen:hauptstudium:ls12:approx_2012 [09.07.2014 17:19] – angelegt errnosyspruefungen:hauptstudium:ls12:approx_2012 [24.07.2016 09:17] (aktuell) – ThiloK
Zeile 7: Zeile 7:
   * Erkläre GreedyCol und dessen Güte; Definiere Knotenfärbung   * Erkläre GreedyCol und dessen Güte; Definiere Knotenfärbung
   * Definiere das IndependentSet-Problem; Welchen Zusammenhang gibt es zur Knotenfärbung?   * Definiere das IndependentSet-Problem; Welchen Zusammenhang gibt es zur Knotenfärbung?
-  * Erkläre den GreedyIS-Algorithmus. Unter Verwendung welcher Unbekannten wurde er analysiert? (-> Chormatische Zahl)+  * Erkläre den GreedyIS-Algorithmus. Unter Verwendung welcher Unbekannten wurde er analysiert? (-> Chromatische Zahl)
   * Es wird nach dem Maximierungsproblem zum Knotenfärbungsproblem gefragt, wie es auf einem Übungsblatt vorkam.   * Es wird nach dem Maximierungsproblem zum Knotenfärbungsproblem gefragt, wie es auf einem Übungsblatt vorkam.
   * Frage nach Randomisierten Algorithmen insb. zu MaxSat, Indikatorvariable, Zusammenhang zwischen Wahrscheinlichkeit der Erfüllung einer Klausel und dem Erwartungswert der Anzahl erfüllter Klauseln.   * Frage nach Randomisierten Algorithmen insb. zu MaxSat, Indikatorvariable, Zusammenhang zwischen Wahrscheinlichkeit der Erfüllung einer Klausel und dem Erwartungswert der Anzahl erfüllter Klauseln.