Video 3-6: Rekursionsgleichungen

0:04 Jetzt wissen wir, wie wir asymptotische Approximation von Funktionen beschreiben. Also, ich habe da Funktion, die irgendwie kompliziert ist in ihrem Ausdruck und ich interessiere mich vielleicht nicht für den exakten Wert, sondern nur das grobe Wachstum. Dann wissen Sie jetzt, wie das funktioniert. Äh etwas, was auch rein mathematisch ist, aber eben viel in Algorithmen vorkommt, sind rekursiv definierte Folgen, die direkt daherkommen, dass man ein Problem oder ein Algorithmus hat, der auch rekursiv aufgeschrieben ist. Das klassische Beispiel dazu ist dieses dieses Spielpuzzel der Türme von Hannoi. Bevor wir sehr viel Zeit damit verwenden, mal kurz die Frage, wie bekannt das schon ist.

0:51 Was ich mit erklären meine ist insbesondere auch die Lösung, also die systematische Lösung dieses Puzzles. Ich werde es dann auch für alle anderen, es gibt bestimmt ein oder zwei, die es vielleicht noch nie gesehen haben. Ich werde es ganz kurz erklären, was da äh was es damit auf sich hat. Ähm, aber wenn Sie insbesondere den Lösungsalgorithmus schon kennen, dann würde ich da ein bisschen aufs Gas treten.

1:21 Also sieht nach so einer etwa äh bunten Mischung aus. Ähm, also vorab die Enttäuschung, es ist zwar eine schöne Geschichte, da gibt's so eine so eine Mythologie drumrum, äh dass in einem Tempel irgendwo, der in verschiedenen Städten platziert wurde und wahrscheinlich nicht Hanoi gemeint war, von dem der es damals aufgeschrieben hat, ähm eher in Indien äh Mönche Scheiben von A nach Bwegen Und wenn sie damit fertig sind, dann geht die Welt zu Ende oder geht die Welt unter mit einem lauten Knall. Äh, das alles ist eine eine rein erfundene Geschichte von Mathematikern, weil sie das Puzzle schön fanden und die Geschichte irgendwie motivierender. Äh, soll sie aber nicht von dem schönen Puzzle ablenken.

2:12 Also bunte Mischung, also man auch vom Tempo so ein bisschen bunte Mischung. Ich habe mich hier bemüht, das zu malen mit Klötzen, die ich bewegen kann. Also, sie haben ähm im Original 64 solcher bunten Scheiben. Dann wären wir aber definitiv nicht fertig. Dazu später mehr. In dem Beispiel hier sind es vier und ich habe drei Posten, auf die ich die legen kann. Im Original diamantenen Nadeln, aber vielleicht nicht ganz so dramatisch. Ich habe mal Holzpfosten versucht zu malen. Und die Regeln sind einfach. Wir hätten gerne diesen Turm statt hier z.B. auf dem rechtesten äh von diesen Nadeln. Und ich darf aber immer nur einzelne Scheiben bewegen und ich darf zu keiner Zeit eine größere Scheibe auf eine kleinere legen. Also am Anfang kann ich überhaupt nur die oberste bewegen, wenn ich nur eine bewegen darf. Das heiß ich kann muss die runternehmen. Ah, die Scheibe ist schon zerfallen. Das ist schlecht. So, das heißt, ich könnte die hier hinlegen.

