Effiziente Algorithmen

at Universität zu Köln

Join course
278
Discussion
Documents
Flashcards
Macht hier jemand EA im SS 19?
Ich überlege es zu belegen.
im WS19/20.
Hat hier jemand die EA-Klausur vom SS 2018 bei Jünger?
Wenn man beispielsweise beim Phasenschnittalgorithmus den z (min) Graph angeben soll, gibt man den Graph ein nachdem man geschrumpft hat oder den vorherigen?
muss das für die Kanten in G oder die Kanten im Residualgraphen getestet werden?
Im Residualgraphen, denn der Fluss ist minimal genau dann wenn es im Residualgraphen keinen gerichteten negativen Kreis gibt. Und das ist genau dann der Fall wenn es ein zulässiges Potential gibt.
danke dir
Kann jemand erklären, wie man im Blütenschrumpfalgorithmus für allg. Graphen die Y -Variablen (also die für ungerade Schnitte) für das duale Problem bestimmt? Die y Werte hat man ja immer an den Knoten stehen, aber die groß Y Werte sind mir ein Rätsel..
Wenn man die Optimalität von x nicht mit dem kompl. Schlupf, sondern mit dem starken Dualitätssatz beweisen sollte, kann man dann auch sagen, dass als Bsp. y3=0 ist, weil die 3 Gleichung bei der Überprüfung mit x nicht bindend ist, weil sie nicht mit Gleichheit erfüllt ist?
Wenn man beim Netzwerk Simplex Algorithmus das y v also die Kosten pro Knoten ab Startknoten r berechnet, darf man Rückwärtskanten nehmen, sprich man nutzt den Residualgraphen. Frage ist: Warum darf man bei Minimum Kosten Flüssen nicht den Residualgraphen nutzen, wenn man die Knotenpotenziale berechnet pro Knoten, um zu beweisen, dass es keinen negativen kreis gibt, weil alle Knotenpotentiale zulässig sind?
Im Netzwerk-Simplex-Algo. arbeitet man ja immer mit einer Baumlösung, d.h. man hat einen Baum T und das y_v steht dann für die Kosten des eindeutigen r-v-Wegs in T. Das ist also ein zulässiges Potential aber eben nur auf T, und da kann es ja gar keine Kreise geben, also auch keine negativen.
Danke :)
Was ist der Unterschied zwischen Fords und Ford Bellmann Algorithmus?
View 2 more comments
Habe noch ein Frage zum Ford Algorithmus. Man hat eine feste Reihenfolge und durchgeht diese Reihenfolge. Wie oft macht man dies? Bis sich nichts mehr ändert? Was ist wenn man die Reihenfolge z.n. ba hat. b steht auf unendlich weil es noch nicht besucht ist. die Kante ba hat kosten noch -4. und A hat ein Knotenpotential von z.b. 5. Wie würde man dann unendlich minus 4 rechnen? Würde sich das Knotenpotential von A ändern oder konnte man die Kante nicht gehen, weil der Knoten noch nicht besucht wurde. Vielen Dank
Wenn sich nichts mehr ändert, heißt das ja, dass für alle Kanten, die Bedingungen für ein zul. Potential erfüllt sind, du hast also ein zul. Potential gefunden und damit endet die while Schleife. Also ja, wenn sich nicht mehr ändert, kannst du aufhören. Wenn du in deinem Beispiel der festen Reihenfolge folgst und dein aktueller Knoten b hat Potential unendlich, dann kannst du den eigentlich gleich überspringen, weil unendlich +/- irgendwas bleibt unendlich, das potential der anderen knoten ändert sich nicht
Wenn man im bipartiten Graph mit einem Maximum Fluss Algorithmus das maximale Matching berechnen soll, bekommen dann die Kanten wo drüber ein Fluss gelaufen ist eine Matching Kante?
View 2 more comments
Wenn du das Max-Fluss-Problem im bipartiten Graphen löst, indem du Quelle und Senke hinzufügst und den Kanten im ursprünglichen Graph Kapazität 1 gibst, entsprechen die Kanten, auf denen Fluss fließt, den Matchingkanten im Ursprungsgraphen
Vielen Dank :)
Wie geht es weiter, wenn ich im Blütenschrumpfalgorithmus für Min. Kosten Matching im allg. Graphen alle Knoten im aktuellen T zu einem Pseudoknoten geschrumpft habe? (also z.B. wenn T aus nur 3 Knoten besteht und Wurzel und der 3. Knoten durch Gleichheitskante verbunden sind). Ist dann der Pseudoknoten die neue Wurzel oder suche ich eine neue?
Wie findet man in einem bipartiten Graph die Knotenüberdeckung raus?
Nimmt man beim Netzwerk Simplex Algorithmus (wenn man die Kante mit den negativen Kosten gefunden hat) die erste Rückwärtskante als h oder die geringste?
Man sucht ja das θ = min{x_j | j Rückwärtskante in C(T,e)} - dein h ist quasi das j, welches du mit dem Minimum findest. Also die Rückwärtskante mit dem geringsten Fluss.
Danke :)
das müsste doch eine 5 sein, richtig?
View 1 more comment
Die acht müsste eine fünf sein. Das war die Frage ?
Achso, die Markierung war auf dem Buchstaben :D ja klar, du hast Recht, in diesem Schritt ist der Nettofluss bei s 5.
Hallo zusammen, wer hat die Tage vielleicht Zeit und kann Nachhilfe in Effiziente Algorithmen geben? Vorallem die Themen Blütenschrumpf, und Matching. Ich wäre auch bereit dafür zu zahlen. Ich würde mich freuen. Also vielleicht am Tag 1-2 Stunden :)
Ich verstehe hier bei der Aufgabe 2 nicht, wie ich den Netzwerk-Simplex-Algorithmus anwenden soll.. Es muss doch auf den Kanten ein Fluss gegeben sein..? Übersehe ich etwas? Kann mir jemand erklären wie man den Algo hier anwendet..? Danke!
den fluss kannst du selber bestimmen, indem du schaust das die flussbedingungen nach bestimmung des flusses erhalten bleiben (sprich das was rein geht, muss auch rausgehen). wenn du dann noch darauf achtest, dass auf nicht baumkanten kein fluss fliest, kannst du quasi rückwärts von knoten (a) aus beginnen fluss fließen zu lassen. bei (a) ist es nämlich eindeutig, da der fluss hier zunächst nur von knoten (r) aus fließt und daher 1 sein muss
No area was marked for this question
Das ist willkürlich, du musst die quasi "geschickt" wählen. Es gibt hier aber mehrere Möglichkeiten die alle zu v(G) ≤ 5 führe
danke dir
weiß jemand wie ich hier auf die menge der A knoten komme? bzw. wie diese zu wählen sind? passiert das mit dem blütenschrumpf algorithmus für maximales matching?
ich habe das jetzt mal mit dem blütenschrumpf-algorithmus für maximales matching durchgespielt und komme auf die A knoten wie in der lösung. kann ich nur empfehlen das ganze, ist eine gute übung um zu schauen, ob das den algorithmus wirklich verstanden hat
No area was marked for this question
Aufgabe 2) Meiner Meinung nach birgt die Kante bh noch eine Kostenreduktion von -1 ? aktuelle Kosten: 11, über b: 10?
View 4 more comments
Deine Kante bh ist falsch rum, schau mal auf dem Aufgabenblatt nach ;) Die Richtung ist hb. Und dann gibt es noch keine Rückwärtskante bh, weil es auf hb keinen Fluss gibt.
so schnell kann's gehen, danke dir :)
Muss natürlich -1 sein, wie auch im nächsten Schritt wieder korrekt weitergemacht.
Hier muss (u_e, x_e) stehen!! Beim Beispiel zu Korollar 3.4 auch, irgendwie hab ich das falschrum aufgeschrieben. Macht ja auch keinen Sinn, wenn man sich das anschaut, dass dort mehr drüber fließt als es Kapazität gibt.
wieso ist a=0 und c=4 ?
Das sind die Potenziale, also ya und yc bzgl. a
Das hier, was unter der Summe aussieht wie ein e Element S ist eigentlich ein e Element Delta (das Delta sieht hier wie ein S aus). Nur um Verwirrung zu vermeiden
Das hier muss eine -1 sein, die Kante 5 ist ja "eingehend" am Knoten d.
hat einer von euch vllt die lösung von dem übungsblatt 6.Das wäre echt nett☺
Hat zufällig einer die Klausur vom Ersttermin und kann die bitte hier hochladen?
aufgabe 1, ganz klassisch x* mit hilfte von kompl. schlupf beweisen (siehe übung 3 aufg.1) Aufgabe 2: ein minimaleKostenFlussproblem (primal) gegeben -> Dualisieren Aufgabe 3: Ford-Bellmann Algo ausführen 3b) irgendnen kleiner beweis mit potential und neg. kreis Aufgabe 4: a) Wann terminiert goldberg-tarjan b) wie viele relabel operationen führt goldberg,tarjan aus -> BEgründe c) Goldberg tarjan für aktuellen knoten x ausführen, bis inaktiv Aufgabe 5 MinKostFlüsse gegeben, beweise oder wiederlege ob Fluss a und b optimal Aufgabe 6a) das Spiel mit perf Maschine aus der VL beweisen aufgabe 6b) gebe für minKostMatching mit blütenschrumpf algo eine zulässige lösung y an über duales Programm copy+paste aus der WhatsApp Gruppe
Dankeschön
Und das hier durchgestrichen. "Es existiert KEIN"
Das hier muss y1 - y2 sein, sonst ergibt die Ersetzung mit y Tilde keinen Sinn.
Dass das hier 8 sein muss, sieht hoffentlich jeder - trotzdem die Anmerkung der Vollständigkeit halber.
Hier muss natürlich x Element aus dem R hoch n (nicht m) stehen, sorry!
Das hier muss natürlich (wie auch im Appendix A des Lehrbuchs nachzulesen) y Transformiert klein b = - 1 heißen.
No area was marked for this question
Hallo :) Kann mir jemand erklären, wo die 8 (Knoten r, Initialisierung) herkommt? Bzw was generell in der linken Zahl passiert?
Wenn ich mich richtig erinnere (ist 1 Jahr her und hab das noch nicht im Detail angeschaut) kommt da ne 8 hin, weil es insgesamt 8 Knoten sind. Die linke Zahl (ich glaube "Distanz") wird so lange erhöht (relabel), bis man auf einen Knoten pushen kann, wo die lnike Zahle geringer ist. Deswegen ist Schritt 1 relabel(a) (-> linke Zahl ist 1) und dann erst push(a,d).
Genau, das label von r ist stehts die Anzahl der Knoten im Netzwerk. In der Vorlesung ist der Überschuss von r die Summe der Flüssen, die r an seinen Nachbarn schickt (hier wäre also -13). In der Übung ist der Überschuss von r aber 0. Wurde gesagt warum? Bzw. welche Version wir nutzen sollen?
Hallo Wo erhalte ich das elektronische Skript von der Vorlesung?? LG
View 1 more comment
Hey ja aber das sind nur die Notizen oder ? Habe bei manchen Kommilitonen ein Skript gesehen, welches identisch zu den Aufzeichnungen und Folien von Herr Jünger war.
Ja das sind die Vrolesungsnotizen. Die Mitschrift von allem anderen lade ich ja hier hoch. Wo es ein komplettes Skript geben soll, ist mir nicht bekannt, evtl. aus früheren Semestern von anderen Studis... ;)
Hier fehlt die Kante b-g oder?
das habe ich mir auch gedacht O.o
Kleiner Hinweis: Von der Vorlesung am 20.06. gibt es keine Mitschrift, da der Prof hier ausnahmsweise ein Skript hatte. (Das findet ihr im entsprechenden Ilias Kurs)
No area was marked for this question
Hey, ist es korrekt, dass die Vorlesung auf Seite 5 endet oder ist etwas schief gelaufen beim Upload? Danke schonmal :)
Hi, ja das ist korrekt so, ich hab immer ein 8 Seiten Dokument. Meistens wird das auch voll nur diesmal nicht - und ich hab vergessen die leeren Seiten wieder zu entfernen ;)
Perfekt, danke für die schnelle Antwort (und natürlich deine Mitschriften)!
Was soll das bedeuten?
Das ist einfach nur die grafische Erklärung warum ein Graph mit Kreis nicht optimal sein kann: Die Kante hat ein Gewicht größer gleich null, und wenn der Kreis aufgelöst wird, der Graph aber immer noch ein aufspannender Baum ist bzw. zusammenhängend ist, dann muss er besser sein.
Hier ist die WhatsApp Gruppe für das aktuelle Semester (SS18) Effiziente Algorithmen bei Prof. Jünger: https://chat.whatsapp.com/FHBxD1DNWkQJEUxZFLuHB0