TU Wien:Algorithmen auf Graphen VU (Chwatal)/Prüfungsfragen WS08
Zur Navigation springen
Zur Suche springen
Gepostet von duracell im Informatikforum:
Da der Vortragende des dritten Blocks nicht anwesend war, wurde ich auch nur zu den ersten zwei Kapitel befragt. Die Fragen waren:
- Johnson's Algorithmus (welches SP-Problem löst er, Funktionsweise, Beweise!, Erklärung der zugrundeliegenden Algorithmen)
- Dijkstra (Vorraussetzungen, wieso funktioniert Addieren des kleinsten negativen Kantengewichtes nicht?)
- Minimum Cost Flow (wie, wozu, warum, feasible solution / optimal solution => alles!)
Fragen einer anderen Prüfung:
- Dijkstra (Voraussetzungen, warum sind negative Kantengewichte nicht möglich?, warum funktioniert das Addieren des kleinsten negativen Kantengewichts nicht?)
- Minimum Cost Flow (Definition, wie wird eine gültige Lösung gefunden?, Optimalitätskriterium der negativen Zyklen, Algorithmus dazu)
- Nachteile von Ford-Fulkerson (nur pseudopolynomiell)
- Was ist ein m-augmentierender Pfad? Was ist ein Matching?