Descision-Based Approaches - Dynamic Programming / Greedy Algorithms

Video thumbnail (Frame 0) Video thumbnail (Frame 14086) Video thumbnail (Frame 16007) Video thumbnail (Frame 24961) Video thumbnail (Frame 34561) Video thumbnail (Frame 36474) Video thumbnail (Frame 48769) Video thumbnail (Frame 61064) Video thumbnail (Frame 73359) Video thumbnail (Frame 85654) Video thumbnail (Frame 97949) Video thumbnail (Frame 102959) Video thumbnail (Frame 107237) Video thumbnail (Frame 113134) Video thumbnail (Frame 115006) Video thumbnail (Frame 124364) Video thumbnail (Frame 126704)
Video in TIB AV-Portal: Descision-Based Approaches - Dynamic Programming / Greedy Algorithms

Formal Metadata

Title
Descision-Based Approaches - Dynamic Programming / Greedy Algorithms
Title of Series
Part Number
11
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.
Loading...
Ziffer Process (computing) String theory Price index Matching (graph theory) Physical quantity Number Sequence Substitute good Sign (mathematics) Field extension Insertion loss Finite set String (computer science) Length Pairwise comparison Standard error Set (mathematics) Variable (mathematics) Computer programming Substitute good Similarity (geometry) Ring (mathematics) Index Function (mathematics) Military operation Optimum
Function (mathematics) String theory Hausdorff dimension Aerodynamics Pairwise comparison Mathematical optimization Computer programming Matrix (mathematics) Recursion Fundamental theorem of algebra Sequence
Kante Adaptive optimization Slide rule Graph (mathematics) String theory Computer programming Substitute good Number Integral domain Logic Function (mathematics) Iteration Estimation Vertex (graph theory) Aerodynamics Length Arc (geometry) Recursion
Product (category theory) Slide rule Graph (mathematics) Lemma (mathematics) String theory Weight Computer programming Knapsack problem Hausdorff space Sign (mathematics) Mathematics Causality Integral domain Logic Function (mathematics) Vertex (graph theory) Aerodynamics Summation Plant variety (law) Integer Arc (geometry) Recursion
Adaptive optimization Optimization problem Lemma (mathematics) Maxima and minima Two-dimensional space Parameter (computer programming) Knapsack problem Recursive language Sign (mathematics) Plane (geometry) Function (mathematics) Physicist Universe (mathematics) Supremum Estimation Integer
Kante Zahl Weight Maxima and minima Parameter (computer programming) Weight Order of magnitude Number Hausdorff space Energie Natural number String (computer science) Supremum Summation Length Arc (geometry) Directed graph Adaptive optimization Logarithm Eigenvalues and eigenvectors Binary number Moment (mathematics) Laufzeit Set (mathematics) Knapsack problem Recursive language Computational complexity theory Grand Unified Theory Logic Function (mathematics) Integer Mathematical optimization Scale (map) Recursion Längster-Weg-Problem
Kante Greatest element Greedy algorithm Weight Direction (geometry) Maxima and minima Lösung <Mathematik> Decision tree learning Number Subset Solution set Heuristic Spacetime Length Recursion Arc (geometry) Directed graph Social class Adaptive optimization Slide rule Raum <Mathematik> Decision tree learning Maximum (disambiguation) Moment (mathematics) Term (mathematics) Knapsack problem Sequence Recursive language Maxwell's demon Function (mathematics) Network topology Strategy game Table (information) Integer Mathematical optimization Recursion Längster-Weg-Problem
Greedy algorithm Direction (geometry) Neighbourhood (graph theory) Lösung <Mathematik> Decision tree learning Term (mathematics) Infinity Independence (probability theory) Subset Network topology Forest Strategy game Heuristic Spacetime Set theory Optimum Physical system
Kante Stress (mechanics) Spanning tree Weight Graph (mathematics) Hamiltonian mechanics Maxima and minima Matching (graph theory) Infinity Independence (probability theory) Mathematics Network topology Forest Graph (mathematics) Vertex (graph theory) Directed graph Shortest path problem INTEGRAL Set (mathematics) Subset Sign (mathematics) Forest Travelling salesman problem Network topology Number theory Set theory Power set Mathematical optimization Physical system Combinatorics
Spanning tree Graph (mathematics) Weight Hamiltonian mechanics Maxima and minima Matching (graph theory) Infinity Spanning tree Subset Independence (probability theory) Causality Network topology Graph (mathematics) Vertex (graph theory) Directed graph Shortest path problem INTEGRAL Raum <Mathematik> Euclidean vector Military base Set (mathematics) Subset Sign (mathematics) Algebra Travelling salesman problem Number theory Set theory Linear subspace Mathematical optimization Physical system
Maxima and minima Set (mathematics) Infinity Element (mathematics) Physical quantity Independence (probability theory) Subset Algebra Basis <Mathematik> Finite set Forest Set theory Physical system
Kante Stress (mechanics) Spanning tree Greedy algorithm Weight Graph (mathematics) Hamiltonian mechanics Maxima and minima Lösung <Mathematik> Matching (graph theory) Black box Function (mathematics) Weight Subset Independence (probability theory) Connected space Network topology Graph (mathematics) Vertex (graph theory) Directed graph Shortest path problem Military base Maximum (disambiguation) Set (mathematics) Element (mathematics) Subset Sign (mathematics) Forest Independent set (graph theory) Basis <Mathematik> Travelling salesman problem Function (mathematics) Network topology Many-sorted logic Number theory Set theory Negative number Quote Mathematical optimization Mathematical optimization Physical system Combinatorics
Spanning tree Greedy algorithm Graph (mathematics) Weight Real number Maxima and minima Matching (graph theory) Element (mathematics) Independence (probability theory) Subset Sign (mathematics) Forest Connected space Network topology Basis <Mathematik> Function (mathematics) Graph (mathematics) Many-sorted logic Number theory Negative number Mathematical optimization Physical system
so genau präsentieren und deren mehr so seine Haftstrafe Lernmaterialien an der TU Darmstadt so oder sein ich
denke wir sollten noch mal zurückkommen auf das Thema was womit wir beim nächsten Mal geändert haben weil ich das vielleicht ein bisschen zu oberflächlich betrachtet hatte sie erinnern sich dieses Beispiel zeigt ganz gut worum es hier prinzipiell geht wir haben 2 verschiedene rings über denselben Alphabet in diesem Anwendungsfall bei DNA-Sequenz vergleiche sind das ist ein Alphabet vor 4 Buchstaben die Traditional Art Sekretär sind aus aus Gründen der biologisch der Namensgebung und was wir rauskriegen sollen für dieses vorgegeben und Strings S und T ist ein solches Alignment sie sehen was da so passiert sie sehen Treffer C trifft sie A trifft Art wie dem T A trifft und so weiter sie sehen sprühender also dieses gehen hier steht das keinen kein Zeichen Instinkt die oder umgekehrt dieses in Tegetthoff kein Zeichen eines sie sehen aber auch hier noch aber das ist ja durchaus Ersetzungen geben kann dass die in der Distanz das heißt also wie viel mehr Editier Operation wie die Operation muss man tun um 1 trinken den anderen zu überführen in die Operation als das Einfügen Löschen jeder substituieren und sie sehen wir wollen wir wollen die diese Anzahl der Idee Schritte um ihren weil wir umgekehrt die Anzahl der Treffer maximieren ja wir wollen wissen wie viele Treffer gibt es das gibt uns die Information oder so ist definiert wie ähnlich die beiden Zeugen sind man könnte die Endlichkeit von 2 SMS auch anders definieren aber diese Definition hat sich bewährt sie entspricht ungefähr dem was man unter Innigkeit intuitiv verstehen würde oder beispielsweise gerne die logischen Anwendung was man hier als die Ähnlichkeit braucht zum Vergleich um daraus biologische Rückschlüsse zu ziehen und sie so auch algorithmisch gut handhabbar was wir letztes Mal schon ein bisschen gesehen haben es geht aber nicht über das was ich jetzt gesagt habe ich hinaus nämlich dahin gehend dass diese verschiedene Operationen einfügen löschen nicht also hier minus und Substitution also hier C wird durch substituiert Umfragen springe es so zu restriktiv zu kommen dass diese verschiedene Operation unterschiedlich viel kosten auf dieses auf diese Größen und auf auf diese Allgemeinheit in Betracht wir das das steht im Prinzip hier erst einmal die mir vielleicht mal ganz kurz diese Folie durch über beim nächsten Mal über schlagen also unterschlagen über übersprungen hatten wir haben dieses Alphabet Signal hier fügen noch das Minus dazu als zusätzliches Zeichen das gibt uns um das eigentliche Alphabet mit dem wir operieren Sigmar Keller und was ist jetzt ein alleine diese beiden Akteure weg wir sind die beiden in Kurztrips das war es und sie auf der letzten Folie die sind darf ich fragen ob jemand von ihnen keine formalen Grundlagen Informatik gehört hat 10 okay das eigentlich nicht Notations Frage Signal für Stern ist die Menge aller Arzt rings aller Zeichenketten über dem Alphabet das heißt das was hier steht ist nicht unter Ziffer 1 es nicht anders aus als A B A und B ist dringend über dem Alphabet so was rauskommen soll als allein ist so wie das auf das sind wohl gesehen haben aufgefüllt notfalls hier mit führenden oder ändern minus gleiche Länge für beide Strings und wir wollen keine totale Leerstelle haben ja also es macht hier keinen Sinn eine Zeile zu einer spielt schön eine Spalte so haben ein Index zu haben wo in beiden Strings aufgefüllt wurde mit minus das abschließende das von vorne rein aus obwohl die und bei Optimalität das sowieso automatisch auf ausgeschlossen wurde schließen es einfach hier auf Ausfalls offenkundig sind ist so das was hier steht im jetzt nicht also muss mal gucken was man durch die was hier steht ist das umgekehrte nur ich was was letztendlich unten aber steht dass wir wenn wir in diesen Arbeiten Alphabet Ursprungs Alphabet mit diesen minus 1 drin haben die also auch minus und zusätzlich Zeichen aus Signal halten kann dann ist die dass die Einschränkung von diesen Szenen wie auf sich mal eben das was rauskommt wenn man sämtliche ausstrahlt also mehr steht hier nicht das ist ein bisschen komplizierter formuliert sie kennen das wenn man es richtig formal korrekt vom jetzigen ist formalen Grundlagen Informatik beispielsweise dann wird dann wird man so was kommt in den wahrscheinlich vertraut vor wenn sie von statt und gehört haben und besonders solche da Sachen die Beweise rekursiv definieren die Einschränkung eines eine Element eines einzelnen Zeichens aus dem Alphabet ist das Zeichen selber die Einschränkung des minus 1 ist der wäre es also eines Drinks das muss man eingestehen wir es trinken das wird oder wenn sie wenn Sie die Kogge der der Nation von 2 Screens haben deren anschauen gerade die Einschränkung dass die einschränken die Kogge die Einschränkung der kommt der Nation ist die komme könne der beiden einschränkt ja so ist das rekursiv definiert und sagt nichts anderes als umso einschränken zu kommen wenn sich der Trainer streichen Sie alle minus raus und drittens es alles zusammen auf 1 dringend wieder unter ist so wir wir führen bisschen intuitivere Formulierungen in der dieser Begriff vor allem ein Mertsch ist also in diesem Beispiel hatten wir und ist Mensch C und C Seesen Mensch an und an die und die dass ein Mensch ist 1 absieht ionischen eine Ersetzung ist das hatten wir glaube ich hier nur einmal dieses C und dieses die ist eine Ersetzung und bei einfügen löschen sehen Sie die Definition ist jetzt ein bisschen asymmetrisch durchgesetzt ist immer symmetrisch behandelt egal welche erst in der 2. ist wenn wir darüber sprechen wollen und nur deshalb dann betrachten das ein bisschen asymmetrisch gibt das Problem ist weiterhin symmetrisch ist egal welches in der er sich erst in der 2. ist aber wenn wir darüber sprechen und unterscheiden wir eine Einfügung ist also wir gucken von 1. 10. 2. eine Einfügung ist dann wenn hier vorher nichts war so wie jedes minus hier und hinterher das geht ist und entsprechend eine Löschung der riechen ist es genau umgekehrt wer einen freue ich irgendwo was war im uns Tränen G und ihren und uns dann ist nichts was wir jetzt dann definieren können ist für die verschiedenen Arten von von Situation die wir an diese für Situationen wir können jeweils für jede Situation die Kosten erreichen also wie will wie schwerwiegend ist ist dass wir eine Substitution von wie schwerwiegend ist das für eine Einfügung in der erfahren wie schwer es ist wie wir diese bestrafen wir das dass wir eine Löschung vornehmen müssen prinzipiell gilt das auch für mehr tschüss die bestrafen die Stadt bestrafen wir das Leid das in der Show kommt aber das ist natürlich und nicht der Sinn der Sache dass er das Modell um einfach zu sein er erlaubt auch Bestrafung von Manchester oder sind das alles natürlich er praktisch in sämtlichen Anwendung die mir bekannt sind und so auch in diesem an Beispiel hier ist in möglichst viele Menschen zu haben also man würde nicht bestrafen würde alles andere einfügen ein und Ersetzung bestrafen so dann ist die Distanz wenn Sie einfach einfügen löschen und ersetzten jeweils mit einem Zähler bestrafen mit alle mit Kosten wird 1 dann kommt hier genau die jede Distanz raus wie viele dieser Operation muss man tun um den einst einen andern überfielen aber wir sind etwas allgemeiner so etwas wie eine gewichtete Version der Indizes Tanz jeder einfüge Operation die wir machen jeder der schon mal zu machen jeder ihre Ersatz und Operation hat die bestimmten Kosten hat also alle Lauschoperationen denselben kosten wird also ein man Seiten kosten wird alle ersetzt uns Operation an denselben kosten wird aber die 3 einmal können unterschiedlich so
das hatten hatten wir schon so weit gesehen also wir wollen wir wollen mit möglichst wenig kosten wollen wissen entweder können wir sagen ein und wie das gesehen haben oder die andere Blickwinkel mit möglichst wenig Kosten von einem zum andern zu kommen und da zumindest dann wenn einfügen und löschen gleich schwer ist ist das weiterhin symmetrisch ja das ist egal ob wir durch Einfügungen waschen von SCT oder von T zu es kommen erst dann wenn einfügen unterschiedlich teuer sind ist es nicht mehr so mild dann spielt eine Rolle bei der Ausrichtung das falsch ist ist das haben
wir beim letzten Mal hier schon betrachtet hat mir eine Tafel betrachtet müssen wir nicht mehr weiter durch gehen also ich will mal sagen Sie die Video die Videos in denen er mache die meisten sind schon gerendert sie sind sogar schon zum Großteil beim hochgeladen und noch nicht freigegeben ich weiß nicht was da ich habe jetzt jemanden aus meiner Arbeitsgruppe beauftragt das sich da mal dahinter kennt dass das endlich mal was wird so das hat mir betrachtet aber viel
schöner ist natürlich also sowohl ästhetisch schöner als auch vielleicht einsichtiger es ist ist diese Vorstellung hier dass wir das Ganze verstehen als ein kürzester Wege Problem das hier hin hier ist der Input auf der linken Seite die Bayerns Drinks tragen wir so ab und Bauern einen Grafen nach dieser Logik auf nämlich wir haben für hin für jede für jede Einfügung den schon haben jeweils eine Kante eine horizontal oder vertikal und Case kannte das in der vielleicht am besten hier rechts bei dieser Lösung wenn das strafbar wenn es ein bisschen schwierig zu erklären diese kannte vertikal runter entspricht diese Einfügung und dann sind wir schon hier das im 1. drin ein die es im 2. Trimester nichts mehr hier diese Einfügung das oben nichts ist und und wissen aber entspricht diesen horizontal die rund 10 Tagen kannte nehmen wir uns hier zum Beispiel diese mehr schwer T das entspricht dieser diagonal wenn ja und dieser Substitution dieser Sitzung entspricht dann wo sind wir dieser vertikalen könnte und jetzt können wir auf diese kannten das ist durch die Farben angedeutet die fahren sind etwas unglücklich gewählt weil nach Schätzungen mehr als 10 Prozent der Bevölkerung grün sind können sich mehr für späteren Vorträge und so sonstigen grafischen Gestaltung das so schön so schön symbolkräftig Rot und Grün ist das es keine gute Kombination aus um verschiedene Dinge zu gestalten wegen dieser weit verbreiteten Rot-Grün geklagt hier durch diese Vorhaben trotzdem GUI in diesem Fall ist es nicht so problematisch weil die weil die unterschiedlich gefärbten kannten auch Rot und Grün auch unterschiedlich verlaufen die roten sind die Einfügung oder schonen kann man mit 2 belegen die Substitution mit 3 ich weiß nicht warum ich mit 4 belegt sind für mich Sinn machen aber so funktioniert es endlich auch glaube ich und dann den am kürzesten Weg finden von da nach da von oben links nach unten rechts und Christa weg heißt so so selten wie möglich Einfügungen Überschwemmungen und also so oft wie möglich ein Mensch das was man letztendlich haben will also Entschuldigung ich etwas Falsches gesagt was sie gesagt habe ich verstehe nicht warum hier in Irene 3 nicht mehr versteht es ist ja nun Beispiel und wenn man Beispiel kreiert comma dass man endlich frei darin die Zahlen so zu werden wie man es will was ich eigentlich eigentlich meinte es wenn wir an unserer Anwendungsbeispiel oder an jede Distanz zurückdenken wenn wir konkrete jedes Distanz ja nehmen dann würde es genau kommen wenn wir hier beispielsweise bei der 2 bleiben bei den südindischen und hier auf auf 4 statt 3 gehen eine also nur Substitution ist das nein es ist schön und in Distanz wäre wenn ich auch noch 2 stünde es Hamas langsam bei der Substitution wenn Sie hingegen eine Substitution eine Ergänzung auf einen schönen einerseits und auffassen als eine Löschung plus 1 eine Einfügung so kann man es auch aufpassen zu kommen ja auch ihre Distanz definieren dann würde hier sinnvollerweise oder man würde die Kanten sogar ganz streichen dann würde Löschung und Einfügung eben durch Rote Karte von vornerein wird wir hatten 200. Mal an dieser Stelle auch schon angedeutet das will ich auch nicht weiter vertieft General das kürzeste Wege Problem von der von 1 bis 3 der Probleme von einem Knoten sollen anderen kürzesten Wege zum Wasser die Distanzen zu werden dass dieser Algorithmus ein Beispiel für dynamische Programmierung auch ist es gibt eine uns Formel die Länge eines christliches von es zu einem Knoten V ist die Länge eines ist das Beste was man kriegen kann wenn man einen können einen Fahrt zu und Vorgänger nämlich aus der Kommission der große umzudrehen zu einer Iteration zu machen und Schritt für Schritt vom starken aus vom vom einfachsten Fall immer schritt für Schritt das weiter aufzubauen weil aus Sinn dieser
so das hatten wir das ist nichts anderes als als eine verbale Beschreibung von dem was wir eben gesehen haben ich denke das können wir hier überspringen selbstverständlich erwarte ich nicht von ihnen werden in der Prüfung wenn wir über diese Dinge reden wenn Sie mir
beispielsweise hierzu was sagen können diese Dinge erklären könnte aber diese
verständlich nicht von Ihnen das mir dann sagen und wie sieht es jetzt verbale Beschreibung auf den Folien aus denen sich das eine Folie weiter sehr verständlich nicht wenn sie hingegen von sich ausmalen sie möchten es lieber auf diese Art und Weise darstellen meinetwegen
so sind wir damit durch ein weiteres Beispiel für manchen da nicht vor und auch abgeschlossen das ist ein Problem man schon mal sagt man das ist das wir wir haben Probleme oder ähnliches bewahren ist vielleicht gutes anschauliches Beispiel sie schreiben ein möglich waren sonst wüsste nicht möglich mir geworden Problem als und sie haben schwere Mode transportieren so schwer dass sie Mitglied einer der also das Sie wissen ein wenn das zulässige Gesamtgewicht nicht überschritten ist dann wird man das schon in Wagen eine kleben das heißt also es geht darum möglich viele an zu tun in diesem geworden also das ist diese das Gesamtgewicht der Stadt versteht sich ja genau gesagt stehen die maximal zulässige zu laden das kann man aber noch nicht mit weiter führen das ist der Spezialfall entwickelt Problem also Rucksack Problem man kann so aussehen wenn wir beim Beispiel ob auch aber die Dinge die man in einem Rucksack sehr sehr letztendlich die wegen meinem Zeitplan haben sind nicht nur unterschiedlich schwer sie das oder nehmen wir den Blick muss ich das fertige Gericht sind nun sein sind unterschiedlich schwer und sie sagen sich sie wohl nicht mehr als 30 Kilo schlechten weiß ich nicht also ich glaube ich würde der Protest 30 Kilo schweren wollen aber die die nahm auch noch angewiesen wäre wenn sie schon aus mit mitnehmen wollen dann wollen sie nicht die 30 Kilo möglichst genau vor sondern sie denn wer zu maximieren gegeben dass die Gesamtgewicht der der von dem was mit mehr oder belegen dass das gesamte insgesamt 30 so die Gewichte sind hier die Eigennutz also wir haben zunächst einmal ende N wie Nordpol verschiedene Stücke die wir im Rucksack oder sonst wohin reintun wollen wir wenn nicht wir werden es nicht schaffen die allein zu tun so dass einfach zu lösen wir sind schaffen eine Auswahl davon rein zu tun die Gewichte sind die tz die Auswahl die Auswahl wirklich beschrieben durch 0 1 Werte XJ bedeutet für das Stück nur mal gerade in also wir haben die ein Ständers vor diesem einfach indiziert 1 bis 1 für das Stück nur mal J das bedeutet XJ gleich 1 dass diese Stücke drin ist dass wir diese Stücke in unser Haus war immer ein in das die in unseren Rucksack in einem oder Möbel worden ich sage gleich 0 bedeutet dass wir diese Stücke nicht in unserer Auswahl haben das nicht mitnehmen beziehungsweise im Rucksack und die Profite werden sinnigerweise mit CD Kost hier und nicht mit P wie Profit abgekürzt aber gut das sind dir Sorten von Appstore Tradierungen die man den Gegner an Format wir erwarten darf dass das geht nicht so wie wie diese Fälle die ich immer mal wieder auftreten im Service Veranstaltungen der Mathematik und wo sich dann studieren an auf welche beschweren wir haben nur gelernt somit die gleich 1 ist zumal wir gleich 1 bis kennen wir nicht sie verstehe den Absatz von statt oder werden so diese C die Kosten also Profite dieser maximieren wollen Kosten wir natürlich maximieren sondern Profite nach derselben Logik das Produkte sagte immer was das Produkt wenn die wenn einer das Gewicht des des Stückes ist und XJ ist nun oder 1 und 1 bedeute ist dabei das bedeutet für den das jute Stück nicht in Auswahl ist dann ist dieser so 0 wenn diese Stücke in Auswahl ist wenn also ich sogleich 1 ist dann ist dieses Romans gleich eine Art das das was sehr effektive aufzählen dass die Summe der gewichteten Auswahl und genauso hier was Effekt dieselbe Logik noch sehr effektiv aufzählen ist die Summe der Profite stecke die in unserer Auswahl sind und diese aus weil es durch die x-Werte aus 0 und 1 gesteuert also wir wollen solche X werde nun und 1 finden so Mix aus ganz sogar ganz weil ich wie so ganz und nicht nur 1 also ich hier formuliert ist haben Sie sogar von jedem dieser einzelne Stücke in beliebig großer Auswahl aber ich glaube im weiteren also dass sie nicht nur ein Stück von dieser Sorte haben sondern beliebig viele zu Hause und haben sie kann noch mehr einnehmen aber ich glaube im weiteren Verlauf wird wird es wird dass er bitte der Fall betrachte sein das sich von jeder Sorte nur ein Stück haben nehme das hier auch schon so hier ist die Einschränkung das Gesamtgewicht darf nicht größer sein als die zulässige Zuladung oder die 30 Kilogramm Rucksack Minuskel Eigengewichtes Rucksacks versteht sich und das ist dann der Gewinne maximieren wolle das
übliche Sie kennen das schon bei Optimierungsproblem aus der Realität kann man fast blind vor fast 8 nur fast in Kauf werden dass die Problemstellung jeweils in schwer ist wissen was das praktisch bedeutet haben nicht thematisiert was theoretisch bedeutet wir waren erforschen thematisiert was es praktisch bedeutet das bedeutet für jeden Algorithmus denn denn die überhaupt nur denkbar auch wenn keine oder nicht also für den Algorithmus der in dieser Welt in diesem Universum denkbar wäre gibt es Beispiele Instanzen von relativ kleiner Größe auf den dieser Algorithmus sich dort rechnen oder das durch über alles die Zeit die nach Schätzung der Physiker für dieses Universum noch übrig bleibt wird definitiv nicht ausreichen ist nur noch in Arbeit und lassen und wenn sein bis der zum Ende kommt da keine gute Situation aber das ist leider die die typische Situation in der Realität in der Praxis und genau darum geht es bei Optimierungsalgorithmen mit solchen Situationen um zu gehen aber diese Folie
Trachten ich glaube da kommen wir später noch einmal oder nicht wir betrachten vor aber der es genau an wir konnten uns genau an was hier was hier dabei herauskommt ja was das eigentlich bedeutet hier was hier steht nämlich wir haben wieder das und zweidimensionale Schimmer wie wir das jedes Mal bisher gekannt haben wir also eigentlich bei jedem Beispiel das ja betrachtet haben zu dynamische Programmierung mal diesen zweidimensionales Parameter Schema und das ist kein Zufall dass es eigentlich eher typisch so was Sie hier haben abgetragen von 0 bis irgendwo B haben Sie das ist das was auf dieser Folie das Lamm da ist ja in unserem den wird hier und das was sie hier abgetragen haben ist wir haben von 0 bis werden die Anzahl der Stücke die das ist er so es ist manchmal so ist kleiner gleich n und größer gleich 0 also wir fangen Filialen Fall 0 und 0 1 in unserer Situation so und was steht hier was merken was wollen wir hier für diese Kombination rechnen die was wir berechnen wollen ist die optimale Auswahl aus nicht x 1 bis x enden sondern nur bis X er war also diejenige die die gleich 1 bis n nämlich bis Ende sollen eben bis er auch 10 die XII minimiert maximiert so das jetzt nicht D unser eigentlich uns eigentlich obere Schranke sondern erst mal diese zwischen obere Schranke so das Gesamtgewicht kleiner gleich dieser zwischen obern Schranke ist was das Gesamtgewicht sie die wir nicht sehen sondern es sind die es jetzt X E gleich 1 bis 8 kleiner gleich bleibender ja schrittweise bauen wir wieder die Lösung auf mit dem Hintergedanken das ist jetzt hier es komme hier wieder zurück also dieser wird ich ja abgetragen habe der wird auf dieser Folie Niki Lander genannt und es definiert gutes definiert so wie es da steht also mach mal jene Gleichheit als als Aussage und es gemäß Definition identisch mit der ob mit dem Oppel weder optimal Auswahl oder mit dem mit dem Wert dem Profite der optimalen Auswahl aus diesem Teil aller Stücke so dass diese Bedingung dafür ist jetzt ham wir wieder so ein 1 Schema das dass wir schrittweise das aufbauen können gut rekursiv nämlich das Schema die er lahmender können wir wieder konstruieren aus die minus 1 nur also die optimale Auswahl wenn wir das Stück Nummer er gar nicht brauchen und aus dem das brauchen wir nicht die er auf dieser Ebene ein gutes Stück weiter weg in diesem Schema G erfolgen lernen der minus aber da was steht da in dieser Rekursion habe ich was vergessen also so dass man ich noch ja gut was ich hier habe sind die Einträge in in diesem quadratischen Schema die müssen auch dann mit diesen Profit fährt der muss noch dazu kommen richtig aber das ist nur so sagen worauf wo die Wert da hat wohl jemand die Werte hat in diesem quadratischen Schema um diesen nächsten wer zu berechnen das da noch das Summenformel dazu kommt ja was steht hier letztendlich was hier steht ist das lässt sich gut verbalisieren die optimale Lösung für dieses er also diese 1. er ersticke und diese obere Schranke gelangen dar es gibt 2 Möglichkeiten wie diese optimale Lösung aussieht eine Möglichkeit ist dass das Stück Nummer 1. drin ist oder die andere Möglichkeit ist dass so Stück Nummer er nicht drin ist das hier ist heißt Stücke Nummer er ist nichts optimal ausmalen für er und lande ja wer nicht drin ist wenn diese Stücke nicht drin ist dann ist die optimale Auswahl für R und lahmender identisch mit optimalen Auswahl für 1 1 und dar man nur die Stücke 1 bis 1 1 drin sind das hier wiederum ist hingegen die die Situation Stücke nur er ist in der optimalen Auswahl was ist die optimale Auswahl in diesem Fall das ist diese Stücke Nummer R plus der optimalen Auswahl für diese obere Schranke
ja für für die jetzt betrachtet obere Schranke wo dieses Stück er drin sein soll minus dem weil das ja noch mit rein passen muss ja wenn vielleicht kann ich das noch mal ganz kurz damit das deutlicher wird Anzeichen wenn Sie eine optimale Auswahl haben T ein bisschen länger vielleicht die in die Gesamt in die Gesamtkapazität bis er einen reicht und sie haben das Stück Stück Nummer er drin da haben Sie hier also die Länge AEG und was ist die optimale Auswahl aus den 1. 1. wo sie unter der Bedingung dass das Stück Nummer er drin ist halt ist er so das ist die optimale Auswahl von den 1. er minus einstecken die hier rein passt noch inne ach optimale Auswahl aus 1 bis minus 1 so dass da noch genug Platz ist um dieses neue Stück dazu zu tun und deshalb gehen wir etwas ungewohnt nicht einfach hier sind die Einzeller runtergegangen von R 1 1 hier gehen wir nicht einen Zähler runter sondern die wir gehen gleich die ganze Menge von runter denn wir brauchen ja so und damit die Rekursion funktioniert wir müssen den Platz haben für das Ertl Stück für Stück Nummer 1 und das heißt halt wenn optimal Auswahl betrachten für wir für die obere Schranke lahmender minus ja das wenn das was hier steht denn diese länger ist ja gerade dann dann dann ist er ja okay ach so hier ist die von er angegeben und nicht die von er minus 1 ach so Sie sagen welchen er steht also man muss immer natürlich die Möglichkeit auch betrachten ob das nicht vielleicht ein Tippfehler ist nehmen an dass es kein Tippfehler kann ich jetzt nicht genau sagen Sie sagen weil hier er steht sie mir doch wieder eine Situation konsistent auch mit dem was sie oben steht dass wir nicht nur ein Stück von dieser Sorte haben sondern sondern beliebig viele macht wenn die für mich Sinn ja stimmt das ist das ist in sich plausibel ja ja was dazu gelernt danke so dass alle sind jetzt die Rahmenbedingungen die wir uns jetzt hier nicht angucken sowie teuer ist dieser Algorithmus na ja so teuer wie das quadratische Schema eben ist jeder einzelne der zu berechnen in diesem quadratischen Schema kostet konstanten Aufwand weil wir hier nur auf 2 verschiedene andere Werte zugreifen müssen und dass in dieser relativ einfachen Formel 1 verwursten und wie groß ist dieses quadratische Schema das hatten wir vorher an der Tafel die eine Dimension geht bis Großbeeren und die also Dimension des kleinen und dann haben der genau dieser Größenordnung eines Algorithmus so komisch ich habe eben auf der letzten Folie gesagt dass das Problem endlich weg ist und jetzt auf einmal haben so einen effizienten Algorithmus dar wie kann das sein hier sehen Sie noch mal Zahlenbeispiel 1. Mal das gehen wir jetzt nicht durch das können sie sich dazu war er zum zum Gegencheck ihres Verständnisses können sich das zu Hause selber anschauen das gedacht comma gleichen warum ist das Problem auf der einen Seite in beschwere also gar nicht gut lesbar und warum ist es auf einmal hier doch recht gut lösbar der period dieser Widerspruch löst sich auf durch etwas was ich bisher nicht so thematisiert hatte nämlich was heißt haben was genau bedeutet das dass diese Laufzeit so dramatisch schlecht ist bei endlich schwer was bedeutet es beim oder kleinen Beispielen schon die Laufzeit so dramatisch ist was bedeutet dass es die Größe eines Beispiels sie sind daran gewöhnt die Größe eines Beispiels nehmen sie die die 2 Jahr sortieren die Größe eines Beispiels drücken Sie aus in der Anzahl der Elemente in der in der Sequenz bei Zottmann sich ein bisschen anders dann nehmen sie dann noch die die Länge des Strings in 2 in die um die größte einer eine Eingabe darzustellen wenn sie Grafen Problem haben wieder extra oder ähnliches ja also wenn ein Algorithmus haben dann sind sie daran gewöhnt die Größe eines eine Eingabe in der Anzahl der Knoten und der Anzahl der kann Kanten anzugehen wenn man so Komplexitätstheorie Tische fundamentale Sachen betrachtet endlich schwer in der Komplexitätstheorie in einer in einem Teilgebiet letztendlich ein Teilgebiet der mathematischen Logik dann muss man sich denn aber muss man sie in genau fest klopfen fest definieren was von der Größe einer Instanz ansieht eine Eingabe und man hat sich dazu entschlossen die Größe einer Eingabe eben durch die Kodierung es größer darzustellen das im Alltag eine Konsequenz die einzige Fall wie 2 wurden unter den typischen Algorithmen die dort gelehrt werden der ein der einzige Fall wo das tatsächlich durchgehalten wurde ist backe zu Art die Größe der Eingabe ist die Summe aller Zeichen Allahs Trinks die eingegeben werden zum Sortieren schon bei Kriegs- oder ähnlichem stimmt das nicht ganz denn Sie haben ja eine wenn Sie einen sagen die Anzahl der Elemente in der Eingabe Sequencer stimmt nicht mehr sind es könnte zum Beispiel ja auch die die Eingabe lärmende könne beispielsweise Springs sein bringst deren größter abhängig von der die die genau die bitte schön die genauso viele Zeichen haben das ich unendlich viele Zeichen hauptberuflich das für die wie viele Zeichen haben können natürlich ist er und andere eine gute Musik Wichser da nicht wirklich einen Lock-in oder ein Kamerad weil für jeden Vergleich zweier Elemente wenn es zum Beispiel Strings sind
müssen sie als Zeichen für Zeichen die gegebenenfalls wenn die sich am Anfang sehr ähnlich sind und wenn sie am Anfang identisch sind Zeichen bezeichen vergleichen Beziehung und wummernde herausfinde eines kleiner der andere ist kleiner ja das stimmt eigentlich nicht ganz was wir also es stimmt schon in gewisser Weise aber es entspricht nicht dem was von Komplexitätstheorie betrachtet wenn auch nicht auch schon nicht wenn Sie Zahlen betrachten sie sind daran gewöhnt zahlen zu betraf 2 Zahlen miteinander zu vergleichen kostet konstanten Aufwand sonst Energie G 2 auch gelernt selbst wenn sie bei mir gelernt haben und sie so gelernt das stimmt natürlich aber nur solange diese Zahlen alle in die denn die in die Größe des Datentyps lagen oder hat da oder was hineinpassen in dem Moment wenn das nicht mehr der Fall ist wenn sie von wirklich beliebigen Zahlen ausgehen wenn sie also eine Datenstruktur wünsche aber beginnt glaube ich oder beginnt das ich weiß nicht genau wenn Sie so was ähnliches also wo sie beliebig lange natürliche Zahlen ausdrücken können das stimmt das natürlich nicht mehr einer Fall weil dann kommt dann kommt es darauf an wie groß diese Zahl ist wie viel Speicherplatz ist es um diesen mehr Speicherplatz ist umso mehr müssen sie potenziell miteinander vergleichen festzustellen welche der 2 Zahlen kleiner ist die Speichergröße ist aber von Zahlen es aber logarithmisch das haben Sie mal irgendwo mitgekriegt vielleicht sogar schon in der Schule das hatten wir hier beispielsweise Dekodierung es länger der Zahl groß B E ist der Logarithmus von bei mir wenn Sie das als SMS trinkt 0 1 trinke ganz normal im Binärsystem kodieren dann Krise genau das raus so endlich als zunächst einmal Folgendes wir es bis jetzt nicht wirklich thematisiert jetzt müssen aber mal tun endlich wieder heißt es gibt nicht mal eine eine einen Algorithmus der auch nur polynomialen auf Zeit hätte der dieses Problem ist ja Polin kann beliebig schlecht sein ja es muss ja nicht n 3 Seiten dieses oder er noch 2 wie sieht's die 2 können es kann auch hoch eine Million sein selbst einen solchen Algorithmus das Laufzeit wie er noch eine Million gibt er hatte noch eine Million scheint das kann es nicht geben dann endlich das Problem und sie können es weiter für noch 1 Jahr oder was auch immer schlechte Nachrichten aber es ist auch tatsächlich so beim indischer Klapse Problemen wenn sie die Kodierung Länge hernehmen als Maßstab dann in dieser komprimierten größte wird jede will es keine bringen immer ein Algorithmus geben aber wir betrachten die Situation des aus dem anderen Blickwinkel ich viel vielleicht eher das in Worten beschreiben als das jetzt hier dazu nur zu sagen ich komme vielleicht ich comma auch wieder zurück folgendes wenn Sie zum Beispiel lernen wie dessen Rucksack Ja oder oder nehmen Sie das Beispiel mit dem wir bewahren mehr dann werden sie eine gewisse Granularität inne Gewicht Messung haben wenn Sie da schwere Möbel Partien wenn sie vielleicht auf die Granularität von ganzen Kilogramm gehen oder wenn wenn Sie unbedingt wollen vielleicht auch die Granularität von ganzen Vielfachen von 100 Gramm aber mehr wenn sie da bestimmt nicht machen Sie werden bestimmt nicht auf Mikrogramm oder etwas darunter die die Gewichte von Möbeln von den Möbeln genau bestimmen ja sie haben eine starke Granularität und wenn sie ein zulässiges sagen wir ein Kilo und den Sinn zulässiges Gesamtgewicht oder der zulässige Zuladung von nicht fabulieren mal 2 Tonnen haben dann heißt das die die Größe Größe in der sich alles abspielt die Zahlen aber in der sich alles abspielt ist bis zu bis zu 2000 über 2000 gibts nix mehr eine Summe von mir besteht über 2000 brauchen Sie gar nicht zu betrachten einzelne Möbelstücke den mehr als weiteren wegen auch nicht zu betrachten was es gibt dabei haben und das heißt also in diesem was worauf ich hinaus will ist in in dieser Sichtweise wenn Sie sagen in dieser Sicht weise macht es Sinn es ist es ist anders gezählt die Komplexität in anderen Parametern nicht in der Input größer wo alles logarithmisch codiert ist sondern sondern wie sie sehen sagen Kilo für Kilo an in dieser Sichtweise ist das ganze effizient lösbar ja wenn hier B 2000 ist ganz bei also Granularität ein Kilogramm und das BA 2 Tausend Kilogramm und ist sicherlich auch nicht zu groß dann dann spielt es überhaupt keine Rolle ob das gemessen an einer wirklich in einer wirklichen Input größer er wohl wo die ganzen Werte und und C Werte alle irdische Größe haben so dass im Verhältnis zu diesem kleinen kompakten Kodierung wie man sind Publizität zur betrachtet der Laufzeit riesengroß ist aber gemessen an den ich an der Jungs Größe sondern wirklichen eigentlich in Tiere die exponentiell groß selber in der in der gut ihre eigene Gudjons Christen ja jede Zahl ist exponentiell groß in ihrer eigenen größer weil umgekehrt die Kodierung einer Zahl ist ja wenn sie also nicht in der Kodierung es größere der Zahlen das ganze betrachten sondern in den Zahlen selber was man eine kompliziertere Regeln nicht macht aber hier schon dann ist das Ganze in diesem im Verhältnis dazu doch effizient lösbaren zwar sehr effizient ich brauche nicht das ist das was was dahinter steht und solches Verhalten wenn wir also nicht die Kuh die Jungs böse da zahlen sondern die Zahlen selber hernehmen wenn das dann nicht mehr so gruselig schlechte Laufzeiten hat nicht dass ich mal Paul ich meine nur eine Million oder 1 noch eine Milliarde oder sonst was ist denen man diese Problemstellungen oder diese Algorithmen eigentliche Problemstellung sollte polynomial nicht polynomial aber weil das würde bedeuten Polin Nummer 1 Input größer aber sollte Boliden in Nummer polynomial in den Zahlen selber die für sich schon exponentiell in der Bund sind also durch diesen Unterschied zwischen den Zeilen Länge zwischen großer Zahl und ihrer gut Jungs Größe versteckt sich der Unterschied dass ist gemessen an der Kodierung größte wie man das in der Komplexitätstheorie betrachtet Kerosin auf hat aber gemessen an den Zahlen selbst keine großen auf hat ist auf das mal die Situation so aber leider nicht immer so es wäre schön wenn das immer so wäre dann könnte dies eine Folie auflegen und dann wäre die ganze Vorlesung die kann er das ganze Semester mit dieser Info erledigt aber das nicht immer so ist müssen wir noch weiter mehr müssen wir noch viele andere die Einsätze betrachten die wir bisher betrachtet haben die betrachten so letztlich doch nur vor vor ihr zurück Knapsack als Wege Problem wir hatten auch wieder nicht überraschend ich denke das ist auch eine typische Situation das man in dynamische Programmierung es Ansätze auch verstehen kann als Wege Probleme das hatte eben beim allein Problem schon hier auch einer etwas anderen Situation was ist hier diese was ist hier der
Graf der Graf geht durch sämtliche Werte von 0 bis zu groß B also das 6. in diesem Beispiel hier das groß B so sie sehen es gibt eine Kante jeweils von einem Wert zum nächsten diese Kante drückt aus das wenn es in dieser du denn im wurde diese Beziehung 4 aus das wir von er minus 1 Bachelor das ist falsch und sich als mehr sage man zu dass Deutschland ist mir etwas andere dynamische Programmierung es drückt aus dass wir von einem Landerer zum nächsten haben wird gehen ohne also ist es nicht dieses quadratische Schemas ist ein anderes Schema gut dass ich das rechtzeitig gemerkt habe steht hier auch ein mit können wer lesen kann ist klar im Vorteil dass man von einem Namen da zunächst den Namen der geht ohne dass sich was ändert ja also eine Möglichkeit wie die wie Sie es optimal hier sein könnte wäre für B gleich 6 wäre es könnte sein dass die optimale Lösung für die gleich 6 identisch ist mit der optimalen Lösung für den gleich 5 das heißt dann würde man die optimale Lösung durch den Grafen durch bis 5 vernehmen und dann auch diesen Schritt um anzuzeigen von 5 nach 6 passiert nichts mehr ist im Allgemeinen nicht unbedingt so was sie sehen ist hier für jede für jedes Stück und hier ist es auch notwendig sogar dass die Stücke öfters vorkommen können hier geht es in dieser Veränderungen geht es gar nicht anders für steht das sie haben hier sehe ich was haben wir hier wir haben 1 Stück länger 6 1 Stück länger 10 ein Stück Länge 15 und ein Stück Länge 16 oder Gewicht in unserem Beispiel 1 Zimmer Gerichte und einfache Art von links nach rechts von 0 nach 6 kann man verstehen dass ein Ausfall wir werden einmal die 10 gegenüber diese könnte wenn einmal die 6 gehen über diese kannte und will nichts mehr dann gehen wir über die Sieg Dinge zu dieser kannte hier wobei die Entschuldigung PR die die diese Zahlen sind die Kurse die Profite Entschuldigung diese 6 10 15 sinken die Profite die die das Gericht es ausgedrückt durch die Länge der kannte also diese keine geht von 0 bis 3 das heißt sie hat länger 3 Gewicht 3 in unseren Beispielen diese könnte hier die diese kann hier die die Note die Profit 6 tragen haben Länge 2 das heißt die sie haben Gewicht 2 und so weiter so welches eine so betrachte der kann ja durchaus und das auch mittendrin sogar noch mal den 0 er habe ist es Liga irgendein fad vielleicht erst diesen vor Ort hier diese könnte hier nehmen 3 Schritte weiter zu kommen hier ein Schritt weiter zu kommen mit 0 Prophet natürlich bei der nächsten zunehmen und hier Nummer 2 Schritte weiter so komme mit 6 Profit das wäre also die Auswahl einmal ein Stück mit Gewicht 3 und Profit sehen der Plus gar nichts bloß einmal ein Stück mit Gewicht 2 Ei und Profit 6 das wäre dieser Fahrt oder wir müssen Wanderfahrten nehmen hernehmen wir dem muss ein Sticker mit Gewicht 15 und er mit Profit 15 und Gewicht 4 plus einmal Gewicht 2 und Profit 6 und sind auch bei des angekommen ja jede mögliche Auswahl von Stücken ist der Äquivalent zu einem solchen Fahrt und hier ist es wichtig dass wir die Problemstellung so betrachten nicht so wie sie endlich normaler als der Literatur wie es ihr typischerweise kenne sondern in einer etwas anderen Situation nämlich Sie sehen hier man kann auch eine Fahrt haben dass es sich gar nicht anders als dass sich gar nicht verhindern dass es sich gar nicht modellieren werden um das auszuschließen sie kann noch Einfahrt haben ein Stück von dieser Sorte plus noch ein Stück von dieser Sorte bloß noch ein Stück von dieser Sorte das heißt also ganz konkret die Situation dass wir nicht von jeder Sorte beliebig viele Stücke drin haben die wir dazu zu zusammenpacken könne denken Sie sich eine Palette mit sie wo sie Pakete von verschiedener Art drauf platzieren können zum Beispiel ja gut aber alles andere was ich gesagt habe funktioniert nur das was auf dieser Folie ist aber alles andere funktioniert auch in denen eigentlich natürlicheren Szenario von dem ich ursprünglicher ausgegangen bin dass jedes Stück jeder nur einmal vorkommt ja jedes Sie haben für typischerweise nur ein Möbelstück von jeder Sorte und wenn sie mal viel stiller haben dann sind das eben viele verschiedene Stücke die zufällig dieselben krank ist die haben selber Gewicht derselbe Profit so damit sie würde mir dynamische Programmierung durch ein sehr mächtiger Ansatz aber die wie immer man könnte die ganze Vorlesung Qiagen ganz ist ein ganzes Semester für nur mit dem Thema dynamische Programmierung aber wichtig ist erst einmal hier über alle dass sie da einen Einblick bekommen Einverständnis bekommen so dass sie gegebenen falls dann auch vielleicht auf eigene Faust dann wenn sie vor einer solchen Situation stehen dann er weitere agieren können so wir kommen jetzt zu einer anderen Klasse von Algorithmen D heißen die und die nicht umsonst so wie es auf Englisch direkt die Richter Algorithmen weil sie immer das tun was in dem Moment kurz sich also eigentlich wäre fände ich es besser eine bessere Formulierung Begriffsbildung wenn man sie kurzsichtige Algorithmen und ich denke das trifft's besser dass man kurze dass sie kurz ich immer schauen in meinem kleinen eingeschränkten Blickfeld was ist das Beste was ich jetzt als nächstes tun kann so in welche Richtung ich jetzt am besten so hob ein Schritt weiter es habe ich ein neues aber weiterhin eingeschränktes Blickfeld was ist das Beste was wo wo kann ich jetzt am besten in und so weiter aber es hat sich etabliert dass Kredit zu nennen und so werden wir das jetzt auch einen so ist müssen wir noch mal auf die Vorstellung des ganzen Kapitels des ganzen Abschnitts vielleicht sollte ich noch mal einen guten so ich sollte noch mal ganz kurz so dynamische Programmierung zurückkommen denn mir fällt gerade auf dass wir gar nicht thematisiert haben was das Thema dynamische Programmierung eigentlich mit dem Oberthema des ganzen Abschnitt zu tun hat das scheint bei die irgend einer Überarbeitung der Folien und zwar nicht bei einer Überarbeitung durch nicht sondern durch jemand anders einmal weggefallen
zu sein also müssen es jetzt hier nach tragen ich hatte es ursprünglich reingeschrieben so sie ich es geht in diesem ganzen Abschnitt das ist weit zurückdenken vor Weihnachten es geht in diesem ganzen Abschnitt um solche Branching Tür ist das heißt also der wir können so so sagen der Lösungsraum wird schrittweise meistens bin mehr muss aber nicht immer sein wird schrittweise zerlegt in dem er verschiedene verschiedene Bedingungen jeweils hinzugefügt werden hier also dem Einsteller Beispiel was betrachtet haben mal sowas wie zum Beispiel x 1 gleich 0 x 1 oder kleiner gleich 0 x 1 größer 0 so sowas in der Form war das der Lösungsraum zerlegt wird in alle Lösungen bei den diese Dinge für diesen eine Lösung bei den diese Bedingung für und so weiter und so fort und irgendwo unten sind dann die einzelnen zulässigen Lösungen als Blätter so weit eingeschränkt dass das noch eine Lösung eines für sie Lösung übrig bleibt oder gar keine es kann auch sein und wir haben in verschiedenen Algorithmen beispielsweise bei bauen war das sehr intensiv so hatten wir immer geschaut was kann man tun an einem Knoten dass wir nicht den ganzen Teil warum wir da drunter ist auswerten müssen dass wir da nicht durchlaufen müssen weil wir können es natürlich leisten diesen ganzen Baum zu durchlaufen sie wissen allein schon wenn es nur binäre ist sie wissen was mit der Breite dieses Baumes passiert wenn er wenn wir wenn er eine gewisse Tiefe hat ja das explodiert das gewann ich machen und da haben wir immer geschaut können wir können wir vernünftigerweise davon ausgehen das könnte wissen wir haben ein Zertifikat in der Hand einen Beweis in der Hand dass wir diesen Teil Baum nicht durchsuchen müssen wir außerhalb dieses ums und außerhalb alle andern bisher abgeschnittenen Teile Bäume immer noch eine optimale Lösung übriggeblieben ist das war immer das könnten sie beispielsweise begonnen baut und dem Bundes ist bei dynamische Programmierung genauso diese diese Formulierungen im Maximum ich hier hier hier wird es vielleicht klarer hier das Maximum von 2 Optionen ja was sie was Sie im Grunde tun wenn Sie wenn Sie hier Sohn Schema durchgehen habe ich das noch aufgezeichnet oder so schon wieder ja es leider weg dieses Maximum dort in der Rekursionen das bedeutet sie haben Zweifel verschiedene Möglichkeiten sie zerlegen Lösungsraum für erlahmender für für die 1. er Stücke und für Oboe schon erlahmen dar den Zwillingen Sie in 2 Teilräume diesen Lösungsraum nämlich den bei Maximum des 1. was passiert wenn ich das letzte Stück gar nicht hinzunehmen wenn schon mir steht nix hinzunehmen was passiert auf der einen Seite wenn ich das letzte Stück hinzunehmen ja genau so wie wir das auch bei deutschen worden an also der betrachtet haben sagen wir das Schritt für Schritt zeigt diese Schritt für Schritt in Teil bauen und genauso beim Siegels allein beispielsweise der was passiert eine Möglichkeit ist ganz zum Schluss würde substituiert können läuft oder eingefügt oder gemanagt was passiert dann jeweils es sei denn das also in die 4 verschiedene möglich die verschiedenen schienen Teilmengen des Lösung Raumes o wo die letzten beiden gematcht oder G 1 gelöscht oder eines eingefügt oder oder wo substituiert wird und kämen dann in diesem Fall nicht auf dem binären sondern auf dem auf dem viergliedrigen Baum aber es ist immer dasselbe das geht dann Schritt für Schritt weiter wenn sie die Rekursion Folgen die das so schritten Schritt weiter und Sie kriegen genauso einen Baum nur was sie jetzt anders machen bei der dynamischen Programmierung ist dass sie erkennen also in das vielleicht ist gerade nicht aber sie erkennen dieser Knoten hier und dieser Knoten hier die Teile Bäume die da drunter sind identisch also brauchen also einmal berechnen und sinnvollerweise nicht indem man untergeht im Baum an der einen Stelle das berechneten wieder hoch geht und dann an einer Stelle feststellt das war schon mal berechnet also wo man sich noch mal zu berechnen sondern in dem sondern dem Bottom ab schon von vornherein berechneten das nur einmal berechnet die Situation dieses Format Umbau kennen der dass man tatsächlich bald dem ab geht uns einmal berechnen man das und beim 2. Mal stellt man fest dass sie schon mal berechnet worden wo man nicht einmal die kann auch auftreten in komplexeren Situationen da habe ich vor langer Zeit unseren sie Jahre oder so mal selber so eine dynamische Programmierung gebaut und wo wo es nicht mit quadratischer Anzahl von solchen verschiedenen Konstellation gab eine viel viel größere Anzahl also wo das Schema ein schon für sich genommen viel zu groß war wo ich für jede Kombination auf dich mal gestoßen bin dann und das berichtet habe in einer Hersh Tabelle diese Kombination abgelegt habe und wenn ich später auf einer anderen Stelle im Baum wiederzusehen Kombination gekommen bin hat oder bei unterblieben Kombination bin schau ich nach habe ich nachgeschaut ist diese Kombination von daher stabile wenn er gleich den wird einfach also diese Sichtweise er ist durch durchaus ihre Relevanz dass wir das Einordnen in diesem Oma Abschnitt über Branching in Triest so jetzt komme aber wieder zu bewahren entließ zurück den er etwas etwas näher dran und zwar auf eine sehr langweilige Art wie genau einmal einen Zweig im Entscheidungsbaum ich habe das passend wie gesagt also Entscheidungsbaum weil weil der Begriff im Allgemeinen gehen genau einen Fahrt unter bis zu einem Blatt und jedes Mal also wir gehen eine Schritt runter einschritt Schritt unter ein Schritt 1 Schritt 1 Schritt 1 Schritt 1 Schritt so bis wir bei dem Blatt sind und dieses Mal gucken wir wie ich das sagte mit dem eine ganze Gesichtsfeld was scheint jetzt die beste Möglichkeit zu sein um ein Schritt die dazu kommen welche der verschiedenen Wahlen kann sieht es plausibel aus so gerne sind solche Methoden also solche Methoden die Algorithmen aber wir werden uns hier auf die Standardsituation noch einschließen nämlich eine spezielle Situation die uns einige an Kopfschmerzen bereiten würde das ich es schon mal im Voraus so es gibt ja noch was dazu zu
sagen zum die Algorithmus will ich denke es ist erst noch vom grundsätzlich ja klar nicht Glieder grünes ist kann man auch sehen als Bezahlverfahren Beck tritt gegen sie einen werden Bettringen gehabt und geht runter stellt fest dumm gelaufen irgendwas ist ja verkehrt wieder zurück vielleicht ein Schritt zurück oder sogar mehrere Schritte zurück um diese um den umsehen umgekehrt stellt die TU da die diesen Widerspruch aufzulösen und dann versuchen muss eine Richtung bäckt Regen der Spezialverfahren Beiträgen geht das Bezahlverfahren wegträgt in das Handy zurückgehen das sie nur einmal runter und das war's so wir betrachten aber eine bestimmte
Situation dieser sehr häufig ist die eigentlich so die typische Situation ist ich will auch gleich bevor ich Sie jetzt überfrachten mit Mutationen und und nicht ganz so einfach zu durchschauen den Informationen will ich Ihnen aber auch gleich von vorn herein sagen wohin das führen wird so dass der kleine Motivation so die eine oder andere Durststrecke zu überwinden das wird führen wie die Algorithmus ist offensichtlich in den meisten Fällen schlecht sehen die lokale Suche bei Nachbarschafts basiert sind die die Algorithmen offen werden im Allgemeinen keine Optimum finden sondern werden oft genug auch sogar sehr schlechte Lösung finden es gibt viele Situationen der Praxis wo kriege Algorithmen schon sehr gute Lösungen liefern aber es gibt auch Situationen der Praxis Vogel ergründen Grotten schlechte Lösung liefern aber auch sehr gute Lösung muss noch nicht optimal ist und sein muss nicht das Beste die beste Lösung sei sondern eben nur relativ nah dran was wir worauf wir hinzielen ist eine Charakterisierung unter welchen Umständen der Krieg die Algorithmus tatsächlich garantiert eine optimale Lösung gefragt das kann man sehr gut kannte sie ihren S plus ein bisschen kompliziert wir werden auch als ein Nebenprodukt aus höherer Warte nochmal sehen der Gruppe von Kruska den sie dunkel noch eine Änderung kamen über minimal Stunde Bäume maximal Sponde Wälder ist eigentlich Algorithmus das ist noch nicht die tiefe Einsicht dass wenn gleich noch mal sehen das er das ist wie ein ist aber diese Charakterisierung unter welchen Umständen ein eigenes tatsächlich die beste Lösung liefert diese Charakterisierung beweist auch noch mal wieder dass der Algorithmus von Kruska tatsächlich die optimale Lösung liefert also wir wir werden jetzt auf eine Resultat hinsteuern wo der in dem die Optimalität es also bis groß gerade einen der eingebettet ist wenn man so will so das war die Vorrede jetzt geht's hier zur Sache das Unabhängigkeit System Independent System ist noch was relativ einfach ist sie haben vielleicht gehen wir einfach zu Beispielen hier er bevor
wir dass das immer genau von Ihnen haben schönes Beispiel ist Knapsack wieder wo wir eben waren Unabhängigkeit System heißt
jeder Auswahl in Auswahl haben und die passt rein der können Sie auch Elemente aus denen es passt immer noch ein also die Auswahl man Klappe Problem ein Unabhängigkeitsliste sehen nehmen Sie ein anderes Beispiel her Wälder Wälder einem Baum spannender Weltenbaum also Züge freier teils und Graf eines eines Grafen als kann die Menge wenn sie so ein zu befreien so Graf alles kann Reifen haben und Sie nehmen noch kannten aus dann bleibt Züge frei das heißt die Menge aller Züge freien Sogkraft eines Grafen sind eine Unabhängigkeitsliste ja comma gerecht 2 Hoche die Mathematiker haben Sie recht mitbekommen legen sehr viel Wert auf elegante Notation und auch die Informatik erleben er wert auf irgendwelche witzigen Notation die ehemalige er auf elegante auch ja ich muss es langsam daran denken dass das ganz normal irgendwann weltöffentlich gestellt wird also soll ich mich jetzt hier nicht rausnehmen das ist nichts anderes als die Potenzmenge der Menge E es gibt gewisse Gründe warum man das eine er als gut passen zu anderen Notationen sehen kann ja also letztendlich steckt dahinter die fikation eine Auswahl mit mit dem mit der Kaktus schon vom Östringen also mit dem 0 1 trennte diese Auswahl bezeichnet das hat das 2 also es weisen abgesehen für 0 comma decimal 1 was hier steht es 0 comma decimal 1 2 Rene verdichtet zu 2 Hoche das kann man elegant finden gut also das uns da jetzt nicht weiter beirren dass einfach die Potenzmenge 2 Amri die Potenzmenge der Menge E so anderes Beispiel Mädchens in einem Grafen mehr ich ein Mensch in einen Grafen aber sehen Sie was das ist das sind 7 kann man ja wo wohl keine 2 Kanten denselben Lohn gemeinsam haben wenn ich da noch keine wegnehme ist weiterhin ein Menschen das fällt mir gerade nicht mal
spicken noch ein schönes Beispiel
ne die ein Beispiel gefallen mir nicht so doch jetzt ein Beispiel noch was was wir später nochmal betrachten werden wenn man sich eine Menge von wegen unabhängigen Vektoren her wenn Sie davon welche mitnehmen ist das immer noch länger unabhängig also sind sind Mengen von der unabhängigen Vektoren ein Unabhängigkeitsliste in der es bedeutet nichts anderes als wenn Sie eine eine Menge y im Unabhängigkeit System haben eine Auswahl ist eine monatliche System und sie haben Teilmenge X davon dann ist dieses X ebenfalls ein Unrecht das ist so wie das immer gesagt habe er das Mädchen kann rausnehmen ist immer noch mit Schenk deshalb ist die Menge aller Mädchens in einem Grafen an und das ist so die 1. beginnt jetzt eigentlich sogar wird und dann mit denen die leere Menge ist natürlich ne Teilmenge jeder Menge hier das heißt also wenn sie wenn Sie als die in m 2 wenn sie X als leere Menge einsetzen die natürlich Teilmenge von ihm y ist dann ist folgt aus 2 sowieso schon dass die leere Menge ebenfalls im Unabhängigkeit ist im ist stimme nicht ganz was Sie gesagt habe das ist das ist redundant ist das eine das ist wie eine schöne schöne elegante Weise 1 der Sinn von dem einst ist einfach auszusagen dass dieses unabhängig es nicht leer ist ja ich habe ihm gesagt die leere Menge ist ist automatisch garantiert in und unabhängig das System drin weil sie wenn sie ein Element y aus dem ist immer nehmen eine Auswahl y jede Menge so Teilmenge davon dann ist wäre man natürlich automatisch auch vorausgesetzt dass und wie es ist dem es nicht mehr dann gibt es diese Argumentation nicht dass ich im Y er ne mehr als 700 unabhängig im was solches y gibt also muss man in wie noch sagen die leere Menge er also das Pflicht das es dem ist nicht wär es könnte man dann einfach sagen sein M 1 1. Bedingung ist dass Effekt des ist wenn nicht mehr und es wäre zu einfach zu und Liga und kann dadurch genauso gut sagen die leere Menge sein wenn es unmöglich ist im ist völlig Idee Äquivalent so schön als elegant nicht so wir werden noch was besonderes brauchen die so genannten Basen wir werden auch feststellen dass das was mit dem zu tun hat was Sie außer der Algebra als Basen kennen gelernt haben dass sehr viel sogar zu tun hat diese wenn sie einem maximales Match in haben in dem Sinne dass sie keine kannte man zu führen können so dass noch Mädchen wird dann ist das eine Basis ich habe es Base gesagt Basis seit den Deutschen oder was war anders Beispiel Klapse Problem wenn Sie eine Auswahl haben die in den Rucksack reinpasst oder die das zulässige Gesamtgewicht überschreitet und wenn sie keine weitere Stücken zu den können egal welches und dass die gesamte nicht überschreiten dann ist diese Auswahl die sie jetzt ist eingetroffen haben eine Basis das ist das ist der Herr der Begriff Basis hier und vielleicht schon die 1. des was das mit der Basen in jener über zu tun hat das sind natürlich immer maximale Mengen vor eine Basis 1 und darum so eines Raumes ist immer eine maximale Menge von Wiener unabhängigen Vektoren ja sie können innerhalb des in diesem Unterraum keine weiteren weckte hinzunehmen so dass das ganze Berliner unabhängig bleibt daher kommt diese Begriffsbildung ich hoffe
Sie haben es in der Algebra nicht so weit verdrängt ist was ich jetzt für Sie bewusst oder Vorbilder so das kann man einmal als Maxime Jungs Problem ja betrachten wir wollen ja wichtig sind hier die die kleinen feinen Unterschiede ich meine nicht Unterschied dass sie in Max und Hemmingstedt steht seine kleinen feinen Unterschiede die hier zwischen hier und hier Maximierung ist einfach zu formulieren wir wollen eine Auswahl finden also wir haben eine Unmenge gegeben ich sollte noch dazu sagen wir betrachten immer nur
endlich und so wie das auch im Beispiel gesehen haben entschieden dicke die kann man des Grafen ist bei uns es gibt auch es gibt auch die Ringe über unendlich große Grafen wir hier betrachten wir in die große Grafen Andy finde nun endlich vielen kannten Mertsching die Menge aller kannten den Grafen aus dem einen Menschen spielen kann ist eine solche endlichen Menge und sie sehen schon es ist auch kein Zufall dass in der Literatur diese diese Grundmenge immer groß ihr bezeichnet wird das kommt genau aus diesem Beispiel insbesondere zum Beispiel spannende Wälder wir diente die wie die Hintergrundes wurdest essen Kantenlänge deshalb groß e so
Maximierung sublimes wir wollen eine unabhängige man Menge finden so dass die das Gesamtgewicht maximal ist okay machen uns klar das wird automatisch immer eine Basis sein wenn wir wenn wir positive Katrin positive Gewicht auf den auf den Grund man haben hier alle allgemeinen ist das nicht der Fall ist nicht vorausgesetzt dass sämtliche Gewichte positiv sind aber wenn die Gewichte was wir in der Praxis der übliche Falles aber wenn ich alle positiv sind da wird es automatisch eine Basis sein denn wenn man den zu dem kann das hat positive zusätzlichen Profit immer noch einen und haben eine bessere Lösung gefunden bei Minimierung des ist was anderes er wenn die Gewichte aller positiv sehen ist in dieser Formulierung nicht zwingend gegeben aber es eben die typische Situation wenn die Gerichte eine positiv sind was ist die minimale Lösung die leere Menge toll aber das Problem der Problemstellung ich hier was aber das nicht das was man will was man will ist die kommt jetzt deutlich zum Ausdruck weil es nicht sich automatisch ergibt was man will ist immer eine Basis von minimalen Gesamtgewicht diese Bemerkung hier sollte sollte man nicht übersehen diese Menge aller verschiedenen unabhängigen Teilmengen ist nicht ist nicht aufgelistet wir haben keinen keine löste das ist eine Züge Freiheit Subkow das 1 zu 5 also groß das ist ein Züge für Fall so Graf und so weiter sondern wir gehen davon aus wenn wir wenn wir eine Teilmenge der Gesamtmenge haben eine Auswahl haben den gibt es da etwas was wäre das mal in Informatik gemein Orakel denn das hat nichts mit dem eingetragenen Warenzeichen zu tun haben es Ihnen in dieser Form der Begriff Orakel schon in Informatik typische was Informatik begegnet letztendlich also ob in ich würde Begriffes Blackbox sie stellen Anfrage und Sie kriegen antworten Sie haben keine Ahnung wie diese Verbrechen ist also sehr dezent Sie sie rufen Funktionen Prozeduren Methode auf und kriegen mehr geben wir geben in diesem Fall diese Teilmenge F freien und kriegen die Antwort Jahr es ist unabhängige Mengen eines ist keine ernannt werden das einheitliche System die man alle Züge freien sub Grafen eines gelaufen ist dann checkt dieses Orakel einfach Atemzüge muss oder nicht oder wenn es wenn das in die Unabhängigkeit System die Menge aller Mädchens eines Grafen sind daraus besteht dann Scheck dieses Orakel einfach ob irgendwo 2 Kanten ein Klon gemeinsam haben da gibts Wein aus und wenn sie wenn keine Sorge wir könnten einen Klon gemeinsam haben gibt es ja auch aus so ist der bisher das muss ich nur mal überlegen war unabhängige Menge genau unabhängige Menge von Knoten nennt man auch stabile Menge von Noten also die diesen Begriff finde sie aber diese Problem schaffen sie auch als Independent der Probleme am wir wollen eine möglichst große Menge von Knoten finden so bis nämlich immer Channel auf chronische Aufgaben wir wollen eine möglichst große Menge von Quoten findet um oder merke man möglichst großen Gesamtgewicht weil die Erfindung gewichtigen sind so dass keine Frage nur durch eine könnte man dann verbunden sind das ist das Maximum wälzt der bisher Problemen auch das ein und habe ich das System wenn sie auch so eine Menge von Knoten die sich alle gegenseitig nicht berühren Knoblauch rausnehmen ist die Eigenschaft weiterhin dafür dass sie sich gegenseitig die dieses Beispiel hier ist besonders wichtig weil es besonders beispielhaft ist Vorspiel Ort ist die Rundtouren sind keine unabhängige mehr denn wenn sie auch noch unter könnten aus Lehm ist kann rund um mehr aber sie die Rundtouren sind auf natürliche ich für fast ein trivialer Art und Weise die Basen einer einer 1 Unabhängigkeit Systems was sie sogar welche Systems das sind sämtliche Teilmengen von rund war das ist eine typische Situation ja wenn Sie sie sie haben automatisch immer wenn sie so wenn Sie wenn Sie so was wie Rundtouren beispielsweise haben als zulässige Lösungen sie haben immer wenn sie wenn sie sämtliche Teilmengen zu nehmen haben Sie automatisch trivialerweise mehr Trägersystem und können so zu er dann im und das Bild das eben die Fundierung aber für den der die Algorithmus dass sie umgekehrt Schritt für Schritt kann zu nehmen müssen und ist das 3. Beispiel damit da habe ich mich mit irgendjemand mal intensiv darüber gestritten ob das setzten sinnvoll Beispiel ist oder nicht haben ich lasse es mal aus ich bin war wenn sie mich Prüfung überzeugende sinnvolles Beispiel ist kann das nur gut sein für die Wartung von auf der Knapsack hatte wir eben das bei den Three hat mir also vor ist's genau wenn Sie wenn die zulässigen Lösungen die Spannen Bäume sind eines Grafen dann sind die Züge freien sub Craven das entsprechend induzierte unabhängig mehr alle Teilmengen der für der Spannung Bäume ist gerade die Menge der zu befreien Grafen zu der zu befreien so Grafen in diesem Baum in diesen Grafen Mädchen hatten wir auch schon gehabt und ich nochmal anzusprechen
so wir betrachten Maximierung das Problem wir sind es eigentlich so weit fertig also wir sollten an dieser Stelle jetzt Schluss machen sobald ein paar Minuten ein paar Minuten vielleicht noch ein 2 Minuten noch das hier sollte langsam aber sicher was auf dieser Folie steht sollte eine kleine Änderung ein groß vielleicht bei Ihnen provozieren was Markus Karl für maximal spannende Welt dar sie sortieren zu 1. die Kanten machen Gericht und dann betrachten Sie jeder eine einzelne kannte sie beginnen mit dem leeren Baum mehr Nieren Wald sie betrachten jeder einzelne kannte nach Gewicht und wenn diese kannte einzige schließt dann verwerfen sie wieder wenn sie kannte keine Züge schließt den Sie sich dazu genau das steht in abstrakter Form in den Begriffsbildungen der und eines Unabhängigkeit System steht hier auch wir sortieren zuerst die Elemente der Grundmenge fangen an mit mit einer leeren mit mit der Lehre Menge als man das unnatürliche Systems und solange wir nicht aus dem Munde welches System rausgehen durch Hinzufügen weitere Elemente der Grund der Menge solange lange fügen wir weiterhin zu so hier ist es vielleicht noch mal die Begründung dafür letztes Wort die Begründung dafür hier
steht von da vor ihm stand nicht aus dem positiven reellen Zahlen jeweils aber damit Sie mal Schluss Maximierung Problem
betrachten brauchen wir uns Ellen Menzel mit dem mit negativen gerichtlich anzuschauen die wir niemals in einer optimalen Lösung an an die sollten die meisten zu so damit sind wir für heute durch ich möchte mich bei Ihnen bedanken und wir sehen uns
dann beim nächsten Mal wieder
Loading...
Feedback
hidden