Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 12 » effi-2017-02 (Übersicht)
no way to compare when less than two revisions
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
— | pruefungen:hauptstudium:ls12:effi-2017-02 [05.04.2017 14:49] (aktuell) – angelegt breakfast | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
+ | DFS: | ||
+ | * Was kann man mit Tiefensuche in ungerichteten Graphen berechnen? | ||
+ | * Woran erkenne ich Artikulationspunkte? | ||
+ | * Warum funktioniert das? | ||
+ | * Warum O(|V|+|E|)? (das V ist hierbei nicht so wichtig) | ||
+ | Fluesse: | ||
+ | * Flussproblem: | ||
+ | * Fluss erklaeren (er fand es nicht gut, dass ich erst erklaeren wollte wie man den Fluss berechnet und dann das Konservierungsgesetz. Sagt das Gesetz vorher ;-)) | ||
+ | * Was war voll der wichtige Begriff? (erweiternder Pfad) | ||
+ | * Was habe ich fuer einen Graphen, wenn ich die Kanten entsprechend in beide Richtungen einzeichne und so? (Residualgraph) | ||
+ | * Warum ist der Fluss maximal, wenn es keinen erweiternden Pfad gibt? (hier ist Schnitt wichtig) | ||
+ | * *malt das Beispiel mit potenziellem O(maximale Kapazitaet) aus der Vorlesung* Hier ist wichtig, dass die Laufzeit exponentiell sein kann. | ||
+ | * Dann kamen wir zu geschichteten Netzwerken. | ||
+ | * Wichtig: Auf dem geschichteten Netzwerk wird der maximale Fluss (des geschichteten Netzwerks) berechnet. | ||
+ | * Warum ist diese Methode mit dem geschichteten Netzwerk geil fuer die Berechnung des maximalen Flusses auf dem urspruenglichen Netzwerk? (ich sagte O(|V|^2 * |E|) ist besser als O(|V| * |E|^2); er wollte hoeren, dass es besser ist als das exponenzielle (und unabh. von Kapazitaeten)) | ||
+ | * Irgendwann hat er auch nach dem integrality theorem gefragt. (beide fanden es ganz lustig, als ich integrity theorem sagte) | ||
+ | |||
+ | Zu den anderen Themen kam tatsaechlich nix. Ich wusste das meiste, brauchte aber teilweise etwas Hilfestellung, |