Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

@@ Zeile 1: / Zeile 1: @@
+====== 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?