Fachrat Informatik - Forum

Aus meiner Sicht waren die Schwerpunkte bei den Definitionen (Matchings, Färbung, Flussnetze, usw in der Reihenfolge), wo man welche Algorithmen anwenden kann und wie diese grob funktionieren. Sehr wichtig war bei allen Algorithmen die Laufzeit, den Pseudocode selbst musste ich zum Glück jedoch nur für List-Ranking aufschreiben. Habe aber gehört, dass andere da mehr Algorithmen aufschreiben mussten, wenn sie deren Laufzeit nicht richtig verstanden hatten.
Interessant war noch die Frage, wie man die exponentielle Laufzeit von Ford-Fulkerson (Flussnetzwerke) wegbekommt. Da musste ich erklären, warum diese Ansätze im Skript wirklich funktionieren und ein Beispiel geben, darauf war ich erst durch einen Tip vom Vorprüfling vorbereitet.
Beweise waren unwichtig, bis auf die, die in der Prüfungsankündigung erwähnt wurden - die beiden Färbungsbeweise wurden bei mir abgefragt, ich musste die Beweisidee skizzieren.
Graphen und parallele Algorithmen wurden bei mir gleichermaßen abgefragt und insgesamt ging es eher in die Breite. Das war bei mir aber bisher bei allen mündlichen Prüfungen so.
Notenabzüge waren fair, dh wenn man eine Frage selbst mit Tipps nicht hinkriegte, oder ein Thema gar nicht konnte, gab es schon Abzüge, aber nicht wegen (weniger) Kleinigkeiten.

Da gab es drei Möglichkeiten laut Skript, z.B. immer blockierende Pfade wählen. Aber da gab es auch wieder Sonderfälle, die nicht klappen und ich wusste in der Prüfung, als wir darüber sprachen, auch nicht so recht weiter. War aber auch nicht so schlimm, das wurde auch nicht erwartet.

So, auch grad Prüfung gehabt.

Quoted

Exponentielle Laufzeit: Kurze augmenting paths wählen, oder? *kopfkratz

Genau, entweder einen kürzesten (Edmonds-Karp) oder mehrere kürzeste bzw. einen "blockierenden Fluss" (Dinic). Ansonsten stand in den Folien noch, dass man immer nur einen Pfad mit einer bestimmten sinnvollen Mindestkapazität wählen könnte, ohne spezifisch zu sagen, was das Minimum sein sollte. Tiefer gehende Details oder Beispiele musste ich aber nicht wissen.

Pseudocode musste ich zum Glück gar nicht aufschreiben, da es Arne gereicht hat, dass ich die Arbeitsweise der Algorithmen erklären konnte. Prinzipiell ging es am Anfang einmal durch alle Graphenalgorithmen: BFS, DJP, BF, FW, FF: was machen die, wieso braucht man sie, welche Laufzeit haben sie und wie kommt die zustande? Ein Beispiel sollte ich für ein anderes Problem konstruieren: wieso kann man bei negativen Gewichten nicht einfach auf alle Kanten eine Konstante addieren und dann DJP anwenden? Zur Färbbarkeit kam nur die Frage nach dem Satz von Kuratowski und Wagner und was ein Minor ist.

Parallele Algorithmen kamen bei mir etwas kurz, vermutlich weil ich vorher etwas getrödelt habe. Da kamen hauptsächlich grundlegende Fragen: Was ist eine PRAM, was unterscheidet die Typen, wie regelt man Schreibzugriffe bei CRCW-PRAMS? Was sind Kosten und wann ist etwas optimal? An Algorithmen kamen nur die binären Bäume am Beispiel der Summierung von n Zahlen, die Laufzeit und Optimalität, und wie man es besser machen könnte, und wieso es dann optimal ist. Dann noch die Laufzeit und Optimalität von compCC, und dann war die Prüfung auch schon vorbei.

Das was nano zur Bewertung gesagt hat kann ich im Prinzip bestätigen. Ich hatte am Anfang auch das Gefühl, ziemlich versagt zu haben, weil ich die Laufzeiten des BFS-Algorithmus für verschiedene Datenstrukturen erst hingekriegt habe, nachdem Arne mich gebeten hat, den Algorithmus nochmal zu erklären. Auch bei anderen Laufzeiten hab ich sehr stockend geantwortet, das Beispiel zu konstruieren hat ziemlich lange gedauert und beim Beheben der exponentiellen Laufzeit hab ich zu Anfang mit Mindestkapazität und -fluss verhaspelt. Aber offenbar gab es dafür am Ende keine Abzüge.