After-Test Thread 23.06.2016

  • Ok, fand's jetzt nicht so schlimm wie ich befürchtet hatte ("Befürchtung" war eher Ungewissheit, da sie ja den Stoff umgekrempelt haben). Beweis-artige Frage (die ich immer am schwierigsten fand in der Übung) war nur eine mit 10 Punkten.


    Aus dem Gedächtnis (ohne Gewähr)


    1.) 17 Punkte


    1.1) (8 Punkte) Minimal Vertex Cover in zwei Graphen mit Kantengewichten markieren (einer davon war ein Baum)


    1.2) (9 Punkte) Einsetzaufgabe Weighted-Independent-Set-In-A-Tree(T) in vorgeschriebenen Code, alle Zuweisungen für Mmin und Mmax und return-Wert (insgesamt an 5 Stellen).


    2.) 20 Punkte


    2.1) (10 Punkte) Zeigen wie Gütegarantie für Approx-Vertex-Cover(G) sich verändert wenn Kantengewichte aus der Menge {1, 2, 4} ausgewählt werden. Ich hab irgendwas mit max(M) hingeschrieben, glaub nicht, dass es richtig ist.


    2.2) (10 Ounkte) Multiple-Choice Frage (zwei Blöcke, je 4 Punkte) zu NP-Vollständigkeit, Transitivität, usw. Zusätzlich frage mit 2 Punkten wie die Laufzeit ist für X >= Y >= Z mit Rxy n^2, Ryz n^3 und Z n^1.5 (oder so ähnlich).


    3.) 13 Punkte
    Branch and Bound berechnen, exakt wie im Vorlesungs/Übungsbeispiel


    3.1) (? Punkte) Weights und Reihenfolge bestimmen


    3.2) (? Punkte) Der eigentliche Algorithmus, den Baum zeichnen (es war ein leerer Baum zum einsetzen und erweitern gedruckt), Abbruchbedingungen usw.


    3.2) (2 Punkte) Die optimale Menge und deren Wert