WEBVTT

00:08.220 --> 00:13.220
Okay, dann begrüße ich Sie jetzt recht herzlich zur zweiten Vorlesung

00:13.220 --> 00:17.520
über Repräsentation von Folgen.

00:20.660 --> 00:25.260
Wir haben beim letzten Mal gelernt, wie man Kippus flechtet,

00:25.960 --> 00:30.140
allerdings auf eine etwas neuartige Art und Weise, nämlich mit

00:30.140 --> 00:31.580
verketteten Listen.

00:33.200 --> 00:37.680
Wir haben uns insbesondere mit doppeltverketteten Listen beschäftigt,

00:38.300 --> 00:43.400
wo also sogenannte List-Items Vorwärts- und Rückwärtszeiger enthalten

00:43.400 --> 00:45.020
auf Vorgänger und Nachfolger.

00:45.880 --> 00:50.160
Damit das auch wirklich konsistent, durchgängig funktioniert, haben

00:50.160 --> 00:55.520
wir so ein Dummy-Item eingefügt, das dann Vorgänger des ersten und

00:55.520 --> 00:59.360
Nachfolger des letzten richtigen Listen-Items ist.

00:59.360 --> 01:04.540
Und damit war es dann sehr leicht möglich, eine Listenklasse zu

01:04.540 --> 01:07.780
definieren, wo die meisten Funktionen Einzeiler sind.

01:09.360 --> 01:15.960
Es gab dann einen Achtzeiler-Splice, der eine Teilliste rausschneidet

01:15.960 --> 01:20.480
aus einer Liste und an einer anderen Stelle möglicherweise in einer

01:20.480 --> 01:22.780
anderen Liste wieder einsetzt.

01:22.780 --> 01:29.580
Und daraus konnten wir dann sehr einfach Verschiebe-Operationen von

01:29.580 --> 01:31.020
List -Items ableiten.

01:32.640 --> 01:35.740
Für Einfügen und Löschen brauchten wir zusätzlich eine

01:35.740 --> 01:36.720
Speicherverwaltung.

01:37.820 --> 01:40.800
Da hatte ich noch eine längere Diskussion mit einem ihrer

01:40.800 --> 01:45.320
Kommilitonen, der noch einmal darauf hingewiesen hat, dass man

01:45.320 --> 01:49.620
natürlich unterscheiden muss zwischen Speicherverwaltung von Sprachen

01:49.620 --> 01:55.640
wie C und C++, wo man explizit Speicher anfordern und auch wieder

01:55.640 --> 02:02.340
freigeben muss, und Sprachen wie Java, wo die Speicherfreigabe

02:02.340 --> 02:05.500
automatisch durch eine Garbage Collection erledigt wird.

02:07.940 --> 02:10.420
Ich bin jetzt kein Java-Experte.

02:12.320 --> 02:15.320
Ich könnte mir tatsächlich vorstellen, dass die Java

02:15.320 --> 02:21.120
-Speicherverwaltung eher dahingehend optimiert ist, viele kleine

02:21.120 --> 02:24.320
Objekte einigermaßen vernünftig zu verwalten.

02:26.440 --> 02:34.000
Und man würde möglicherweise davon absehen, diese Freelist-Lösung zu

02:34.000 --> 02:35.820
wählen, die ich hier vorgestellt habe.

02:37.800 --> 02:40.600
Trotzdem ist das, denke ich, sinnvoll auch zu kennen.

02:40.920 --> 02:45.960
Ich behaupte weiterhin, dass für viele Anwendungen diese Variante mit

02:45.960 --> 02:48.900
der Freelist deutlich effizienter sein wird, als sich auf die Java

02:48.900 --> 02:51.080
-Speicherverwaltung zu verlassen.

02:56.710 --> 03:02.670
Genau, dieses Teillisten-Manipulieren mittels Splice kann man dann zum

03:02.670 --> 03:05.090
Beispiel auch zum Konkatenieren von Listen verwenden.

03:05.090 --> 03:10.550
Wir hatten dann noch einen Dirty-Trick kennengelernt, wie man das

03:10.550 --> 03:17.270
eigentlich nicht benötigte Nutzlast-Element des Dummy-Headers

03:17.270 --> 03:23.050
verwenden kann als Wächter-Element beim Suchen von Daten.

03:24.710 --> 03:28.490
Das war aber jetzt im Wesentlichen eine Möglichkeit, ein Beispiel

03:28.490 --> 03:30.230
vorzustellen für Wächter-Elemente.

03:35.230 --> 03:39.690
Ich bin dann noch auf ein anderes Design-Problem bei

03:39.690 --> 03:45.430
wiederverwendbaren Datenstrukturen eingegangen, dass man nämlich einen

03:45.430 --> 03:48.110
Trade -off hat zwischen Funktionalität und Effizienz.

03:48.110 --> 03:54.570
Zum Beispiel war es so, dass man einen Listendatentyp relativ leicht

03:54.570 --> 04:01.730
anreichern kann durch einen Member, das die jeweilige Größe speichert,

04:02.210 --> 04:09.630
man dann aber Probleme mit diesen Splice-Operationen kriegt, die

04:09.630 --> 04:13.990
beliebige Teillisten manipulieren, deren Größe man a priori nicht

04:13.990 --> 04:14.390
kennt.

04:14.390 --> 04:17.450
Und dann muss man sich überlegen, soll jetzt das Size effizient

04:17.450 --> 04:21.350
unterstützt werden oder dieses Splice oder was mache ich da?

04:21.850 --> 04:27.790
Und das war ein Beispiel dafür, dass man die ultimate Implementierung

04:27.790 --> 04:30.770
einer Datenstruktur nicht finden wird, sondern dass man immer schauen

04:30.770 --> 04:34.650
muss, welche Funktionalität brauche ich und wie kann ich die effizient

04:34.650 --> 04:35.270
unterstützen.

04:42.080 --> 04:46.340
Dann haben wir als Variante von verketteten Listen die einfach

04:46.340 --> 04:51.760
verketteten Listen kennengelernt, die ein bisschen einfacher sind,

04:51.840 --> 04:55.660
weniger Platz brauchen, aber eben nicht alle Operationen effizient

04:55.660 --> 04:56.260
unterstützen.

04:56.480 --> 05:02.160
Insbesondere das Delete ist da so nicht unterstützt.

05:04.660 --> 05:09.940
Es gab dann einen Trick, wie man zumindest das Einfügen am Ende, also

05:09.940 --> 05:17.060
Pushback unterstützen kann, indem man mit dem Listenobjekt zusätzlich

05:17.060 --> 05:21.060
ein Member speichert, das auf das letzte List-Item verweist.

05:23.300 --> 05:29.580
Gibt es noch Fragen zu verketteten Listen, die vielleicht während der

05:29.580 --> 05:32.720
letzten beiden Tage aufgekommen sind?

05:34.060 --> 05:38.520
Dann machen wir jetzt weiter mit Arrays.

05:41.000 --> 05:46.780
Im Prinzip kennen Sie Arrays aus... ja, die meisten

05:46.780 --> 05:50.260
Programmiersprachen haben Arrays, Java hat Arrays, C hat Arrays.

05:51.360 --> 05:55.440
Die eingebauten Datenstrukturen sind aber im Allgemeinen beschränkte

05:55.440 --> 05:59.200
Felder, das heißt ich muss bei der Erzeugung schon angeben, wie groß

05:59.200 --> 06:01.820
die sind und kann nachträglich die Größe nicht mehr ändern.

06:02.720 --> 06:06.500
Und wir wollen jetzt besprechen, wie man unbeschränkte Felder oder

06:06.500 --> 06:12.360
Unbounded Arrays definiert, die zusätzlich die Operationen Pushback

06:12.360 --> 06:13.540
und Popback unterstützen.

06:13.860 --> 06:17.660
Wo ich also am Ende ein Element anfügen kann oder das letzte Element

06:17.660 --> 06:23.080
entfernen kann und die dann logischerweise auch die Operation Size,

06:23.600 --> 06:26.040
also Größe, unterstützen sollen.

06:27.080 --> 06:29.560
Und das Ganze soll natürlich effizient sein.

06:33.850 --> 06:38.330
Anwendungen, ja es gibt eigentlich sehr viele, also in C und ich

06:38.330 --> 06:41.710
glaube auch in Java, in C++ und Java heißen die jeweils Vector.

06:42.570 --> 06:50.650
Das sind die mit die am meisten gebrauchten Datenstrukturklassen, die

06:50.650 --> 06:52.230
man so sieht in Anwendungen.

06:54.130 --> 06:58.970
Und der Grund, warum ich Ihnen das hier vorstelle, ist zweifach.

06:59.070 --> 07:03.930
Zum einen ist es natürlich interessant zu sehen, wie eine der am

07:03.930 --> 07:07.610
weitesten verbreiteten Datenstrukturen überhaupt implementiert werden,

07:08.090 --> 07:09.730
warum man das so und nicht anders macht.

07:10.450 --> 07:14.330
Und wir werden insbesondere eine wichtige Entwurfs- und Analysetechnik

07:14.330 --> 07:18.450
kennenlernen an diesem Beispiel, nämlich amortisierte Analyse.

07:21.330 --> 07:24.990
Um jetzt mal konkrete Beispiele zu nennen, stellen Sie sich vor, Sie

07:24.990 --> 07:30.370
haben eine Datei mit Daten, zum Beispiel, da stehen die Kanten eines

07:30.370 --> 07:31.010
Graphen drin.

07:33.430 --> 07:36.870
Aber Sie wissen nicht, wie viele Zeilen, sagen wir mal immer eine

07:36.870 --> 07:37.850
Zeile, eine Kante.

07:38.210 --> 07:40.910
Sie wissen aber nicht, wie viele Zeilen da drin sind, es ist halt

07:40.910 --> 07:42.570
einfach eine unstrukturierte Datei.

07:43.030 --> 07:46.030
Dann lesen Sie das nach und nach ein und wollen das eben in eine

07:46.030 --> 07:49.790
interne Datenstruktur, in ein Array einfügen, mit dem Sie dann später

07:49.790 --> 07:50.630
arbeiten können.

07:51.030 --> 07:55.350
Dann ist es halt am komfortabelsten, so eine Vektorklasse zu

07:55.350 --> 07:58.650
verwenden, wo man dann nach und nach die Zeilen einfach reinschreibt.

08:00.990 --> 08:06.470
Wir werden weitere Beispiele sehen, wo wir zum Beispiel einen Stapel

08:06.470 --> 08:10.690
brauchen oder eine Warteschlange, wo man die Länge auch nicht kennt.

08:13.210 --> 08:18.370
Prioritätslisten und viele andere Datenstrukturen, wo man eine Menge

08:18.370 --> 08:22.590
von Objekten verwaltet, aber a priori nicht weiß, wie viele das sein

08:22.590 --> 08:22.870
können.

08:28.320 --> 08:32.120
Die Idee ist, wir machen das gleiche wie bei beschränkten Feldern.

08:32.600 --> 08:35.880
Wie werden überhaupt beschränkte Felder auf unserem Maschinenmodell

08:35.880 --> 08:36.460
abgebildet?

08:36.460 --> 08:38.740
Naja, so ein Array ist ein Stück Hauptspeicher.

08:39.520 --> 08:45.000
Das fängt an einer bestimmten Stelle an und nimmt dann so viel Platz

08:45.000 --> 08:46.760
ein, wie die Elemente halt brauchen.

08:46.960 --> 08:49.900
Also Größe des Elements mal Anzahl Elemente.

08:53.300 --> 08:56.200
Die Idee bei einem Pushback wäre dann, naja, dann hänge ich das

08:56.200 --> 08:59.300
Element halt ans Ende an und vergrößere die Größe.

09:00.220 --> 09:05.060
Und jetzt ist natürlich der Trick, kann ja sein, dass kein Platz dafür

09:05.060 --> 09:10.780
da ist, dass hinter dem letzten Element des Momentan-Arrays irgendein

09:10.780 --> 09:13.220
anderes wichtiges Datenobjekt steht.

09:15.200 --> 09:19.900
Dann muss mein Array halt umkopiert werden, irgendwo anders hin und

09:19.900 --> 09:21.980
dort größer neu angelegt werden.

09:22.670 --> 09:24.340
Und das werden wir implementieren.

09:25.380 --> 09:29.980
Genauso Popback wir verringern, das ist ein Size-Member.

09:30.740 --> 09:35.220
Und was wir da dann allerdings machen ist, wenn wir dann zu viel Platz

09:35.220 --> 09:38.860
verbrauchen, dann wird auch wieder umkopiert und geschrumpft.

09:40.580 --> 09:47.400
Es ist übrigens so, dass in C++ in der Standard-Template-Library die

09:47.400 --> 09:52.580
Vektorklasse dort, die wächst bei Pushback, aber die schrumpft bei

09:52.580 --> 09:53.340
Popback nicht.

09:54.320 --> 09:56.160
Weiß jemand, wie das bei Java ist?

09:57.840 --> 10:01.380
Also insofern lernen wir hier auch schon eine fortgeschrittenere

10:01.380 --> 10:06.060
Datenstruktur kennen, als das, was in der C++ Standard-Template

10:06.060 --> 10:07.980
-Library tatsächlich implementiert ist.

10:10.740 --> 10:15.580
So, also dieses Konzept ist jetzt nicht so kompliziert.

10:17.560 --> 10:22.000
Und der naheliegendste Ansatz wäre jetzt zu sagen, naja, wir sorgen

10:22.000 --> 10:25.000
halt dafür, dass immer genau der passende Platzverbrauch da ist.

10:25.620 --> 10:28.360
Aber stellen Sie sich vor, Sie haben jetzt eine sehr typische

10:28.360 --> 10:33.460
Anwendung, wo Sie n Pushback-Operationen nacheinander durchführen.

10:33.460 --> 10:38.260
Zum Beispiel eben diese n Zeilen einer Datei in Ihren Vektor einfügen.

10:38.620 --> 10:42.580
Dann wird mit jeder Operation das komplette Array umkopiert.

10:43.440 --> 10:46.680
Das heißt, die Laufzeit ist irgendwie sowas Summe i gleich eins bis n

10:46.680 --> 10:47.000
i.

10:47.600 --> 10:49.740
Das ist Theta n Quadrat.

10:50.600 --> 10:54.500
Also Sie haben hier eine Datenstruktur, deren Implementierung

10:54.500 --> 10:58.540
quadratische Laufzeit braucht, um so ein Array aufzubauen.

10:58.540 --> 11:02.380
Das ist eine Katastrophe, wenn das Array zum Beispiel eine Milliarde

11:02.380 --> 11:03.380
Elemente enthält.

