Descision-Based Approaches - Dynamic Programming / Greedy Algorithms
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| 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 | |
| Identifiers | 10.5446/21466 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
12
00:00
SequenceSimilarity (geometry)Matching (graph theory)Pairwise comparisonProcess (computing)Insertion lossSubstitute goodStandard errorString theoryFunction (mathematics)Computer programmingField extensionPrice indexFundamental theorem of algebraMathematical optimizationAerodynamicsString (computer science)ZifferOptimumIndexMilitary operationVariable (mathematics)NumberLengthSubstitute goodSign (mathematics)Set (mathematics)Finite setRing (mathematics)Physical quantityComputer animation
09:33
RecursionMatrix (mathematics)Hausdorff dimensionSequenceComputer programmingAerodynamicsString theoryFunction (mathematics)Graph (mathematics)Integral domainVertex (graph theory)Arc (geometry)Slide ruleLemma (mathematics)Sign (mathematics)IntegerKnapsack problemSubstitute goodNumberLengthEstimationIterationLogicKanteAdaptive optimizationGeometryLösung <Mathematik>String (computer science)Similarity (geometry)Recursive languageVolumeWegeproblemComputer animation
18:58
Lemma (mathematics)Sign (mathematics)IntegerKnapsack problemFunction (mathematics)Maxima and minimaWeightUniverse (mathematics)SummationPlant variety (law)PhysicistEstimationAdditionLogicCausalitySupremumHausdorff spaceTwo-dimensional spaceProduct (category theory)MathematicsAdaptive optimizationOptimization problemParameter (computer programming)Computer animation
28:23
IntegerFunction (mathematics)Maxima and minimaKnapsack problemMathematical optimizationSupremumOrder of magnitudeRecursive languageSet (mathematics)Hausdorff spaceNumberPlane (geometry)LengthLinear regressionComputer animation
37:49
IntegerKnapsack problemFunction (mathematics)Mathematical optimizationNatural numberLaufzeitLogicString (computer science)LengthNumberEnergieBinary numberKanteWeightParameter (computer programming)Scale (map)Moment (mathematics)SummationComputational complexity theoryZahlEigenvalues and eigenvectorsGrand Unified TheoryLogarithm
47:14
IntegerRecursionKnapsack problemDirected graphWeightArc (geometry)Längster-Weg-ProblemSlide ruleMaxima and minimaFunction (mathematics)Mathematical optimizationMaxwell's demonGreedy algorithmHeuristicStrategy gameTerm (mathematics)SpacetimeDecision tree learningLengthAdaptive optimizationNumberDirection (geometry)LaufzeitZahlComputational complexity theoryKanteMoment (mathematics)Social classWegeproblemCharakteristik <Algebra>Graph (mathematics)Weight
56:40
Greedy algorithmHeuristicStrategy gameTerm (mathematics)SpacetimeDecision tree learningIntegerKnapsack problemRecursionDirected graphWeightArc (geometry)Längster-Weg-ProblemFunction (mathematics)Maxima and minimaNetwork topologyRecursionGreatest elementSolution setTable (information)Raum <Mathematik>SubsetMaximum (disambiguation)Adaptive optimizationDecision tree learningLösung <Mathematik>SequenceRecursive languageDirection (geometry)SupremumComputer animation
01:06:05
Independence (probability theory)Physical systemInfinitySubsetSet theoryWeightGraph (mathematics)Vertex (graph theory)Graph (mathematics)Maxima and minimaHamiltonian mechanicsDirected graphMathematical optimizationCombinatoricsTravelling salesman problemShortest path problemSign (mathematics)Number theoryINTEGRALNetwork topologyMatching (graph theory)Spanning treeForestSpanning treeSet (mathematics)Power setSubsetStress (mechanics)Network topologyMilitary baseLinear subspaceEuclidean vectorNeighbourhood (graph theory)MathematicsRaum <Mathematik>KanteAlgebraLösung <Mathematik>OptimumCausalityForestMatching (graph theory)Vector graphicsUnabhängigkeitssystemSubgraphKantenmengeLinear algebraIndependence (probability theory)
01:15:30
Physical systemIndependence (probability theory)Maxima and minimaBasis <Mathematik>SubsetElement (mathematics)InfinitySet theoryMathematical optimizationWeightGraph (mathematics)Graph (mathematics)Vertex (graph theory)Hamiltonian mechanicsDirected graphCombinatoricsTravelling salesman problemShortest path problemNetwork topologyNumber theorySign (mathematics)Connected spaceMatching (graph theory)Spanning treeForestFunction (mathematics)Many-sorted logicNegative numberGreedy algorithmStress (mechanics)QuoteSet (mathematics)Independent set (graph theory)Maximum (disambiguation)Network topologySubsetWeightMathematical optimizationReal numberMilitary baseKanteFunction (mathematics)Black boxLösung <Mathematik>Physical quantityForestFinite setSpanning treeMaxima and minimaUnabhängigkeitssystemSet theoryTheoryMatching (graph theory)Finite set
01:24:56
Greedy algorithm
Transcript: German(auto-generated)
00:01
präsentiert von Open Learnware, die Plattform für Lernmaterialien an der TU Darmstadt. So, hallo allerseits. Ich denke, wir sollten nochmal zurückkommen auf das Thema, womit wir beim letzten Mal geendet hatten, weil ich das vielleicht ein bisschen zu
00:20
oberflächlich betrachtet hatte. Sie ändern sich. Dieses Beispiel zeigt ganz gut, worum es hier prinzipiell geht. Wir haben zwei verschiedene Strings über demselben Anwendungsfall. Bei DNA-Sequenzvergleich ist das ein Alphabet von vier Buchstaben,
00:40
die traditionell A, C, G, T sind, aus Gründen in einer biologischen Namensgebung. Und was wir herauskriegen sollen für diese zwei gegebenen Strings S und T, ist ein solches Alignment. Sie sehen, was da so passiert. Sie sehen Treffer. C trifft C, A trifft A, T trifft T, A trifft A und so weiter. Sie sehen Sprünge.
01:06
Also dieses G hier trifft kein Zeichen im String T. Oder umgekehrt, dieses A in T trifft kein Zeichen in S. Sie sehen aber auch hier noch, dass es durchaus Ersetzungen geben kann. Das ist die Edit-Distanz.
01:25
Das heißt also, wie viele Editieroperationen muss man tun, um einen String in den anderen zu überführen. Edieroperation heißt einfügen, löschen, substituieren.
01:40
Und Sie sehen, wir wollen diese Anzahl der Edierschritte minimieren, weil wir umgekehrt die Anzahl der Treffer maximieren wollen. Wir wollen wissen, wie viele Treffer gibt es? Das gibt uns die Information. Oder so ist definiert, wie ähnlich die beiden Strings sind.
02:01
Man könnte die Ähnlichkeit von zwei Strings auch anders definieren, aber diese Definition hat sich bewährt. Sie entspricht ungefähr dem, was man unter Ähnlichkeit intuitiv verstehen würde. Oder beispielsweise hier eine biologische Anwendung, was man hier als Ähnlichkeit braucht, um daraus biologische Rückschlüsse zu ziehen.
02:24
Und sie ist auch algorithmisch gut handhabbar, was wir letztes Mal schon ein bisschen gesehen haben. Geht aber ein bisschen über das, was ich jetzt gesagt habe, hinaus. Nämlich dahingehend, dass diese verschiedenen Operationen einfügen, löschen, also hier Minuszeichen und Substitutionen. Also hier C wird durch A substituiert,
02:44
um von String S zu String T zu kommen. Dass diese verschiedenen Operationen unterschiedlich viel kosten. Auf diese Größen, auf diese Allgemeinheit hin betrachten wir das. Das steht im Prinzip hier erst einmal. Gehen wir vielleicht nochmal ganz kurz diese Folie durch,
03:04
die wir beim letzten Mal unterschlagen, übersprungen hatten. Wir haben dieses Alphabet Sigma hier, fügen noch das Minus dazu als zusätzliches Zeichen. Das gibt uns dann das eigentliche Alphabet, mit dem wir operieren Sigma quer.
03:21
Und was ist jetzt ein Alignment? Diese beiden A quer B quer sind die beiden Input-Strings. Das war S und T auf der letzten Folie. Die sind, darf ich fragen, ob jemand von Ihnen keine formalen Grundlagen der Informatik gehört hat? Sie? Okay. Das ist eigentlich hier eine Notationsfrage.
03:41
Sigma quer Stern ist die Menge aller Strings, aller Zeichenketten über dem Alphabet Sigma. Das heißt also, was hier steht, ist nicht unter Ziffer 1, ist nicht anders als A und B sind Strings über dem Alphabet Sigma quer. Was rauskommen soll als Alignment, ist, so wie wir das auf der letzten Folie gesehen haben,
04:09
aufgefüllt notfalls hier mit führenden oder endenden Minuszeichen gleiche Länge für beide Strings. Und wir wollen keine totale Leerstelle haben. Es macht hier keinen Sinn,
04:21
eine Spalte zu haben, einen Index zu haben, wo in beiden Strings aufgefüllt wurde mit einem Minus. Deshalb schließen wir das von vornherein aus, obwohl das bei Optimalität sowieso automatisch ausgeschlossen würde. Schließen wir es einfach hier aus, weil es offenkundig sinnlos ist.
04:44
Das, was hier steht, nehmen wir jetzt nicht, müssen wir mal gucken, was im Einzelnen durchgeht. Was hier steht, ist das Umgekehrte, nämlich, was letztendlich hier unten in Otherverse steht, dass wir, wenn wir in diesem erweiterten Alphabet, Ursprungsalphabet mit diesem Minuszeichen,
05:03
einen String haben, der also auch Minuszeichen und zusätzliche Zeichen aus Sigma verhalten kann, dann ist die Einschränkung von diesem String W auf Sigma eben das, was rauskommt, wenn man sämtliche Minusse wieder rausstreicht. Also mehr steht hier nicht. Das ist ein bisschen komplizierter formuliert. Sie kennen das.
05:21
Wenn man das richtig, formal, korrekt formuliert, Sie kennen das aus der formalen Grundlageninformatik beispielsweise, dann wird man, sowas kommt Ihnen dann wahrscheinlich vertraut vor, wenn Sie Veranstaltungen gehört haben. Man wird solche Sachen typischerweise rekursiv definieren. Die Einschränkung eines Ein-Elemente eines einzelnen Zeichens aus dem Alphabet ist das Zeichen selber.
05:43
Die Einschränkung des Minuszeichens ist der leere String, also eines Strings, das nur als Minuszeichen besteht, ist der leere String, das leere Wort. Oder wenn Sie die Konkordination von zwei Strings haben, deren Einschränkung ist gerade die Einschränkung,
06:02
die Einschränkung der Konkordination ist die Konkordination der beiden Einschränkungen. Ja, so ist das Rekursiv definiert und sagt nichts anderes als, um zu der Einschränkung zu kommen, nehmen Sie sich den String her und streichen Sie alle Minuszeichen raus und drücken Sie es alles zusammen auf einen String wieder und dann haben Sie es.
06:27
So, wir führen ein bisschen intuitive Formulierungen, intuitive Begriffe ein. Ein Match ist, was wir in diesem Beispiel hatten hier, A und A ist ein Match, C und C ist ein Match, A und A, G und G, das sind Matches.
06:44
Eine Substitution, eine Ersetzung ist, das hatten wir glaube ich hier nur einmal, dieses C und dieses A, das ist eine Ersetzung. Und bei Einfügung und Löschen sehen Sie, die Definition ist jetzt ein bisschen asymmetrisch, bis jetzt hatten wir die Strings immer symmetrisch behandelt, ist egal,
07:01
welcher der erste, welcher der zweite ist. Wenn wir darüber sprechen wollen, und nur deshalb, dann betrachten wir es ein bisschen asymmetrisch, die Problemstellung ist weiterhin symmetrisch, es ist egal, welcher String der erste, welcher der zweite ist. Aber wenn wir darüber sprechen wollen, unterscheiden wir, eine Einfügung ist, wenn, also wir gucken von ersten String zum zweiten, eine Einfügung ist dann,
07:24
wenn hier vorher nichts war, so wie hier das Minuszeichen hier und hinterher hier das G ist. Und entsprechend eine Löschung, Deletion ist genau umgekehrt, wenn vorher hier irgendwo was war, im oberen String das G und hier im unteren String ist nichts mehr.
07:43
Was wir jetzt dann definieren können, ist für die verschiedenen Arten von Situationen, wir haben diese vier Situationen, wir können ja jeweils für jede Situation Kosten berechnen, also wie schwerwiegend ist es, dass wir eine Substitution vornehmen,
08:02
wie schwerwiegend ist es, dass wir eine Einfügung vornehmen, wie schwer ist es, wie sehr bestrafen wir das, dass wir eine Löschung vornehmen müssen. Prinzipiell gilt es auch für Matches, wie stark bestrafen wir, dass ein Match vorkommt, aber das ist natürlich irgendwie nicht der Sinn der Sache.
08:22
Das Modell, um einfach zu sein, erlaubt auch Bestrafungen von Matches, aber der Sinn der Sache ist natürlich praktisch in sämtlichen Anwendungen, die mir bekannt sind, und so auch in diesem Anwendungsbeispiel hier, ist der Sinn, möglichst viele Matches zu haben, also man würde Matches nicht bestrafen, man würde alles andere einfügen,
08:40
Löschungen und Ersetzungen bestrafen. So, dann ist die Distanz, wenn wir einfach einfügen, löschen und ersetzen, jeweils mit einem Zähler bestrafen, mit Kostenwert 1, dann kommt hier genau die Edet-Distanz raus. Wie viele dieser Operationen muss man tun, um den einen String in den anderen zu überführen,
09:01
aber wir sind etwas allgemeiner, also etwas wie eine gewichtete Version der Edet-Distanz. Jede Einfügeoperation, die wir machen, jede Löschoperation, die wir machen, jede Ersetzungsoperation hat einen bestimmten Kostenwert. Also alle Löschoperationen haben denselben Kostenwert, alle Einfügeoperationen haben denselben Kostenwert,
09:20
alle Ersetzungsoperationen haben denselben Kostenwert, aber die drei können unterschiedlich sein. So, das hatten wir schon soweit gesehen. Also wir wollen mit möglichst wenig Kosten, wir wollen wissen, entweder können wir sagen, ein Alignment, wie wir es gesehen haben,
09:42
oder die andere Blickwinkel, mit möglichst wenig Kosten von einem zum anderen zu kommen. Und da zumindest dann, wenn Einfügen und Löschungen gleich schwer ist, ist das weiterhin symmetrisch. Es ist egal, ob wir durch Einfügungen löschen von S zu T oder von T zu S kommen.
10:00
Erst dann, wenn Einfügungen und Löschungen unterschiedlich teuer sind, ist es nicht mehr symmetrisch. Dann spielt es eine Rolle, welcher der erste, welcher der zweite String ist. Das hatten wir beim letzten Mal hier schon betrachtet, hatten wir an der Tafel hier betrachtet, müssen wir nicht mehr weiter durchgehen. Also ich will noch mal sagen, die Videos sind in der Mache, die meisten sind schon gerendert,
10:23
sie sind sogar schon zum Großteil beim ELC hochgeladen, aber noch nicht freigegeben. Ich weiß nicht, was da ist. Ich habe jetzt jemanden aus meiner Arbeitsgruppe beauftragt, dass er sich da mal dahinterklemmt, dass das endlich mal was wird. So, das hatten wir betrachtet, aber viel schöner ist natürlich,
10:42
also sowohl ästhetisch schöner als auch vielleicht einsichtiger ist, ist diese Vorstellung hier, dass wir das Ganze verstehen als ein kürzester Wegeproblem. Hier hinten ist der Input auf der linken Seite, die beiden Strings tragen wir so ab
11:00
und bauen einen Grafen nach dieser Logik auf. Nämlich, wir haben für jede Einfügung, für die Löschung haben wir jeweils eine Kante, eine horizontale oder eine vertikale Kante. Das sehen wir vielleicht am besten hier rechts bei dieser Lösung, wenn Sie das schwarz da erkennen, ist ein bisschen schwierig zu erkennen.
11:23
Diese Kante vertikal runter entspricht dieser Einfügung, nein, dieser Löschung hier, das im ersten String ein G ist und im zweiten String ist da nichts mehr. Hier diese Einfügung, das oben nichts ist und unten ist ein A, entspricht dieser horizontalen Kante.
11:45
Nehmen wir uns hier zum Beispiel diesen Match her, T, das entspricht dieser diagonalen Kante hier. Und dieser Substitution, diese Ersetzung entspricht dann, wo sind wir hier, dieser vertikalen Kante.
12:04
Und jetzt können wir auf diese Kanten, das ist durch die Farben angedeutet, die Farben sind etwas unglücklich gewählt, weil nach Schätzungen mehr als 10% der Bevölkerung grob grün blind sind. Und Sie können sich merken für Ihre späteren Vorträge
12:21
oder sonstigen grafischen Gestaltungen, dass so schön Symbol kräftiger rot und grün ist, dass es keine gute Kombination ist, um verschiedene Dinge verschieden zu gestalten wegen dieser weit verbreiteten rot-grünen Blindheit. Hier durch diese Farben trotzdem, in diesem Fall ist es nicht so problematisch,
12:45
weil die unterschiedlich gefärbten Kanten rot und grün auch unterschiedlich verlaufen. Die roten sind die Einfügungen und Lösungen, kann man mit zwei belegen, die Substitution mit drei, ich weiß nicht warum die nicht mit vier belegt sind,
13:00
das würde für mich eher Sinn machen, aber so funktioniert es eigentlich auch, glaube ich. Und dann will man einen kürzesten Weg finden, von da nach da, von oben links nach unten rechts. Und kürzester Weg heißt, so selten wie möglich Einfügungen, Lösungen und Ersetzungen,
13:20
also so oft wie möglich ein Match, das was man letztendlich haben will. Also, Entschuldigung, ich habe jetzt etwas falsches gesagt, als ich gesagt habe, ich verstehe nicht, warum hier eine 3 und nicht eine 4 steht, es ist ja nur ein Beispiel. Und wenn man ein Beispiel kreiert, ist man natürlich frei darin, die Zahlen so zu wählen, wie man es will.
13:40
Was ich eigentlich meinte, ist, wenn wir an unser Anwendungsbeispiel oder an die Edelstanz zurückdenken, wenn wir konkrete Edelstanz hernehmen, dann würde es genau hinkommen, wenn wir hier beispielsweise bei der 2 bleiben, bei Insert Intelligent und hier auf 4 statt 3 gehen. Also eine Substitution ist dasselbe.
14:01
Entschuldigung, Edelstanz wäre, wenn hier auch eine 2 stünde, jetzt haben wir es langsam, bei der Substitution, wenn Sie hingegen eine Substitution, eine Ersetzung auffassen, als eine Löschung plus eine Einfügung, so kann man das ja auch auffassen, so kann man ja auch Edelstanz definieren, dann würde hier sinnvollerweise eine 4 stehen.
14:22
Oder man würde die Kanten sogar ganz streichen, dann würde Löschung und Einfügung eben durch rote Kanten von vornherein realisiert. Wir hatten es beim letzten Mal an dieser Stelle auch schon angedeutet, das will ich aber auch nicht weiter vertiefen, dass generell das kürzeste Wegeproblem,
14:42
das steigste Problem von einem Knoten zu einem anderen, die kürzesten Wege bzw. die Distanzen zu finden, dass dieser Algorithmus ein Beispiel für dynamische Programmierung auch ist. Es gibt eine Rekursionsformel, die Länge eines kürzesten Weges von s zu einem Knoten v ist das Beste, was man kriegen kann, wenn man einen fährt,
15:05
zu irgendeinem Vorgänger. Die Länge eines kürzesten Weges von startknoten s zu v
15:33
ist die Länge eines kürzesten Weges zu irgendeinem Vorgänger, die 1, 2, 3, 4 plus dieser Länge.
15:43
Das Beste, was man aus diesen 4 Möglichkeiten hat, ist der kürzeste Weg, der kürzeste Distanz von s und v. Das gleiche Thema, das wir die ganze Zeit getan haben hier, nämlich aus der Rekursion die Rekursion umzudrehen, zu einer Iteration zu machen und Schritt für Schritt
16:03
vom startknoten aus, vom einfachsten Fall immer Schritt für Schritt das weiter aufzubauen. Weil, aus demselben Grund wie immer, werden wir einfach, man könnte natürlich auch einfach Rekursionsformeln implementieren, nichts implementieren,
16:21
aber sie müssen zum Beispiel, es werden wenige, wenige Wege unendlich, unendlich oft, aber sehr, sehr oft, viel zu oft immer wieder neu berechnen und wieder verlaufen.
16:40
So, das ist nichts anderes 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 in der Prüfung, wenn wir über diese Dinge reden, wenn Sie mir beispielsweise hierzu was sagen können, diese Dinge erklären können.
17:01
Erwarte ich selbstverständlich nicht von Ihnen, dass Sie mir dann sagen, und wie sieht das jetzt gemäß verbaler Beschreibung auf den Folien aus? Die ändern sich, das war eine Folie weiter, selbstverständlich nicht. Wenn Sie hingegen von sich aus meinen, Sie möchten es lieber auf diese Art und Weise darstellen, meinen wegen. So, sind wir damit durch.
17:21
Ein weiteres Beispiel für dynamische Programmierung, dann haben wir dynamische Programmierung auch abgeschlossen. Das ist ein Problem. Manchmal sagt man, das ist ein Möbelwagenproblem oder Ähnliches. Möbelwagen ist vielleicht ein gutes einschauliches Beispiel. Sie haben ein Möbelwagen.
17:45
Sonst würde es ja nicht Möbelwagenproblem heißen. Und Sie haben schwere Möbel daran zu transportieren. So schwer, dass die Geometrie keine Rolle spielt. Also, dass Sie wissen, wenn das zulässige Gesamtgewicht nicht überschritten ist,
18:00
dann wird man das schon irgendwie in den Wagen reinkriegen. Das heißt also, es geht darum, möglichst viel an Gewicht reinzutun in diesen Möbelwagen, sodass das zulässige Gesamtgewicht natürlich nicht überschritten ist. Versteht sich.
18:20
Oder genau gesagt, die maximal zulässige Zuladung. Das kann man aber noch einen Schritt weiterführen. Das ist nur ein Spezialfall vom Integer-Knapp-Sack-Problem, also Rucksack-Problem. Man kann auch sagen, bleiben wir beim Beispiel Rucksack auch,
18:43
die Dinge, die man in einen Rucksack, das ist ja selbe letztendlich, die Dinge, die man in einem Rucksack laden kann, sind nicht nur unterschiedlich schwer, es muss nicht das Kriterium Gewicht sein, es kann auch das Kriterium Volumen sein, sind unterschiedlich schwer
19:01
und Sie sagen sich, Sie wollen nicht mehr als 30 Kilo schleppen, ich sage es Ihnen mal um eine Zahl, weiß ich nicht, also ich glaube, ich würde nur unter Protest 30 Kilo schleppen wollen, aber die Dinge haben auch noch einen gewissen Wert. Wenn Sie schon eine Auswahl mitnehmen wollen, dann wollen Sie nicht die 30 Kilo
19:21
möglichst genau vollkriegen nur, sondern was Sie eigentlich wollen ist, wenn die Dinge unterschiedlichen Wert haben, den Wert zu maximieren unter dem, das Gesamtgewicht, also der Wert von dem, was Sie mitnehmen, unter dem, dass das Gesamtgewicht insgesamt die 30 Kilo nicht überschreitet. So, die Gewichte sind hier die AJs,
19:42
also wir haben zunächst einmal N, N wie Nordpol, hier sind verschiedene Stücke, die wir im Rucksack oder sonst wohin reintun wollen, wir werden es nicht schaffen, die alle reinzutun, sonst wäre es einfach zu lösen, wir werden es nur schaffen, eine Auswahl davon reinzutun,
20:01
die Gewichte sind die AJs, die Auswahl, die Auswahl wird beschrieben durch 01-Werte, xj bedeutet für das Stück Nummer J, also wir stellen uns vor, die sind einfach indiziert, 1 bis N,
20:21
für das Stück Nummer J, bedeutet xj gleich 1, dass dieses Stück drin ist, dass wir dieses Stück in unsere Auswahl hineinnehmen, dass wir die in unseren Rucksack hineinnehmen oder in den Möbelwagen, xj gleich 0 bedeutet, dass wir dieses Stück nicht in unserer Auswahl haben, dass wir es nicht mitnehmen im Möbelwagen bzw. im Rucksack.
20:41
Und die Profite werden sinnigerweise mit C wie Kost hier und nicht mit P wie Profit abgekürzt, aber gut, das sind die Sorten von Abstrahierungen, die man denke ich in der Informatik erwarten darf, dass das geht.
21:00
Nicht so wie diese Fälle, die immer mal wieder auftreten, in Service-Veranstaltungen der Mathematik, wo sich dann Studierende an nach welcher beschweren, wir haben nur gelernt, Summe I gleich 1 bis N, Summe J gleich 1 bis M kennen wir nicht. Also Sie verstehen
21:20
den Abstrahnschritt, über den wir hier reden. So, diese C wie Kost sind also Profite, die wir maximieren wollen, Kosten wollen wir natürlich nicht maximieren, sondern Profite. Nach derselben Logik. Das Produkt besagt ja immer, was bedeutet dieses Produkt, wenn aj das Gewicht des j-Stückes ist und xj ist 0 oder 1 und 1 bedeutet,
21:42
es ist dabei. Das bedeutet, wenn das j-Stück nicht in der Auswahl ist, dann ist dieser Summand 0, wenn dieses Stück in der Auswahl ist, wenn also xj gleich 1 ist, dann ist dieser Summand gleich aj. Das heißt, was wir effektiv aufzählen, ist die Summe der Gewichte in der Auswahl. Und genauso hier, dieselbe Logik, was wir effektiv aufzählen,
22:02
ist die Summe der Profite derjenigen Stücke, die in unserer Auswahl sind. Und diese Auswahl ist durch die x-Werte aus 0 und 1 gesteuert. Also wir wollen solche x-Werte 0 und 1 finden, so ein x aus sogar ganzzahlig, wieso ganzzahlig? Und nicht 0,1?
22:22
So wie es hier formuliert ist, haben sie sogar von jedem dieser einzelnen Stücke eine bliebig große Auswahl. Aber ich glaube, dass sie nicht nur ein Stück von dieser Sorte haben, sondern bliebig viele zur Auswahl haben und sie können auch mehrere reinnehmen. Aber ich glaube, im weiteren
22:40
Verlauf wird das eher der Fall betrachtet sein, dass sie von jeder Sorte nur ein Stück haben. Also nehmen wir das hier auch schon an. So, hier ist die Einschränkung. Das Gesamtgewicht darf nicht größer sein als die zulässige Zuladung oder die 30 Kilo beim Rucksack. Minus Eigengewicht des Rucksacks, versteht sich. Und das ist dann
23:01
der Gewinn, den wir maximieren wollen. Das Übliche, Sie kennen das schon hier, bei Optimierungsproblemen aus der Realität kann man fast blind drauf wetten. Fast, natürlich nur. Fast blind drauf wetten, dass die Problemstellung jeweils endlich schwer ist. Sie wissen,
23:20
was das praktisch bedeutet. Wir haben hier nicht thematisiert, was es theoretisch bedeutet. Wir haben aber mehrfach schon thematisiert, was es praktisch bedeutet. Es bedeutet, für jeden Algorithmus, der überhaupt nur denkbar wäre, ob ihn kennt oder nicht. Also, für jeden Algorithmus, der in dieser Welt, in diesem Universum
23:41
denkbar wäre, gibt es Beispiele, Instanzen von relativ kleiner Größe, auf denen dieser Algorithmus sich tot rechnen würde. Also, tot rechnen würde heißt, die Zeit, die nach Schätzung der Physiker für dieses Universum noch übrig bleibt, wird definitiv nicht
24:00
ausreichen. Es werden noch ein paar weitere Universen notwendig sein, bis der zum Ende kommt. Keine gute Situation, aber das ist leider die typische Situation in der Realität, in der Praxis. Und genau darum geht es bei Optimierungsalgorithmen mit solchen Situationen umzugehen.
24:21
Wollen wir diese Folie betrachten? Ich glaube, da kommen wir später nochmal. Oder, ne, wir betrachten die Folie, aber wir gucken uns genauer an. Wir gucken uns genauer an,
24:40
was hier dabei herauskommt, was das eigentlich bedeutet, hier, was hier steht, nämlich, wir haben wieder so ein zweidimensionales Schema, wie wir das jedes Mal bisher
25:02
gekannt haben. Also, eigentlich bei jedem Beispiel, das wir betrachtet haben zu dynamischer Programmierung, hatten wir so ein zweidimensionales Parameterschema. Und das ist kein Zufall, das ist eigentlich eher typisch. So, was Sie hier haben abgetragen,
25:21
von 0 bis irgendwo B haben Sie, das ist das, was auf dieser Folie das Lambda ist. Nehmen wir uns irgendeinen Wert her. Und das, was Sie hier abgetragen haben, ist
25:42
von 0 ebenfalls bis N, die Anzahl der Stücke, das ist R. R ist, mal ich mal so, ist kleiner gleich N und größer
26:01
gleich 0. Also, wir fangen mit dem trivialen Fall 0 und 0 an, in unserer Situation. So, und was steht hier? Was wollen wir hier für diese Kombination berechnen? was wir hier berechnen wollen,
26:22
ist die optimale Auswahl aus nicht x1 bis xN, sondern nur bis xR.
26:44
Also, diejenige, die I gleich 1 bis N, ne, nicht bis N, sondern eben bis R, C, I, xI maximiert,
27:04
sodass jetzt nicht D, unser eigentlicher oberer Schranke, sondern erst mal diese Zwischenober Schranke, sodass Gesamtgewicht
27:22
kleiner gleich dieser Zwischenober Schranke ist. Was ist das Gesamtgewicht? Ci, nein, nicht Ci, sondern das sind die AIs jetzt, xI, I gleich 1 bis R, kleiner gleich Lambda. Schrittweise bauen wir wieder die Lösung auf.
27:41
Mit dem Hintergedanken, das ist jetzt hier, jetzt kommen wir hier wieder zurück, also dieser Wert, den ich hier abgetragen habe, der wird auf dieser Folie GR Lambda genannt und es definiert, gut, es definiert so, wie es da steht,
28:00
also machen wir hier eine Gleichheit als Aussage und es gemäß Definition identisch mit der optimalen Auswahl oder mit dem Wert, dem Profit der optimalen Auswahl aus diesem Teil aller Stücke, sodass diese Bedingung erfüllt ist.
28:21
Jetzt haben wir wieder so ein Schema, dass wir schrittweise das aufbauen können. Rekursiv, nämlich
29:08
das Schema GR Lambda können wir wieder konstruieren
29:21
aus GR minus eins Lambda, also die optimale Auswahl, wenn wir das Stück Nummer R gar nicht brauchen
29:42
und aus dem, das brauchen wir hier nicht, GR auf dieser Ebene, ein gutes Stück weiter weg, in diesem Schema GR von
30:00
Lambda minus AR Was steht da in dieser Rekursion? Hab ich was vergessen? Ach so, das muss ich noch... Ja gut, was ich hier habe, sind die Einträge in diesem quadratischen Schema.
30:20
Die müssen noch mit diesem Profitwert, der muss noch dazu kommen, richtig. Aber das ist nur sozusagen, woher man die Werte hat in diesem quadratischen Schema, um diesen nächsten Wert zu berechnen. Dass da noch
30:41
eine Formel dazu kommt, ja. Was steht hier letztendlich? Was hier steht ist, das lässt sich gut verbalisieren, die optimale Lösung für dieses R, also diese ersten R-Stücke und diese obere Schranke Lambda, es gibt zwei Möglichkeiten, wie diese optimale Lösung aussieht.
31:02
Eine Möglichkeit ist, dass das Stück Nummer R drin ist oder die andere Möglichkeit ist, dass das Stück Nummer R nicht drin ist. Das hier ist, heißt, Stück
31:22
Nummer R ist nicht in der optimalen Auswahl für R und Lambda, ja.
31:46
Wenn es nicht drin ist, wenn dieses Stück nicht drin ist, dann ist die optimale Auswahl für R und Lambda identisch mit der optimalen Auswahl für R-1 und Lambda. Weil nur die Stücke 1 bis R-1
32:00
drin sind. Das hier wiederum ist hingegen die Situation in dem Stück Nummer R ist in der optimalen Auswahl. Was ist die optimale
32:21
Auswahl in diesem Fall? Das ist dieses Stück Nummer R plus der optimalen Auswahl für diese obere Schranke, ja, für die jetzt betrachtete obere Schranke, wo dieses Stück R drin sein soll, dem AR, weil das ja noch mit reinpassen
32:42
muss. Ja, wenn vielleicht kann ich das nochmal ganz kurz, damit das deutlicher wird, anzeichnen.
33:26
Wenn Sie eine optimale Auswahl haben, die, ein bisschen länger vielleicht, die in die Gesamtkapazität
33:41
bis L reinreicht und Sie haben das Stück Nummer R drin, dann haben Sie hier also die Länge AI und was ist die optimale Auswahl aus den ersten R-Stücken,
34:02
wo Sie unter der Bedingung, dass das Stück Nummer R drin ist, halt hier ist ein R, so, das ist die optimale Auswahl von den ersten R-1-Stücken, die hier rein passt noch in die
34:20
optimale Auswahl aus 1 bis R-1, sodass da noch genug Platz ist, um dieses neue Stück dazu zu tun und deshalb gehen wir etwas ungewohnt, nicht einfach, hier sind wir einen Zähler runtergegangen,
34:41
von R nach R-1, hier gehen wir nicht einen Zähler runter, sondern wir gehen gleich die ganze Länge von AR runter, denn wir brauchen ja, damit die Regression funktioniert, wir müssen den Platz haben, für das Stück Nummer R und das heißt halt, wir müssen die optimale Auswahl betrachten,
35:00
für für die Oberschranke lambda minus AR, denn das, was hier steht, denn diese Länge ist ja gerade dann lambda minus AR,
35:26
ach so, hier ist G von R angegeben
35:41
und nicht G von R-1, ach so, sie sagen, weil hier ein R steht, also man muss immer natürlich die Möglichkeit auch betrachten, ob das nicht vielleicht ein Tippfehler ist, nehmen wir mal an,
36:01
das ist kein Tippfehler, kann ich jetzt nicht genau sagen, sie sagen, weil hier R steht, sind wir doch wieder in der Situation, konsistent auch mit dem, was hier oben steht, dass wir nicht nur ein Stück von dieser Sorte haben, sondern beliebig viele. Macht irgendwie für mich Sinn, ja?
36:20
Stimmt, das ist in sich plausibel, ja? Gut, wieder was dazu gelernt, danke. So, das andere sind jetzt die Rahmenbedingungen, die brauchen wir uns jetzt hier nicht angucken. So, wie teuer ist dieser Algorithmus? Na ja, so teuer wie das quadratische Schema eben ist, jeder einzelne Wert zu berechnen
36:41
in diesem quadratischen Schema kostet konstanten Aufwand, weil wir ja nur auf zwei verschiedene andere Werte zugreifen müssen und das mit dieser relativ einfachen Formel alles verwursteln. Und wie groß ist dieses quadratische Schema? Das hatten wir vorher an der Tafel. Die eine Dimension geht bis groß B
37:01
und die andere Dimension bis klein N und dann haben wir genau diese Größenordnung eines Algorithmus. So. Komisch. Ich hab eben auf der letzten Folie gesagt, dass das Problem endlich schwer ist. Und jetzt auf einmal haben wir so einen effizienten Algorithmus da.
37:22
Wie kann das sein? Hier sehen Sie nochmal ein Zahlenbeispiel erst einmal. Das gehen wir jetzt nicht durch. Das können Sie sich zum Gegencheck Ihres Verständnisses können Sie sich das zu Hause selber anschauen. Da kommen wir gleich hin.
37:41
Warum ist das Problem auf der einen Seite endlich schwer? Also gar nicht gut lösbar. Und warum ist es auf einmal hier doch recht gut lösbar? Der Punkt, dieser Widerspruch löst sich auf durch etwas, was ich bisher nicht so thematisiert hatte.
38:00
Nämlich was heißt was genau bedeutet das, dass diese Laufzeit so dramatisch schlecht ist bei NP-Schwer? Was bedeutet das, dass bei moderat kleinen Beispielen schon die Laufzeit so dramatisch ist? Was ist die Größe eines Beispiels? Sie sind daran gewöhnt, die Größe eines Beispiels nehmen Sie
38:21
GDI2 her, sortieren. Die Größe eines Beispiels drücken Sie aus in der Anzahl der Elemente in der Sequenz. Bei Bucket Sort machen Sie es ein bisschen anders. Da nehmen Sie dann noch die Länge der Strings hinzu, um die Größe einer Eingabe darzustellen. Wenn Sie ein Grafenproblem haben, wie Dijkstra oder ähnliches,
38:44
wenn Sie so einen Algorithmus haben, dann sind Sie daran gewöhnt, die Größe einer Eingabe in der Anzahl der Knoten und der Anzahl der Kanten anzugeben. Wenn man so komplexitätstheoretisch fundamentale Sachen betrachtet, wie NP-schwer
39:00
in der Komplexitätstheorie, in einem Teilgebiet, letztendlich einem Teilgebiet der mathematischen Logik, dann muss man sich genauer, muss man sie genau festklopfen, festdefinieren, was man unter Größe einer Instanz ansieht, einer Eingabe, und man hat
39:20
sich dazu entschlossen, die Größe einer Eingabe eben durch die Kodierungsgröße darzustellen. Das hat aber eine Konsequenz. Der einzige Fall bei der GE2, unter den typischen Algorithmen, die dort gelehrt werden,
39:41
der einzige Fall, wo das tatsächlich durchgehalten wurde, ist Bucket Sort. Die Größe der Eingabe ist die Summe aller Zeichen, aller Strings, die eingegeben werden zum Sortieren. Schon bei Bucket Sort oder ähnlichem stimmt es nicht ganz, denn sie haben ja eine, wenn sie sagen, die Anzahl der Elemente in der
40:02
Eingabe-Sequenz, das stimmt nicht. Es könnte zum Beispiel ja auch, die Eingabe-Elemente könnten ja beispielsweise Strings sein. Strings, deren Größe abhängig von N ist, die die die genauso viele
40:23
Zeichen haben oder letztendlich unendlich viele Zeichen haben beliebig viele Zeichen haben können. Und natürlich ist der Algorithmus wie Quick Sort da nicht wirklich n log n oder n², weil für jeden Vergleich zweier Elemente,
40:42
wenn es zum Beispiel Strings sind, müssen sie ja Zeichen für Zeichen gegebenenfalls, wenn sie sich am Anfang sehr ähnlich sind, wenn sie am Anfang identisch sind, müssen sie ja Zeichen für Zeichen vergleichen, bis sie irgendwo mal herausfinden, der eine ist kleiner, der andere ist kleiner. Ja, das stimmt eigentlich nicht ganz, also er stimmt schon in gewisser Weise,
41:01
aber es entspricht nicht dem, was man in der Komplexitätstheorie betrachtet, auch schon nicht, wenn sie Zahlen betrachten. Sie sind daran gewöhnt, zwei Zahlen miteinander zu vergleichen, kostet konstanten Aufwand. So haben sie es in der GD2 auch gelernt, selbst wenn sie es bei mir gelernt haben, haben sie es so gelernt.
41:21
Stimmt natürlich aber nur, solange diese Zahlen alle in die in die in die Größe des Datentyps Long oder Double oder was hineinpassen. In dem Moment, wenn das nicht mehr der Fall ist, wenn sie von wirklich beliebigen Zahlen ausgehen,
41:40
wenn sie also so eine Datenstruktur wie ein Java Bigint glaube ich, oder Bigintische heißt das, ich weiß nicht genau, irgendwie so was ähnliches, also wo sie beliebig lange natürliche Zahlen ausdrücken können, da stimmt das natürlich nicht mehr, weil dann kommt es darauf an, wie groß diese Zahl ist, wieviel
42:00
Speicherplatz das ist, und je mehr Speicherplatz das ist, umso mehr müssen sie potentiell miteinander vergleichen, um festzustellen, welche der zwei Zahlen kleiner ist. Die Speichergröße ist aber, von Zahlen ist aber logarithmisch. Das haben sie mal irgendwo mitgekriegt. Vielleicht sogar schon in der Schule. Deshalb sind wir hier beispielsweise
42:22
die Kodierungslänge der Zahl groß b ist der Logarithmus von b. Wenn Sie das als ein String, 01 String ganz normal im Binärsystem kodieren, dann kriegen Sie genau das raus.
42:46
NP-Schwer heißt zunächst einmal Folgendes, wir haben das bis jetzt nicht thematisiert, jetzt müssen wir es aber mal tun. NP-Schwer heißt, es gibt nicht mal eine, einen
43:02
Algorithmus, der auch nur Polynomial Laufzeit hätte, der dieses Problem löst. Polynomial kann beliebig schlecht sein. Es muss ja nicht N hoch 3 sein, oder N hoch 2, wie Sie es aus der GD2 kennen. Es kann auch N hoch 1 Millionen sein. Selbst einen solchen Algorithmus, dessen Laufzeit
43:20
durch N hoch 1 Millionen nach oben beschränkt ist, kann es nicht geben für ein NP-Schweres Problem. Und Sie können das weiterführen, N hoch 1 Milliarde oder was auch immer. Schlechte Nachrichten. Aber, es ist auch tatsächlich so, beim Integer-Knapster Problem, wenn Sie die Kodierungslänge
43:40
hernehmen, als Maßstab dann in dieser komprimierten Größe, wird es keinen Polynomialen Algorithmus geben. Aber, wir betrachten die Situation jetzt aus einem anderen Blickwinkel. Ich will vielleicht eher
44:00
das in Worten beschreiben, als das jetzt hier zu sagen. Ich komme dann vielleicht darauf wieder zurück. Folgendes. Wenn Sie so ein Beispiel hernehmen, wie das mit dem Rucksack, oder nehmen Sie das Beispiel mit dem Möbelwagen her,
44:21
dann würden Sie eine gewisse Granularität in der Gewichtsmessung haben. Wenn Sie da schwere Möbel packen, dann werden Sie vielleicht auf die Granularität von ganzen Kilogramm runtergehen. Oder wenn Sie unbedingt wollen, vielleicht auf die Granularität von ganzen Vielfachen von 100 Gramm. Aber mehr werden Sie da bestimmt nicht machen. Sie werden bestimmt nicht auf
44:40
ein Mikrogramm oder etwas herunter die Gewichte von den Möbeln genau bestimmen. Sie haben eine starke Granularität. Und wenn Sie ein zulässiges, sagen wir mal, ein Kilo und wenn Sie ein zulässiges Gesamtgewicht oder eine zulässige Zuladung von, ich fabuliere mal, zwei Tonnen haben, dann heißt das, die Größe, in der sich alles abspielt,
45:01
die Zahlengröße, in der sich alles abspielt, ist bis zu 2000. Über 2000 gibt es nichts mehr. Eine Summe von Möbelstücken über 2000 brauchen Sie gar nicht zu betrachten. Einzelne Möbelstücke, die mehr als zwei Tonnen wiegen, brauchen Sie nicht zu betrachten, falls es die dabei haben.
45:23
Und das heißt also, worauf ich hinaus will, ist, in dieser Sichtweise werden Sie sagen, in dieser Sichtweise macht es Sinn. Es ist anders gezählt, die Komplexität in anderen Parameter, nicht in der Inputgröße,
45:41
wo alles logarithmisch codiert ist, Sie sehen sozusagen Kilo für Kilo an. In dieser Sichtweise ist das Ganze effizient lösbar. Wenn hier das B 2000 ist, also Granularität ein Kilogramm
46:02
und das B hat 2000 Kilogramm und N ist sicherlich auch nicht zu groß, dann spielt es überhaupt keine Rolle, ob das gemessen an einer wirklichen, an der wirklichen Inputgröße, wo die ganzen A-Werte und C-Werte alle nur logarithmische
46:21
Größe haben, sodass im Verhältnis zu diesen kleinen, kompakten Codierung, wie man sie in Komplexitätstheorie betrachtet, der Laufzeit riesengroß ist, aber gemessen an den, nicht an der Codierungsgröße, sondern an den wirklichen eigentlichen Integern, die exponentiell groß selber
46:41
in der ihrer eigenen Codierungsgröße sind. Jede Zahl ist exponentiell groß in ihrer eigenen Codierungsgröße, weil umgekehrt die Codierung einer Zahl logarithmisch ist. Wenn Sie also nicht in der Codierungsgröße der Zahlen das Ganze betrachten, sondern in den Zahlen selber,
47:00
was man in der Komplexitätstheorie eben nicht macht, aber hier schon, dann ist das Ganze im Verhältnis dazu doch effizient lösbar, und zwar sehr effizient lösbar. Das ist das, was dahinter steht und solches Verhalten, wenn wir also nicht die Codierungsgröße der Zahlen, sondern die Zahlen selber hernehmen,
47:21
wenn das dann nicht mehr so gruselig schlechte Laufzeiten hat, dass es nicht mal ein hoch eine Million oder ein hoch eine Milliarde oder sonst was ist, dann nennt man diese Problemstellungen oder diese Algorithmen eigentlich die Problemstellung pseudopolinomial. Nicht polinomial, aber, weil das würde bedeuten
47:40
polinomial in der Inputgröße, aber pseudopolinomial polinomial in den Zahlen selber, die für sich schon exponentiell in der Inputgröße sind. Also durch diesen Unterschied zwischen den Zahlenlängen, zwischen der Größe der Zahl und ihrer Codierungsgröße versteckt sich der Unterschied. Das ist gemessen an der Codierungsgröße, wie man das in der Komplexitätstheorie betrachtet,
48:03
gruseligen Aufwand hat, aber gemessen an den Zahlen selbst kein gruseligen Aufwand hat. Ist öfters mal die Situation so, aber leider nicht immer so. Es wäre schön, wenn das immer so wäre, dann könnten wir diese eine Folie auflegen und dann wäre die ganze Vorlesung für das ganze Semester mit dieser eine Folie erledigt. Aber da es nicht immer so ist,
48:21
müssen wir noch weiter, müssen wir noch viele andere die Ansätze betrachten, die wir bisher noch betrachtet haben und die wir noch betrachten werden. So, jetzt gehe ich noch eine Folie zurück. Knapsack als ein Wegeproblem. Wir hatten auch wieder nicht überraschend. Ich denke, das ist auch eine typische Situation,
48:42
dass man in dynamische Programmierungsansätze auch verstehen kann, als Wegeprobleme. Das hatten wir eben beim Alignmentproblem schon, hier auch in einer etwas anderen Situation. Was ist hier diese, was ist hier der Graph? Der Graph geht durch sämtliche Werte
49:01
von Null bis zu Groß B. Also das Sechs ist in diesem Beispiel hier das Groß B. Sie sehen, es gibt eine Kante jeweils von einem Wert
49:21
zum nächsten. Diese Kante drückt aus, dass wir in dieser drückt im Grunde diese Beziehung hier aus, dass wir von R-1 ne, Entschuldigung, das ist falsch, was ich hier jetzt sage.
49:45
Ne, es ist eine etwas andere dynamische Programmierung. Es drückt aus, dass wir von einem Lambda Wert zum nächsten Lambda Wert gehen ohne also es ist nicht dieses quadratische Schema, es ist ein anderes Schema.
50:01
Gut, dass ich das noch rechtzeitig gemerkt habe. Steht hier auch Another Recursion. Wer lesen kann es klar im Vorteil. Dass man von einem Lambda zum nächsten Lambda geht, ohne dass sich was ändert. Also eine Möglichkeit,
50:20
wie 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 B gleich 6 identisch ist mit der optimalen Lösung für B gleich 5. Das heißt, dann würde man die optimale Lösung durch den grafenden Durch bis 5 hernehmen und dann noch diesen Schritt, um anzuzeigen, von 5 nach 6 passiert
50:40
nichts mehr. Ist im Allgemeinen nicht unbedingt so. Was Sie sehen, ist hier für jede, für jedes Stück und hier ist jetzt auch notwendig sogar, dass die Stücke öfters vorkommen können. Hier geht es, in dieser Formule geht es
51:00
gar nicht anders. Für jedes Stück, das Sie haben, hier sehe ich, was haben wir hier? Wir haben eine Stück Länge 6, eine Stück Länge 10, eine Stück Länge 15 und eine Stück Länge 16 oder Gewicht. In unseren Beispielen waren es immer Gewichte. Und ein Fahrt von links nach rechts, von 0
51:22
nach 6, kann man verstehen als eine Auswahl. Wir wählen einmal die 10 gehen über diese Kante, wählen einmal die 6 gehen über diese Kante und wählen nichts mehr, dann gehen wir über diese Kante, gehen wir zu dieser Kante hier. Wobei, Entschuldigung,
51:41
diese Zahlen sind die Profite, diese 6, 10, 15, 16 sind die Profite. Das Gewicht ist ausgedrückt durch die Länge der Kante. Diese Kante geht von 0 bis 3, das heißt sie hat Länge 3, Gewicht 3 in unseren Beispielen. Diese Kante hier, diese Kante hier, die Profite 6
52:02
tragen, haben Länge 2, das heißt sie haben Gewicht 2 und so weiter. So, wenn ich jetzt einen Fahrt so betrachte, der kann ja durchaus auch mittendrin sogar nochmal eine 0 habe, ist eigentlich egal, irgendein Fahrt. Vielleicht erst diesen Fahrt hier,
52:21
diese Kante hier zu nehmen, 3 Schritte weiterzukommen, hier ein Schritt weiterzukommen, mit 0 Profit natürlich, weil wir nichts hinzunehmen. Und hier nochmal 2 Schritte weiterzukommen mit 6 Profit. Das wäre also die Auswahl, einmal ein Stück mit Gewicht 3 und Profit 10 plus gar nichts,
52:40
plus einmal ein Stück mit Gewicht 2 und Profit 6. Das wäre dieser Fahrt. Oder wir können uns einen anderen Fahrt hernehmen, wir nehmen uns ein Stück her mit Gewicht 15 und mit Profit 15 und Gewicht 4, plus einmal Gewicht 2 und Profit
53:00
6 und sind auch bei B angekommen. Ja, jede mögliche Auswahl von Stücken ist äh ... stoß zu einem solchen Fahrt und hier ist es jetzt wichtig, dass wir die Problemstellung so betrachten, nicht so wie sie eigentlich normaler, also in der Literatur, wie ich es typischerweise kenne,
53:23
sondern in einer etwas anderen Situation, nämlich Sie sehen hier, man kann auch einen Pfad haben, das lässt sich gar nicht anders, das lässt sich gar nicht verhindern, das lässt sich gar nicht modellieren, um das auszuschließen. Sie können auch einen Pfad haben, ein Stück von dieser Sorte plus noch ein Stück von dieser Sorte plus noch ein Stück von dieser Sorte.
53:42
Das heißt also, wir haben ganz konkret die Situation, dass wir nicht von jeder Sorte beliebig viele Stücke drin haben, die wir da zusammenpacken können. Denken Sie sich eine Palette, wo Sie
54:00
Pakete von verschiedener Art drauf platzieren können, zum Beispiel. Aber alles andere, was ich gesagt habe, funktioniert nur, nur das, was auf dieser Folie ist, aber alles andere funktioniert auch in dem eigentlich natürlicheren Szenario, von dem ich ursprünglich ausgegangen bin,
54:21
dass jedes Stück nur einmal vorkommt. Sie haben typischerweise nur ein Möbelstück von jeder Sorte. Und wenn Sie mal vier Stühle haben, dann sind das eben vier verschiedene Stücke, die zufällig dieselben Charakteristik haben, dasselbe Gewicht, dasselbe Profit. So, damit sind wir mit dynamischer Programmierung
54:41
durch ein sehr mächtiger Ansatz. Aber wie immer, man könnte eine ganze Vorlesung hier, ein ganzes Semester füllen, nur mit dem Thema dynamischer Programmierung. Aber wichtig ist erst einmal hier überall, dass Sie einen Einblick bekommen, ein Verständnis bekommen,
55:04
sodass Sie gegebenenfalls dann auch vielleicht auf eigene Faust dann, wenn Sie vor einer solchen Situation stehen, dann weiter agieren können. So, wir kommen jetzt zu einer anderen Klasse von Algorithmen.
55:21
Greedy heißen die und die heißen nicht umsonst so. Greedy heißt auf Englisch gierig. Gierige Algorithmen, weil sie immer das tun, was in dem Moment kurz ist. Also eigentlich wäre, fände ich es besser, eine bessere Formulierung, eine bessere Begriffsbildung, wenn man sie kurzsichtige Algorithmen nennt.
55:42
Ich denke, das trifft es besser, dass Sie kurzsichtig immer nur schauen, in meinem kleinen eingeschränkten Blickfeld, was ist das Beste, was ich jetzt als nächstes tun kann? So, in welche Richtung gehe ich jetzt am besten? So, Haupteinschritt weiter. Jetzt habe ich ein neues, aber weiterhin eingeschränktes Blickfeld. Was ist das Beste, wo kann ich jetzt am besten hingehen und so weiter?
56:02
Aber es hat sich etabliert, das Greedy zu nennen. Und so werden wir das jetzt auch nennen. So, jetzt müssen wir noch mal zurückgehen auf die Grundvorstellung des ganzen Kapitels, des ganzen Abschnitts.
56:34
Vielleicht sollte ich noch mal ein, ich sollte noch mal ganz kurz zur dynamischen Programmierung zurückkommen, denn mir fällt gerade auf, dass wir gar nicht thematisiert haben,
56:43
was das Thema dynamische Programmierung eigentlich mit dem Oberthema des ganzen Abschnitts zu tun hat. Das scheint bei irgendeiner Überarbeitung der Folien, und zwar nicht bei einer Überarbeitung durch mich,
57:02
sondern durch jemand anders, mal weggefallen zu sein. Also müssen wir es jetzt hier nachtragen. Ich hatte es ursprünglich reingeschrieben. So, Sie erinnern sich, es geht in diesem ganzen Abschnitt, da müssen Sie jetzt weit zurückdenken, vor Weihnachten.
57:22
Es geht in diesem ganzen Abschnitt um solche Branching Trees. Das heißt also, wir können das so sagen, der Lösungsraum wird schrittweise, meistens binär, muss aber nicht binär sein, wird schrittweise zerlegt,
57:43
in dem verschiedene Bedingungen jeweils hinzugefügt werden. Hier, also ein Standardbeispiel, was wir betrachtet haben, war so was wie z.B. x1 gleich 0, x1 oder kleiner gleich 0, x1 größer 0.
58:03
So was in der Form, dass der Lösungsraum zerlegt wird in alle Lösungen, bei denen diese Bedingung erfüllt ist, und alle Lösungen, bei denen diese Bedingung erfüllt ist usw. usf. Und irgendwo unten sind dann die einzelnen zulässigen Lösungen als Blätter.
58:22
Soweit eingeschränkt, dass nur noch eine Lösung, eine zulässige Lösung übrig bleibt oder gar keine. Das kann auch sein. Und wir hatten in den verschiedenen Algorithmen, beispielsweise bei Branch & Bound war das sehr intensiv so, hatten wir immer geschaut, was kann man tun an einem Knoten, dass wir nicht den ganzen Teilbaum, der da drunter ist, auswerten müssen.
58:44
Dass wir da nicht durchlaufen müssen, weil wir können uns natürlich nicht leisten, diesen ganzen Baum zu durchlaufen. Sie wissen allein schon, wenn es nur binär ist, Sie wissen, was mit der Breite dieses Baumes passiert, wenn er eine gewisse Tiefe hat. Ja, das explodiert, das können wir nicht machen.
59:00
Und da haben wir immer geschaut, können wir vernünftigerweise davon ausgehen, dass wissen wir, haben wir ein Zertifikat in der Hand, ein Beweis in der Hand, dass wir diesen Teilbaum nicht durchsuchen müssen, weil außerhalb dieses Teilbaums
59:20
und außerhalb aller anderen bisher abgeschnittenen Teilbäume immer noch eine optimale Lösung übrig geblieben ist. Das war immer das Grundprinzip, beispielsweise bei Branch & Bound. Und im Grund ist das bei dynamischer Programmierung genauso.
59:42
Diese Formulierungen immer mit Maximum hier, hier wird es jetzt vielleicht klarer, hier das Maximum von zwei Optionen. Ja, was Sie im Grunde tun, wenn Sie hier...
01:00:00
Wenn wir so ein Schema durchgehen, habe ich das noch aufgezeichnet oder ist das schon wieder ... Ja, ist leider weg. Dieses Maximum dort in der Rekursion, das bedeutet Sie haben zwei verschiedene Möglichkeiten. Sie zerlegen den Lösungsraum für R lambda, für die ersten R-Stücke und für Oberschrank der lambda.
01:00:33
Den zerlegen Sie in zwei Teilräume. Diesen Lösungsraum nehme ich den, bei Maximum das erste.
01:00:43
Was passiert, wenn ich das letzte Stück gar nicht hinzunehme? Wenn ich vom letzten Stück nichts hinzunehme? Was passiert auf der anderen Seite, wenn ich das letzte Stück hinzunehme? Ja, genauso wie wir das auch bei Branchenbau und anderen Algorithmen betrachtet haben,
01:01:03
zerlegen wir das Schritt für Schritt, diese Rekursion, das Schritt für Schritt in Teilräume. Und genauso beim Sequencer-Alignment beispielsweise. Was passiert, eine Möglichkeit ist, ganz zum Schluss wird substituiert, gelöscht oder eingefügt oder gematcht.
01:01:23
Was passiert dann jeweils? Wir zerlegen das also in die vier verschiedenen Teilmengen des Lösungsraums, wo die letzten beiden gematcht oder eins gelöscht oder eins eingefügt oder wo substituiert wird.
01:01:41
Und kämen dann in diesem Fall nicht auf den Binären, sondern auf einen viergliedrigen Baum. Aber es ist immer dasselbe. Das geht dann Schritt für Schritt weiter. Wenn Sie die Rekursion folgen, geht das Schritt für Schritt weiter und Sie kriegen genau so einen Baum. Nur, was Sie jetzt anders machen bei der dynamischen Programmierung ist,
01:02:08
dass Sie erkennen, also das vielleicht jetzt gerade nicht, aber dass Sie erkennen, dieser Knoten hier und dieser Knoten hier, die Teilbäume, die da drunter hängen, sind identisch.
01:02:25
Also braucht man es nur einmal berechnen. Und sinnvollerweise nicht, indem man runtergeht im Baum, an der einen Stelle das berechnet und wieder hochgeht und dann an der anderen Stelle feststellt, das war schon mal berechnet, also braucht man es nicht normal zu berechnen,
01:02:41
sondern indem man das Bottom-up schon von vorneherein berechnet und das nur einmal berechnet. Die Situation, wie Sie das vom Bottom-up her kennen, dass man tatsächlich Bottom-up runtergeht und einmal berechnet man das und beim zweiten Mal stellt man fest, es ist schon mal berechnet worden, braucht man nicht normal.
01:03:00
Die kann auch auftreten in komplexeren Situationen. Da habe ich vor langer Zeit, 25 Jahre her oder so, mal selber so eine dynamische Programmierung gebaut, wo es nicht eine quadratische Anzahl von solchen verschiedenen Konstellationen gab, sondern eine viel, viel größere Anzahl, also wo das Schema schon für sich genommen viel zu groß war,
01:03:25
wo ich für jede Kombination, auf die ich mal gestoßen bin, dann, und das berechnet habe, in einer Hashtabelle diese Kombination abgelegt habe und wenn ich später auf einer anderen Stelle im Baum wieder zur selben Kombination bekommen bin
01:03:42
oder bei irgendeiner beliebigen Kombination bin, habe ich nachgeschaut, ist diese Kombination schon in der Hashtabelle? Wenn ja, kann ich den Wert einfach nehmen. Also diese Sichtweise hat durchaus ihre Relevanz, dass wir das einordnen in diesem Oberabschnitt über Branching Trees.
01:04:05
So, jetzt kommen wir aber wieder zu Branching Trees zurück, etwas näher dran und zwar auf eine sehr langweilige Art. Wir gehen genau einmal einen Zweig im Entscheidungsbaum,
01:04:20
ich habe jetzt Branching Trees gesagt, also Entscheidungsbaum war der Begriff, im Allgemeinen gehen wir genau einen Pfad runter bis zu irgendeinem Platz. Und jedes Mal, also wir gehen einen Schritt runter, einen Schritt runter, einen Schritt, einen Schritt, einen Schritt, einen Schritt, einen Schritt, so bis wir bei einem Platz sind.
01:04:40
Und jedes Mal gucken wir, wie ich das sagte, mit dem eingegrenzten Gesichtswelt, was scheint jetzt die beste Möglichkeit zu sein, um einen Schritt tiefer zu kommen? Welche der verschiedenen Wahlen sieht jetzt plausibel aus? So, generell sind solche Methoden, heißen solche Methoden, Gridi-Algorithmen,
01:05:01
aber wir werden uns hier auf die Standardsituation noch einschießen, nämlich eine spezielle Situation, die uns einiges an Kopfschmerzen bereiten wird. Das sage ich jetzt schon mal im Voraus. So, gibt es hier noch etwas dazu zu sagen zum Gridi-Algorithmus?
01:05:26
Nö, ich denke es ist erstmal von grundsätzlichen her klar, nicht? Gridi-Algorithmus kann man auch sehen, als im Spezialverfahren von Backtracking, Sie erinnern sich, ich hatte einen Backtracking gehabt, man geht runter, stellt fest, dumm gelaufen, irgendwas ist hier verkehrt, geht wieder zurück, vielleicht einen Schritt zurück oder sogar mehrere Schritte zurück,
01:05:45
um den Catch-22 da, den Widerspruch aufzulösen. Und dann versucht man es in eine andere Richtung. Backtracking, der Spezialverfahren von Backtracking, Gridi ist der Spezialverfahren von Backtracking, dass wir nie zurückgehen. Dass wir nur einmal runtergehen und das war's.
01:06:04
So, wir betrachten aber eine bestimmte Situation, die sehr, sehr häufig ist, die eigentlich so die typische Situation ist. Ich will auch gleich, bevor ich Sie jetzt überfrachte mit Notationen und nicht ganz so einfach zu durchschauenen Informationen,
01:06:24
will ich Ihnen aber auch gleich von vornherein sagen, wohin das führen wird. So als eine kleine Motivation, so die eine oder andere Durchstrecke zu überwinden. Das wird dahin führen, Gridi-Algorithmus ist offensichtlich in den meisten Fällen schlecht.
01:06:40
So ähnlich wie lokale Suche, bei Nachbarschaftsbasiert, sind Gridi-Algorithmen, wenn im Allgemeinen kein Optimum finden, sondern wenn oft genug auch sogar sehr schlechte Lösungen finden. Es gibt viele Situationen in der Praxis, wo Gridi-Algorithmen schon sehr gute Lösungen liefern, aber es gibt auch Situationen in der Praxis, wo Gridi-Algorithmen Grotten schlechte Lösungen liefern.
01:07:04
Aber auch sehr gute Lösungen müssen auch nicht optimale Lösungen sein. Muss nicht die beste Lösung sein, sondern eben nur relativ nah dran. Worauf wir hinzielen, ist eine Charakterisierung,
01:07:21
unter welchen Umständen der Gridi-Algorithmus tatsächlich garantiert eine Optimallösung liefert. Das kann man sehr gut charakterisieren, ist bloß ein bisschen kompliziert. Wir werden auch als ein Nebenprodukt aus höherer Warte noch mal sehen. Der Algorithmus von Kruskar, den Sie dunkel noch in Erinnerung haben,
01:07:44
über minimal spannende Bäume, maximal spannende Wälder, ist ein Gridi-Algorithmus, das ist noch nicht die tiefe Einsicht, das werden wir gleich noch mal sehen, dass das ein Gridi-Algorithmus ist. Aber diese Charakterisierung, unter welchen Umständen ein Algorithmus tatsächlich die beste Lösung liefert,
01:08:03
diese Charakterisierung beweist auch noch mal wieder, dass der Algorithmus von Kruskar tatsächlich die Optimallösung liefert. Wir werden jetzt auf ein Resultat hinsteuern, in dem die Optimalität des Algorithmus von Kruskar eingebettet ist, wenn man so will.
01:08:23
So, das war die Vorrede, jetzt geht es hier zur Sache. Das Unabhängigkeitssystem, Independence System, ist noch was relativ einfaches. Sie haben, vielleicht gehen wir einfach zu Beispielen hier her, bevor wir das noch mal genau formulieren.
01:08:50
Ein schönes Beispiel ist Knapsack wieder, wo wir eben waren. Unabhängigkeitssystem heißt, jede Auswahl, wenn Sie eine Auswahl haben und die passt rein,
01:09:05
dann können Sie auch Elemente rausnehmen und es passt immer noch ein. Also sind die Auswahlen beim Knapsack-Problem ein Unabhängigkeitssystem. Nehmen Sie ein anderes Beispiel her, Wälder, Wälder in einem Baum, spannender Welt im Baum,
01:09:21
also zykelfreier Subgraph eines Grafen als Kantenmenge. Wenn Sie so einen zykelfreien Subgraph eines Grafen haben und Sie nehmen noch Kanten raus, dann bleibt es zykelfrei. Das heißt, die Menge aller zykelfreien Subgraphen eines Grafen sind ein Unabhängigkeitssystem.
01:09:43
Ja, kommen wir gleich. Zwei hoch E. Die Mathematiker, haben Sie ja vielleicht mitbekommen, legen sehr viel Wert auf elegante Notationen. Und auch die Informatiker legen eher Wert auf irgendwelche witzigen Notationen.
01:10:06
Die Mathematiker eher auf elegante. Ich muss jetzt langsam daran denken, dass das Ganze ja mal irgendwann weltöffentlich gestellt wird, also sollte ich mich jetzt hier nicht rauslehnen. Das ist nichts anderes als die Potenzmenge der Menge E.
01:10:22
Es gibt gewisse Gründe, warum man das als gut passend zu anderen Notationen sehen kann. Ja, also letztendlich steckt dahinter die Identifikation einer Auswahl mit dem 0,1 String, der diese Auswahl bezeichnet.
01:10:46
Deshalb das 2. Also 2 ist eine Abgrößung für 0,1. Was hier steht ist 0,1 hoch E verdichtet zu 2 hoch E. Das kann man elegant finden.
01:11:02
Gut, also lassen wir uns da jetzt nicht weiter beirren. Das ist einfach die Potenzmenge 2 hoch E. Die Potenzmenge der Menge E. So, anderes Beispiel, Matchings in einem Grafen. Ja, wenn ich ein Matching in einem Grafen habe, Sie erinnern sich, was das ist. Das ist eine Kantenmenge, wo keine zwei Kanten denselben Knoten gemeinsam haben.
01:11:24
Wenn ich dann noch Kanten wegnehme, ist es weiterhin ein Matching. Jetzt fällt mir gerade, jetzt muss ich mal spicken. Noch ein schönes Beispiel. Nee, die anderen Beispiele gefallen mir nicht so. Doch jetzt ein Beispiel noch, was wir später nochmal betrachten werden.
01:11:42
Nehmen Sie sich eine Menge von linear unabhängigen Vektoren her. Wenn Sie davon welche wegnehmen, ist der Rest immer noch linear unabhängig. Also sind Mengen von linear unabhängigen Vektoren ein Unabhängigkeitssystem.
01:12:00
Es bedeutet nichts anderes, als wenn Sie eine Menge Y im Unabhängigkeitssystem haben. Eine Auswahl Y im Unabhängigkeitssystem. Und Sie haben eine Teilmenge X davon, dann ist dieses X ebenfalls ein Unabhängigkeitssystem. So wie ich das immer gesagt habe. Wenn Sie aus Matching-Kanten rausnehmen, ist es immer noch ein Matching.
01:12:21
Deshalb ist die Menge aller Matchings in einem graveneinen Unabhängigkeitssystem. Die erste Bedingung hier ist eigentlich sogar redundant. Denn die Leeremenge ist natürlich eine Teilmenge jeder Menge hier. Das heißt also, wenn Sie X als die Leeremenge reinsetzen, die natürlich Teilmenge von jedem Y ist,
01:12:45
dann folgt aus M2 sowieso schon, dass die Leeremenge ebenfalls ein Unabhängigkeitssystem ist. Bestimmt nicht ganz, was ich gesagt habe, dass es redundant ist. Das ist wieder eine schöne elegante Weise.
01:13:03
Der Sinn von M1 ist einfach auch zu sagen, dass dieses Unabhängigkeitssystem nicht leer ist. Ich habe eben gesagt, die Leeremenge ist automatisch garantiert in jedem Unabhängigkeitssystem drin. Wenn Sie ein Element Y aus dem Unabhängigkeitssystem hernehmen, eine Auswahl Y,
01:13:25
Leeremenge ist eine Teilmenge davon, dann ist Leeremenge natürlich automatisch auch drin. Vorausgesetzt, das Unabhängigkeitssystem ist nicht leer. Dann gibt es diese Argumentation nicht, dass ich Y hernehme aus dem Unabhängigkeitssystem, weil es kein solches Y gibt. Also muss man irgendwie noch sagen, das Unabhängigkeitssystem ist nicht leer.
01:13:44
Jetzt könnte man natürlich einfach sagen, M1, erste Bedingung ist, das Unabhängigkeitssystem ist nicht leer. Aber das wäre jetzt so einfach, das wäre unelegant. Man kann natürlich genauso gut sagen, die Leeremenge ist Teilmenge, das Unabhängigkeitssystem ist völlig äquivalent. Ist doch schön alles elegant, nicht?
01:14:01
So, wir werden noch was Besonderes brauchen, die sogenannten Basen. Wir werden auch feststellen, dass das was mit dem zu tun hat, was Sie aus der linearen Algebra als Basen kennengelernt haben, dass es sehr viel damit sogar zu tun hat. Diese, wenn Sie ein maximales Matching haben, in dem Sinne, dass Sie keine Kante mehr hinzufügen können,
01:14:25
sodass es noch ein Matching bleibt, dann ist das eine Basis. Ich habe jetzt Base gesagt, Basis, sagt man im Deutschen. Oder was war ein anderes Beispiel? Knapsackproblem, wenn Sie eine Auswahl haben, die in den Rucksack reinpasst oder die das zulässige Gesamtgewicht nicht überschreitet.
01:14:43
Und wenn Sie kein weiteres Stück hinzunehmen können, egal welches, ohne das zulässige Gesamtgewicht zu überschreiten, dann ist diese Auswahl, die Sie jetzt bis dahin getroffen haben, eine Basis. Das ist der Begriff Basis hier. Und vielleicht schon die erste Idee, was das mit Basen in linear Algebra zu tun hat,
01:15:05
das sind natürlich immer maximale Mengen, eine Basis eines Unterraums oder eines Raumes, ist immer eine maximale Menge von linear unabhängigen Vektoren. Sie können innerhalb in diesem Unterraum keinen weiteren Vektor hinzunehmen, sodass das Ganze noch linear unabhängig bleibt.
01:15:23
Daher kommt diese Begriffsbildung. Ich hoffe, Sie haben jetzt linear Algebra nicht so weit verdrängt, dass ich jetzt für Sie bürmische Dörfer rede. So, das kann man einmal als Maximierungsproblem betrachten.
01:15:42
Wichtig sind hier die kleinen feinen Unterschiede. Ich meine jetzt nicht den Unterschied, dass hier ein Max und hier ein Min steht, sondern die kleinen feinen Unterschiede zwischen hier und hier. Maximierung ist einfach zu formulieren. Wir wollen eine Auswahl finden, also wir haben eine Grundmenge gegeben.
01:16:00
Ich sollte noch dazu sagen, wir betrachten hier immer nur endliche Grundmengen. So wie wir es auch in den Beispielen gesehen haben. Matching, die Kanten eines Graphen bei uns, es gibt auch Theorien über unendlich große Graphen. Wir hier betrachten nur endlich große Graphen mit endlich vielen Knoten, endlich vielen Kanten. Matchings, die Menge aller Kanten in einem Graphen, aus dem man Matchings bilden kann,
01:16:20
ist eine solche endliche Menge. Und Sie sehen schon, es ist auch kein Zufall, dass in der Literatur diese Grundmenge immer E bezeichnet wird. Das kommt genau aus diesen Beispielen, insbesondere aus den Beispielen spannende Wälder. Der intuitive Hintergrund ist eine Kantenmenge, deshalb E.
01:16:42
So, Maximierungsproblem ist, wir wollen eine unabhängige Menge finden, sodass das Gesamtgewicht maximal ist. Okay, machen wir uns klar, das wird automatisch immer eine Basis sein. Wenn wir positive Gewichte auf den Grundmengen haben.
01:17:05
Hier allgemein ist das nicht der Fall. Es ist nicht vorausgesetzt, dass sämtliche Gewichte positiv sind. Aber wenn die Gewichte, was ja in der Praxis der übliche Fall ist, wenn die Gewichte alle positiv sind, dann wird das automatisch eine Basis sein. Wenn man noch ein Element hinzunehmen kann, das hat positives zusätzlichen Profit,
01:17:22
nehmen wir ihn rein und haben eine bessere Lösung gefunden. Bei Minimierung ist es was anderes. Wenn die Gewichte alle positiv sind, ist in dieser Formulierung nichts zwingend gegeben, aber es ist eben die typische Situation. Wenn die Gewichte alle positiv sind, was ist die minimale Lösung?
01:17:41
Die leere Menge. Toll. Tolle Problemstellung. Hier, aber das ist nicht das, was man will. Was man will, kommt hier jetzt deutlich zum Ausdruck, weil es sich nicht automatisch ergibt. Was man will, ist immer eine Basis von minimalem Gesamtgewicht.
01:18:05
Diese Bemerkung hier sollten wir nicht übersehen. Diese Menge aller verschiedenen unabhängigen Teilmengen ist nicht aufgelistet. Wir haben keine Liste, das ist eine zyklfreie Subkraft, das ist ein zyklfreier Subkraft,
01:18:24
das ist ein zyklfreier Subkraft und so weiter. Sondern wir gehen davon aus, wenn wir eine Teilmenge der Gesamtmenge haben, eine Auswahl haben, dann gibt es da etwas, was man in der Informatik immer ein Orakel nennt. Das hat nichts mit dem eingetragenen Warenzeichen zu tun.
01:18:42
Ist Ihnen in dieser Form der Begriff Orakel schon in der typischen Informatik begegnet? Letztendlich, ein equivalenter Begriff ist Blackbox. Sie stellen eine Anfrage und Sie kriegen eine Antwort. Sie haben keine Ahnung, wie diese Antwort berechnet worden ist. Letztendlich, Sie rufen eine Funktion, Prozedur, Methode auf und geben in diesem Fall diese Teilmenge F rein
01:19:06
und kriegen die Antwort Ja, es ist eine unabhängige Menge, Nein, es ist keine. Wenn das Unabhängigkeitssystem die Menge aller zyklfreien Subgrafen eines Grafen ist, dann checkt dieses Orakel einfach, ob ein Zykl drin ist oder nicht.
01:19:21
Oder wenn das Unabhängigkeitssystem die Menge aller Matchings eines Grafen sind, dann checkt dieses Orakel einfach, ob irgendwo zwei Kanten einen Knun gemeinsam haben. Dann gibt es Nein aus und wenn keine zwei Kanten einen Knun gemeinsam haben, gibt es Ja aus.
01:19:41
So, Stable Set, das muss ich nochmal überlegen, das war unabhängige Menge. Genau, unabhängige Menge von Knoten nennt man auch stabile Menge von Knoten. Also diesen Begriff finden Sie, diese Problemstellung finden Sie auch als independent Problem.
01:20:09
Wir wollen eine möglichst große Menge von Knoten finden. So ein bisschen ähnlich wie Matching, nur jetzt auf Knoten statt auf Kanten. Wir wollen eine möglichst große Menge von Knoten finden oder mit möglichst großem Gesamtgewicht,
01:20:21
weil auf den Knoten Gewichte gegeben sind, sodass keine zwei Knoten durch eine Kante miteinander verbunden sind. Das ist das Maximum Rate Stable Set Problem. Auch das ein Unabhängigkeitssystem, wenn Sie aus so einer Menge von Knoten, die sich alle gegenseitig nicht berühren, Knoten noch rausnehmen, ist die Eigenschaft weiterhin erfüllt, dass sie sich gegenseitig nicht berühren.
01:20:42
Dieses Beispiel hier ist besonders wichtig, weil es besonders beispielhaft ist, wenn mir das Wortspiel erlaubt ist. Die Rundtouren sind keine unabhängige Menge, denn wenn Sie aus einer Rundturkante rausnehmen, ist es keine Rundturme mehr.
01:21:03
Aber die Rundtouren sind auf natürliche, ich will fast sagen triviale Art und Weise, die Basen eines Unabhängigkeitssystems. Was ist dieses Unabhängigkeitssystem? Das sind sämtliche Teilmengen von Rundtouren. Das ist eine typische Situation.
01:21:26
Sie haben automatisch immer, wenn Sie sowas wie Rundtouren beispielsweise haben, als zulässige Lösungen, wenn Sie sämtliche Teilmengen hinzunehmen, haben Sie automatisch, trivialerweise,
01:21:41
das Unabhängigkeitssystem. Das ist die Fundierung für den Grädi-Algorithmus, dass Sie umgekehrt Schritt für Schritt Kanten hinzunehmen, bis es ein Rundtor ist. Das dritte Beispiel, da habe ich mich mit irgendjemand mal intensiv drüber gestritten,
01:22:04
ob das jetzt ein sinnvolles Beispiel ist oder nicht. Ich lasse es mal aus. Wenn Sie mich in der Prüfung überzeugen können, dass es ein sinnvolles Beispiel ist,
01:22:22
kann das nur gut sein für den weiteren Verlauf der Prüfung. Knapsack hatten wir eben, Spanning Tree hatten wir eben, also Forests, genau. Wenn die zuglässigen Lösungen die spannenden Bäume sind eines Grafen, dann sind die zyklfreien Subgrafen das entsprechend induzierte Unabhängigkeitssystem.
01:22:41
Alle Teilmengen der spannenden Bäume ist gerade die Menge der zyklfreien Subgrafen in diesem Grafen. Matching hatten wir auch schon gehabt, brauchen wir nicht nochmal anzusprechen. So, wir betrachten Maximierungsproblem. Wir sind jetzt eigentlich soweit fertig,
01:23:03
also wir sollten an dieser Stelle jetzt Schluss machen, ein paar Minuten vielleicht noch, ein, zwei Minuten noch. Das hier sollte langsam aber sicher, was auf dieser Folie steht, sollte eine kleine Erinnerung an Kruskal vielleicht bei Ihnen provozieren.
01:23:21
Was war Kruskal für maximal spannende Wälder? Sie sortieren zuerst die Kanten nach dem Gewicht und dann betrachten Sie jede einzelne Kante. Sie beginnen mit einem leeren Baum, mit einem leeren Wald. Sie betrachten jede einzelne Kante nach Gewicht.
01:23:44
Und wenn diese Kante ein Zyklo schließt, dann verwerfen Sie sie, betragen Sie sie nicht wieder. Wenn diese Kante kein Zyklo schließt, nehmen Sie sie dazu. Genau das steht in abstrakter Form in den Begriffsbildungen eines Unabhängigkeitssystems steht hier.
01:24:01
Wir sortieren zuerst die Elemente der Grundmenge, fangen an mit der leeren Menge als Element des Unabhängigkeitssystems. Und solange wir nicht aus dem Unabhängigkeitssystem rausgehen durch hinzufügen weitere Elemente der Grundmenge, solange fügen wir weiter hinzu.
01:24:21
So, hier ist vielleicht noch mal die Begründung dafür, letztes Wort, die Begründung dafür, hier steht vom Parfolienstand nicht aus den positiven, reellen Zahlen jeweils, aber wenn wir zum Beispiel das Maximierungsproblem betrachten, brauchen wir uns Elemente mit negativen Gewicht nicht anzuschauen.
01:24:47
Die werden niemals in einer optimalen Lösung drin sein. Die sollten wir niemals hinzufügen. 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.