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

Effiziente Kombinatorische Algorithmen

DFS:

  • Was ist eine nichttrivale Eigenschaft, die wir auf ungerichteten Graphen mit Tiefensuche berechnet haben?
  • Was ist eine zweifache ZHK?
  • Definiere Artikulationspunkt.
  • Was ist der Superstrukturgraph? Eigenschaften?
  • Wie berechnen wir 2ZK genau?
  • Was haben Rückkanten im Tiefensuchbaum für Eigenschaften?
  • Warum funktioniert der Algorithmus?
  • Wie ist die Laufzeit?

VC:

  • Es wurde das Kapitel „parametrisierte Komplexität“ kurz erläutert. Wie war die Überschrift dieses Kapitels?
  • Was haben wir für ein Beispiel behandelt?
  • Definiere Vertex Cover.
  • Wann nennen wir einen Algorithmus parametrisiert?
  • Wie sah der parametrisierte Algorithmus aus der Vorlesung zu Vertex Cover aus? (Dabei wurden noch die beiden Lemmata aus der Vorlesung gefordert)
  • Wie ist die Laufzeit?
  • Wie können wir nun aus dem Algorithmus für das Entscheidungsproblem einen Algorithmus für das Optimierungsproblem machen?
  • Was ist die Worst-Case Laufzeit dieses Algorithmus? Dafür sollte ich die beiden Laufzeitgraphen von Brute-Force und parametrisiertem Algorithmus hinzeichen. Der Schnittpunkt (Break-Even-Point), der gleichzeitig Maximum ist, ist dabei kleiner als die beiden Maxima der Algorithmen selbst.

DP:

  • Wir haben das TSP betrachtet. Definieren Sie dieses.
  • Wie können wir dieses Problem schneller als mit Laufzeit (n/e)^n lösen?
  • Warum funktionert das?
  • Wie ist die Laufzeit?