11:03.500 --> 11:06.540
Ja, dann wird Ihr Rechner ganz schnell stehen.

11:08.080 --> 11:09.560
Und geht das schneller?

11:10.100 --> 11:10.640
Fragezeichen.

11:10.900 --> 11:14.560
Natürlich geht das schneller, aber wir werden jetzt sehen, wie.

11:15.860 --> 11:16.040
So.

11:18.660 --> 11:20.760
Hier ist jetzt unsere Klassendeklaration.

11:22.780 --> 11:24.580
U-Array ist halt unbounded Array.

11:24.580 --> 11:30.880
Das ist wieder eine generische Klasse mit dem Typ Parameter Element.

11:31.760 --> 11:33.700
Wir haben zwei numerische Members.

11:34.460 --> 11:39.580
W ist die allozierte Größe und n ist die logische Größe.

11:40.500 --> 11:45.960
Und der Trick ist natürlich, dass wir ein bisschen mehr allozieren,

11:46.340 --> 11:48.000
als wir tatsächlich brauchen.

11:49.580 --> 11:52.380
Und dann haben wir Luft, um mehrere Elemente einzufügen.

11:52.380 --> 11:53.420
Das ist die Grundidee.

11:53.480 --> 11:54.740
Und der Rest sind Details.

11:55.680 --> 11:59.260
Und natürlich muss man die Details sorgfältig festlegen, damit am Ende

11:59.260 --> 12:01.380
eine effiziente Lösung rauskommt.

12:04.200 --> 12:09.540
Die eigentlichen Nutzdaten stehen in so einem Array B, 0 bis W minus 1

12:09.540 --> 12:10.240
of Element.

12:11.320 --> 12:17.020
Wobei man dazu sagen muss, das verbirgt jetzt so ein bisschen, was da

12:17.020 --> 12:18.760
im Speicher tatsächlich passiert.

12:18.760 --> 12:25.420
Also dieses Objekt U-Array wird im Allgemeinen drei Members besitzen.

12:25.540 --> 12:31.160
W, n und ein Zeiger auf dieses Speichergebiet, das ich tatsächlich

12:31.160 --> 12:31.980
alloziert habe.

12:36.640 --> 12:40.700
Das ist ein Array bis Größe W, so wie ich es alloziert habe.

12:41.060 --> 12:44.780
Wobei nur die ersten n Elemente tatsächlich gültig sind.

12:44.780 --> 12:51.320
So, und jetzt haben wir wieder eine Datenstruktur-Invariante, die ja

12:51.320 --> 12:54.000
auch bei den verketteten Listen schon ganz wichtig war.

12:54.680 --> 12:58.640
Und die sagt, naja, also W soll mindestens so groß sein wie n, das ist

12:58.640 --> 12:58.980
klar.

12:59.700 --> 13:03.160
Sonst speichere ich Elemente in Speicherbereichen ab, die mir gar

13:03.160 --> 13:04.180
nicht gehören, sozusagen.

13:06.260 --> 13:11.480
Und es darf aber bis zu einem Faktor Alpha mehr sein, als ich

13:11.480 --> 13:12.200
alloziert habe.

13:12.200 --> 13:15.940
Aber es soll halt nicht beliebig viel mehr sein, als ich tatsächlich

13:15.940 --> 13:16.380
brauche.

13:17.340 --> 13:20.600
Die Implementierung, die ich angebe, da wird Alpha gleich 4 sein.

13:23.630 --> 13:26.690
Aber das ist natürlich ein Tuning-Parameter, an dem man drehen kann.

13:28.770 --> 13:34.750
Genau, was gibt es noch an syntaktischen Sachen?

13:34.750 --> 13:42.250
Wir machen das 0.w-1, das ist eine Kurzschreibweise für 0,...,n-1.

13:42.450 --> 13:47.310
Also die natürlichen Zahlen von 0 bis w-1 sind damit gemeint.

13:50.970 --> 13:55.870
Dann habe ich hier einen Operator, eckige Klammer, das ist jetzt so

13:55.870 --> 14:02.630
ein Hybrid aus meiner Pascal-Notation für Funktionen und dem Syntax

14:02.630 --> 14:04.430
von C++ für Operatoren.

14:06.510 --> 14:09.850
Also der Operator, eckige Klammer, verhält sich im Prinzip wie eine

14:09.850 --> 14:16.710
Funktion, kriegt als Parameter einen Array-Index und liefert zurück

14:16.710 --> 14:17.270
ein Element.

14:20.910 --> 14:25.890
Es gibt hier eine Vorbedingung, die sagt, es gibt nur ein vernünftiges

14:25.890 --> 14:30.790
Ergebnis, wenn i zwischen 0 und n-1 liegt.

14:32.470 --> 14:37.050
Das ist auch so etwas, wo man das Bound-Checking tatsächlich auch ein-

14:37.050 --> 14:40.590
oder ausschalten kann, je nachdem, ob man jetzt auf Effizienz- oder

14:40.590 --> 14:42.710
Fehlersuche aus ist.

14:42.710 --> 14:47.390
Und man gibt einfach das ite-Element zurück, also das ist trivial.

14:48.410 --> 14:52.490
Diese Funktion size gibt den Wert n zurück, das ist auch trivial.

14:54.590 --> 14:58.390
Und das Spannende sind jetzt natürlich die Funktionen pushback und

14:58.390 --> 14:58.790
popback.

14:59.350 --> 15:03.970
Aber gibt es an dieser Stelle Fragen zu der Klassendeklaration?

15:04.650 --> 15:08.170
Also insbesondere sind Sie wahrscheinlich immer noch dabei, diese

15:08.170 --> 15:09.910
Pseudocode -Notation zu lernen.

15:09.910 --> 15:12.990
Da möchte ich jetzt nicht zu schnell vorgehen.

15:18.650 --> 15:30.230
So, die Operation pushback funktioniert so, wenn n gleich w ist.

15:30.350 --> 15:33.750
Das heißt, ich habe den gesamten allocierten Speicher bereits

15:33.750 --> 15:35.130
aufgebraucht.

15:36.190 --> 15:37.570
Dann muss ich was tun.

15:38.630 --> 15:42.970
Sonst kann ich einfach e an die n-te Stelle schreiben und n

15:42.970 --> 15:43.790
inkrementieren.

15:44.950 --> 15:46.230
Das ist der einfache Fall.

15:47.330 --> 15:48.290
Sonst was passiert?

15:48.370 --> 15:50.610
Das ist hier jetzt mal bildlich an einem Beispiel dargestellt.

15:50.730 --> 15:55.330
b verweist auf einen Array der physikalischen Größe 4.

15:55.470 --> 15:57.470
In dem Fall ist jetzt auch n gleich w.

15:58.330 --> 16:02.770
Das heißt, das Ding ist vollgefüllt mit den Elementen 0, 1, 2 und 3.

16:04.710 --> 16:09.770
Und ich würde gerne Element e hier anfügen, da ist aber kein Platz.

16:10.650 --> 16:14.090
Deshalb rufe ich reallocate an auf und sage, ich möchte doppelt so

16:14.090 --> 16:15.530
viel Platz haben wie bisher.

16:18.370 --> 16:24.150
Das liefert mir dann n Array zurück mit 8 verfügbaren Plätzen, von

16:24.150 --> 16:25.890
denen nur die ersten 4 belegt sind.

16:26.310 --> 16:29.850
Und dann kann ich halt mein e da einfach dahinter schreiben.

16:31.070 --> 16:33.870
Dann muss ich überlegen, wie funktioniert dieses reallocate.

16:38.360 --> 16:42.080
Es kriegt als Parameter n neuen Wert für w, w'.

16:43.620 --> 16:45.560
Setzt w auf w'.

16:46.780 --> 16:51.220
Alloziert n Array der Größe w'.

16:51.220 --> 16:55.240
Das ist jetzt meine Schreibweise für Speicherallokation.

16:57.440 --> 17:00.460
Ich weiß jetzt nicht, ob das Pascal ist oder so.

17:01.420 --> 17:02.680
Dispose ist Pascal.

17:03.260 --> 17:04.840
Allocate wahrscheinlich auch.

17:06.500 --> 17:09.600
Also ich alloziere n Array der Größe w'.

17:10.280 --> 17:13.040
In dem Fall auch schon w von Elementen.

17:13.120 --> 17:15.900
Das ist am Anfang halt tabula rasa.

17:16.220 --> 17:19.660
Da steht nichts drin oder irgendwelche undefinierten Werte.

17:22.040 --> 17:27.560
Und jetzt wird der Inhalt von b in mein Array b' kopiert.

17:28.320 --> 17:32.740
Dann zeigt sowohl b auf 0, 1, 2, 3 als auch b'.

17:34.920 --> 17:40.160
Und anschließend kann ich diesen Zeiger b auf den Anfang des

17:40.160 --> 17:43.560
Speicherbereichs b' umsetzen.

17:44.420 --> 17:45.760
Das geht in konstanter Zeit.

17:48.680 --> 17:52.820
Und auch das b freigeben.

17:52.820 --> 17:55.500
Also damit sage ich dem Betriebssystem bzw.

17:55.500 --> 17:59.500
dem Laufzeitsystem, dieses Stück Speicher, auf das b bisher verwiesen

17:59.500 --> 18:01.320
hat, wird nicht mehr benötigt.

18:02.980 --> 18:07.420
Wo funktioniert explizite Speicherverwaltung in C++?

18:11.200 --> 18:14.620
Ja, in Java wird man glaube ich im Wesentlichen diese Zeile weglassen.

18:14.620 --> 18:18.820
Ich weiß nicht, ob man Java auch hinzugeben kann, dass bestimmte

18:18.820 --> 18:20.320
Sachen nicht mehr gebraucht werden.

18:25.620 --> 18:27.040
Gibt es dazu Fragen?

18:27.960 --> 18:29.920
Also es ist eigentlich auch noch sehr einfach.

18:34.610 --> 18:37.250
Und dann brauchen wir schließlich noch die Funktion popback.

18:42.890 --> 18:46.550
Die ist nur dann sinnvoll, also wir haben wieder eine Vorbedingung,

18:46.750 --> 18:51.290
wenn das Array überhaupt Elemente enthält.

18:51.470 --> 18:54.990
Also es ist irgendwie nicht klar, was man tun soll, wenn man aus einem

18:54.990 --> 18:56.530
leeren Array etwas entfernt.

18:59.150 --> 19:04.330
Wenn das gegeben ist, kann ich halt n, die Anzahl logischer Elemente,

19:04.370 --> 19:05.170
dekrementieren.

19:06.990 --> 19:11.070
Und eigentlich wäre jetzt gar nicht mehr zu tun, aber ich könnte ja

19:11.070 --> 19:13.170
die Datenstruktur invariante verletzen.

19:13.910 --> 19:27.490
Wenn w dadurch unter 4n fällt oder auf 4n steigt, also n sinkt und w

19:27.490 --> 19:28.750
bleibt erstmal konstant.

19:28.910 --> 19:32.610
Wenn ich also jetzt nur noch ein Viertel des Platzes tatsächlich

19:32.610 --> 19:34.910
belege, sage ich jetzt reicht es aber.

19:35.450 --> 19:37.770
Und ich gebe dann die Hälfte davon frei.

19:38.230 --> 19:41.230
Also dann würde ich wieder ein reallocate 2n machen.

19:44.370 --> 19:47.750
Das klingt jetzt auf den ersten Blick sehr konservativ, also wir

19:47.750 --> 19:49.330
lassen hier noch viel Freiraum.

19:49.830 --> 19:54.190
Kann mir jemand sagen, was schief geht, wenn ich hier reallocate n

19:54.190 --> 19:55.070
schreiben würde?

20:09.480 --> 20:12.440
Also logisch wäre das erstmal kein Problem, ich kann da irgendeinen

20:12.440 --> 20:13.000
Wert wählen.

20:19.480 --> 20:23.200
Genau, also wenn man dann anschließend ein Element einfügt, würde man

20:23.200 --> 20:26.760
dann für zwei Operationen zweimal alles umkopieren.

20:26.840 --> 20:28.820
Das klingt jetzt ein bisschen verschwenderisch.

20:29.840 --> 20:32.540
Und wir werden halt später auch zeigen, dass so wie wir es hier

20:32.540 --> 20:36.020
machen, das in gewisser Weise beweisbar effizient ist.

20:37.620 --> 20:39.460
Die zweite Hälfte haben wir auch noch.

20:40.400 --> 20:44.340
Genau, und das möchte ich aber jetzt ein bisschen formaler erklären,

20:44.420 --> 20:45.460
was das überhaupt bedeutet.

20:45.560 --> 20:47.300
Diese Implementierung ist effizient.

20:49.840 --> 20:54.400
Also nehmen wir mal an, wir haben ein anfangs leeres, unbeschränktes

20:54.400 --> 21:01.220
Feld U und eine beliebige Operationenfolge Sigma 1 bis Sigma M von

21:01.220 --> 21:03.360
Pushback und Popback Operationen.

21:03.360 --> 21:11.280
Also die anderen Operationen, Abfragen der Größe, Zugriff auf Elemente

21:11.280 --> 21:14.640
sind unkritisch, die brauchen immer konstante Zeit, egal was ich da

21:14.640 --> 21:14.860
tue.

21:15.980 --> 21:19.540
Interessant sind die Pushback und Popback Operationen, davon haben wir

21:19.540 --> 21:22.640
M Stück, die nennen wir Sigma 1 bis Sigma M.

21:26.020 --> 21:32.480
Und ich behaupte, dass die von unserem Algorithmus in Zeit O von M

21:32.480 --> 21:37.900
ausgeführt werden, egal welche Folge von Operationen das ist.

21:38.680 --> 21:42.400
Also in welcher Reihenfolge da Pushback und Popback hintereinander

21:42.400 --> 21:42.800
kommen.

21:45.900 --> 21:50.840
Das bedeutet insbesondere, ich nehme meine Gesamtzeit M, wenn ich die

21:50.840 --> 21:55.640
teile, O von M und ich teile das durch die Anzahl Operationen, das ist

21:55.640 --> 21:58.320
M, dann kommt O von 1 raus.

21:58.980 --> 22:02.340
Und eine Sprechweise, die sich als sehr nützlich in der Informatik

22:02.340 --> 22:06.540
herausgestellt hat, ist, dass man sagt, die Operationen Pushback und

22:06.540 --> 22:10.520
Popback haben amortisiert konstante Ausführungszeit.

22:11.340 --> 22:16.360
Das ist wichtig, diese Begriffsdefinition zu machen, weil es wäre

22:16.360 --> 22:20.760
falsch zu sagen, die Operationen Pushback und Popback haben konstante

