Dynamisches Programmieren | Algorithmen und Datenstrukturen - Vorlesung 22
Philipp Kindermann
https://www.youtube.com/watch?v=sSTzVUHg7-g

Transkript (automatisch erstellt)

0:00 herzlich willkommen zur 22 vorlesung von algorithmen und datenstrukturen wie angekündigt werde ich die vorlesung heute mal aufnehmen und durch vorher zur
0:08 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
0:17 eigenen tempo anschauen kann weil ich jetzt nicht so viele warten nicht so viele fragen stellen mit der kommunizieren können deswegen schaut
0:25 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
0:34 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
0:43 wir haben das in der vorlesung schon mehrere entwurfs techniken kennen gelernt gerade am anfang uns waren bei angefangen mit dem inkrementellen
0:51 algorithmen sowie in sessions ort wir hatten rezessiver algorithmen sowie mercks ort werden teile und herrsche es war auch unter anderem merger & spiel
1:04 hatten randomisierter algorithmen sowie zum beispiel remmers quixote heute wollen wir das nochmal erweitern und wohl noch eine weitere entwurfs
1:13 technik ändern nämlich das dynamische programmieren wobei programmieren hier jetzt nichts mit dem programmieren klassischen schützen zu tun hat sondern
1:23 das bedeutet hier dass wir mit einer tabelle arbeiten und nicht den computer programm schreiben dynamisches programmieren hat sehr viel
1:31 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
1:41 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
1:50 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
1:59 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
2:09 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
2:19 unterschiedliche bereiche aufgeteilt dieser unabhängig voneinander lösen können beim dynamischen programmieren zerlegen
2:27 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
2:37 wieder sortieren dass wir das in unterschiedliche bereiche unterteilen aber dass manche zahlen eben in mehreren bereichen gleichzeitig so
2:45 dass wir der geometrisch versuchen zu veranschaulichen wir haben eben gewisse anzahl von punkte da können wir hier so zum beispiel
2:53 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
3:02 so kriegen wir unterschiedliche teil instanzen wobei hier die einzelnen bereiche alle komplettes jungs sind sind hier diese teilmenge neben überlappend
3:12 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
3:23 ausschaut die lösungen von den teil instanzen die mir hier haben die werden jetzt dafür aber zwischengespeichert und nicht immer
3:33 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
3:42 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
3:52 das bedeutet dann eben dieses dynamische programmieren er schaut sich teil instanzen an aber wenn man speichert die ergebnisse jeweils in der tabelle
4:02 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
4:11 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
4:21 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
4:30 daraus für drei elemente usw das teile und herrsche benutzen wir hauptsächlich für entscheidungs oder berechnungs probleme und das dynamische
4:40 programmieren benutzen wir hauptsächlich wenn wir optimierungs probleme haben wenn sie also nicht nur einfach eine lösung gibt sondern wenn es viele
4:48 mögliche lösungen gibt wir aber die beste davon finden wollen wird es dynamische programmieren gibt so einen standard farb- laden und da
4:58 besteht aus vier schritt erstmal wollen wir für eine optimale lösung die struktur charakterisieren dann wollen wir uns relativ den wert
5:08 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
5:19 vierten schritt wollen wir dann aus den berechneten informationen konstruieren das neue ich die schritte die man jedes mal durchgehen muss wenn man dynamisches
5:28 programm macht wobei der vierte schritt bei den meisten eigentlich sehr ähnlich ausschaut und man den meistens überspringt weil der eigentlich relativ
5:36 klar ist aus den ersten drei schritten wir machen den heute bei einem beispiel mit aber ansonsten werden wir denen meistens weglassen
5:45 wir wollen es heute zwei probleme anschauen an dem er feststellen wollen wir denn dieses dynamische programmieren funktioniert das erste ist das
5:54 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
6:04 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
6:14 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
6:22 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
6:30 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
6:40 bekommen schauen wir uns mal ein ganz kleines beispiel einfach mal nur einen stab der länge 4
6:48 welche möglichkeiten haben wir jetzt diesen stab zu unterteilen auf wie viele kommt er da
6:57 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
7:08 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
7:17 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
7:27 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
7:35 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
7:42 mal gefunden haben und eine lösung kriegt man natürlich noch mal mach jetzt hier nochmal durchschneiden dann haben wir jetzt vier
7:49 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
7:58 schneiden die kann auch schon die optimale lösung sein wenn uns das den besten ertrag gibt wir haben jetzt also acht mögliche
8:07 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
8:14 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
8:22 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
8:37 von diesen acht lösungen werden und jetzt die beste also würden wir uns einer tag maximieren
8:44 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
8:56 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
9:05 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
9:17 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
9:27 machen um unserem attraktion maximieren eine möglichkeit ist natürlich einfach alle möglichkeiten auszuprobieren des
9:36 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
9:45 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
9:56 diese kombination davon würden uns dass eine zerlegung geben das heißt wir haben hier en -1 stücke einmal
10:05 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
10:15 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 -
10:29 einst so hier zweimal ihr zweimal ihr 200 weiter und das hier ist natürlich exponentiell und exponentiell ist nichts was wir
10:40 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
10:49 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
10:59 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
11:07 oder wir probieren sie einfach mal mit einem einfacheren ansatz mit so einem sogenannten greedy ansatz genau genommen haben wir hier nicht zu
11:16 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
11:25 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
11:35 drittel geteilt durch dieser teil als es immer noch hoch die dieses ganze stückchen hier also europa wurzeln im exponenten man
11:47 das ist immer das problem jetzt mit einem retina algorithmus aus wie konkret die algorithmus ausschauen
11:57 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
12:09 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
12:21 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
12:32 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
12:42 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
12:53 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
13:01 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
13:10 ziemlich streichens der tabelle und spiel wiederholen den prozess bis wir fertig sind die frage die man sich stellen müssen
13:19 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
13:30 beispiel finden das könnt ihr euch mal überlegen was glaubt ihr dann ist dieser algorithmus optimal oder ist das nicht
13:41 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
13:52 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
14:00 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
14:10 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
14:19 also ist es im allgemeinen auch nicht in wir noch mal zurück zu unserer idee mit allen zerlegung anschauen
14:29 wir wollen da jetzt den dynamischen programmierung ansatz darauf anwenden so dass man vielleicht nicht jeder einzelne zerlegung nochmal berechnen muss
14:40 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
14:53 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
15:03 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
15:15 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
15:29 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
15:41 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
15:53 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
16:04 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
16:15 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
16:25 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
16:33 kriegen können und angenommen wieder wir kennen all diese werte bis minus 1 dann könnten wir jetzt einfach alle schnitte ausprobieren
16:43 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
16:53 dann anschauen welcher schnitt ist jeder inder beste wenn wir also so ein schnitt nehmen dann zerlegt es das problem in zwei
17:03 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
17:14 einen schritt machen können wir immer danach regressiv an zwei teillösungen die unabhängig voneinander sind wieder irgendwie eine optimale
17:25 lösung finden und können die an zusammensetzen dieser uns jetzt also den wert einer optimalen
17:34 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
17:48 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
17:59 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
18:11 schnitt das benehmen dem profit für den kompletten stab oder beschneiden anstelle 1 dann kriegt man den maximalen ertrag hier plus den
18:22 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
18:32 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
18:44 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
18:56 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
19:08 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
19:17 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
19:24 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
19:34 durchgehen lassen es gibt eine kleine verbesserung die wir uns überlegen können und zwar wenn wir
19:43 sagen wir schneiden hier durch unserer lösung die hat ja ganz viele schritte und was wir hier machen ist ja im prinzip
19:51 beraten was ist denn der erste schnitt also wir probieren alle möglichkeiten aus raten heißt normalerweise im programmieren deiner algorithmics man
20:01 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
20:11 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
20:19 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
20:29 mehr weiter unterteilt das beschränkt uns ein lösungs raum nicht weil angenommen bekennen die optimale lösung wir haben stark wir
20:38 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
20:46 regressiv weiter unterteilt deswegen dürfe man das machen wir verbieten einfach hier alles und dann müssen wir hier links nicht nochmal
20:55 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
21:05 länge damit haben jetzt nicht mal zwei berechnung sondern nur noch eine und die lösung die man ausrechnen dass jetzt
21:13 einfach pm oder pe 1+1 oder p2 plus minus zwei bis minus 1 plus ist das hier können wir uns jetzt ein
21:27 bisschen schöner aufschreiben das ist das maximum über jedes von 1 bis en aus also den profit von
21:39 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
21:52 +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
22:03 möglichkeiten in so eine kleine form packen das kommt man hier oben noch nicht weil man hier unterscheiden mussten zwischen mps und denise
22:12 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
22:23 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
22:31 aufspalten 2 wie schaut das ganze jetzt aus wenn wir das jetzt berechnen wollen wir machen
22:40 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
22:50 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
23:01 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
23:13 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
23:23 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
23:34 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
23:43 schreiben ich gehe davon aus ihr habt es geschafft also gebe ich euch jetzt die lösung wir
23:53 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
24:03 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
24:15 und eva berechnen wie repressiv indem er einfach wieder diese tabelle übergeben aber mbn um ihn reduzieren und wenn das größer
24:27 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
24:35 hatten und dem neuen wert und am ende geben wir dann das kku zurück was uns eben genau diesen ertrag liefert
24:46 schauen wir uns mal die laufzeit jetzt von dieser methode dafür müssen wir uns jetzt wieder eine funktion definieren und zwar die
24:55 funktion a von ende gibt es die gesamtzahl der aufrufe von dieser funktion stangen zerlegung haben und zwar beim ausführen von stangen
25:07 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
25:19 durchlauf sondern auch in den ganzen rezessions schritten fangen wir bei null an wenn wir eine null übergeben dann gehen wir gar nicht
25:29 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
25:38 ihr nicht mehr dazu wenn das jetzt ne eins wäre jemand so nochmal durch wir rufen dass alma selber
25:46 auf und beginnen einmal durch die schleife machen das einen regressiven aufruf für von 0 das hätten jetzt zwei
25:56 verbraucht wenn man das allgemein für n machen dann haben wir natürlich einmal selber aufrufen und dann nochmal für alle werte
26:04 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
26:20 aggressiv ans peter aufschreiben und die frage ist natürlich was kriegt man hier aus
26:28 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
26:36 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
26:48 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
26:57 noch ausrechnen was herauskommt und da kommt man ziemlich schnell drauf dass das ganze zwei hoch n ist also exponentiell
27:06 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
27:22 + 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
27:38 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
27:47 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
27:57 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
28:05 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
28:13 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
28:21 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
28:30 stimmt und da hat man die richtige laufzeit gefunden so wir haben jetzt also alle unsere überlegungen gemacht wir haben alles
28:40 inclusive schönen definiert wir haben uns eine funktion aufgeschrieben dieses regressiv berechnet aber wissen nicht besser geworden dass es immer noch
28:48 exponentiell und woran liegt das jetzt als erfahrung ist es immer noch nicht besonders gut wenn wir uns jetzt einfach nur mal die
28:59 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
29:10 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
29:22 unseren reaktions baum durch wenn wir uns jetzt mal den nächsten schritt anschauen wo man hier ein minus
29:29 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
29:39 nochmal regressiv entstanden zerlegung von pe und ein - zwei rein obwohl wir das ja eigentlich schon mal auf dem obersten level berechnet haben also
29:47 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
29:56 - 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
30:07 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
30:16 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
30:23 das natürlich sehr lang und da kommt jetzt das dynamische programmieren und spielt statt es jetzt einfach so ganz stupide immer relativ
30:33 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
30:44 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
30:53 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
31:02 schaue einfach in einer tabelle nach das heißt wir benutzen jetzt einen tabelle wo alle diese werde rein
31:10 gespeichert werden das ist jetzt das sogenannte zeitspeicher tausch oder auf englisch time memory trade off wir benutzen jetzt mehr speicher also eine
31:20 extra tabelle wo wir uns zwischen ergebnisse rein speichern um die laufzeit zu verlängern das speicher geht hoch laufzeit geht runter aber die
31:29 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
31:39 bei kürzestem wege suchen von erst nachdem wir konnten uns eigentlich eine tabelle vorher mal irgendwie ausrechnen wo wir
31:47 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
31:57 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
32:07 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
32:17 zerlegung nach memory stand zerlegung wir uns zusätzlich sachen merken und zwar machen wir jetzt uns einig dass b ist inter 3
32:28 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
32:37 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
32:48 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
32:57 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
33:06 wahrscheinlich -1 reinschreiben wenn man weiß dass man auf jeden fall immer einen positiven ertrag hat keine 09 schreiben aber irgendwas wo man ganz
33:17 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
33:26 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
33:37 zweite methode die hauptstadt zerlegung die wir eigentlich arbeit macht der geben wir jetzt also wieder unsere eingabe tabelle wir geben hier wieder
33:46 eine zahl an und begeben java zusätzlich nochmal dieses eray wo jetzt unsere teillösung dänische ausgerechnet haben dringen gespeichert sind und
33:56 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
34:09 - 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
34:17 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
34:27 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
34:33 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
34:40 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
34:49 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
34:59 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
35:09 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
35:22 die frage ist jetzt natürlich wieder was ist die laufzeit davon haben wir die gleiche laufzeit wir vorher bei der repression oder
35:33 sind wir assen tote schneller das ist hier jetzt relativ schwer zu analysieren wir müssen jetzt wieder eine
35:41 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
35:50 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
36:01 methode geben die macht genau die gleiche arbeit wie hier nur halt nicht so mit dieser rezession sondern arbeitet die bottom up
36:10 das was hier jetzt sind diese neuen funktion passiert dass genau das gleiche wie hier es ist nur anders formuliert ist nur anders aufgeschrieben
36:19 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
36:31 ertrags ray machen wo wir unsere teillösungen reinschreiben und ii von null ist natürlich nun
36:42 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
36:55 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
37:08 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
37:18 für den wir vor den rekord aufgestellt haben dass die uns jetzt eben den ertrag gibt und speichern das dann in unserer tabelle
37:27 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
37:38 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
37:49 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
38:01 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
38:09 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
38:20 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
38:31 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
38:39 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
38:49 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
39:01 und damit kann man jetzt hier viel einfacher unsere laufzeit analysieren benutzen immer noch eine tabelle aber wir gehen uns einfach einmal von unten
39:10 nach oben gucken wir uns einmal diesen grafen der teil instanzen an also wir haben teil
39:20 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
39:31 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
39:44 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
39:53 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
40:06 also für eine teil- instanziert müssen wir andere optimale lösungen die wir vorher
40:15 berechnet haben schon mal an stand das hier ist also ein kreis der hat
40:25 +1 knoten und wie viele kannten kanten graf mittäter von knoten haben jede kante ist zwischen zwei knoten also
40:37 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
40:47 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
40:57 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
41:08 addition und damit kommen wir her auf ofen eng vertraut zeit weil wir eben in diesen grafen wovon m ² kanten haben
41:20 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
41:30 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
41:39 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
41:48 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
41:58 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
42:08 hier auch wieder diese addition zählen und stark indes nicht so einfach mit der schleife weil wir hier halt regionen mit schleifen verbinden
42:18 da kommen uns aber trotzdem natürlich auch einfach diese addition wieder so als graf vorstellen und damit die eigenschaften von graphen verwenden um
42:26 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
42:36 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
42:49 was haben jetzt also gemacht wir haben zwei methoden gefunden nochmal die memo stangen zerlegung und die bottom up zustand erlegen die
42:57 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
43:08 nur noch quadratische zeit brauchen statt exponentielle ein quadrat statt zwei wochen und der unterschied zwischen eng quadrat und zwei wochen ist so
43:18 gewaltig dass wenn ihr seid 2 spiel an sagen wir mal erst sehen zwei hoch wer dann schon 1024
43:31 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
43:45 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
43:56 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
44:07 zahlen von innen schon zwischen der laufzeit von einer minute und von jahrtausenden aus was einfach gar nicht mehr machbar ist
44:18 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
44:27 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
44:35 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
44:45 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
44:55 unser ausrechnen dass sie müssen irgendwie jetzt nochmal aus den berechnenden informationen uns diese optimale lösung rekonstruieren
45:05 deswegen erweitern wir jetzt unseren algorithmus ein kleines bisschen so dass man das eben auch noch mal üben die mit speichern
45:15 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
45:25 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
45:36 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
45:46 wir was besseres gefunden haben eine bessere lösung dann setzen wir unser kuh natürlich auf das maximum
45:56 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
46:09 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
46:21 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
46:30 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
46:39 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
46:51 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
47:01 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
47:13 rekonstruieren wenn wir das die zerlegung ausgeben wollen für unser p e und n dann machen wir anfangs einfach diese
47:24 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
47:34 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
47:43 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
47:55 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
48:06 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
48:15 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
48:27 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
48:38 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
48:49 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
48:58 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
49:09 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
49:22 unsere zerlegung wir wollen uns jetzt noch mal ein kleines weiteres beispiel anschauen
49:31 nämlich die sogenannten längsten wege beim längsten wegen wir haben bisher schon kürzeste wege gemacht mit der
49:41 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
49:51 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
50:01 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
50:14 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
50:23 weiter und die sind alle unterschiedlich aber dass k s maximal weil es eben längst weg ist
50:34 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
50:42 charakterisieren gucken wir uns also mein ganz kleines beispiel an wir wollen hier in kürzesten weg von es nachts häfen
50:52 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
51:07 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
51:17 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
51:29 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
51:38 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
51:48 hier jetzt aber ein kleines problem da kürzt der längste einfache weg von es nach dem gibt es zwei möglichkeiten entweder
51:59 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
52:10 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
52:22 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
52:32 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
52:41 einfach wäre das heißt hier können wir jetzt unser dynamisches programm nicht verwenden und tatsächlich wissen wir auch nicht
52:48 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
53:01 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
53:09 finden zwischen zwei knoten der jeden anderen knoten genau einmal besucht und das ist ein klassisches mb schweres problem
53:19 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
53:29 könnte man auch dass hamilton weg problem effizient lösen da ist wenn man davon ausgeht die ungleich mp gibt es hier keine
53:37 effiziente lösung wenn man doch mal eine findet dann hat man mit wenigen problem gelöst
53:44 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
53:55 fest parameter berechenbarkeit oder schnelle exponential zeit algorithmen dass wir uns aber alle sachen die wir in der vorlesung die nicht machen es kommt
54:04 ein fortgeschrittener algorithmen oder man vereinfacht das problem halten zusätzliche restriktionen rein dieses problem leichter machen bis wir eine
54:15 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
54:25 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
54:34 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
54:44 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
54:53 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
55:03 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
55:14 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
55:24 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
55:36 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
55:49 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
56:03 werde es jetzt eben kein längster ästhetik gewesen außerdem gilt das eben die knoten die man sich auf diesen teil streben an
56:13 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
56:24 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
56:33 s class preis also gilt auch unsere beobachtung 2 und wir können hier jetzt ein dynamisches programm anwenden
56:42 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
56:50 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
57:01 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
57:11 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
57:22 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
57:33 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
57:45 gewichts funktion haben man kann das natürlich auch für ungewichtete machen dann sind alle unsere gewichte einfach 1
57:55 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
58:04 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
58:13 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
58:20 gucken können wenn man nicht viel über das problem weiß dann ist das rezessive meistens einfach weil das kümmert sich selber
58:28 darum dass es alles richtigen reihenfolge macht guckt einfach wieder stelle nachweislich hier die lösung schon wenn ich dann berechne ich weiter
58:37 ansonsten cookies danach das hat auch als nachteil dass man wieder mehr speicher braucht wenn man immer noch diese ganze region aufrecht
58:46 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
58:55 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
59:02 wassertiefen suchen vorlesung benutzen das begehen das theologisch durch und dann können wir uns sicher gehen immer wenn wir einen knoten anschauen dann
59:13 haben wir schon alle knoten verarbeitet für diese kann dorthin gibt das ist ja die eigenschaften der topologische sortierung
59:21 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
59:31 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
59:42 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
59:52 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
1:00:01 ausgeben würde so ganz nebenbei die kürzesten wege in kreisfreien grafen die kommen wir jetzt auch zu modellieren also statt da extra
1:00:12 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
1:00:23 algorithmen und man kann damit auch das so genannte t9 problem lösen das kennt es von euch sicherlich keiner mehr aber mein erstes
1:00:33 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
1:00:47 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
1:00:56 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
1:01:06 mal machen so das war's für heute über das dynamische programmieren in dem buch
1:01:15 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
1:01:25 beispiel ketten von matrix multiplikation denkt ihr euch vielleicht ja durch praxisrelevante jetzt kommt damit so was nie matrix multiplikation
1:01:34 braucht man tatsächlich andauernd man sieht's nicht auf den ersten blick aber häufig wenn man irgendwelche
1:01:43 probleme hat auch auf graphen kann man sich diese effizienz matrizen anschauen und muss dann irgendwo mal was multiplizieren
1:01:51 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
1:02:02 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
1:02:12 einfach teil folgen zu finden in zeichenketten asse textpassagen übereinstimmen kann man über den namen skalieren machen
1:02:19 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
1:02:29 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
1:02:40 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
1:02:49 anfragen wo jedes wort mit einer gewissen wahrscheinlichkeit angefragt wird und dann kann man sich für diese
1:02:57 wahrscheinlichkeiten den optimalen zug form berechnen der da eben besser und das wenig zeit braucht
1:03:05 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
1:03:15 algorithmen der praxis ich hoffe das video hat euch gefallen und ich wünsche euch noch einen schönen deshalb auch