Mein EffAlg Prüfungsprotokoll - Ein Drama in 2 Akten

oder auch: wie ich meine 1. mündliche Prüfung seit 2 Jahren hoffnungslos in den Sand setzte :)

Note: leider nicht nicht bestanden.

Wohl so hoffnungslos, dass mir ein Nicht-Bestehen nicht angeboten wurde, explizit danach gefragt hatte ich aber auch nicht.

Ich habe seit 4 Jahren so viele Tiefensuchen, Suchen von starken Zusammenhangskomponenten
und Flussalgos implementiert, ich hätte nicht gedacht das es so schief gehen kann, aber lest selbst!

(Vorsicht: mein Hirn ist etwas löchrig, Teile könnten fehlen)
(Vorsicht: diese Prüfung ist kein positives Beispiel, für einen angehenden Komb. Alg. Profi könnte es weh tun)
(Vorsicht: ich bin echt schlecht darin, gut lesbare Protokolle zu schreiben)

Tiefensuche auf gerichteten Graphen, was ist nontriviale Eigenschaft?

(Diese Frage liest mal so oft in Prüfungsprotokollen, aber ich habe ehrlich
immer noch keine Ahnung was man damit erfragen will / worauf man hinaus will)

(frei nach O-Ton Wanka: es sollte doch mittlerweile bekannt sein, dass ich immer mit Tiefensuche anfange!
War mir leider nicht so bekannt, habe dieses wichtige Informationsdetail wohl verplant.
Also Zukünftiger Prüfling: merk es dir!)

Nach der Tiefensuche kommt ein Baum raus. Ein Baum? (Nein! Ein Wald!!!)

Zusätzlich zu den normalen Kanten sind da noch „gestrichelte“ Kanten drin,
Rückwärtskanten, Cross-Kanten und Vorwärtskanten.
Jedenfalls kann man dann da starke und schwache Zusammenhangskomponenten bilden.
Habe die über Wege in beide Richtungen für alle zu allen Knoten, bzw einem zu allen Knoten definiert.
Und was fehlt da noch? Ich hab die Maximalität vergessen…

Was tun tief und dfnr?
(k.A. welche welche ist, ich verwechsel die immer)
Die eine nummeriert die Besuchsreihenfolge, die andere in welcher Komponente der Knoten ist.
Die Komponentennummer bildet sich über die kleinste über normale Kanten und dann genau eine „gestrichelte“ Kante.
Rückkanten sind richtig, aber welche Cross-Kanten nimmt man?
Hatte in dem Moment nur die Cross-Kanten zwischen 2 Bäumen im Kopf.

Und bin dann nicht auf die zwischen 2 Ästen gekommen, die dann in der gleichen
starken Zhg sein sollen (zum Zeitpunkt dieses Protokolls bin ich immer noch verwirrt).
hab deswegen „gar keine“ gesagt.

an der Stelle hat Wanka dann abgebrochen und wir sind zu Flüssen gewandert.

Was ist die Eingabe eines Flusses?
→ s, t, G, c

c bildet (haha Kanten, ich hab die ganze Zeit Knoten und Kanten durcheinander gesagt)
Kanten auf N ab, Wanka so: nein, in der Vorlesung sogar auf R+.

Dann formale Definition eines Flusses, was ist der Wert eines Flusses.
Was ist ein Schnitt.

Es wurde nach dem Wichtigsten von Ford und Fulkerson gefragt.
Ich dachte zuerst Flussberechnung an sich, aber ging wohl zuerst zu den
erweiternden Wegen und Residualgraphen.

Und irgendwo hab ich gleich schon das Min-Cut-Max-Flow Theorem in den Raum geworfen.

Dann noch kurz zu der Komplexität vom unmodifizierten Ford-Fulkerson, ist halt exponentiell in c.
Und bei rationalem c sogar unendlich lange Laufzeit (was mir Wanka gesagt hat, ich habs vergessen).

Dann zu Dinic, und was das besser macht.

Geschichtetes Netzwerk, welches aus kürzesten Wegen von s nach t besteht.
Welchen kürzesten Weg nimmt man?, ich so: egal, irgendeinen
(haha, bei Dinic nimmt man ja alle kürzesten Wege)

dann noch ein bisschen Zusammenhang mit Schnitten und so ich erspare dem Leser hier mal den Rest…

Zu dem ganzen Komplexeren, also Parametrisierte Komplexität(haha), Umwandlung in exakten Algo,
VC, k-SAT, usw sind wir nicht gekommen.
Also genau die Themen, in die ich die meiste Zeit gesteckt hatte :)
Mehr Zeit hätten die ganzen Basics, aber in ihrer formalen Form abbekommen sollen.

Ob die Prüfung bei den anderen Themen besser verlaufen wäre? Vermutlich nicht,
ich hätte auch dort vermutlich einfach zu wenig Beweise und Definitionen
auswendig gekonnt.

Moral der Geschicht:
lernt die Basics, advanced stuff fragt er sonst eh nicht!

Ansonsten war EffAlg, ne nette Veranstaltung, die Übungsaufgaben waren gut gestellt.
Die Aufzeichnung der Vorlesung aus 2016 (siehe video.cs.fau.de) auch sehr gut,
die im WS20/21 gehaltene Vorlesung hab ich nicht besuchen können, weil ich in
diesem Slot selbst eine Übung halten musste.

Aber sich allein, ohne eine Lerngruppe von der man leechen kann, aus
Prüfungsprotokollen sich auf diese Prüfung vorzubereiten für mich eher wenig
machbar.

tl;dr: kann man schon mal gemacht haben.