22:20.760 --> 22:21.900
Ausführungszeit.

22:22.220 --> 22:27.340
Denn gelegentlich kommt es ja mal vor, dass ein einziges Pushback so

22:27.340 --> 22:32.140
eine Umkopieroperation ausführt, die halt lineare Laufzeit in der

22:32.140 --> 22:34.580
Größe des Unbounded Arrays hat.

22:35.400 --> 22:41.560
Aber diese Beobachtung, dass die Gesamtausführungszeit für so eine

22:41.560 --> 22:48.420
Operationenfolge, wenn ich die umlege, auf alle Einzeloperationen nur

22:48.420 --> 22:52.720
konstant teuer ist, das ist eine wichtige Beobachtung.

22:52.720 --> 22:55.660
Und es gibt sehr viele Datenstrukturen oder Algorithmen mit dieser

22:55.660 --> 23:01.320
Eigenschaft und die sind oft viel einfacher und in der Praxis

23:01.320 --> 23:07.480
effizienter als entsprechende Varianten, die im schlechtesten Fall

23:07.480 --> 23:11.980
jedes Mal diese konstante Ausführungszeit erreichen.

23:16.330 --> 23:20.250
So gibt es Fragen, was dazu gemeint ist mit amortisiert konstante

23:20.250 --> 23:23.350
Ausführungszeit für Pushback und Popback.

23:23.350 --> 23:26.210
Das ist jetzt erstmal eine Behauptung, die müssen wir beweisen.

23:29.230 --> 23:32.990
Und da geht jetzt der nächste Lerneffekt ein.

23:34.550 --> 23:38.390
Wir wollen nicht nur irgendeinen ad hoc Beweis für diese konkrete

23:38.390 --> 23:42.010
Eigenschaft führen, sondern wir wollen eine Analysetechnik einführen,

23:42.090 --> 23:46.270
die man für ganz viele solche Argumentationen brauchen kann.

23:47.010 --> 23:49.750
Nämlich die Kontomethode oder man könnte die auch die

23:49.750 --> 23:51.170
Versicherungsmethode nennen.

23:52.510 --> 23:58.590
Wir machen jetzt folgendes, wir sagen eine Operation Pushback und

23:58.590 --> 24:03.170
Popback belaste ich nicht nur mit den Kosten, die sie tatsächlich

24:03.170 --> 24:10.030
verursachen, sondern die müssen zusätzlich zwei Münzen, zwei Token

24:10.030 --> 24:14.670
irgendeiner Rechengröße einzahlen auf ein Konto.

24:16.570 --> 24:21.010
Unsere Konvention ist, ein Pushback zahlt zwei Token ein und ein

24:21.010 --> 24:23.110
Popback zahlt ein Token ein.

24:24.150 --> 24:30.690
Und dafür müssen sie aber nicht bezahlen, in unserer amortisierten

24:30.690 --> 24:33.490
Rechnung, für die Aufrufe von reallocate.

24:35.170 --> 24:39.730
Und die Konvention, die ich sage, wenn ich reallocate zwei N aufrufe,

24:40.530 --> 24:45.850
dann kostet das N Tokens.

24:47.070 --> 24:51.670
Und worum es jetzt geht, ich zeige, dass es niemals passiert, dass

24:51.670 --> 24:56.150
reallocate aufgerufen wird und mehr Tokens abgehoben werden, als auf

24:56.150 --> 24:56.830
dem Konto liegen.

24:57.810 --> 25:03.830
Und wenn ich das zeigen kann, habe ich bewiesen, die amortisierten

25:03.830 --> 25:05.670
Kosten sind halt tatsächlich konstant.

25:09.790 --> 25:16.890
Man könnte das auch so formulieren, Pushback und Popback haben eine

25:16.890 --> 25:22.830
Versicherungspolice abgeschlossen, gegen die Eventualität, dass sie

25:22.830 --> 25:24.390
reallocate aufrufen müssen.

25:24.390 --> 25:32.550
Dafür müssen sie bei jedem Aufruf eine Gebühr bezahlen, das sind diese

25:32.550 --> 25:33.070
Tokens.

25:34.950 --> 25:39.830
Dafür müssen sie für den Fall, dass der Fall der Fälle eintritt,

25:40.070 --> 25:40.690
nichts zahlen.

25:41.390 --> 25:45.350
Das ist so, wie wenn sie eine Diebstahlsversicherung für ihr Fahrrad

25:45.350 --> 25:46.550
abschließen oder sowas.

25:48.030 --> 25:51.330
Sie müssen natürlich jedes Jahr diese Versicherungsgebühr bezahlen,

25:51.850 --> 25:54.390
dafür, wenn ihr Fahrrad tatsächlich geklaut wird, müssen sie nichts

25:54.390 --> 25:57.770
bezahlen oder kriegen ihr Geld wieder zu.

26:00.880 --> 26:02.240
Ja, gucken wir uns das mal an.

26:02.300 --> 26:04.100
Ich werde einen Induktionsbeweis führen.

26:04.820 --> 26:08.120
Der erste Aufruf von reallocate, der passiert genau dann, wenn N

26:08.120 --> 26:08.980
gleich zwei ist.

26:08.980 --> 26:14.360
Also wenn ich irgendwie mindestens zwei Pushbacks gemacht habe, dann

26:14.360 --> 26:16.820
habe ich aber vier Tokens bereits eingezahlt.

26:20.400 --> 26:25.840
Ich mache ein reallocate zweimal zwei, muss zwei Tokens bezahlen, habe

26:25.840 --> 26:28.840
aber schon vier eingezahlt, also ich bin auf der sicheren Seite.

26:29.480 --> 26:31.100
Das ist unser Induktionsanfang.

26:31.100 --> 26:35.880
So, wenn ich jetzt weitere Aufrufe von reallocate mache, dann gibt es

26:35.880 --> 26:38.340
zwei wichtige Fälle zu unterscheiden.

26:39.240 --> 26:43.240
Also entweder ich habe vorher irgendeinen Aufruf von reallocate 2N

26:43.240 --> 26:48.160
gemacht, der unproblematisch war, das ist unsere Induktionsannahme.

26:48.860 --> 26:55.540
Danach kommt irgendeine Folge von Operationen, die damit endet, dass

26:55.540 --> 26:57.880
ein reallocate 4N aufgerufen wird.

26:57.880 --> 27:00.480
Also es hat sich verdoppelt, die Größe geht rauf.

27:01.240 --> 27:05.800
Dann weiß ich, zu dem Zeitpunkt, als das hier aufgerufen wurde, waren

27:05.800 --> 27:07.160
nur N Elemente drin.

27:07.600 --> 27:10.300
Zu dem Zeitpunkt waren zwei N Elemente drin.

27:10.860 --> 27:14.600
Das geht nur, wenn zwischendurch mindestens N Pushbacks stattgefunden

27:14.600 --> 27:14.920
haben.

27:15.640 --> 27:18.780
Es könnte auch sein, dass zwischendurch noch Popbacks dabei waren, die

27:18.780 --> 27:21.020
durch weitere Pushbacks ausgeglichen wurden.

27:21.020 --> 27:25.180
Aber das führt nur zu weiteren Einzahlungen aufs Konto.

27:25.760 --> 27:29.000
Und der schlechteste Fall ist tatsächlich, dass hier nur Pushbacks

27:29.000 --> 27:30.040
stattgefunden haben.

27:33.000 --> 27:36.240
Und es soll halt eine Folge sein, wo keine reallocate Aufrufe

27:36.240 --> 27:36.920
dazwischen waren.

27:38.020 --> 27:42.980
So, dann habe ich aber diese N Pushbacks, jede davon hat zwei Tokens

27:42.980 --> 27:43.260
eingezahlt.

27:43.900 --> 27:46.840
Das heißt, ich habe mindestens zwei N Tokens auf dem Konto.

27:46.840 --> 27:51.780
Und das ist genau das, was ich für dieses reallocate 4N bezahlen muss.

27:52.260 --> 27:53.980
Ich bleibe also auf der sicheren Seite.

27:55.500 --> 27:58.800
Die andere Möglichkeit ist, die Größe schrumpft.

27:59.480 --> 28:04.540
Also ich habe ein reallocate 2N und dann wird irgendwann reallocate N

28:04.540 --> 28:05.300
aufgerufen.

28:07.800 --> 28:13.840
Zu diesem Zeitpunkt waren N Elemente in der Queue.

28:14.720 --> 28:15.900
Nee, Quatsch.

28:17.520 --> 28:19.340
Wie viele waren in der Queue?

28:20.200 --> 28:22.180
Jetzt muss ich nachdenken.

28:34.490 --> 28:35.070
Ah ja, genau.

28:35.270 --> 28:37.330
Also nach einem reallocate...

28:38.810 --> 28:40.710
Meine Invariante sagt mir,

28:45.200 --> 28:53.580
wenn ich ein reallocate auf Größe 2N mache, dann sind danach

28:53.580 --> 28:55.640
mindestens N Elemente in der Queue.

28:56.580 --> 28:57.660
Das ist wichtig.

29:00.840 --> 29:02.640
Jetzt müssen wir auf unseren Code mal gucken.

29:02.720 --> 29:03.680
Wie war das Popback?

29:09.510 --> 29:13.390
Da sind noch wie viertel...

29:19.030 --> 29:24.510
Also ich mache immer ein reallocate 2N und das heißt, ich habe danach

29:24.510 --> 29:26.490
N Elemente drin.

29:28.690 --> 29:30.350
Mindestens N Elemente drin.

29:33.090 --> 29:36.570
Das heißt, zu dem Zeitpunkt waren mindestens N Elemente drin.

29:37.350 --> 29:42.450
Das wird erst aufgerufen, wenn ich höchstens N halbe übrig habe.

29:42.990 --> 29:45.430
Das heißt, es wurden mindestens N halbe rausgeholt.

29:46.290 --> 29:49.710
Jedes davon hat mindestens ein Token eingezahlt.

29:50.630 --> 29:58.710
Und das genügt aber, um die N halbe Tokens zu bezahlen, die als Kosten

29:58.710 --> 30:00.350
für das reallocate N anfallen.

30:00.350 --> 30:03.210
Das heißt, ich bleibe auch auf der sicheren Seite.

30:06.110 --> 30:10.970
Und beim nächsten Mal werden wir kennenlernen, wie man amortisierte

30:10.970 --> 30:15.870
Analyse weiter verallgemeinert und was man noch mit anbauenden Arrays

30:15.870 --> 30:18.690
machen kann und Vergleich mit Listen und so weiter.

30:19.370 --> 30:21.030
Und wir machen jetzt weiter mit der Übung.

30:21.370 --> 30:21.790
Dankeschön.

30:23.070 --> 30:25.830
Das ist übrigens das Sparschwein.

30:26.230 --> 30:29.490
Jetzt dürft ihr einmal überlegen, welche Methode das symbolisiert.

30:34.600 --> 30:39.340
Das mit der Konto-Methode erzählt euch nachher der Julian.

30:40.320 --> 30:46.700
Wir machen jetzt erst noch ein wenig Nachtrag zu den Rekurrenzen, die

30:46.700 --> 30:48.360
wir letztes Mal schon angesprochen hatten.

30:51.900 --> 30:55.240
Und zwar habe ich euch erzählt, dass es da so ein paar Grobkategorien

30:55.240 --> 30:59.640
gibt, nämlich eine allgemeine Rekurrenz, wo alles Mögliche drinstehen

30:59.640 --> 30:59.840
kann.

31:01.320 --> 31:04.160
Dann gibt es lineare Rekurrenzen.

31:04.420 --> 31:08.760
Das ist dann, wenn der neue Term von den vorhergehenden K linear

31:08.760 --> 31:09.340
abhängt.

31:10.180 --> 31:14.100
Und in der Informatik kommen häufig die, ich habe sie irgendwie

31:14.100 --> 31:19.300
Rekursionen aus divide-and-conquer-Algorithmen genannt, wo halt N in B

31:19.300 --> 31:23.680
-Teile geteilt wird, dann dort das Problem rekursiv gelöst wird und

31:23.680 --> 31:29.300
beim Zusammenführen der Einzellösungen dann wieder F von N mal A

31:29.300 --> 31:31.900
Arbeit anfällt.

31:33.960 --> 31:37.000
Diese Rekursionsgleichungen aus der Informatik, die werden häufig mit

31:37.000 --> 31:38.340
dem Mastertheorem gelöst.

31:38.440 --> 31:41.220
Das habt ihr auf dem nächsten Übungsblatt drauf am Freitag.

31:42.360 --> 31:44.880
Und das ist im Wesentlichen Pattern-Matching.

31:46.560 --> 31:49.560
Gegeben eine Rekursionsgleichung, welche von diesen Fällen.

31:51.580 --> 31:56.000
Es gibt noch eine ganze Reihe anderer Rekursionsgleichungen und da

31:56.000 --> 31:58.740
kommt man mit dem Mastertheorem dann nicht voran.

31:58.980 --> 32:02.360
Und da möchte ich euch jetzt ein paar von vorführen, oder eine

32:02.360 --> 32:06.080
vorführen, wie man die löst, und zwar mit der Substitutionsmethode.

32:07.460 --> 32:11.920
Wenn man so eine Rekursionsgleichung hat, wo man erstmal nicht das

32:11.920 --> 32:15.500
Mastertheorem anwenden kann, weil hier irgendwie kein Bruch drin

32:15.500 --> 32:17.380
steht, dann ist man erstmal aufgeschmissen.

32:19.240 --> 32:25.420
Aber diese Rekursionsgleichung gilt nur für ganz bestimmte Werte, weil

32:25.420 --> 32:27.240
irgendwie muss die Wurzel ja funktionieren.

32:28.740 --> 32:31.440
Und was man dann sich überlegt, ich ersetze eine Variable,

32:35.640 --> 32:41.380
substituiere eine Variable, die man halt irgendwie neu nennt, m gleich

32:41.380 --> 32:43.360
2 hoch bzw.

32:43.600 --> 32:49.600
log 2 n, wobei, also im Prinzip stelle ich fest, dass ich hier sowieso

32:49.600 --> 32:51.080
nur Zweierpotenzen drin habe.

32:51.080 --> 32:54.620
Deswegen mache ich mein n gleich 2 hoch m.

32:55.560 --> 32:59.160
Und wenn ich das umdrehe, dann kriege ich halt m ist log 2 n.

33:02.540 --> 33:08.160
Und dann kriege ich, wenn ich jetzt mein t von n beschränke, wenn mein

33:08.160 --> 33:11.420
t von n gerade so eine Form hat, 2 hoch m,

33:14.440 --> 33:23.860
dann gilt für diese 2 hoch m, m t von Wurzel aus 2 hoch m plus 1.

