Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Dynamische Programmierung und Greedy - Grundlagen
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 49 Zeilen
- haye ist sarah hier heute erzähle ich euch etwas zur dynamischen programmierung und kreativ erfahren wann wir diese anwenden und was das überhaupt
- ist fangen wir an mit der dynamischen programmierung der ursprung von der dynamischen programmierung liegt in die
- wartung conquer das kennt ihr vielleicht von verfahren wie zum beispiel dem merger sword im prinzip haben wir mehrere schritte am anfang haben wir
- unser problem in unabhängige teilproblem anschließend lösen wir diese probleme und im letzten schritt setzen wir unsere teillösungen wieder zusammen und haben
- daraus unsere gesamt problem gelöst der unterschied zwischen der dynamischen programmierung und die weithin konkret sieht wie folgt aus
- bei die weiteren konkret würden wir identische probleme immer und immer wieder lösen bedeutet wenn wir das gleiche problem zehnmal haben dann
- würden wir es zehnmal lösen bei den dynamischen programmierungen müssten wir was die lösung von diesem teil problem ist werden sie einmal berechnen und
- anschließend wieder verwenden das bedeutet wenn wir viele identische probleme haben dann ist die dynamischen programmierung besser als die weitere
- konter aber für was für eine art probleme eignet sich dem dynamische programmierung überhaupt das sind so genannte optimierungs problem das
- bedeutet wir haben probleme bei denen wir zum beispiel ein minimum maximum finden möchten beispiele dafür wäre zum beispiel die
- matrix ketten multiplikation oder wenn wir eine gemeinde die längste gemeinsame teil folge von zwei strings zum beispiel finden wollen würden das wären probleme
- die man sehr gut mit der dynamischen programmierung lösen kann vor allem ist ein problem gut mit der dynamischen programmierens lösen bei
- denen wir viele abhängige teil probleme haben so wie ich eben schon erklärt habe merken wir uns nämlich diese probleme können sie immer und wieder
- wiederverwenden und eben genau das ist die grundidee wir speichern die lösung von problemen dafür können wir zum beispiel tabellen
- verwenden identische probleme müssen so nicht doppelt gelöst werden woraus folgt dass wir eine laufzeit verbesserungen haben und diese laufzeit verbesserung
- ist nicht zu unterschätzen wenn wir vorher ein problem haben dass wir eine exponentielle laufzeit lösen müssten was unfassbar schlecht ist wie ein computer
- das problem kann bedürftigen schon programmierungen nun im polynja laufzeit lösen war es wiederum super für den computer ist aber wie gehen wir vor
- wenn wir ein problem mittels der dynamischen programmierung lösen möchten wir haben insgesamt vier schritte im ersten schritt überlegen wir uns was
- denn die struktur einer optimalen lösung ist im zweiten schritt überlegen wir uns eine rezensions gleichung im dritten schritt brächte wir den wert einer
- optimalen lösung spricht das minimum oder das maximum wenn wir beispielsweise einen weg von a nach b berechnen möchten dann würde uns
- dieser schritt sagen die strecke ist beispielsweise 200 kilometer lang wenn wir den kürzesten weg finden wollen die kürzeste weg sind 200 kilometer
- der vierte schritt er würde dann einer optimalen müssen konstruieren das wäre dann sozusagen aus unserem vorherigen erkenntnissen würden wir hingehen uns
- dann wirklich diese route überlegen beziehungsweise würden diese gute nachvollziehen und dann zum beispiel mit unserem navigationssystem eben von a
- nach b kommen innerhalb dieser 200 kilometer der vierte schritt kann beispielsweise aufgefallen wenn die ja weg dann aber
- gar nicht interessant ist unbeweglich nun herausfinden möchten was ist dann sozusagen unsere minimale router oder unsere minimale distanz von punkt a zu b
- so jetzt habe ich euch die grundlagen zur dynamischen programmierung erklärt und möchte im folgenden etwas auf glee die eingehen wann und wofür verwenden
- überhaupt rudi wie die ist genauso wie die dynamische programmierungen ein verfahren mit denen wir optimierungs probleme lösen können
- das bedeutet wir wollen wieder ein minimum oder im maximum finden im allgemeinen kann man sagen dass algorithmen bei den begriff verwenden
- eine kürzere laufzeit haben als die all gruppen mit der dynamischen programmierung allerdings haben wie verfahren auch ein
- nachteil sie haben nämlich höhere anforderungen an das problem zumindest wenn man die probleme optimal lösen möchte bei credit gehen wir nämlich volk
- vor wir lösen teil probleme lokal das bedeutet wir nehmen die lösung die uns zu einem gewissen zeitpunkt am besten erscheint ohne das globale wissen
- bedeutet wir schauen uns nicht jede mögliche lösung an das bedeutet wir treffen zuerst eine entscheidung und werden unser
- teilproblem erst danach bei den dynamischen programmierung ist das genau andersherum die kritik können wir so uns lösungen
- annähernd für np hatte probleme können diese probleme aber immer noch nicht optimal lösen so nun überlegen wir uns wann wir eine optimale lösung erhalten
- wenn wir die diebe nutzen und zwar haben wir da im prinzip zwei voraussetzungen und zwar brauchen wir bei credit einmal die teilproblem eigenschaft die muss
- erfüllt sein das bedeutet sozusagen das werden wir unsere teilproblem optimal lösen dann haben wir unser gesamtproblem auch
- optimal gelöst sprich die zusammengesetzten teil problemlösung ergeben unsere lösung für das gesamtproblem dass es die teilproblem
- eigenschaft und die wie die eigenschaft besagt dass wir dies sehr ähnlich dass wir die lokal gelösten teil probleme optimal lösen
- das bedeutet dass wir auch wenn wir kein globales wissen über unsere teil probleme haben dass wir sie trotzdem lokal optimal lösen können
- das erfüllt es dann kriegen wir mit kuli eine optimale lösung die dynamische programmierung ist etwas einfacher
- bei der brauch wir nur die teilproblem eigenschaft das bedeutet wenn die erfüllt es dann die von uns die dynamische programmierung eben eine
- optimale lösung wie gesagt der nachteil hierbei ist dass die dynamische programmierung in der regel länger braucht als greely verfahren
- zusammengefasst wann also verwenden the greedy und wann die dynamische programmierung wie verwenden wir genau dann wenn die grün die eigenschaft
- erfüllt ist oder wie möglichst schnell zu einer lösung kommen möchten zum beispiel bei einem mp hat ein problem und die optimale lösung zweitrangig es
- spricht wir wollen nur eine annäherung und nicht das genaue ergebnis die dynamische programmierung verwenden wir genau dann falls wir eine optimale
- lösung erzielen möchten und uns die laufzeit erst mal egal ist oder zweitrangig das waren so die wichtigsten punkte zur dynamischen programmierung
- und sowie die wissen und wann er welches verfahren verwenden sollte ich hoffe das video hat euch gefallen in zukunft werde ich nochmal darauf
- eingehen welche probleme man mit den jeweiligen verfahren zu lösen kann wer da einige beispiele geben und die mal von vorn bis hinten zeigen wie das ganze
- funktioniert wenn ihr fragen habt dann schreibt die gerne in die kommentare und ja wir hören uns wieder
Zum Nachlesen
Dynamische ProgrammierungDynamische Programmierung ist eine Methode zum algorithmischen Lösen eines Optimierungsproblems durch Aufteilung in Teilprobleme und systematische …
InformatikAls einfache Rechengeräte leisteten Abakus und später der Rechenschieber unschätzbare Dienste. 1641 konstruierte Blaise Pascal eine mechanische …
CodeIn der Kodierungstheorie nennt man die Elemente, aus denen ein Code besteht, „Codewörter“, die Symbole, aus denen die Codewörter bestehen, bilden ein „Alphabet“ …
Theoretische InformatikIhre Inhalte sind die Automatentheorie, die Theorie der formalen Sprachen, die Berechenbarkeits- und Komplexitätstheorie, aber auch die Logik und formale …