Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 12 » effi-2018-02 (Übersicht)
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
| Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung | |
| pruefungen:hauptstudium:ls12:effi-2018-02 [16.02.2018 08:50] – christian-de | pruefungen:hauptstudium:ls12:effi-2018-02 [16.02.2018 08:57] (aktuell) – christian-de |
|---|
| * Herleitung durch Herrn Wanka: Spezielles Optimierungsproblem ist ein "Flussproblem". Was ist gegeben? Wichtig ist die Unterscheidung zwischen dem Problem selbst und der Definition eines Flusses. Hier hilft eine Skizze auf dem Papier. Er ging detailliert auf die Restriktionen ein und wollte die Flusserhaltung, Kapazitätsfunktion inkl. Schranken und den Fluss genau erklärt haben (er wollte u.a. darauf hinaus, dass Kapazität > 0 sein muss und Fluss >= 0 sein kann). | * Herleitung durch Herrn Wanka: Spezielles Optimierungsproblem ist ein "Flussproblem". Was ist gegeben? Wichtig ist die Unterscheidung zwischen dem Problem selbst und der Definition eines Flusses. Hier hilft eine Skizze auf dem Papier. Er ging detailliert auf die Restriktionen ein und wollte die Flusserhaltung, Kapazitätsfunktion inkl. Schranken und den Fluss genau erklärt haben (er wollte u.a. darauf hinaus, dass Kapazität > 0 sein muss und Fluss >= 0 sein kann). |
| * Genaue Erklärung und Unterscheidung: "Fluss vs. Wert des Flusses", "Schnitt und Kapazität des Schnitts" | * Genaue Erklärung und Unterscheidung: "Fluss vs. Wert des Flusses", "Schnitt und Kapazität des Schnitts" |
| * Herleitung erweiternde Wege und die Aussagen von Ford & Fulkerson (inkl. aller vorangegangener Definitionen zu nützlichen Kanten, Residualgraph, etc.). Hier ging es immer mal wieder zwischen erweiternden Wegen, maximalen Flüssen und minimalen Schnitten hin und her, bis die beiden Aussagen und deren Zusammenhang komplett durchleuchtet waren. Er wollte auch ein Beispiel gezeichnet haben, warum der Residualgraph nötig ist (Sperrfluss-Beispiel mit 4 Knoten aus dem Skript). Ich hab die Frage falsch verstanden und mit dem 4-Knoten-Beispiel die exponentielle Laufzeit bei Kapazität "c" erklärt. Dann hat er mich wieder zurückgelenkt auf den Sperrfluss. | * Herleitung erweiternde Wege und die Aussagen von Ford & Fulkerson (inkl. aller vorangegangener Definitionen zu nützlichen Kanten, Residualgraph, etc.). Hier ging es immer mal wieder zwischen erweiternden Wegen, maximalen Flüssen und minimalen Schnitten hin und her, bis die beiden Aussagen und deren Zusammenhang komplett durchleuchtet waren. Er wollte auch ein Beispiel gezeichnet haben, warum der Residualgraph nötig ist (Sperrfluss-Beispiel mit 4 Knoten aus der Vorlesung). Ich hab die Frage falsch verstanden und mit dem 4-Knoten-Beispiel die exponentielle Laufzeit bei Kapazität "c" erklärt. Dann hat er mich wieder zurückgelenkt auf den Sperrfluss. |
| * Zu Dinic kam gar nicht mal so viel, er ist dann eher auf das Beispiel mit unendlicher Laufzeit (Konstellation mit den Lambdas) abgedriftet. Ich sollte das Beispiel hinzeichnen und erklären, warum das ein Problem ist. Reihenfolge der Fluss-Belegung war nicht wichtig, nur wie das zustande kommt (Geometrische Reihe und Konvergenz!). | * Zu Dinic kam gar nicht mal so viel, er ist dann eher auf das Beispiel mit unendlicher Laufzeit (Konstellation mit den Lambdas) abgedriftet. Ich sollte das Beispiel hinzeichnen und erklären, warum das ein Problem ist. Reihenfolge der Fluss-Belegung war nicht wichtig, nur wie das zustande kommt (Geometrische Reihe und Konvergenz!). |