3:11 Und äh jetzt habe ich mehr Möglichkeiten. Ich kann die Scheibe wieder weiter bewegen. Das hätte ich aber auch eben schon tun können. Das heißt, cleverer wäre mit der grünen was zu machen. Hier drauf darf ich nicht, das ist verboten. Ich kann sie höchstens hier drüben hinlegen. Und wenn ich mir jetzt anschaue, jetzt kann ich die rote Scheibe nirgends hin bewegen. Alles ist belegt mit kleineren Scheiben. Die grüne Scheibe kann ich höchstens zurücklegen. Also, bleibt mir eigentlich gar nicht viel übrig, als die hier zu bewegen. Jetzt habe ich die Wahl, wo ich sie hinpacke. Ich könnte sie wieder hier zurückpacken oder ich kann sie hier drauf packen. Das ist zielführender. Dann kann ich nämlich jetzt die rote Scheibe bewegen. Ja, und dann können man hier die wieder auf den Ursprungsstapel machen. Dann haben wir uns ein bisschen Platz geschaffen. Dann können wir den grüne hier drauf packen und dann den hier da drauf. Und jetzt kann ich tatsächlich die unterste Scheibe bewegen. Ich kann die blaue nehmen und hier rüber verschieben.

4:05 Und jetzt muss man schon anfangen zu denken, was muss ich jetzt machen? Ich kann wieder nur die kleinste Scheibe bewegen, aber ich kann jetzt eine falsche oder richtige Bewegung machen.

4:17 Ja, kleine nach rechts. Dann geht die grüne hierhin, die kleine oben drauf und die rote ans Ziel und die lilane hier rüber und die grüne an den Rand. Okay, ich werde schon schlampig. Das heißt, das sollte langsam zu Ende gehen. Gut, geschafft.

4:41 Gut, das ist Türme von Hannoi. Ähm, wenn man das so macht, kriegt man das schon so hin mit den paar Scheiben. Und wenn man ein bisschen drüber nachdenkt, ist auch nicht so schrecklich schwierig. Es gibt nur immer wieder diesen Punkt, wo ich die kleinste Scheibe bewegen muss und da habe ich immer die Auswahl. Wenn ich den falschen Pfosten wähle, dann habe ich am Ende den anderen, den untersten von dem, den ich Turm, den ich beschieben will, auf dem falschen, dann müsste ich es alles noch mal rückgängig machen. Kann man drüber nachdenken und das vermeiden. Es gibt aber einen wunderschönen rekursiven Algorithmus, der völliges Denken vermeidet. Und äh gerade in der Theorie sind wir oft manchmal ein bisschen denkfaul, wenn sich es denn einrichten lässt. Der rekursive Algorithmus ist hier beschrieben. Im Allgemeinen muss der von verschiedenen Pfosten zu anderen Pfosten formuliert sein. Das heißt, es gibt hier immer einen der drei Stäbe. Das ist die Quelle.

5:37 Ein anderer Stab ist die das Ziel und der dritte, der noch übrig bleibt, ist der Puffer. Das ist der Stab, den ich zur Verfügung habe, um Plötze zu parken zwischenzeitlich. Und dann gibt's noch N. Das ist die Anzahl äh von Klötzen, die ich jetzt bewegen will. Ziel von diesem von dieser Prozedur ist die obersten N Stücke, die aktuell in S liegen, nach T zu verfrachten.

6:06 In Klammer auf, dabei verwenden wir dann diesen Pufferstock B als Zwischenspeicher und ähm danach ist die Prozedur zu Ende. Das heißt, das Gesamtproblem ist in unserer Formulierung von oben ts auch paar neu von habe ich den Dingern Namen gegeben, sagen wir von 1 nach 3. Also ich will von 1 nach 3. Als Puffer nehme ich zwei. Na ja, und am Anfang alle Klötze oder in unserem Beispiel waren das eben vier, nicht? Äh, also entweder n oder Beis in unserem Beispiel waren das vier Stück. So würde ich das aufrufen, um das eigentliche Problem zu lösen. Das ist aber eine rekursive Prozedur, die sagt, entweder bin ich schon fertig, ich muss gar nichts bewegen, oder ich bewege die obersten n-1 Scheiben auf den Puffer, dann habe ich Platz, um die unterste Scheibe, die Ente Scheibe vom Start zum Ziel zu bewegen und dann muss ich nur den anderen Turm wieder zurückschieben.

