Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 12 » effi-2022-02 (Übersicht)
Effiziente kombinatorische Algorithmen bei Prof. Wanka, Februar 2022.
1. Welche nicht-triviale Berechnung haben wir auf ungerichteten Graphen durchgeführt?
Zweifache Zusammenhangskomponenten
2. Was ist eine zweifache Zusammenhangskomponente?
Sei V' eine Teilmenge von V und G' der durch V' induzierte Teilgraph, dann ist das eine zweifache ZHK wenn G' zweifach zusammenhängend ist und es keine Teilmenge V gibt, so dass V' eine echte Teilmenge von V ist (wichtig: G' ist damit maximal).
3. Was bedeutet zweifach Zusammenhängend?
Wenn ein Graph G keinen Artikulationspunkt enthält
4. Was ist ein Artikulationspunkt?
Der Knoten u ist ein AP wenn zwei Knoten x, y existieren so dass alle Wege zwischen x und y über u verlaufen (wichtig: Existenzquantor).
5. Wie erkennen wir einen Artikulationspunkt mit der Tiefensuche?
Der Knoten u ist ein AP wenn für einen im Tiefensuchbaum benachbarten Knoten v gilt: tief[v] >= dfnr[u] (wichtig: es muss nur einen solchen Knoten geben)
6. Wie erkennt man ob die Wurzel ein AP ist?
Wenn die Wurzel den Ausgangsgrad >= 2 im Tiefensuchbaum hat
7. Was ist die tief-Nr?
Die kleinste dfnr von einem über Baumkanten gefolgt von höchstens einer Rückkante erreichbaren Knoten.
8. Was bewirken Rückkanten?
Schließen Kreise
9. Welchen Zusammenhalt haben Kreise?
2-fach, wir sind deshalb auf der Suche nach Kreisen im Tiefensuchbaum um die 2-fachen ZHK zu erkennen.
10. Was ist die Definition eines Flussproblems?
11. Was ist die Definition eines Flusses?
Konservierungsgesetz + der Fluss pro Kante muss zwischen 0 und er Kapazität der Kante liegen.
12. Was ist die Kapazität eines Flusses?
Hier wichtig dass es sowohl von der Senke als auch von der Quelle aus definiert werden kann aufgrund des Konservierungsgesetzes.
13. Was ist ein erweiternder Weg?
14. Was ist das Konzept von Rückwärtskantes?
Machen eine vorher getroffene Entscheidung rückgängig. Ein Fluss kann umgelenkt werden.
15. Kann ein maximaler Fluss nur über Vorwärtskanten gefunden werden?
(Hier hab ich etwas verkackt): Nein, ein Beispiel aus der VL war ähnlich dem Graph mit der exponentiellen Laufzeit nur an jeder Kante eine Kapazität von 1. Wenn man einen erweiternden Weg über die mittlere Kante nimmt kommt man ohne das Konzept der Rückwärtskantes nicht auf einen maximalen Fluss.
16. Wann ist ein Fluss maximal?
Wenn es keine erweiternde Wege mehr gibt und jeder Versuch in einem Knoten v endet mit… + Konstruktion des s-t-Schnittes + Zwischenfrage was ein s-t-Schnitt ist
17. Kann es einen noch minimaleren Schnitt geben?
Nein, nach Lemma … ist der minimale Schnitt der, der gleich der Flusskapazität ist.
18. Wie nennt man dieses Konzept?
Max-Flow-Min-Cut Theorem.
19. Was ist schlecht an der Berechnung von maximalen Flüssen über Residualgraphen?
Beispiel mit exponentieller Laufzeit
20. Welcher Algorithmus macht das besser?
Algorithmus von Dinic
21. Welche Konstruktion verwendet der und wie sieht diese aus?
Geschichtetes Netzwerk: Knotenmenge V-tilde und Kanten E-tilde erklären
22. Was ist eine Schicht im Netzwerk?
Die Knoten mit dem selben Abstand zur Quelle bilden eine Schicht.
23. Welche Art von Graph ist das geschichtete Netzwerk?
DAG
24. Welche guten Eigenschaften hat das geschichtete Netzwerk?
Wenn Fluss maximal dann ist V-tilde leer. Jeder Weg im geschichteten Netzwerk ist ein erweiternder Weg, d.h. es genügt die „greedy“-Suche.
25. Wie oft wird das geschichtete Netzwerk höchstens neu berechnet und warum?
Wird höchstens |V|-1 mal neu berechnet da der Abstand der Knoten pro Iteration um mindestens 1 weiter weg von der Quelle hin zur Senke wandert.
26. Was ist eine Knotenüberdeckung?
27. Welchen exakten Algorithmus haben wir zur Berechnung einer minimalen Knotenüberdeckung kennen gelernt?
Ich glaub der Algorithmus hieß MVC, man sollte die einzelnen Schritt erklären (Wenn es eine Kante gibt in dem ein Knoten den Grad 1 hat + wenn alle Knoten den Grad 2 haben …)
28. Was ist die Laufzeit des Algorithmus? Wie leitet man die her?
t(n) ⇐ t(n-1) + t(n-4) + poly(n)
Charakteristisches Polynom aufstellen
29. Welchen Algorithmus hatten wir für das Entscheidungsproblem von Vertex Cover?
DivideAndConquerVC erklärt (wichtig ist, dass hier das k mit jeder Iteration um 1 reduziert wird)
Obwohl ich 2 Fehler gemacht habe, hat es noch für eine 1.0 gereicht. Also die Bewertung und die Fragen sind sehr fair.
Aus den Übungen kam nichts dran, aber keine Garantie dass das in Zukunft auch so ist.