Merken

Randomisierte Approximationsalgorithmen

Zitierlink des Filmsegments
Embed Code

Automatisierte Medienanalyse

Beta
Erkannte Entitäten
Sprachtranskript
ist die sich auf Herr er kann MH immer
herzlich willkommen zur heutigen Vorlesung ich hoffe ich wurde letzte Woche gut vertreten und es hat alles ganz gut geklappt tut mir Leid es passiert es leider Mehr mir noch 3 Wochen um es passt in den 3 Wochen leider nur dreimal haben tut mir leid ich hatte Sie am Anfang schon angekündigt es ganz und gar nicht meine Absicht wenns geht schau ich dass ich auch Montag und Mittwoch in Bandar bin aber das klappt leider doch mein zusätzliches Amt im Moment nicht wir hab ich hab gesehen wir haben jetzt auch noch mal vielleicht was man noch so vorhaben dann auch gleich an der Stelle der aber nur noch 3 Wochen in "anführungszeichen wir sind wenn wir jetzt mal nicht Stoffumfang schaut ganz gut in der Zeit wären Größenordnungen noch 20 Seiten wenn man das in dem Skript anschaut und wir haben eine immer nicht Schnitt geschafft von 4 bis 5 Seiten pro Vorlesungen so grob das heißt wir sind vermutlich in mit dem Stoff in der Größenordnung 4 Vorlesungen Durach es gibt es 2 Möglichkeiten also eine Seite hin auf jeden Fall noch erzählen wollte sich normalerweise im Anschluss an Tranchen bauen das letzte Mal gemacht nämlich diese manchen Card Verfahren Verfahren was sozusagen wirklich implementiert wird in der Praxis also so ein bisschen Einblick wenn Sie so auf der Pakete benutzen es gibt sie Plex wären was tun wir denn genau um solche Probleme zu lösen das hab ich als Folien Vortrages wollte jetzt nicht den Assistenten geben dass sich dort eine arbeiten deswegen wollt ich Ihnen das unabhängig sozusagen von dem Stoff noch erzählen das ich dann vermutlich wenn man dann doch sehen also heute in 2 Wochen dann machen und dann haben wir eine Vorlesung noch offen ich glaubte wahrscheinlich macht es keinen Sinn dass ich nur noch Wirkstoffe Beleg kann ich mir natürlich wenn Sie das möchten wir war letztes Mal so ein Kapitel blieben alle mit roten es gibt Zusagen von theoretischer Seidel einige interessante Aspekte zu Pi mal mit roten ich bislang außen vor gelassen ich kann die vielleicht noch mal ein bisschen an skizzieren in der letzten Vorlesung aber eine Vorlesung ist dazu zu wenig um um das intensiv betreiben zu können was sich aber gerne auf jeden Fall mit ihnen machen würde ist die Lehrveranstaltungsevaluation nochmal durchsprechen das würd ich dann für die letzte Vorlesung vorsehen und wenn man dann eine Stunde oder was auch immer für fertig sind oder gar eine ganze Vorlesung es wahrscheinlich niemand böse letztendlich der nicht immer außer Sie sagen wir wollen noch irgendwas oder sie können natürlich auch umgekehrt sagen dass die immer gemeint ist jetzt oder wir können um eine kleine Wiederholungs-und den machen so und so zu letzte Vorlesung was was war das ganze Semester was hätten wir eigentlich alle gelernt haben sollen und was sind sowie die Highlights die aus meiner Sicht hätten hängen bleiben sollen können auch gerne in der letzten Folge 90. ich sehe und aber Stellen liegen also vielleicht machen wir dann das dass bei der letzten Vorlesung Lehrveranstaltungsevaluation machen und ich erzähl doch mal viel passieren was es so alles gemacht haben und was hätte hängen bleiben soll ok für auch für diejenigen die dann vielleicht Prüfungen machen wollen werden das vereinbart dass wir keine schriftliche machen eine überschaubare Anzahl und das neue individuell dass sie einfach Prüfungstermine ausmachen Insel wenn sie meinen so weit zu sein und das brauchen Prüfung zu machen ok gut ja inhaltlich dann sind wir ein ganzes Stück sozusagen letzte Woche weiter gekommen in der Hinsicht dass wir ich gehe noch eine Woche zurück heuristische Verfahren angeschaut haben also wir haben unser lange damit beschäftigt wie bestimmt man gute untere Schranken dann haben unsere mystische Verfahren angekuckt Kuli und auch mal so wie Standard Methoden die in der wie ist der häufig in der Praxis verwendet werden der Buße Deutsch genetische Algorithmen 7 mit Anilin und so weiter die haben es sehr hohe Beliebtheit insbesondere außerhalb der Mathematik und weil er dessen Verfahren das haben sie sicher gesehen da gibt eine viel dazu zu sie nur leicht verständlichen irgendwie intuitiv na und die kann man auch auf alles an wir so nach dem Motto wenn man einen Hammer hat ist alles Nagel und man hat dann diesen Hammer genetischen Algorithmus und ich musste meine Parameter ein bisschen anders einstellen und schon gar nicht ein und dasselbe Verfahren auch auf jedes andere Problem verwenden und es hat natürlich die Nähe der Eigenschaften ist lang genug laufen lässt dann wird die Lösung qualitativ besser ist auch was das irgendwie intuitiv ist Qualität kostet und das 3. Team aus in hohe Laufzeiten und und das ist einfach verständlich man kann ich es schön bildlich darstellen wie sie diese Verbesserungsprozess von solchen Algorithmen darstellt also wenn sich später mal Industrie rausgehen und mit andern zu tun haben wenn sie häufig diese Schlagworte finden aber der Kern ist eigentlich das was wir gemacht haben kann auch ganze Bücher drüber schreiben ganze Konferenzen der zu veranstalten und jedes Mal eine neue Anwen jedes Mal neuen Parameter jedes Mal an der Schraube ist Tränen andern Schrauben bisschen da gibt es sehr viele zu weshalb auch besonders beliebt ist aber vielleicht nur das ist so stark dass auch insgesamt kann ein Stück einordnen können es ist auch so das muss man auch sagen dass ist für viele Probleme im Moment auch keine wirkliche Alternative gibt weiß es sehr komplex sind weil sie hohe ja nicht gelten zum Beispiel drinnen schwierigeren Bedingungen die so mit mit den klassischen Verfahren nicht hm nicht handhabbar sind da und dann dass so ein Verfahren funktioniert immer allerdings wenn meine Struktur hat und man kann diese Struktur aus das sich und dann sind meistens andere Verfahren besser also Beispiel Wasser diese Verfahren dann auch dass der Linzer ist mein Problem benutzt aber der sowieso so gut Stück untersucht wir alle würde das sind so gut die exakten das Mandat auf soll Gefahr nicht der zurückgreifen muss was anders ist es irgendwie schön muss mechanischen Prozesse haben wo sie ob die Geometrie Optimierung machen wollen dergleichen und 1 Simulation schon sehr aufwendig ist und eventuell Tagesstunden Stunden oder Stunden rechnet wie geht man da um sie könne dich nicht dies ganze Simulation sozusagen mathematische Modelle dieser dass zumindest sehr aufwendig in solchen Fällen bieten sich natürlich solche Verfahren an die nicht unabhängig sind sozusagen von von den zugrunde liegen Strukturen um einfange Blackbox verwenden kann die aufrufende spuckt eine Lösung aus also weit vielleicht noch mal aber es hat also das Tempo guter den ich auch ausgiebig mit ihnen Stück Wald erläuterten vielleicht nochmals nach können und letzte Woche über war man dann so weit dass wir gesagt haben geht schauen uns an man denn wirklich eine globale optimales interessiert sind wir mit einer Salzgeber gute und ein anderes als gute obere Schranke ausmachen wenn Lücke da ist ja und da mal 2 Verfahren kennen gelernt ein planschen bauen das so dieses klassische Verfahren ist genau beides auch ausnutzen kann und diese Panchen bauen Verfahren auch wenn jetzt erst mal sehr einfach klingt sind doch die die heute am erfolgreichsten sind insbesondere man die Bauens gut hinbekommen also die untere Schranke und auch die obere Schranke welche dann in 2 Wochen nochmal ausführlich dazu erzählen was wird denn da im Detail alles wirklich genau gemacht und das interessante ist dass sich der algorithmisch in den in den letzten 10 20 Jahren unheimlich viel getan hat gerade in diesem Bereich also Brunch und Stuttgart oder Pantschen bauen Verfahren nicht Schnittebenen Verfahren was das bauen die machen Heuristiken auf der auf der prima in Seide ist momentan das beste Verfahren was es gibt zig alle kommerziellen Pakete und auch die auch die Wissenschafts Pakete basieren alle auf diesem Prinzip und tun einer der bekanntesten Vertreter der auch sozusagen momentan die führende softe zu warten ob XP von Franzi plexere jetzt eine neue Firma gegründet Grobi und den ist auch das auch schon aus offenbar es annähernd so gut es die packs also der klar an der Stelle des Marktführers der Welt mal so Vorträge vielleicht kann ich die Zahlen auch dann mal zeigen dass seiner Folien da werd ich noch mal fragen wie der Fortschritt in dem Bereich war ein Mann der hat er verfolgt das ist seit 20 Jahren als er angefangen hat mit seiner 1. Software Nader 19 wird 90 mit seiner Version 1 0 von Citrix inzwischen so bei 11 11 1 11 2 einfach mal verglichen was war der rechnerische Fortschritt und algorithmische Fortschritte ja sie Rechner sind auch immer schneller geworden dann ein denselben Algorithmus einfach auf heutigen Rechnern genommen auf damaligen und kann zu melden ganz gut vergleichen die kriegen die Rechner sind zumindest gemischt Anzeigeprogramme betrifft in den Faktor 1600 Größenordnung schneller geworden aber die Verfahren die Algorithmen sind Faktor 2 Inhalt oder 3 Tausend schneller geworden das heißt man in derselben Zeit doch durch Verbesserung der Algorithmen der Struktur ausnutzen und doch Analyse der mathematischen Modelle und deutlich höheren Faktor rausgeholt als sozusagen 10. Hardware und das ist was was man immer
auch bedenken sollte wenn man Algorithmen entwickelt nicht nur warten bis der schneller Rechner kommt und sondern es macht immer Sinn sozusagen über die Algorithmen selber nachzudenken versuchen die zu verbessern da steckt eigentlich mindestens das gleiche Potenzial wenn nicht noch mehr über das interessante ist den Fortschritt kann man jetzt multiplizieren wir nicht 1 Tausend 600 Mal die 2800 oder was nehmt Angry irgendwas im Bereich 5 6 Millionen Faktor schneller als vor 15 Jahren war heißt was vor einem Tag nicht berechenbar war ist jetzt im Sekundenbereich Flächenbrand und da sieht man sozusagen was da wirklich auch so lesen was das auch für die Anwendung bedeutet ja konnte man vor 15 20 Jahren vielleicht nur Probleme lösen die wirklich von Planungs Natur sind bin ich sozusagen größere Standorte bestimme Fabriken Bau oder dergleichen weil eben die Rechenzeiten mindestens ein Tag vielleicht die Woche oder länger dauerten zu 10 Sekunden bereiten kann durchaus online Entscheidung als in Echtzeit sozusagen Optimierung ist Problem gelöst und damit auch in Echtzeit sozusagen die Ergebnisse einsetzen also das sieht auch sieht man sozusagen sich da man sich viel getan haben damit auch die Akzeptanz in der Praxis deutlich größer geworden ist so viel vielleicht auch nochmals nach haben dann als als 2. Aspekt noch als 2. exakt das Verfahren dynamische Programmierung kennen gelernt dynamische Programmierung hat eigentlich 2 wesentliche Aspekte des eine ist was bei dynamischen Programm da immer der Fall ist ist dass es des gleicht der des Kindes über die Laufzeit anschaut dass geschicktes E-Nummer tionsverfahren aber das Innovations Verfahren ist so dass sie auch tatsächlich alle Fälle durchprobieren muss wenn sie einen Rucksack nochmal denken muss für alle Kapazitäten und für alle Gegenstände muss die komplette Matrix doch arbeiten dann hilft messbar City oder sonst irgendwie abschneiden Baum den gibt es dann nicht mehr wie bei Brand bauen sein Prinzip auch tief aber durch geschickte Lichtschranken kann ich da große Teile dieses exponentiell großen Baums abschneiden bei dynamische Programmierung nicht der Fall da ist sozusagen die beste Laufzeit leichter schlechtesten auf Zeit das muss man immer im Hinterkopf behalten auf der anderen Seite weiß man auch die Laufzeit explizit und da haben wir ein schönes Beispiel gesehen beim Rucksack wo eben als Laufzeit n mal b auskommen wobei die die rechte Seite ist das Wehklagen im Sinne der Komplexität dies exponentiellen Eingangsgröße aber wie es in der Praxis häufigen kleine wir haben da wie ich es mir sagen wenn zum Geldbeträge geht ist dass ich mein Budget einen 1. Player das ist ne Million das heißt also Milliarde seines Pina 10 Computer ja also wenn um reale Daten geht dann wenn dann verschwinde dieses B dem große O sozusagen dann hat befassen einen Algorithmus also deswegen kann es durchaus sein dass dynamische wurde mir durchaus für spezielle Anwendung unheimlich schnell läuft und Rucksack ist ein solches Beispiel was sich letzte Woche angeguckt haben gut so weit als Rückblick nochmal gibt es dann nochmal Fragen zu den letzten Vorlesung gut wenn das nicht der Fall ist hat der die Nicole Nowak letzte Woche angefangen nein indes letzte Kapitel einzusteigen was ist da die Idee zu zu sagen was wir haben und das Mehr wenn wir optimale Lösung bestimmen wollen gibt 2 Möglichkeiten sozusagen das eine ist wir wollen wirklich die exakte Lösung bestimmen die globale optimale Lösung dann müssen wir aber exponentielle Laufzeit in Kauf nehmen an das sagt die Komplexitätstheorie die mich ganz sein Programme gehören zu dem Bereich der endlich schweren Problemen das heißt solange diese Frage ist P gleich NP nicht geklärt ist gehen wir eigentlich davon aus das wenn ich die geht optimale Lösung will in es Käs exponentielle Laufzeit so ist kann ich mich aber auf der andern Standpunkt stellen was passiert denn wenn ich dieses dieses dieses hohe Ziel die global optimale Lösung zu finden auf gehe und sage ich bin ich bin eben nur einer guten Lösung interessiert aber ich nicht garantieren dass sich in schneller Zeit fertig werden also ich möchte sagen garantieren dass ich nur polynomial Laufzeit verwendet kann ich dann irgendwas Aussagen über die Garantie der Lösungen wir haben heuristische heuristische Verfahren kennen gelernt die Kri der klar Polen lesen haben wir gesehen dass Kritik zum Beispiel genau dann die optimale sind findet in Essen Madrid ist und jetzt gehen wir ein Stück weg sagen wir wir wollen's nicht genau charakterisieren das optimal des Empfindens sondern wir können vielleicht garantieren kann ich Ihnen die diesen Faktoren kommen ja und dann sind in der Welt diese Approximation sverfahren das heißt gegeben Stück von der Güte auf der verlassen die Optimalität aber wir wollen sozusagen den Fehler den man machen noch einstellen und am besten eine konstante einschränken und sagen ok ich erlaube mit Faktor 2 schlechte Lösung ab ich weiß ich bin garantiert in kurzer Laufzeit werden ja und da werden wir uns jetzt ein paar Beispiele auch anschauen dieses dieses Prinzip kann man kann man noch erweitern indem man sagt es waren dann die die Approximation Schemata und voll als Approximation Schimmer was er letztes Mal die Definition angeschaut haben einmal gesagt ok vielleicht kann ich auch Algorithmen entwickeln die nicht wo ich die mit der Genauigkeit selber einstellen kann ja also ich sage ich möchte garantiert nur maximal Faktor 1 , 5 x 1 Jahr oder nur Faktor 1 Komma 1 oder was auch immer ja und es ist klar dass ich so wenig wie höhere Genauigkeit ist muss sich irgendwo in der Laufzeit widerspiegelt weil ich keine Aussage möcht hat 1 , 0 muss eine exponentielle Laufzeit auskommen muss irgendwie exponentiell in diese in dieser Genauigkeit sein und das ist das was mir auch darauf geschrieben haben Pop wollen immer alles Approximation Schirmer ist dann 1 wo ein diese Genauigkeit als bei nicht interessiert aber in den Laufzeiten geht es exponentiell natürlich ein und die Frage ist was kann ich denn am besten erreichen das Beste was ich das erreichen kann sie diese voll Polen JAL Approximation Schemata als ich kann maximal erwarten wenn ich dieses Epsilon vorgehen wie genau ich will dann kann ich maximal Polo polynomial in der Kodierung sein das Problem sein um den einzusetzen man würde erwarten dass eigentlich die liebe ich da stehen Kodierung Klänge von einst doch Erzählungen aber das geht gerade nicht mehr weil dann weiß ich dass sich das Problem auch gleich global optimal lösen kann in Polen aller Zeiten das ist der 1. Satz im uns dazu angucken wollen wir also Sicherheit vielleicht nochmal das Sicherheit das war wie die Kernpunkte von dieser Definition vom letzten Mal hin das war also in Kapitel 6. Approximation sei Algorithmen und hatten 3 Definitionen die 1. aber ist Apps an Approximation so Algorithmus war es aber ebenfalls aber polynomial ist und b die Lösung also C ist kleiner gleich Epsilon malt sie Orte bei minimiert uns Probleme schade denn genehmigungsfrei hin der Maximierung ist entsprechend größer gleich y mal war also wichtig an dieser Stelle 2 Dinge ich will Polen im Jahr als sein also schnelle Laufzeit und ich nicht das garantieren das ist die eine Geschichte das war der Teil der Weber reisten pro luminales Approximation Schlemmer ja welchen jetzt Epsilon vorgeht falls einmal Art Polen ja läuft ja wir Pollen nun Neal und B Güte Garantie ist 1 +plus Erzählung bisher sehr 1 -minus für feste Sätze wir also ich wieder Polonia lität umpolen
malität nur in der Kodierung Länge ja von wie wäre das Erzählen selber geht nicht mit einem die Laufzeit typischerweise kriegt man dann irgendwelche Laufzeiten einst ich erzielen hoch n oder irgendwie sowas was an sich nicht vor dem Jahr der aber des wird sich nicht in der Laufzeit wir so und das 2. und das Beste was man sozusagen erzielen kann es dann sinnvoll Polen immer alles er also das wollen nicht dass er steht nicht für voll sondern für Foley polynomial im englischen ja wurde Polen Proxy mäßigen Skin so und das ist das Gleiche wie oben also falls Sie haben polynomial und jetzt aber in der Kodierung Zwänge und eben 1 der Erzählung und eben wieder Güte Garantie hat und mit der Garantie 1 bis E also das waren das waren die 4 die mir die wir kennen gelernt haben was natürlich und wie schon gesagt wenn die am liebsten hätte wenn sozusagen die alle die Laufzeit Polen gerade wenn ich hier auch noch so n die Kodierung seinen schreiben könnte also wenn da nicht das allerbeste und man fragt sich natürlich zunächst ja warum ist es nicht die nächste Stufe der dass ich hier jetzt auch noch die Kodierung Länge schreiben kann und es gibt keine des Fall man uns keine des Fall gibt es sagt der nächste Satz weil wenn nicht den die Falle hätte den ewig gleichen Polen ein Algorithmus für mein Problem dem Zeugnis der Satz 6 2 0 also seit G ein diskretes Optimierungsproblem also gibt es 1 es passt das polynomial in der Kodierung Sleng Länge von Epsilon ist wir und dann dann existierten wollen Algorithmus für Kieselstrand gut und wir machen wir das ja die Idee ist einfach geschickt sozusagen wenn ich so ein Ding habe zu geschickt mit dem des Algorithmus zu spielen und zwar ich kann das Epsilon selber wählt er und wenn ich jetzt sozusagen polynomial in diesem Erzählungen denn da wenige selbst und so geschickt dass man Algorithmus so nah dran sein muss dass sich praktische Optimallösung ab bis auf bis auf der A 1 bei mir sind es geht optimiert wurden wir können davon ausgehen dass es die Funktion ganzzahliges das heißt es ein sie was ich schaffen muss ist dass ich mit meinem F Pass bis auf 1 ein optimales und und ich mein Epsilon geschickt genug will dann kann ich es Ärzte und Pollen und Yale wählen in der Kodierung des Problems und bin aber maximal um diesen Ei um diese ein Zweck und damit weil sich das Ding muss die optimale so werden so und das ist genau der Beweis dazu also werden wir konsolidieren und einfach neues wenn man ein neues Verfahren angegeben dieses F passen es war ja so aber ein solches es passt .punkt für die war noch Folgendes 1. Schritte wir setzen Apps gleich Inhalt und wenn man aber auf das iOS an ok ist der 1. Schritt und jetzt kommt der 2. wo man dieses stellt der Verein genug wären es noch mal einfach die Lösung die wir hier ausgesprochen gelegen wir +plus 1 aber gleich sehen dass genau das tut er jedes 2. Delta oder mein 2. Epsilon zu befreien will dass ich dann bis auf 1 genau daran werden und das ist das was wir machen so und jetzt aber auf wie mit Güte und Alter an ja und sei sie aber Modell davon E die Lösung wenn wir zeigen jetzt erstmals behaupten Behauptung ist mehr das genau diese Lösung C A von der davon I =ist gleich c oft waren so als 1. das überprüfen wie ist hier steht er noch mal damit wir übergehen F Pass haben müssen überprüfen ist alles Polen ja was wir hier gemacht haben das offensichtlich jeder Fall Zusammenhalt ist in Ordnung aber oft ist eben als sicheres polynomial die Zahl ist auch polynomial ja warum wir die die Funktion was rausging muss mit polynomial Größe sein sonst könnte das Verfahren oben Polen sein das heißt dieses Delta ist Polen und damit es hat dich dieser Schritt auch wieder polynomial weil ich ja mein Algorithmus läuft der polynomial I und der Kodierung Zwänge von diesen dem was dann wieder Polen hat es also das ganze Dennis polynomial also 1 bis 3 sind polynomial ist das 1. so und das so einfach überprüfen was passiert wenn unser Ziel Funktion wir schauen uns mal den Wert von optimale Lösung an dass sich auch so schreiben kann soll die optimale Lösung ist sicherlich mindestens so gut wie das hier was der Algorithmus Ausspruch spuckt also von der von E wir dann von dem Wissmann nachdem das Ding Approximation so Algorithmus ist ist der kleiner gleich 1 plus Eltern mal sie ob von I ja das ist genau die Wasser Elftal sagte er stets nochmal die gütiger entließ eines besetzten Landes welche die das als das Delta soll setzen zum einfach Geld dahin ist nix anderes 1 plus schreiben ab 1 durch CA das soll ich das selbst machen CIA y von IE +plus 1 mal sehen ob der von E so jetzt hier schätzt man das Ding ab also wir wissen Folgendes das sicherlich an dieser Stelle ich als dass man den das ist echt kleiner als 1 plus 1 durch sie ab von ihm mal C ob von i ist der Fall wer dieses C ob das ist sicherlich echt kleiner als dieser wird hier eine sie ab von Epsilon ist er größer gleich als das hier damit sie ob es sicherlich kleiner ich da noch 1
drauf weil die also hier geht natürlich ein dass C ganzzahlige ist also die optimale Lösung C a in der Eizelle und ist +plus 1 ist ist echt größer als dieses C ob und dann wirklich das alles umgedreht hier genau dieses kleine Zeichen hin dass Bau ist nur der fertig schreiben das ist nichts anderes als sie ob von ihm +plus 1 ok sondern wir das ist nochmal anschauen hier steht sie ob ja hier steht die Lösung die ich gefunden hab hier steht ein echtes kleiner und hier steht sie ob von E-Plus 1 so und nachdem die die Zielfunktion 18 C ganzzahlige Swissmedic Zielfunktion optimal Zielfunktion ist auch ganzzahlige nachdem hier echt kleiner steht bleibt dem gar nichts anders übrig als genau dieser Welt zu sein also das heißt wir uns doch mal die Definition anzuschauen wie gesagt dieser des Fall macht keinen Sinn so zeigen dass wir hier fordern dass das Ding auch noch bringen in etwa ist es heißt das ist wirklich das beste sozusagen was man erwarten könnte und wir werden jetzt Beispiele kennen lernen und der schauen einfach mal so ein paar Fälle an wie wir jetzt wissen wie einst in diese Kategorie wir werden uns einige zu diesem anschauen und das ist sehr beliebt diese Polonia Approximation Schüler gibt es deutlich weniger der dort wo es gibt ein sehr schönes Fest Rucksack Problem das haben 2 sehr muss halt nur schaffen gesperrt es dann am Mittwoch anschauen und für diese ganze Welt diese Approximation so Algorithmen da gibt es nicht wir ähnlich große Trickkiste wie man dort verwenden kann unser jegliche Garantien zu bekommen und wir schauen es Eintr exemplarisch in diese Trickkiste rein und schauen uns ein paar solcher Techniken an ganz bekannte Beispiele wo häufig verwendet wird ist es geduldigen Problem also wenn es nur darum geht Shops obwohl die Maschinen zu verteilen oder Jobs an Personen zu verteilen und dann versuchen möchte sozusagen mal die die Produktion sei dass sie maximal Produktionszeit zu minimieren des und typisch typische Anwendung man muss sowas gerne verwendet wird es gibt aber auch genauso bei bei anderen Fragen also es gibt aber auch was ich sagen wollte das Problem wo sowas nicht gibt also was ein was auch interessante Fragen im Zusammenhang ist was ist dann sozusagen das beste was man erreichen kann also das beispielsweise Steiner Baum Problem genannt wenn also Steiner brummte Dennis es folgen dem Grafen ich habe ich habe Teilmenge der Knoten ich gerne miteinander verbinden möchte aber wenn Sie sich erinnern könne ein Weg Probleme sich gibt 2 Punkte vor dem mächtig miteinander verbinden dessen weg oder war das beim Ausspannen Baum kennen gelernt ich hab ne Menge von ich alle Knoten miteinander verbinden auf kürzestmögliche Art aber gesehen dass der Collider optimale Lö Optimalität liefert und ich 2 Punkte verbinden Bilder liefert der Geiselgangster ganz fest aber mit dynamische Programmierung auch gesehen dass die das auch in Polen Jan Algorithmus das heißt die 2 Extremfälle 2 Punkte verbinden Grafen geht schnell und alle .punkt dem Grafen verbinden geht auch schnell jetzt machen möchte ist mir die beliebige Teilmenge vorgeben was genau diese Teilmenge nur verbinden das haben wir dann das Steiner Baum Problem und sich genau zwischen diesen beiden Polen Jahren fehlen da und da zeigt sich dass dieses Problem endlich schwer ist also das ist ja es anscheinend sieht bewiesen worden dass dies diese Zwischenbereich schwer ist sondern an die Leute versucht anzufangen Approximation so Algorithmen zu entwickeln da keine wie schnell auf ein der 2 approximativ ist als Faktor 2 kann man sich noch ganz gut überlegen unter gewissen Voraussetzungen aber diesen also zum Beispiel dass die 3 expedieren gilt kann man den Pollen Yale kann man in polynomial derzeit eine Lösung finden die maximal zweimal so schlecht ist sondern fangen die Leute an zu Bett eifern und immer bessere Approximation es Garantien zu finden zwischen auf 1 Komma 6 3 8 oder irgendwie sowas also in über 100 Meter Lauf nahmen an ,komma 7 8 oder 8 7 oder was es gerade Rekord 7 7 oder 7 5 fängt da an genauso bei Approximation sei würden was der 2. und 3. Nachkommastelle immer noch mehr die Ideen noch mehr sozusagen Algorithmen zu tunen um die besseren um noch eine besseres Epsilon dorthin zu bekommen umgekehrt stelle sich die Frage wo ist denn wie weit kann das maximal je der Hundertmeterlauf wird vermutlich nie Mensch gehen 5 Sekunden läuft also irgendwo ist eine untere Schranke und können für manche Sachen kann man hier unterscheiden angeben also es gibt auch so aus sagen wir dann sagen ok wenns denn wenn Erzählungen gibt was sagen mal kleine 1 Komma 5 ist dann hab ich auch wieder so eine Aussage wie hier ein kleines Problem auch gleich in Polen an der Zeit ist das heißt es es endlich schwer unter der Schranke von so und so zu kommen und da gibt es auch in diesen Literatur dazu die können auch in dem Umfang ja alles machen ich will ihn einfach so ein bisschen Einblick geben was was in dem Zusammenhang gern und viel gemacht wird und was ein paar Tricks sind umso wenigstens von davon kennenzulernen und und ein wollen uns gleich im nächsten anschauen sehen gleich 2 Ticks auf einmal die Überschrift des randomisierte Verfahren was man gerne tut in solchen Fällen also bei sehr heuristischen Verfahren ist zu würde fehlen ja weil häufig was passiert wenn man sich nur lästige anschaut wenn man sie macht wenn man verschiedene Beispiele rechnet gern immer denselben Fehler war weil man an der einen Stelle auf runde oder abrundet oder nach welchen Kriterien sich überlegt darf ich geh ich liegen sehr gehe ich nach rechts und es bleibt ein für viele Fälle so hat auch egal ist ,komma anwenden wenn ich irgendwo bin deshalb hier häuslich sich schlecht verhält dann ist es häufig an den gleichen Stellen das Problem ist natürlich kann natürlich auch wenn ich die Entscheidung jetzt ändere und Sager starben nach links auf wie nach rechts in willst damit wirklich war es gibt wieder entsprechend viele Beispiele wo es genau anders besser werden und n aus ist Zusage gebe es in den weißen Höflichkeit da ich lass es dem öfters laufen schnellen Algorithmus hab ich den in der Welt der Polen ja allen also wird man das er ich hab schnelle Laufzeit also dass sich das Ding halt öfters laufen dann stelle ich mir den Schein kann würde ich wenn es oft genug über offene Laster Bergischer irgendwann mal richtig gewartet haben und das kann man dann auch mal den man nachweisen sozusagen den ist lang genug laufen lassen dann randomisierte Verfahren dann schaff ich tatsächlich dass ich richtig würde sollen jetzt das immer noch ein Nachteil dass in einem wie sie das Verfahren hab ich muss ein Würfel und versucht dann weiß ich auch nicht wie oft ich den Befehl muss damit in gutes Ergebnis gelegt dann kann er wieder nur Aussagen machen wenn er Bridge also im Erwartungswert bin ich gut aber für viele solche Fälle kann ich dann am Schluss wieder die Randomisierung also ich sag ich zu für die Analyse der nicht dem Zufall ein dann kriege ich vermutlich um das Thema auch gleich ein Beispiel sehr gute Ergebnisse und dann versuche ich diesen zufolge heraus zu generieren und das ist das was Moses mein Beispiel anschauen wollen das 2. was wir damit gleich auch noch haben mit also das ist ein Blick in diese Schublade sozusagen fördern wir Approximation 1 und 2 der oft verwendet der Trick ist dass es allen wie die Mächtigkeit von linearen Programm zu verwenden Hermann modelliert erstmals ganz Tagesprogramm allerlei ziert das zum linearen Programm und wir wissen ja alle gerne Programme kann man können aller Zeiten ist sei es die ganzen Mächtigkeit des lösen linearer Programme kann ich ausnutzen und jetzt muss ich eine auch wenn Lösung ich Glück habe sie ganz aber diese Fälle kennen gelernt ist wahrscheinlich ganzzahlig muss andere geschickt runden Augen bei der Lösung geschickt Runde ich 2 Effekte die ich kriege zulässige Lösung und ich weiß auch wie verlier ich doch das Runden ja doch das runden verlier dich was der Zielfunktion habe ich ganz gleichzeitig abschätzen wie viel ich verliere ich hab DLP-Lösung in der Hand und ist eine untere Schranke für die optimale Lösung wenn man solche Apps bestimmen wollen mir immer abschätzen wie gut kann ist das ob bestenfalls werden und das LPI gibt uns gleich mit Schranke die wie Gutes LP bis ist die dann zeige Lösung maximal werden kann damit ich 2 Fliegen erreicht bei tollen Jahre und ich hab obgleich sie die untere Schranke und das wollen wir uns jetzt diese beiden Tricks aus der Welt der Approximation so Algorithmen Scharbeutz zum genauen Solms geduldigen Problem an also 6
1 randomisierte Verfahren wir und der war als Beispiel folgendes Problem an also wir haben Maschinen im identischen Maschinen M 1 das Große im Kleinen mindestens 2 davon und so langweilig haben Jobs J 1 das Ende n auch mindestens 2 Jahre sowie am Mehr an die Entscheidung weil wir den Job also die Idee ist sagen haben hier meine Maschinen auf den wird irgendwas produziert M 1 bis ja und was ich jetzt hab es zusätzlich irgendwelche Jobs wenn nur 2 Farben guten und was sonst noch also der sagen wir wird eines der es braucht und wieso lagen im Job ihr 2 braucht ist solange ja wir meinen Job J 3 das vielleicht nur so lange und so weiter ja J 4 für die Frage ist müssen die einfach auf diese auf diese Maschinen verteilen war also müssen eintscheiden produzieren man über den Job nur oder nicht wenn nicht müssen wir Straw Kosten bezahlen ja meiner Produktionsaufträge haben und wenn wir den wohl lieber zu für müssen mich straf kosten zwar also das ist das er hat also jeder Job ja dort weil eh hat Straw kosten ich drauf Kosten E bei Ablehnung und wer Productions Kurszeiten und Produktionszeiten Ort so was mir jetzt also das heißt die Produktionszeit kann abhängen nachdem welcher Maschine ich den zuordnen ja bin ich denn hier zu Wort melden J 1 dann kann es sein dass der so lange braucht bin ich aber auf der anderen Maschine laufen lassen kann es sein dass er deutlich schneller läuft weil einfach die Maschine was also was auch immer das ist ,komma Umrüstkosten alle sitzen sicher vereinfachtes Schema das kann einerseits S 2 identische Maschinen zum 1 kann aber daraus sein dass vielleicht die eine mal schneller gelaufen lassen wird umso zu seine Kapazität Engpass zu vermeiden oder Umrüstkosten an der Stelle wir sind sozusagen in der Altstadt beendet wird muss vielleicht um den 9. beginnen auch irgendwelche Puffer eingebaut werden und dergleichen als besitzt einen immer Realität anschaue ist die Welt immer noch wie kompliziert wir schauen jetzt sozusagen aber wir alle Realität real Aspekte einbeziehen will wie kein so schönes also Partnersender der Unterschied zwischen das was muss sozusagen theoretisch das erreichen was man praktisch beziehen kann auf deine Zeit ist auch so dass in diesen Algorithmen sehr gute Idee stecken die man dann trotzdem auf die Realität anpassen kann also die ist einfach die Annahme so dass es durchaus unterschiedlich sein kann ja und wenn dem nicht so ist kann man sie alle gleich setzt es den funktioniert auch sozusagen in diese Zeit und dass sich gleich sind so was wir jetzt tun müssen ist einfach die Jobs sie irgendwie zuordnen wir haben hier den zweier was weiß ich da hinsetzen nein und dann 3 was soll ich aber sagen wir den Dreier setzt man hier hin ja und den 4 da und was wir uns angucken ist am Schluss der Macs Plänen also das ist sozusagen diese Zeit hier ja das ist das drehen ist das so genannte Macs also die Produktionszeit der langsamsten Maschine das Ziel ist das denn ziel ist es demnächst der und Kunden des also die Produktionszeit Hey langsamsten Maschine zu minimieren gut also unser Aufgabe er kann nachweisen dass Problem ist endlich wäre also ist es auch wenn es um Probleme haben hab ich auch schon mal gesagt ist immer die Frage was soll sie
denn als überlegen zu welchem Typ von Problemen gehört dass es könnte der sein es gibt kann schnell Algorithmus das Beispiel Kuli funktioniert da gut könnte er sagen ich neben den dicksten Job ja denn als bei sich zu alt Sudanesen 2. dicksten als nächstes und dergleichen Frage liefert das eventuell die optimale Lösung könnte er sein ja und überlegen was kann diesen komplizierten Approximation oder so voll Polenreise Approximation Schema und dann übermorgen kommt also der Moment Kritik Klicks auf das Ding also deswegen ist immer wichtig sich am Anfang Gedanken machen in welcher Welt bewege ich mich den bin ich in der Welt der polynomial Algorithmen und bin in der Welt der der schweren Probleme den Beschwerden Probleme und ich weiß ich bin in der Welt endlich Schwäne ist die Wahrscheinlichkeit sehr gering dass Malcom hallo das Ganze so und so lösen in so einer Kenner der gleichzeitig gelöst das P gleich NP ist ja gut kann pasieren aber ist unwahrscheinlich also deswegen ist immer wichtig erst mal sich vorab Gedanken zu machen in welcher Welt bin ich und ich hier in dieser Welt ist mir tatsächlich in der endlich Beschwerden Welt das haben 3 Herren nachgewiesen ich immerhin dass ist ja dem Satz 6 4 das gelte wegen Problemen es ist endlich schwer ist ein nachgewiesenes Kurt Heller Entschuldigung von erwürgen und Teller und würde ginge und zwar in das was in was im Skript ist die das steht das nur Kommuniqué scheinbar ich hab das damals 2000 Tote aus 1 war das war hat der Matthias Kurt Heller über das die einen Vortrag gehalten auf einer wissenschaftlichen Konferenz angesagtester eigene das Problem des das hat viele Aspekte wo ich gerade gesagt hat die grüner volles darstellen kann aber wenn ich diese Foliensatz schickt da leider auch gemacht deswegen steht der Moment es gibt dennoch Börse kommen die Kirchen aber inzwischen ist es auch veröffentlicht das wegen die ich hier der Vollständigkeit halber die veröffentliche und das ist das Publizieren das Programm in die Valium 94 in Seite 361 bis 300 74 und das Ganze im Jahr 2000 3 also man nachlesen will das Heft gibt auch in der Bibliothek kann das Orginal dazu gerne nachgucken also die auch den Algorithmus den ich jetzt dann erzähle entwickelt aber die sind genauso Vorgang nicht gesagt hab alte Firma versuchen Problem zu lösen so dass mal gucken welche Welt bewegen und uns ja also wissen offensichtlich in der schweren Welt und jetzt macht sind sozusagen Approximation sei gute Nacht den gut so wie Warner vor den ich aber gesagt überall ein dieser Tricks verwenden das ist sozusagen LP Information ausnutzen also um die Krim er ihn dazu brauch Mannesmann Gemisch ganz Tagesprogramm also brauchen wir Gemisch ganzzahlige Formulierung von dem Problem und dann können wir dazu die Apple-Aktie angucken also müssen und es erst mal Gedanken machen wie formuliert man das als ein Gemisch ganz Tagesprogramm ja das wäre also tu mir das mal formulieren als mit wir werden kann so war es was ist das ist formulieren als mit mir überlegt sich bei welche Variablen der brauchen also einmal was bei entscheiden müssen ist mir den Job überhaupt an ja oder nein also viermal so variabel erhalten y j gleich 1 falls Shop J gewählt wird um 0 sonst so wenn er gewählt wird muss man natürlich verteilen um den Job ,komma beliebig aufsplitten also wir können doch einmal Skilaufen an aufeinander und dergleichen mehr ja das heißt wir müssen diese Anteile festlegen dass die Namen XI Orte sozusagen leichter Anteil von Job oft offenbar schließen darunter unser eigene Zielfunktion dieser dieser Mehr Experten des den wollen wir minimieren also ist sind die brauchen auch noch TS da Experten ok so wie Sie das die Zielfunktion aus einmal wollen wir diesen Experten minimieren das ist dass sie aber andererseits das war wie unsere Straw kosten auch mit berücksichtigen das heißt wir müssen noch Summe über obgleich 1 bis n 1 -minus y er
hat warum ist dem so wichtigen Job nehmen und fallen keine an besteht in 0 also keine keine Strafe kosten nicht dem Stettiner 1 dann freilich auf Kosten die Zielfunktion es genauso mir aus diesem Index Band was diese Strafe kosten so also uns überlegen was damals für Randbedingungen als damals Randbedingungen Bedingungen man kann ja also an dass wir demnächst beim Modellieren oder das heißt wir schauen uns einfach mal auf einer Maschine an die Top sieht ausgeführt werden da das sehr größer gleich sein als das was auf einer Maschine läuft aber so hier gleich 1 bis Ende des Prozesszeiten wer kleiner gleich die und das für alle Maschinen I also auf einer Maschine läuft das die dafür höchstens so groß sein dass das dass ich mir die mir würde es auch an ja also wird sicherlich keine Lücke sei nach dass das ist minimiert das allein reicht aber noch werde ich musste mich auch noch garantieren dass nicht jeden Job 8 da sich komplett doch für das was ich da auch noch folgende Bedingungen dies gleich in denen nur wenig jetzt über alle Maschinen die also eh gleich 1 bis Ende dieses Ding muss auch kleiner gleich diese es offensichtlich ja dass dieser Mehr X-Beine kleiner gleich sein kann als bissig das ist sein Gesicht aus einem Produkt ist die Summe der Produkts also der der Produktionszeiten für ein Produkt bis auf verschiedene Maschinen verteilt zu groß muss es eigentlich auch sein warum mussten so sein ich kann meine können auf folgendes machen ich mach die eine Maschine gleich am Anfang nur also ich kann den PIN ein Shop parteilich gleich auf der 1. Maschinen erledigen damit schneller weniger dichtes die kleinen funktioniert hier nicht man kann es doch der Reorganisation kriegt man das hin das ist hat sich erfüllt sein muss nur weil ich kein Nebenjob beliebige unterbrechen oder jederzeit offen eine Maschine einsetzen ohne dass ich irgendwelche Übergangszeiten hat er und damit sieht man ein dass wenn ich die 2 Bedingungen tatsächlich hab ich tatsächlich diesen Experten variiert hat also das heißt es sind die beiden Bedingungen für diesen Experten also jetzt haben wir aber noch nicht getan als man es einmal so getan als würden alle alle wählen das dass er noch koppeln mit denen wir den Ablehnern waren so modelliert man 1. Hilfe dich einfach mehr nicht das kann man ganz geschickt in eine Ungleichung unterbringen nämlich wenig ein Shop anschauen in denen alle Maschinen ist es genau dieses y j was heißt das hier ist lange hat ist 0 wenn ich den Job nicht aus für das heißt da müssen auch mal alle Variablen 0 XI sind alle größer gleich 0 das heißt es ist eine wird auf 0 setzt für diesen Job nicht aus wenn es auf 1 setzt sowie die Anteile sich genau zu 100 Prozent zu 1 auch weil es genau das was mir gesagt haben dass der Anteil als der prozentuale Anteil der auf dieser Maschine durchgeführt und damit hab ich tatsächlich mein komplettes Modell und ich brauche den noch das y J 0 1 fertig ist ok jetzt fragen so der Modellierung so wie Sie dass unser Algorithmus aus Lammersmann deterministischen also erst Algorithmus dazu Algorithmus 6 5 bei der Mindestsicherung der Algorithmus also die Idee dass wir wir bestimmen die Apple-Aktie mir Herr sei also ick Stern y stand optimale Lösung der LP Galaxien war nur dass wir Polen mehr als kann Polen aller Zeitungen sollen es werden und Essen man muss ganz einfach nur sind da wahrscheinlich einige von diesen Variablen gebrauchen die Frage sehr jungen auch mal hier und mal ab begeben und es einfach ein alter vor zwischen 1 und 1 also Welle 0 kleiner als kleiner 1 sondiert und mal jeden Job in der Größe ist als alt war und Mehr auf einer kleinen das also um ab ganz simpel also alle Jobs J ja wer ist y Stern kleine gleich alles war während dann setzen wir y gleich XI Ort gleich 0 für Ali und ist y Stern größer als vor ja dann setzt man y j gleich 1 und des XI Orte setzt nur auf XI Art Sternburg YJ starten kann und das war's nun Schluss gibt X und Y aus dem also wir müssen sie aufpassen Dixie Orts müssen anpassen wenn er vorher
dann muss das Anschauen der viel zu mir der ich sie Stern gleich YJ Stern besitzt wird Stern selber muss er nicht 1 zu 1 ja damit wir diese Bedingungen hier wieder erfüllen müssen das sozusagen doch das YJ standhalten werde muss ein Instrument ist meine 1 ergeben das schaffen in dem man jeder doch das ist doch das YJ Stern teilen er dann steht hier die einen hier Städten Exilort standen YJ Stern damit summieren sich die genau zu 1 auf und wir können auch Teil meiner garantiert größer ist als denn das heißt es den wird auch so dass es da Algorithmus wir nachweisen so funktioniert haben nicht nein n ja wir wir haben es nicht ist also übrigens sehr beliebt dieser und ohne Geschichten habe ich vielleicht LP aus und je nachdem was ist für wert ist und nicht einfach auf oder ab allerdings kann man nur in ganz wenigen Fällen nachweisen dass man damit auch vernünftige Lösungen kriegt für allgemeine gemischt Anzeigen Programme wo man keine Struktur Aussagen hat greift dieses einfache und in aller Regel nicht ja ,komma ganz selten zu guten Lösungen gibt es eine Menge von Kälbern dazu dies alles versucht haben aber das nie richtig gelegt gut aber hier funktioniert und wir schauen uns an das ist nämlich lesen kann sind 2 Approximation sei bereit Algorithmus also Satzes der nächste Satz Satz 6 6 Algorithmus 6 5 ist 2 approximativ also das 1. was mir sehen polynomial ist da ja wir lösen Apple-Aktien Ispo Jahr und der Rest ist einfach unten also Polen Genialität das kein Problem also polynomial es kein Problem so es die Güte abschätzen dazu brauchen wir 2 Aussagen einmal gilt Folgenabschätzung statt dass man ihnen sagt was dazu ist immer kleiner gleich als 1 doch 1 -minus als war mal 1 -minus YJ Stern so warum ist das der Fall wäre mit Y J 1 ist dann ist es offensichtlich trivial Team größer gleich 0 dass auch interessante Fall ist das Y J 0 ist wenn YJ 0 ist dann schauen wir mal was passiert ja dann ist es y Stern kleine gleich alt war das heißt 1 Wissensbestandes größer gleich 1 bis 1 von kürzlich dass gerade weggekommen einst aus also die Umleitung ist okay der 2. ist X E J ist sicherlich immer kleiner als 1 doch Fahrer mal XI Ort stellen kann und ist das der Fall ja dass ich sie ab 0 ist ist auch die Welt in Ordnung das ist der 1. Fall denke die Ungleichung sicherlich immer wenn Fall ist der hier ja da wird Exilort gerade auf Exilort stand doch y Gesetz aber nur in dem Fall dass das y was soll über Jahrzehnte machen hier alles nur für den Fall dass YJ größer ist als alle vor mir und damit dreht sich das um das 1 doch bislang wird er kleiner gleich 1 Tag alt von der Michel auch die ungleichen so jetzt schreibe mir die Zielfunktion auf also die Zielfunktion Std "anführungszeichen Summe 1 -minus y je er hat ja gleich 1 bis n so und das hier ,komma abschätzen des tekammer abschätzen doch schauen hier steht noch nochmal wir doch einst doch als vermeidlich standen wir 3 hier hier einfach jedes XI Orte doch das YJ Stern ja und damit kriegen wir das auch hier oben die beiden deswegen Geklingel jeweils ist eines der Stern beziehungsweise die alle ist die unterschlagen dass also das heißt ,komma noch das Alter abschätzen als ist leider gleich 1 Tag alt war dann das ist der 1. Teil +plus 1 so jetzt die Geschichte hier aus ja dieses den Schatz wir doch das ab +plus 1 Tag 1 -minus als damals Summe 1 -minus y Stern er ab ok wird gleich 1 bis Ende solle Zimmer großzügig gehe je nachdem was Größe ist sondern mir kleiner gleich das ist Maximum als einst doch Alfa und eines doch 1 -minus Alfa um hier den gleichen Faktor zu bekommen so malte ich dann los Summe York gleich 1 bis N 1 -minus y wird
standen der Ort wir war so und das war's eigentlich schon mal das es uns unser die Lösung was in Klammern steht die Lösung ist immer mindestens so gut wie ganzzahlige optimale Lösung das heißt die können wir wir können wir leider schreiben ist kleiner gleich Marx eines der Wallfahrt 1 der 1 -minus als malt sie ob der ja und jetzt ist er die Frage ist es alt war mehr frei gewählt bislang einer Welle wären dann ginge die Güte garantiere aus das ist die Frage ist also wie damit man jedes Max möglichst klein gelegen während des ist mehr als vergleichen halte dass ich das genau gleich gehen ja und das ist gleich zweimal C ob für alle vergleichen halten an das heißt uns am Algorithmus um dann mal gar keine Fehler machen sondern einfach gleich als Offenheit setzen und gegen die die bestmögliche Garantie und so jetzt aber eigentlich in dem es um klassische Approximation sei muss zweier 2 Approximation Mehr wir haben Kollegialität wir haben in den sinkt die Zusage auch der Faktor 2 Leslie indirekt das das hier 1 sind polynomial und beging er klassische konstante erzwang gleich 1 oder 2 nachdem man sehen möchte und Hand garantiert in eine Lösung die höchstens doppelt so schlecht ist wie die optimale ist das ist die Frage können wir das Ganze noch verbessern und jetzt kommt eben diese Idee mit diesen randomisierten rein was ich über anfangs gesagt hat die haben wir jetzt einigen Parameter alpha hier stehen ja und was diese alles für der allenfalls ein nix anderes als sozusagen zu sondieren wer geht den Eliten Korber die rechten pro Jahr wäre in welchem shop welche nämlich nicht und das haben wir hier ist sehr stark gemacht dem einfach gesagt in Alter gleich einhalten ja wir können auch sehr billige Art und Weise einfach verschiedene Sachen hier probieren wie das Alter funktioniert ja welchen Viertel Dreiviertel oder sonst was will an also lass uns an dieser Stelle würfeln wir wissen etwas wirklich gut ist und es geschickt ist also wohl einfach ja und es kostet unser keine Zeit DLP-Lösung berechnen einfach aus 12 und Mann als und gucken was viele Lösung rauskommt und das machen wir beliebige oft Würfen beliebige dann die Frage scharf ist darf leidet sogar bei dieser wurde Optimallösung sogar dabei oder wie gut der dich dann ja und doch diesen Trick dass nicht ein und dasselbe öfters probiert ich hab es tatsächlich einen deutlich besseren fragte hinzu gelegen kommt sogar mit dieser Idee so Faktor 1 , 5 8 und das war zu sein dem Beispiel nochmal anschauen da sieht man also dieses Potenzial dieses ab randomisierte des 12. häufig auch in der Praxis auch immer so nachweisen kann hier kam es halt schön nachweisen aber die Idee an der Stelle wo ich Entscheidungen treffe und irgendwas fest die ja das ist ein typischer Fall für rüstigen wo ich halt immer ich normal funktioniert aber man aber genauso gut auf die Nase fallen und deswegen nahm an der Stelle würde würde und das beliebig oft laufen lässt dann der trefflichen Fall dabei sein der besser ist ja und das ist hier garantiert so und das häufig auch in der Praxis zu dass wir das machen und es kostet praktisch nix 1. lineare Laufzeit welcher tausendmal Würfel ist Kinderarzt .punkt sollte alles über das nur formalisieren würfeln ja was heißt nur Filme für eine Zufallsvariable ein ja und wir müssen jetzt Erwartungswerte Bildung gucken was dann als Erwartungswert auskommen also das ist der Algorithmus 6 7 das ist die randomisierte Variante wir sind wir waren in den 1. Schritt aber wie beim anderen also 1 wir lösen das LP ja so und 2. ersetzt würden wir da also für jedes ich weiß sein der vor das mal wieder rückgängig machen für jedes Alter in dem Intervall für die Zufallsvariable 1 ein sowie ihn bis 1 ja ist eine gleichverteilt Zufallsvariable hier sein so geschnitten mit y SYN Stern er für die obige stellte ausführe Schritt 3 aus für den Schritt 3 in Algorithmus 6 5 aus Herr so und das 3. geht die beste n Lösungen aus das das ganze Verfahren das habe da gleich mit 2 wichtigen ihrer Geschichte mit untergebracht nämlich mal schauen immer würfeln also das war ein CI will
dass es gerade am Schluss geschickte gewählt das was Vernünftiges rauskommt aber das einzige was wir jetzt mit der Beobachtung reinbringen ist Folgendes wir können jetzt
natürlich beliebigen zum Intervall Würfel ausschauen soll die Lösung an aber uns das genau anschauen wann geringe denn tatsächlich eine andere Lösung wir gingen und
dann der andere Lösungen des Alban einfach diesen Schwellwertes von NYC ja also nur wenn ich jetzt angenommen sagen wir die in der Größe nach sortiert ist ein steigender gleich 1 und 2 stehen und so weiter ich liege nur dann ne andere Lösung hier wenn ich jetzt über eine von diesen Schwellen übergeben das Alter zwischen 0 und y 1 oder Zuschüsse 2 und 2 und dergleichen ja das heißt eigentlich muss sich dabei würfeln es reicht nicht genau diese Schwellenwerte ab zu prüfenden wird dann gegen andere Lösung er aber um das zu analysieren die das diesen Weg über wir vergessen mal das machen dass
die Zufalls Analyse machen Erwartungswert und dann bis es tut sich noch was an der Quelle also muss ist wenn man jede gute Lösungen ausgebildet zu werden muss ist auch an ein von diesen entstellen schon passiert sei ja und damit kriegen wir den Zufall am Ende wieder los und das ist dann wenn diese der Randomisierung ok also schauen uns dass man den Beweis der zu also sei als Vergleich verteilte Zufallsvariable auf dem Intervall 1 doch eh und 1 ja dann gilt einmal für den Erwartungswert die Phontäne also gleich verteilt Zufallsvariable rechnen Erwartungswert aus sie sind immerhin Integral von den Grenzen 1 doch eh bis 1 man Ideal war ja damit dass der
Zufallsvariable es das Intervall hat Länge insgesamt weniger es 1 doch eh das heißt damit das hier wird sich zu 1 normiert müssen wir den Faktor egal immer so 1 dazu schreiben also das heißt Erwartungswert ist nix anderes als das Integral über die den Wahl Grenzen von dem Objekt die und das ist die Normierung auf 1 an sollte schauen uns an der Rissener dieser Erwartungswert =ist gleich r Gleiter aber gerade hier schonmal ausgenutzt ja dieses des wir also dass die was wir außerdem ist immer kleiner gleich als einst auch als normales des Stern das können wir sicher ein Schreiben das ist kleiner gleich jedoch II -minus 1 Integral 1 doch eh bis 1 1 Tag alt war der 1. die alles daran so dass dich dann ist jetzt ganz daran dass es eine Lösung die der man nach vorne ziehen so was ist dieses Integral was ist die Stammfunktion von einst sowie X ist log x dann haben wir hier Blog von Alfa an den Grenzen eines und 1 See Lob von 1 ist 0 -minus lockt von 1 wieder 0 +plus lockt von Elop von Essen 1 gemeine Faktor 1 was ist das Ganze gleich E doch -minus 1 Malti statt ja also die 1. Ungleichung Demirci reinkriegen ist die Sie hier kleiner gleich jedoch immer das einst Mathew statt so die Hoffnung ist dass wir das jetzt für den 2. Teil aber noch auf unsere Zielfunktion dass es für den 1. Teil des des ist ,komma dass die gleich Abschätzung Hoffmann dass man auch für den 2. Teil der Zielfunktion hinbekommen und dann haben wir dann meine Güte Garantie von Faktor e doch minus 1 kommen wir jede im 1 ist ungefähr 1 , 5 8 saß werden es signifikante Verbesserung gegenüber diese dieser Größe hier so den 2. Teil müsse es auch noch entsprechend abschätzen und da also ein bisschen mehr rechnen aber es aber bei der Bild ich war uns das mal an wir hatten also nur dass man sieht Sie haben den Teil haben wir ja den Hammer Grad abgeschätzt und in den Teilen des Meeres nur abschätzen wir und die Hoffnung ist dass wir diesen Teil im Erwartungswert auch wie dieser Zahl abschätzen können das ist unser Ziel und das Klima auch wir ich bin wir ich ich wir haben ja wir war also Erwartungswert und den 2. Teil der Zielfunktion Summe hat gleich 1 gesehen als wenn y J das vormals abschätzen noch als wir so ein bisschen bisschen Wahrscheinlichkeit nur minimal wir hier machen ja gleich 1 bis n so dass er hat also 1. Erwartungswertes linear werden das die wir können wir vorher rausziehen dass ihr Ort ist ja eine konstante das können auch noch ferne ziehen so bleibt also stehen Erwartungswert von 1 -minus y j Vista Erwartungswert von Eiswiese y und den Algorithmus nochmal anschauen wir wohnten ab wenn es y Stein kleiner gleich alt war ist und wir wohnten auch wenn größer ist wenn es heißt es ist leider jede Wahrscheinlichkeit ja das YJ Stern kleiner gleich als Alfa ist nochmal also wir haben wir brauchen den Erwartungswert Frauen aber die Wahrscheinlichkeit dass sozusagen dieser wird hier 1 ist das ist die Wahrscheinlichkeit dass dieser Wert 1 ist es genau der NY Stein kleine gleicht dem Alfa es war dann dann rund nur das y ab verschiedensten gleich 0 und dann wenn ich traf Kosten fällig so das heißt es müssen ausrechnen wenn hinschreiben Summe gleich 1 bis n Art so wie ich mir diese Wahrscheinlichkeit aus dass ist Wahrscheinlichkeit also alle weisen sie Zufallsvariablen und das geht eigentlich von YJ Stern bis 1 ja mal in mal den Fakten schaffe ich mal die Innereien des Alfa kann sie gleich verteilte Zufallswahl bis in GAL von stand 1 dass genau dieser Plan von meiner Zufallsvariablen das muss ich aufpassen eine Zufallsvariable nur ab 1 Ei läuft also muss ich hier schreiben also eh Max ja aber es könnte sein YJ Stern ist es YJ Stern ist kleiner als das 1 sowie ihren keiner richtig Zufallsvariable das der erst ab 1 RWE da also damit aber das korrekt wiedergeben will wiedergegeben zum aber großzügiger und verzichten auf auf das eine Story in schreiben da doch kleiner gleich Summe ja das gleich 1 bis n j Integral von YJ Stern bis 1 er jedoch éliminés 1 die Alfa so das ,komma nach vorne ziehen nun das ist eine Konstante nach vorne steht in der Gral von y stand 1 über 1 der Alfa kämen und alles ist Inhalt ist das also das ist so meine J gleich 1 bis N e J die doch im minus 1 und das ist nix also das 1 -minus YJ stand dieses in und also dieses Integral über der 1 ist genau dieser Anteil wäre danke so dass sie nur nach vorne das ist eh doch eben wie das eines Summe J gleich 1 bis n Ort 1 -minus y 1. Stern und die Welt ist in Ordnung ja genau das was wir hier brauchen aber wieder mit diesem Faktor haben reisen er für den 2. Teil der Zielfunktion hier da muss es anschauen Erwartungswert hier ist kleiner gleich sozusagen diesen Teil das heißt insgesamt wenn das heißt der Erwartungswert von meiner Lösung Summe J gleich 1 bis n die J 1 -minus YJ es immer kleiner gleich E -minus 1 mal sie oft nun wichtige zienzfaktor doch eh -minus 1 sind es ungefähr 1 , 5 8 wir war also wir sehen da 2 Dinge das eine ist und das sieht man diesen schönen an dem Beispiel ganz gut das eine ist aber wir viel erreicht man wirklich was also dass jetzt erst mal was mir als haben das ist alles besetzt Zufalls basiert also der Würfel ja mit ihnen Erwartungswert was raus haben Erwartungswert Zimmer mindestens so gut das heißt wenn Erwartungswert Männer so gut es muss es mindestens eine Lösung geben die so gut ist ja wir können der die Wege lang Würfel und beging ständige Lösungen die schlechtesten 1. Erwartungswert der Erwartungswert der er also damit ich diesen Erwartungs damit sich dieser Wagen fährt da sicher realisiert muss es Lösungen geben die mindestens so gut sind wir vermutlich auf die deutlich besser sind damit mehr Mittel wieder diesen Wert erreichte das heißt wir müssen jetzt im Moment an dieser Stelle ja es gibt Lösungen die mindestens so gut sind was wir nicht wissen Sie lange würfeln müssen wir es keiner sei nicht nur für 3 Milliarden Mal es kommt als meine Lösung aus die schlechter ist als die Serie hat dafür kommen die nächsten 3 Milliarden mal 1 der besser ist das ist an Zufallsvariablen dass man nie weiß er wann sich was realisierte so und jetzt gucken wir noch mal zurück ja und schauen dann tut sich denn wirklich was bei uns umrunden deswegen habe das hier schon mal mit eingebaut es kann ja tatsächlich nur andere Lösungen aus an diesen Schnittstellen und so und das heißt wir müssen da sich dann der hunderttausendmal würfeln sondern es reicht sozusagen indem man den Lehrern Domizil in dem man das Alter für genau diese Punkte trifft ja der Randomisierung erreicht man dort gibt es nur wenn wir in dem man als Fahrer aus y 1 Stern bist sie dann n Sternenwelt also alle ja gern ausgerechnet im waren die Lösung ist das wir wissen es gibt aber nur in verschiedene Lösungen und wir rufen alle nach dem Erwartungswert kleiner gleich dem der das muss eine von diesen n Lösungen mindestens so gut sein wie der Wartungs ja und damit aber insgesamt jetzt sogar in ihren ist sich mit einer rein deterministischen Algorithmus der sagte er ,komma 4 2 sozusagen noch besser ist als die 2 Approximation das heißt doch ehemaliges aufrufen das orginal schaffen wird sich deutlich bessere Güte und es ist so es ist typisch für diese Art von Algorithmen und das liefert ein aber auch gleichzeitig die des das juristische Verfahren allgemein probieren nicht nur sozusagen eine Variante wenn man sich nicht entscheiden kann so und so viel an dieser Stelle und man kann dann häufig nachweisen wir sicherlich etwas theoretische Beispiele wie hier aber häufig funktionieren diese Dinge dann auch in der Praxis dass aus diesen Ideen die überall Approximation sagen kommt aber wie auch viele für praktische Verfahren heutige Runde Verfahren wie gemischt Anzeigeprogramme über übersehen zwar häufiger auch auf diese besiegten Idee zugrunde da will ich sagen dass er 2 Minuten zu früh dran aber es lohnt sich jetzt immer den nächsten .punkt anzufangen bedanke mich geholt und schönen Tag noch und bis Mittwoch
Parametersystem
Faktorisierung
Untere Schranke
Obere Schranke
Prozess <Physik>
Mathematik
Momentenproblem
Laufzeit
Blackbox
Heuristik
Zahl
Computeranimation
Rechenbuch
Kerndarstellung
Größenordnung
Schnitt <Mathematik>
Optimierung
Struktur <Mathematik>
Geometrie
Numerisches Modell
Länge
Faktorisierung
Matrizenmultiplikation
Dynamische Optimierung
Laufzeit
Baum <Mathematik>
Besprechung/Interview
Empfindlichkeit
Heuristik
Optimierungsproblem
Aussage <Mathematik>
Optimum
Zahl
Komplexitätstheorie
Kapazität <Mathematik>
Lösung <Mathematik>
Exakte Lösung
Rechenbuch
Vorlesung/Konferenz
Optimierung
Mathematische Größe
Ebene
Faktorisierung
Zusammenhang <Mathematik>
Große Vereinheitlichung
Laufzeit
Besprechung/Interview
Optimum
Erwartungswert
Meter
Randomisierung
Offene Abbildung
Zielfunktion
Vorlesung/Konferenz
Untere Schranke
Dynamische Optimierung
Gruppe <Mathematik>
Physikalischer Effekt
Heuristik
Aussage <Mathematik>
Umfang
Teilmenge
Menge
Würfel
Rundung
Total <Mathematik>
Momentenproblem
Welle
Formation <Mathematik>
Randbedingung <Mathematik>
Biprodukt
Summe
Index
Variable
Vollständigkeit
Ungleichung
Vorlesung/Konferenz
Zielfunktion
Parametersystem
Faktorisierung
Laufzeit
Welle
Besprechung/Interview
Aussage <Mathematik>
Maximum
Entscheidungstheorie
Summe
Lösung <Mathematik>
Erwartungswert
Ungleichung
Menge
Zufallsvariable
Würfel
Vorlesung/Konferenz
Zielfunktion
Lösung <Mathematik>
Erwartungswert
Zufallsvariable
Würfel
Randomisierung
Vorlesung/Konferenz
Integral
Faktorisierung
Länge
Punkt
Momentenproblem
Zahl
Gradient
Integral
Konstante
Mittelungsverfahren
Summe
Lösung <Mathematik>
Erwartungswert
Stammfunktion
Ungleichung
Würfel
Zufallsvariable
Rundung
Randomisierung
Abschätzung
Vorlesung/Konferenz
Zielfunktion

Metadaten

Formale Metadaten

Titel Randomisierte Approximationsalgorithmen
Serientitel Diskrete Optimierung (Optimierung II)
Teil 21
Anzahl der Teile 26
Autor Martin, Alexander
Lizenz CC-Namensnennung - keine kommerzielle Nutzung - Weitergabe unter gleichen Bedingungen 3.0 Deutschland:
Sie dürfen das Werk bzw. den Inhalt zu jedem legalen und nicht-kommerziellen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen und das Werk bzw. diesen Inhalt auch in veränderter Form nur unter den Bedingungen dieser Lizenz weitergeben.
DOI 10.5446/31793
Herausgeber Technische Universität Darmstadt
Erscheinungsjahr 2009
Sprache Deutsch

Inhaltliche Metadaten

Fachgebiet Mathematik

Ähnliche Filme

Loading...