7:13 Das elegante an der rekursieren Formulierung ist, ich muss nicht drüber nachdenken, wann muss ich welche die kleine Scheibe auf welchen der Stöcke legen. Das ergibt sich automatisch durch die Rekursion.

7:24 Okay, der Algorithmus ist nett. Worauf ich eigentlich hinaus will, ist wie lange dauert das denn? Die ursprüngliche Geschichte mit den Mönchen war, es gibt diese Diamantnadeln mit massiven Goldscheiben, aber 64 davon. Und die Frage ist, wie lange haben wir denn noch, bis die Welt untergeht?

7:50 Okay, dem wollen wir uns ähm mit Hilfe der Rekursionsgleichung äh annähren. Ähm es gibt ja noch so eine ganz hübsche Animation, die überspringe ich jetzt mal. Können Sie sich in Ruhe selber angucken, wenn Sie mögen. Also, wie lange braucht der Code? Dafür müssen wir sagen, was unser unser Kostenmaß ist. Was was zählen wir hier? Äh, das das hängt jetzt ein bisschen dran, wie lange diese Mönche brauchen, diese Goldscheiben rumzuwurten. Aber sagen wir mal, was uns interessiert ist, wie viele Scheiben wir bewegen. Und die Umrechnung in Zeiteinheiten ist dann, wie Sie sehen, werden relativ egal. Also, wir bewegen äh die Anzahl Bewegungen von Scheiben ist das, was zählt und nur Zeile sech im Code macht das. Alles andere ist nur administrativer ähm rekursiver Aufruf und so weiter.

8:37 Das heißt, wir ähm können uns anschauen, wie oft wir diese Zeile sechs erreichen. Dann haben wir die Gesamtzeit abgeschätzt. Das wird aber davon abhängen, welcher Parameter n hier gewählt ist, wie viele Scheiben ich bewegen muss. Für n = 0 muss ich gar nichts tun, da ist der Aufwand 0. Für jedes größere N mache ich diese rekursiven Aufrufe und dann eine Bewegung in der Mitte. Das heißt, ich habe zweimal die Bewegung für n - 1 und eine zusätzliche Bewegung. Und das kann man als Rekursionsgleichung aufschreiben, um genau diesen diesen Sachverhalt abzubilden.

9:17 Also formal ist t von n die Anzahl Bewegung in Scheiben, damit wir eine Notation haben. Dann ist t von 0, das war der erste Teil gleich 0, keine Bewegung und t von n ist eben 2 x tn - 1 + eine extra Bewegung in der Mitte. Okay, das ist so die übliche Art, wie man das aufschreibt. Man gibt eine Anfangsbedingung an für einen kleinen Wert, wo es eine feste Anzahl, feste Kosten gibt. Und für einen rekursiven Algorithmus haben wir dann für bestimmte größere Eingaben, beliebig große Eingaben, eine Beschreibung der Kosten in Abhängigkeit der Kosten für kleinere Eingaben.

10:01 Aber das sagt uns jetzt nicht so richtig, wie teuer das ist. Da könnte man jetzt für 64 noch anfangen, das einzusetzen und dann können Sie das schon ausrechnen. Aber wir wollen das ja wie die Profis asymptotisch machen.

10:15 Also versuchen wir die mal ähm komplett in eine explizite Darstellung zu überführen. Hier noch mal die Rekursion von eben. Und was ich Ihnen versuche auf einer Folie zu zeigen, ist ein ein Rezept, mit dem man oft diese Dinger lösen kann. Da gibt's einen kreativen Schritt in der Mitte, den man nicht im Allgemeinen hinkriegt. Ist auch quasi beweisbar unmöglich, dass das immer geht, aber oft geht's eben oder für die Beispiele, die Sie in der Klausur kriegen werden, geht's auf jeden Fall. Erster Schritt ist oft mal für ein paar kleine Werte einsetzen, was der was das Ergebnis ist. Manchmal riecht man dann schon das Muster. Äh, das habe ich hier auch mal gemacht. Also, der Anfang ist ja schon gegeben. Für n = 1 habe ich zweimal den vorherigen Wert + 1, das ergibt 1. Dann für n = 2 hab man zweimal den vorherigen Wert + 1. 2 x 1 + 1= 3 und so weiter und so fort.