33:26.600 --> 33:28.860
Und Wurzel, was machen wir damit?

33:29.060 --> 33:29.900
Das ist m halbe.

33:32.140 --> 33:35.700
2 hoch m halbe plus 1.

33:38.340 --> 33:43.420
So, ich habe jetzt quasi eine neue Variable m eingeführt und die ist

33:43.420 --> 33:44.240
abhängig von n.

33:45.100 --> 33:49.080
Und der nächste Trick, den man hier macht, ist eine neue Rekurrenz

33:49.080 --> 33:49.620
definieren.

33:49.720 --> 33:52.460
Man überlegt sich, was jetzt s von m ist.

33:53.520 --> 33:57.900
Wobei dieses s von m gleich t von 2 hoch m ist.

34:02.230 --> 34:05.010
So, das s von m ist t hoch 2 hoch m, das steht hier.

34:05.890 --> 34:08.930
Das heißt, das ist erstmal das, was hier steht.

34:09.770 --> 34:12.710
Jetzt möchte ich aber diesen Ausdruck wieder in s von m schreiben.

34:13.950 --> 34:14.830
Wie mache ich das?

34:15.510 --> 34:20.850
Nun, das ist dann s von m halbe plus 1.

34:21.550 --> 34:27.870
Weil das hier oben hat ja die Form t von 2 hoch etwas und t von 2 hoch

34:27.870 --> 34:30.010
etwas m ist s von m.

34:30.810 --> 34:33.670
Deswegen, das obere ist hier dieses etwas, ist m halbe.

34:33.670 --> 34:35.050
Und deswegen kommt es hier hinein.

34:36.610 --> 34:39.350
Jetzt müssen wir uns noch überlegen, wofür eigentlich dieses s gilt.

34:40.170 --> 34:46.730
Das gilt nämlich nur für, wenn m gleich 2 hoch k ist.

34:48.090 --> 34:52.970
Und den Anfangswert von s von 2 bis 1.

34:54.750 --> 34:56.070
Das sind diese beiden Anfangswerte.

34:57.110 --> 35:01.070
So, jetzt könnte man wahrscheinlich Mastertheorien anwenden.

35:01.070 --> 35:04.110
Allerdings gibt es Mastertheorien, was man nicht mehr sieht, und

35:04.110 --> 35:05.970
tatsächlich nur eine asymptotische Schranke.

35:08.330 --> 35:10.630
Und wenn wir das genau lösen wollen, dann müssen wir ein bisschen

35:10.630 --> 35:11.190
weitermachen.

35:12.190 --> 35:14.310
Oder gibt es schon jemanden, der die Lösung quasi errät?

35:15.690 --> 35:18.050
Ja, man kann das schon raten, wenn man das einmal gesehen hat, aber

35:18.050 --> 35:18.810
wir machen mal weiter.

35:19.350 --> 35:23.850
Wir substituieren mit dem gleichen Prinzip.

35:25.670 --> 35:27.970
Jetzt gehen wir die Variablen aus und nennen sie mal p.

35:28.910 --> 35:30.770
Was müssen wir hier machen mit unserem p?

35:30.870 --> 35:34.150
Das m soll wieder das Gleiche, 2 hoch k.

35:34.570 --> 35:35.630
Das ist jetzt der Trick.

35:37.030 --> 35:41.870
2 hoch p und p ist log 2m.

35:44.310 --> 35:46.030
Im Prinzip macht man jetzt das Gleiche nochmal.

35:47.590 --> 35:53.290
s ist 2 hoch p, also s 2 hoch m.

35:54.750 --> 36:02.110
Wenn ich hier ein m einsetze, dann ist das s von 2 hoch p gleich s von

36:02.110 --> 36:07.490
2 hoch p halbe plus 1.

36:09.070 --> 36:10.490
So, das könnt ihr rechnen.

36:10.970 --> 36:18.610
s von 2 hoch p gleich s von 2 hoch p minus 1 plus 1.

36:19.330 --> 36:23.050
Und jetzt definiere ich mir nochmal eine neue Regressionsgleichung.

36:27.940 --> 36:33.160
u von p ist einfach u von p minus 1 plus 1.

36:33.440 --> 36:34.860
Wieder Anfangswerte überlegen.

36:35.400 --> 36:41.620
p gilt jetzt für alles, größer als 1.

36:41.840 --> 36:45.000
Und u von 1 ist 1.

36:46.420 --> 36:47.800
Möchte mir die jemand lösen?

36:52.420 --> 36:53.620
Es ist ganz einfach.

36:56.140 --> 36:57.600
Es ist einfach gleich p.

36:58.780 --> 37:00.340
Und zwar ohne Rekursion.

37:00.460 --> 37:00.640
Warum?

37:00.780 --> 37:01.780
Ich fange bei 1 an.

37:02.720 --> 37:04.820
u von 2 ist 1 plus 1.

37:05.560 --> 37:07.360
u von 3 ist 2 plus 1.

37:08.400 --> 37:08.960
Einfach p.

37:17.290 --> 37:20.270
Okay, aber jetzt wollen wir zurück zu t von n.

37:21.510 --> 37:25.790
Also wir wissen, unsere Rekursionsgleichung u zurück einsetzen.

37:32.400 --> 37:34.960
u ist gleich p.

37:37.620 --> 37:40.720
Wir wissen jetzt, u ist gleich p.

37:41.600 --> 37:48.040
s ist gleich s von m.

37:49.980 --> 37:51.000
Mal gucken.

37:54.420 --> 37:55.420
Wir kommen hier zurück.

37:57.520 --> 37:58.460
Von 2 hoch p.

38:00.680 --> 38:02.240
Ist von m.

38:03.740 --> 38:04.920
Hier fehlt noch irgendwas.

38:05.900 --> 38:07.320
Ah, hier fehlt natürlich etwas.

38:10.990 --> 38:13.170
p war log 2m.

38:15.390 --> 38:18.270
Und s von m war nur definiert für 2 hoch k.

38:19.550 --> 38:28.210
s von m war u von 2 hoch p.

38:31.130 --> 38:32.950
Wir wollen jetzt s von m ausrechnen.

38:32.990 --> 38:33.390
Sieht es jemand?

38:39.400 --> 38:40.720
War 2 hoch p.

38:45.430 --> 38:45.950
Genau.

38:53.230 --> 38:59.450
Und s von 2 hoch p war u von p.

39:07.180 --> 39:09.200
Ja, ich habe hier irgendeinen Schritt zu schnell gemacht.

39:09.340 --> 39:09.900
Das mal überlegen.

39:13.220 --> 39:15.120
Hier haben wir etwas definiert.

39:15.200 --> 39:20.500
u von 2 hoch p ist 2 hoch m.

39:21.380 --> 39:23.080
s von 2 hoch m ist 2 hoch p.

39:24.440 --> 39:24.880
Genau.

39:28.440 --> 39:30.120
Ja, das habe ich vergessen vorhin.

39:30.280 --> 39:33.180
Das s von p ist u von p.

39:33.460 --> 39:35.420
Denn sonst könnte man diesen Schritt hier gar nicht machen.

39:36.980 --> 39:40.400
Das ist hier angewandt und dort angewandt.

39:40.920 --> 39:43.300
Und deswegen ist das hier einfach nur p.

39:44.740 --> 39:47.500
Und p war log 2m.

39:49.640 --> 39:53.080
Damit haben wir herausbekommen, dass s von m ist log 2m.

39:54.920 --> 39:56.620
Für m 2 hoch k.

39:58.980 --> 40:00.460
Jetzt kommt noch ein Schritt zurück.

40:00.920 --> 40:07.720
t von n haben wir definiert als 2 hoch m.

40:12.790 --> 40:14.930
Und t von 2 hoch m war s von m.

40:19.420 --> 40:20.920
Und s von m haben wir gerade gelöst.

40:20.920 --> 40:22.340
Das ist nämlich log 2m.

40:26.620 --> 40:29.920
Und m war log 2n.

40:31.540 --> 40:36.360
Damit haben wir gezeigt, das ist log 2n.

40:42.720 --> 40:46.560
Für n gleich 2 hoch 2 hoch k.

40:49.080 --> 40:49.800
Gut.

40:52.420 --> 40:53.460
Dann doch noch die Schaft.

40:55.660 --> 40:58.800
Das sind die ersten Formen von Rekursionsgleichung.

40:58.960 --> 41:00.120
Solche kommen hoffentlich auf dem Übungsblatt.

41:06.080 --> 41:11.500
Es gibt noch eine sehr fortgeschrittene Form der

41:11.500 --> 41:13.380
Rekursionsgleichungslösung.

41:13.380 --> 41:15.160
Achso, hat irgendjemand Fragen dazu?

41:18.460 --> 41:24.540
Im Prinzip überlegt man sich, was ich für eine Ersetzung mache.

41:24.740 --> 41:26.920
Und diese Ersetzung, was für Ersetzungen sind da gültig?

41:27.020 --> 41:29.980
Das ist gültig dann, wenn ich irgendwie umkehrbare Funktionen

41:29.980 --> 41:30.360
verwende.

41:32.000 --> 41:37.580
Die eine Variable muss mit der anderen durch eine bijektive Funktion,

41:37.660 --> 41:41.080
durch eine invertierbare Funktion zusammenhängen.

41:41.080 --> 41:43.880
Und dann kann ich eine neue Rekursionsgleichung definieren.

41:45.120 --> 41:48.740
Es gibt noch eine andere Methode, mit der man Rekurrenzen lösen kann.

41:48.820 --> 41:53.180
Und zwar Rekurrenzen der form der linearen Form, die hier.

41:54.380 --> 41:57.840
Und zwar in fast jeder beliebigen Kompliziertheit.

41:58.380 --> 42:01.400
Das machen viele Mathe-Algebra-Programme so.

42:02.060 --> 42:04.240
Ich führe euch das an einem Beispiel mal vor.

42:06.260 --> 42:09.000
Und das Beispiel ist wie üblich eines der einfachen.

42:10.740 --> 42:12.920
Nämlich die Fibonacci-Zahlen.

42:15.240 --> 42:17.180
Den Jahr multipliziert mit 1.

42:18.880 --> 42:20.220
Und jetzt gibt es einen Trick.

42:20.380 --> 42:24.140
Man geht über sogenannte Potenzreihen an dieses Ding heran und errät

42:24.140 --> 42:28.000
durch eine Rechnung eine Lösung, die man nachher noch verifizieren

42:28.000 --> 42:28.320
muss.

42:28.820 --> 42:29.440
So, nochmal.

42:30.300 --> 42:34.860
Wir überlegen, das ist eine Art Trick-Rechnung, wir definieren uns

42:34.860 --> 42:40.640
eine eigentlich nicht konvergierende Potenzreihe, wobei die Folge

42:40.640 --> 42:43.880
selbst die Koeffizienten dieser Potenzreihe sind.

42:44.620 --> 42:45.900
So, jetzt steht eine Potenzreihe da.

42:48.480 --> 42:51.680
Ob die jetzt hier eigentlich konvergiert, intusiert uns nicht.

42:52.520 --> 42:55.220
Was wir jetzt stattdessen machen, ist das hier einfach mal einsetzen.

42:58.140 --> 43:04.020
Die Koeffizienten der Potenzreihe sind die Folgenglieder der Fibonacci

43:04.020 --> 43:04.420
-Zahlen.

43:04.880 --> 43:10.920
Das heißt, f von 0, der erste Summand dieser Potenzreihe ist f von 0,

43:11.000 --> 43:13.480
z hoch 0, plus f von 1, z hoch 1.

43:14.920 --> 43:18.580
So, und den Rest kann ich durch diese Rekursionsgleichung ausdrücken.

43:18.740 --> 43:20.020
Das geht ab 2 los.

43:21.760 --> 43:23.680
Dann steht die Rekursionsgleichung drin.

43:28.850 --> 43:30.690
Und hinten steht z hoch n.

43:33.170 --> 43:34.310
Was sehen wir hier?

43:34.610 --> 43:36.330
Nun, das ist 0.

43:37.050 --> 43:40.110
Das ist 1, das ist 1z.

43:40.450 --> 43:45.410
Und jetzt rechnet man mit bekannten Gesetzen für Potenzreihen.

43:45.470 --> 43:47.330
Wir haben im Prinzip hier nur z, das ist eine 1.

43:49.950 --> 43:51.470
Hier machen wir erstmal nichts.

43:51.950 --> 43:52.910
Das ist schon kompliziert genug.

43:55.350 --> 43:57.150
Aber was man offensichtlich schon sieht, man kann das

43:57.150 --> 43:57.830
auseinanderziehen.

44:08.600 --> 44:10.740
Okay, ich habe es gerade schon gesagt, wir ziehen das jetzt

44:10.740 --> 44:11.220
auseinander.

44:11.520 --> 44:18.160
z plus den ersten Teil, in Summe n gleich 2 bis unendlich, f von n

44:18.160 --> 44:23.720
minus 1, z hoch n, plus diese zweite Summe.

44:23.820 --> 44:26.320
Und jetzt können wir uns schon überlegen, was wir da an

44:26.320 --> 44:28.780
Indextransformationen drauf loslassen.

44:33.860 --> 44:36.300
Hier transformieren wir den Index mal auf...

44:36.300 --> 44:38.240
Was können wir denn jetzt machen?

44:38.620 --> 44:42.940
Wir werden versuchen, diese Form wieder auf diese Form

44:42.940 --> 44:43.460
zurückzubringen.

44:44.520 --> 44:47.940
Sodass wir am Ende auf der rechten Seite wieder das Groß-F von z

44:47.940 --> 44:48.520
stehen haben.

44:48.920 --> 44:51.780
Das heißt, wir müssen versuchen, die hier wieder in diese Form zu

44:51.780 --> 44:52.140
bekommen.

44:52.540 --> 44:55.300
Das Erste, was wir hier machen, ist einfach mal die Index ums 1

44:55.300 --> 44:55.960
kleiner machen.

44:57.900 --> 45:00.520
Wir versuchen hier, wieder f von n hinzubekommen.

45:00.600 --> 45:02.660
Das machen wir, indem wir einfach bei 1 anfangen.

45:02.800 --> 45:06.080
Denn dann, wenn man sich das überlegt, n ist gleich 2, dann steht hier

45:06.080 --> 45:06.940
eigentlich f von 1.

45:07.400 --> 45:08.760
Das heißt, hier muss ich erstmal gar nichts machen.

45:09.460 --> 45:10.900
f von n.

45:12.460 --> 45:15.820
Hier oben hat sich aber was getan, hier muss ich ja bei 2 anfangen.

45:22.610 --> 45:23.570
Meine Schrift...

