Logo TIB AV-Portal Logo TIB AV-Portal

Descision-Based Approaches - Constraint Programming / Dynamic Programming

Video in TIB AV-Portal: Descision-Based Approaches - Constraint Programming / Dynamic Programming

Formal Metadata

Title
Descision-Based Approaches - Constraint Programming / Dynamic Programming
Title of Series
Part Number
10
Number of Parts
12
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.
solution sets strategy Raumen topology Mean-Field-Theorie neighborhoods Ecken Lösungen variables localization subset
Zahl topology Laufzeit feasibility variables current
Zuge constraints logical consistency constraints spiral Lösungen sets variables variables domain solution sets logic image space reduce
logical consistency constraints Graph variables image space variables current domain
logical consistency constraints Graph bin image space variables current variables reduce domain
Kanten logical consistency constraints Graph sets bin image space variables reduce current domain
Hyperraum Raumen logical consistency constraints Graph form bin variables variables domain graphs Integration logic graphs vertices Quote current hyperplanes
logical consistency constraints Graph sample canonical bin variables variables domain fraction spacetime validation image space reduce current
topology logical consistency constraints Graph Quote bin reduce variables current domain
Continuous function logical consistency constraints Graph real form inequalities variables subset domain strategy topology graphs heuristics vertices image space hyperplanes rules bin variables Integration topology Ecken reduce current
matrix constraints directions structure End Normale Hidden Markov model structure variables number subset großer domain sequence chain mathematics Matrix scalar heuristics Dimension aerodynamic design Recursive multiple Kette rules Pascal deoptimization multiple moment Laufzeit matrices program undecidability product gute scalar contrast topology Berechnung optimal matrix Faktoren
Difference equations Zahl bottom matrix structure chain Matrix Dimension Recursive category multiple multiple Produkte Ranges matrices bottom undecidability product similar Berechnung Optimum optimal integer matrix Recursive
Difference equations matrix structure Ranges matrices bottom product number similar chain Matrix Optimum iterations optimal integer category matrix multiple Recursive
Difference equations job string indicators Multiplizität <Mathematik> matchings sequence chain mathematics Erweiterung loss string Dimension form spacetime Länge comparison multiple deoptimization Errors sets bottom program undecidability product similar logic functions Optimum matrix
job string indicators matchings sequence substitutive sign Erweiterung loss Dimension form spacetime aerodynamic design Recursive comparison unite exponentiation Errors moment program undecidability distances similar Positionen Spring functions Optimum table optimal matrix Recursive
Kanten deoptimization bottom Slides Graph string Gewicht <Mathematik> program undecidability Energie Integration functions vertices aerodynamic design Länge Recursive Arc Matching (graph theory) Recursive
job lines Graph directions string matchings sequence substitutive loss form aerodynamic design vertices comparison Arc deoptimization Slides Errors inner program knapsack problems distances similar sign Integration functions optimal integer matrix Recursive
so genau sind die anderen immer so sein dass er verlängert werden an der TU Darmstadt so hallo
allerseits ist jetzt 4 Wochen her seit dem wir uns das letzte mal hier gesehen haben zu dieser Veranstaltung ich hoffe Sie haben diese Zeit gut genutzt wofür auch immer Studium Arbeit Familie hängen lassen was auch immer machen wir Endspurt bis zum Ende des Semesters also der Vorlesungszeit ist nicht mehr so lange hin aber natürlich wenn wir doch mal ein bisschen zurückschauen wir noch mal ein bisschen kurz etwas etwas sanfter einsetzen selbstverständlich wieder den innerhalb dieser 4 Wochen könnt ihr vielleicht das ein oder andere aus dem Gedächtnis entschwunden sein da müssen wir wieder hin wir sind momentan bei einem relativ kleinen Abschnitt zum Thema Sie sehen es hier kommst Weintrauben endlich innerhalb des ganz großen Abschnitt das und ist tschüss wir hatten zuerst Nachbarschafts basierte Verfahren das fing an mit lokaler Suche einfachsten Fall dann hat er solche Dinge wie sie würde den D-Link oder Evolution schade oder genetische Algorithmen oder tabu Suche und danach sind wir dann zu den Entscheidungs- basierten ansetzen gegangen wo die Grundidee das Grundkonzept ist dass man schrittweise den Lösungsraum dem man gar nicht kennt denn es sagen aber trotzdem immer meistens Binder in 2 Teile zerlegt in dem man weitere Bedingungen eine führt zum Beispiel auf eine Variable X kleiner 1 x größer gleich 1 das hat das hat man die leise Bedingung einmal eingeführt und einmal negiert eingeführt so dass man den Lösungsraum zerlegt hat in allen Lösungen für die einer seit 6 kleine 1 ist aber seit 6 größer gleich 1 ist und diese Teile der das Lösungsraum dass die kann man dann weiter zerlegen beziehungsweise in der Hoffnung dass man dass man möglichst früh sagen kann dieser Teil des Lösungs Raums der jetzt schrittweise durch Einführung solcher weiteren Bedingungen entstanden ist dieser diese Teilmenge danach können wir durch irgendeine einen Ansatz belegen dass dieser Teile garantiert keine für uns interessanten Lösung enthalten wird oder vielleicht enthält interessante Lösungen aber wir können belegen dass dann außerhalb dieses teilten außerhalb aller bisher abgeschnittenen Teile immer noch eine interessante Lösung für uns übrig bleibt das ist so das Grundkonzept kannst Weintrauben das hatten wir an dem Beispiel oder bitte verglichen als Algorithmus das hatten wir an dem Beispiel der n Damen und geschaut weil das ein richtig schönes anschauliches Beispiel ist sie sehen es nochmal hier dieses Bild hatten wir beim letzten Mal vor Weihnachten bei der letzten Veranstaltung schon uns genau betrachtet wenn Sie sich vorstellen die verschiedenen Möglichkeiten wie man die 1. Dame in der 1. Spalte platziert im Prinzip gibt es nur 2 Möglichkeiten er alle als andere dazu ist symmetrisch und man nicht noch mit zu betrachten es gibt die Möglichkeit die da die 1. Dame in die Ecke zu platzieren oder es gibt die Möglichkeit die 1. Dame hier nicht in die Ecke zu platzieren sondern sondern sondern als der Mittelfelder weil wir nur 4 kurz wir der Schachbretter hier haben bei einem großen Schachbrett geht es uns entsprechen noch mehr Möglichkeiten und wenn das angucken was ist dann zum für Möglichkeiten gibt die 2. Dame zu platzieren jeweils bleibt nicht allzu viel übrig da sehen Sie kann man schon diverse Fälle abschneiden ganz logisch und muss sich nur noch um die Fehler kümmern die da die nicht hier ist schon abgeschnitten werden können weil zum Konflikt gibt aber sie sehen wie dieses Beispiel zeigt dass man da ganz schnell sehr viel abschneiden kann wenn man jetzt einfacher blindlings von links nach rechts durch geht ist das immer noch ein bisschen ärgerlich weil sie sehen die einzige echte Lösung ist so wie der Baum der definiert ist so wie wir hier die Reihenfolge links rechts definiert haben ganz recht das heißt also es was wir wollen ist in hat endlich auch Strategien zu entwickeln die uns sagen es ist wahrscheinlich vorteilhaft da hier lang zu gehen und weniger vorteilhaft hier Lanze gehen wir versuchen Sie es mal hier bis wir zu einer Lösung kommen sowohl das hatten wir alles
schon gesehen ich nicht noch mal durchgehen das können Sie sich auf den Aufnahmen wenn sie denn endlich mal online sind sich noch mal alles anschauen also ich bin hinterher dass die Aufnahme und ich endlich online sind ich habe ein meine Assistenten jetzt damit beauftragt das war dass er das dann übernimmt also wie ist man bisher vorgestellt hatte scheint es nicht zu klappen das haben wir uns auch schon betrachtet das man nicht nur einen Schritt zurückgeht geht werden wenn man ein Konflikt reingeht also hier dieser
Baum so geredet immer runter stellen fest hier gibt es ein Konflikt also die wir ein Schritt wieder hoch stellen fest wenn wir wieder den nächsten Versuch starten ist ein Konflikt der die wieder hoch ein Schritt zurück und so weiter aber wie wir an diesem Beispiel
letztes Mal schon gesehen haben muss das nicht unbedingt etwas bringen denn sie sehen hier die die Konflikte mit anderen Damen und ich es in Konflikt mit der Dame Spalte 1 hier in Konflikt mit den Damen in Spalte nein in Zaire in Spalte 3 und genau hier und in Spalte 4 und so weiter das ist gar nichts bringt den letzten die letzte Dame die hier der 5. Spalte platziert ist wieder weg zu nehmen denn überall da wo es in Konflikt mit der Dame in der 5. Spalte gibt gibt es auch Konflikte mit anderen das heißt mein Mann für verschwendet Laufzeit indem man einfach nur einen Schritt zurück geht wie der Baum ebenso geredet hat man muss algorithmisch genau hinschauen zum Beispiel hier beim N Darmproblemen dass man sich dass sie diese Sequenz von zu einer Zahl genau anschaut um zu sehen dass man mindestens 2 Schritte zurück gehen aus oder vielleicht noch mehr Schritte dass man versucht zu verstehen was hat was hat diese ausweglose Situationen diese Sackgasse letztendlich was ist der Hauptschuldige was die Hauptschüler der Hauptschuldige Konstellationen und so weit zurück springt der Hauptschuldige Konstellation könnte er theoretisch weit vorne seine muss ja gar nicht hier in den letzten Stunden passiert sagen wir können vielleicht schon gar zu Anfang ein Fehler gemacht haben das sehen Sie ja noch mal bei dem Beispiel hier hier
in alle 1. Schritt auf der linken Seite haben wir schon von vorne rein einen als einen Fehler gemacht der nicht mehr auszubügeln ist weil sie sehen es gibt keine Möglichkeit geht und mir eine Lösung zu finden schon dieser 1. Schritt fahren verlangt das heißt also ideal wäre es zu verstehen also auch wenn man vielleicht dass ich hier schon sitzen dann wenn man runter gegangen es irgendwo zu verstehen dass das was hier zum Konflikt letztendlich geführt hat sich hier vor mir schon der erste Schritt war das ist nicht auflösbar ist das gucken das
noch mal ein bisschen genau an heute das hatten wir auch schon betrachtet Konsistenz Techniken das ist jetzt nicht mehr das N Darmproblemen sondern allgemein betrachtet wir hatten hier 2 Variable die einfach groß und groß B genannt sind beide haben einen einen definiert einen Wertebereich die Variable aber kann eine werde 3 bis 7 an ganzzahlig die Variable B kann eine wird als bis 5 an dem ganzzahlig und wir haben ist ein sehr einfaches Beispiel wie Sie sehen wer nur eine einzige Nebenbedingungen nämlich dass die Variable aber kleiner der wird von Art kleiner dem wird von B ist und allein diese Demütigung schier schauen besagt er das dass die meisten Werte von an die meisten Wirte und B von vorne rein gar nicht mehr möglich sind Ja wenn kleiner B gelten solle ja B kann höchstens 5 sein das heißt also 5 6 7 kannte er gar nicht mehr sein und während kann muss mindestens 3 sein das heißt 1 2 3 können für Bega ich gut das ist natürlich nicht vollständig es sind immer noch Paare drinnen von Belegungen für A und B wie hier an gleich 4 B gleich 4 die immer noch nicht die Bedingung erfüllen aber immerhin wir haben der Lösungsraum schon mal deutlich reduziert und ich habe ihn bei dieser Gelegenheit auch eine allgemeine Erfahrung kommuniziert die da sehr wichtig ist das sieht alles aus wie Spielereien gut das ändern Problem ist dass sich die Spirale aber eine sehr lehrreiche aber das sieht auch aus wie Spielereien aber oft ist es so wenn sie eine aus der Praxis eine Problemstellung bekommen egal woher er aus der Logistik Transport Planungen Projektplanung was auch immer dass da so viel Redundanz drinsteckt in den Daten die sie bekommen und dass sie durch solche Techniken im Prinzip dafür sorgen kann dass das Problem also in gewisser Weise steckt da viel Rauschen trennen Problem viele viele viele Möglichkeiten das Problem zu lösen die in Wirklichkeit gar keine Lösungen sind und durch solch einfache Techniken kann man deshalb in der Praxis viel reißen dass man zunächst einmal das das Problem eben nicht unbedingt hundertprozentig löst damit aber das Problem deutlich reduziert vor ein paar Termin hat ich in ein anderes Beispiel dazu gezeigt aus meiner eigenen Praxis Sie erinnern sich die Überdeckung von Zügen durch durch Service Bahnhöfe wo einfache Reductions Techniken dafür gesorgt haben dass am Ende das was am Ende nach dieser Reduktion übriggeblieben ist dass sich das sehr effizient optimal lösen könnte ließ allein durch Blut voraus ausprobieren aller Möglichkeiten so schön es natürlich im Allgemeinen nicht sein wie in diesem Beispiel mit den Zügen aber immerhin man kann die ganze Menge vorher machen um die Problemstellung deutlich zu reduzieren bevor man dann anfängt mit anderen also weiter daran zu arbeiten und letztendlich reden wir hier von solchen Dingen so diese Kunst scheint hat aber das hatten wir schon
eingeführt will ich noch mal kurz die
die hier die wesentlichen Punkte Nordgrabens ist muss sie ist na einfach sehr primitive Sache sie haben wird und potenziell Bedingungen auf einer einzigen variabel zum Beispiel X kleiner 1 solche belegen kann geben als haben wir bei ganz Anti-Viren-Programmen das sollte X aus 0 1 sein dass es heißt X größer gleich 0 war eine den X kleiner gleich 1 war eine Bedingung und Variablen Werte mögliche variabel wird im Wertebereich von X die nicht größer gleich 0 oder kleiner gleich 1 sind wären damit sofort abgeschnitten Not konsistent heißt das wäre dann tatsächlich die er den Wertebereich jedes Knoten so weit reduziert haben das jede Bedingung die nur dieses X als Variable enthält wie X kleiner gleich ein zum Beispiel sondern Bedingung das hier diese Bedingungen erfüllt ist durch alle Werte die dann noch in dem reduzierten Wertebereich drin sind kannten Konsistenz
ist ein Schritt weiter nämlich dass wir Paare von Bedingungen haben das ist genau der Fall den wir in diesem Beispiel ja
hatten Sie haben eine binäre Würdigung eben bei Knoten Konsistenz hatten wir eine und Bedingung auf einem auf einer das haben wir eine binäre belegen auf 2 Variablen und wir sagen dass die Störung das die Wertebereiche von A und B bekannten konsistent sind werden diese wenn die weite Bereiche so weit reduziert worden sind dass alle Paare schau mal
nein das ist falsch formuliert wir müssen jetzt hier ganz genau auf die Formulierung achten für jeden wert in der Domäne der einen variablen Wertebereich der einen Variablen gibt es einen wert im Wertebereich der anderen Variablen so dass die beiden Werte X und Y dann tatsächlich die Bedingung erfüllen und das ist hier in diesem
Beispiel tatsächlich erfüllt sie sehen hier im vorletzten dash noch eine Bemerkung wenn wir durch die bedingt kleiner B die beiden Wertebereiche von A und B auf 3 4 und auf 4 5 produziert haben gibt es immer noch Paare von Werten aber ich bin gleich 4 die die Bedingungen aktueller B nicht erfüllen aber kannten Konsistenz ist schwächer verlangt nicht so viel Sie sehen ja wie schwer es ist ging es gar nicht in 2 Wertebereiche ich hier zu definieren die Kanten konsistent sind also die Führung die solche unzulässigen Paare nicht mehr enthalten weil dann müssten Sie hier noch was rausstreichen sie wissen nicht ob Sie das dürfen ob Sie der sich damit nicht die Lösung verbauen ja allgemein würde man das gar nicht schaffen sowie in diesem Bild Beispiel auch wenn ich noch zusätzliche Bedingung gibt die eine er da sind der mehr Informationen geben was man hier noch ausschließen kann an werden dann müssen wir damit leben dass ist das ist noch Paare gibt die die Bilder Werte von a und 1 b die dem Video aktueller den ich erfüllen aber keinen Konsistenz ist aus diesem Grund schwächer für jeden wert in der einen Menge in einem Wertebereich also für 3 oder 4 für aber gibt es jeweils einen wird in der anderen also 4 oder 5 so dass dieses Paar dann tatsächlich die Bedingung erfüllt für 3 ist es die 4 oder auch die 5 für 4 ist die 5 die das erfüllen oder deshalb weil man solche Fälle nicht nicht so richtig schön ausschließen kann es keinen Konsistenz
deutlich schwächer definiert aber immer
noch stark genug um viel zu reißen so warum
Revier von Knoten könnten könnten wir noch mal zurück sie können die Variablen auffassen als die Knoten eines nicht unbedingt eines Grafen sondern eines über Grafen das was ich jetzt an Anzeichen war schon beim letzten Mal dass es nur noch mal eine Änderung und eine Bedingung die nur eine Variable USA hier zum Beispiel enthält sowas wie X kleiner 1 oder A kleiner als in diesem Fall das ist dann eine Quoten Bedingungen weil sie nur diesen Quoten enthält eine Bedingung für die A und B enthält wäre dann eine kannten Bedingung und wenn sie noch mehr als einen mehr als 2 Variablen enthält und so durch ist häufig vorkommt schon sehr sogar so sogar sehr viele aufzeichnen man das ein bisschen so solange es noch übersichtlich bleibt ist dann etwas was man in der Graphentheorie eine über kannte nennt ja also dieselbe Logik W E beispielsweise Hyperraum das ist eben was vieldimensional oder noch höheres Raumes dreidimensional kannte ist 2 werde ich über keine wäre dann 3 oder noch wirklich ist immer dieselbe Logik wie im wie das wie man dazu kommt irgendwo das Präfix fühlbar dazu zu setzen überhaupt singen wir außer zwischen Literatur bekannt oder bin ich okay das Protokoll es war keine Meldung dar
so gut wir es noch mal ein Beispiel mit 2 Bedingungen immer hat den Beispiel kann das ist das mit einer beginnt jetzt mit 2 Bedingungen und 3 Variablen x ungleich Z und Y kleiner Z das sind die 3 Wertebereiche jeweils 1 2 und sie kann was über sie hier auf der linken Seite haben es ist das Original das ist nicht kannten konsistent warum weil die 2 zum Beispiel hier bei X bedeuten wenn der 2 hier steht dann bedeutet das dass hier eine einstellen muss bei Z und dann ist diese Bewegung nicht mehr erfüllbar also für den wenn ich's immer 2 hat ist die Bedienung geht nicht mehr fühlbar zwischen Z und Y das wenn keine Zeit ist und umgekehrt wenn Y gleich 2 ist da waren es zu von vorne rein auch diese Bedingungen nicht mehr erfüllbar das y keine erzählt ist ja also wenn wir hier bei X über bei y jeweils schließen dass das sie nicht das ist da keine keine Belegung der der Werte bin ich X nehme die X gleich 2 denn wir 2 für x da kann ich versuchen eine Belegung von Z und Y zu finden so dass sich insgesamt eine konsistente Bewegung findet und wenn ich das nicht finde dann kann ich die 2 sicher eliminieren und genau aus demselben Grund Swahili Medien bekomme zur rechten Seite ja die einst hier oben kann ich auch eliminieren weil die BOY kleiner Z kann ich mit zeitgleich 1 niemals erfüllen wenn y 1 oder 2 haben kann als wird und so komme hier zur könnten Konsistenz Sie sehen wir reden nicht wie in dem 1. Beispiel mit mit A und B wir reden nicht immer davon dass wir uns jede kannte einzeln anschauen sondern das dieser der 2 bei x nicht möglich ist ergibt sich erst dadurch dass wir nicht nur X mit 2 belegen dann automatisch steigt um nichts wert ist Z mit 1 und erst dann finden Sie hier heraus das die billigen y kleiner Zettel die nächste kannte nicht erfüllbar ist so Sie sehen auch das wie das kann die Konsistenz ist hatte eben schon mal festgestellt hier noch mal ein Beispiel das kann man Systems zwar schon sehr viel reist erfahrungsgemäß das soll ich jetzt einfach mal so sie können mit dieser Form oder nicht aber Sie sollten durch aus wenn sie von Problemstellung stehen berücksichtigen dass man mit solchen Techniken vielleicht erst mal anfängt die auch relativ einfach zu implementieren sind und sich dann anguckt wie die Instanzen die man aus der Praxis bekommen hat wie man die dann was dann am Ende nach einem solche Techniken raus bekommt sie sehen hier hat mehr da war es noch mal fast das selbe Beispiel nur mit Ick S Y Z jeweils ungleich also die müssen alle 3 und S 1 sind natürlich sofort das kann gar nicht sein wenn XYZ jeweils nur 2 Werte 1 und 2 annehmen können das ist kein inkonsistent finden von x eine Belegung für y für jedes 6. 7 Pfennig surfen Sampling y Definition blieben Zeitwertung für und Winzer Verbilligung es wird aber insgesamt ist natürlich nicht lösbar das habe hat man weitere noch schärfere bitte er Begriffe von Konsistenz eingeführt die ich hier nicht weiter diskutieren will die sind hier nur während Fahrt Konsistenz und K Konsistenz wenn sie interessiert können Sie danach googlen hier kann man uns nicht weiter darum vor allem auch weil es unter Umständen mit Kanonen auf Spatzen geschossen ist dass der Aufwand die Wertebereiche mit solchen Konsistenz Würdigung zu reduzieren sich einfach nicht irgendwann nicht mehr lohnt die komplizierte die Techniken sind sich einfach nicht mehr lohnt für das was man als Ergebnis dabei heraus bekommt ist es immer eine Abwägungsfrage die man in jeder neuen Situation in deren anwenden Situation bei jeder neuen Algorithmen Problemstellung wieder aufs Neue machen muss er es können durchaus Situation gebe es kann durchaus Anwendungsfälle geben wo man feststellt fahrt Konsistenz was wir hier nicht diskutieren ob Fahrt Konsistenz ist eine sinnvolle Technik der Mehraufwand der in der Mitte Anlaufzeit was es kostet Pfad Konsistenz herzustellen ist es wert
sowohl das komme vielleicht am besten wieder am Beispiel an hier wovon hier die Rede ist
nämlich wieder an unserem schön illustrativen Beispiele ist im Grunde etwas was man eigentlich ja an diesem Beispiel wird klar dass das wieder über Dinge reden die man eigentlich auf die man eigentlich auch selber kommen könnte nicht wo man ein ich erkenne volle sowie Optimierungsalgorithmen bräuchte um darauf zu kommen aber Sie wissen auf die einfachste Ideen kommt man immer als letztes er an diesem Beispiel wird es deutliche hätten sie das alle intuitiv selber auch gemacht in in anderen abstrakteren Situation vielleicht nicht von vorne herein nämlich wenn Sie eine Dame platzieren dass sie dann hier schon mal alles wegstreichen und dann noch gucken was das hier übrig bleibt hier an Möglichkeiten ist an sich die zweite davor platziert streichen noch weiter weg und stellen fest für die nächste da haben wir für die nächste Spalte die nächste Spalte ist vollständig mit weggestrichen können nichts mehr machen ja und Sie sehen wenn Sie das vergleichen mit mit dem ursprünglichen Bild ist es natürlich deutlich ziert sie habe mehr Aufwand pro Schritt pro Quoten dieses Grafen dass sie alles wegstreichen müssen ob es geht nochmal zurück
hier war das ursprüngliche Bild sie können sich natürlich
vorstellen wenn wir nicht von 4 Kurzferien sondern von größeren Dimension dass dann der der Unterschied zwischen diesen beiden Bildern dann auch noch größer
wird so hier haben sie mir auf ein jeweils so sehr
sich streichen müssen aber auf der einen Seite haben Sie damit den Knoten deutlich reduziert die Ideen Baum deutlich reduziert so dass sie schneller dann wenn es nun mal so ist dass sie unglücklicherweise zuerst nach links abgebogen sind erstmal mal hier über eine suchen und dann irgendwann erst nach rechts kommen muss die zulässige Lösung gibt das sie das dann schneller erreichen das ist noch einen Schritt weiter so was haben wir hier hier haben wir die aktuellen die bis dahin gesetzten Positionen aus am mehr verglichen mit den Positionen die noch zu den auch zukünftige Setzungen da setzen würden also werden hier in diesen bei der in diesem Gluten beispielsweise die 1. beiden Spalten besetzt und bestellen Konsistenz der wenn man so will Konsistenz Erstellung stellen Konsistenz her mit den da mit den Variablen die wir später noch setzen wobei ich nicht ich glaube hier da müsste noch ein Kreuz wenn nicht an an dieser an dieser Stelle denn das wird ja auch überdeckt durch diese Dame die hier gesetzt haben oder ja nicht okay ist ein eigenwilliger empfiehlt was okay gut das wichtige ist ja nicht dass die Bilder richtig sind dass richtiges dass Ihr Verständnis richtig ist immer kleine Ehepaare Unstetigkeiten in den Bildern drin ist umso Verständnis fördern ist das das ist zwar jetzt nicht die reine Lehre der Didaktik aber ich will er manchmal von Erfahrungswerten so hier auch und das war jetzt wirklich das war vielleicht ist ein bisschen mehr aus ist es ein bisschen flapsig gemeint aber es war durchaus ein bisschen ernstgemeint hat ist noch nicht fertig so wir haben das haben wir eben gemacht die aktivierte der schon gesetzten Dramen Vergleiche mit den mit den Möglichkeiten abgleichen wenn man so will mit den Werten der noch nicht besetzten haben und nein jetzt muss ich mir überlegen was hier genau gemacht wurde ja genau man hat also hier ist nur das Endresultat da das schon festgestellt wird diese Platzierung der Dame oben links war also in eine Ecke war von vornherein ein Fehler in dem man mehr tut als nur alles abzustreichen was von dieser Dame von dieser einzelnen Dame überdeckt wird sondern in dem man dann schon schaut die die nicht abgestimmt genau und wir haben jetzt hier ja wenn die da ist aber platziert sie würde die unteren beiden Kreuze erst mal noch nicht in der zweiten Spalte er das war hier noch an dieser Stelle noch frei aber man kann weiter schauen vorwärts schon bevor man hier was belegt aber keine kann man weiter schauen ob da noch Belegungen übrig bleiben und wenn keine Bewegung mehr übrig bleiben dann kam da kann man die natürlich auch aus kreuzen und hat das ideale Ziel erreicht dass man hier schon weiß diese Dame da oben ist fehlplatziert hat mehr Aufwand nochmal mehr Aufwand als eben in meiner sind nun aber man hat die die Knoten mehr des des Baumes noch nochmal deutlich reduziert das heißt auf wenn man das gemacht hat comma darüber und stellt fest Tuch aber es klappt ja ok fürs Protokoll die Frage war was der Vorteil ist ach das ist wie oft im Leben ich die Pänz wenn wenn Sie so sie schlimmstenfalls probieren Sie mal beides aus und stellen fest was von beiden wird schneller funktioniert und in manchen Situationen stellen sie fest dass eine muss besser in einer Situation stellen sie fest dass eine funktioniert besser das können Sie sich leisten bei der Implementation so von relativ klein ist beide Optionen die nur eine Option zu implementieren also die Antwort auf Ihre Frage es gibt nicht immer einer Verbesserung dadurch sie müssen sich vorstellen wobei wir die ganze der Vorlesung reden essen großer Werkzeugkasten wo man immer schauen muss was ist das richtige Werkzeug ja wenn Sie so was ist die Rolle der den D-Link her oder Evolution Strategien in einer Situation wo in einer praktischen Anwendung wo man mit lokaler Suche immer wieder superduper Ergebnisse gerecht zum Beispiel weil die Situation konvexe ist wo man dann sogar immer die die beste Lösung recht hat sie mir den Weg oder er wird so schon regiere sowas keinen Vorteil in einer Situation sehr wohl ich weiß nicht ob ich ob meine sagen kann ich habe Ihre Frage beantwortet man expandiert den Knoten nicht wirklich sondern man rechnet ja auf dem ein Tableau und war weil ich ehrlich mit mehreren Tableau aus und meinen guckt sich gleich gemeinsam die die beiden gemeinsam an er die jetzt hier aus gekreuzt sind und guckt sich an ob irgendwas der eine streicht das weckt einen Streich das weg auf dann üben was übrig bleibt es ist der ähnliche Situation als jemand expandieren oder das ist richtig was jetzt besser ist etwas was weniger gut ist das muss man dann sehen wir besser wird kann ich ihn nicht gehen dazu sind wir leider zu nah in der realen Welt auch wenn das hier kein reales Welt Beispiel ist mitten im Darm so vielleicht nur mal ganz kurz bevor wir letzter Punkt wenn wir solche Techniken anwenden das wär das wär Wertebereiche reduzieren ist über die Frage wo fangen wir denn eigentlich an was was ist aussichtsreiche welche variable fangen wir denn an welche war mit dem der betreffende ist und so weiter und was sich das ist jetzt auch wieder eine Kommunikation aus Erfahrungen was sich bewährt hat sind vor allem 2 Regeln wenn eine Variante von vornerein schon kleine Bereich hat das ist durchaus aussichtsreich ist die dann als 1. herzunehmen und deren werde Bereich noch weiter zu verkleinern weil wenn sie wenn sie war aber haben den Riesen Wertebereich hat von 1 bis 1000 und sie schaffen es diese Wertebereich auf 1 bis 999 zu reduzieren da haben sie nicht viel geworden aber wenn Sie eine Variable habe mit Wertebereich 1 und 2 und Sie schaffen es denn auf 1 zu reduzieren da haben sie so in Anführungszeichen das ganz auf die Hälfte reduziert natürlich nicht immer weil die beiden mit teilen in Teilmengen des Lösungs Raums wo in der wir diese Weibern ein sowohl 2 ist natürlich nicht gleich groß sind aber so als heuristische Vorstellung oder andere Regeln die sich die die die sich durchaus bewährt hat ist davor schon richtig dicke nehmen wir dem gibt da eben eben noch mehr drauf zu schauen weil die Wahrscheinlichkeit sogar groß ist dass man den Wertebereich ganz auf dann stark reduzieren kann mit den bei mit dem billigen die man schon hat plus dem was man noch einführt führt gut mehr will ich hier zu kurz wenn vor wenn ich sagen es gibt ganz tagungsfreien Zukunft Weintrauben Menck also Konferenz die mehrere Konferenzen die jedes Jahr stattfinden überall auf der Welt es gibt Zeitschriften zu Kunst Weintraube Schminke und alles also dann können Sie ja wissen was für ein riesiges Forschungsgebiet das ist wie bei den anderen Themen auch das das wir hier über eine sehr große Forschungsgebiete nur kurz antippen mehr können und wollen wir in dieser Vorlesung hier natürlich nicht mehr macht gar keinen Sinn hier mit Ihnen zu machen von entfallen Zeitproblem die wir damit hätte natürlich mal ganz abgesehen es kann hier nur und geben einen Überblick zu geben so der so das ist dass sie ungefähre Vorstellung haben vielleicht waren sie an welche Art von Technik denken sollten und dass Sie auch wissen
wo und wie sie sich dann darüber informieren können dann über weiteres die Literatur zerfällt typischerweise immer oder Fälle vielleicht zu viel gesagt aber sie finden typischerweise auf der einen Seite mathematische Abhandlungen mathematisch Beweise von irgendwelchen Konvergenz Verhalten beispielsweise für spezielle Situationen und ähnliches und auf der anderen Seite Erfahrung dass 2. Erfahrungsberichte von praktischen Anwendungen und drittens auch empirische kommt wieder studieren auf Basis formen künstlich generierten aber systematischen systematische generierten Instanzen so dass man da systematische Computer er ist immer nicht Erfahrung sammeln kann in punkto Konvergenz Verhalten gute Laufzeit und so weiter so ein weiteres Thema dynamische Programmierung da das ist Ihnen vielleicht schon unter diesem Titel begegnet mir geht es so ja weiß ich jetzt nicht ich will ein Beispiel kurz und einfach das nicht auf den Folien steht das vielleicht wäre dass sie vielleicht er die die 2 gesehen haben ein alt bekanntes Beispiel das sieht mindestens in der Mathematik gesehen haben eigentlich schon in der Schule wahrscheinlich sie kennen das ja oder dessen noch zum wie sich das ausspricht n über k und wenn ich sie schreibe ändern sich wahrscheinlich auch wieder in die Formel so wollen Sie berechnen nichts einfacher als das wie Sie wissen was die Fakultät ist also berechnen 1 das Produkt von 1 bis n Teil das also durch das Produkt von 1 bis K und alles noch mal durch das Produkt von 1 bis n minus klar welch wir so machen wenn Sie so machen ich würde ich so machen weil das Zwischenergebnis hier bitte riesengroß ich glaube bei allen gleich 17 oder irgendwo ich weiß nicht mehr genau sprengt schon den den im Bereich und den Lohnbereich spricht dann kurz danach gut zweite Möglichkeit ist das sehe dass Sie das das sehe er dass Sie das als im Produkt Schreibweise umformulieren das kennen sie auch ich hoffe dass ich das jetzt hier wir worden was müsste ich ja nochmal nachschauen sollen aber sie wissen was hier steht ne ich hätte ich nochmal mal nachschauen sollen so würdest ist jetzt genau das Produkt also Ende n faculty durch Endes K Fakultät ist gleich er mal N minus 1 x Minus K plus 1 und das ganze geteilt durch Ka Moore K minus 1 mal 1 und wir stellen fest dass es dieselbe Anzahl von davon von Faktoren im im Zähler und der Nenner ist das heißt jetzt vielleicht noch hoffentlich hin Hmm minus E plus 1 durch ihr so muss das jetzt sein nicht gleich 1 bis K die wir natürlich auch hat aber den Nachteil dass sie numerische mittelmeerischen Problem hat also mit Metronoms darum zu kämpfen haben Sie können ein ganzheitliche rechnen indem sie die Rekursion ist vor hernehmen habe ich neulich das ist richtig ja in minus 1 durch überkam minus 1 Jahr das Pascalsche Dreieck steckt dahinter das können Sie dann auch was ist das Problem wenn Sie das letzte wenn Sie wenn Sie so rekursiv das machen wobei Rekursion Anker das ist ne über 0 gleich 1 für alle in also Sie haben einen Anker für beson ändert was ist das Problem gar keins wenn Sie so wenn Sie einmal so rekursiven lamentieren ja das ist das ist ja sofort n über k gleich diese Formel ist so fordere Größe und die sofort als rekursive Methoden Jahr oder als rekursive Funktionen zählte bloß Plus oder was auch immer implementieren können das Problem an der Sache ist hier kleinen Moment wir brauchen erst machten so dass man das kleine Problem lösen Platz zu schaffen das Problem hier das 1. Mal wenn Sie n über k berechnen in den See N minus 1 überkam minus 1 und minus 1 über Kabel rechnen das ist dann ja weitergeht N minus 2 über Caminos ist 2 N minus 2 überkam minus 1 N minus 2 über K war minus 1 jetzt und N minus 2 überkam minus 2 ich hoffe dass wir das was wir hier falsch über klar so und das setzt sich immer weiter fort es ja Sie kennen das Problem das ist ein exponentielles Wachstum an rekursiven Aufrufen und sie sehen dass diese rekursiven Aufrufe dieses exponentielle Wachstum eigentlich völlig unnötig ist wie Sie sie hier sehen das die das immer wieder dieselben Werte berechnet werden ja hier hier konnten Baum von rekursiven Aufrufen da drunter und hier kommt nochmal Baumwolle rekursiven Aufrufen da drunter und beide Beine sind identisch beide Bäume werden zweimal durch den Rekursen durch die Abarbeitung der rekursiven Methode durchlaufen ohne Sinn und Zweck so die Idee von dynamische Programmierung ist gerne dass man Rekursionen umdreht Rekursion heißt diesen Baum hier Tor Top-down du zu durchlaufen ja oben das n über k damit haben Sie später Sohn aufgerufen und die anderen Aufrufe kommt dann so top down dadurch zustande das man das umdreht das man ich zeige das mal so wir haben guck ob ich das gut zeichnen kann wir haben nur das haben ist nicht nur guten bist bis Ende und wir haben hier kann gleich neue kann die ich Allens und so fort man nochmals vor die 1. Schicht und da mache ich immer so klar gleich 0 Carl gleich 1 und so weiter und so nein schön ich eben nicht Karl sondern Ellen gleich nur n gleich 1 und so weiter bisher zudem allen was sie eigentlich haben wollen n über k für kann gleich 0 wissen Sie können Sie wollen einfach nur dann schreiben so jetzt gehen wir K gleich 1 n gleich 1 kann gleich 1 damit beginnt dann schreiben Sie über alles rein was ist das das ist einfach allen besteht einfach 1 2 3 4 5 6 7 und so weiter hier schreiben Sie jetzt das deutlich
jetzt wenn man so einen hier der 2 über Kabel 2 3 über 2 viele über 2 und so weiter Sie sehen das Bildungsprinzip den Scheidepunkt ist der zunächst einmal wenn Sie sich die Formel nochmal vergegenwärtigen dass sie das Berechnen aus den beiden werden dann finden sie das hier als Sohn Bild n über k hier haben Sie minus 1 über K minus 1 und hier haben Sie also hier setze sich das bis da oben hin fort als und Dreieck was er sich das Pascalsche Dreieck irgendwie umgedreht ist wie bisschen anders gedreht und hier N minus 1 K sie können immer hier wenn in einer Zeile so ist also scheinen wenn sie in einer Zeile die Wörter berechnet haben können Sie daraus die Werte der nächsten Zeile berechnen und haben jeden einzelnen zwischen Wert hier wie diesen genau einmal berechnet natürlich alle zwischen werde die und wollen auch genau einmal berechnet und haben dieses Vielfache unsinnige redundante wiederholen der Sinn der Berechnung der selben Werte immer wieder aufs Neue haben Sie damit vermieden das ist das Grundprinzip was meines Erachtens an diesem Beispiel sehr sehr gut Deutsch aber sie versichern dass er vorgesehen dieses Beispiel okay dann haben Sie etwas Neues gesehen welche beruhigt und wenn sie es noch schlau anstellen dann brauchen Sie jetzt nicht zum zweidimensionales Ehre dazu sondern der können sie immer wieder nur dieses erregt und überschreiben immer wieder die Werte also erst 1. die Werte der Multis alle drinnen die die für Call gleich 0 dann überschreiben es geeignet mit den Werten der 1. solle mit dem Partner Zeugen soll und so fort das finden Sie so häufig im Internet irgendwo diesen Algorithmus dass wir das hier nicht weiter ausführen müssen wie man das machen kann in einem einzigen erregt Zeile für Zeile machen anderer Art bitte zu berechnen abzuspeichern bis man am Ende in der letzten im letzten in der letzten comma das er weiß zudem gesuchter geht das kommt das ist das Grundprinzip von die beiden kommen Erstellung von von dynamische Programmierung die beiden Conga haben Sie wahrscheinlich die 2 auch kennengelernt Beispiel nichts Standardbeispiel Smash sorgt das ist was andres müssen das andere ist auch da haben Sie oder Klicks und was auch immer da haben Sie auch eine binäre Rekursion ja das innerhalb eines regen Sohns Aufrufes zweimal rekursiv derselbe Algorithmus aufgerufen wird aber auf das disjunkten die Teilmengen der Gesamt Instanz ja das eine völlig andere Situation so hier gehen wir mal noch mal ganz kurz drüber und kommen zum nächsten Beispiel wir werden gleich noch mal zurückkommen anders interessantes Beispiel ist Matrixmultiplikation sie haben es hier verschiedene Matrizen von verschiedenen Größen ja also die Matrixmultiplikation funktioniert wird sich jetzt einfach mal voraus gut so hier zum Beispiel 10 kurz 100 Matrix Nudelgrieß 5 Matrix 1 5 kurz 50 Matrix für soll ja mal vorkommen nicht jetzt ist es entscheidend dass können Sie hier sehen sie wissen es geht es also zu tief gesetzt bei der Matrixmultiplikation er sehe man sich dunkel an so furchtbare Worte wie assoziativ gesetzt sie wissen sie können erst A 1 und A 2 multiplizieren und dann das Ergebnis was sie daraus bekommen nochmal mit aber die beziehen oder sie können erst A 2 mit A 3 multiplizieren und 1 dann mit dem Ergebnis von den beiden multiplizieren beides führt zum selben Ergebnis Wind Assoziativität führt aber in punkto Anzahl der Multiplikation die sie auszuführen haben nicht zum selben Ergebnis ich will die Rechnung jetzt hier nicht noch mal durchgehen kann 7 Stücke mal durch die er selber durchgehen falls Sie der Meinung sind dass sie in der Richtung Fehler gefunden haben geben sie mir Bescheid aber ich glaube die Rechnung ist korrekt aber sie sehen den den deutlichen Unterschied sie haben 7 Tausend 500 normale skalare Multiplikation Skala heißt eben von 2 Zahlen also von 2 Double ganz konkret weiter oder zieht lustloserer oder zählt und ihren die 75 Tausend ja also viel deutlicher Unterschied ja mal ganz gut aber der schlecht machen und wenn sie es sich eine Kette von dreien haben wo Sie wo Sie wo Sie das jetzt noch gut aus ausrechnen können sondern Sie haben jetzt eine lange Kette Jahr von von Matrizen sie haben jetzt auch 1 x zweimal 3 x 1 4 Mal 527 mal auf 528 x 796 Mal war 797 und so weiter und so fort bis zu irgendwie Art Tausend meinetwegen danach können sie natürlich nicht mehr vorab hier diese Rechnungen ausführen wie sie klammern müssen denn sie haben exponentiell viele Möglichkeiten zu klammern sie kann zum Beispiel sagen ich berechne zuerst die beiden hier Jahr und in den Bereich ich zuerst die beiden hier und dann berechtigt die beiden hier mal A 5 mal A 6 wir dann erst die beiden hier und dann die hier und sofort ja Zicke sehe die Klammer Strukturen können beliebig komplex werden und welche dieser Klammer Strukturen jetzt die beste ist das können Sie jetzt nicht mehr so schön einfach hier mal vergleichen weil sie müssten nicht mehr 2 Fälle miteinander vergleichen sondern exponentiell viele Fehler aber Sie sehen noch mal diesen schönen Beispiel wie dramatisch die Unterschiede sein können so was macht man da dynamische Programmierung natürlich ist ja schließlich der Name des Abschnitts was heißt das das heißt es wird mischen wir gleich period 5 schon noch erscheint so wenn Sie das so was haben von A 1 bis irgendwo Tausend meinetwegen Matrizen einer zu multiplizieren wir wissen nicht wie die optimale Lösung noch nicht wollen wir jetzt rauskriegen aber irgendwo gibt es für diese klar morgen oberste Stufe irgendwo G 10 aber die und E-Plus 1 so dass wir zuerst mit irgendwelchen wilden Zaman Struktur darin mit dem sich ein Fundament zu erst alles hier auch multipliziert haben und dann alles hier auf multipliziert haben das muss irgendwo geben wenn wir von rechts nach links einfach blind auf multiplizieren dann wäre das Ergebnis gerade nur weil aber 2 in den mache ich das richtig ne suchen A 2 3 close bracket A 4 close bracket A 5 close bracket und so weiter bis Tausend close bracket a close bracket Bummelzonen Reamonn auch close bracket und hier entsprechend viele open bracket das heißt also das wäre wenn wir von Libyen von links nach rechts auf das
Multiplizieren und uns Gedanken zu machen ob das jetzt gut oder schlecht ist dann wäre das der Fall die gleich so 999 hätten wir sozusagen dann gewählt wenn wir also von links nach rechts auf multiplizieren so das hier das obere das will ich jetzt mal vielleicht das wieder wegwischen ist sicherlich nicht ganz so wichtig das gibt eine Rekursion nämlich einerseits Einfluss und andererseits aber E-Plus 1 er 1000 ja wenn ich wenn ich wüsste dass das ihr richtig gewählt ist dann bräuchte ich nur noch in Anführungszeichen hierfür optimale Auswertungs- Reihenfolge und hierfür sind optimal Auswertungs- Reihenfolge berechnet werden Gesamtergebnis ich weiß es aber nicht was heißt das ich weiß es nicht das heißt ich muss über alle möglichen East das Minimum für minimiere oder oder wird ist das Optimum für 1 bis 1000 ist gleich der Minimum vom Optimum für 1 bis in die plus Optimum für plus 1 bis 1000 wobei die welche Werte kann es annehmen 1 bis 999 und geschweifte Klammer ja wir wissen nicht welches das richtige ist also schreiben wir erst mal hin wir wollen über alle möglichen East die in Frage kommen das beste Abend was ist das Beste das ist einerseits das Beste für die linke Seite bis zum wie und andererseits das Beste für rechte Seite ab dem E-Plus 1 die beiden natürlich addiert da fällt natürlich noch was plus dem Aufwand den denn die beiden machen plus das aufwand letzte Multiplikation beides ist beides zusammen beide Matrizen zusammen multiplizieren das habe ich jetzt für ihre unterschlagen also die Ergebnisse Matrix zu multiplizieren mit dir ergibt das Matrix 4 so so eine jetzt schreiben 1. einmal uns eigentlich geht ja wir haben seine schon gesehen Fully Liebhaber Versailles einen da steht das Wort ein das ist trennen das ist die open bracket im Englischen wird zwischen den verschiedenen Arten mit verschiedenen Worten unterschieden verstehen wird unterschieden die runde Klammern ist parente ist in Deutsch sprechen noch von Parenthese meinte ums andere ist die geschweiften Klammern sind weiß das und ging damals ein breites ok doch wirklich richtig Änderung ich glaube schon dass es so war so früh Volleyball sei ist heißt im Prinzip ist weiß ich nicht ob wir das noch hier wo haben wir heißt dass wir die Auswertungs- Reihenfolge durch Klammern die wir die Ausweisung Folge die wir haben wollen durch Klammern vollständig angezeigt haben so ein wieder eine also rekursive Definition entweder eine einzelne Matrix also ich in dem Fall die hier wenn wir die 1. ausgespart haben oder das Produkt zweier Rekursionen zweier solch voll eingeklammert Madrids Produkte und da wiederum mit klammert das heißt das was ich 13 gezeichnet habe es keine entspricht nicht dieser Definition der Name eines Tages muss er nach damit der Definition Genüge getan wird besonders in der geht es auch noch eine Klammer dann er spricht diese Definition so was wollen wir wir wollen wir haben gegeben diese Matrizen von der die ganze Zeit sprechen mit irgendwelchen Dimension die natürlich so zusammen passen dass die Matrixmultiplikation definiert ist also wenn sie könne nur zweimal trotz multiplizieren wenn die Spalten Zahl der 1. identisches mit der 2. 2. 2. das ist natürlich Voraussetzung sein und wir wollen jetzt Klammern setzen vollständig Klammern setzen zur Angabe der Auswertungs- Reihenfolge so dass diese Anzahl der skalaren Multiplikation minimiert wird und hier sehen Sie in etwas anderer Form diese Minimums Bildung die ich eben hier einer Tafel hatte beziehungsweise noch habe hier unten mit etwas anderer Notation was ist dieses hat das wird hier irgendwo definiert dass es auf dieser Folie ja hier gleich da drüber das ist dies das was ich hier als Optimum für irgendwas geschrieben habe diese ne J ist das Optimum für die optimale Multiplikation das Auswertungs- Reihenfolge für die Matrizen von AI bis eine Ortsführung Zone Teil Sequenz der gesamte Quinns aller Matratzen wenn ich gleich alt ist dann ist dieser dann ist es natürlich neue klar ein also Matrix es sich zu multiplizieren dies einfach dar das nix zu tun wenn aber nicht die gleiche das sondern wenn die kleine ja das wenn wir also eine Sequenz haben von wenn es eine Sequenz Alibis AJ von Matrizen ansehen die mehr als eine Matrix umfasst dann kommt jetzt genau diese bedienen zum Tragen nicht und kann sein dass ich bei der Notation das ein bisschen anders gehandhabt haben wir wie hier ich glaube gar nicht mal muss ungefähr dasselbe selber Notation sein das Optimum für den 1. Bereich von vom Anfang der Sequenz bis zu einem Wert K das Optimum für den zweiten Bereich ab K plus 1 bis Ende Sequenz das Ganze über alle möglichen Kasdi hat ich hier jetzt als East definiert was hier K steht ist hier I ich sollte das vielleicht mal entsprechend anpassen hier konform zu den Folien steht hier über Allen K dafür doch 1 der Aufwand für den 1. Teil der Aufwand den zweiten Teil und das ich ironischen dazu geschrieben haben auf und letzte Multiplikation der hängt natürlich von den 3 Dimensionen der der bei der beiden beteiligten Matrizen ab der 1. Teil hier er ergibt eine Matrix minder bestimmt sein und nur bestimmt nicht spalten Zahl der zweite Teil die ergibt eine bestimmte Zeit und bestimmte Spalten Zahl und Sie können leicht selber nachprüfen dass das hoffentlich die richtige was ist P hier es die Zeilen oder die Spalten zahlen dann machen wir das denn das ist es natürlich immer beides ist Zeilenzahl einer Matrix und sprach den Spalten Zahl einer Matrix und seinen Zahl der nächsten Matrix können Sie nachprüfen eine ruhige Stunde dass diese dass das hier als auf ein für die letzte Multiplikation hoffentlich korrekt ist viel aber sicher so das wäre
dann der Algorithmus in diesem Beispiel das ist einfach nur noch neue Nahrung Huperei mit mit Indiz ist ja da steckt ist eigentlich gar nicht so viele neue Informationen drehen Sie sehen hier haben Sie ja die Minimums Berechnung so und wir fahren erst einmal an dass wir dass wir die Werte die wir schon kennen nämlich die Wärter
wo von allen einzelnen Matrizen dass
wir die schon einsetzen nämlich zu 0 für einzelne Matrix ist nichts zu tun und schrittweise gehen wir vor dass wir dass wir schrittweise für immer größere Teilbereiche das sollt die vielleicht mal doch versuchen zu visualisieren was sie eigentlich in den Algorithmus passiert wir haben jetzt im Bereich ich dort immer das zu vielleicht von 1 ein bisschen tiefer von 1 bis 1000 also das ist mir gerade so muss einig und was wir uns im 1. Schritt ankucken eh gleich J ist wie mache ich das jetzt richtig ich glaube ich muss indes ist anders formulieren 1 diese Häkchen hier dich dein gezeichnet habe sind die Zahlen ich glaube ist wird dann klarer so für Igler gleich J gucken wir uns jedes Intervall berechnen wir alle Werte im 1. Schritt des Algorithmus in den 1. Durchlauf der Schleife oder beziehungsweise in diesem Fall in der EL in der Dieter in der Initialisierung berechnen wie es für jeden wird eine einzelne etwas wenn wir jetzt den nächsten Schritt gehen ihn gleich haben es einst unterscheiden sich um 1 dann machen wir folgendes ich deute das mal so einen für diese 2 für diese 2 für diese 2 für diese 2 und so weiter für jedes aufeinanderfolgende Paar bisher berechnen wir uns den optimalen wert und für den ersten Schritt wenn die beiden sich schon schon noch mehr unterscheiden wir wenn wir 3 Matratzen und haben bereichen wir uns für dieses Treppe und für dieses Treppe und für diese für jedes Treppe das ist ein bisschen unübersichtlich ja was was aber passiert ist in der Islamisierung berechnen wir das Optimum für alle für jede einzelne Sequenz die genau eine Matrix enthält in der 1. Iteration berechnen wir daraus dann das Optimum für jede Sequenz die 2 Matratzen und Feldhase ganze 2 Matrizen und hält in dem muss einfach diese Matrixmultiplikation genau anschauen für jedes dann im im nächsten Iterationsschritt Bereichen wäre das dann das Optimum für die Sequenz 1 2 3 die Sequenz 2 3 4 die diese wenn 3 4 5 und so weiter und so fort bis Ende 2 N minus 1 A N und so weiter
jeweils für die 3 und das haben wir gesehen wie man das macht indem wir einmal einmal so umklammern und einmal so umklammern und so fort immer weiter für
später wenn wir wenn wir schon wenn wir jetzt die Ergebnisse haben wir Sequenzen der länger 500 also in der man für länger der für sie können Dinge 527 dann erreichen wir dafür alle Sequenzen Länge 527 das heißt von 1 bis 5 127 von 2 bis 128 von 3 bis 5 129 und sofort dann brechen wir daraus das Optimum für auch für alle Sequenzen der Länge nach dieser Größe und vor das Optimum für alle Sequenzen der Länge 528 und so fort seine Schema die das schon hatten bei dem wieder merke 14. und mehr steht ja eigentlich nicht dass nun formuliert in so einem 2. Kurt so was ist das auch so dass es noch noch ein bisschen mehr Code darum herum was sie was war das jetzt hier das schlimme also das ist die rekursive Möglichkeit wie man das machen kann dennoch noch schöner und das ist das Ziel des Möglichkeit so ist es Beispiel ist aus der Biologie auch wieder ein Beispiel für dynamische Programmierung sie haben 2 Sequenzen dann wäre der von DNA-Sequenzen das sind vielleicht aus der Biologie noch irgendwie dunkel geläufig ich weiß nicht Mittelstufe oder wo also ich hatte das Thema DNA-Sequenzen der Biologie und ich habe wir gehen nach der Mittelstufe abgewählt insofern wer sich unwahrscheinlich wenn es auch eine Mittelstufe vielleicht gesehen haben sie wissen das menschliche Erbgut nicht das menschliche so auch von allen Tieren und von allen Pflanzen und und noch nie niederen Lebensformen ist nach einem einheitlichen Schema codiert das ist die DNA-Sequenz aus Sicht der Informatik oder aus unserer üblichen Sicht oder aus Sicht der Mathematik interessiert uns natürlich überhaupt nicht was das jetzt genau für für chemische Formeln sind die in diesem Riesenmolekül drin sind sondern die Informationen die uns interessieren die wir zu verarbeiten her haben ist ein eine DNA-Sequenz ist er eines dringen von ziemlich großer Länge von Milliarden Menge über dem als einem Alphabet mit 4 Buchstaben diese 4 Buchstaben wenn traditionelle Art CGT genannt das sind die Anfangsbuchstaben der 4 sollen die die da tatsächlich dann diesen diesen springe bilden also und sie wollen 2 solches Drinks Vergleich natürlich weil nicht in der Praxis nicht 2 solche kleinen kurzen Strings vergleichen sondern wie gesagt Strings des Milliarden länger haben und was heißt das vergleichen sie wollen versuchen möglichst große Übereinstimmung zu zu erreichen hier sehen Sie ich denke das müsste ich dafür dass das Optimum ist hier sehen Sie eine sehr gut ist ist eine sehr gute wenn nicht sogar optimal Übereinstimmung die beiden in bestimmt war in die Beine stimmen überein das G hatte keine Übereinstimmung dass hier vom 2. dringend er hat hier keine Übereinstimmung dass aber ein Minus hier hier sind 2 diese die die jeweils keine Übereinstimmung haben also hier hat man dann immer um der Übereinstimmung hinzukriegen hier an dieser Stelle hat man den es einen Buchstaben übersprungen hielt meinen TM Buchstaben über der was die Einstellung hier hat man das gehen 1. übersprungen wird man das aber im 2. dringen übersprungen und hier wenn Sie so wollen aber überspringt man beide gleichzeitig schon fragte dahin aber die aber diese natürlich die passt natürlich nicht hier das TT das das GG die passt natürlich zusammen so kann man das Visualisieren ein solches Alignment eine solcher Abgleich von 2 solchen Strings also letztendlich ist das sie kann vielleicht von von einem Kontext die Edith des Tanz oder eine feige der Mindestanzahl aus ok also diejenigen in unserer sagt das ist die dir das ist nichts anderes als die Tanz und Sie kennen vielleicht wie gesagt der Minister davon eine freie Meinung ist die älteste und nichts Großartiges so wie machen Sie das im Prinzip nach derselben Logik außen dass viele Formen hier nicht dass mal gleich wieder entschärfen durch ein paar Bilderchen mehr so wenn Sie diese 2 ist rings haben hier ich deute sie Nummer 1 das ist der eines trägen dass der muss dringend dann gut die wir natürlich immer länger dann wäre dieses allein Alignment ist perfekt alleine das können Sie sich als Sohn Mertsching zum Beispiel auch vorstellen ein Mädchen bei dem es keine Kreuzung gibt natürlich darf nicht das Ziel sein das geht nicht ein Mädchen zwischen den Zeichen des 1. seines Weibes trinkst so dass sich keine 2 Mädchen kann überkreuzen so wenn Sie jetzt hier irgendwo mittendrin zum Beispiel diese kann der drin haben die beiden korrespondieren miteinander haben Sie festgelegt ja sind der Meinung dass das eine gute Idee ist die beiden Kosten die einzulassen dann bedeutet das in dem Bereich das 1. und in den Bereich des 2. das beides zusammengenommen dieser Bereich des 1. dieser Bereich des 2. für diese 2 teils drin das wollen Sie natürlich optimale Lösung haben Sie bekommen eine optimale Lösung hier in den sie für diese teils Drinks jeweils eine Lösung haben und dann hier fortfahren bis sie sind auch wieder bei einer Rekursion das ist die Motivation der Rekursion wollen wir mal gucken dass wir das alles hier außen dass viele
Formen und warum es nur so viele Formen sein in okay wir konzentrieren uns auf diese Formel ja ich denke das ist das ist das das ist das Richtige und alles was wir dafür brauchen was war versuchen mündlich zu sagen damit Sie das wenn Sie
wollen dann natürlich auch noch mal schriftlich nachvollziehen können aber Clubs da nicht
oder lieber doch der Herren er gemeint ist also dieser rekursiven Formel so was ist das Theater steht kann glücklicherweise auf dieser Folie die Kosten eines optimalen Alignment ist Wir sind jetzt also noch ein Schritt weiter das wir denn
auch wo sind wir denn da mehr also
die Güte eines optimalen Alignment ja für genau für das was ich eben angedeutet hatte wenn das wie es um das T ist dann ist das in der Notation dieser Folien hier die Position I minus 1 und die Position j minus 1 und wir können hier 3 Möglichkeiten wäre für wen wir jetzt auf I Wiegard kommen wollen also hier auf diesen Schritt J halt halt dahin zurück wenn das Optimum haben wollen dann sagt diese vor vor diese Formel hier wir gucken uns an was ist links von dieser Position alles und was passiert hier an dieser Stelle und entscheiden dann auf dieser Basis was wir machen was können was welche Optionen haben wir hier an dieser Stelle wir können haben Moment das ist in der stimmt die Rekursion an dieser Stelle ich glaube ich muss es nochmal anders zeichnen so ein bisschen unübersichtlich schlichtes das so zeichne so wir sind hier hierbei die und hier sind um wobei muss er nicht dabei das gleiche Größe haben so das Optimum was man für diesen Bereich jetzt haben kann von vorne bis jeweils bzw. J jetzt geht es an dieser Stelle i und j 3 Möglichkeiten warum steht hinter hinten minus 1 und J minus 1 ach so oft bei meiner war ich habe nicht berücksichtigt dass die in das die Indizien ist der einzelnen Zeichens trinken 0 bis es ihr besiegen muss 1 sind das das habe ich ich habe die ganze Zeit hier verwirren lassen das heißt wir denn wirklich von ihm Minus auf hieß es die Position 0 und jetzt die Positionen Ines 1 beziehungsweise jeder der sein dann passt es wieder so das Optimum das optimale nennt ich hier für das Ganze ist D J eckige oder runde Klammern ohne Klammern für das ganze bis ihnen das alles bisher den es einsetzt stimmt das so ist definiert weil die ist weil die Springs Indiz Hilfsmittel beginne ich mit 1 so was kann mir passieren wenn wir uns diese beiden hier anschauen diese beiden Zeichen es gibt 3 Möglichkeiten ja Slapstick es gibt 3 Möglichkeiten wie ein auch wie ein allein man überhaupt aussehen kann ein 1. Möglichkeit ist die beiden passen zusammen und werden auch allein sind wenn sie zusammenpassen müssen sich allein sein aber eine Möglichkeit ist die werden alle eint eine zweite Möglichkeit ist also welche von den ist das hier das ist die mittlere das ist die mittlere die beiden werden alle die beiden werden werden miteinander identifiziert und in dem Fall wenn wir sagen die beiden wenn miteinander identifiziert heißt es wir müssen optimales Alignment hierfür finden für alles bisher beziehungsweise bis hier das ist die mittlere Zeile hier dann gibt es natürlich die Möglichkeit mal gucken die 1. Zeile welche ist das da dass der hier nicht allein führt dass der nicht mit einem anderen Knoten er mit einem Zeichen von T identifiziert wird wenn wir nicht identifiziert wird heißt es wir müssen optimal ist allein man für diese beiden SAPs subst rings finden hier der bleibt außen vor und hier für das Optimum ergibt insgesamt dem Optimum für die Situation gegeben dass der nicht im Spiel ist dass der übersprungen wird das ist die 1. Zeile und die dritte Zeile spiegelsymmetrisch dazu wir stellen wir sagen der hier wird nicht mit mit dem Maler Heinz das habe ich es nicht und gesagt es im Beispiel symmetrisch period ja das heißt wir haben diese Situation wider wie vorher wir haben eine Rekursionen dass wir sagen können das optimale allein man für diese beiden subst rings der 1 bis ihnen das einst aber bisher des 1 lässt sich rekursiv formulieren als das Optimum was man hier an dieser Stelle tun kann plus dem war Optimum was immer erst gibt dass die Rekursion das Optimum vom Rest wieder dieselbe Situation wenn wir jetzt das einfach als Rekursionen implementieren worden da würde sich tot rechnen weil laufend auch wieder dieselben immer wieder dieselben Werte hier berechnen würde exponentielle Anzahl sogar sogar 3 ihn also nicht nur 2 Spiele 2 rekursive Aufrufe innerhalb einer unsere gesund Schritte sondern sogar 3 also sogar noch exponentiell zur Basis 3 nicht mehr zu brauchen es war also richtig brutal und das weiß Trinkmengen von von so wenn wir haben das ist ordentlich nicht also der die die diesen so viel mehr also so den Exponenten also sind wir weit jenseits von Gut und Böse also aber was man auch hier wieder machen kann ist das kann man beispielsweise durch Schema hier ausdrücken dass sie diese Werte schrittweise von den Rico Suns Anfänge dass Sie zuerst die hier in der Tabelle berechnen positiv die 0 0 gleich 0 das sind die das sind diese Werte hier an so und so also wenn wenn Sie weil für irgendwie im 1. Subszenen betrachten die Situation das der zweite Subszenen wer ist es ist der Moment jetzt muss ich wieder mit dem auf beim anschauen wenn hier eine 0 ist dann heißt es das 0 minus 1 es fehlen also ist das war das Absingen diese Werte tragen Sie hier ab und dann berechnen Sie Schritt für Schritt nach dieser Formel in diesem Fall von links oben nach rechts unten berechnen Sie die die Werte durch und kriegen damit dann dann das Optimum auf dem Weg aus das kann
man auch noch zeichnerisch darstellen so wie hier falls Sie hat immer von Ihnen eine römische wurde und bei mir gehört okay gemacht und ist da haben sie die Zeichen schon mal gesehen ja man dazu grüßen Wege komme ich gleich sie können das auch zeichnerisch so interpretieren sie sie haben den einst Ring hier denn anders trinken dar sie haben für jede Paarung hier so eine Zelle aus 2 kannten um würden den nach rechts gehen aus 2 kann nicht so richtig nach unten gehen und eine haben und der diagonal kannte und wenn Sie wenn Sie die die wir da kannte verwenden heißt es dass die beiden kann sich hier sind 2 verschiedene diagonal kannten drin einerseits die Grünen wo die beiden Zeichen übereinstimmen was also eine zulässige Paarung wäre und anders als die blauen wo das nicht übereinstimmt sie stimme ich mit Dir überein also entsprechend eigentlich eigentlich Verbot also eigentlich etwas was mich bringt und Sie können das interpretieren als die Möglichkeit von hier oben nach von der um links nach rechts unten einen Pfad zu finden der Art der optimale fiel der möglichst viele grüne Kanten enthält je mehr grüne kann enthält umso besser umso mehr je grüne kannte die Sie in diesem Pfad haben hier sehen Sie Sumpf und Beispiel Fahrrad schwarz gezeichnet viele kann dieser Fahrt enthält ist ein Treffer wie kriegen Sie das hin einen solchen Fahrt von hier oben links nach unten rechts so berechnen indem sie kannten Gewichte drauflegen nämlich die Grünen kann können zum Beispiel Gewicht 0 alle anderen könnten Gewicht deutlich größer 0 haben und dann sorgte ein Algorithmus wieder extra schon dafür dass sie die Anzahl der Grünen kann zu maximieren der kürzeste Weg ist ein wichtiges Stichwort dabei da gehe ich auch über die vor den hinaus auch kürzeste Weg ist nicht da muss ein allgemeines wieder Extras ist anders als dynamische Programmierung was ist denn Ihre Rekursion bei kürzesten Wegen so sie haben sich vor allem vor dem Start Noten S zu hören die Quotenfrau grüß ist er weg nein dieser kürzeste Weg hat und der letzte kannte einer von den Kardinal Foreign gehen ist die letzte ja ich haben Sie irgendwelche Knoten oder sein Geld ja und zu den haben sie auch immer einen Christen Weg eben dieser Knoten der sieht halt irgendwie aus das muss nicht so könnten und sein dieses gezeichnet aber natürlich können auch so multiplication sign so kann natürlich auch viel gemeinsam haben Diebe als und ist so ihr so was die Rekursion der kürzeste Weg von es nach Frau dem er mir meistens dann mit Delta von vor abkürzt ich denke so dass bei Ihnen auch Energie die 2 abgekürzt bis gleich wieder ein Minimum das Minimum aller dieser Möglichkeiten Christa Weg bis zum Vorgänger Knoten und Länge letzten kannte Minimum Delta von Plus länger V wobei gelten muss das erstmal und V deutlich von der dass in Grade da ein so das ist ein das ist eine Frau ich hoffe Sie können das bekennen wobei gelten muss das Frau in der kann man enthalten ist das ist die Rekursion und sie könnten natürlich auch kürzeste Wege von erst noch V so berechnen wenn sie diese Rekursionen bemänteln und und und laufen lassen geht es dauert aber ewig natürlich bis sie bis sie das Ergebnis raus kommen aus denselben Gründen wieder weil sie irgendwelche Zwischenwerte so wie hier wie sehr sehr häufig immer wieder wiederholt berechnen dann wie ein Zwischenergebnis brauchen und dann wieder vergessen dann wieder neu berechnen und so weiter so was ich stattdessen machen das sei Algorithmus unterwegs zu sie berechnen er sie berechnen Bottom ab für jeden Knoten für den sie schon aus dem bisher berechneten echten Distanz werden dann den ersten das 1 zu berechnen können berechnen Sie den Umbau nur schrittweise auf das Übel gekommen sind welches ist der nächste Knoten das da haben Sie meine Beweise dazu gesehen dass es immer der Knoten mit der geringsten mit dem geringsten Schlüssel werden der in der Breite Kilo das ist nichts anderes als dynamische Programmierung ist sie berechnen Bottom ab für jeden eines anstatt die Rekursion top-down rechnen zu lassen und redundant laufend immer das selbe brechen lassen berechnen sie Bottom ab für jeden Knoten einmal denn Distanz wert bis sie zu den Gewinn des Tanzes des gewünschten Knoten angekommen sind so dann haben wir diese
ganzen Sachen übersprungen ich will ganz
deutlich sagen wollen dass bei diesem Thema
jetzt wo wir jetzt diese ganzen vom begraben übersprungen haben weil sie ganz Alignment wenn Sie mir das in der Prüfung gut darlegen können was wir
alles übersprungen habe mit den Formen bin ich begeistert und dann bewegt sich die Prüfung in Richtung schon mal einer sehr guten Note wenn sie nur in Anführungszeichen das erklären können dass wir in der Vorlesung gehört haben sich wunderbar es ist nämlich auch voll und ganz mit zufrieden
so das wir sie natürlich auch auf diesen Edith Craven hechelte kurz gesagt dass die des Tanz das
selbe ist ja hier comma noch zu einem letzten und durchaus interessanten Beispiel mit dynamische Programmierung aber dazu comma heute nicht mehr sondern die Zeit des ich darf mich für heute bei Ihnen bedanken und würde mich freuen Sie beim nächsten Mal wieder zu sehen
Feedback