11:09 Wenn Sie so ein bisschen da drauf schielen, dann fällt Ihnen vielleicht schon auf, dass ist immer eins weniger als eine zweierpotenz. Aber wir tun mal so, als wären wir ein bisschen betriebsblind oder die Rekursion ein bisschen komplizierter. Der zweite Schritt ist, wir raten die Lösung. Na gut, ähm soweit so äh nutzlos als Ratschlag. Aber was eben oft hilft, ist die Rekursion in sich selbst einsetzen. Ich habe eine Darstellung für TN, für große N. Die kann ich erstmal hier einsetzen und dann mache ich das noch mal. für tn - 1, wenn n- 2 ist, kann ich noch mal die gleiche ähm Entsprechung einsetzen. Also, ich habe hier zweimal und dann das ganze Ding.

11:55 Dann ma ich das vielleicht noch mal. Ähm, woher vereinfachen wir ein bisschen die 2 hier? Ich mich multipliziere aus. Das heiß, ich habe 2 hoch 2 mal das t von n - 2 und hier hinten die 1 war von Anfang und dann habe ich zweimal die 1 hier aufgesammelt. Jetzt setzen wir das noch mal ein und dann kriegt man das gleiche. Ich habe hier eine Potenz von der 2, die sozusagen zusammen mit dem ähm Abzug hier von n größer wird. Und hier außen sammle ich zweier Potenzen. Ich fange mit ein an, dann mit 2, dann mit 2 x 2 und so weiter. Und an der Stelle kann man jetzt vielleicht äh das Muster besser erkennen. Wie lange muss ich das machen? Na ja, so lange bis hier meine Anfangsbedingung erreicht ist. Ich also das Muster in genau dieser Weise noch ein paar mal fortsetze. Irgendwann bin ich hier bei t0 und dann muss ich aufhören. Dann gilt erstens dieser rechte Teil auch gar nicht mehr. Aber ich weiß vor allem auch schon, was das Ergebnis von t0 ist. Das heißt für für den Teil, das ist ja einfach 0. Ja, t von 0 ist 0 mal 2 ho n.

13:02 Was also übrig bleibt, ist diese Summe der ersten n - 1 zweier Potenzen. Das kann ich natürlich auch als Summe schreiben und dann wissen Sie vielleicht die so die zweierpotenzen aufsummiert ergibt die nächst größere zweierpotenz -1. Ansonsten gibt's natürlich das TCS Sheet, wo das drauf steht oder sie haben direkt geraten. Der Punkt ist soweit so gut ist das kein formaler Beweis. Das sieht zwar sehr plausibel aus, aber wir hätten manchmal gerne hundertprozentige Gewissheit, ob wir denn auch richtig geraten haben und überall zwischendrin gerade hier diese Schritte da, diesen der Kernschritt ist hier den die Verallgemeinerung zu sehen, da macht man manchmal auch Fehler. Also wollen wir diese Lösung ähm, die wir da geraten haben, noch verifizieren. Also formal als Lämmer aufgeschrieben. Lösung dieser Rekursion ist eben 2 hoch n - 1.

14:04 Und beweisen können wir das immer ganz einfach und ohne viel zu denken, aber mit hinterher der Gewissheit, dass auch stimmt, wenn die Rechnung durchgeht per Induktion.

14:15 Induktion hätte ich vielleicht auch eine Frage machen sollen, wie sehr das noch bekannt ist. Ich zeige Ihnen einfach dieses eine Beispiel in voller Zoomstufe und sie werden auch noch Gelegenheit haben hier bei den anderen Modulen das äh ausreichend zu üben. Dann reicht das hoffentlich. Äh was ich nicht aufgeschrieben habe, ist warum das dann ein korrekten Beweis liefert. Induktion besteht immer aus drei Teilen im Induktionsanfang, der Induktionsvoraussetzung und dann im Induktionsschritt. Die Induktionsan der Induktionsanfang ist die der kleinste Wert von n. Dieses Lemmer hier ist ja ähm eigentlich eine Kurzform von für alle n in n0.