45:23.570 --> 45:26.570
Hier ist es doch noch ein ganzes Stückchen einfacher.

45:26.730 --> 45:28.790
Wir fangen sowieso bei 2 an, subtrahieren hier 2.

45:28.970 --> 45:31.290
Das heißt, das fängt eigentlich bei f von 0 sowieso an.

45:32.210 --> 45:33.990
Und deswegen können wir es gleich schon einschreiben.

45:38.320 --> 45:43.140
Hier nicht vergessen, hier steht Zn hoch n plus 2.

45:43.920 --> 45:45.720
Wir haben eine Index-Transformation gemacht.

45:46.120 --> 45:47.400
Das Unendliche muss ich nicht transformieren.

45:47.760 --> 45:48.260
Passiert nichts.

45:50.400 --> 45:52.060
Wir wollen ja hier hin zurück.

45:53.380 --> 45:55.880
Das heißt, wir können hier das rausziehen, ein Glied.

45:56.300 --> 45:56.720
Und hier auch.

45:59.560 --> 46:00.780
Z davor schreiben.

46:02.240 --> 46:04.340
Und eigentlich wollen wir hier eine 0 haben.

46:04.440 --> 46:06.600
Deswegen schreiben wir mal forciert eine 0 hin.

46:06.720 --> 46:09.680
Und gucken danach, was wir dazufügen müssen, um das zu korrigieren.

46:11.040 --> 46:12.080
Z hoch n.

46:12.520 --> 46:13.280
Jetzt haben wir eine 0.

46:13.440 --> 46:15.340
Eigentlich müssen wir hier wieder was abziehen.

46:15.340 --> 46:17.760
Nämlich f von 0, Z hoch 0.

46:18.740 --> 46:19.560
So, jetzt stimmt es wieder.

46:20.340 --> 46:22.260
Hier müssen wir nur Z² rausziehen.

46:24.820 --> 46:25.600
Jam, jam, jam.

46:29.060 --> 46:30.740
f von n, Z hoch n.

46:30.840 --> 46:32.120
Oh, da steht schon das von vorher.

46:34.360 --> 46:35.160
Was ist das?

46:36.880 --> 46:37.960
Können wir da auch nach oben gucken?

46:38.200 --> 46:39.420
Ah, nix.

46:39.800 --> 46:39.960
0.

46:40.940 --> 46:43.960
Das heißt, wir haben hier Z plus...

46:45.060 --> 46:46.080
Also, nix.

46:46.820 --> 46:47.880
f von Z.

46:51.180 --> 46:52.380
Plus Z².

46:52.800 --> 46:53.900
Und das ist auch f von Z.

46:55.080 --> 46:56.000
Was steht hier?

46:57.560 --> 46:58.180
Mal nach oben gucken.

46:58.320 --> 46:58.760
f von Z.

47:02.810 --> 47:04.410
Was schließen wir daraus?

47:05.030 --> 47:10.290
Dass diese seltsame Potenzreihe eigentlich einen Bruch erfüllt.

47:11.140 --> 47:19.310
Nämlich, wenn ich das auf die Seite bringe und teile durch f von Z,

47:19.610 --> 47:25.550
dann steht hier 1-Z-Z².

47:28.210 --> 47:29.750
Was haben wir hier gerade gezeigt?

47:30.730 --> 47:36.070
Wir haben eine Formel für die Potenzreihe gezeigt.

47:36.350 --> 47:37.390
Warum existiert denn sowas?

47:38.250 --> 47:40.890
Eine geschlossene Form für die Potenzreihe.

47:41.250 --> 47:42.910
Nun, ihr kennt alle eine geometrische Reihe.

47:43.510 --> 47:47.620
Die Summe von n gleich 0 bis unendlich.

47:48.570 --> 47:49.450
Z hoch n.

47:50.010 --> 47:51.170
Z hoch n.

47:51.990 --> 47:54.470
Ist 1 durch 1-Z.

47:56.110 --> 47:58.170
Genau sowas haben wir da oben auch gezeigt.

48:00.890 --> 48:05.390
Und diese Formel steht hier eigentlich auch schon nochmal drin.

48:06.270 --> 48:10.250
Wir werden jetzt versuchen, diese Formel wieder zu verwenden, um das

48:10.250 --> 48:11.570
zurück zu transformieren.

48:21.670 --> 48:25.810
Wir haben hier jetzt eine Potenzreihe.

48:26.930 --> 48:27.550
f von Z.

48:29.130 --> 48:32.550
Z durch 1-Z-Z².

48:33.350 --> 48:41.690
Und das Ziel wird jetzt in nächster Zeit sein, a durch 1-αz plus b

48:41.690 --> 48:46.070
durch 1-βz zu transformieren.

48:46.410 --> 48:50.550
Denn, wenn wir das geschafft haben, können wir diese Formel anwenden,

48:50.910 --> 48:52.470
um das zurück zu transformieren.

48:53.630 --> 48:56.270
Das α steht ja unten einfach als Klammern drin.

48:57.090 --> 48:58.170
Das ist ein Vorfaktor.

48:58.170 --> 49:03.210
Wenn wir diese Form in diese transformiert haben, dann können wir die

49:03.210 --> 49:07.730
geometrische Reihe verwenden, um das hier wieder als Potenzreihe

49:07.730 --> 49:08.350
darzustellen.

49:11.390 --> 49:14.990
Dieser Schritt, den habt ihr in der Schule schon x-mal durchgekaut,

49:15.110 --> 49:16.970
das ist eine Partialbruchzerlegung.

49:19.590 --> 49:25.770
Das machen wir jetzt im Schnelldurchlauf, gesappt, weil meine Kollegen

49:25.770 --> 49:26.630
wollen auch noch was sagen.

49:31.200 --> 49:33.040
Genau, Partialbruchzerlegung, hier steht übrigens nicht alles.

49:34.440 --> 49:35.700
Diese Partialbruchzerlegung wollen wir.

49:37.560 --> 49:40.460
Das ist der Nenner von dem, was ich da gerade gezeigt habe.

49:41.640 --> 49:44.960
Im Schnelldurchlauf, was macht man hier zuerst?

49:45.120 --> 49:47.560
Nun mal ein multipliziertes hier aus, dann gibt sich das da.

49:48.880 --> 49:51.180
Das findest du auch im Netz, das muss man nicht abschreiben.

49:52.080 --> 49:56.020
Dann hat man hier ganz normal ausmultipliziert, hat man so einen

49:56.020 --> 50:01.380
mittleren Term und den Termenpreis Quadrat, setzt man gleich zu dem

50:01.380 --> 50:02.900
oberen, wie macht man das?

50:02.960 --> 50:04.440
Man macht das mit Koeffizientenvergleich.

50:05.700 --> 50:10.000
Das bedeutet, im Prinzip muss hier eine 1, die da steht, 1 muss gleich

50:10.000 --> 50:11.180
dem hier sein.

50:11.580 --> 50:14.720
Und genauso muss das 1, also minus 1, was hier steht, gleich dem da

50:14.720 --> 50:14.940
sein.

50:15.220 --> 50:16.220
Das ist genau das, was hier steht.

50:17.440 --> 50:18.340
Ach so, das ist schon mal ein Minus.

50:19.260 --> 50:20.300
Verrechnet man sich sehr gerne.

50:21.860 --> 50:23.880
Okay, Partialbruchzerlegung, das ist die erste Beziehung in der

50:23.880 --> 50:24.820
Partialbruchzerlegung.

50:24.820 --> 50:26.020
Damit kann ich das lösen.

50:27.100 --> 50:30.020
Allerdings, wenn man das, also man dreht den hier um, setzt den dort

50:30.020 --> 50:32.580
ein, bekommt man das da, bekommt man allerdings eine quadratische

50:32.580 --> 50:33.040
Gleichung.

50:33.660 --> 50:35.980
Und diese quadratische Gleichung habt ihr in der Schule auch gelernt,

50:36.100 --> 50:38.080
wie man die löst, nämlich Mitternachtsformel.

50:38.920 --> 50:41.600
Und wir bekommen hier zwei Nullstellen für die Gleichung.

50:42.620 --> 50:44.980
Und das ist Alpha, das ist 1 plus Minus Wurzel 5 Halbe.

50:47.180 --> 50:49.280
So, wenn man sich da nicht verrechnet hat, kommt das raus.

50:50.660 --> 50:53.020
Diese Zahl heißt der goldene Schnitt.

50:55.180 --> 50:57.000
Immer wenn das auftaucht, ist es besonders.

50:57.320 --> 51:00.080
Wenn es außerhalb der Mathematik auftaucht, dann ist es meistens

51:00.080 --> 51:02.680
Zufall und hineininterpretiert, hier ist es kein Zufall.

51:05.080 --> 51:09.100
Die eine Nullstelle, da wo Plus steht, nennt man halt den einen

51:09.100 --> 51:11.080
goldenen Schnitt, da wo Minus steht, den anderen goldenen Schnitt.

51:11.760 --> 51:15.640
Wir nennen die jetzt erstmal 4, weil sonst muss ich dann weniger

51:15.640 --> 51:16.040
schreiben.

51:16.720 --> 51:19.760
Dieser goldenen Schnitt hat diese beiden Beziehungen und diese beiden

51:19.760 --> 51:23.400
schönen Beziehungen sind genau die, die wir als Koeffizienten hier

51:23.400 --> 51:24.180
drin brauchen.

51:26.340 --> 51:29.940
Allerdings brauchen wir noch Vorfaktoren, das A und das B.

51:31.480 --> 51:37.140
Und wenn man das halt ausmultipliziert und durchrechnet, bekommt man,

51:37.200 --> 51:41.200
das machen wir jetzt nicht, A und B ist 1 durch Wurzel 5, Minus 1

51:41.200 --> 51:41.940
durch Wurzel 5.

51:42.600 --> 51:43.800
Dürft ihr nachrechnen, wenn ihr wollt.

51:44.560 --> 51:46.780
Wichtig ist, wir haben eine Partialbruchzerlegung.

51:51.400 --> 51:53.300
Die geht im Übrigen natürlich auch immer.

51:58.460 --> 52:01.060
A ist 1 durch Wurzel 5.

52:02.720 --> 52:06.000
B ist Minus 1 durch Wurzel 5.

52:08.220 --> 52:09.220
Und der Rest gilt hier oben.

52:09.700 --> 52:11.320
Mein Alpha ist das Phi.

52:11.320 --> 52:16.060
Phi ist 1 plus Wurzel 5 halbe.

52:17.060 --> 52:19.320
Beta ist mein Vierdach.

52:22.960 --> 52:24.900
1 minus Wurzel 5 halbe.

52:26.020 --> 52:31.460
Setzt man hier oben ein und macht diese Rücktransformation, die ich

52:31.460 --> 52:32.740
euch gerade erklärt habe, nochmal.

52:34.440 --> 52:37.060
Ich habe jetzt raus F und Z.

52:37.060 --> 52:47.220
F und Z ist A, 1 durch Wurzel 5,

52:50.720 --> 52:56.640
mal 1 durch 1 Minus Phi Z.

53:00.060 --> 53:02.720
Minus 1 durch Wurzel 5.

53:03.820 --> 53:06.300
1 durch 1 Minus Phi Dach Z.

53:08.720 --> 53:10.100
Was haben wir jetzt gelernt?

53:10.100 --> 53:13.440
Noch erstmal nichts, aber wir können das hier einsetzen.

53:15.320 --> 53:16.260
Und das machen wir jetzt.

53:18.000 --> 53:28.260
1 durch Wurzel 5, mal die Summe, n gleich 0 bis unendlich, von Phi Z

53:28.260 --> 53:37.840
hoch n, Minus 1 durch Wurzel 5, Summe n gleich 0 bis unendlich von Phi

53:37.840 --> 53:40.280
Dach Z hoch n.

53:41.840 --> 53:44.320
Und das Ganze als eine Formel schreiben.

53:47.640 --> 53:53.520
Wir stopfen alles zusammen in eine einzige Potenzreihe.

53:54.520 --> 53:55.580
Das ist am geschicktesten.

53:59.200 --> 54:01.320
Ich nenne das jetzt einfach hier A.

54:02.700 --> 54:04.160
A Phi.

54:04.160 --> 54:04.200
A Phi.

54:08.860 --> 54:14.000
Plus B Phi Dach, hoch n, Z hoch n.

54:16.740 --> 54:18.720
Und jetzt gucken wir nochmal ganz am Anfang.

54:22.540 --> 54:26.540
F und Z ist die Potenzreihe von F und n, Z hoch n.

54:36.900 --> 54:42.000
Und daraus schließt man jetzt, und der Schluss gilt nicht, aber man

54:42.000 --> 54:45.040
kann die Vermutung anstellen, dass das stimmen könnte.

54:46.180 --> 54:48.560
Der Schluss gilt deswegen nicht, weil die möglicherweise nicht

54:48.560 --> 54:49.140
konvergieren.

54:49.780 --> 54:55.460
Aber man kann vermuten, dass F von n gleich A Phi plus B.

55:03.130 --> 55:04.590
Ne, das B stimmt schon.

55:08.700 --> 55:11.340
Ich darf hier nicht hoch die Klammer machen.

55:16.310 --> 55:17.330
Die Klammer stimmt.

55:19.150 --> 55:20.310
Das hier stimmt nicht.

55:21.730 --> 55:23.850
Also die Klammer stimmt schon, aber das n stimmt hier nicht.

55:24.570 --> 55:26.250
Ich kann ja nicht einfach die Klammer falsch gesetzt.

55:27.570 --> 55:30.190
Das Phi von n ist hier drin, das Z hoch n gilt hier.

55:30.610 --> 55:34.430
Das Z von n kann ich rausnehmen, dann bleibt hier aber Phi von n.

55:34.810 --> 55:36.450
Und das A ist das 1 durch Wurzel 5.

55:37.170 --> 55:37.570
Okay?

55:43.890 --> 55:46.410
Das ist aber nur eine Vermutung, das gilt nicht.

55:49.190 --> 55:51.970
Was man jetzt aber weiß, man hat diese Vermutung, die können wir auch

55:51.970 --> 55:52.570
mal ausschreiben.

55:52.690 --> 55:56.690
Das ist nämlich diese berühmte Formel für die Fibonacci-Zahlen.

55:56.790 --> 56:02.230
1 durch Wurzel 5 von 1 plus Wurzel 5 Halbe hoch n.

56:03.810 --> 56:05.650
Das kann ich ersetzen, hier steht ein Minus.

56:05.650 --> 56:08.930
Das B ist ja Minus 1 durch Wurzel 5.

56:09.830 --> 56:14.210
1 minus Wurzel 5 Halbe hoch n.

