| Datum: | 22.4.99 | |
|---|---|---|
| Prüfer: | Mayr | |
| Name: | Stefan Dirnstorfer | |
| Fächer: | Effiziente Algorithmen I (Mayr) | |
| Effiziente Algorithmen II (Mayr) | ||
| Graphische Datenverarbeitung (Zenger) | ||
| Rekursive Verfahren (Zenger) | ||
| Logik (Esparza) |
| Algorithmen I: | |
| Mayr: | Was ist ein minimaler Spannbaum? |
| Ich: | Nachdem ich mich hier etwas verheddert hatte, bohrte Herr Mayr so lange nach, "Wieviele Kanten? In welchen Graphen?...", bis er mir glaubte, dass ich doch wusste worum es ging. Die richtige Antwort wäre gewesen: "Zyklenfreier Teilgraph der alle Knoten verbindet". |
| Mayr: | Wie berechnet man ihn? |
| Ich: | Mit Prim oder mit Kruskal. |
| Mayr: | Wie funktioniert die Union-Find Struktur? |
| Ich: | Baum mit Pfadkompression. (Prof. Mayr wies darauf hin, daß letztere bei Kruskal nicht notwendig sei, da der Baum max log(n) hoch wird und die Komplexität sowieso vom Sortieren dominiert wird.) |
| Algorithmen II: | |
| Mayr: | Was ist ein Matching? Wie berechnet man es? |
| Ich: | Teilgraph mit knotendisjunkten Kanten. Alternierende/Augmentierende Pfade. Hopford & Carp für bipartite Graphen. |
| Mayr: | Wie löst man Flußprobleme? |
| Ich: | Dinic: Residuennetzwerk. BFS zum finden des kürzensten
augmentierenden Pfades, DFS zum Finden blockierender Flüsse. Push/Relabel: Labelfunktion ist Schranke für den Abstand zur Senke. Überfluß wird zu Knoten mit kleineren Labeln "gepushed". |
| Logik: | |
| Mayr: | Was hat den der Esparza so gemacht? |
| Ich: | Aussagen Logik, Prädikaten Logik, Kalküle. |
| Mayr: | Vollständigkeit? Korrektheit? Endlichkeitssatz? Tautologie? |
| Mayr: | "A, A -> B => B" Was ist das? |
| Ich: | Modus Ponens. |
| Rekursive Verfahren: | |
| Mayr: | Was haben Sie da eigentlich gemacht? |
| Ich: | Ich habe erzählt was mir so eingefallen ist. Irgendwann hat dann Herr Mayr gemeint, daß er das schon mal ein einer Habilitationsschrift gelesen hätte und es darauf beruhen lassen. |
| Graphische Datenverarbeitung: | |
| Mayr: | Farbmodelle? |
| Ich: | Additiv, Subtraktiv, HSV |
| Mayr: | Was macht mit Kanten? |
| Ich: | Gaurand: Farbinterpolation, Phong: Normaleninterpolation. |
| Mayr: | Kann man bei Vierecken linear interpolieren? |
| Ich: | Habe ihm Bilineare Interpolation erklärt. Er wollte aber einfach nur "Nein" hören. |
Das war die mit Abstand angenehmste Athmosphäre, in der ich je geprüft worden bin. Zu Beginn wurde mir erst mal eine Tasse Kaffee angeboten, wozu ich allerdings keinen Nerv hatte. Herr Mayr stellte klar und nicht zu schwierige Fragen, erwartet aber auch klare Antworten;-). Er verzichtete schließlich darauf mir meine Note mitzuteilen, sagte aber, dass es eine "glatte" Note sei.