14:57 Das ist was das was das Lemmer meint, ähm ohne es zu sagen, weil TN genau für diese definiert ist. Und solche Aussagen, die über gan über natürlichen Zahlen allquantifiziert sind, also für alle natürlichen Zahlen gilt dieses und jenes, kann man per Induktion beweisen. Und wir fangen mit der kleinsten Zahl an, für die die Aussage gemacht ist. T von 0. T von 0 ist 0 nach der Anfangsbedingung und das ist auch der Wert, den ich bekomme, wenn ich unsere geradene geschlossene Darstellung einsetze. Also stimmt der Induktionsanfang Haken dran.

15:37 Dann formulieren wir allgemein eine Induktionsvoraussetzung. Also angenommen, ich habe schon bewiesen, für alle n str bis zu einem gewissen n ist das korrekt. mein meine geratene geschlossen Darstellung entspricht dem Wert der Rekursionsgleichung.

15:56 Dann machen wir den Induktionsschritt, indem wir das n ein größer machen. Das heißt, wir versuchen zu zeigen, wenn die Induktionsvoraussetzung gilt für ein n, dann können wir daraus herleiten, dass sie auch für n + 1 gilt. Und ähm in der Praxis für solche Rekursionen ist es immer einfach nachrechnen und gucken, dass es passt. Wir fangen mit tn + 1 an. Am Ende hätten wir gerne, dass da dann steht 2 hoch n + 1 - 1. Das ist die geschlossene Darstellung, die wir gerne hier sehen würden. Das wissen wir aber noch nicht. Das wollen wir beweisen. Deswegen das Ausruzeichen. Was wir wissen ist, dass hier n + 1 mindestens 1. Ich darf also meine rekursive Darstellung für die Rekursion einsetzen. 2 x t von n + 1. Und jetzt ist hier das n klein genug, damit die Induktionsvoraussetzung äh schon gilt oder schon hier anwendbar ist. Das heißt, mit der Induktionsvoraussetzung kann ich hier jetzt das TN ersetzen durch unsere geschlossene Darstellung.

17:03 Und dann muss ich nur ausrechnen, dass es dann einmal ausmultipliziert und dann vereinfacht genau die Form, die wir wollten, nämlich unsere geschlossene Darstellung für ein ein größeres N.

17:17 Und das ist dann auch alles. Das ist der formale Beweis, dass unser rein geratene geschlossene Darstellung auch wirklich das Richtige tut. Je nachdem, wie man zu dieser Lösung kommt, kann man manchmal sich den Intutionsbeweis sparen, aber oft ist der schnell genug gemacht, s dass die schnellste Variante solche Rekursion zu lösen ist mit irgendeiner Methode, irgendjemand hat ihn zugeflüstert, probier mal diese Lösung und dann einfach nachrechnen, ob es äh im Induktionsschritt funktioniert.

17:48 Äh liefert Ihnen dann die Antwort. Was heißt das jetzt für unsere Türme von Hanneu? Das heißt, wir wissen für 64 die Anzahl Bewegung ist 2 hoch 64 - 1. Das ist eine riesige Zahl. Äh, mindestens 6. 2 hoch 10 ist etwa 1000. Das heißt, es ist schon äh eine große Zahl, die schon gar keinen schönen Namen mehr hat. Bor ich jetzt was falsches sage, aber es ist etwa 10 hoch 18, nicht? Also noch deutlich größer, aber so von der groben Größenordnung. Äh das wird also nicht fertig werden bzw. w wir alle erleben es nicht mehr, dass diese dass die Welt zu Ende geht, weil die Türme von Hannoi fertig sind.