56:15.330 --> 56:17.550
Das ist diese berühmte Formel, die jetzt herausfällt.

56:19.470 --> 56:23.450
Doch das gilt nicht, aber wir können das, wenn wir die Vermutung

56:23.450 --> 56:25.190
haben, mit Induktion beweisen.

56:27.330 --> 56:29.470
Das ist die Formel, die hier herausgefallen ist.

56:30.530 --> 56:31.730
Ein bisschen verschönert.

56:32.470 --> 56:33.070
Induktionsanfang.

56:33.070 --> 56:36.370
Induktionsschritt, spare ich euch, könnt ihr nachrechnen.

56:37.050 --> 56:40.170
Stimmt, aber muss durchgeführt werden.

56:42.230 --> 56:45.470
Und das sind erzeugende Funktionen.

56:45.950 --> 56:51.630
Mit dieser Technik kann man fast alle lineare Rekursionsgleichungen

56:51.630 --> 56:52.030
lösen.

56:53.530 --> 56:58.210
Meistens geht es einfacher, aber mit dieser eleganten Methode kriegt

56:58.210 --> 56:59.250
man tatsächlich alle hin.

57:00.130 --> 57:00.890
Gut.

57:05.010 --> 57:07.410
So viel von meiner Seite.

57:08.690 --> 57:11.230
Jetzt kommt amortisierte Analyse, Sebastian.

57:12.110 --> 57:12.870
Ja,

57:19.830 --> 57:20.990
genau, es ist nicht legal.

57:22.250 --> 57:24.450
Nur wenn sie konvergiert, ist es legal.

57:25.810 --> 57:26.950
Absolut konvergiert sogar.

57:27.910 --> 57:30.910
Richtig, man ignoriert diese ganze Geschichte mit Konvergenz.

57:31.690 --> 57:36.390
Das ist eine Art Trickrechnen.

57:37.130 --> 57:40.710
Man macht eine Bijektion von den Potenzreihen auf die unendlichen

57:40.710 --> 57:41.110
Folgen.

57:43.610 --> 57:47.270
Und dann rechnet man da ohne Konvergenz rum und bekommt ein Ergebnis.

57:48.250 --> 57:50.130
Dieses Ergebnis ist nicht richtig.

57:51.930 --> 57:53.850
Aber man kann vermuten, dass es richtig ist.

57:55.990 --> 57:57.110
Und das dann zeigen.

57:58.630 --> 57:59.550
Das ist der Trick.

58:01.750 --> 58:02.350
Ja?

58:03.570 --> 58:05.290
Okay, ja.

58:06.770 --> 58:07.310
Bist du dran?

58:30.320 --> 58:34.980
Prof. Sanders hat ja eben schon angefangen, was über amortisierte

58:34.980 --> 58:35.800
Analyse zu erzählen.

58:36.060 --> 58:40.480
Und weil es eben so wichtig ist und auch hochgradig klausurrelevant,

58:43.020 --> 58:44.320
erzähle ich ein bisschen mehr darüber.

58:45.020 --> 58:49.640
Und zwar jetzt hier ein Beispiel von einem Binärzähler.

58:51.840 --> 58:55.320
Eine Zählvariable, die hochzählt von 0 bis M, aber eben in

58:55.320 --> 58:55.960
Binärdarstellung.

58:56.320 --> 58:57.500
Das sieht dann ungefähr so aus.

58:57.580 --> 58:59.520
Wir fangen an bei 0 und dann 1.

59:00.420 --> 59:02.700
Und ihr seht rechts die Zehnerdarstellung und links die

59:02.700 --> 59:03.320
Binärdarstellung.

59:04.200 --> 59:05.160
Das ist ziemlich trivial.

59:05.160 --> 59:15.040
Und allgemein hat man diese Stellen Beta i und im CS-System ist es die

59:15.040 --> 59:16.300
Summe über Beta i 2 hoch i.

59:18.020 --> 59:19.820
Wie könnte man das jetzt implementieren?

59:21.040 --> 59:22.920
Also ich habe mir jetzt so eine Implementierung überlegt.

59:23.180 --> 59:25.340
Diese Funktion BinaryIncrement.

59:26.500 --> 59:27.600
Was macht die genau?

59:28.300 --> 59:31.040
Naja, also im ersten Schritt addiert die halt einfach auf die erste

59:31.040 --> 59:32.060
Stelle mal 1 drauf.

59:32.780 --> 59:33.160
Klasse, ne?

59:34.240 --> 59:37.460
Und jetzt kann man sich ja überlegen, für diesen Binärzähler muss ja

59:37.460 --> 59:42.680
irgendwie gelten, dass diese ganzen Stellen, Beta i, eben alle 0 und 1

59:42.680 --> 59:42.900
sind.

59:43.380 --> 59:44.920
Und diese Invariante wird hierbei verletzt.

59:45.160 --> 59:46.820
Also es kann sein, dass das Beta 0 halt 2 wird.

59:47.620 --> 59:52.140
Und dafür braucht man jetzt diese Schleife unten drunter, die, falls

59:52.140 --> 59:56.680
dieses Beta 0 2 ist, eben diese Stelle auf 0 setzt und auf die nächste

59:56.680 --> 59:57.660
Stelle 1 drauf addiert.

59:59.120 --> 01:00:02.500
Und das macht so lange, bis halt alle Stellen wieder 0 und 1 sind.

01:00:03.160 --> 01:00:05.760
Und dass das irgendwann auch terminiert, davon könnt ihr euch

01:00:05.760 --> 01:00:06.320
überzeugen.

01:00:06.620 --> 01:00:08.180
Und das ist eigentlich ziemlich einfach einsehbar.

01:00:08.720 --> 01:00:09.840
Ich habe auch ein Beispiel mitgebracht.

01:00:11.240 --> 01:00:13.240
Wir addieren auf diese Zeit jetzt 1 drauf.

01:00:13.880 --> 01:00:15.240
Fangen wir mit der ersten Stelle hier an.

01:00:15.580 --> 01:00:16.680
Da wird ein 2 draus.

01:00:17.980 --> 01:00:19.340
Die wird ersetzt durch den 0.

01:00:19.880 --> 01:00:21.460
Und auf den nächsten Schritt wird 1 drauf addiert.

01:00:22.160 --> 01:00:24.260
Und dann schiebt sich halt die 2 hier immer so weiter durch.

01:00:26.120 --> 01:00:28.040
Bis, ja, irgendwann hier ein 1 dasteht.

01:00:29.720 --> 01:00:33.780
Jetzt haben wir uns von der Korrektheit des Verfahrens überzeugt.

01:00:34.540 --> 01:00:36.440
Jetzt schauen wir uns mal die Laufzeit an.

01:00:37.320 --> 01:00:39.720
Und zwar müssen wir uns erst mal überlegen, was zählen wir eigentlich

01:00:39.720 --> 01:00:40.380
bei einer Laufzeit.

01:00:41.600 --> 01:00:47.080
Und unser Modell hier ist, dass die teuerste Operation, sage ich mal,

01:00:47.560 --> 01:00:48.580
immer so ein Bitflip ist.

01:00:49.340 --> 01:00:50.080
Nehmen wir einfach mal an.

01:00:53.840 --> 01:00:57.060
Dann zählen wir halt hier die Anzahl der Bitflips, für dieses

01:00:57.060 --> 01:00:58.300
Beispiel, das ich gerade mitgebracht habe.

01:00:58.720 --> 01:01:01.120
Und wir sehen halt, dass das ziemlich viele sind.

01:01:01.300 --> 01:01:02.780
Das ist den O von Log M.

01:01:03.360 --> 01:01:04.560
Ich zähle von 0 bis M.

01:01:05.520 --> 01:01:08.940
Und beim Addieren von dieser Zahl brauche ich Log, also die Anzahl der

01:01:08.940 --> 01:01:10.180
Bitstellen, Schritte.

01:01:10.800 --> 01:01:11.340
Also Log M.

01:01:12.480 --> 01:01:14.440
Und das ist schon ein bisschen komisch, also unerwartet.

01:01:14.520 --> 01:01:18.920
Man könnte ja irgendwie sagen, dieses Addieren plus 1 ist eine atomare

01:01:18.920 --> 01:01:19.380
Operation.

01:01:21.600 --> 01:01:23.820
Warum hat dieses Worst-Case-Laufzeit-O von Log M?

01:01:23.920 --> 01:01:25.700
Das ist nicht so schön.

01:01:28.200 --> 01:01:32.280
Aber man kann halt eben zeigen, dass diese teuren Worst-Case

01:01:32.280 --> 01:01:37.840
-Operationen so selten sind, dass sie aufgewogen werden von den

01:01:37.840 --> 01:01:40.760
anderen, viel häufigeren, günstigeren Operationen.

01:01:41.040 --> 01:01:43.020
Und genau das macht eben die amortisierte Analyse.

01:01:48.300 --> 01:01:52.680
Wir nehmen jetzt weiterhin an, dass TM die Gesamtkosten für M

01:01:52.680 --> 01:01:56.800
-Operationen sind und die amortisierten Kosten, das stand eben schon

01:01:56.800 --> 01:02:00.720
auch an den Vorlesungsformulen, ist eben halt einfach dieses TM durch

01:02:00.720 --> 01:02:00.960
M.

01:02:02.060 --> 01:02:03.800
Und jetzt eine kleine Quizfrage.

01:02:05.260 --> 01:02:08.520
Die amortisierten Kosten für die Inkrement-Operationen, wer denkt,

01:02:08.640 --> 01:02:10.840
dass es in amortisiert O von 1 geht?

01:02:14.380 --> 01:02:17.100
Und wer denkt, dass es amortisiert O von Log M ist?

01:02:18.680 --> 01:02:20.280
Das ist jetzt gar keiner.

01:02:21.120 --> 01:02:24.440
Ja, also ist klar, O von Log M ist schon Worst-Case und ich habe

01:02:24.440 --> 01:02:27.760
gesagt, es ist besser, also wird es wohl O von 1 sein, amortisiert.

01:02:27.820 --> 01:02:28.920
Aber das müssen wir jetzt erstmal zeigen.

01:02:30.060 --> 01:02:34.360
Und es gibt im Wesentlichen zwei Methoden in der amortisierten

01:02:34.360 --> 01:02:35.860
Analyse, die man da durchführen kann.

01:02:36.780 --> 01:02:39.340
Das erste ist die Aggregatmethode und das zweite ist die

01:02:39.340 --> 01:02:40.120
Bankkontomethode.

01:02:40.920 --> 01:02:42.660
Und ich fange jetzt mal mit der Aggregatmethode an.

01:02:42.660 --> 01:02:47.320
Und was wir da machen wollen, ist eigentlich dieses T von M direkt

01:02:47.320 --> 01:02:47.660
auszurechnen.

01:02:48.660 --> 01:02:49.320
Das geht manchmal.

01:02:49.660 --> 01:02:50.440
In dem Fall geht es hier.

01:02:51.120 --> 01:02:53.960
Schauen wir uns erstmal an, was sind eigentlich die Kosten von den

01:02:53.960 --> 01:02:54.840
einzelnen Operationen?

01:02:55.620 --> 01:02:59.440
Die erste Operation von 0 auf 1 flippt nur ein Bit, also Kosten 1.

01:03:00.360 --> 01:03:03.440
Und dann die zweite Operation flippt schon zwei Bits und die dritte

01:03:03.440 --> 01:03:04.800
nur eins und so weiter eben.

01:03:05.760 --> 01:03:07.660
Aber das bringt uns nicht viel, was wir jetzt eigentlich machen.

01:03:07.660 --> 01:03:11.880
Wir schauen uns mal an, nicht pro Operation, sondern pro Stelle.

01:03:12.740 --> 01:03:15.220
Wie oft wird jede Stelle geflippt?

01:03:15.720 --> 01:03:20.480
Naja, also dieses Beta Null wird hier jedes Mal geflippt.

01:03:20.920 --> 01:03:22.700
Also bei M Operationen M Mal.

01:03:23.720 --> 01:03:28.200
Die zweite Stelle wird nur M halb Mal geflippt und die dritte Stelle

01:03:28.200 --> 01:03:29.440
nur M viertel Mal.

01:03:30.300 --> 01:03:33.300
Und wenn man das halt jetzt mal aufsummiert alles, kann man das nach

01:03:33.300 --> 01:03:35.600
oben abschätzen durch diese Summe hier.

01:03:35.600 --> 01:03:39.480
Und das ist eine geometrische Summe und das ist halt gerade 2M.

01:03:40.440 --> 01:03:43.220
Und wenn wir das jetzt teilen durch die einzelnen Operationen, kommt

01:03:43.220 --> 01:03:44.880
da 2 raus und das ist konstant.

01:03:45.460 --> 01:03:47.560
Dann haben wir halt gezeigt, dass es amortisiert konstant ist.

01:03:49.260 --> 01:03:50.840
Ich zeige jetzt mal eine zweite Methode.

01:03:51.240 --> 01:03:54.080
Das war auch die Methode, die in der Vorlesung heute drankam.

01:03:54.740 --> 01:03:57.720
Nämlich die sogenannte Bankkontomethode oder Kontomethode oder

01:03:57.720 --> 01:03:59.880
Versicherungsmethode eben.

01:04:02.200 --> 01:04:04.380
Das läuft so ein bisschen von der anderen Richtung ab.

01:04:05.600 --> 01:04:09.620
Und hier sehen wir die Laufzeiten der Operationen als Gebühren an, die

01:04:09.620 --> 01:04:13.740
der Algorithmus zu zahlen hat, um diese Operation durchzuführen.

01:04:14.480 --> 01:04:18.720
Und wir sagen dann, dass vor jeder Operation erhält der Algorithmus

01:04:18.720 --> 01:04:19.520
ein bestimmtes Gehalt.

01:04:20.700 --> 01:04:24.760
Und was wir zeigen wollen ist, dass der Algorithmus alle Operationen

01:04:24.760 --> 01:04:25.900
von diesem Gehalt bezahlen kann.

01:04:25.900 --> 01:04:29.660
Das heißt, er muss bei den günstigen Operationen ein Gehalt sparen,

01:04:29.720 --> 01:04:34.980
aus seinem Konto legen, um die teuren Operationen dann davon zu

01:04:34.980 --> 01:04:35.640
bezahlen zu können.

01:04:37.160 --> 01:04:39.940
Und was man halt machen muss, ist, er muss diesen Gehalt G finden und

01:04:39.940 --> 01:04:40.760
zeigen, dass es geht.

01:04:42.380 --> 01:04:44.320
Das machen wir jetzt mal genau für diese Bankkontomethode.

