FSI Informatik/pruefungen/hauptstudium/ls12/approx

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

Diese Seite ist nicht editierbar. Du kannst den Quelltext sehen, jedoch nicht verändern. Kontaktiere den Administrator, wenn du glaubst, dass hier ein Fehler vorliegt.

====== Approximationsalgorithmen, 2012-07-31 ======

Fragen aus der Prüfung, in Klammern steht teils die Richtung der Antwort:

  * Was ist ein Kombinatorisches Optimierungsproblem?
  * Was ist ein Approximationsalgorithmus? (-> + Unterscheidung: absolute Güte, relative Güte)
  * Erkläre GreedyCol und dessen Güte; Definiere 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? (-> Chromatische Zahl)
  * 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.
  * Erkläre Derandomisierung von MaxSat; Was macht ein Problem+Algorithmus derandomisierbar?

Im Allgemeinen schadet es auch nicht, etliche relativen Güteschranken zu den Problemen zu kennen.