Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 12 » Mein EffAlg Prüfungsprotokoll - Ein Drama in 2 Akten (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

--- pruefungen:hauptstudium:ls12:effi-2021-04-08-1 [08.04.2021 14:25] – Format stef_15
+++ pruefungen:hauptstudium:ls12:effi-2021-04-08-1 [08.04.2021 14:33] (aktuell) – Format 2.0 stef_15
@@ Zeile 8: / Zeile 8: @@
 explizit danach gefragt hatte ich aber auch nicht.
-Ich habe seit 4 Jahren so viele Tiefensuchen, Suchen von starken
+Ich habe seit 4 Jahren so viele Tiefensuchen, Suchen von starken Zusammenhangskomponenten\\
-Zusammenhangskomponenten und Flussalgos implementiert, ich hätte nicht gedacht das es so schief gehen kann, aber lest selbst!
+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: 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)
@@ Zeile 21: / Zeile 19: @@
 Tiefensuche auf gerichteten Graphen, was ist nontriviale Eigenschaft?
-(Diese Frage liest mal so oft in Prüfungsprotokollen, aber ich habe ehrlich
+(Diese Frage liest mal so oft in Prüfungsprotokollen, aber ich habe ehrlich\\
-immer noch keine Ahnung was man damit erfragen will / worauf man hinauswill)
+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!
+(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.
+War mir leider nicht so bekannt, habe dieses wichtige Informationsdetail wohl verplant.\\
 Also Zukünftiger Prüfling: merk es dir!)
@@ Zeile 31: / Zeile 29: @@
 (Nein! Ein Wald!!!)
-Zusätzlich zu den normalen Kanten sind da noch "gestrichelte" Kanten drin,
+Zusätzlich zu den normalen Kanten sind da noch "gestrichelte" Kanten drin,\\
-Rückwärtskanten, Cross-Kanten und Vorwärtskanten.
+Rückwärtskanten, Cross-Kanten und Vorwärtskanten.\\
+Jedenfalls kann man dann da starke und schwache Zusammenhangskomponenten bilden.\\
-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.\\
-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?
+Was tun tief und dfnr?\\
-(k.A. welche welche ist, ich verwechsel die immer)
+(k.A. welche welche ist, ich verwechsel die immer)\\
+Die eine nummeriert die Besuchsreihenfolge, die andere in welcher Komponente der Knoten ist.\\
-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?\\
-Die Komponentennummer bildet sich über die kleinste über normale Kanten und dann genau eine "gestrichelte" Kante.
+Hatte in dem Moment nur die Cross-Kanten zwischen 2 Bäumen im Kopf.\\
-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).
+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.
@@ Zeile 60: / Zeile 50: @@
 ===== Akt 2: Flussalgorithmen =====
-Was ist die Eingabe eines Flusses?
+Was ist die Eingabe eines Flusses?\\
 -> s, t, G, c
-c bildet (haha Kanten, ich hab die ganze Zeit Knoten und Kanten durcheinander gesagt)
+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.
+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.
+Es wurde nach dem Wichtigsten von Ford und Fulkerson gefragt.\\
+Ich dachte zuerst Flussberechnung an sich, aber ging wohl zuerst zu den\\
-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.
+Dann noch kurz zu der Komplexität vom unmodifizierten Ford-Fulkerson, ist halt exponentiell in c.\\
-Und bei rationalem c sogar unendlich lange Laufzeit.
+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.
+Geschichtetes Netzwerk, welches aus kürzesten Wegen von s nach t besteht.\\
+Welchen kürzesten Weg nimmt man?, ich so: egal, irgendeinen\\
-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...
 ===== Ende :( =====
-Zu dem ganzen Komplexeren, also Parametrisierte Komplexität(haha), Umwandlung in exakten Algo,
+Zu dem ganzen Komplexeren, also Parametrisierte Komplexität(haha), Umwandlung in exakten Algo,\\
-VC, k-SAT, usw sind wir nicht gekommen.
+VC, k-SAT, usw sind wir nicht gekommen.\\
-Also genau die Themen, in die ich die meiste Zeit gesteckt hatte :)
+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.
+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,
+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
+ich hätte auch dort vermutlich einfach zu wenig Beweise und Definitionen\\
 auswendig gekonnt.
-Moral der Geschicht:
+Moral der Geschicht:\\
 lernt die Basics, advanced stuff fragt er sonst eh nicht!
-Ansonsten war EffAlg, ne nette Veranstaltung, die Übungsaufgaben waren gut gestellt.
+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 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
+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
+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
+Prüfungsprotokollen sich auf diese Prüfung vorzubereiten für mich eher wenig\\
 machbar.
 tl;dr: kann man schon mal gemacht haben.