01:04:45.080 --> 01:04:52.960
Und zwar kann ich zeigen, dass man mit 2 Chips pro Inkrementoperation

01:04:52.960 --> 01:04:55.060
auskommt oder 2 Token, wie es in der Vorlesung hieß.

01:04:56.740 --> 01:04:58.160
Warum ist das so?

01:05:00.720 --> 01:05:05.780
Man kann sich überlegen, dass der Zählvorgang bei so einem Inkrement

01:05:05.780 --> 01:05:08.960
immer genau 1 Bit auf 1 setzt.

01:05:09.540 --> 01:05:13.500
Also mindestens und Maximum 1 Bit wird auf 1 gesetzt.

01:05:14.300 --> 01:05:17.320
Und diesen Flip zahlen wir halt mit einem Chip.

01:05:18.580 --> 01:05:20.840
Und man kann sich dann weiter überlegen, dass irgendwann dieses 1 auf

01:05:20.840 --> 01:05:21.860
0 gesetzt werden muss.

01:05:23.280 --> 01:05:26.280
Und mit dem zweiten Chip, den wir kriegen, den sparen wir, um

01:05:26.280 --> 01:05:27.500
irgendwann dieses Bit wieder auf 0 zu setzen.

01:05:31.400 --> 01:05:32.740
Und warum klappt das?

01:05:33.420 --> 01:05:37.600
Naja, man kann sich halt in der Invariante überlegen, dass der

01:05:37.600 --> 01:05:41.740
Kontostand, den man aktuell gespart hat, immer gleich die Anzahl der 1

01:05:41.740 --> 01:05:42.160
Bits ist.

01:05:43.000 --> 01:05:45.160
Und dann ist klar, wenn man halt irgendwann mal so eine teure

01:05:45.160 --> 01:05:47.700
Operation hat, wo man die ganzen 1 Bits auf 0 setzen muss, kann man

01:05:47.700 --> 01:05:48.420
das halt bezahlen.

01:05:48.420 --> 01:05:53.300
Und warum diese Invariante gilt, das kann man halt überweisen mit

01:05:53.300 --> 01:05:53.560
Induktionen.

01:05:54.100 --> 01:05:56.740
Das ist nämlich eine nette Übungsaufgabe, das könnte man probieren.

01:05:57.800 --> 01:05:58.600
Also es ist ziemlich einfach.

01:06:01.120 --> 01:06:04.840
Jetzt habe ich noch ein paar Plots mitgebracht, wo wir einfach mal für

01:06:04.840 --> 01:06:08.380
dieses Binary Increment die Kosten plotten.

01:06:09.000 --> 01:06:11.380
Hier erstmal die Kosten pro Operation.

01:06:12.380 --> 01:06:14.880
Da sieht man, es gibt ziemlich viele Operationen, die sehr günstig

01:06:14.880 --> 01:06:15.060
sind.

01:06:15.500 --> 01:06:18.220
Aber es gibt auch immer wieder welche, die halt teurer werden.

01:06:19.180 --> 01:06:21.100
Die eben logarithmisch ansteigen.

01:06:22.660 --> 01:06:23.900
Das bringt uns noch nicht so viel.

01:06:24.100 --> 01:06:27.800
Jetzt summieren wir mal die Kosten bis zu einem bestimmten M.

01:06:28.200 --> 01:06:32.540
Das ist quasi der Summenplot, also der Plot über die Summe von diesen

01:06:32.540 --> 01:06:33.720
vorliegenden Operationen.

01:06:33.820 --> 01:06:35.180
Da sieht man, es steigt schon ziemlich stark an.

01:06:35.360 --> 01:06:39.040
Aber halt, wie wir eben gezeigt haben mit der Analyse, können wir halt

01:06:39.040 --> 01:06:41.920
das begrenzen durch eine Gerade der Steigerung 2.

01:06:43.040 --> 01:06:44.140
Und es bleibt halt immer drunter.

01:06:44.740 --> 01:06:51.440
Wenn man jetzt einen Plot macht, wo dieses Tm durch M geteilt wird,

01:06:51.980 --> 01:06:55.020
sieht man auch klar, dass das hier immer durch 2 begrenzt ist.

01:06:55.920 --> 01:06:59.400
Genau, und das war jetzt das einfache Beispiel.

01:06:59.500 --> 01:07:01.240
Jetzt kommt noch ein anderes Beispiel und noch eine sehr interessante

01:07:01.240 --> 01:07:01.800
Datenstruktur.

01:07:02.380 --> 01:07:03.920
Da wird jetzt Sebastian ein bisschen mehr darüber erzählen.

01:07:22.490 --> 01:07:28.010
So, ich habe jetzt noch eine neue Datenstruktur mitgebracht, die wir

01:07:28.010 --> 01:07:29.450
quasi zusammen entwickeln wollen.

01:07:29.850 --> 01:07:31.750
Die nennt sich Hotlist-Datenstruktur.

01:07:31.870 --> 01:07:34.690
Die soll drei wesentliche Operationen unterstützen.

01:07:34.890 --> 01:07:37.930
Einmal einen Insert, was mir für einen Schlüssel und ein Datenelement

01:07:37.930 --> 01:07:42.030
das Datenelement zu diesem Schlüssel in der Datenstruktur ablegt.

01:07:42.030 --> 01:07:46.430
Ich habe eine Lookup-Funktion, die mir gegeben ein Schlüssel das

01:07:46.430 --> 01:07:48.030
Datenelement dazu wieder zurückliefert.

01:07:49.050 --> 01:07:51.970
Und eine Delete-Operation, die mir das Datenelement für einen gewissen

01:07:51.970 --> 01:07:52.750
Schlüssel löscht.

01:07:53.790 --> 01:07:57.370
Und was ich mit der Datenstruktur machen will, ich will jede dieser

01:07:57.370 --> 01:08:03.010
Operationen in amortisiert von Wurzelendzeit ausführen können.

01:08:04.110 --> 01:08:08.330
Und diese Datenstruktur benutzt im Wesentlichen zwei Arrays.

01:08:08.330 --> 01:08:12.130
Hier ein großes Array der Größe N und ein kleines Array der Größe

01:08:12.130 --> 01:08:12.710
Wurzel N.

01:08:13.350 --> 01:08:15.970
Und was man sich jetzt, bevor wir genau angucken, wie ich da Elemente

01:08:15.970 --> 01:08:18.770
einfüge, was man sich schon überlegen kann, wenn ich irgendwie in

01:08:18.770 --> 01:08:24.150
diesem großen Array hier Elemente drin habe, dann kann ich die

01:08:24.150 --> 01:08:26.290
Elemente dort nicht komplett unsortiert speichern.

01:08:26.390 --> 01:08:28.670
Weil wenn ich die komplett unsortiert speichern würde und müsste dort

01:08:28.670 --> 01:08:31.770
ein Element suchen für diesen Lookup, müsste ich ja einmal dieses

01:08:31.770 --> 01:08:35.010
ganze Ding durchlaufen und hätte damit schon eine Laufzeit von O von

01:08:35.010 --> 01:08:35.250
N.

01:08:35.650 --> 01:08:37.870
Wir wollen ja aber besser sein, wir wollen ja O von Wurzel N

01:08:37.870 --> 01:08:38.310
erreichen.

01:08:38.330 --> 01:08:41.390
Das heißt also, ich muss irgendwie diese Elemente in diesem großen

01:08:41.390 --> 01:08:42.810
Array hier sortiert vorhalten.

01:08:43.810 --> 01:08:44.850
In irgendeiner Art und Weise.

01:08:45.670 --> 01:08:50.370
Und wie wir das machen, schauen wir uns an mit der Operation Insert.

01:08:50.970 --> 01:08:52.550
Die hat im Wesentlichen zwei Fälle.

01:08:52.710 --> 01:08:57.770
Der einfache Fall ist, in diesem Wurzel N großen Array, was so meine

01:08:57.770 --> 01:08:59.870
Hotlist ist, ist noch Platz.

01:09:00.850 --> 01:09:03.990
Wenn ich also da noch Platz habe, dann füge ich hier einfach mein

01:09:03.990 --> 01:09:08.410
aktuelles Element ein, erhöhe den Zeiger, der mir zeigt, wo meine

01:09:08.410 --> 01:09:12.290
nächste freie Position ist und bin damit fertig.

01:09:12.450 --> 01:09:14.170
Ich habe also konstante Laufzeit.

01:09:16.050 --> 01:09:18.770
Der kompliziertere Fall ist, was passiert, wenn diese Hotlist jetzt

01:09:18.770 --> 01:09:19.690
hier mal voll ist.

01:09:20.830 --> 01:09:23.030
Was ich dann mache, ist folgendes.

01:09:23.090 --> 01:09:25.990
Ich sortiere diese Elemente in der Hotlist.

01:09:26.430 --> 01:09:29.750
Das werden wir noch in der Vorlesung sehen, dass wir N Elemente im

01:09:29.750 --> 01:09:32.850
Worst Case in O von N Log N Zeit sortieren können.

01:09:32.850 --> 01:09:36.810
Das heißt also, für diese Hotlist hier gilt, ich kann sie in Wurzel N

01:09:36.810 --> 01:09:38.790
Log Wurzel N Zeit sortieren.

01:09:39.570 --> 01:09:45.470
Und dann merge ich meine sortierte Liste mit diesen Elementen in

01:09:45.470 --> 01:09:45.990
dieser Liste.

01:09:46.610 --> 01:09:49.990
Und klar, bei der ersten Merge-Operation ist diese Liste hier leer.

01:09:51.290 --> 01:09:55.750
Und bei einer weiteren Merge-Operation habe ich also hier eine Folge

01:09:55.750 --> 01:09:58.850
von sortierten Elementen und meine Wurzel N Elemente sind auch

01:09:58.850 --> 01:09:59.310
sortiert.

01:10:00.030 --> 01:10:04.630
Und diese Zusammenführungs-Operation kann ich in linearer Zeit in der

01:10:04.630 --> 01:10:06.170
Summe der beiden Listenlängen machen.

01:10:06.350 --> 01:10:09.210
Das heißt also, in diesem Fall würde mich diese Zusammenführungs

01:10:09.210 --> 01:10:14.190
-Operation O von N plus Wurzel N kosten, was also in O von N liegt.

01:10:15.070 --> 01:10:17.790
Und somit ist die Gesamtlaufzeit in diesem zweiten Fall, in diesem

01:10:17.790 --> 01:10:19.270
teuren Fall, linear.

01:10:20.550 --> 01:10:23.370
Jetzt muss ich natürlich wieder ein Amortisierungs-Argument zeigen,

01:10:24.490 --> 01:10:28.150
dass amortisiert die Laufzeit konstant ist für so einen Insert.

01:10:28.910 --> 01:10:31.330
Und was man sich da überlegen kann ist, naja, wenn ich so eine

01:10:31.330 --> 01:10:34.670
Zusammenführungs -Operation gemacht habe, ist meine Hotlist ja wieder

01:10:34.670 --> 01:10:35.090
frei.

01:10:35.390 --> 01:10:39.010
Ich habe also Wurzel N Plätze wieder frei und die nächsten Wurzel N

01:10:39.010 --> 01:10:41.130
Operationen kann ich in konstanter Zeit machen.

01:10:42.230 --> 01:10:45.990
So eine Zusammenführungs-Operation an sich, haben wir ja gesagt, hat

01:10:45.990 --> 01:10:49.650
linearen Aufwand, also hat irgendwie Kosten C mal N.

01:10:50.410 --> 01:10:53.590
Und was ich jetzt also machen kann, auch wieder über diese Bankkonto

01:10:53.590 --> 01:10:57.330
-Methode ist, überlege mir okay, bei jedem Mal, indem ich ein Insert

01:10:57.330 --> 01:11:00.810
in diese Hotlist mache, spare ich C mal Wurzel N an.

01:11:02.050 --> 01:11:05.610
Was ich dann also habe, wenn die Hotlist voll ist, ich habe also genau

01:11:05.610 --> 01:11:10.930
C mal N gespart und kann also damit diese teure Merge-Operation

01:11:10.930 --> 01:11:13.490
amortisieren und bezahlen.

01:11:16.050 --> 01:11:19.790
Damit hätten wir die Insert-Operation geklärt und jetzt wird auch

01:11:19.790 --> 01:11:21.570
klar, wie dieser Lookup hier dann funktioniert.

01:11:22.690 --> 01:11:26.770
Wenn ich einen Key suche, dann schaue ich zunächst mal in diesem

01:11:26.770 --> 01:11:28.830
großen Area mit binärer Suche nach.

01:11:29.670 --> 01:11:32.930
Die ganzen Elemente sind ja sortiert, das heißt in logarithmischer

01:11:32.930 --> 01:11:35.470
Zeit kann ich rausfinden, ob mein gesuchtes Element da drin ist oder

01:11:35.470 --> 01:11:35.670
nicht.

01:11:36.650 --> 01:11:40.210
Und falls es nicht drin ist, dann suche ich diese Hotlist komplett,

01:11:40.370 --> 01:11:41.930
laufe einmal durch und suche da mein Element.

01:11:42.510 --> 01:11:47.630
Und somit komme ich dann hier auf die Laufzeit von O von Wurzel N für

01:11:47.630 --> 01:11:48.150
mein Insert.

01:11:50.390 --> 01:11:52.590
Was jetzt noch zu zeigen bleibt, ist das Delete.

01:11:53.830 --> 01:11:56.510
Da sieht es im Wesentlichen so aus, man kann sich vorstellen, ich habe

01:11:56.510 --> 01:11:58.690
jetzt nicht nur diese beiden Arrays, in denen die Datenelemente

01:11:58.690 --> 01:12:01.870
gespeichert sind, sondern für jedes Element auch noch ein Bit, was mir

01:12:01.870 --> 01:12:04.910
irgendwie sagt, ist das Element jetzt wirklich gerade valid oder habe

01:12:04.910 --> 01:12:05.530
ich es gelöscht.

01:12:05.530 --> 01:12:08.050
Also wenn das Bit 1 ist, dann nehme ich an, das Element ist in der

01:12:08.050 --> 01:12:08.850
Datenstruktur drin.

01:12:09.290 --> 01:12:11.850
Wenn das Bit 0 ist, sage ich, es ist gelöscht.

01:12:12.450 --> 01:12:15.230
Und was ich dann im Wesentlichen machen muss, ist naja, ich mache

01:12:15.230 --> 01:12:19.010
einen Lookup, suche das Element mit dem Key und setze dieses Bit

01:12:19.010 --> 01:12:19.790
einfach auf 0.

01:12:20.790 --> 01:12:24.770
Somit habe ich für den Delete-Fall hier auch wieder eine Laufzeit von

