Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Dynamisches Programmieren | Algorithmen und Datenstrukturen - Vorlesung 22
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 380 Zeilen
- herzlich willkommen zur 22 vorlesung von algorithmen und datenstrukturen wie angekündigt werde ich die vorlesung heute mal aufnehmen und durch vorher zur
- verfügung stellen und wir werden da in der vorlesung einfach nur darüber reden und decken frage stellen nachdem sich dass jeder jetzt in seinem
- eigenen tempo anschauen kann weil ich jetzt nicht so viele warten nicht so viele fragen stellen mit der kommunizieren können deswegen schaut
- bitte selber dass er an gewissen stellen wenn ihr ein bisschen mehr zeit brauchte mitzukommen pause macht und das alles versteht und auch wenn ich euch mal eine
- frage stellen werden im video macht selbstständig pause denkt drüber nach und findet eine lösung zu finden und schaut danach rast weiter
- wir haben das in der vorlesung schon mehrere entwurfs techniken kennen gelernt gerade am anfang uns waren bei angefangen mit dem inkrementellen
- algorithmen sowie in sessions ort wir hatten rezessiver algorithmen sowie mercks ort werden teile und herrsche es war auch unter anderem merger & spiel
- hatten randomisierter algorithmen sowie zum beispiel remmers quixote heute wollen wir das nochmal erweitern und wohl noch eine weitere entwurfs
- technik ändern nämlich das dynamische programmieren wobei programmieren hier jetzt nichts mit dem programmieren klassischen schützen zu tun hat sondern
- das bedeutet hier dass wir mit einer tabelle arbeiten und nicht den computer programm schreiben dynamisches programmieren hat sehr viel
- mit teile und herrsche gemeinsam und zwar haben wir bei teile und herrsche instanzen rigozzi findet island verlegt sowie beim workshop dann war einmal in
- der mitte durchgeschnitten und haben dann die linke und die rechte hälfte jeweils angeschaut wir haben die unabhängig voneinander gelöst und es
- dann wieder zusammen verbunden wenn wir uns das hier zumal als 2d anschauen wir haben mir so eine anzahl von punkten und wir wollen die
- unterteilen durch gewisse linien da wird so für so ausschauen belegen hier erstmal eine horizontale linie durch da kann man jeweils rezessive der vertikale
- linien durch legen mit der horizontale wieder vertikale und jetzt haben wir eine linie durch jeden einzelnen punkt und wir haben die ebene hier so
- unterschiedliche bereiche aufgeteilt dieser unabhängig voneinander lösen können beim dynamischen programmieren zerlegen
- wir instanzen auch in teil instanzen allerdings können die hier im gegensatz zur hat teile und herrsche überlappen also es kann sein dass wir angenommen
- wieder sortieren dass wir das in unterschiedliche bereiche unterteilen aber dass manche zahlen eben in mehreren bereichen gleichzeitig so
- dass wir der geometrisch versuchen zu veranschaulichen wir haben eben gewisse anzahl von punkte da können wir hier so zum beispiel
- teilmengen von zwei punkten nehmen die aber überlappen dann können wir teilmenge von drei punkten nehmen von vier punkten oder von fünf punkten und
- so kriegen wir unterschiedliche teil instanzen wobei hier die einzelnen bereiche alle komplettes jungs sind sind hier diese teilmenge neben überlappend
- aber beides beruht darauf dass man es eben diese teil instanzen löst und sich dann eine lösung für das gesamte problem zu wie auch immer das dann im detail
- ausschaut die lösungen von den teil instanzen die mir hier haben die werden jetzt dafür aber zwischengespeichert und nicht immer
- neu berechnet das ist ein unterschied zu teile und herrsche hier gehen wir einmal durch diesen reaktions baum durch alles und hier kann sein dass wir die
- mönche teil instanzen mehrfach anschauen müssen und um das problem zu umgehen dass die laufzeit zu hoch geht wenn wir dann immer unsere teillösungen speichern
- das bedeutet dann eben dieses dynamische programmieren er schaut sich teil instanzen an aber wenn man speichert die ergebnisse jeweils in der tabelle
- dort geht man zb top down also wir fangen ganz obenan mit allen elementen dann nehmen wir die hälfte wieder die hälfte und so weiter und so geht es bei
- allen teilen und herrschen und verbaut von oben nach unten sich was auf einen dynamischen programmieren geht es hingegen von bottom up also von unten
- nach oben würden hier zum beispiel erst mal die lösungen für die eigenen elementen teilmengen berechnen dann daraus lösung für zwei elemente dann
- daraus für drei elemente usw das teile und herrsche benutzen wir hauptsächlich für entscheidungs oder berechnungs probleme und das dynamische
- programmieren benutzen wir hauptsächlich wenn wir optimierungs probleme haben wenn sie also nicht nur einfach eine lösung gibt sondern wenn es viele
- mögliche lösungen gibt wir aber die beste davon finden wollen wird es dynamische programmieren gibt so einen standard farb- laden und da
- besteht aus vier schritt erstmal wollen wir für eine optimale lösung die struktur charakterisieren dann wollen wir uns relativ den wert
- einer optimalen lösung definieren im dritten schritt wollen wir dann den wert der optimalen lösung berechnen das machen wir meistens bottom up und im
- vierten schritt wollen wir dann aus den berechneten informationen konstruieren das neue ich die schritte die man jedes mal durchgehen muss wenn man dynamisches
- programm macht wobei der vierte schritt bei den meisten eigentlich sehr ähnlich ausschaut und man den meistens überspringt weil der eigentlich relativ
- klar ist aus den ersten drei schritten wir machen den heute bei einem beispiel mit aber ansonsten werden wir denen meistens weglassen
- wir wollen es heute zwei probleme anschauen an dem er feststellen wollen wir denn dieses dynamische programmieren funktioniert das erste ist das
- sogenannte zerlegung problem ist ein relativ einfaches problem wir nehmen uns einen stab der länge m und wir können diesen stab jetzt unterteilen in
- kleinere stücke einfachheit halber sagen wir mal die müssen alle ganzzahligen länge haben und diese kleineren städte die können wir jetzt verkaufen also wir
- haben jetzt sagen beim alten starb der längere 100 meter den kommen wir jetzt vielleicht nicht unbedingt im laden packen aber wir können da ein meter
- stücke drauf packen die können wir jetzt in den laden stellen verkaufen oder abwickeln zwei meter große stücke oder drei meter große stücke machen und wir
- wollen natürlich am ende so viel profit wie möglich kriegen wir wollen also so zerlegen dass wir unseren ertrag maximieren dass wir möglichst viel geld
- bekommen schauen wir uns mal ein ganz kleines beispiel einfach mal nur einen stab der länge 4
- welche möglichkeiten haben wir jetzt diesen stab zu unterteilen auf wie viele kommt er da
- wir können den jetzt so durchschneiden dass wir erst mal ein stück der länge 1 haben und dahinter ein special länge 3 oder länge 2 lange 2 oder länge dreiheit
- länger 1 das sind alle lösungen die wir kriegen wenn wir genau einen stadt machen wir können aber natürlich auch jetzt dieses stück der länge 3 oder dies
- erhöht der länge 2 nochmal unterteilen also können jetzt hier nochmal schnitt durch machen oder hier nochmal schnitt wenn wir zwei schnitte haben kriegen wir
- dadurch jetzt einmal die lösung wenn wir hier nochmal durchschneiden die lösungen man mir hier nochmal durch schneiden oder die lösung wenn wir hier noch mal
- durchstarten wir können natürlich auch hier nochmal durchschneiden aber dann kriegt man auch wird er diese lösung heraus dass die gleiche den man ja schon
- mal gefunden haben und eine lösung kriegt man natürlich noch mal mach jetzt hier nochmal durchschneiden dann haben wir jetzt vier
- stücke deiner größe 1 er denkt dabei würde dass das hier auch schon eine lösung ist also ein stab einfach nur so zu lassen wie er ist und gar nicht
- schneiden die kann auch schon die optimale lösung sein wenn uns das den besten ertrag gibt wir haben jetzt also acht mögliche
- lösungen für den stab der länge 4 und wir wollen dafür herausfinden welches nun die beste aber dafür müssen natürlich erst mal wissen welche länge
- gibt uns wie viel geld das wir würden jetzt als input jetzt noch mal zusätzlich eine tabelle geben kriegen die uns sagt wenn wir ein stab der länge
- ihr haben also 1234 was ist dann unser ertrag bei bg 12 des 125 länge 38 und länge 49 jetzt wieder die frage für euch welche
- von diesen acht lösungen werden und jetzt die beste also würden wir uns einer tag maximieren
- gibt es dafür einfach mal schrittweise durch dieses lösung hier da haben wir ein stück der länge 4 das gibt 119 euro hier haben wir zwei stücke der länge 1
- gibt uns jeweils ein euro 1 länge 2 gibt uns fünf euro haben so haben wir hier sieben genauso viel kriegen wir hier haben wir
- auch zweimal 1 und 1 x 22 x 1 1 x 2 das ist klar hier haben wir vier stücke länger 14 euro ein stück der ränge drei und eins der länge 1 49 euro das gleiche
- hier aber hier haben wir zwei stücke der länge 2 dass das hier gibt es zehn euro also wer das unsere optimale lösung wir müssen zwei stäbe der länge 2 draus
- machen um unserem attraktion maximieren eine möglichkeit ist natürlich einfach alle möglichkeiten auszuprobieren des
- werts der rohe gewalt ansatz müssen uns also die frage stellen wie viele möglichkeiten gibt es ein stab der länge in zu zerlegen und
- wenn wir nur ganz eilige längen haben wollen dann bedeutet es natürlich wir können hier nach jedem stück der länge 1 irgendwo einen schnitt durch machen und
- diese kombination davon würden uns dass eine zerlegung geben das heißt wir haben hier en -1 stücke einmal
- anschein nach 1 einmal noch zwei und so weiter bis nach en - 1 meter und wir können für jedes von diesen stücken uns entscheiden machen wir hier jetzt im
- schnitt oder nicht wir haben also en -1 mal die wahl zwischen zwei optionen dh die gesamtzahl der unterschiedlichen zerlegung der kriegen es zwei hoch -
- einst so hier zweimal ihr zweimal ihr 200 weiter und das hier ist natürlich exponentiell und exponentiell ist nichts was wir
- haben wollen weil das es nicht effizient da werden wir schon selbst mit sehr kleinen zahl von m unsere grenzen stoßen dass der computer dann schon jahre
- braucht um die optimale lösung zu finden wir können es uns nicht leisten jetzt alle zerlegung durchzugehen und für jeden ertrag zu berechnen
- hier gibt es also unterschiedliche möglichkeiten wir können entweder und sitzt auf nur gewisse beschränken dann mussten wir herausfinden dass mir welche
- oder wir probieren sie einfach mal mit einem einfacheren ansatz mit so einem sogenannten greedy ansatz genau genommen haben wir hier nicht zu
- reden - 1 zerlegung weil wenn wir hier schneiden und sonst nirgends oder wenn wir hier schneiden uns sonst nirgends kriegen mir eigentlich genau die gleiche
- zerlegung raus aber selbst wenn wir diese duplikate herausfischen es ist immer noch eine exponentielle anzahl und zwar ist es eh hoch pi mal würze 2 in
- drittel geteilt durch dieser teil als es immer noch hoch die dieses ganze stückchen hier also europa wurzeln im exponenten man
- das ist immer das problem jetzt mit einem retina algorithmus aus wie konkret die algorithmus ausschauen
- wir wollen immer irgendwas machen was jetzt lokal besonders gut ist lokal besonders gut heißt wir wollen immer greedy die lösung nehmen die sich
- jetzt gerade am besten land fühlt dann ist eine möglichkeit wir gucken es ist einfach mal jede menge an und für jede davon schauen wir erstmal ja wie
- viel euro pro meter kriegen wir denn wenn wir ein stück dieser länge haben das heißt wir berechnen überall dem preis pro meter
- für ein stück den level der länge 1 wird es jetzt natürlich der 1 hier hätten wir länge 2 wir gegen fünf euro hat dessen ertrag von zweieinhalb dass sie hat zwei
- und zwei drittel dass sie hat zwei und ein fetter und jetzt können wir erstmal so viele stücke nehmen wie es geht die eben die länge haben wo das maximiert
- wird und wenn wir damit fertig sind dann kann sein dass noch so kleine reste heißt und da machen das ganze einfach nochmal das
- schauen wir von den längen die noch übrig sind wieder welche davon ist die beste nehmen dann ganz viele davon und so weiter bis wir alles haben so
- ziemlich streichens der tabelle und spiel wiederholen den prozess bis wir fertig sind die frage die man sich stellen müssen
- ist hier natürlich gibt es das optimum wir denken ja das tut es da muss man das beweisen aber wenn wir denken nein das tut es nicht dann muss man gegen
- beispiel finden das könnt ihr euch mal überlegen was glaubt ihr dann ist dieser algorithmus optimal oder ist das nicht
- nein er ist natürlich nicht optimal sonst wär und zu vorlesungen hier schon vorbei und ein gegenbeispiel sieht man schon hier wenn wir uns die quotienten
- anschauen der größte prozent haben wir hier ein stück der länge 3 dass der algorithmus wird erstmal ein stück der länge 3 nehmen für acht euro
- und dann noch ein stück der länge 1 für 1 euro kriegt also eine lösung raus die ein ertrag von 9 hat haben wir vorher gesehen haben wenn wir zwei stücke der
- länger zwei nehmen kriegen wir an ertrag der größe 10 und haben damit eine bessere lösung damit es da algorithmus selbst auf diesem beispiel nicht optimal
- also ist es im allgemeinen auch nicht in wir noch mal zurück zu unserer idee mit allen zerlegung anschauen
- wir wollen da jetzt den dynamischen programmierung ansatz darauf anwenden so dass man vielleicht nicht jeder einzelne zerlegung nochmal berechnen muss
- wir definieren uns jetzt erstmal für starb der länge ist der maximale ertrag demir da kriegen können und zwar inklusive aller möglichen verteilungen
- die wir haben wenn wir also ein stab der länge 1 haben dann entspricht es einfach nur diesen p1 aber wenn wir jetzt einen stab der länge 2 haben dann ist es
- entweder den zwei monaten in stücke der länge 1 oder wir behalten es einfach dhc 2 wer jetzt die fünf weil das beste ist die zwei zu behalten
- 3 wer hier müssen wir wieder alle möglichkeiten durchgehend 31 oder eine 21 oder die drei behalten sehens bestes die drei behalten also very 38 aber hier
- haben wir gesehen dass beste zwei stücke der länge 2 also verifier gleich ziehen wenn wir jetzt einfach mal nur einen schnitt anschauen wir sagen jetzt
- einfach wir nehmen unseren starb und wir gehen jetzt einfach mal davon aus wir schneiden den an dieser stelle hierdurch was wäre jetzt der maximale ertrag den
- wir für diesen stab kriegen wenn wir an dieser stelle durchschneiden das ist natürlich der maximale ertrag den wir hier links kriegen können + den
- maximalen ertrag dem er hier rechts kriegen können wenn hier also länge ist dann müssen wir hier einfach nach gucken was ist denn da maximaler ertrag für
- länge und hier haben wir dann länge in - sie als wäre es hier der maximale ertrag von starb der länge m - wenn man also davon ausgehen dass man
- all diese werte schon kennen dann könnten wir jetzt für diesen schnitt ausrechnen was ist denn jetzt der beste vertrag den man mit diesem schnitt
- kriegen können und angenommen wieder wir kennen all diese werte bis minus 1 dann könnten wir jetzt einfach alle schnitte ausprobieren
- können jeweils nach gucken was es denn jetzt für diese zwei teillösungen die optimale lösung und können die so zusammensetzen und uns
- dann anschauen welcher schnitt ist jeder inder beste wenn wir also so ein schnitt nehmen dann zerlegt es das problem in zwei
- unabhängige teil probleme einmal des links und einmal des rechts und das nennt man das phänomen der optimalen teil struktur es egal was wir hier für
- einen schritt machen können wir immer danach regressiv an zwei teillösungen die unabhängig voneinander sind wieder irgendwie eine optimale
- lösung finden und können die an zusammensetzen dieser uns jetzt also den wert einer optimalen
- lösung regressiv definieren und zwar wenn wir einen stab der länge m haben dann berechnen wir den steuerertrag gm wir wissen nicht welchen schnitt machen
- müssen das heißt wir müssen alle schnitte ausprobieren wir berechnen en einfach als das maximum über alle möglichen schnitte das heißt
- wir müssen jedes mögliche uns rausnehmen schnitt sagt uns ja einfach nur nach ihr metern schneiden wir durch also kriegen wir entweder gar kein
- schnitt das benehmen dem profit für den kompletten stab oder beschneiden anstelle 1 dann kriegt man den maximalen ertrag hier plus den
- maximalen ertrag rüben oder wir schneiden anstelle 2 da kriegt man maximalen ertrag ihr plus dem maximalwert rüben und so weiter und das
- bis zum letzten spiel schneiden hier an 1 der kick maximalen ertrag hier plus dem maximalen ertrag da das heißt wir haben hier quasi en
- möglichkeiten wie können wir diesen erste schnitt setzen entweder gar nicht oder an einer dieser 1 -1 stellen und angenommen wir kennen jetzt eben
- alle diese erträge von 1 1 - 1 können wir jetzt regressiv einfach nachschauen was sind hier die optimale lösung ist das problem ist natürlich wir kennen die
- nicht also müssen wir die jetzt auch wieder berechnen das heißt um einem maximalen ertrag für einen stab der länge in -1 zu finden muss sie müssen
- wir jetzt wieder genau diese formel anwenden und haben wir jetzt wieder ein - 1 möglichkeiten wir dann den nächsten schritt setzen können wir müssen mal
- ausprobieren und da müssen dann auch wieder rico sif den ertrag für alles von 1 bis 10 -1 berechnen und haben schon eine sehr große reaktion die man
- durchgehen lassen es gibt eine kleine verbesserung die wir uns überlegen können und zwar wenn wir
- sagen wir schneiden hier durch unserer lösung die hat ja ganz viele schritte und was wir hier machen ist ja im prinzip
- beraten was ist denn der erste schnitt also wir probieren alle möglichkeiten aus raten heißt normalerweise im programmieren deiner algorithmics man
- probiert einfach jede möglichkeit dies gibt auszuprobieren aus wo setzt man den ersten schnitt und für jede möglichkeit davon kriegen wir das ein problem
- der erste schnitt da haben wir jetzt aber nicht gesagt welcher das ist dh wir können uns jetzt darauf beschränken zu sagen wir raten jetzt nicht wo man den
- ersten schnitt sondern wir raten wir den linken schnitt setzt wir probieren also immer noch alle möglichkeiten aus aber wir sagen jetzt links dürfe man nicht
- mehr weiter unterteilt das beschränkt uns ein lösungs raum nicht weil angenommen bekennen die optimale lösung wir haben stark wir
- haben ganz viele schnitte dann hätten wir jetzt auch einmal für den ersten schnitt die lösung ausprobiert wo man links das behalten und rechts neben
- regressiv weiter unterteilt deswegen dürfe man das machen wir verbieten einfach hier alles und dann müssen wir hier links nicht nochmal
- degressiv berechnen sondern können hier einfach direkt in der tabelle nachschauen divas eingabe gekriegt dann was es denn der profit für den stab der
- länge damit haben jetzt nicht mal zwei berechnung sondern nur noch eine und die lösung die man ausrechnen dass jetzt
- einfach pm oder pe 1+1 oder p2 plus minus zwei bis minus 1 plus ist das hier können wir uns jetzt ein
- bisschen schöner aufschreiben das ist das maximum über jedes von 1 bis en aus also den profit von
- starb der länge plus e von also der besten lösung wenn wir noch einen staat der länge - sie haben und wenn wir hier ändern setzen da werden pm
- +0 und der beste profit die wir für einen stapler lingen 0 haben ist natürlich 0 kriegt man gar nichts für und deswegen können wir jetzt alle diese
- möglichkeiten in so eine kleine form packen das kommt man hier oben noch nicht weil man hier unterscheiden mussten zwischen mps und denise
- der vorteil ist jetzt zusätzlich dazu dass wir schöne aufschreiben können wir können halt jetzt eine lösung aus einer zahl der eingabe und einem werte
- optimalen teillösung berechnen es müssen in jedem schritt vorwärts regressiv weiter gucken eben nur an einer stelle weitermachen und uns nicht nochmal
- aufspalten 2 wie schaut das ganze jetzt aus wenn wir das jetzt berechnen wollen wir machen
- das jetzt erstmal was natürlich quatsch ist aber wir machen sie es erstmals so wie bei die weiter kongress sowie beim export wir gehen von oben nach unten und
- berechne jetzt regressiv alle unsere lösungen ja mal so gesagt em ist das maximum aus dem profit für ein stapel enge e-plus regressiv berechnet ertrag
- von start der länge in - sie schreiben wir uns mal als pseudo court auf wir machen eine funktion stand zerlegung wir kriegen als eingabe unsere
- tabelle die uns quasi sagt für jedes i was ist denn unser ertrag von der länge haben und die zahlen das ist einfach die länge von diesen
- und wir haben gesagt der ertrag für stark meter länge 0 ist null wenn also jene 0 übergeben mitdenken man 1 0 zurück
- wie schaut es der rest der funktion aus können sie den aufschreiben probieren sie es mal pausieren sie mal und versuchen den zahlencode ihn zu
- schreiben ich gehe davon aus ihr habt es geschafft also gebe ich euch jetzt die lösung wir
- rechnen hier ein kuh das ist erstmal - unendlich aber wir gehen dann in einer schleife eben alle werte von 1 bis ende durch das ist
- im prinzip dieser teil ihr einst kleinen gleiche kleiner gleich en und für jedes berechnen jetzt diesen wert also p von a wir gucken wir hier nach
- und eva berechnen wie repressiv indem er einfach wieder diese tabelle übergeben aber mbn um ihn reduzieren und wenn das größer
- ist als das größte das man bisher gefunden haben dann wird es hier festgesetzt deswegen wenn jemand das maximum aus dem besten wert immer bisher
- hatten und dem neuen wert und am ende geben wir dann das kku zurück was uns eben genau diesen ertrag liefert
- schauen wir uns mal die laufzeit jetzt von dieser methode dafür müssen wir uns jetzt wieder eine funktion definieren und zwar die
- funktion a von ende gibt es die gesamtzahl der aufrufe von dieser funktion stangen zerlegung haben und zwar beim ausführen von stangen
- zerlegung von p e und n also wenn wir die mit einem wert n aufrufen wie viele regressive aufrufe haben werden dann insgesamt also nicht nur in diesem
- durchlauf sondern auch in den ganzen rezessions schritten fangen wir bei null an wenn wir eine null übergeben dann gehen wir gar nicht
- aggressiv weiter also kommt hier insgesamt 1 raus weil man es ja einmal selbst aufgerufen haben aber wir gehen nicht mehr degressiv rein deswegen kommt
- ihr nicht mehr dazu wenn das jetzt ne eins wäre jemand so nochmal durch wir rufen dass alma selber
- auf und beginnen einmal durch die schleife machen das einen regressiven aufruf für von 0 das hätten jetzt zwei
- verbraucht wenn man das allgemein für n machen dann haben wir natürlich einmal selber aufrufen und dann nochmal für alle werte
- von 1 bis nsn die rezessiven zahlen anschauen also einsplus die summe von 1 sn dass das hier auch von - dass das was hier steht da kommen jetzt das ganze so
- aggressiv ans peter aufschreiben und die frage ist natürlich was kriegt man hier aus
- wir können das erst mal ein bisschen umformen wir können dieses - die hirsche loswerden weil wenn wir uns einfach anschauen was für zahlen kommen hier
- dann rein bei ihr gleich eins steht hier ein minus 1 das geht runter bis nsn ist gleich null also haben wir eigentlich alle zahlen von 0 bis 1 - 1 stehen also
- machen wir jetzt einfach eine summen formel von null bis minus 1 über von j jetzt schaut euch schon mal ein bisschen schöner aus und jetzt müssen wir aber
- noch ausrechnen was herauskommt und da kommt man ziemlich schnell drauf dass das ganze zwei hoch n ist also exponentiell
- wieso das jetzt genau beweisen dass köhler jetzt einfach so machen wir setzen einfach dieses zwei hoch in hier überall ein also wir haben hier 20 + 2 1
- + 2 hoch 2 usw also 12 + 4 + 8 bis alles ist zwei wochen - 1 und wenn man alle diese zahlen aufsummieren dann kommt man halt auf zwei wochen - 1 und wenn man
- diese einst hier vorne dazu rechnet dann kommt mal wieder auf zwei wochen raus das heißt so können wir das jetzt durch vollständige induktion beweisen dass
- diese zahl korrekt ist aber für vollständige induktion muss das natürlich auch erstmal auf die lösung kommen die man beweisen will wie kommt
- man darauf indem man es einfach ausprobiert also wir schauen uns einfach an was a von null da kommen auf die eins dann können wir dann unser von 1 einfach
- mal regressiv ausrechnen und sehen wir da kommt mit zwei raus wir können wir uns hart von drei mal ausrechnen dann zehnmal kommt eine vierer von vier
- ausrechnen sehen bekommt eine 8 aus und mit ein bisschen gefühl sieht man dann relativ schnell dass es wahrscheinlich exponentiell ist wenn man schon gesehen
- hat 1 2487 das verdoppelt sich immer also probierten das dann mit dieser vermutung aber durch vollständige induktion zu zeigen kommt man drauf das
- stimmt und da hat man die richtige laufzeit gefunden so wir haben jetzt also alle unsere überlegungen gemacht wir haben alles
- inclusive schönen definiert wir haben uns eine funktion aufgeschrieben dieses regressiv berechnet aber wissen nicht besser geworden dass es immer noch
- exponentiell und woran liegt das jetzt als erfahrung ist es immer noch nicht besonders gut wenn wir uns jetzt einfach nur mal die
- ersten zwei schritte anschauen wir kommen am anfang an mit ende ist gleichwohl ja die länge von unserem staat und hier berechnen wir jetzt
- repressiv stang zerlegung von minus 1 und minus zwei und minus drei von einem minus 4 und so weiter und für jede von diesen zahlen gehen wir jetzt durch
- unseren reaktions baum durch wenn wir uns jetzt mal den nächsten schritt anschauen wo man hier ein minus
- 1 reinpacken da müssen wir hier auch noch mal aggressiv werde alles für enders 2 - 3 - 4 und so weiter durchrechnen das heißt wir gehen hier
- nochmal regressiv entstanden zerlegung von pe und ein - zwei rein obwohl wir das ja eigentlich schon mal auf dem obersten level berechnet haben also
- müssen wir zwei mal die komplette rezession führen - zwei durchlaufen wir müssen dreimal die komplette rezession führen - drei durchlaufen viermal für 1
- - 4 und so weiter und so wird es einfach immer größer immer größer und dadurch wird das dann exponentiell weil wir sehr viele sachen einfach mehrfach berechnen
- wir haben das eigentlich schon mal ausgerechnet wir wissen was es die beste zerlegung wenn wir hier sag mal in 110 haben aber wir machen das ganze nochmal
- machen die ganze berechnung noch mal und wir machen die nicht nur einmal noch mal nein wir machen die tausend male nochmal und dadurch dauert
- das natürlich sehr lang und da kommt jetzt das dynamische programmieren und spielt statt es jetzt einfach so ganz stupide immer relativ
- alles neu ausrichten zu müssen merken wir uns das was er gerne macht das ist das ist der ganze schlauen trick wir merken uns einfach diese lösung die wir
- hier gefunden haben statt zu neu zu berechnen also machen irgendwo notizen wo man auch schreiben hey ich weiß schon was ist die beste zerlegung und wenn ich
- eine starb der länge 5 ab da kriege ich nämlich das raus also wenn ich später noch mal nachgucken muss muss sich das nicht noch mal neu ausrechnen sondern
- schaue einfach in einer tabelle nach das heißt wir benutzen jetzt einen tabelle wo alle diese werde rein
- gespeichert werden das ist jetzt das sogenannte zeitspeicher tausch oder auf englisch time memory trade off wir benutzen jetzt mehr speicher also eine
- extra tabelle wo wir uns zwischen ergebnisse rein speichern um die laufzeit zu verlängern das speicher geht hoch laufzeit geht runter aber die
- laufzeit geht um sehr viel mehr hier runter als dass unser speicher steigt das kann man übrigens auch bei vielen anderen sachen machen also zum beispiel
- bei kürzestem wege suchen von erst nachdem wir konnten uns eigentlich eine tabelle vorher mal irgendwie ausrechnen wo wir
- für jedes t den kürzesten weg darin gespeichert haben und dann kommen wir später natürlich in konstanter zeit im bad finden aber die tabelle wird riesig
- die werden natürlich quadratisch groß und deswegen muss man das sehr viel speicher aufwenden um die laufzeit dann später runter zu kriegen und hier machen
- wir halt jetzt nur wenig speicher aber die laufzeit geht uns sehr viel runter wir passen jetzt also unsere methode ein bisschen an statt rico sie bestanden
- zerlegung nach memory stand zerlegung wir uns zusätzlich sachen merken und zwar machen wir jetzt uns einig dass b ist inter 3
- von null bis m das entspricht das genau dem ertrag das ist jetzt genau dieses das baby unserer repressions formel haben und hier wollen wir uns jetzt
- jeweils speichern was ist denn jetzt der beste ertrag den wir haben würden wir die stange unterteilen nach länge das heißt wir fangen an wenn wir längere
- haben kommt himmel 0 rein das ist klar da kann man nichts weiteren dateien aber alle anderen elemente die muss man noch ausrechnen also setzen wir die erst mal
- alle auf - und endlich - unendlich heißt für uns jetzt erstmal das müssen wir noch nicht was negatives kann ja nicht raus kommen in der praxis würde ich
- wahrscheinlich -1 reinschreiben wenn man weiß dass man auf jeden fall immer einen positiven ertrag hat keine 09 schreiben aber irgendwas wo man ganz
- klar weiß dieses ergebnis kann nie vorkommen dass man sieht da steht das hier drin heißt es ich das muss ich noch aus regnen
- also für alles von 110 bis was noch nicht deswegen steht - endlich da und jetzt wie es häufig bei regus treffens lösungen haben haben wir jetzt die
- zweite methode die hauptstadt zerlegung die wir eigentlich arbeit macht der geben wir jetzt also wieder unsere eingabe tabelle wir geben hier wieder
- eine zahl an und begeben java zusätzlich nochmal dieses eray wo jetzt unsere teillösung dänische ausgerechnet haben dringen gespeichert sind und
- das schaut jetzt fast genau so aus wir unsere rezessions stangen zerlegung der einzige unterschied ist wenn hier in unserem schon was anderes drin steht als
- - unendlich wir hier hast du schon mal irgendwann eine andere zahl rein geschrieben haben heißt es wir haben da schon mal die optimale lösung berechnet
- die kennen wir schon also können wir die direkt zurückgeben statt dass man die ganze region noch mal durchlaufen lassen aber wenn ihr noch nix drin steht wenn
- ihr ohne - nennt die steht dann muss man natürlich die ganze arbeit machen und das ist einfach genau die gleiche funktion auch mal wenn man ihm wieder
- ein coup ist - dann endlich da wollen wir jetzt den besten ertrag finden wir gehen unsere schleife durch das heißt wir probieren alles aus von 1 bis
- endungen der schnitt setzen und berechnen ja was ist dann der profit für das erste stück der länge bloß regressiv was es da ertrag für das
- zweite stück der länge m - sie nur dass wir hier halte es auch wieder unsere ray wo jetzt die teillösung vielleicht schon drin steht mit übergeben damit wir das
- entsprechend nachschauen können falls wir die lösung schon kennen und damit sich diese erfüllt nachdem wir das jetzt ausgerechnet haben müssen wir
- das jetzt natürlich auch eine rein schreiben wir kennen jetzt was der maximale ertrag für ein stab der länge von 1 auf kuh und gehen zurück
- die frage ist jetzt natürlich wieder was ist die laufzeit davon haben wir die gleiche laufzeit wir vorher bei der repression oder
- sind wir assen tote schneller das ist hier jetzt relativ schwer zu analysieren wir müssen jetzt wieder eine
- rezessions formel aufstellen für die laufzeit aber die laufzeit die wir da kriegen die hängt davon ab was wir schon vorher gemacht haben deswegen lässt sich
- dass da jetzt nicht so genau sagen also statt hier jetzt die regions- formel aufzustellen werde ich euch jetzt noch mal eine neue methode zusätzlich
- methode geben die macht genau die gleiche arbeit wie hier nur halt nicht so mit dieser rezession sondern arbeitet die bottom up
- das was hier jetzt sind diese neuen funktion passiert dass genau das gleiche wie hier es ist nur anders formuliert ist nur anders aufgeschrieben
- schauen wir uns also mal gemeinsam diese methode an wir haben als eingabe wieder unser raid mit den profiten wir haben uns und wir wollen uns wieder so ein
- ertrags ray machen wo wir unsere teillösungen reinschreiben und ii von null ist natürlich nun
- und startet jetzt relativ zu machen machen wir jetzt alles jetzt in einer schleife zu beginn durch von j von 1 sn und wir rechnen uns jetzt eben erst mal
- von 1 dass wir berechnen uns erstmal was ist der maxime der ertrag der für einen stab der länge 1 kriegen und der ist natürlich genau p von 1
- autos können wir jetzt allgemein hier durch eine regression formel machen wir gehen von 1 bis 4 und schauen uns eben genau diese formel an
- für den wir vor den rekord aufgestellt haben dass die uns jetzt eben den ertrag gibt und speichern das dann in unserer tabelle
- also wenn wir uns das genau anschauen als erstes berechnen wir von 1 wir machen hier einen schleifen von 1 bis 1 berechnen mir was sp von
- 10 also da schreibt man einfach p von 1 rennen also wir können nicht weiter unterteilt ist klar wenn ihr gleich zwei ist gehen wir hier eine schleife durch
- wir berechnen erstmal was ist der profit für ein stück der länge 1 plus was den ertrag für ein stück der länge 1 und das haben wir ja vorher schon ausgerechnet
- steht schon unsere tabelle drin und das zweites was der profil für ein stück der länge 2 und da rausnehmen jetzt wäre die beste
- lösung und das ganze dann für drei wieder entweder mitnehmen dreier stück oder 2 und 1 oder 1 1 und 2 4 anna vierer stück oder drei plus eins oder
- zwei plus eins oder eins zwei und wir benutzen hier das jetzt halt die wichtige beobachtung wir schauen sie jetzt eigentlich immer nur erträge an
- von stangen die kürzer sind ist ja klar wenn man schneiden kann man nie ne stange kriegen die länger ist das heißt wir gucken uns hier nur werte an die wir
- schon berechnet haben die also schon hier in unserem drin steht und damit können wir das hier zum bottom up indem er einfach jeweils schrittweise
- die länge des stabs erhöhen unsere lösungen berechnen statt das mir durch eine rezession gehen muss wir haben also keinen regressiven aufruf
- und damit kann man jetzt hier viel einfacher unsere laufzeit analysieren benutzen immer noch eine tabelle aber wir gehen uns einfach einmal von unten
- nach oben gucken wir uns einmal diesen grafen der teil instanzen an also wir haben teil
- instanz der länge 0 der länge 1 der länge 2 länge 3 länge 4 jetzt für unser beispiel können in graphen kanten einfügen nun
- bekannte bedeutet wenn wir teil instanz deckel länge j haben dass die times 1 j da müssen wir einmal die optimale lösung von teil instanz anschauen
- wenn wir also starb der länge 1 haben dann müssen wir einmal die optimale lösung für länge 0 anschauen starb dann länge 2 haben müssen wir einmal optimal
- lösen für 1 und 4 0 anschauen bei der drei einmal für 21 und 0 4 1 mal 4 3 2 1 0 das sind also immer alles anschauen was wir vorher schon berechnet haben
- also für eine teil- instanziert müssen wir andere optimale lösungen die wir vorher
- berechnet haben schon mal an stand das hier ist also ein kreis der hat
- +1 knoten und wie viele kannten kanten graf mittäter von knoten haben jede kante ist zwischen zwei knoten also
- kann es maximal täter vom quadrat viele seien und dieser graf der gibt uns jetzt eben auch diese laufzeit dieses dynamischen programms zurück das sind
- genau die anzahl addition die wir haben weil wir jedes für jede von diesen kanten schauen wir uns einmal tabellen einen tag hier de an davon
- müssen jeweils eine addition machen aber jeder wird auch nur einmal angeguckt also nur für eine schau mir das jahren so jede kante hier entspricht genau eine
- addition und damit kommen wir her auf ofen eng vertraut zeit weil wir eben in diesen grafen wovon m ² kanten haben
- so kann man uns jetzt beweisen für diese bottom up standen zerlegung dass die eine laufzeit von overland verdrahtet eine andere möglichkeit ist sie jetzt
- natürlich auch einfach das klassische zu machen wir haben hier eine schleife geht von 1 bis 10 also machen was immer von 1 bis 10 da drin hat man eine schleife von
- 1 passiert also manchmal noch mal eine summe von 1 bis jetzt und hier haben eine addition kostet uns also jeweils 1 und wenn wir das ganze aus rechnen da
- kann man genau auf unsere laufzeit und wissen dadurch auch das sofort ein quadrat liegt aber dieser analyse hier mit den kanten die funktioniert eben
- nicht nur für die bottom up standen zerlegung sondern die kammer auch für unsere vorherige methode die memo stanzel erlegung hier verwenden indem er
- hier auch wieder diese addition zählen und stark indes nicht so einfach mit der schleife weil wir hier halt regionen mit schleifen verbinden
- da kommen uns aber trotzdem natürlich auch einfach diese addition wieder so als graf vorstellen und damit die eigenschaften von graphen verwenden um
- die laufzeit zu beweisen also auch wenn man das jetzt bei dieser methode nicht brauchen das ist denn gut dass du im hintergrund kopf zu behalten man kann
- sich so einen grafen aufbauen für diese teil instanzen und sich dann einfach anschauen wie viele kannten haben wir da drin und da kriegen wir die laufzeit aus
- was haben jetzt also gemacht wir haben zwei methoden gefunden nochmal die memo stangen zerlegung und die bottom up zustand erlegen die
- jeweils für die kosten von einem weiteren rey mit enplus a1 elementen also und einer extra speicher und die lösung berechnet nur dass wir hier jetzt
- nur noch quadratische zeit brauchen statt exponentielle ein quadrat statt zwei wochen und der unterschied zwischen eng quadrat und zwei wochen ist so
- gewaltig dass wenn ihr seid 2 spiel an sagen wir mal erst sehen zwei hoch wer dann schon 1024
- aber im quadrat ist nur 100 da ist noch faktor 10 aber jetzt sitzt mal 20 12 hoch 20 ist ungefähr eine millionen aber 20 zum
- quadrat es nur 400 und so steigt das immer weiter 32 ist dann schon eine milliarde aber hier kommt nur auf 900 ist es immer noch unter 1000 und dann
- kommt man auf 10 12 10 15 10 noch 18 während es sich die hier immer noch im tausender bereich aufhält und das macht ganz schnell den unterschied für kleine
- zahlen von innen schon zwischen der laufzeit von einer minute und von jahrtausenden aus was einfach gar nicht mehr machbar ist
- wir haben jetzt natürlich noch einen schritt den man noch gar nicht angeschaut haben wir müssen jetzt noch die optimale lösung konstruieren was mir
- hier immer machen ist wir berechnen eigentlich immer nur den ertrag also wenn wir diesen algorithmus laufen lassen was kriegt man am ende zurück
- eine zahl das sagt uns genau das ergebnis des 10 und dann sitzt man da ja auch schon cool jetzt weiß ich ich kann die stange
- irgendwie so zu legen dass sich aber das sagt uns nicht wie er gibt uns immer nur dieses gut zurück wir müssen also jetzt irgendwie nochmal die zerlegung selber
- unser ausrechnen dass sie müssen irgendwie jetzt nochmal aus den berechnenden informationen uns diese optimale lösung rekonstruieren
- deswegen erweitern wir jetzt unseren algorithmus ein kleines bisschen so dass man das eben auch noch mal üben die mit speichern
- machen dass man das gleich gefallen wir machen wir dann neue tabelle setzen 300 rein wir machen wieder unsere schleife da wollen wir jetzt für alle jungs von 1
- bis 10 wieder ausrechnen was denn die beste lösung das haben wir genauso wie vorhin gemacht aber hier danach erst einmal eine kleine änderung
- nämlich statt dass wir hier einfach das maximum ausrechnen gucken wir uns an an welcher stelle ändert sich dann das also immer wenn das kku sich ändert also wenn
- wir was besseres gefunden haben eine bessere lösung dann setzen wir unser kuh natürlich auf das maximum
- aber wir sprechen jetzt in der 2 tabelle in dieser tabelle l und sitzt noch mal woher haben wir das denn jetzt gekriegt das sagt uns jetzt also für eine stange
- der länge j haben wir die beste lösung gekriegt als wir uns dann schnitt nach länge gesetzt haben das heißt wir müssen hier jetzt
- natürlich auch noch mal massiv zusätzlich die cell mit übergeben bzw hinter porto mappus nicht unbedingt negativ aber wir müssen hier ist eingabe
- haben oder wir müssen uns das hier noch mögen die rein schreiben wir machen sie jetzt das eingabe damit es dann eben die perlen funktion die die aufruf gemacht
- hat dass die auch noch zugriff darauf hat und hier in l nachschauen kann was gibt mir jetzt also zurück zum einen natürlich diesen rat den kann man sich
- aber auch direktors murray auslesen der steht nähe von n aber für jedes wort von 110 haben wir jetzt eben in dieser tabelle noch drin stehen wir haben die
- beste lösung hier gekriegt in dem anschnitt nach länge gemacht haben und daraus können wir uns jetzt ganz einfach wieder die lösung den lösungsweg
- rekonstruieren wenn wir das die zerlegung ausgeben wollen für unser p e und n dann machen wir anfangs einfach diese
- zwei race l und e wir führen diese erweiterte bottom up zerlegung mit diesen arrays aus und uns jetzt auszugeben gehen wir einfach durch
- sergej durch gruppen einmal nach bei 11 von n was steht drin wollen wir das schnitt gemacht geben dass er aus und das sagt uns jetzt
- zum beispiel nach stelle 10 haben im schnitt gesetzt also guckt man danach ja das heißt rechts haben wir jetzt noch länge 1 -10 hast den alltag kammer hier
- aus e finance inc kriegt wir gucken jetzt also drin was steht in 11 von minus zehn drin wo wir den nächsten schritt gemacht haben und das sagt dann
- ist er wieder schnitt nach soundsoviel da guck mal wieder da wir in den nächsten eintrag von elf nach und können so uns eben durch dieses rl durchhangeln
- und alle unsere schnitte wiederfinden und kriegen somit wiederholt die länge des teilstücks und wiederholt unsere lösung wenn also das hier jetzt unsere
- optimale lösung wäre dann wird das bedeuten wir mal ein schnitt nach länge 3 einmal nach zwei und noch einmal nach zwei gemacht und das wären jetzt auch
- genau die tabellen einträge von l einmal für die sieben jetzt ganze haben würden drei drin stehen dann die 4 das ist dieses stück steht der 23 und dann am
- ende noch zwei stück steht nicht zwei drin wir haben also ganz am ende geschnitten beziehungsweise gar nicht und wir wissen so jetzt genau wie lange
- unsere ganzen teilstücke sind gemälde 3 und zweimal mit 2 und das ist jetzt unsere ganze lösung für dieses problem zu kümmern die für
- die starb zerlegung eben uns ausrechnen mit diesen dynamischen programm wie kriegt man unseren attraktiviert und was ist der profit am ende und wie wir
- unsere zerlegung wir wollen uns jetzt noch mal ein kleines weiteres beispiel anschauen
- nämlich die sogenannten längsten wege beim längsten wegen wir haben bisher schon kürzeste wege gemacht mit der
- extraktion spiel hier haben wir jetzt als eingabe erstmal in der ungewichteten gerichteten grafen also wir haben richtungen die mir lang gehen dürfen wir
- haben einen start und knoten s&t und es gibt auch eine fahrt von es nach dem was man hier jetzt finden wollen ist ein
- längster einfacher ästhetik bei einfach bedeutet dass wir keine knoten auf dem weg mehrfach besuchen griff suchen also eine folge von knoten von null bis vk
- wobei wir bei es anfang mai aufhören und diese kanten auf dem weg müssen alle unser grafen sein dass wir haben bekannte von frauen erfahren und so
- weiter und die sind alle unterschiedlich aber dass k s maximal weil es eben längst weg ist
- und können jetzt wieder unsere schritte von der dynamischen programmierung durchgehen das heißt wir müssen erstmal die struktur der optimalen bösen
- charakterisieren gucken wir uns also mein ganz kleines beispiel an wir wollen hier in kürzesten weg von es nachts häfen
- wie könnten wir das jetzt angehen indem wir teil instanzen bilden und die dann zusammensetzen um kürzesten weg von es nach de zu finden
- eine idee wer jetzt dass wir uns einfach mal anschauen mit welchen kann kommen mit einem buy an also wir können entweder von v kommen
- oder wir können von ihm kommen das heißt wir können uns jetzt teilen stunts und definieren wir finden einmal den weg von es nach v den längsten und hören damit
- dieser kannte auf das ist eine möglichkeit wie man hinkommen oder wir suchen den längsten weg von ist nach und hören damit der kante ut auf das man
- jetzt also zwei mögliche lösungen und andere lösung kann sie eigentlich geben wir können nur von frau davon nach t hinkommen
- hier jetzt aber ein kleines problem da kürzt der längste einfache weg von es nach dem gibt es zwei möglichkeiten entweder
- svt oder sut wir haben also einen längsten einfachen weg des so ausschaut das setzt sich jetzt zusammen aus dem weg von es nach
- und der kante ut wenn wir uns jetzt aber mit einem stunts anschauen sagt findet in kürze den längsten einfachen weg von es nach
- dann gibt er uns nicht diese kante aus sondern diesen weg da hier hinten entlangführt wir können einmal nach frau laufen danach tee und danach zurück und
- dann haben wir einen einfachen weg der länge 3 gefunden nun können wir da jetzt nicht die kante ut drinnen dran hängen weil das ganz nahe neben nicht mal
- einfach wäre das heißt hier können wir jetzt unser dynamisches programm nicht verwenden und tatsächlich wissen wir auch nicht
- wie man dieses problem effizient lösen kann weil das ist mp schwer und um zu sehen dass es schwer ist kommen da kommt man recht einfach drauf indem er sich
- das mal ein bisschen hamilton weg vergleicht damit den weg haben wir einmal kurz erwähnt am anfang bei den grafen und da geht's darum man will weg
- finden zwischen zwei knoten der jeden anderen knoten genau einmal besucht und das ist ein klassisches mb schweres problem
- und dieser längste weg wenn hamilton weg gibt dann ist es eben so eine aber besucht genau jedem knoten einmal und wenn man das jetzt lösen könnte dann
- könnte man auch dass hamilton weg problem effizient lösen da ist wenn man davon ausgeht die ungleich mp gibt es hier keine
- effiziente lösung wenn man doch mal eine findet dann hat man mit wenigen problem gelöst
- was macht man jetzt als algorithmics wenn man ein problem hat das irgendwie schwer ist versucht man entweder andere ansätze wie ira programmieren oder
- fest parameter berechenbarkeit oder schnelle exponential zeit algorithmen dass wir uns aber alle sachen die wir in der vorlesung die nicht machen es kommt
- ein fortgeschrittener algorithmen oder man vereinfacht das problem halten zusätzliche restriktionen rein dieses problem leichter machen bis wir eine
- version gefunden haben die sich effizient lösen lässt und das kann man hier machen indem man jetzt einfach zusätzlich sagt der graf
- soll kreisfrei oder art zyklisch sein dass wir wollen hier jetzt keinen gerichteten kreis haben sonst in graf hier anschauen hier haben wir ganz viele
- gerichte kreise also ganz viele heißt wir haben hier ein wir haben hier einen hier einen hier einen also zwischen geben knoten paar sozusagen
- und wir haben auch noch mal zwei die komplett durch alles durchlaufen einmal der hier und auch der in die andere richtung da sind wir sechs kreise und
- die nicht haben dürfen dann wird das problem einfach wenn wir uns nämlich jetzt den längsten stw kann schauen dann können wir ein
- paar beobachtungen anwenden die erste ist alle wege in den kreis weingarten sind einfach angenommen wir haben den weg der nicht einfach ist das heißt er
- besuchte irgendein knoten doppelt dann kommt irgendwann bei diesem knoten an folgt kannten bis er wieder bei den knoten ist aber das wird bedeuten dass
- ein kreis entlang gelaufen ist und in dem grafen gibt es keinen kreis also beobachter nein stimmen und die zweite ist hier haben wir jetzt eine
- optimale struktur weil wenn du jetzt mal davon ausgehen es gibt einen längsten s&t weg der durch läuft also es gibt einen weg der stadt so aus erst mal die
- teilstrecke von es nach und dann die teilstrecke von nach t dann ist es längst asu weg und der thai weg von uc ist ein längst weg ansonsten
- werde es jetzt eben kein längster ästhetik gewesen außerdem gilt das eben die knoten die man sich auf diesen teil streben an
- stück dann schaut genau es ansonsten wenn es irgend noten gibt der hier vorkommt hier vorkommt dann hätte man da auch wieder den kreis gefunden
- das heißt wir hätten hier in knoten wir laufen kanten entlang bis er wieder bei ihm selber sind das wissen einmal im kreis gelaufen und es gibt es nicht wenn
- s class preis also gilt auch unsere beobachtung 2 und wir können hier jetzt ein dynamisches programm anwenden
- gehen wir also unser fahrplan weiter durch wir haben es ist erstmal charakterisiert wir müssen quasi einen knoten auf dem weg finden ein relativ
- den längsten pfad zu ihm finden und dann längste fahrt von ihnen zu themen aus dieser struktur können wir uns jetzt wieder relativ eine optimale lösung
- definieren und zwar ist der längste weg von es zu sich selber natürlich 0 aber zu jedem anderen knoten kann man das berechnen
- indem wir einfach alle eingehenden kanten von dem anschauen und zwar muster katja über irgend so eine eingehende kannte gelaufen sein das heißt wir
- schauen uns alle knoten uhr an für diese gerichte bekannte von nach frau geht dann gucken wir nach was ist der längste fahrt nach und hängen die kante uv dran
- also das gewicht von uv und mit dem gewicht arbeiten wir hier weil wir eben jetzt mit einem gewichteten grafen arbeiten und hier nochmal unsere
- gewichts funktion haben man kann das natürlich auch für ungewichtete machen dann sind alle unsere gewichte einfach 1
- das ist unsere inklusive definition und jetzt müssen wir wieder die optimale lösung berechnen das können wir jetzt wieder auf zwei arten machen wir können
- das natürlich wieder regressiv machen oder wir können das wieder bottom up machen das wichtige dabei ist eben dass wir uns auf dem weg wieder unsere
- optimalen lösungen die man gefunden haben zwischenspeichern dass das mit der tabelle haben die wo eben alle diese werte drin stehen die männer wieder nach
- gucken können wenn man nicht viel über das problem weiß dann ist das rezessive meistens einfach weil das kümmert sich selber
- darum dass es alles richtigen reihenfolge macht guckt einfach wieder stelle nachweislich hier die lösung schon wenn ich dann berechne ich weiter
- ansonsten cookies danach das hat auch als nachteil dass man wieder mehr speicher braucht wenn man immer noch diese ganze region aufrecht
- halten muss wenn man jetzt also schon vorher weiß in welcher reihenfolge man alles berechnen muss dann kann man das bottom up machen und schneller
- die frage ist natürlich immer wie macht man das sportheim ab als wie finde ich eine gute reihenfolge und da kann man es einfach unsere topologische sortierung
- wassertiefen suchen vorlesung benutzen das begehen das theologisch durch und dann können wir uns sicher gehen immer wenn wir einen knoten anschauen dann
- haben wir schon alle knoten verarbeitet für diese kann dorthin gibt das ist ja die eigenschaften der topologische sortierung
- dass die initialisierung zu unsere de werde ds gleich null alles andere auf - unendlich machen dann eine vor schleife durch die knoten von links nach rechts
- also entlang der topologischen sortieren und berechnen die idee werte eben nach dieser regressiven funktion wobei wir uns immer sicher sein können dass wir
- alle diese die eu schon kennen eben auch sonst topologischen satire raus und dann zimmer eigentlich schon fertig dann haben wir schon unsere lösung
- gefunden und dann kommen wir das gleiche wie vorhin machen wieder um unseren weg tatsächlich zu konstruieren uns dass wir jetzt erstmal nur die länge von dem weg
- ausgeben würde so ganz nebenbei die kürzesten wege in kreisfreien grafen die kommen wir jetzt auch zu modellieren also statt da extra
- stern zu benutzen kann man hier einfach minimum stadt maximum verwenden und plus unendlich statt - unendlich und dann kriegt man auch das mit dem gleichen
- algorithmen und man kann damit auch das so genannte t9 problem lösen das kennt es von euch sicherlich keiner mehr aber mein erstes
- handy da hatte ich noch tasten von 109 und die null und hinter jeder taste waren dann noch mal drei buchstaben zb hinterher 2 war änderte 1 von abc was
- mich zweimal gedrückt habe kam der ausbau nicht damit gedrückt hatten zehn und so weiter und hier kann man sich daneben auch noch mal angucken ja wie
- komme ich denn jetzt zu einem buchstaben welchen weg muss ich hier entlang gehen um irgendwohin um irgendein satz zu schreiben und das kann man eben mit dem
- mal machen so das war's für heute über das dynamische programmieren in dem buch
- gibt es noch mal viele weitere probleme wenn sie interessiert die auch praxis relevant sind und diese dort mit dem literarischen programm ihr lösen zum
- beispiel ketten von matrix multiplikation denkt ihr euch vielleicht ja durch praxisrelevante jetzt kommt damit so was nie matrix multiplikation
- braucht man tatsächlich andauernd man sieht's nicht auf den ersten blick aber häufig wenn man irgendwelche
- probleme hat auch auf graphen kann man sich diese effizienz matrizen anschauen und muss dann irgendwo mal was multiplizieren
- oder vielleicht ein bisschen klarer dass man das braucht die längste gemeinsame teil folge in zeichenketten so wir gucken uns jetzt zum beispiel zwei texte
- an und wir wollen herausfinden ja was ist denn das längste gemeinsame stück das zum beispiel für die plagiats findung ganz schön oder auch allgemein
- einfach teil folgen zu finden in zeichenketten asse textpassagen übereinstimmen kann man über den namen skalieren machen
- und auch sogenannte optimale binäres suchräume kann man darüber machen da bin ich such beim bisher ja es kann besonders schlecht seien indem sie
- einfach ein langer parteien bekommen sie balancieren aber es gibt daneben noch das problem dass man schon vorher weiß einfach mit welcher häufigkeit welche
- sachen dann angefragt werden und dann kann man für jeden baum sagen wie gut er eigentlich so mischen wie lange braucht er insgesamt für eine sequenz von
- anfragen wo jedes wort mit einer gewissen wahrscheinlichkeit angefragt wird und dann kann man sich für diese
- wahrscheinlichkeiten den optimalen zug form berechnen der da eben besser und das wenig zeit braucht
- das war's für heute wir haben jetzt noch genau zwei vorlesung vor uns nächste woche nämlich einmal kritik rhythmen und programmieren in der praxis oder
- algorithmen der praxis ich hoffe das video hat euch gefallen und ich wünsche euch noch einen schönen deshalb auch