Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 12 » effi-2022-02

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
pruefungen:hauptstudium:ls12:effi-2022-02 [23.02.2022 10:28] – letmesee2pruefungen:hauptstudium:ls12:effi-2022-02 [23.02.2022 10:49] (aktuell) – letmesee2
Zeile 9: Zeile 9:
 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). 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?+**3. Was bedeutet zweifach Zusammenhängend?**
  
 Wenn ein Graph G keinen Artikulationspunkt enthält Wenn ein Graph G keinen Artikulationspunkt enthält
  
-4. Was ist ein Artikulationspunkt?+**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). 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?+**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) 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?+**6. Wie erkennt man ob die Wurzel ein AP ist?**
  
 Wenn die Wurzel den Ausgangsgrad >= 2 im Tiefensuchbaum hat Wenn die Wurzel den Ausgangsgrad >= 2 im Tiefensuchbaum hat
  
-7. Was ist die tief-Nr?+**7. Was ist die tief-Nr?**
  
 Die kleinste dfnr von einem über Baumkanten gefolgt von höchstens einer Rückkante  erreichbaren Knoten. Die kleinste dfnr von einem über Baumkanten gefolgt von höchstens einer Rückkante  erreichbaren Knoten.
  
-8. Was bewirken Rückkanten?+**8. Was bewirken Rückkanten?**
  
 Schließen Kreise Schließen Kreise
  
-9. Welchen Zusammenhalt haben Kreise?+**9. Welchen Zusammenhalt haben Kreise?**
  
-2-fach, wir sind auf der Suche nach Kreisen im Tiefensuchbaum um die 2-fachen ZHK zu erkennen.+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?+**10. Was ist die Definition eines Flussproblems?**
  
-11. Was ist die Definition eines Flusses?+**11. Was ist die Definition eines Flusses?**
  
-12. Was ist die Kapazität eines Flusses?+Konservierungsgesetz + der Fluss pro Kante muss zwischen 0 und er Kapazität der Kante liegen.
  
-13. Was ist ein erweiternder Weg?+**12. Was ist die Kapazität eines Flusses?**
  
-14. Was ist das Konzept von Rückwärtskantes?+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. Machen eine vorher getroffene Entscheidung rückgängig. Ein Fluss kann umgelenkt werden.
  
-15. Kann ein maximaler Fluss nur über Vorwärtskanten gefunden 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. (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?+**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+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?+**17. Kann es einen noch minimaleren Schnitt geben?**
  
 Nein, nach Lemma ... ist der minimale Schnitt der, der gleich der Flusskapazität ist. Nein, nach Lemma ... ist der minimale Schnitt der, der gleich der Flusskapazität ist.
  
-18. Wie nennt man dieses Konzept?+**18. Wie nennt man dieses Konzept?**
  
 Max-Flow-Min-Cut Theorem. Max-Flow-Min-Cut Theorem.
  
-19. Was ist schlecht an der Berechnung von maximalen Flüssen über Residualgraphen?+**19. Was ist schlecht an der Berechnung von maximalen Flüssen über Residualgraphen?**
  
 Beispiel mit exponentieller Laufzeit Beispiel mit exponentieller Laufzeit
  
-20. Welcher Algorithmus macht das besser?+**20. Welcher Algorithmus macht das besser?**
  
 Algorithmus von Dinic Algorithmus von Dinic
  
-21. Welche Konstruktion verwendet der und wie sieht diese aus?+**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.
  
-Knotenmenge V-tilde+Aus den Übungen kam nichts dran, aber keine Garantie dass das in Zukunft auch so ist.