01:12:24.770 --> 01:12:25.570
O von Wurzel N.

01:12:27.590 --> 01:12:32.490
Was jetzt aber passiert ist, also es funktioniert, wenn ich nur wenige

01:12:32.490 --> 01:12:33.630
Lösch -Operationen habe.

01:12:34.030 --> 01:12:37.390
Wenn ich jetzt aber ganz oft lösche, dann kommt es ja vor, dass in

01:12:37.390 --> 01:12:40.450
dieser Datenstruktur hier ganz viele Elemente drin sind, die so ein

01:12:40.450 --> 01:12:41.510
valid Bit auf 0 haben.

01:12:41.930 --> 01:12:44.210
Und das macht mir dann natürlich mein Insert kaputt, weil ich die ja

01:12:44.210 --> 01:12:45.670
dann auch irgendwie immer mitschieben müsste.

01:12:46.210 --> 01:12:52.450
Das heißt, wenn ich mehr als O von 1 Lösch-Operationen zwischen zwei

01:12:52.450 --> 01:12:55.090
Merge -Schritten habe, muss ich die Datenstruktur wieder

01:12:55.090 --> 01:12:55.990
reorganisieren.

01:12:56.590 --> 01:12:58.970
Und das mache ich dann, indem ich einfach durch diese Listen durchgehe

01:12:58.970 --> 01:13:03.650
und alle Elemente, die dieses valid Bit auf 0 gesetzt haben, die werfe

01:13:03.650 --> 01:13:04.410
ich einfach raus.

01:13:05.350 --> 01:13:09.090
Und man kann dann mit dem gleichen Argument wie beim Insert zeigen,

01:13:09.170 --> 01:13:12.790
dass auch die Laufzeit hier amortisiert in O von Wurzel N ist.

01:13:14.670 --> 01:13:17.190
Somit haben wir also gesehen, diese Hotlist-Datenstruktur, wie am

01:13:17.190 --> 01:13:20.630
Anfang versprochen, liefert Insert und Delete in amortisiert O von

01:13:20.630 --> 01:13:21.450
Wurzel N Zeit.

01:13:21.450 --> 01:13:25.390
Und beim Lookup haben wir sogar im Worst Case eben hier O von Wurzel

01:13:25.390 --> 01:13:25.590
N.

01:13:27.810 --> 01:13:30.130
Es war es jetzt soweit zur amortisierten Analyse.

01:13:30.210 --> 01:13:34.590
Jetzt habe ich noch ein Beispiel mitgebracht zu dem Unbounded Array,

01:13:34.690 --> 01:13:36.470
was Professor Sanders gerade eingeführt hat.

01:13:37.930 --> 01:13:40.610
Und was wir jetzt machen wollen, wir wollen die Frage beantworten, wie

01:13:40.610 --> 01:13:45.530
viel Speicherplatz brauche ich gleichzeitig im Worst Case, um N

01:13:45.530 --> 01:13:46.650
Elemente zu speichern.

01:13:46.650 --> 01:13:51.650
Also gegebene beliebige Folge an Pushback und Popback Operationen.

01:13:52.550 --> 01:13:56.530
Wie viel Speicherplatz brauche ich im Worst Case für meine N Elemente?

01:13:57.370 --> 01:14:00.590
Und hier habe ich mal vier mögliche Antworten mitgebracht.

01:14:01.630 --> 01:14:07.610
A wäre 2N plus minus C, B 3N plus minus C, C 4N plus minus C und D

01:14:07.610 --> 01:14:12.510
sogar das Sechsfache von meiner Anzahl Elemente, die ich einfüge.

01:14:13.450 --> 01:14:14.190
Wie sieht es aus?

01:14:14.250 --> 01:14:15.030
Wer ist für A?

01:14:15.550 --> 01:14:16.550
Ich brauche so das Doppelte.

01:14:18.210 --> 01:14:19.070
Wer ist für B?

01:14:20.590 --> 01:14:21.570
Dreifachen Speicherplatz.

01:14:22.790 --> 01:14:23.710
Wer ist für C?

01:14:23.810 --> 01:14:25.050
Ich brauche viermal so viel.

01:14:26.850 --> 01:14:27.810
Und wer ist für D?

01:14:27.910 --> 01:14:29.330
Ich brauche sogar sechsmal so viel.

01:14:31.390 --> 01:14:31.930
Glaubt keiner?

01:14:32.090 --> 01:14:33.410
Okay, dann schauen wir mal, was passiert.

01:14:34.530 --> 01:14:36.690
Also schauen wir es uns jetzt hier live an.

01:14:36.690 --> 01:14:39.950
Ich habe mein anbaute Array, füge ein paar Elemente ein.

01:14:40.030 --> 01:14:42.870
Jedes Mal, wenn es voll wird, verdopple ich die Größe.

01:14:45.710 --> 01:14:49.450
Und jetzt kommen wir genau zu dem Punkt, mein Array ist wieder voll

01:14:49.450 --> 01:14:51.230
und jetzt wollen wir uns anschauen, was brauche ich?

01:14:52.330 --> 01:14:54.490
Wie viel Speicherplatz brauche ich, wenn ich jetzt gerade dieses

01:14:54.490 --> 01:14:56.590
Reallocate auf diese doppelte Größe mache?

01:14:57.730 --> 01:14:59.670
Wenn man sich das anschaut, ist das genau in diesem

01:14:59.670 --> 01:15:03.010
Vergrößerungsschritt hier, habe ich mein altes Array, das ist voll.

01:15:03.010 --> 01:15:07.050
Und ich habe das neue, was doppelt so groß ist und noch dieses neue

01:15:07.050 --> 01:15:07.830
Element hier eingefügt.

01:15:07.910 --> 01:15:11.110
Das heißt also gerade in dem Schritt während der Vergrößerung brauche

01:15:11.110 --> 01:15:14.950
ich schon mal 3n-1 Speicherzellen für mein Array.

01:15:15.450 --> 01:15:20.350
Das heißt also auch, dass wenn ich den maximalen Wert kenne für mein

01:15:20.350 --> 01:15:25.330
unbounded Array, dann ist in dem Fall ein bounded Array oftmals

01:15:25.330 --> 01:15:28.150
besser, weil ich dann eben schon mal hier einen Faktor 3 an

01:15:28.150 --> 01:15:29.390
Speicherplatz sparen kann.

01:15:31.150 --> 01:15:34.750
Also soweit, wie wir es uns jetzt aktuell angeguckt haben, die Leute,

01:15:34.830 --> 01:15:37.450
die Antwort B gesagt haben, wären richtig.

01:15:38.430 --> 01:15:39.230
Aber jetzt schauen wir mal weiter.

01:15:39.370 --> 01:15:41.050
Bisher haben wir ja nur Elemente eingefügt.

01:15:41.510 --> 01:15:43.570
Was passiert jetzt, wenn ich Elemente weiterhin...

01:15:44.730 --> 01:15:46.050
Ich will noch was sagen.

01:15:47.330 --> 01:15:49.470
Das hat aber Professor Sanders jetzt auch gerade in der Vorlesung

01:15:49.470 --> 01:15:50.110
schon angesprochen.

01:15:50.230 --> 01:15:52.650
Nämlich die Frage, warum schrumpfe ich dieses Array jetzt nicht

01:15:52.650 --> 01:15:53.550
einfach direkt wieder?

01:15:54.370 --> 01:15:58.010
Und die Antwort ist, ich weiß ja nicht, was in Zukunft passiert.

01:15:58.190 --> 01:16:01.550
Wenn ich es jetzt schrumpfen würde und hätte danach wieder ein

01:16:01.550 --> 01:16:05.430
Pushback, dann müsste ich ja wieder das Array vergrößern, wie der

01:16:05.430 --> 01:16:06.930
Kommilitone schon erwähnt hat vorhin.

01:16:07.430 --> 01:16:10.510
Und infolge von N solchen Push- und Popback-Operationen wird mir dann

01:16:10.510 --> 01:16:13.110
quadratische Laufzeit geben, was ich auf jeden Fall vermeiden will.

01:16:14.350 --> 01:16:16.570
Deswegen haben wir ja in der Vorlesung gehört, wir schrumpfen erst,

01:16:17.530 --> 01:16:21.450
wenn mein Füllstand nur noch ein Viertel der Kapazität des Arrays ist.

01:16:21.890 --> 01:16:28.130
Das heißt also, ich werfe jetzt ein paar Elemente wieder raus.

01:16:29.750 --> 01:16:33.550
Und jetzt sind wir genau kurz vor dem Zustand, ab dem ich ein

01:16:33.550 --> 01:16:34.490
Reallocate machen würde.

01:16:34.610 --> 01:16:37.890
Wenn ich jetzt hier die 11 rausschmeiße, das hier sind 16 Elemente,

01:16:37.970 --> 01:16:39.350
dann hätte ich nur noch genau 4 gefüllt.

01:16:39.570 --> 01:16:41.290
Dann würde ich also die Arraygröße halbieren.

01:16:43.490 --> 01:16:47.170
Und genau vor diesem Schrumpfen, also eins bevor ich schrumpfen würde,

01:16:47.550 --> 01:16:50.890
habe ich einen Platzverbrauch von 4n-1 Speicherstellen.

01:16:51.790 --> 01:16:54.830
Das heißt also, in dem Moment sind die Leute, die Antwort C gesagt

01:16:54.830 --> 01:16:56.930
haben, auf der richtigen Seite.

01:16:57.910 --> 01:17:00.390
Aber ist es jetzt die finale Antwort oder geht es noch weiter?

01:17:00.770 --> 01:17:03.150
Wenn wir jetzt noch einen Schritt weiter machen, nämlich wir führen

01:17:03.150 --> 01:17:08.090
dieses Reallocate tatsächlich aus, dann sehen wir, dass wenn

01:17:08.090 --> 01:17:11.190
irgendjemand jetzt die Antwort gesagt hätte, ja 6n plus minus C,

01:17:11.310 --> 01:17:12.490
derjenige wäre richtig gelegen.

01:17:13.370 --> 01:17:15.590
Was nämlich passiert ist, in dem Moment, in dem ich das Array

01:17:15.590 --> 01:17:19.990
schrumpfe, habe ich hier das alte Array, was ja meine Größe 4n hat.

01:17:20.730 --> 01:17:23.610
Und ich muss dieses neue auf Größe 2n allocieren.

01:17:23.730 --> 01:17:30.790
Das heißt also, in dem Moment habe ich Speicherplatz 6n Speicherzellen

01:17:30.790 --> 01:17:32.130
belegt.

01:17:33.350 --> 01:17:36.250
Und das Ganze gilt natürlich nur für den Fall, dass ich eine

01:17:36.250 --> 01:17:41.190
Speicherverwaltung habe, die mir keine Schrumpfoperation bietet, in

01:17:41.190 --> 01:17:43.490
der das Ganze ohne Kopieren funktioniert.

01:17:43.490 --> 01:17:46.290
In dem Fall, ich habe ja immer hier gezeigt, oder in dem Beispiel

01:17:46.290 --> 01:17:49.610
hier, funktioniert das Schrumpfen ja nur dadurch, dass ich dieses neue

01:17:49.610 --> 01:17:54.110
Array einlege und die alten Elemente rüber kopiere.

01:17:54.450 --> 01:17:56.970
Wenn ich schrumpfen kann, ohne dass ich das neue Array anlege, dann

01:17:56.970 --> 01:17:58.750
ist der Speicherverbrauch hier natürlich geringer.

01:18:03.280 --> 01:18:07.240
Und in der Vorlesung wurde es ja auch schon erwähnt, wir haben diese

01:18:07.240 --> 01:18:09.540
zwei Konstanten, mit denen wir spielen können.

01:18:09.540 --> 01:18:12.540
Einmal, wenn mein Array voll ist, um wie viel vergrößere ich es?

01:18:13.220 --> 01:18:17.380
Und ab welchem Rest-Füllstand lasse ich es wieder schrumpfen?

01:18:18.640 --> 01:18:21.800
Und damit kriegt man so einen gewissen Trade-off zwischen der

01:18:21.800 --> 01:18:24.260
Geschwindigkeit und dem Platzverbrauch, den ich hier habe.

01:18:25.380 --> 01:18:28.500
Und das lässt sich eben regeln über diesen Vergrößerungsfaktor Beta,

01:18:28.740 --> 01:18:30.460
der war bei uns hier 2.

01:18:30.660 --> 01:18:34.380
Wenn mein Array voll war, dann habe ich ein neues Array angelegt, was

01:18:34.380 --> 01:18:35.700
die doppelte Größe hatte.

01:18:36.660 --> 01:18:42.700
Und diese Füllstandschranke Alpha, die bei uns 4 war, in dem Moment,

01:18:42.760 --> 01:18:45.680
in dem ich nur noch ein Viertel meines Arrays belegt habe, habe ich

01:18:45.680 --> 01:18:46.920
die Arraygröße halbiert.

01:18:48.240 --> 01:18:51.240
Und in der verallgemeinerten Version sieht es dann eben so aus, dass

01:18:51.240 --> 01:18:58.100
ich sagen kann, ich realoziere auf die Größe Beta mal n und ich

01:18:58.100 --> 01:19:07.900
verkleinere, wenn mein aktueller Füllstand Alpha mal n kleiner als die

01:19:07.900 --> 01:19:11.300
Array -Kapazität ist, dann reduziere ich das Array um die Hälfte.

01:19:12.960 --> 01:19:15.980
Und was man zeigen kann, ist, dass die amortisierten Laufzeiten

01:19:15.980 --> 01:19:20.220
asymptotisch gleich bleiben, wenn Beta Größe 1 ein Alpha-größer Beta

01:19:20.220 --> 01:19:20.520
ist.

01:19:21.080 --> 01:19:23.800
Und was man sich überlegen kann, ist na gut, wenn ich jetzt Alpha und

01:19:23.800 --> 01:19:28.680
Beta größer mache, dann bin ich schneller, da ich ja mehr auf

01:19:28.680 --> 01:19:32.420
konstante Zeitoperationen machen kann, bevor ich jetzt ein Reallocate

01:19:32.420 --> 01:19:33.960
machen muss.

01:19:34.520 --> 01:19:36.880
Aber ich habe eben auch mehr Speicherplatzverbrauch.

01:19:37.640 --> 01:19:42.880
Und ganz analog dazu, wenn ich Beta und Alpha kleiner mache, dann bin

01:19:42.880 --> 01:19:47.380
ich langsamer, habe aber dafür weniger Speicherverbrauch als diese 6n,

01:19:47.600 --> 01:19:48.980
die wir in unserem Beispiel gesehen haben.

01:19:49.900 --> 01:19:50.640
Das war es auch von mir.