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.

Link zu der Vergleichsansicht

Nächste Überarbeitung		Vorherige Überarbeitung
pruefungen:hauptstudium:ls12:effi-2018-02 [16.02.2018 08:41] – angelegt christian-depruefungen:hauptstudium:ls12:effi-2018-02 [16.02.2018 08:57] (aktuell) – christian-de
Zeile 5: Zeile 5:
 Bewertung war sehr fair, er hat über ein paar Wackler und eine Verwechslung bei den Flüssen hinweggesehen. Ihm geht es offensichtlich darum, dass zum Schluss die richtigen Erklärungen und Begründungen kommen - Hilfestellung dazu gibt er wenn nötig. Bewertung war sehr fair, er hat über ein paar Wackler und eine Verwechslung bei den Flüssen hinweggesehen. Ihm geht es offensichtlich darum, dass zum Schluss die richtigen Erklärungen und Begründungen kommen - Hilfestellung dazu gibt er wenn nötig.
  
-Ich hatte das "Paket DFS + Flüsse". Sind nur zwei Themen (andere Protokolle haben meistens 3 Themen), dafür wurden sie sehr detailliert besprochen.+Ich hatte das "Paket DFS + Flüsse". Sind nur zwei Themen (in anderen Protokollen waren es meistens drei Themen), dafür wurden sie sehr detailliert besprochen.
  
 **DFS-2ZK**: **DFS-2ZK**:
   * Was haben wir für ungerichtete Graphen kennengelernt, was ist zweifache ZHK, was Artikulationspunkt? Hier haben wir uns durch die Definitionen gehangelt. Wichtig war ihm noch, dass die ZHK maximal ist und was das bedeutet.   * Was haben wir für ungerichtete Graphen kennengelernt, was ist zweifache ZHK, was Artikulationspunkt? Hier haben wir uns durch die Definitionen gehangelt. Wichtig war ihm noch, dass die ZHK maximal ist und was das bedeutet.
-  * Welche Mechanismen benutzt der Algo? dfnr und tief-Funktion inkl. Beispiel auf Papier+  * Welche Mechanismen benutzt der Algo? -> dfnr und tief-Funktion inkl. Beispiel auf Papier
   * Dann ging es noch genauer um Rückkanten und was sie eigentlich tun (Kreis schließen), wo sie auftauchen können und wo nicht (Rücksprung auf Ästen, ...)    * Dann ging es noch genauer um Rückkanten und was sie eigentlich tun (Kreis schließen), wo sie auftauchen können und wo nicht (Rücksprung auf Ästen, ...) 
   * Woran erkennt man Artikulationspunkte und warum ist das zuverlässig?   * Woran erkennt man Artikulationspunkte und warum ist das zuverlässig?
Zeile 17: Zeile 17:
 **Flüsse**: **Flüsse**:
   * 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). 
-  * Unterscheidung: "Fluss vs. Wert des Flusses" +  * 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!).