Network Flows VI

Video thumbnail (Frame 0) Video thumbnail (Frame 14991) Video thumbnail (Frame 17512) Video thumbnail (Frame 20472) Video thumbnail (Frame 22982) Video thumbnail (Frame 32152) Video thumbnail (Frame 39753) Video thumbnail (Frame 41572) Video thumbnail (Frame 49166) Video thumbnail (Frame 62481) Video thumbnail (Frame 66801) Video thumbnail (Frame 78384) Video thumbnail (Frame 80309) Video thumbnail (Frame 82099) Video thumbnail (Frame 89384) Video thumbnail (Frame 92952) Video thumbnail (Frame 97016) Video thumbnail (Frame 104079) Video thumbnail (Frame 108586) Video thumbnail (Frame 113939) Video thumbnail (Frame 123961)
Video in TIB AV-Portal: Network Flows VI

Formal Metadata

Title
Network Flows VI
Title of Series
Part Number
13
Number of Parts
15
Author
License
CC Attribution - ShareAlike 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this license.
Identifiers
Publisher
Release Date
2012
Language
German

Content Metadata

Subject Area
Abstract
Auf Basis analytischer Sachverhalte entwickeln wir algorithmische Ideen für Verfahren auf Graphen. Daraus entstehen zunächst generische Verfahren, welche formal bezüglich ihrer Korrektheit und Laufzeit analysiert werden. Im Anschluss daran werden in jedem Kapitel Techniken zur Verbesserung und Beschleunigung vorgestellt. Abgerundet wird der Stoffplan durch zahlreiche Modellierungs- und Anwendungsbeispiele und der (optionalen) Implementierung eines Benchmarks verschiedener algorithmischer Varianten.
Loading...
Kante Series (mathematics) Zahl Decision tree learning Direction (geometry) Moment (mathematics) Maxima and minima Set (mathematics) Kapazität <Mathematik> Theory Number Chain Mechanism design Film editing Plane (geometry) Uniformer Raum Function (mathematics) Vertex (graph theory) Length Integer Maß <Mathematik> Flux Directed graph
Iteration Höhe Function (mathematics) Graph (mathematics) Vector space Maxima and minima Vertex (graph theory) Mathematical analysis Integer Maß <Mathematik> Arc (geometry) Directed graph
Sign (mathematics) Eigenvalues and eigenvectors Desire path Mathematical analysis Directed graph
Kante Sign (mathematics) Operations research Decision tree learning Direction (geometry) Square Mathematical analysis Directed graph
Metre Operations research Graph (mathematics) Laufzeit Maxima and minima Feasibility study Square Mathematical analysis Set (mathematics) Vector potential Discrete element method Sign (mathematics) Iteration Function (mathematics) Vector space Iteration Vertex (graph theory) Summation Integer Arc (geometry) Maß <Mathematik> Directed graph Proof theory
Kante Operations research Decision tree learning Höhe Square Mathematical analysis Function (mathematics) Vector potential Exploratory data analysis Function (mathematics) Scalar potential Iteration Summation Abschätzung Proof theory
Operations research Function (mathematics) Maxima and minima Correlation and dependence Iteration Mathematical analysis Vector potential Directed graph Proof theory
Zahl Decision tree learning Graph (mathematics) Maxima and minima Mathematical analysis Vector potential Order of magnitude Iteration Phase transition Vector space Vertex (graph theory) Summation Arc (geometry) Maß <Mathematik> Directed graph Proof theory Operations research Series (mathematics) Laufzeit Feasibility study Square Sign (mathematics) Mathematics Function (mathematics) Lie group Abschätzung Integer
Kante Zahl Höhe Maximum (disambiguation) Square Mathematical analysis Equation Vector potential Order of magnitude Phase transition Function (mathematics) Military operation Military operation Summation Length Factorization Proof theory
Phase transition Scaling (geometry) Algebraic structure Mathematical analysis Proof theory
Stress (mechanics) Höhe Scaling (geometry) Interior (topology) Maxima and minima Kapazität <Mathematik> Parameter (computer programming) Order of magnitude Physical quantity Film editing Military operation Function (mathematics) Strategy game Iteration Integer Vertex (graph theory) Integer Maß <Mathematik> Directed graph
Scaling (geometry) Function (mathematics) Interior (topology) Maxima and minima Condition number Mathematical analysis Vertex (graph theory) Abschätzung Integer Maß <Mathematik> Directed graph Maß <Mathematik>
Mathematics Logarithm Scaling (geometry) Phase transition Condition number Square Mathematical analysis Maß <Mathematik>
Greatest element Link (knot theory) Scaling (geometry) Maxima and minima Mathematical analysis Function (mathematics) Vector potential Physical quantity Mathematics Natural number Phase transition Military operation Number theory Vertex (graph theory) Summation Length Maß <Mathematik> Directed graph Proof theory Logarithm Interior (topology) Square Set (mathematics) Function (mathematics) Quotient Integer Factorization
Decision tree learning Scaling (geometry) Maxima and minima Mathematical analysis Vector potential Number Phase transition Military operation Function (mathematics) Lie group Maß <Mathematik> Maß <Mathematik> Proof theory
Shortest path problem Decision tree learning Scaling (geometry) Interior (topology) Maxima and minima Mathematical analysis Vector potential Chain Military operation Phase transition Function (mathematics) Network topology Condition number Vertex (graph theory) Musical ensemble Integer Maß <Mathematik> Factorization Directed graph Proof theory
Metre Operations research Zahl Numerisches Gitter Scaling (geometry) Laufzeit Maxima and minima Price index Square Mathematical analysis Kapazität <Mathematik> Vector potential Professional network service Order of magnitude Phase transition Military operation Function (mathematics) Cloning Greatest common divisor Maß <Mathematik> Proof theory
Sign (mathematics) Operations research Residual (numerical analysis) Film editing Ende <Graphentheorie> Heuristic Maxima and minima Energy level Vertex (graph theory) Arc (geometry) Grothendieck topology Mach's principle
Operations research Zahl Maxima and minima Distance Film editing Phase transition Ecke Heuristic Energy level Set theory Heuristic Vertex (graph theory) Length Proof theory
Film editing Langsam wachsende Funktion Link (knot theory) Zusammenhang <Mathematik> Heuristic Cloning Heuristic Professional network service Flux
so genau in die Wohnung der immer so sein Nachbarn für den hat er ihn an der TU Darmstadt so
andererseits sehe kann diesen Algorithmus zum letzten Mal eine andere der Vorgehensweise als wir sie vorher betrachtet haben dasselbe Problem maximale Flüsse zu lösen hier ist das habe ich jetzt mal auch zum wiederholten Mal gesagt wir sind vielleicht nicht so schnell wie die wie andere Dozenten mit derselben Vorlesung hier was dann natürlich dazu führt dass die gewusst sich entsprechend nach hinten aus verschiedenen versteht sich aber mir geht es darum dass Sie die Dinge wirklich diese die Konzepte wirklich richtig verstehen denn das ist es was man sinnvollerweise aus einer Vorlesung effizienter Grafen Algorithmen mit hinaus man kann die Ideen die dahinter stehen seien wir ehrlich wenn sie nicht später später nach an der Uni in meine Richtung irgendwie weitergehen denn wenn sie mit diesen speziellen Algorithmen auch mit denen die wie er vielleicht dieses Mal hier nicht schaffen werden ehe nicht wieder in Kontakt kommen aber was sie an Ideen an Konzepten gesehen haben das wird das wird hoffentlich vom bleiben wert sein ich denke auch dass ich wahrscheinlich im nächsten Jahr diese 2 ständige Vorlesung zu einer dreistündigen machen kann damit sogar so langsam mal wie ich das schafft diesen ganzen Stoff durchzuziehen so worum geht es hier die die die der der Grundgedanke oder das Bild was man vielleicht vor Augen haben sollte ist das schon zu jedem Zeitpunkt wenn sie sich als das allzu Schnappschuss vorstellen gibt es so etwas wie ein Ausfluss aus aus es hinaus das jeder Einheit Fluss dessen ganze Menge einer Fluss aus es hinausgehen die dann irgendwo im Moment gerade versickern irgendwo mittendrin zum Teil vielleicht sogar schon bis die angekommen sind ansonsten irgendwo mittendrin sich aufstauen Exzess Überschuss produziert an diesen Knoten Fluss geht rein aber geht nicht weiter daraus erzeugen so und so was wie den Druck und wir wollen schrittweise wie sind Überschuss immer so viel wie möglich Überschuss von den momentan aktiven Kloten Überschuss haben immer weiter voranbringen mit der Zielsetzung möglichst viele nach T zu zu kriegen und das was wir aus dir heraus gedrückt haben aber nicht auf die Reihe kriegen wir hier irgendwo Schnitte sind deren Kapazität kleiner ist als das was wir ausdrücken können unmittelbar bei ist da das das dann so nach und nach wieder danach es zurück gewandert so dass am Ende alle Überschüsse an zwischen Knoten beseitigt sind nur noch es es geht oder Fluss aus es raus in der Nacht herein und weil die invariante immer ist dass es zu jedem Zeitpunkt einen Schnitt gibt von erst nach die der vollständig saturiert ist nun definitiv nix mehr rüber gehen kann davon ist er das Hotel Seite das hat wissen wir wenn am Ende ein zulässiger Fluss entstanden ist und auch die Haltungsbedingungen erfüllt ist Kapazitäten sowieso übererfüllt dann ist es auf jeden Fall maximal Fluss und auch am Ende immer noch 1 Einschnitt sollte wird ist und wir sie kennen das misslungen Charts Theorien die der Fluss wird 1 1 maximal ist gleich gehe die Kapazität eines minimalen schnell dass die minimal Kapazität und ob so und das Ganze wird gesteuert durch diese ominösen validen Nebels dass das Labels das mit dieser Bedingung das wenn Sie eine Kante andersrum nicht so rum wenn Sie eine kann bevor wir haben über diesen Fluss überschütten können ja vor könnte wo noch wo noch restlos möglich ist noch Kapazität übrig ist oder eine rückwärts oder Bekannte rückwärts wo wo positiver Fluss drauf ist denn sie wieder weg gehen können wenn Sie so eine sehr gering haben was sie falls Sie was wir schon bei der kürzesten bei mit somit Christen wegen kennen gelernt haben dass Ihnen das dann tatsächlich diese Steuerung ohne ohne Kontrolle oder wirklich bewusst bewusste bewusst Einflussnahme dass ihn das diese Steuerung ermöglicht dass der Fluss wenn es geht bis T geht und wenn es nicht bis T gilt das dann wieder ich will nochmal ganz genau herausarbeiten was den Scheitelpunkt ist den wir uns da werden Sie die entscheidende Idee wenn Sie eine Fahrt haben er von irgendwo nach irgendwohin Jahr von X nach Y und dieser Fahrt habe K könnten Goldene Zahl wir wissen von dank VW da W IV und V kleiner gleich ich hoffe ich habe das jetzt richtig gemacht und ich habe das hier doch Forschung gemacht also die von V kleiner gleich die von plus 1 so rum war die magische Formel die von Frau Sgrena gleich die von wie plus 1 und wenn Sie das über den ganzen Tag hinweg hernehmen dann ergibt sich sofort das von X kleiner gleich die von y Glos K sein muss ja einfach einfach über geredet und da K kleiner gleich allen ist ja einen fahrt und Bezirke ach ein die sogar kleiner gleich im Minus 1 ich zu ich kleiner Engel da K kleiner in sein muss wissen Sie dass diese lebe und wenn es einen auch wenn es einen Fluss in Fahrt von X nach Y geht ist diese bleibe höchstens auseinander sein können also dieses Label kann höchstens minus 1 Zähler höher sein als dieses Label die das ist entscheidend wichtig in der Argumentation Weise wenn diese beiden Labels mehr also einer sind mindestens N dann gibt es keinen Fluss erhöhen und hat mehr da schließt sich der Kreis an dieser Stelle wenn sie wissen dass dieses Leben hier größer als er ist und das Leben von T weil man wohl dann wissen Sie es gibt keine für seine Fahrt mehr von diesem Knoten machte sie wissen alles was sie hier ein Überschuss haben das geht das muss nach S zurückgeschossen werden und das geht auch weil das Leben von es ist allen hat die hören und irgendwann durch ihre Länge Schritte schritt für Schritt wird das Leben von X immer dann wenn es nicht anders geht wenn wir von ihm den Überschuss von X nicht sind schieben können auf eine Ebene tiefer immer abwärts zu einem niedrigeren lebe werden wir immer hoch und wiederbeleben das Leben von nichts und irgendwann würde es hoch genug sein das ist erfahren verlesen wurden aus der Überschuss dann wieder schrittweise nach es zurück gehen wird das ist die Magie von der wir reden und ich versuche zu kommunizieren und weil ich weiß dass ich selber damals leise gebraucht habe um diese Magie zu begreifen und weil ich mal davon ausgehe er unbescheiden dass ich zu den den vielleicht gehöre die relativ schnell mit sowas klarkommen Versuch ich dass ich hier möglichst deutlich zu machen ich hoffe das gelingt mir so der Mechanismus ist ganz einfach es ist eine Schleife so lange ist der Fluss so nicht zulässig ist es erfüllt immer das optimale diskrete das ist aber nicht zulässig weil wir die Versailles Bedingung verletzt solange es dort diese Knoten gibt wo also Überschuss da ist der aufgestaute so weiter geschickt werden sollte man uns die Knoten wenn wir von diesen bluten aus der Überschuss nach den Regeln der Kunst weiter schicken können nämlich danach er müsse bei arg heißt dass hier tatsächlich ein gleich steht und nicht nur kleiner gleich das also wirklich wie die Intuition ist dass der Fluss ist immer eine Stufe abwärts fließt dann machen wir das dann tun verschiedene so viel wie möglich Fluss drüber also natürlich wissen so viel Überschuss ist weil wir keine unter Schutz wenn ich das so sagen darf hier produzieren wollen also höchstens den Überschuss erbauen und nicht mehr als das und das ist natürlich die Restkapazität und wenn das nicht der Fall ist dann leben wir den Piloten den setzte das Leben dieses Knotens wo wir diesen Überschuss nicht mehr kriegen konnten über eine über irgendeine etwas über arg setzen wir den gerade mal so hoch das wieder mindestens eine ebenso bei arg da ist eine K 1 kannte vor VW so so das ist so dass da ein Gefälle wieder ab um um einen Zähler vorhanden ist also wir hatten schon wissen schon die Analyse eingestiegen beim letzten
Mal wie finden wie fängt es an wir fangen
damit an dass wir den denn bist einen bestimmten Schnitzer nämlich den Toten Essen Staat Noten und den Rest der saturierten den einfach auf wieder kann die rausgeht möglichst viel Lust setzen allein Fluss natürlich am Anfang 0 so
dass wir am Anfang schon die invariante erfüllt haben und wir haben aktive Knoten wir haben ja schon gesehen dass der er das ist das die Fluss werde tatsächlich immer ein Brief er geben also immer nur in jedem Knoten außer ist und die immer nur mehr Fluss rein als rausgeht in das wir am Anfang auch kein Widerspruch erzeugen mit den Definitionen wenn wir wenn wir es auf die Höhe Entsetzen gut wir haben auch schon gesehen was eben gesagt haben zunächst einmal ist wenn 2 Knoten mindestens N auseinander sind das ist das ist der Fall bei und wie die 1. gleich in und T ist gleich neue dann wissen wir es gibt keinen für seine seinen Fahrt von erst nach tätig und das für die ganze Zeit so bleiben in bleibt auf dieser Höhe Teeblatt auf dieser Höhe es bleibt immer ein wendet mehr gelingt das heißt also die erfülltes es gibt keinen Fluss einen Pfad von es nach T das haben wir alles schon gesehen in in
diesem Punkt noch mal der wird dann noch mal heute eine Rolle spielen noch mal dieses Bild das eben ganz am Anfang gesehen haben wenn für Überschuss an um dem bloßen ist da musste und woher kommt der kann nur aus es herkommen ja das heißt hier ist irgendwie Fluss eine gewisse Anzahl von Fluss einhalten müssen über einen Pfad kann auch über verschiedene fade gekommen sein muss dieser Überschuss da gekommen sein das heißt aber im Umkehrschluss dass man auch Fluss rückwärts wieder nach zurückschicken könnte spricht das ist ein Fluss in Fahrt fallen einem Überschuss Knoten von jedem die den Überschuss kann und dass es zurück geht nämlich der die Pfade alle Pfade über die Fluss hereingekommen ist
so das hier ergibt sich dafür aus sofort dann wer sollte das Leben irgendeines Knoten als dann nicht ganz für Überschuss ja doch stimmt für jeden Überschuss Knoten er gilt gilt das ist ein Fall zurück geht nach S Einfluss in der Fahrt es hat für ihren wenn dieser Knoten für 2 1 oder höher hätte gäbe es diesen fahre zurück nicht ja und das heißt also 1 einen Überschuss Knoten kann man niemals so hoch leben grüß er größer gleich 2 1 dann das würde dieser Aussage widersprechen dass Fluss eigenen Fahrzeug gibt und hier haben wir ja gesehen wenn es Einfluss erhöhenden Fahrt von 1 und zum anderen gibt kann eine Label dass das das Label höchstens entweder sein oder weniger als in höher sein als das Intel klebe und da wir Überschuss Knoten erleben könnte auch niemals einen anderen Knoten oder Überschuss haben der auf dem US-Label kommt so oder so wir
wissen die Labels in alle sind für alle Knoten lieber fliegen mit dem gesamten Verlauf des Algorithmus und er des Lebens der wie das Leben immer zwischen 0 und kleiner 2 n so dass wir also von vornherein wissen wir haben höchstens 2 im Quadrat erleben Operation und das hat mir schon mehrfach gesehen warum das so ist dass wir es hatte wäre der Porsche ist das heißt also die bei den wir so viel fürs rüberschicken über eine Kante das die Restkapazität vollständig aufgebraucht ist dass das beschränkt ist durch die Läden Operation Weine sie haben zunächst einmal ein Gefälle von und von da nach da zwischen den bei diesem des Lebens das werden sie sehr Missernten mal ein ein Gefälle von danach da sie Fluss rüberschicken zwischen den beiden Labels wenn das saturiert ist dann geht da nichts mehr über das heißt damit er später noch mal einen einen Push übergehen kann in derselben Richtung muss hier was mit dem Geld passieren der muss man irgendwann mal zweimal Mindestzahl hoch gegangen sein damit wieder mal Fluss zurückgeschickt werden kann in die eine Richtung und er dann muss der nochmal 2 hochgegangen sind damit noch mal in derselben Richtung Fluss geschickt worden sein kann das heißt also wir haben für jede Kante müssen so von allen Moral ein saturierten Pursch möglich weil danach die Idee das Leben mit am oberen Anschlag ist das das Label starten und ist dieser könnte so kann das
das interessante sind es immer die nicht Natur ihren dann Prosch ist das heißt die bei denen ein dabei den Fluss von er über eine kann dann würde ich es sie geschont der schon Kiel geschossen irgendwas würde Sorry nicht was Protokolle das war wirklich kein Freudsche Versprecher möchte ich deutlich klarstellen aber eben nicht immer noch als Kapazität übrig bleibt was heißt
das genau noch mal zurück zum Algorithmus
entweder es so die Restkapazität als ist das ist der Flaschenhals Satory unter Bush oder je in Zeile 7 oder der gesamte Überschuss wird ab von von der einen Karte zunächst 11 über diese keine von einem Knoten zum nächsten Knoten verschoben ohne dass der die Restkapazität damit vollständig aufgebraucht wäre bleibt noch Kapazität übrig das heißt die gesamte
Überschuss wird verschoben so
jetzt kommt eine interessante Technik zum zum abschätzen von von von Laufzeiten die ich hier in diesem Bereich glaube ich würde zum 1. Mal entwickelt worden ist aber die inzwischen schon in vielen anderen also das Problem stellen nicht nur bei Grafen Algorithmen Eingang gefunden hat nämlich meinen Sie so eine so genannte Potenzial Funktion her dazu wo man mal wieder ein bisschen Platz würde der so was ist diese Potenzial Funktion in diesem Fall die Summe aller kann Label von allen natürlich alle Knoten lebe von einem Knoten die aktiv sind die also Überschuss haben so dass eine Funktion die ist wenn man es mal über die Laufzeit verfolgen diese Potenzial Funktion wie sie genannt Fly so die ist am Anfang vor der 1. Iteration 0 weil wir zunächst einmal ganz zu Anfang haben wir 1 0 Fluss mit dem wir alles initialisieren also am Anfang sind alle alle Fluss Werte 0 also vom Libanon an danach fügen Sie ersetzen die die die Fluss Werte der kann es rausgehen hoch das heißt also wir erzeugen tatsächlich Knoten aktive Knoten Knoten mit Überschuss das heißt also durch diesen Schritt kommen wir zu einer Anfangssituation so hier das ist vor der 1. Iteration hier die Stelle dass es nach der 1. die nach dem erst nach der Situation 8. 2. 8. 3. und so weiter so die verschiedene Operation die wenn jeder Operation machen ein Sartory ein Bursch eine nicht hat und ihren Wunsch oder lebe die sorgen dafür dass die dass diese Funktion irgendwie hier hoch und runter geht und ganz zum Schluss wenn der Algorithmus terminiert ist diese Funktion wieder bei 0 denn es gibt keine aktiven wurden die eine und eine Summe über die leere Menge wissen Sie ist immer neue ja also Sie diese den Funktion irgendwie aus so was wissen wir noch wir wissen dass sie höchstens 2 2 im Quadrat sein kann hier ist und zwar im Quadrat oberhalb oder es trifft höchstens die höchste Spitze weil ja jedes einzelnen leben müssen 2 n werden darf gut so jetzt gucken was anderes was mit dieser Funktion mit diesen viel passiert in verschiedenen Oberwart Arten von Operation wenn wir eine dieser billigen starten während ich bin mir nicht sicher ob der Satz so stimmt also ich bin eigentlich sogar ziemlich sicher dass das so nicht stimmt wie man sie ein bisschen abschwächen aber das reicht auch was eigentlich hier stehen müsste was stimmt und was er auch das korrekte was auch reicht ist dass sämtliche reelle belegen Operation zusammen was die hier jeweils eine Erhöhung bringen also hier solche Erhöhungen von hier nach da oder von hier nach da oder von hier nach da wenn diese verlangten diese Westflanke mehr alle zusammenzählen was also so langsam hier ist Sie kennen das vom vom Fahrradfahren in den Alpen da erzählt man ja auch sämtliche Anstiege zusammen um damit angeben zu können dass man da 10 Tausend Meter würden würden Differenz geschafft hat oder so etwas aus meiner eigentlichen alten nicht schaffen könnte wenn man nur die die höchste Spitze oder die höchsten bis die Höhendifferenz hernimmt so also es kann nicht mehr als insgesamt 2 hoch im Quadrat an Erhöhung in Folge davon passieren wollen sie wir an dem Anschlag also diese 1. Satz hier 1 Läden Grieses frei bei waren hinter dem stehe ich nicht ich glaube
nicht dass der richtig ist aber sei es ist egal denke mal ersatzlos streichen der zweite Satz ist korrekt so einen saturiert unter Pursch erhält wie um höchstens 2 n weil wir was passieren kann ist dass ein was kann Bayern sagte während Pursch passieren es kann sein kann überhaupt eine Bush passieren es kann sein dass ein Knoten der vorher nicht in in diesem Sommer ein gezählt hat weil nicht aktiv war dass der 40 aktiv wird weil vorher keine Überschuss hatte und durch diesen Porsches jetzt Überschuss bekommt kann aber höchstens 2 n werden also diese das Leben keine wissen zwar in sein von diesem Knoten der vorher keiner würde sollten jetzt Überschuss hat so das so dass also und das betrifft nur einen einzigen Juden mal wo immer nur eine einzige kann denn diese Iterationen der Überschuss weiterschieben das heißt also eine Erhöhung von Vieh um höchstens 2 n kann bei ebenso drehen passieren mehr und mehr kann das nicht erhöht werden so und jetzt kommt die Gegenrechnung wir wollen die nicht zur Tour ihren emporschoß abschätzen weil für die noch keine Abschätzung haben und der geht eine Sache ist der das machen wir indirekt wir schätzen ab um wie viel höchstens diese Westflanke sei insgesamt in Summe so sein können dass das habe gerade im gemacht das ergibt uns automatisch auch eine Abschätzung der aus Pflanzen der der muss geht denn denn wenn wir bei 0 anfangen bei und enden dann ist das die Summe von Allah alle Höhendifferenzen hoch gleich diese Verwandten und unnatürlich so den Scheitelpunkt ist jetzt das nicht zur Theorie und der Pursch sie vermindert diese diese Potential Funktionen und zwar um mindestens 1 warum das müssen wir uns noch mal genau anschauen was da passiert war er nicht so du ihren Bursch das was heißt nur nicht so tun immer Pursch das heißt erst einmal Porsches sowieso nur dann erlaubt wenn die Frau gleich DIW plus 1 genau ist er dann dürfen wir ja der Fluss über eine Kante rüberschicken so wenn wir nicht saturiert und sind dann heißt das dass der gesamte er dass die gesamte Überschuss der eine Frau dabei V ist Platzwarte durch diese kann durch und noch viel zu kommen und das bedeutet V O würde inaktiv hat kein Überschuss mehr damit geht die von Frau raus aus der Summe hier ist ja die Summe über alle aktiven Piloten des von VW draus kann sein dass wir vorher aktiv war dann kommen die von Frau Ryan aber die von Veräußerung einzelner kleiner als die von Lesern einzelner kleiner als die von V das heißt in so mehr die von Frau geht raus weil sie nötig geworden ist möglicherweise die war die von wie vorher nicht drin und es und jetzt drinnen in der Summe ist aber ein sehr kleiner das heißt insgesamt in Summe es ist ist diese Summe kleiner dem um 1 um mindestens 1 kleiner geworden falls wie schon selber Arzt bin aktiv war ist er wahrscheinlich um mehr als 1 kleiner geworden und damit haben wir eine Abschätzung für die nicht so tolerant emporstrebte war wir wissen da die Rebellen Operation kann insgesamt nur 2 im Quadrat fiel Westflanke erzeugen also also hochgehen Schritte wir wissen jeder einzelne Sartori und Pursch kann höchstens 2 n Höhen Erhöhung der Polizei Funktion erreichen die an dieser Tour ihren Po Schritte schon auf der zur vorletzten wurde auf abgestellt schützt nach oben was war das noch mal das war einmal also
methodisch und wir wissen nur so
viele wie hier wieder gelingen sollte Natur Schritte an Erhöhung gebracht haben kann jetzt hier durch die dieser nicht so der jungen Paul Schritte eine Verminderung hineinkommen genauso viele und da ist jeder einzelne Iteration mindestens um 1 vermindert ist damit die Anzahl Iterationen mit nicht zu dulden Porsche die Anzahl der nächste Doreen für vermindert so und damit ergibt sich er gibt wir können höchstens und so viel höher werden auch nur so und das heißt nur so und so vielen Dank nicht so Werner Bush würde könnten wir auch haben ergibt sich insgesamt als ein totes Ofen in Körper das ist ein interessanter finde ich persönlich interessante Argumentationsweise er gezogen warum ich nie in der diesen Satz nicht ich stehe weil weil potenzielle muss sie Weblink anschauen hier
diese Setzung muss ja nicht das Leben von vor um exakt 1 mit haben es kann auch mehr als 1 gewesen sein ja sonst so sonst könnte man sich um die Zahl der also machen dann könnte man die einfach hinschreiben die vor für die vom 1 und fertig ja also je nicht hier muss ich eines rauskommen im Allgemeinen deshalb stehe
nicht unter diesen Satz der behauptet
dass die Summe der Labels um durch eine wieder Blick eines also nicht nur um 1 erhöht wird gut wir gehen dieses
Beispiel nicht durch das gucken Sie sich im stillen Kämmerlein an gehen wir zu wie vor Briefen durch eine es geht immer in den verschiedenen Variationen von Hilfe durch geht es immer darum die nichts durch einen pro Schritte Abt nach um abzuschätzen unterschiedlich gut abzuschätzen derweil die Gelände Schritte die hat man von im Quadrat dieser Tour werden Tonschritte Ofen einmal wir hatten irgendwo vor ein paar ersetzt es mal für ein paar Folien gesehen die Bemerkung dass es Beispiele gibt es man Beispiele konstruieren kann bei den wirklich im Quadrat und einmal erreicht wird die Größenordnung so dass man also da keine Schonzeit eine Verbesserung hinzukriegen aber bei die nicht drehen Po Schritte die bei deren Abschätzung der viel schlechter ist da kann man noch viel dran rumbasteln um möglichst weit runter zu kommen und eine Variante wie man da war darunter kommen können ist die Fifo Variante von von Entschuldigung von die Sudwischer in Brief lobt Bush Algorithmen was wir machen ist einfach folgendes wir halten die Knoten einer Adju drin so eine abgeben Knoten sind irgendwie in beliebiger Reihenfolge nicht dass es nicht so weit nach hinten tun ich musst deinen Platz wir sind in einer Kilo treten in unser beliebige Reihenfolge nach wie vor Pioneer kennt wir nehmen den 1. Knoten raus denn hier versuchen so viel Fluss wie nur möglich darüber zu schicken er über diverse kannten wenn der mehrere zur Auswahl haben so lange bis es nicht mehr geht das kann zur Konsequenz haben das neue Knothe bisher nicht aktiv waren jetzt aktiv geworden als Überschuss bekommen haben von diesem Knoten aus Überschuss gegangen Angeloni bis jetzt noch kein Überschuss halten die werden hinten angehängt dasselbe wieder wir nehmen uns in 1. Blue Knoten raus tun alles um den Überschuss los zu werden wir schaffen es vielleicht oder wir schaffen es auch nicht vollständig los zu werden es gibt jetzigen es bekomme potenziell wieder inne das neue aktive Knoten weil weil Knoten Überschuss bekommen durch den jetzt die war kein Halten und so weiter und so fort und irgendwann komme dann zu gehen an sie kennen Sie kennen das Spielchen nicht von irgendwelchen ja ich denke man in welchen Kinder spielen auf Kindergeburtstagen oder oder Phasen Spielchen oder ähnliches wo man eine Reihe bildet und von außen hinten jetzt wieder rein und oder umgekehrt und so nach und nach die die Reihe immer weiter so das ist alles das ist die einzige Variation der ganzen Sache das habe ich ihm gesagt ja ein als Denkmodell wenn wir hier an diesem Punkt angekommen sind macht es Sinn zu sagen dass nur als Denkmodell das ist nicht implementiert dem Algorithmus ja der es geht stur einfach die für die Vive durch nimmt sich immer dass das Element aber um darüber nachzudenken über Laufzeit nachzudenken macht es Sinn dass in Phasen einzuteilen und zu sagen so wenn der ursprünglich her Inhalt decke der Kyu vollständig abgearbeitet ist kommt eine neue Phase und wenn dieser Inhalt irgendwann mal wieder abgearbeitet es kommt wieder eine neue Phase und so weiter war es einfach nur um besser drüber reden zu können das steht hier würden dash so die
Behauptung ist dass wir da jetzt um einiges besser sind dass wir statt in bereit jetzt noch 3 haben das heißt also bei dichtbesetzten Grafen mit einer hohen kann sagen kann werde ich der Verbesserung in der also tot weg bei den besetzten Grafen wo die wo die Kanten Zahl Größenordnung Kurden Zahl ist da haben wir damit nichts erreicht ist ist gleichgeblieben so gut was ist die Argumentation in jeder Phase wir gucken uns die Phasen jetzt einzeln an in jeder Phase haben wir jeden Blut nur einmal betrachtet ja wenn bevor bevor es dem Jungen wiederkommen ist der gesamte Inkiow Inhalt eine bitte der US-Schwimmstar bei einem abgehandelt so in jeder was was man sich jetzt klar machen muss ist was bedeutet dass die Knoten wir haben gesagt wenn wir den Zug Not mehr und versuchen jetzt möglichst allen Fluss brausten von diesen Knoten mit es ein Überschuss über Kanten woanders hin zu bringen was bedeutet das es bedeutet wenn wir erst wenn die 1. Push schon nicht zur Theorie und ist das dann schon alle Überschuss weg einig also wird durch bedeutet aller Überschusses abgetragen so für wen der 1. pro Schulen nicht der Doreen ist das ein Überschuss abgetragen fertig wenn der 1. Natur ist kannst was in beim 2. oder wenn der 1. oder 2. der 3. oder 4. oder 5. und 6. Bush zu dosieren sind kann es vielleicht beim 7. durch einig Zeitungen bestehen aber das immer in der ja das entscheidende period hi mehr wenn wir ein Knoten hernehmen und versuchen Einfluss rauszuschicken so viel wie möglich dann gibt es hatte wie eine sehr eine satte in Porsche vielleicht nur 0 vielleicht auch eine Million und am Ende noch eine nicht so durch eine Pursch vielleicht wenn es wenn schaffen Überschuss ganz aus bringt vielleicht noch einen maximal 1 nicht durch einen Busch der dann den Rest vom Überschuss ab trägt ohne dass die der dass die Restkapazität auf dieser Kante damit ausgeschöpft ist so das heißt also in einer Phase es könne höchstens für jeden Knoten einmal ein nicht zu duldender Bush geschehen so das heißt wir haben diese noch 3 bewiesen wenn wir zeigen können dass die Anzahl der Phasen nur ein Quadrat ist war in jeder Phase das kann jeder Knoten nur einmal einig zu drehen und Bush haben weiteren dann seinen Überschuss weg ist und dann ist er fertig so es gibt nur neue Potenzial Funktion immer wieder die Summe also also Distanz werde von einem Überschuss Knoten jetzt wenn wir das Maximum und etwas andere Argumentation aber sehr sehr ähnlich bestellen Sie dafür ist auch auch hier die des Werte sind ja alle bis mindestens 0 und höchstens 2 sogar ich kleiner zeigen also kann er keine wie das Maximum über die Werte auch nur zwischen 0 und 2 hingegen gut also der ähnliches Bild wie das hier hatten wir nicht mehr mit 2 im Quadrat sondern ich das einfach mal hier korrigiere jetzt mit 2 N weil ich immer diese waren das Maximum fällt ein Faktor in weg so wenn wir jetzt auch hier auch hier stehe ich nicht genau hinter diesem Satz Ich mach mal weiter so hinter diesem 1. Satz in einer Frau also ohne man der Rechnung hinter diesem zweiten Satz stehe ich nicht hier also gehen wir mal zurück 1. Satz eine Phase in der keine Gelände Operation stattfindet ist zunächst mal eine Phase weiter der keinen kein Leben hochgesetzt wird keine manipuliert wird aber es kann wieder passieren das oder was heißt das heißt es ist keine Lüge passiert muss das heißt es brauche keine Gelände passieren weil sämtliche Überschuss von sämtlichen Knoten weiter geschickt worden sein könnte ja hat dann muss keine Läden passieren und dann immer wieder dieses Argument was wir schon vorher hatten sich leider aber nicht mehr an der Tafel habe halten konnte aus Platzgründen in der nehme ich das Argument das wär ja immer nur von Fauna W um einen egal wie soll ich mal wie 1 wie 2 die 3 und so weiter das wie immer diese Gleichung haben dass wir nur dann Fluss rüberschicken wenn das erfüllt ist werden wenn das Gefälle gerade passt und das bedeutet wenn dieser dieser Knoten und ihrer Länge heißt eine Phase ohne jede heißt jeder der Knoten die angefasst worden sind kriegt ein Überschuss weg hier und dieses des dieser des wird fällt weg bei dieser Gruppe nicht aktiv ist nur die die Werte die die Fährte bleiben ja sämtliche Knoten lieber angefasst worden sind da haben was erfolgreich den Fluss weiter zu schicken um einen wird um eine des um ein wir drunter das heißt der maximal die maximalen nur die maximalen Höhen Werte von den wir oder geschickt haben was vorher maximal ist die Cloudy bei den Fore dieses Maximum angenommen und ist die sind alle aus dem Spiel bei die neue maximal wurden höchstens am sind mindestens 1 kleiner das steht hier das ist das was hier steht so hier hinter diesem stehe ich nicht hundertprozentig ist auch nicht notwendig was letztendlich benötigt wird ist das was was hier unten steht sämtliche Phasen Brille Operation zusammen können Sie höchstens um 2 in Quadrat erhöhen mehr als das brauchen wir auch nicht so die Anzahl der Phasen in denen wir eine reale gelingt haben können ist höchstens 2 im Quadrat und die Phasen die keine haben können das sind die hier wo jeweils das wo also jeweils wir mindestens ein Schritt auf der Ostflanke machen runter können auch 2 ein Quadrat höchstens sein insgesamt ergibt sich im Quadrat viele Phasen vielleicht müssen starker Tobak aber wenn Sie sich in danach noch damit auseinandersetzen glaube ich insbesondere wenn sie dann die Videoaufnahmen hoffentlich endlich dann haben werden Sie wäre wir denke ich würde das gar nicht so schwer zu verstehen sein wenn man das erst durch gestiegen ist so ist es immer dieselbe Argumentation wir auf der einen Seite bestimmte Operationen wie das Vieh hochtreiben aber von den wissen wir das nicht beliebig hoch gehen kann und die Operation dieser abschätzen wollen die an die degressive abschätzen wollen die treibt das wie immer unter und wir wissen wenn sich beliebig getrieben werden kann kann so nicht beliebig häufig unter getrieben werden oder man es ist 0 so damit
haben wir das Fifo schon erledigt
und wir konnten allein in meines achten sehr
interessanten Idee die Grundidee von diesen Exzess gelingt Variante ist auch das ist eine Technik die ich glaube wirklich hier zum 1. eingeführt worden ist die aber in vielen vielen Stellen zwischen verwendet wird weil sie einfach auch eine sehr natürliche logische Sache eigentlich ist die Idee ist weil wie gehen Sie ja dass du schon irgendwas ran da es gibt verschiedene möglich also ungelöst Problemstellungen zu lösen sagen wir beispielsweise irgendwelche Möbelstücke in den Möbelwagen 1 zu tun wie gehen sie daran in einer ersten Phase Park packen Sie die großen dick die schweren Möbelstücke rein und eine davon keiner an denen sich die mittelschwere also davon keine mehr haben in dem sich die leichten und am Ende kommen dann die Kinkerlitzchen wer so würde man das machen nicht nur damit die Kinkerlitzchen oben und die schwere Möbel unten sind sondern sie würden auch dann machen wenn es keinen keine Probleme dieser Art gibt weil sie erst einmal des die großen wenn sie die großen schweren Sachen mit Überlegung in überschaubare Größe eine überschaubare Anzahl verstaut haben dann wird sich das mit den kleinen Sachen schon irgendwie wie packen hassen das wird schon klappen und das ist die Idee hier wir dass wir da zuerst nur die Überschüsse weiterschicken die groß sind richtig knackig sind richtig viel Überschuss haben und uns um kleine Überschüsse gar nicht kümmern und dann erst wenn die so weit erledigt sind dann gehen wir einen Schritt weiter und Sonne immer dafür dass die Überschüsse nie in die die das auf größer werden wenn die große Überschuss erledigt sind wenn die wenn die nächste Phase nehmen die Überschüsse von der nächstkleineren größere sozusagen und Bearbeiten des sorgen dafür dass es keine das den Wok und keine richtig großen Überschüsse wieder auflaufen erstmal der keinen Sinn dass sie sämtliche Khenkin Galizien so zusammen pappen als Überschuss dass das Ganze genauso groß wird wie ein großes Möbelstück ein sondern dass sie wirklich als Galizien dann verteilen die und so weiter bis sie bis sie am Ende er bis bis sie am Ende gar nix mehr haben bis die größte sie betrachten kleiner ist als die größte der Kinkerlitzchen die sie haben so habe da gehen wir die
wir direkt zum Algorithmus so wenn wir
zum Algorithmus war die Sachen die dort jetzt vor erklärt stehen wir gleich im Netz auch mündlich also brauchen sie nicht noch mal also durch zu gehen aber dafür haben sie es trotzdem schriftlichen sich später damit befassen so wie das üblicher Jahren gerichteten Grafenwerth jetzt ist es wahrlich nicht wirklich wichtig aber schon schon sehr nützlich das für ganz Eilige Kapazitäten haben nehmen wir als gegeben hin Sie wissen ja es ist keine einschränkende Allgemeinheit von ganz Präsidenten auszugehen so Rosenthal wird natürlich und was wir wollen ist wie üblich an maximal Fluss von S nach T wir fangen wieder an mit dem Üblichen dass wir den Fluss initialisieren mit 0 das wir die die Distanz Label erst einmal vorbei rechnen als die echten Distanzen von jedem Knoten machte das ist nichts Neues das war bei allen gesehen Varianten von Briefen Push genau dasselbe auch das ist nix Neues diese 2 ist exakt dieselbe kannten die aus es raus gehen da setzen wir den Fluss wird auf den Anschlag so dass wir dann den 1. saturierten Schnitt haben das von es nach des tatsächlich keine Versender fortgeht setzt man das Leben in die Höhe von 1. N die Höhe von T S 0 weil sehr sehr weil die des Wert der im Schritt 2 korrekt berechnet worden sind und die Entfernung von T zu T ist natürlich 0 und hier ist jetzt die die Größe von der die Rolle ist eine von der die von der die Rede ist Störung und sie sind schon durch diese merkwürdige Konstruktion war steht hier was ist das in Worten damit meine ich jetzt nicht dass er in Worte zu sagen dass es 2 hoch obere gehaust Klammer das meine ich nicht was meinte dieses aus es war die Wahl des war die größte wie die größte Kapazität in nein das was stehen sie diese was bedeutet dieser diese vor mir auf der rechten Seite in Worten der genau die nächsthöhere Zweierpotenz über dem höchsten über dem müssten Kapazitätswert von irgend einer kannte und sie sehen schon das sie immer gesagt werden mehr der worauf das hinauslaufen wird wir werden sehr verständlich dann das diesen Business und zwar bei aber das machen wir mal dann wenn wir schrittweise halbieren damit wir dann immer eine ganze Zahl haben Sie dann bei 1 angekommen sind und danach dann der ganze die Kapazitäten haben nachdem werden den Fall der Vergleich als abgehandelt haben ist nix mehr zu tun so so da sehen Sie dass die Wahl wir nun wir haben weit Schleife darum umgelegt vielleicht mal ganz kurz späten sehen weil der der große durch eines der der gesetzt der halbe das ist die Struktur gerne weit Schleife darum umgesetzt wo wir in jeder Iteration eine bestimmte Delta größere jeweils betrachten und im Prinzip ist das was da drin ist der generische ablesen Bush Algorithmus wieder vor nur mit einer kleinen unterscheiden wir bei der Formel fürs Bush und bei der Auswahl ihrer soll wir suchen uns einen aktiven Piloten hier steht Ursula Chi Ex erst mit Stromüberschuss das bedeutet einfach mindestens die Hälfte von Delta ja wir gucken uns immer nur die Überschüsse an die mindestens der Tage groß sind ja wir wissen Sie sind Wissens der der groß das ist am Anfang klar weil wir das der da am Anfang so gesetzt haben dass ist das dann nicht an muss man sehen kann also dass wir da nie was verschieben können was mehr als der da ist und wir werden dafür sorgen das wir auch später nie mehr als das ihr das aktuelle Delta irgendwo ein Überschuss erreichen so sie nie wieder wenn wir eine wenn wir einen besteht ein einen Bereich zwischen einem Geld und einem der Züge in der der halbe erledigt haben und dann ein Schritt darunter gehen mit halbierten Blätter dass wir nie wieder Überschuss erzeugen zwischendurch der Gruppe der dann im alten Bereich drin ist ja das wär ja witzlos sondern wir wollen die diese Größenordnung zwischen der unter halbe wolle einen einmal erledigen und danach gucken wir uns nur noch kleinere Größenordnung an so müssen aber dafür sorgen dass der 1. Größenordnung angucken nie wieder ein Überschuß passiert dieser Größe und auch Größenordnung so wie wir uns also Knoten ein aktiven Kloten einen Überschuss Knoten mit großen Überschusswärme ist der da halbe nicht irgendeinen sondern eine spezielle nämlich einen unter denen eine mit kleinsten des wird das hat einen Grund auf dem wir noch zu sprechen kommen werden warum das jetzt nicht irgendein beliebiger Knoten mit großem er Überschuss ist so und was wir jetzt machen ist hier dasselbe wie vorher falls wir eine er müsse der arg haben gezeigt dass er sie vorher den schicken in bestimmten Fluss da drüber ansonsten machen wir leben nur der Fluss werden wir rüberschicken der hat sich noch ein bisschen eingeschränkt so wie bisher auch nicht mehr als der Überschuss der einen Knoten dran ist es wird nicht mehr Überschuss weitergereicht als eine Nummer 1 natürlich nicht mehr als das Kapazität auf der kann das über die wir Fluss rüberschicken diese beiden Argumente der Mini Bildung waren vorher schon wenn es kommt ein neues Album in den Zug dafür zu sorgen wir müssen natürlich dafür soll sagen dass das was ein Überschuss an den Knoten muss hinkommt akkumuliert wird das nicht größer ist als das des das was ich ihm gesagt habe wenn sie einmal im Bereich von Überschuss Größen zwischen der halbe und die verlassen haben und dann zu der führte die halbe übergehen ungeachtet des Vögel und so weiter dass wir da nie wieder ein Überschuss erzeugen der der im Bereich der halbe die Delta hatte der in der er der älter ist und deshalb das müssen wir hier eingrenzen damit auch der Überschuss bei diesen ziel Piloten nicht größer als der der wird das ist höchstens der der dem aktuellen Überschuss man Wissens das verschoben wird und das ist die Idee die ganze Änderung das machen wir eingekleidet in diese große weil Schleife für jeden der da Wert beginnen bei dem hier bei dem 1. bis über 1 gelandet sind einmal das heißt wenn man den das wenn ich das jetzt als der den er nehme nicht ich sage das ist der da dann heißt es erst der Bereich der daher wird älter wird betrachtet Überschüsse in dem Bereich dann der dafür dann der halbe dann Delta 8. der führte dann der der 16. bis der 8. und so weiter und so fort so das wissen wir
jetzt über diesen Algorithmus zunächst einmal wissen wir wer nicht sollte Irene Pusch Sie sich es geht immer vor allem um die Abschätzung der nicht zur Tour und Bush würde weil die der gespielt und die saturierten pro Schritte die hat man so gut im Griff von Anfang an von unser 1. Betrachtung 1 für den Erich ein wurden schon der und so gehen wir wie man überhaupt nur haben kann also kommen Sie mir denn nicht unter ihren Po Schritte an und das erstmal Verständnis dass sie da nicht so Turenne pro Schritt eine Innenminister der halbe Einheiten überschickt
warum wenn er nicht saturiert ist wenn er wenn der Bush-Rede nicht operieren ist dann ist die Restkapazität nicht der Flaschenhals sondern entweder ist Yvonne vor der Flaschenhals oder der Terminus Yvonne wie aber schön und aber das hier ist größer der der halbe und das ist auch unsere halbe und deshalb fließt mindestens der daher
darüber und wir haben dafür gesorgt ich diese dritte Argument dass sie ihm schon gesagt hatte dass wir niemals wieder über die der darüber was der darüber komme mit dem Überschuss so jetzt die
Behauptung die Angst der nicht Zenturien Porsches Rohfaser Brustellin Phase aber also für jedes der älter ist ein Verrat und wie viele Phasen haben Sie ja natürlich logarithmisch wieder damit kriege ich immer den die Studierenden Gebetsformeln Logarithmus Jahr schrittweise Halbierung bedeutet logarithmische tiefer das bekannt also kommen das als seines Gerling Phasen so wird muss von und höchstens im Quadrat viele nicht zur Theorie und Bursch Ritter und das Bündnis mehr zu
beweisen werde steht dass ist wir da das muss erstmal beweisen dass in jeder gelingt Phase höchstens ein Quadrat wieder nichts hatten wir mal pro Schritte passieren und noch ne
schöne Potenzial Funktion ist man ohne etwas hübscherer versehen damit kann man eine ganze Menge anfangen nicht nur bei Marxloh auch ganz allgemein wenn Sie es dass sie eine Funktion finden Sie haben verschiedene Arten von Schritten dem Algorithmus die eine Art von Schritten die haben Sie gut unter Kontrolle was die was die Komplexität angeht die andere wollen sie unter Kontrolle kriegen und man sie schaffen eine Funktion zu basteln so dass die A 1 die Funktion hochtreiben und die anderen die Funktion runter treiben dann kriegen sie damit auch diese diese an der Art der Schritt unter Kontrolle Also die Grundidee so da sie bunte Funktion was passiert wir summieren über alle Claude Knoth dem dieses diesen wird jeweils aus und dieser wird es ein bisschen den kann und das kann man auch ein bisschen transparenter formulieren diese Formel der Potenzial Funktion oh was die eigentliche Idee ist ist kommt vielleicht besser aus wenn ich so schreibe E V durch Delta nein des von Frau ja die beiden die über das Überschuss Größen die hängt natürlich zusammen und das hier ist immer kleiner gleich 1 und da wir nur die die Latsch die große Überschüsse betrachten ist es mindestens größere ist es mindestens eineinhalb dieser Quotient hier so gut das aber eben schon gesehen Logarithmus von viele es gelingt Phrasen dieser auf Funktionen wie die Sie da einfach mal vom Himmel gefallen als gegeben annehmen ab die ist größer gleich 0 nicht sämtliche pro Jahr sämtliche werde hier sind größer gleich 0 also ist das gesamte Figur sei gleich 0 2 Enten wie kleine nicht Quadrats da geht das ein was sich hier aufgezeichnet habe dass dieser Quotient immer kleiner gleich 1 ist das heißt also wenn sie in Gedanken ihr von Frau geteilt durch der dadurch als einzusetzen da wir die Summe die Frau übrig hatten schon gesehen dass die höchstens zwar in Quadrat ist so es es ein bisschen komplizierter eine Brille Link Operation die einen dieser Devise hatte um irgendwas erhöhet wissen unglücklich dass den Erzählungen stehen bei Ärzten denke ich zumindest immer und war sehr klein ist bisher vielleicht schlecht denn also ausnahmsweise mal der wie Epson mir bitte finden natürliche Zahl da kennen Sie auch den kürzesten Mathematikern mit selbst ein kleiner 0 so wenn sie wenn eine Länge Operation denn die Wertung irgendwas erhöht dann kann auch diese gesamte viel funktioniert nun diesen wird erhöht werden werden er von Frau Sgrena berichtete Yvonne Forget hat der ist kleiner gleich 1 das heißt also wie können wir auch hier wieder nur insgesamt um höchstens 2 im Quadrat erhöhen über alle sogar über alles geht in Phasen der gab und ich meine sogar dass als Faktor noch dazu also die Erhöhungen von Vieh dieser Funktion ich erlebe den Operation sind wieder mal schön die Westflanke Niesen und schon wieder er fühlt sind wir mal schön begrenzt so jetzt ein bisschen einer Situation als vorher wo immer dieser Tour 1 schritte Bush Schritte ebenfalls die Funktion erhöht haben mir sogar so bequeme Situation die dass sämtliche pro Schritte saturiert oder nicht Orient Ostflanke bilden also Wuffli runtergeht warum das liegt an die hier kommt jetzt der Punkt im Spiel wo ich gesagt habe dazu
comma noch hier 206 wenn nicht irgendein Noten hier mit mit großem Überschuss sondern einen unter allen sowie großen Überschuss 1 der der der kleinsten kleines ist die wird hat ja das bedeutet noch mal zu Änderung jetzt muss ich aber noch mal klar zu machen das bedeutet sie haben sich wir schieben Fluss immer rüber nur wenn die Bedingung erfüllt ist ich reite immer wieder drauf rum das also Geld und das bedeutet wenn wir das minimal gewählt haben V minimal Vita V gewählt haben so dass die von Frau unter allen Piloten mit großen Überschuss mit dem Überschuss mindestens Delta halbe unter allen diesen Knoten den minimalen des wird hat dann bedeutet das dass sie Latsch Exzesse und so haben wir Frau gerade gewählt deshalb ist hier in dieser bei dieser Minimums Bildung in Zeile 7 hat keinen schickste ist deshalb können wir hier auch mindestens der GAL darüber schicken wenn das jede in der Flaschenhals ist der den gesehen von mehr das habe ich mir gesagt ich hatte versäumt zu begründen warum das ist aber da sie alle das anscheinend geschluckt haben habe ich dann auch die Begründung verschoben jetzt wo ich eher auf das Thema zu sprechen komme keiner hat ist das das heißt es muss ich nur mal kucken wo sind
wir hier stehen geblieben ach nee nur dort wo sehen gesagt haben dort war die Begründung notwendig ist die Gewinnung gar nicht notwendig sondern geht sich automatisch wenn nicht wenn ich sich automatisch aus dieser Bedingung der Vergleich die wir plus 1 ohne die ganze Sache er dich dazu gesagt habe das war notwendig für für für die andere Stelle aber hier es ist notwendig denn die Frau gleich in E-Plus 1 denn das bedeutet dass Überschuss von von Frau wenn es nach Willi geht dann geht es zu einem knurrt von einem Knoten im Netz mit Wert TV zu einem Knoten mit wird die vom des 1 das heißt dementsprechend wird wie reduziert so haben wir festgestellt einig zu dem wir Pursch sind mindestens der halbe Einheiten dafür brauchen wir diese Argumentation das wie kein Latsch das hat das ist klar die in die wir gesichert ist dass das mindestens der der halbe Einheiten sind was dann eben entsprechende gibt um mindestens 0 comma decimal 5 dass wir das Vieh vermindert gut dass noch mal die da das sind die das gelingt vor das wüssten so hoch gehen kann so und wenn wenn wenn wenn das wissen so roch gehen kann und auf der Insel und auf seiner Seite die nicht drinnen Spiel so viel schon wieder vom untergeht Potenzial aufgefordert haben na dann so viel vom unter gebunden übrig für die nicht saturierten nicht hatte wegen pur Schritte ne ungefähr ihr falsch ja wenn jeder mindestens um 0 comma decimal 5 Störung falsch wenn er nicht da drinne Bush-Rede mindestens 0 comma decimal 5 Einheiten das Vieh vermindert dann heißt das ich hiermit im Zähler ist das um was es höchstens erhöht werden kann insgesamt jeder einzelne Schritt kann zumindest muss um mindestens 0 comma decimal 5 vermindern das heißt nur so viele Schritte bleiben insgesamt übrig die nicht nicht zu drehen Po Schritte sein können und damit haben wir die Behauptung bewiesen ist quadratisch viele sind so ist jeder was ich habe noch was
unterschlagen bitten wir Sie wurden dann unterschlagen und ich habe mit wie kriegen wir diese Distanz Label wir noch mal zurück zum
Algorithmus hier von allen Aktiven
Noten mit großen der Überschuss Minister da Überschuss wenn wir in die Noten aus der kleinsten des Wert hat von allen denn jetzt müsste allein geschrieben Achtung da braucht man wieder aufwendige Datenstrukturen Poldi und so weiter das kostet wieder mindestens theoretischen Faktor obendrauf oder so aber die Baum ist hier dass sie keine Vater noch obendrauf kommt sondern wie wir das gemacht ähnlich wie wir das schon mal in einer Situation hier irgendwann am Anfang in der Vorlesung hatten in einem der 1. Termine da ging es um um diesen kürzeste Pfade das wir Rally haben 0 1 2 mit diese mit den typischen NEC ist mit 0 beginnend und das wieder in in jedem I und speichern ja sämtliche Gluten speichern die großen Überschuss haben also den über den Fall kommen und deren des wird gerade jetzt und da können erst einmal von links nach rechts durchgehen um zum 1. und zum 1. zu kommen entscheidender Punkt ist jetzt der ich muss immer wieder darauf rumreiten wenn wir tatsächlich irgendwo wenn irgendwo tatsächlich was passiert also es gibt erlebe dann geht es weiter den dann wandert dieser Knoten weiter nach rechts statt das nichts weiter auf unserem Weg von links nach rechts comma später einem vorbei aber wir verpassen nicht was aber passieren kann es sein dass ein Knoten plötzlich große Überschuss bekommt der kleiner ist als dieser in diesem Leben also linke Hand ist und wenn der Sturm war nichts weiter die gehen dann würde und wenn wir den verpassen er die ist stur von dieser rechts durchzugehen einmal durchzugehen und dann und dann nie wieder dass die Grundidee aber ganz so einfach kann sich gehen mit Relay beschriebenen dass die einzigen schritte wären die die Werte ändern dann dann wäre es kein Problem da comma später bei den du noch mal wieder vorbei aber es kann passieren dass plötzlich dieser Knoten der vorher nicht immer weiteren drin war jetzt rein gehört ins ins dabei ja weil er nämlich große Überschuss bekommen den er vorher nicht hatte eine weil die Frau gleich TV plus 1 ist das ist das worauf ich immer wieder halte hier bin dem Kapitel wissen wir wenn so Piloten passiert vorwiegend zu suchen haben nämlich gerade 1 längst zurück das heißt also unser Zeiger geht in der General Tendenz von links nach rechts aber jedes Mal wenn Essen pro möglich ist wenn man die Liebe wenn erlebe passiert es dann geht geht dieser Knoten weiter aber Zeiger bleibt hier Wählerrand Bush passiert denke der zeige wieder 1 nicht zurück und dann von da aus wieder Bush würdig ist geht er dann wieder einfach links zurückkommen da und so weiter der wenn Fluss bis nach Tee gereicht werden konnte wenn man Dateien auf diese Art und Weise zurück haben Sie Oma die Tormaschine gesehen sie kann das mit dem Band immer hin und her gehen dann in mich das irgendwie dunkel und auf die Art und Weise können Sie bis auf den bis auf den einmaligen Aufwand dass es doch einmal durch Schaffen von links nach rechts insgesamt können Sie die Anzahl der Schritte wie das weitergeht begrenzen durch die Anzahl der pro Schritte und damit sind Sie in der in der subtropischen Komplexität und dieser Besuch haben krieg keine an zum Tod Komplexität und drauf was man so alles mit wie gekramt alles Gute und machen kann nicht so damit sind wir mit ihr
das gelingt insgesamt
fertig das ist nichts anderes als das was ich ihm gesagt habe hier nur noch als gut als Feststellung zum Schluss dass das die Laufzeit das Algorithmus ist n x plus N Quadrat für Grafen für für Instanzen für Eingaben die dünn besetzt sind wo die kann uns Zahl sehr grüneres und der großen Zahl ist und wo die Kapazitäten auch nicht brutal hoch sind sind wir praktisch quadratisch auf einmal quadratischen Anzahl der Knoten das ist doch schon mal ordentlich oder aber schon schon gut weit runtergekriegt zu den zu den Kapazitäten wenn sie sich vorstellen ja alle Netzwerke mit Kapazitäten also typischerweise haben Sie ja bei Kapazitäten irgendwie bestimmte Größenordnung her sie eine Kapazität von 10 Kapazität von 20 aber sind von 30 ausgelegte aus und ich formuliere Nummer das bedeutet dass ihr groß S 3 ja weil sie die Gemeinden bleiben Sie mal den gemeinsamen Nenner nehmen die größte gemeinsame Nenner nee das das den größten gemeinsamen Teiler nehmen können ja man einfach Quatsch allerdings aus gemeinsamen Teiler nehmen können ja also in der Realität reden wir von relativ kleinen es ist nicht unbedingt 3 aber vielleicht er genauso wie bei dem das Tanzen über trachtet haben Sie wenn Sie nach wie das Tanzen betrachten von welchen besonnen reden Sie dann setzen sie gesamt wenn Sie wenn wenn sie gesamtes Kartenmaterial bis Singapur und Kapstadt haben reden sie von Distanzen von von wie viel von diesen 15 Tausend Kilometern insgesamt in Granularität 100 Meter das sind auch nur 150 Tausend ja das ist noch gemessen an der eine Gesamtgröße des des Netzes was sie dann Klonen Karten haben ist das läppisch so ob das ist wirklich eine Verbesserung ist dieser Algorithmus denn auch gute Orden und tratschen dann vorgeschlagen haben darüber gehen die Meinungen durchaus ein bisschen auseinander also generell ist es ist es so als Faustregel auch wenn ein Alkotest eine Aufwandsabschätzung hat die schwierig ist dann ist dieser Algorithmus weiß nur schwierig zu implementieren und mit den Tieren heißt wenn sie doch implementieren ist die Wahrscheinlichkeit groß dass sich viele dabei machen die dann in die langwierig ausbügeln müssen so was kann man
noch so alles machen hier das ist
jetzt ein period sehe ich das richtig
ja das ist ein Punkt zu dem ich nicht allzu viel
sage Walzen Übungsaufgabe ist wir ich will nur den einen Punkt die Illustration des Ganzen sagen die die Intuition die dahinter steht und alles andere klicken Sie bitte selber raus mit ich hatte er auch heute ich zum 1. Mal zum Bild gezeichnet wie man sich so die Situation vorstellen kann natürlich nicht einfach so baumartig sondern das können ich aus wieso alles auswählen über ICANNs Überschuss geben auch mittendrin gibt es mal Überschuss natürlich hier an den Enden gibt's Überschuss das ist so meine Intuition von PR wiesen Schnappschuss von Briefen Pursch Algorithmus aussieht dass sich das so das das eben so viel Flüssigkeit aus von es nach T aus fließt dass es sich da dass er dass sich da durch sämtliche Ritzen im Grafen durch vorwärtsbewegt so und ich habe auch gesagt na ja früher oder später wird der Algorithmus wenn diese werden diese kann Überschuss Knoten wenn der Fluss nicht mehr was bis T weitergereicht werden kann weil zwischen dabei ihre ist ein ein Flaschenhals Schnitt und aller Fluss der darüber gehen kann ist schon übergegangen dann wird es früher oder später werden diese Knoten hier alles Überschuss Knoten also so hoch gewählt werden dass sie höher sind als es und dann wird der Fluss rückwärts zurückfließen das geht auf jeden Fall weil ja hier um mindestens auf diesen Wegen kann der Fluss rückwärtsgehen aber das würde also das nicht unbedingt machen ja der würde Bodenziele den Fluss nicht ich hier auf demselben Weg wieder zurückbringen sondern der wird vielleicht einen anderen Weg wählen so hier lang und hier vielleicht weitergehen und was und dann bleibt hier ein Zehntel übrig ja ist das Ergebnis kein Kraut und Rüben ansehen und die heuristische Idee und diese auf dieser Folie und auf der nächsten Folie geht ist dass wir das eben gerade nicht zulassen sondern dass wir den Algorithmus zwingen durch die kleine Modifikationen dazu immer nur auf den Karten wieder wenn es so weit ist dass der Fluss zurück der es wissen muss was wir einen einer leben wir erkennen an der das es für mindestens so wie es geworden ist dass wir dann das dass er dann wirklich nur könnten verwendet zurückfließen lassen über die der Fluss tatsächliche komme es also rückwärts kannten das ist die Idee hier dabei und das Ganze ist leider nicht ganz so einfach zu beweisen dass das Ganze wirklich funktioniert dann nur muss man ein bisschen hier mit den steilen könnten argumentieren
aber wie Sie das sehen das Ganze ist eine Übung dem will ich hier nicht vorgreifen so eine weitere
heuristische Verbesserung ist halt also das nur so war dass man damit kriegt man keine bei besser was es Komplexität hin aber man kriegt immer in die Praxis sagt Exkremente sein dass es tatsächlich der Algorithmus in dieser in der verbrauchten CPU-Zeit beschleunigt eine weitere Sache ist wir haben ganz am Anfang des Algorithmus die echten Distanzen von Leben Blutnacht T gesetzt als die Werte und danach haben es eben laufen lassen mit Helene und Deutsch diese heuristische Besserung hier besagt dass man hin und wieder mal vielleicht wenn die bekannten Zahl ist vielleicht alle 10 m x oder alle 100 m x oder vielleicht nur 1 2 1 als immer mal wieder zwischendurch die Distanz Levels auffrischt dass man sagt ok vor jetzigen sind dafür die jetzige Situation rechnen wir wieder die Distanzen die Anzahl der kann die man braucht um von eben Knoten nach T eine er Fluss erhöhen zu kommen also mit Restkapazitäten oder wenn das nicht mehr geht wenn der das Leben schon so hoch ist also wenn man mit klar ist dass es nicht mehr nach T gehen kann dann eben plus die Distanz nach es zurück ja also die Knoten hier auf der Seite die Überschuss haben da berechnen wir dann die echten Distanzen nach D und die Knoten auf der Seite die die so hoher Distanzreiter haben mindestens das klar ist da kann kein Fluss mehr rüber rübergehen nach D die sitzen da gucken wir was ist die minimale Distanz nach T zurück in der Anzahl der könnten Fluss erhöhend und das setzen wir als neue die werde ich hier Ecke wieder Ende der gelingt es hatten wir schon mal nur für diese Seite nachgeprüft das also ist das gilt natürlich für die Seite genauso können Sie wenn Sie wollen doch meine Stimme Maler nachprüfen ob es ist identisch das heißt also dass er zwischendurch einfach mal eine kurze Phase entschieden wo wir alle ebenso so hoch setzen wie wir wissen dass sie dass auf jeden Fall gesetzt könne er das sie setzen können ohne dass wir was falsch machen ja ich hatte ja eingangs gesagt diese des Wertes in gewisser Weise eine faule Version 1 Anneliese Versionen der der echten Distanzen macht des und er was man tun kann es einfach zwischendurch das mal wieder die die wird also hoch zu setzen wie die echten Distanzen sind und dann wieder weiter zu machen wenn wir das nicht wollten nicht also häufig macht dann bleibt es dann bleibe der Gesamtaufwand in der asymptotischen Komplexität in die man sowieso schon hat dann wenn er das die also Komplexität nicht ist das was hier gezeigt gesagt wird sonst alle so und so oftmal zehnmal eines anerkannten und wunderbar als anerkannten zwischen mal diesen Zwischenschritt einen schieben um mal wieder die Distanz Liebe einen Bissen hochzutreiben und und einfachen diesen Aufwand zu sparen dass diese Distanz Liebe unnötigerweise also nach und nach und Schritt für Schritt hochgetrieben werden letzte glaube ich Verbesserung die direkt wieder auf dieses Bild ich fast danach zu sagen pflegen und 2 Phasen aus in der 1. Phase versuche mir so viel wie möglich Fluss von erst nach der zu schicken und feststellen es geht nichts mehr der Mann war mit mit der 1. Phase Schluss und stiegen dann so viel wie möglich Fluss wieder nach so Walk das ist in der jetzigen Version der bisherigen Versionen von der Formbriefen durch Algorithmus nicht so gilt in Phasen getrennt sondern das ist so ein bisschen Kraut und Rüben von manchen wird noch Versuch nach der weiter zu schicken bei andern geht schon wieder nach Heist zurück je nachdem wie hoch die Distanz lebe sind die Idee ist hier wirklich ein echtes Schnitt zu machen erst alles noch und wenn da nix mehr geht dann alles was es wie geht das zunächst einmal Betrach- in der 1. Phase betrachten wir nur die Knoten die noch unter der wir von es sind also die noch Kandidaten sind wurde würde Überschuss vielleicht bis T kommen kann und wenn diese Knoten beendet nur würden und 0 erst dann und dann wenn diese Siedlung beendet sind dann gehen in die zweite Phase man wenn es keine Knoten mehr gibt es das Ende dessen kleiner als N ist dann kann man mehrfach gesagt dass unser Indikator dafür das ist nicht mehr mehr dass keine zusätzlichen Fluss mehr keine Überschuss mehr nach T E geschickt werden kann und und dann gucken wir uns an schmeißen sämtliche Knoten raus die auf der sollte sind hier diese alle nicht mehr aktiv weil wenn sie aktiv werden hätten sie immer kleiner als die comma Ausschleusen der und eine alle anderen Knoten die Diebe die lassen wir trennen und von den schicken wir wieder den Fluss nach es zurück drin das sozusagen um auf Wiedersehen gesagt habe wer rechne man jetzt erst als die Senke her nicht mehr T sondern es ist die Senke Bereichen von da aus die Distanz wird zurück und wir machen uns immer weiter wobei das das Ziel jetzt eben nicht mit T sondern es ist aber das ist okay weil wir haben so viel nackte geschickt noch irgendwie geht und doch eine Heuristik eine haben
noch die Kinder aber schon in den Zusammenhang mit Christel wegen Explo fort werden wenn wir einen wenn wir einen eine Schicht für haben die der ist dass das will ich jetzt nicht noch mal wiederholen wir haben es alle schon mal er betrachtet das können Sie gerne dann Transfer ist das sollte sich 1 und 1 1 zu 1 1 zu wählen lassen auf die sie wenn Sie eine haben dessen eine Schicht für haben die in der keiner sehr Klonen ist dann ist dauert an dieser Stelle ein schon saturierte Schnitt und der genau dann es an der Stelle schon ein saturierter schnitt hier Sonne hier sondern Werke an der Stelle saturierte Schnitt alle hier kleiner als dieser wird K alle hier größer als der wird klar und das heißt wir können wir können die alle das jetzt die rassische Verbesserung für können die alle auf für n ohne dass will und es bleibt weiterhin sehr mild lebe Link und die von den Einfluss wieder der es soll so schien es geht immer um dieselbe Sache es es geht bei den neuesten immer wieder darum er zu verhindern dass kleinteilig Schritt für Schritt Fehler es passieren unter zwischendurch den entsprechend Porsches hin und her und hin und her sondern dass man möglichst häufig in dieser Service macht eben mit Gewalt hier in diesen verschiedenen Heuristik mischen Techniken die in großen und hoch machen so dass man sich diese vielen kleinen Schritten mit den dazugehört beleben finden dazu gewinnen in der Porsches einfach heuristisch parat wie gesagt keine Verbesserung an der asymptotischen Komplexität das steht auch nur Joystick er eine durch aus Prag in der Breite empirisch durchaus ernsthafte Verbesserung so und damit bin ich mit diesem Kapitel maximale Flüsse für heute durch Frage ja gibt es gibt auch also von oben und von immer jetzt muss ich noch mal nachdenken der basiert auch auf Briefen Vorschläge bitte genau wie er man kommt immer kam immer näher Ofen immer im waren aber aber hatte sie erreicht ich müsste noch mal nachschlagen was genau die was genau die Idee bei dem Algorithmus war dass er mich daran dass ich das entsprechende Standardwerk über Netzwerke für mal wieder einfordern müsste von den Innendienst ausgeliehen habe haben es basiert aber prinzipiell auf der Preview Porsche ID also die Briefe Poli- der hat sich eine als wirkmächtigsten herausgestellt alle anderen haben so ihre Grenzen und komme nicht darüber hinaus und diese die ganzen anderen Ansätze sind eben deutlich über einmal mal es gibt sogar unter in meinem ein bisschen sondern ganz kleinen sie nicht wird und also einmal in geteilt durch eine sehr langsame wachsende Funktion das gibts auch noch aber die Sachen dann auch sehr kompliziert ist und sie sie ausgelassen das noch die einfachen Varianten gut ich denke es macht keinen Sinn heute mit dem nächsten Thema anzufahren dann verbleiben wir so und wir sehen uns hoffentlich beim nächsten Mal wieder okay statt
Loading...
Feedback
hidden