WEBVTT 00:07.610 --> 00:12.750 So, willkommen zu uns angeguckt, was verstehen wir unter dem 00:12.750 --> 00:13.450 Sortierproblem. 00:16.510 --> 00:22.370 Da war dann die Hauptschwierigkeit zu definieren, was bedeutet... 00:22.370 --> 00:27.950 Wenn ich das in der Prüfung frage oder wenn ich Leuten sage, schreiben 00:27.950 --> 00:29.470 Sie mal einen Checker für Sortieren. 00:30.390 --> 00:33.250 Ja, also der überprüft, dass das, was Sie auch machen, korrekt ist. 00:33.970 --> 00:37.390 Ich wette, zwei Drittel der Leute vergessen zu überprüfen, dass es 00:37.390 --> 00:38.530 auch eine Permutation ist. 00:41.170 --> 00:44.950 Den Algorithmus hinschreiben, der gegeben eine Eingabefolge E1 bis 00:44.950 --> 00:48.210 Enne, eine Ausgabe produziert mit der Eigenschaft, ist ganz einfach. 00:48.210 --> 00:52.230 Vor i gleich 1 zu N, Si gleich E1. 00:53.630 --> 00:55.150 Ist nur leider keine Permutation. 00:57.470 --> 00:58.550 Immer darauf achten. 01:00.790 --> 01:02.490 Gut, Anwendungsbeispiele gibt es mengenmäßig. 01:03.010 --> 01:04.570 Ich hoffe, davon habe ich Sie überzeugt. 01:07.780 --> 01:09.900 Aha, wir haben hier ein Empfangsproblem. 01:11.500 --> 01:14.600 Ist doch zu weit weg, die Fernsteuerung, oder um die Ecke. 01:15.640 --> 01:18.540 Gucken wir mal, dass wir den Rechner ein bisschen woanders hinstellen 01:18.540 --> 01:18.860 können. 01:19.680 --> 01:20.180 Ja. 01:22.680 --> 01:24.680 Vielleicht einfach den Rechner hier draufstellen. 01:34.100 --> 01:34.420 Okay. 01:36.620 --> 01:39.560 Wie gesagt, es gibt viele Beispiele auch aus dem Buch oder dieser 01:39.560 --> 01:40.320 Vorlesung. 01:41.340 --> 01:43.620 Wir hatten dann angefangen mit Insertion Sort. 01:44.200 --> 01:45.540 Das ist wirklich sehr einfach. 01:47.040 --> 01:48.340 Am besten merkt man sich das Bild. 01:48.420 --> 01:51.460 Wir haben eine Invariante, dass im Iden Schritt die ersten I-Elemente 01:51.460 --> 01:52.140 sortiert sind. 01:52.140 --> 01:57.400 Und dann muss ich jeweils ein Element nehmen und hier einordnen. 02:00.200 --> 02:05.280 Da hat übrigens ein Kommilitone schon richtig angemerkt, man kann 02:05.280 --> 02:09.800 Insertion Sort relativ einfach so implementieren, dass man nur O von N 02:09.800 --> 02:16.160 log N Vergleiche braucht, indem man eine binäre Suche verwendet, um 02:16.160 --> 02:20.640 die Position von dem grünen in dem roten Bereich zu identifizieren. 02:20.640 --> 02:23.180 Also man kann ausnutzen, dass das hier bereits sortiert ist. 02:25.900 --> 02:29.680 Allerdings macht man das im Allgemeinen nicht, sondern man macht hier 02:29.680 --> 02:30.420 sowas Naives, 02:33.840 --> 02:36.140 weil einem das asymptotisch nichts bringt. 02:36.220 --> 02:39.640 Man muss ja weiterhin die Elemente verschieben in dem Array. 02:41.340 --> 02:43.700 Beziehungsweise wenn es eine verkettete Liste wäre, nützt es auch 02:43.700 --> 02:46.620 nichts, weil da kann man nicht binäre Suche darin machen. 02:47.360 --> 02:51.240 Und außerdem gibt es eigentlich zwei Hauptanwendungen in der Praxis 02:51.240 --> 02:52.140 von Insertion Sort. 02:52.160 --> 02:55.880 Das ist entweder, wenn die Eingabe ganz klein ist, dann bringt binäre 02:55.880 --> 03:00.140 Suche auch nichts, weil das irgendwie komplizierter ist und man dann 03:00.140 --> 03:02.620 wieder konstante Faktoren an einer anderen Stelle verliert. 03:03.200 --> 03:05.800 Oder wenn die Eingabe bereits fast sortiert ist. 03:06.460 --> 03:10.000 Aber dann ist die binäre Suche auch nicht gut, weil man braucht dann 03:10.000 --> 03:11.240 immer diese Log N Schritte. 03:12.040 --> 03:17.900 Während im Best Case braucht unser naives Verfahren nur lineare Zeit, 03:18.140 --> 03:21.500 während das mit binärer Suche würde hier dann im Best Case wieder N 03:21.500 --> 03:22.160 Log N brauchen. 03:26.300 --> 03:30.240 Jetzt wollen wir uns ein viel effizienteres Verfahren anschauen, das 03:30.240 --> 03:33.500 auch im schlechtesten Fall mit O von N Log N Schritten auskommt. 03:35.060 --> 03:38.060 Wie wir gesehen haben, ist das was anderes als O von N Log N 03:38.060 --> 03:39.960 Elementvergleiche. 03:42.800 --> 03:47.020 Und das ist ein Teile-und-Herrsche-Algorithmus, der sich Merge Sort 03:47.020 --> 03:47.440 nennt. 03:47.660 --> 03:50.140 Also gegeben meine Eingabefolge der Länge N. 03:51.840 --> 03:56.800 Im Teile-und-Herrsche brauche ich im An-Basis-Fall N gleich 1. 03:57.460 --> 03:59.380 Dann ist es schon sortiert, bin ich fertig. 04:01.020 --> 04:05.200 Sonst mische ich die erste Hälfte, ich mische die zweite Hälfte. 04:06.340 --> 04:09.560 Dann kriege ich zwei sortierte Folgen, hier wieder das Blaue und das 04:09.560 --> 04:09.820 Rote. 04:11.980 --> 04:15.220 Ich sortiere die erste Hälfte, ich sortiere die zweite Hälfte. 04:15.700 --> 04:19.120 Und jetzt habe ich zwei sortierte Folgen und will daraus eine global 04:19.120 --> 04:20.120 sortierte Folge machen. 04:20.200 --> 04:20.980 Das nennt man mischen. 04:22.040 --> 04:23.100 Also was ist mischen? 04:23.180 --> 04:26.220 Gegeben zwei sortierte Folgen, berechne eine sortierte Folge der 04:26.220 --> 04:27.360 Elemente aus A und B. 04:28.460 --> 04:32.480 Und der Trick ist, das geht viel schneller als das ursprüngliche 04:32.480 --> 04:33.080 Sortierproblem. 04:36.300 --> 04:38.960 Aber jetzt gucken wir uns erstmal ein Beispiel an. 04:39.060 --> 04:44.220 Wenn wir die Folge 2718281, also wenn man hier das Komma lässt und die 04:44.220 --> 04:46.660 anderen weglässt, ist das gerade die Eulersche Zahl oder die ersten 04:46.660 --> 04:47.300 Ziffern davon. 04:50.800 --> 04:55.180 Nimm die erste Hälfte und die zweite Hälfte, wenn das nicht genau 04:55.180 --> 04:56.460 aufgeht, wird halt gerundet. 04:58.860 --> 05:02.280 Sortiere rekursiv, naja, jetzt wird weiter aufgespalten, rekursiv. 05:02.280 --> 05:08.200 Zum Beispiel die zweite Hälfte, 8281, wir haben 8281 aufgespalten, die 05:08.200 --> 05:10.360 82 jetzt in 8 und 2. 05:10.560 --> 05:12.580 So, jetzt, das sind alles Basisfälle hier. 05:14.180 --> 05:21.080 Jetzt, wenn ich aus der Rekursion zurückkomme, bei Mergesort ist der 05:21.080 --> 05:24.520 schwierige Fall bei Teile und Herrsche der Herrscheteil. 05:24.660 --> 05:29.060 Teilen wird trivial gemacht, aber für das Herrschen muss ich was tun. 05:30.120 --> 05:36.500 Naja, aber die sortierte Folge von 8 und 2 ist 28, 8 und 1 ist 18, 7 05:36.500 --> 05:37.620 und 1 ist 17. 05:38.660 --> 05:44.880 So, jetzt habe ich hier zwei Folgen der Länge 2, 2818, das in 05:44.880 --> 05:46.060 sortierter Reihenfolge ist 1288. 05:47.860 --> 05:53.520 Hier ist es jetzt so, da nehme ich direkt das, was von da kam, 127 und 05:53.520 --> 05:55.960 ganz zum Schluss habe ich diese beiden Folgen, muss die 05:55.960 --> 05:56.180 zusammenmischen. 05:57.000 --> 05:59.860 Jetzt müssen wir uns etwas näher angucken, wie das Mischen geht. 05:59.940 --> 06:01.520 Ich habe ja behauptet, das geht effizient. 06:03.540 --> 06:05.040 Naja, das ist ganz einfach. 06:06.660 --> 06:10.400 Die Anzahl Schritte, die wir machen, ist Summe der Längen der beiden 06:10.400 --> 06:11.580 zu mischenden Folgen. 06:12.380 --> 06:18.000 In jedem Schritt gucken wir uns das erste Element der beiden Folgen an 06:18.000 --> 06:23.320 und vergleichen die beiden und das kleinere davon schieben wir in die 06:23.320 --> 06:24.020 Ausgabe. 06:26.500 --> 06:31.380 Also zwei Eingaben A und B, Ausgabe C, am Anfang ist die Ausgabe leer. 06:36.670 --> 06:39.810 Diese Fernsteuerung hat ein ganz tolles Feature, man kann die 06:39.810 --> 06:45.630 Intensität des Lasers steuern durch die Druckstärke, aber leider kommt 06:45.630 --> 06:47.870 man, wenn man das macht, auch manchmal auf andere Tasten. 06:48.030 --> 06:49.550 Ich bin da nicht so happy mit. 06:51.470 --> 06:55.930 Also hier die beiden, 1, 1, dann ist es egal, dann nehmen wir das A, 06:56.070 --> 06:59.770 das Minimum ist eine 1, wird in die Ausgabe geschoben und aus A 06:59.770 --> 07:00.470 entfernt. 07:01.350 --> 07:05.470 Jetzt gucke ich wieder die beiden ersten Elemente an, 2 und 1, das 07:05.470 --> 07:09.510 Minimum ist 1, das kommt aus B, wird in die Ausgabe geschoben. 07:09.510 --> 07:11.050 Dann habe ich hier mein 1, 1, 07:15.730 --> 07:18.070 irgendwie die Taste ist inzwischen kaputt. 07:22.680 --> 07:24.220 Jetzt haben wir wieder keinen Pointer. 07:29.360 --> 07:31.820 Also diese Taste funktioniert nicht richtig. 07:32.140 --> 07:33.460 Habt ihr einen anderen da? 07:34.880 --> 07:36.500 Müssen wir mal gucken, ob wir damit leben. 07:37.440 --> 07:43.340 Gut, 1, 2, 1... Scheiß Teil. 07:47.800 --> 07:51.160 Das ist so diese Logitech Pointer, ich brauche da immer etwa eine 07:51.160 --> 07:53.240 Woche, danach funktionieren die Tasten nicht mehr. 07:53.580 --> 07:56.100 Obwohl das eine komplett andere Technik ist als die, die ich vorher 07:56.100 --> 07:56.360 hatte. 07:57.320 --> 07:58.700 Ich weiß nicht, was damit los ist. 07:59.480 --> 08:01.800 Gut, jetzt haben wir hier 2, 2. 08:02.460 --> 08:04.520 Teilbreaking nehme ich immer die erste Folge. 08:10.180 --> 08:13.200 Der Batterieanzeiger steht auf voll, also es kann nicht dran liegen, 08:13.360 --> 08:15.200 dass die Batterie leer ist eigentlich. 08:25.550 --> 08:29.310 Wenn er aus war, geht er einmal an und dann verschwindet er. 08:35.310 --> 08:38.210 Dann versuche ich jetzt mit dem Mauszeiger vorzulesen. 08:40.690 --> 08:42.070 Sehen Sie mich nur von hier. 08:42.990 --> 08:45.510 Also, wir haben die 2, 2. 08:46.610 --> 08:49.430 Dann schieben wir die aus A hier hin. 08:51.610 --> 08:53.910 Jetzt bleibt noch 7, 2, 8, 8. 08:53.990 --> 08:56.150 Aha, die 2 ist kleiner, dann kommt die hier hin. 08:57.410 --> 08:59.550 Jetzt ist die 7 kleiner, die kommt hier hin. 09:00.050 --> 09:03.570 Und jetzt, wenn eine der Folgen leer ist, kann man sich überlegen, wie 09:03.570 --> 09:04.490 man damit umgeht. 09:05.730 --> 09:08.990 Eine Möglichkeit ist zu sagen, dann brechen wir ab und konkatenieren 09:08.990 --> 09:10.610 einfach den Rest in die Ausgabe. 09:22.320 --> 09:25.420 Analyse, naja gut, das ist ein Teil- und Herrscheralgorithmus. 09:25.580 --> 09:28.340 Wir können im Wesentlichen das Mastertheorem anwenden. 09:28.680 --> 09:32.900 Also die Ausführungszeit für Eingabegröße n ist lineare Zeit für das 09:32.900 --> 09:38.660 Mischen plus im Wesentlichen 2 mal T von n halber. 09:38.660 --> 09:41.820 Genauer gesagt muss ich einmal aufrunden, einmal abrunden. 09:42.820 --> 09:46.680 Wenn man das jetzt genau machen will für beliebige Eingabegrößen, 09:47.220 --> 09:51.160 steht im Buch, wie man das durch genaueres Rechnen hinkriegen kann. 09:52.600 --> 09:56.940 Eine andere Sichtweise, die ich jetzt für die Vorlesung attraktiver 09:56.940 --> 10:01.400 finde, ist zu sagen, naja, wir wären ja jederzeit in der Lage, die 10:01.400 --> 10:05.860 Eingabe aufzublasen auf die nächste Zweierpotenz und dann zum Beispiel 10:05.860 --> 10:08.480 unendlich große Werte da dran zu hängen. 10:11.520 --> 10:15.260 Dadurch wird die Eingabe nur einen konstanten Faktor größer und dann 10:15.260 --> 10:19.000 ist das Mastertheorem anwendbar und ich bleibe bei O von n log n. 10:26.620 --> 10:30.800 So, jetzt haben wir ein Verfahren, das mit O von n log n vergleichend 10:30.800 --> 10:31.460 auskommt. 10:33.500 --> 10:36.560 Jetzt würde man ja eigentlich gerne Linearzeit haben. 10:36.640 --> 10:37.280 Kann ich das? 10:37.580 --> 10:39.860 Und in gewisser Weise geht das nicht. 10:40.360 --> 10:44.660 Wir werden jetzt zeigen unter bestimmten Annahmen, dass man diese O 10:44.660 --> 10:46.520 von n log n Schritte auch wirklich braucht. 10:47.320 --> 10:50.680 Und untere Schranken sind in der Informatik immer was Schwieriges. 10:51.000 --> 10:55.240 Die Unmöglichkeit einer Verbesserung zu zeigen ist schwierig, weil sie 10:55.240 --> 10:58.400 eine Aussage erfordert über alle denkbaren Algorithmen. 10:59.080 --> 11:02.540 Und das ist halt im Allgemeinen sehr schwierig. 11:03.000 --> 11:07.100 Deshalb hängen untere Schranken meistens mit einschränkenden Annahmen 11:07.100 --> 11:07.560 zusammen. 11:08.160 --> 11:12.160 Die Annahme, die wir hier machen, ist, wir machen vergleichsbasiertes 11:12.160 --> 11:12.660 Satiren. 11:12.700 --> 11:16.620 Das heißt, wir gewinnen Informationen über die Elemente der Eingabe 11:16.620 --> 11:18.800 nur durch zwei Wegevergleiche. 11:19.040 --> 11:21.920 Das ist Element i kleiner gleich Element j. 11:23.020 --> 11:27.060 Das ist die einzige Operation, zwei Eingabeelemente miteinander zu 11:27.060 --> 11:27.400 vergleichen. 11:28.400 --> 11:29.500 Wir dürfen die nicht addieren. 11:30.500 --> 11:34.260 Wir dürfen nicht die Bits eines Schlüssels extrahieren und mit denen 11:34.260 --> 11:34.840 was tun. 11:35.280 --> 11:37.360 Das sind alles sinnvolle Dinge, die man tun kann. 11:37.580 --> 11:40.080 Aber wir betrachten nur Algorithmen, die das nicht dürfen. 11:40.880 --> 11:43.620 Allerdings ist das bereits eine riesige Klasse von Algorithmen. 11:44.620 --> 11:49.200 Und die haben auch aus softwaretechnischer Sicht ihre Vorzüge. 11:50.620 --> 11:53.620 Weil vergleichsbasierte Algorithmen passen sehr gut in eine 11:53.620 --> 11:54.400 Algorithmenbibliothek. 11:55.120 --> 11:59.720 Weil die funktionieren für beliebige Schlüsseltypen. 12:00.420 --> 12:06.100 Die einzige Anforderung ist, dass es eben diese Operation kleiner 12:06.100 --> 12:06.740 gleich gibt. 12:07.100 --> 12:10.040 Die die algebraischen Eigenschaften einer totalen Ordnung haben. 12:11.700 --> 12:17.660 Wir werden beweisen, jeder deterministische vergleichsbasierte 12:17.660 --> 12:24.400 Sortieralgorithmus braucht N log N minus O von N Vergleiche. 12:25.200 --> 12:26.280 Im schlechtesten Fall. 12:27.000 --> 12:31.300 Das schließt nicht aus, dass er nicht bei bestimmten einfachen 12:31.300 --> 12:33.140 Eingaben weniger Vergleiche braucht. 12:33.700 --> 12:36.760 Es schließt auch nicht aus, dass es vielleicht einen randomisierten 12:36.760 --> 12:38.820 Algorithmus geben könnte, der schneller ist. 12:38.820 --> 12:42.460 Allerdings gibt es einen Satz, den wir hier nicht beweisen, der aber 12:42.460 --> 12:43.460 so ähnlich funktioniert. 12:43.980 --> 12:47.840 Der zeigt, dass deterministisch ist hier keine Einschränkung. 12:48.120 --> 12:52.040 Also irgendwie Zufall oder auch im Mittel hilft einem gar nichts. 12:52.940 --> 12:54.640 Dann bleibt man bei dieser Schranke. 12:57.280 --> 13:00.540 Wir beweisen das jetzt für spezielle Eingaben. 13:00.820 --> 13:02.740 Ich meine, damit mache ich das Problem nur einfacher. 13:03.360 --> 13:05.940 Und zwar per Mutationen der Zahlen 1 bis N. 13:05.940 --> 13:09.420 Selbst da ist das der Fall, wenn man vergleichsbasiert arbeitet. 13:12.240 --> 13:16.360 Und eine wichtige Beobachtung dabei ist, es gibt N-Fakultät per 13:16.360 --> 13:19.100 Mutationen der Zahlen 1 bis N. 13:19.700 --> 13:21.100 Und das nutzen wir jetzt aus. 13:22.220 --> 13:26.920 Und außerdem schauen wir uns jetzt eine sehr abstrakte Repräsentation 13:26.920 --> 13:28.880 unserer vergleichsbasierten Algorithmen an. 13:29.460 --> 13:30.860 Das ist auch entscheidend. 13:31.700 --> 13:35.360 Ich habe ja gesagt, um untere Schranken zu zeigen, muss man Aussagen 13:35.360 --> 13:37.380 über alle denkbaren Algorithmen machen. 13:38.040 --> 13:41.420 Da wäre es jetzt sehr kompliziert zu sagen, aha, wir gucken uns die 13:41.420 --> 13:44.820 Menge aller Java-Programme an, die Sortieralgorithmen sind. 13:45.160 --> 13:47.460 Das könnte ja alles Mögliche sein. 13:47.560 --> 13:50.920 Da gibt es ja neben den Vergleichen irgendwelche Kontrollstrukturen, 13:51.300 --> 13:55.560 Datenstrukturen, Prozeduraufrufe, keine Ahnung. 13:56.900 --> 13:59.760 Und da jetzt Aussagen über alle Programme zu machen, ist schwierig. 13:59.760 --> 14:04.600 Aber der Trick ist, wir abstrahieren von dem ganzen Zeug drumherum und 14:04.600 --> 14:05.980 gucken uns nur die Vergleiche an. 14:09.060 --> 14:12.520 Und wir nutzen auch jetzt aus, dass es ein deterministisches Programm 14:12.520 --> 14:12.800 ist. 14:13.060 --> 14:18.260 Und egal, ob das in C oder in Java programmiert ist, wenn es ein 14:18.260 --> 14:23.260 deterministisches Programm ist, gibt es genau zwei Elemente der 14:23.260 --> 14:26.000 Eingabe, die ich zuerst vergleiche. 14:27.180 --> 14:37.820 Und die schreibe ich jetzt in den Wurzel eines sogenannten 14:37.820 --> 14:38.140 Entscheidungsbaums. 14:40.140 --> 14:44.500 Und natürlich ist es so, ich weiß nicht, was mein Algorithmus tut in 14:44.500 --> 14:46.020 Abhängigkeit von diesem Vergleich. 14:47.120 --> 14:52.200 Aber es ist klar, in einem deterministischen Algorithmus, wenn das 14:52.200 --> 14:57.860 Ergebnis kleiner gleich ist, ist wieder genau vorgegeben, was dann 14:57.860 --> 14:58.280 passiert. 14:58.420 --> 15:00.420 Das heißt, es gibt dann einen zweiten Vergleich. 15:01.880 --> 15:05.540 Hier ein möglicher Entscheidungsbaum wäre E2, E3. 15:05.700 --> 15:09.900 Also hier repräsentiere ich einen konkreten Algorithmus zum Sortieren 15:09.900 --> 15:11.300 mit so einem Entscheidungsbaum. 15:11.300 --> 15:17.060 Und naja, wenn das Ergebnis des ersten Vergleichs größer war, dann ist 15:17.060 --> 15:18.980 wieder genau vorgegeben, was passiert. 15:20.160 --> 15:23.940 In diesem Beispiel würde dann E2 mit E3 verglichen und so weiter. 15:25.120 --> 15:27.140 Also wir haben einen Baum, der ist riesig. 15:29.520 --> 15:34.300 Für eine gegebene Eingabegröße wächst die Größe mehr als exponentiell 15:34.300 --> 15:41.760 mit der Anzahl, mit der Eingabegröße. 15:43.380 --> 15:47.480 Also wir blasen unser Programm sozusagen auf, machen aber die Struktur 15:47.480 --> 15:48.320 viel einfacher. 15:48.660 --> 15:51.280 Und es gibt auch keinen Zeitpunkt, wo wir jetzt diesen 15:51.280 --> 15:53.100 Entscheidungsbaum im Rechner speichern müssen. 15:53.100 --> 15:55.620 Das ist einfach ein Werkzeug für einen Beweis. 15:56.920 --> 15:59.460 Und da stört uns das nicht, dass der so groß wird. 16:00.100 --> 16:05.380 Also wir haben eine massive Vereinfachung der Struktur unserer 16:05.380 --> 16:07.540 generischen Programme. 16:08.100 --> 16:12.200 Der Preis ist, dass das kombinatorisch irgendwie sehr groß wird, aber 16:12.200 --> 16:12.880 das stört nicht. 16:13.220 --> 16:17.110 Also wir repräsentieren Programme durch Entscheidungsbäume. 16:19.970 --> 16:26.450 Und der Trick ist jetzt, zu jedem vergleichsbasierten 16:26.450 --> 16:29.070 Sortieralgorithmus gibt es jetzt so einen Entscheidungsbaum. 16:29.710 --> 16:32.750 Genauer gesagt, zu jedem vergleichsbasierten Sortieralgorithmus und 16:32.750 --> 16:36.790 zusätzlich gegebener Eingabegröße kann man so einen Entscheidungsbaum 16:36.790 --> 16:37.590 ableihen. 16:38.850 --> 16:42.450 Wir werden das nicht explizit tun oder eben nur für dieses ganz simple 16:42.450 --> 16:45.470 Beispiel, wo man drei Elemente mit einem konkreten Algorithmus 16:45.470 --> 16:45.950 sortiert. 16:48.610 --> 16:55.890 Und die Anzahl Vergleiche dieses Algorithmus im schlechtesten Fall ist 16:55.890 --> 17:00.750 jetzt nichts anderes als die Tiefe dieses Baums, also der längste Pfad 17:00.750 --> 17:04.070 von der Wurzel zu einem Blatt. 17:04.770 --> 17:09.970 Und wir fragen uns jetzt, wie lang ist dieser längste Pfad mindestens? 17:10.190 --> 17:11.590 Das ist unsere untere Schranke. 17:15.150 --> 17:20.010 Und die Schlüsselbeobachtung ist jetzt folgendes, damit unser 17:20.010 --> 17:25.150 Sortieralgorithmus korrekt ist, muss er alle N-Fakultät verschiedenen 17:25.150 --> 17:27.570 möglichen Eingaben unterscheiden können. 17:28.520 --> 17:34.210 Das heißt, an jedem Blatt unseres Entscheidungsbaums steht eine 17:34.210 --> 17:43.890 Permutation und jede der N-Fakultät möglichen Permutationen muss an 17:43.890 --> 17:45.610 einem der Blätter hier auftauchen. 17:46.950 --> 17:51.090 Das heißt, es gibt mindestens N-Fakultät viele Blätter in unserem 17:51.090 --> 17:52.590 Entscheidungsbaum. 17:55.990 --> 17:58.650 Gleichzeitig ist es so, dieser Entscheidungsbaum ist ein Binärbaum. 18:07.890 --> 18:11.290 Gegeben einer solcher Entscheidung habe ich immer nur zwei mögliche 18:11.290 --> 18:11.910 Nachfolger. 18:12.290 --> 18:16.390 Und jetzt kann ich argumentieren, wie tief muss der denn sein? 18:19.450 --> 18:22.670 Das war jetzt ein Missverständnis. 18:23.230 --> 18:26.070 Einen Pointer habe ich sogar, aber keinen Laser. 18:26.170 --> 18:26.950 Der andere ist kaputt. 18:29.050 --> 18:31.090 Aber wir können versuchen, mit dem hier zu arbeiten. 18:31.250 --> 18:32.930 Lieber einen schwachen Laser als gar keinen. 18:39.310 --> 18:41.890 Ja gut, das kann man einigermaßen sehen, denke ich. 18:45.010 --> 18:48.730 So, jetzt kommt wieder eine Folie Formeln. 18:49.370 --> 18:52.990 Also der Beweis ist nicht so schlimm wie das mit dem Universal 18:52.990 --> 18:53.510 Hashing. 18:57.250 --> 18:59.150 Also, wir haben hier diesen Baum. 18:59.490 --> 19:00.810 Wir wollen wissen, wie tief ist der? 19:00.870 --> 19:02.630 Wir wissen schon, wie viele Blätter es gibt. 19:03.470 --> 19:05.330 Wir wissen, es ist ein Binärbaum. 19:05.890 --> 19:10.010 Und das heißt insbesondere, wenn der Baum Tiefe T hat, dann hat er 19:10.010 --> 19:11.450 höchstens 2 hoch T Blätter. 19:11.590 --> 19:14.650 Das kann man ganz leicht durch vollständige Induktion beweisen. 19:16.030 --> 19:21.110 Und was wir wollen ist, 2 hoch T soll größer gleich N-Fakultät sein. 19:22.030 --> 19:26.370 Das ist eine Anforderung, damit dieser Sortieralgorithmus korrekt ist. 19:26.930 --> 19:30.510 Ja, aber das ist äquivalent zu, wir nehmen jetzt einfach den 19:30.510 --> 19:32.050 Zweierlogarithmus auf den Beiden. 19:32.290 --> 19:36.470 Also die Anforderung ist jetzt, T ist größer gleich Log N-Fakultät. 19:38.090 --> 19:41.350 Jetzt wissen wir aber außerdem, das beweise ich gleich noch, aber das 19:41.350 --> 19:43.950 ist eine Standardformel, die man im Zweifel noch irgendwo nachschlagen 19:43.950 --> 19:44.310 kann. 19:44.910 --> 19:47.770 N -Fakultät ist größer gleich N durch E hoch N. 19:48.270 --> 19:52.310 Wobei E die Eulersche Zahl ist, wieder 2,71 oder sowas. 19:53.950 --> 19:56.150 Das ist Log N durch E hoch N. 19:58.330 --> 20:00.370 Das ist N mal Log N durch E. 20:00.670 --> 20:05.330 Oder wenn ich das hier ausfalte mit Logarithmusgesetzen, ist das N Log 20:05.330 --> 20:06.910 N minus N Log E. 20:07.490 --> 20:09.030 Das ist genau das, was wir zeigen wollten. 20:09.150 --> 20:11.710 Das ist N Log N minus O von N. 20:15.150 --> 20:16.110 Frage dazu. 20:17.490 --> 20:21.210 Also diese zwei Zeilen sind jetzt eigentlich die entscheidende 20:21.210 --> 20:22.030 Herleitung hier. 20:22.510 --> 20:25.990 Der Rest ist nur Standardmathematik, die ich jetzt nochmal vorführe, 20:26.510 --> 20:28.150 die man aber im Zweifel auch nachschlagen kann. 20:28.230 --> 20:31.690 Das ist eigentlich keine informatische Einsicht, die da stattfindet. 20:32.110 --> 20:36.370 Aber was halt wichtig ist, auch für die Klausur, also diese untere 20:36.370 --> 20:40.290 Schranke kommt immer mal wieder in Klausuraufgaben, dass man versteht, 20:40.350 --> 20:46.410 was diese Entscheidungsbäume sind, dass die Blätter Permutationen 20:46.410 --> 20:53.130 haben als Label, beziehungsweise ich muss an den Blättern alle 20:53.130 --> 20:54.870 Permutationen unterscheiden können. 20:55.570 --> 20:57.770 Deshalb brauche ich mindestens N Fakultät Blätter. 20:58.870 --> 21:02.010 Und die Ausführungszeit dieses Entscheidungsbaums ist halt die Tiefe 21:02.010 --> 21:04.590 oder die Ausführungszeit im schlechtesten Fall. 21:05.630 --> 21:08.010 Und daneben diese Argumentation hier. 21:08.450 --> 21:09.450 Gibt es dazu Fragen? 21:14.350 --> 21:17.650 So, jetzt möchte ich Ihnen trotzdem mal zeigen, wie man das hier 21:17.650 --> 21:18.070 zeigt. 21:18.190 --> 21:20.570 N Fakultät größer gleich n durch e hoch n. 21:21.890 --> 21:25.830 Oder genauer gesagt, man kann N Fakultät auch in beiden Richtungen 21:25.830 --> 21:28.170 abschätzen durch sowas wie n hoch n. 21:29.430 --> 21:33.170 Das ist klar, dass N Fakultät kleiner gleich n hoch n ist, weil das 21:33.170 --> 21:36.670 ist ja 1 mal 2 mal 3 mal 4 und so weiter bis mal n. 21:36.770 --> 21:40.390 Und dann kann ich jede dieser n Zahlen durch n ersetzen, kriege ich n 21:40.390 --> 21:40.750 hoch n. 21:41.170 --> 21:42.330 Das ist eine super grobe Abschätzung. 21:43.130 --> 21:45.950 Das hier ist eigentlich schon gar nicht so schlecht als Abschätzung. 21:46.650 --> 21:47.670 Wie beweist man das? 21:50.630 --> 21:53.950 Tatsächlich ist es leichter, etwas über den Logarithmus von N Fakultät 21:53.950 --> 21:56.150 zu sagen, diesmal den natürlichen Logarithmus. 21:57.090 --> 21:58.390 Warum ist das nützlich? 21:58.470 --> 21:59.810 N Fakultät ist ja ein Produkt. 22:00.150 --> 22:03.410 Produkt i gleich 1 bis n von i. 22:04.530 --> 22:09.170 Der Logarithmus eines Produkts ist nach Logarithmusgesetz die Summe 22:09.170 --> 22:09.890 der Logarithmen. 22:11.050 --> 22:13.890 Und mit Summen können wir irgendwie viel besser rechnen. 22:13.990 --> 22:17.510 Das ist in Analysis oder HM, da wird das bis zum Abwinken gemacht. 22:19.730 --> 22:25.550 Ln der N Fakultät ist also Summe von 2 bis n ln i. 22:28.930 --> 22:32.030 Man kann es auch als Summe 1 bis n schreiben, aber das ist jetzt egal, 22:32.330 --> 22:37.910 weil ln 1 ist 0. 22:39.790 --> 22:41.190 Dann wird hier 0 nur addiert. 22:41.650 --> 22:44.070 Jetzt kommt noch ein Trick, der aber auch Standard ist bei 22:44.070 --> 22:45.030 Summenabschätzungen. 22:46.310 --> 22:48.530 Ich kann das durch ein Integral annähern. 22:49.130 --> 22:51.830 Ich habe diese Summe, das ist im Prinzip ein Integral über so eine 22:51.830 --> 22:52.090 Stufenfunktion. 22:54.570 --> 22:57.250 Das kann ich aber abschätzen durch das richtige Integral. 22:59.330 --> 23:03.150 In dem Fall ist das Integral einbeschrieben in diese Stufenfunktion, 23:03.310 --> 23:05.090 das heißt die Abschätzung ist größer gleich. 23:05.950 --> 23:10.270 Das ist größer gleich dem Integral von 1 bis n ln x dx. 23:11.190 --> 23:13.130 Da kann ich in der Integraltabelle nachgucken. 23:13.250 --> 23:21.470 Das Integral von ln x ist x mal ln x minus 1 von 1 bis n. 23:22.070 --> 23:28.350 Also ich setze hier x gleich n, dann kriege ich n mal ln n minus 1. 23:30.150 --> 23:36.190 Minus x gleich 1, dann steht da 1 mal 0 minus 1, also plus 1. 23:36.290 --> 23:39.290 Das plus 1 lasse ich weg, also ist das hier größer gleich n mal ln n 23:39.290 --> 23:39.990 minus 1. 23:42.130 --> 23:46.830 Ich habe gezeigt, ln n Fakultät ist größer gleich n mal ln n minus 1. 23:50.250 --> 23:55.850 Jetzt mache ich e hoch auf beiden Seiten, dann steht da wieder n 23:55.850 --> 24:00.430 Fakultät größer gleich e hoch n mal ln n minus 1. 24:00.910 --> 24:03.350 Und jetzt kann ich wieder eine Gleichheitsumformung machen. 24:03.350 --> 24:13.670 Das ist gleich e hoch n mal ln n, das ist dieser Term, geteilt durch e 24:13.670 --> 24:17.110 hoch n, das ist dieses n mal minus 1. 24:22.450 --> 24:25.570 e hoch n mal ln n ist aber nichts anderes als n hoch n. 24:26.090 --> 24:31.090 Also ich fasse jetzt e hoch ln n als n Basis n zusammen. 24:31.890 --> 24:35.750 Das ist also n hoch n durch e hoch n ist gleich n durch e hoch n und 24:35.750 --> 24:36.550 das wollte ich zeigen. 24:37.390 --> 24:38.090 Fragen dazu? 24:41.190 --> 24:43.850 Also das ist jetzt so ein Rechentrick, den müssen Sie sich auch nicht 24:43.850 --> 24:47.730 auswendig lernen, aber es ist vielleicht schon gut zu wissen, dass man 24:47.730 --> 24:51.030 Summen manchmal durch Integrale nach oben oder unten abschätzen kann. 24:51.110 --> 24:53.470 Das werden wir auch noch mehrfach sehen in dieser Vorlesung. 24:55.570 --> 24:55.950 Frage? 25:04.950 --> 25:08.970 Also wir haben ja gesagt, der letzte Schritt, n log n minus n log e 25:08.970 --> 25:09.770 gleich? 25:15.530 --> 25:19.430 Also das ist der Logarithmus von Basis 2, irgendeine krumme Zahl. 25:19.750 --> 25:21.890 Aber das macht auch keinen Unterschied asymptotisch. 25:21.930 --> 25:24.110 Wenn Sie hier den natürlichen Logarithmus von e nehmen würden, wäre 25:24.110 --> 25:24.990 das einfach 1. 25:25.710 --> 25:27.970 Aber n ist ja auch o von n oder Theta n. 25:30.270 --> 25:31.130 Weitere Fragen? 25:33.150 --> 25:33.670 Okay. 25:36.550 --> 25:40.950 Also haben wir unsere deterministische untere Schranke gezeigt und 25:40.950 --> 25:45.090 ohne Beweis, der ist formal ein bisschen komplizierter, aber benutzt 25:45.090 --> 25:46.630 im Prinzip die gleichen Argumente. 25:47.590 --> 25:53.630 Also man kann auch zeigen, dass man nichts davon hat, wenn man Zufall 25:53.630 --> 25:57.310 in dem Algorithmus mit einbringen darf und man hat auch nichts damit, 25:57.430 --> 26:00.490 wenn man sich statt dem schlechtesten Fall den mittleren Fall 26:00.490 --> 26:01.030 anschaut. 26:02.050 --> 26:03.970 Der beste Fall ist was anderes. 26:05.170 --> 26:08.050 Aber im Mittel brauche ich auch immer diese n log n Schritte. 26:09.910 --> 26:12.950 Das kann man zeigen, werde ich hier nicht tun, weil das formal ein 26:12.950 --> 26:16.010 bisschen komplexer ist, aber man braucht eigentlich keine fundamental 26:16.010 --> 26:17.090 neuen Ideen. 26:17.610 --> 26:21.990 Das Wichtigste hier war für mich erstens zu zeigen, aha, dieses n log 26:21.990 --> 26:25.070 n ist was Fundamentales, solange ich nur vergleichsbasiert arbeite, 26:25.130 --> 26:26.210 kann ich nicht besser werden. 26:26.210 --> 26:30.830 Und überhaupt mal ein Beispiel dafür zu sehen, eine untere Schranke zu 26:30.830 --> 26:35.050 zeigen, ein Argument über alle möglichen Algorithmen in einer 26:35.050 --> 26:35.950 bestimmten Familie. 26:39.970 --> 26:42.450 Jetzt wollen wir uns noch einen weiteren vergleichsbasierten 26:42.450 --> 26:46.770 Algorithmus anschauen, der in der Praxis sehr viel verwendet wird und 26:46.770 --> 26:48.430 an dem man auch wieder viel lernen kann. 26:49.710 --> 26:55.130 Und der zumindest in einer Variante einen entscheidenden Vorteil über 26:55.130 --> 26:57.870 Merge Sort hat, dass er nämlich in Place arbeitet. 26:58.010 --> 26:59.690 Das heißt, er braucht keinen zusätzlichen Platz. 27:00.830 --> 27:06.650 Beim Merge Sort ist es zumindest sehr schwierig, ohne zusätzlichen 27:06.650 --> 27:07.510 Platz auszukommen. 27:07.590 --> 27:10.230 Da gibt es Leute, die das machen, aber das ist wahnsinnig kompliziert. 27:10.670 --> 27:13.670 Man hat immer zwei sortierte Folgen und muss eine sortierte 27:13.670 --> 27:15.630 Ausgabefolge erzeugen beim Mischen. 27:15.630 --> 27:21.550 Und das ist nicht so einfach, das zu machen, ohne dass man im 27:21.550 --> 27:24.050 einfachsten Fall einen Faktor 2 mehr Platz braucht. 27:24.670 --> 27:28.910 Und mit ein paar Tricks braucht man dann ein Viertel n mehr Platz oder 27:28.910 --> 27:29.330 sowas. 27:30.790 --> 27:31.670 Gut, Quick Sort. 27:32.770 --> 27:37.690 Ein anderer Grund, Quick Sort darzustellen, ist, dass man hier sehen 27:37.690 --> 27:41.910 kann, dass man dieses Teile-und-Herrsche-Prinzip oft auf mehrere Arten 27:41.910 --> 27:44.250 und Weisen einsetzen kann. 27:44.250 --> 27:47.970 Beim Merge Sort war das so, wir haben ein triviales Teilen gemacht und 27:47.970 --> 27:50.250 mussten dann beim Herrschen arbeiten, Mischen. 27:51.390 --> 27:53.290 Bei Quick Sort mache ich das genau umgekehrt. 27:53.590 --> 27:58.890 Ich arbeite beim Teilen und dann ist das Herrschen trivial. 28:00.410 --> 28:04.070 Insofern sind die dual zueinander, sagt man in der Mathematik manchmal 28:04.070 --> 28:05.950 auch, die beiden Algorithmen. 28:05.950 --> 28:13.670 Also die Idee ist, wir haben hier wieder den gleichen Basisfall, wenn 28:13.670 --> 28:16.470 die Folge Länge 1 hat, sind wir fertig. 28:18.810 --> 28:22.810 Wir wählen jetzt ein sogenanntes Pivot-Element, das ist ein Element 28:22.810 --> 28:23.330 der Folge. 28:24.090 --> 28:24.110 Wie? 28:24.610 --> 28:25.550 Da reden wir noch drüber. 28:27.330 --> 28:32.410 Und jetzt partitionieren wir die Folge in dieser Implementierung in 28:32.410 --> 28:33.070 drei Teile. 28:33.150 --> 28:35.870 Man kann das auch in zwei machen, aber dann muss man ein bisschen 28:35.870 --> 28:36.890 vorsichtiger sein. 28:37.610 --> 28:41.210 Also eine Folge A, das sind alle Elemente, die kleiner sind als der 28:41.210 --> 28:41.490 Pivot. 28:41.630 --> 28:44.450 Eine Folge B, das sind alle Elemente, die gleich sind dem Pivot. 28:45.090 --> 28:48.870 Eine Folge C, das sind alle Elemente, die sind größer als der Pivot. 28:51.190 --> 28:55.830 Rekursiv werden A und C sortiert, B ist bereits sortiert, weil das ja 28:55.830 --> 28:57.850 alles Elemente mit gleichem Schlüssel sind. 28:59.570 --> 29:01.630 Und da muss ich die nur noch aneinanderhängen. 29:04.510 --> 29:10.270 Also konzeptuell wahrscheinlich noch ein bisschen einfacher als Merge 29:10.270 --> 29:14.550 Sort, weil wie man diese Listen hier bestimmt, braucht man gar nicht 29:14.550 --> 29:15.890 mehr groß drüber nachdenken. 29:15.890 --> 29:19.530 Wenn man das einmal spezifiziert hat, während beim Merging muss man 29:19.530 --> 29:20.750 sich noch ein bisschen mehr überlegen. 29:21.090 --> 29:23.910 Aber beides sehr einfache Algorithmen eigentlich. 29:24.250 --> 29:25.410 Merge Sort und Quick Sort. 29:28.250 --> 29:30.690 Was hier ein bisschen schwieriger ist, ist die Analyse. 29:31.090 --> 29:34.790 Beim Merge Sort hatten wir eine Aufteilung in zwei genau gleich große 29:34.790 --> 29:36.310 Teile oder Plus Minus Eins. 29:37.410 --> 29:41.030 Hier habe ich jetzt so gesagt, wir wählen irgendein Pivot. 29:41.030 --> 29:45.290 Es wäre natürlich schön, wenn wir den Median nehmen könnten von der 29:45.290 --> 29:48.450 Eingabefolge, dann hätten wir auch wieder eine genaue Aufteilung. 29:49.430 --> 29:52.270 Aber den zu bestimmen ist im Allgemeinen zu teuer. 29:53.130 --> 29:56.010 Deshalb werden wir hier eine ungenaue Aufteilung kriegen und das 29:56.010 --> 29:57.910 beeinflusst auch irgendwie die Laufzeit. 29:58.390 --> 30:00.310 Und wie, das werden wir uns halt anschauen. 30:02.970 --> 30:05.110 Fangen wir mal an mit dem schlechtesten Fall. 30:06.130 --> 30:07.610 Das ist keine gute Nachricht. 30:08.930 --> 30:10.970 Wenn das Pivot z.B. 30:11.090 --> 30:17.210 immer das Minimum oder das Maximum der Eingabe ist, was ist dann die 30:17.210 --> 30:18.010 Laufzeit? 30:19.750 --> 30:22.530 T von N ist Theta 1, wenn N gleich 1 ist. 30:23.630 --> 30:24.270 Basisfall. 30:24.990 --> 30:25.490 Sonst? 30:26.370 --> 30:28.650 Ich brauche lineare Zeit, um aufzuspalten. 30:29.470 --> 30:29.850 Plus? 30:31.270 --> 30:33.730 Na ja, was passiert dann, wenn das das Minimum ist? 30:35.370 --> 30:37.870 Dann ist die Folge A leer. 30:38.390 --> 30:40.090 Die Folge B hat genau ein Element. 30:40.950 --> 30:42.470 Also zumindest, wenn die alle verschieden sind. 30:43.090 --> 30:45.570 Und die Folge C hat N-1 Elemente. 30:45.730 --> 30:50.770 Also dann ist T von N gleich lineare Laufzeit fürs Aufteilen plus T 30:50.770 --> 30:51.890 von N-1. 30:53.370 --> 30:57.370 Also sowas wie N plus N-1 plus N-2 und so weiter. 30:57.930 --> 30:59.050 Das ist Theta N². 30:59.870 --> 31:03.330 Also wir haben hier im schlechtesten Fall einen quadratischen 31:03.330 --> 31:08.030 Algorithmus mit konstanten Faktoren, die viel schlechter sind als z.B. 31:08.370 --> 31:09.190 in Search&Sort. 31:10.490 --> 31:15.030 Also wir sehen im schlechtesten Fall keinen besonders guten 31:15.030 --> 31:15.370 Algorithmus. 31:17.350 --> 31:22.770 Aber wir werden sehen, im Erwartungswert, wenn wir zufällige Pivots 31:22.770 --> 31:25.610 wählen, kommen wir ganz nah an die untere Schranke ran. 31:26.850 --> 31:28.370 Das wäre jetzt ein Beispiel. 31:30.870 --> 31:33.010 Wenn wir hier diese Zahlen sortieren wollen. 31:34.990 --> 31:37.870 Implementierungen in Büchern sagen oft, wir nehmen das von der 31:37.870 --> 31:39.570 Position her mittlere Elemente. 31:39.590 --> 31:42.770 Deshalb habe ich die jetzt mal hier so gemacht, dass das genau 31:42.770 --> 31:43.170 passiert. 31:43.270 --> 31:44.430 Wir nehmen das Minimum. 31:45.530 --> 31:47.290 Linke Teil Problem ist leer. 31:47.850 --> 31:49.530 Ein Element, der ganze Rest. 31:50.250 --> 31:51.950 Jetzt nehmen wir den 1 als Pivot. 31:52.050 --> 31:53.030 Das ist wieder das Minimum. 31:53.130 --> 31:53.670 Links leer. 31:54.130 --> 31:55.590 Ein Element, der ganze Rest. 31:56.210 --> 31:59.290 Und dann sieht unsere Rekursion ziemlich übel aus. 31:59.430 --> 32:00.610 Geht ganz weit runter. 32:02.950 --> 32:04.290 Tiefe ist O von N. 32:05.290 --> 32:09.430 Jeden Schritt mache ich Arbeit proportional zur Länge der Eingabe, 32:09.810 --> 32:11.070 also quadratische Arbeit. 32:12.670 --> 32:15.150 Wenn man das Rekursiv implementiert, würde Ihnen hier noch etwas 32:15.150 --> 32:15.970 anderes passieren. 32:16.470 --> 32:20.570 Das ist nämlich der Rekursionsstapel der Maschine, der Ihnen 32:20.570 --> 32:23.210 möglicherweise irgendwann um die Ohren fliegt, weil der auch ganz viel 32:23.210 --> 32:23.910 Platz braucht. 32:26.290 --> 32:27.870 So, das war die schlechte Nachricht. 32:28.730 --> 32:29.890 Die gute Nachricht. 32:30.890 --> 32:32.910 Im besten Fall... 32:33.410 --> 32:35.170 Naja, nicht so gut wie in Search&Sort. 32:35.230 --> 32:36.250 Da hatten wir lineare Zeit. 32:36.310 --> 32:37.330 Hier kriegen wir N log N. 32:37.510 --> 32:41.350 Also der beste Fall ist, dass wir immer den Median auswählen, also 32:41.350 --> 32:41.710 Pivot. 32:42.470 --> 32:44.470 Dann ist die Ausführungszeit halt... 32:44.470 --> 32:45.930 Ja, dann kriegen wir wieder Mastertheorie. 32:46.090 --> 32:49.270 O von 1 für den Basisfall. 32:49.350 --> 32:50.750 O von N fürs Teilen. 32:50.810 --> 32:53.530 Plus 2 mal T von N halber. 32:53.530 --> 32:59.990 Wir haben hier in diesem Fall N halber abgerundet, weil immer 32:59.990 --> 33:04.670 mindestens ein Element, nämlich das Pivot selber, in diesem mittleren 33:04.670 --> 33:06.730 Instanz landet, wo wir nicht mehr sortieren müssen. 33:08.710 --> 33:11.370 Das ist nach dem Mastertheorem O von N log N. 33:11.950 --> 33:12.990 Und hier wäre ein Beispiel. 33:13.570 --> 33:16.150 Wir wählen die 3, das ist genau der Median. 33:16.270 --> 33:18.630 Deshalb sind 3 links, 3 rechts, einer in der Mitte. 33:18.630 --> 33:20.510 Hier nehmen wir den Median. 33:20.630 --> 33:22.270 Einer links, einer rechts, einer in der Mitte. 33:23.150 --> 33:25.050 Und das Ganze ist sehr schön balanciert. 33:26.790 --> 33:27.610 Fragen dazu? 33:28.550 --> 33:30.550 Quicksort, wie funktioniert der Algorithmus? 33:31.450 --> 33:35.690 Wenn Sie Fragen darüber beantworten, schlechtester Fall, bester Fall, 33:36.750 --> 33:40.550 wieder eine Quelle von schönen, vielen, trivialen Klausuraufgaben. 33:41.210 --> 33:43.130 Wenn Sie es gelernt haben und verstanden haben. 33:45.110 --> 33:51.690 So, jetzt möchte ich eine Analyse für einen randomisierten Algorithmus 33:51.690 --> 33:51.970 machen. 33:52.250 --> 33:55.510 Das ist so ähnlich wie bei den Hashtabellen. 33:56.110 --> 33:58.910 Jetzt interessiert mich nicht die Ausführungszeit im schlechtesten 33:58.910 --> 34:02.870 oder im besten Fall, sondern die erwartete Ausführungszeit, wenn ich 34:02.870 --> 34:04.370 den Pivot zufällig wähle. 34:08.570 --> 34:10.630 Ansonsten bleibt der Algorithmus gleich. 34:11.230 --> 34:12.670 Da habe ich hier mal ein Beispiel. 34:12.850 --> 34:14.290 Ich nehme zufällig zum Beispiel die 3. 34:14.430 --> 34:16.710 Da sind 3 links, 6 rechts. 34:18.110 --> 34:20.430 Hier habe ich jetzt zufällig den Pivot erwischt. 34:20.530 --> 34:22.470 Hier sind 2 links, 3 rechts. 34:22.910 --> 34:24.330 Da kann alles mögliche passieren. 34:25.930 --> 34:32.970 Aber die Intuition ist jetzt, dass das ganz gut ist, weil meistens der 34:32.970 --> 34:34.590 Pivot nicht wirklich schlecht ist. 34:36.030 --> 34:40.330 Meistens ist es so, dass er wirklich einen konstanten Teil links hat 34:40.330 --> 34:41.790 und einen konstanten Teil rechts. 34:42.090 --> 34:46.890 Und das genügt schon, um in unserer Rekursion eine logarithmische 34:46.890 --> 34:47.830 Tiefe zu erreichen. 34:49.010 --> 34:53.010 Und die Arbeit auf jedem Level ist sowieso linear, wie im 34:53.010 --> 34:53.830 Mastertheorien. 34:54.170 --> 34:57.670 Das ist jetzt so die Idee für die Analyse. 34:57.670 --> 35:04.750 Es genügt, dass wir meistens einigermaßen gut partitionieren, damit 35:04.750 --> 35:06.570 wir O von N log N Laufzeit kriegen. 35:07.170 --> 35:09.850 Aber wir müssen das jetzt noch formalisieren, diese Intuition. 35:10.550 --> 35:13.670 Und es wäre auch schön, den konstanten Faktor vor der Anzahl 35:13.670 --> 35:16.390 Vergleiche zu kriegen und zu vergleichen mit Merge Sort. 35:16.490 --> 35:21.890 Und das werden wir tun mit einer eigentlich relativ simplen Analyse. 35:25.110 --> 35:29.670 Also, wir wollen jetzt formal beweisen, dass QuickSort mit zufälliger 35:29.670 --> 35:32.890 Pivotwahl die erwartete Laufzeit O von N log N hat. 35:34.690 --> 35:38.470 Wir nehmen an, dass alle Elemente verschieden sind. 35:40.610 --> 35:43.710 Das ist so eine typische Annahme, die man als Theoretiker macht. 35:43.830 --> 35:46.890 Und dann steht da irgendwo, ohne Bedenken des Autors, ohne 35:46.890 --> 35:48.850 Beschränkung der Allgemeinheit. 35:49.870 --> 35:53.850 Und dann sollte man meistens nachfragen, wieso denn ohne Bedenken... 35:55.830 --> 36:00.750 Kann mir jemand sagen, warum das zum Beispiel kein Problem ist? 36:01.450 --> 36:03.570 Da gibt es verschiedene Interpretationen. 36:17.700 --> 36:20.620 Genau, also ein Standardargument bei sowas ist so Tie-Breaking. 36:20.860 --> 36:24.780 Also wir sagen, wir können in linearer Zeit die Eingabe so 36:24.780 --> 36:27.600 transformieren, dass alle Elemente wirklich verschieden sind. 36:27.600 --> 36:31.580 Indem wir zum Beispiel dann nicht mal das Element selber nehmen, 36:31.700 --> 36:36.200 sondern ein Tuple, ein Paar bauen, Element oder Schlüssel des Elements 36:36.200 --> 36:38.000 und Position in der Eingabe. 36:38.620 --> 36:39.940 Und dann sind sie alle verschieden. 36:41.440 --> 36:45.120 Und wir könnten hier aber auch argumentieren, naja, wenn viele gleich 36:45.120 --> 36:47.080 sind, erleichtert das das Problem nur. 36:47.760 --> 36:51.160 Weil das Einzige, was hier verändert wird, ist, dass dann dieser 36:51.160 --> 36:54.020 mittlere Teil bei der Partitionierung größer wird. 36:54.540 --> 36:56.760 Und dann wird das Problem insgesamt leichter. 36:58.080 --> 37:01.460 Wobei das so ein bisschen so ein Händewedel-Argument auch ist. 37:02.060 --> 37:06.600 Aber das Händewedeln ist sowieso schon implizit in diesem OBDA. 37:18.780 --> 37:21.260 Ja ja, intuitiv ist das alles relativ simpel. 37:21.500 --> 37:31.020 Also es ist intuitiv klar, dass wenn ich größere Mittelteile kriege, 37:31.080 --> 37:32.380 dass das dadurch einfacher wird. 37:33.440 --> 37:39.020 Das ist schon richtig, aber in dem Buch steht so eine schöne 37:39.020 --> 37:41.120 Formulierung von meinem Co-Autor. 37:42.660 --> 37:44.560 Clearly bla bla bla bla, ja. 37:45.260 --> 37:49.780 Und dann steht da, Probleme in der theoretischen Informatik finden 37:49.780 --> 37:51.820 sich meistens in der Nähe des Wortes clearly. 37:53.640 --> 37:55.720 Irgendwie so eine Formulierung hat er da gefunden. 37:55.720 --> 38:00.760 Also es kommt halt leider auch ganz oft vor, dass jemand sowas dahin 38:00.760 --> 38:03.740 wirft, so ein OBDA, und dann kommt jemand anders und sagt, nee, nee, 38:03.800 --> 38:07.720 nee, nee, so ohne Beschränkung ist das gar nicht, weil... 38:08.240 --> 38:12.160 Man muss immer vorsichtig sein, aber das mit dem Type-Ranking ist 38:12.160 --> 38:17.400 jetzt eine relativ klare Geschichte, wo klar ist, was man da passiert. 38:17.460 --> 38:18.960 Da würde ich mich jetzt mal drauf zurückziehen. 38:20.620 --> 38:23.320 Dann muss man genau definieren, was man zählt. 38:25.540 --> 38:30.160 Für diesen Algorithmus macht es aus meiner Sicht Sinn, hier drei 38:30.160 --> 38:31.640 Wegevergleiche zu zählen. 38:31.740 --> 38:35.760 Also wir sagen, wenn wir hier eine Eingabe der Länge N haben, dann 38:35.760 --> 38:36.960 machen wir N-Dreiwegevergleiche. 38:37.640 --> 38:41.840 Also jedes Element wird mit dem Pivot verglichen, und dann kriege ich 38:41.840 --> 38:43.040 ein dreiwertiges Ergebnis. 38:43.180 --> 38:46.000 Kleiner, gleicher oder größer, und je nachdem wird es in eine dieser 38:46.000 --> 38:47.940 drei Ausgabefolgen verschoben. 38:47.940 --> 38:52.040 Also langer Rede, kurzer Sinn, wenn ich hier Eingabegröße N, Größe 1 38:52.040 --> 38:55.980 habe, zähle ich genau N-Dreiwegevergleiche. 38:59.030 --> 39:03.890 So, und wir wollen jetzt den Erwartungswert von C von N bestimmen oder 39:03.890 --> 39:04.470 abschätzen. 39:06.130 --> 39:07.710 So, wie macht man das? 39:08.450 --> 39:15.150 Im Buch finden Sie einen relativ einfachen, kurzen Beweis, der 39:15.150 --> 39:16.410 folgende Grundidee hat. 39:16.410 --> 39:22.410 Mit einer Wahrscheinlichkeit von 1,5 wähle ich ein brauchbares Pivot, 39:22.570 --> 39:26.470 in dem Sinne, dass das Aufspaltverhältnis nichts schlechter ist als 1 39:26.470 --> 39:27.430 ,25 zu 3,25. 39:29.910 --> 39:33.450 Und dann wird was vorgerechnet, das zeigt, dass das bereits genügt, um 39:33.450 --> 39:37.610 zu zeigen, dass die erwartete Anzahl Dreiwegevergleiche O von N log N 39:37.610 --> 39:37.870 ist. 39:37.870 --> 39:44.810 Wir machen hier etwas genaueres, was, wie ich finde, auch eleganter 39:44.810 --> 39:45.030 ist. 39:45.130 --> 39:49.550 Also dieses 1,5, das 1,25 und das 3,25, das sind irgendwelche 39:49.550 --> 39:53.570 Konstanten, die vom Himmel fallen und die dann hinterher den 39:53.570 --> 39:57.790 konstanten Faktor, der hier verborgen wird, beeinflussen. 39:58.450 --> 40:00.850 Und vor allem stellt sich dann raus, der konstante Faktor, den man 40:00.850 --> 40:01.650 hier ableitet. 40:01.650 --> 40:06.710 Also eigentlich zeigt man da ja sowas wie C-Dach von N kleiner gleich 40:06.710 --> 40:10.990 konstanter Faktor mal N log N, für hinreichend große N. 40:11.890 --> 40:15.110 Dieser konstante Faktor ist viel größer als das, was wir hier zeigen. 40:15.670 --> 40:20.550 Einfach weil man da so mit der groben Axt Sachen in gut und schlecht 40:20.550 --> 40:24.090 teilt, wo die Wirklichkeit viel komplexer ist. 40:24.830 --> 40:31.610 Also wir werden zeigen, der Erwartungswert von C von N ist kleiner 40:31.610 --> 40:33.310 gleich 2 mal N mal lnN. 40:33.710 --> 40:41.030 Das ist sowas wie 1,45 mal N log N, also sowas wie 45% größer als die 40:41.030 --> 40:42.510 Anzahlvergleiche vom Merge Sort. 40:43.130 --> 40:47.590 Das ist der Preis, den ich dafür bezahle, relativ schlechte zufällige 40:47.590 --> 40:50.690 Pivots zu wählen und nicht genaue Mediane zu bestimmen. 40:50.690 --> 40:53.370 Aber wir sehen, der Preis ist relativ klein. 40:54.390 --> 40:57.370 Und wenn an anderen Stellen im Algorithmus die konstanten Faktoren 40:57.370 --> 41:02.030 dann besser sind, kann es halt sein, dass unter dem Strich Quicksort 41:02.030 --> 41:04.150 der schnellere Sortieralgorithmus ist. 41:04.610 --> 41:07.230 Und das ist auch in vielen Implementierungen der Fall. 41:08.590 --> 41:13.010 Also in den meisten Libraries, die ich kenne, wird Quicksort an 41:13.010 --> 41:17.750 irgendeiner Stelle verwendet, weil es in place ist und weil es 41:17.750 --> 41:20.070 meistens ein bisschen schneller ist als Merge Sort. 41:20.070 --> 41:23.630 Aber ich habe auch schon Implementierungen gesehen, die darauf 41:23.630 --> 41:26.250 hinweisen, dass auf modernen Maschinen Merge Sort tatsächlich ein 41:26.250 --> 41:27.130 bisschen schneller ist. 41:28.070 --> 41:29.170 Du musst da ein bisschen aufpassen. 41:29.470 --> 41:30.310 Willkommen zur Übung. 41:31.990 --> 41:35.050 Ich werde jetzt in den nächsten 20 Minuten nochmal das Thema von 41:35.050 --> 41:37.470 letzter Woche aufgreifen, nämlich Hashing. 41:38.270 --> 41:47.770 Und danach wird Timo euch mit seinem Lieblingsthema beglücken, nämlich 41:47.770 --> 41:48.290 mit Sortieren. 41:50.410 --> 41:53.950 Ich möchte anfangen mit einem sehr praxisrelevanten Thema, nämlich 41:53.950 --> 41:54.990 Unbounded Hashtables. 41:55.650 --> 41:59.470 Zur Motivation ist es so, dass wir in der Vorlesung gehört haben, es 41:59.470 --> 42:03.790 gibt Hashtabellen und dann haben die eine bestimmte Anzahl von Plätzen 42:03.790 --> 42:05.430 M und dann kann man irgendwas tolles zeigen. 42:05.530 --> 42:07.890 Ich komme auch später noch mal darauf zurück. 42:08.090 --> 42:10.990 Man kann irgendwas zeigen, wenn man dann nur so viele Elemente 42:10.990 --> 42:13.490 einfügt, dann ist die erwartete Anzahl von Koalitionen halt konstant. 42:13.490 --> 42:16.450 Aber in der Praxis sieht es halt so aus, dass man von vornherein 42:16.450 --> 42:19.770 eigentlich nicht genau weiß, wie viele Elemente man einfügen möchte. 42:22.090 --> 42:24.710 Und was passiert denn jetzt, wenn man jetzt so viele Elemente einfügt? 42:24.870 --> 42:29.030 Also bei Hashing mit linearer Suche, das geht einfach nicht. 42:29.190 --> 42:32.030 Irgendwann ist das Ding voll und dann gibt es einen Überlauf und ihr 42:32.030 --> 42:33.090 könnt nicht mehr Elemente einfügen. 42:34.330 --> 42:37.130 Bei Hashing mit verkehrten Listen könnt ihr immer mehr Elemente 42:37.130 --> 42:40.930 einfügen, aber was dann passiert ist, es gibt immer mehr Kollisionen 42:40.930 --> 42:43.770 und diese verkehrten Listen werden immer länger und dadurch werden die 42:43.770 --> 42:44.810 Operationen immer teurer. 42:45.690 --> 42:46.850 Und das möchte man halt auch vermeiden. 42:47.890 --> 42:50.470 Und die Lösung dazu, was in der Praxis auch gemacht wird, was auch in 42:50.470 --> 42:54.510 den Standardinterpretierungen, also bei C++ zumindest, gemacht wird, 42:55.070 --> 42:57.950 ist, dass die Hashtabelle dynamisch vergrößert und verkleinert werden 42:57.950 --> 42:58.170 kann. 42:59.170 --> 42:59.950 Wie sieht das aus? 43:02.090 --> 43:06.270 Man muss eben, wenn man einen Insert macht, die Größe verdoppeln, wenn 43:06.270 --> 43:09.110 man eine bestimmte Anzahl, wenn man hier in dem Fall jetzt Anzahl der 43:09.110 --> 43:13.350 Slots Elemente eingefügt hat, muss man dann die Größe verdoppeln und 43:13.350 --> 43:17.110 genauso beim Remove halbiert man die Größe, wenn man nur noch ein 43:17.110 --> 43:19.610 Viertel Anzahl der Slots Elemente drin hat. 43:20.490 --> 43:25.690 Und das ist eigentlich komplett analog zu den Unbounded Arrays, die 43:25.690 --> 43:26.650 wir auch schon besprochen haben. 43:26.810 --> 43:29.330 Deswegen will ich da gar nicht näher drauf eingehen, eigentlich nur 43:29.330 --> 43:34.550 auf den eigentlichen Unterschied drauf eingehen, nämlich bei den 43:34.550 --> 43:43.570 Unbounded Arrays ist es so, dass wenn das Array erneuert wird, also 43:43.570 --> 43:46.930 verdoppelt wird, werden alle Elemente aus dem alten Array reinkopiert 43:46.930 --> 43:47.330 in das neue. 43:48.290 --> 43:50.130 Das geht bei Hashtabellen aber nicht so gut. 43:50.130 --> 43:54.410 Und das Problem ist halt, dass man ja die Hash-Funktion optimiert 43:54.410 --> 43:59.170 hatte vielleicht für diese M Plätze und die nur auf 0 bis M streut. 43:59.650 --> 44:03.810 Wenn ich aber jetzt die Plätze verdopple und zwei M Elemente drin 44:03.810 --> 44:07.210 habe, dann streut meine Hash-Funktion nicht mehr auf die gesamte 44:07.210 --> 44:07.610 Breite. 44:08.210 --> 44:10.630 Das heißt, ich muss jetzt meine Hash-Funktion ändern. 44:11.370 --> 44:14.750 Und das bedeutet da wiederum, dass unter Umständen die Elemente, die 44:14.750 --> 44:17.610 an irgendeiner Stelle stehen in der Hashtabelle, nicht mehr mit der 44:17.610 --> 44:19.030 neuen Hash-Funktion übereinstimmen. 44:19.030 --> 44:22.290 Und was man macht, ist deswegen, dass man einen vollständigen Rehash 44:22.290 --> 44:22.550 macht. 44:22.630 --> 44:29.670 Das bedeutet, man nimmt alle Elemente aus der alten Tabelle raus und 44:29.670 --> 44:30.490 fügt sie neu ein. 44:31.370 --> 44:33.010 Also man hasht die neue Tabelle ein. 44:34.090 --> 44:37.310 Das klingt jetzt erstmal ziemlich aufwendig, aber es ist halt immer 44:37.310 --> 44:37.810 noch linear. 44:37.970 --> 44:41.130 Und das ist das Wichtige für die Analyse dann, denn die Analyse ist 44:41.130 --> 44:44.970 auch wieder komplett symmetrisch zu den Unbounded Arrays. 44:44.970 --> 44:49.790 Nämlich dieses Rehash ist immer noch amortisiert in O von 1. 44:53.010 --> 44:57.670 Das ist komplett genau das Gleiche wie bei den Unbounded Arrays in der 44:57.670 --> 44:58.390 Bankkontomethode. 44:59.150 --> 45:04.450 Bei Insert muss man halt sparen und dann kann man halt mehr 45:04.450 --> 45:08.110 Rechenpower ausgeben bei dem Rehash. 45:09.990 --> 45:12.930 Jetzt will ich auf ein kleines Detail in der Implementierung noch 45:12.930 --> 45:13.290 eingehen. 45:13.710 --> 45:16.850 Das Problem ist, wenn man jetzt immer diese Hash-Tabelle vergrößert, 45:17.050 --> 45:21.990 also 1, 2, 4, 8, 16, dann hat man halt irgendwie, die Tabellengröße 45:21.990 --> 45:23.050 ist immer eine Zweierpotenz. 45:23.830 --> 45:28.330 Und wenn man die Hash-Funktion jetzt immer Modulo der Tabellengröße 45:28.330 --> 45:33.810 rechnet, dann entspricht dieses Modulo der Zweierpotenz eben dem 45:33.810 --> 45:35.310 Extrahielen der k-Niedrigsten Bits. 45:36.110 --> 45:38.190 Und das ist nicht erwünscht, das ist nicht so schön. 45:38.190 --> 45:38.790 Wenn z.B. 45:38.890 --> 45:48.370 jetzt eure Eingabesequenz irgendwelche Strukturen hat, z.B. 45:48.450 --> 45:51.470 dass die k-Niedrigsten Bits immer 0 sind, dann wird es immer auf dem 45:51.470 --> 45:52.230 gleichen Platz gehashed. 45:52.970 --> 45:55.390 Und deswegen ist es in der Praxis besser, wenn man schaut, dass die 45:55.390 --> 45:57.650 Tabellengröße immer eine Primzahl ist. 45:58.890 --> 46:00.510 Möglichst weit entfernt von Zweierpotenzen auch. 46:01.850 --> 46:03.450 Und wie kann man das jetzt machen? 46:03.990 --> 46:06.450 Am einfachsten geht es, wenn man einfach eine Primzahl-Tabelle im Code 46:06.450 --> 46:07.130 direkt ablegt. 46:08.050 --> 46:09.110 Das sind auch gar nicht so viele. 46:09.250 --> 46:13.390 Ihr könnt euch überlegen, wenn ihr halt da 40 Primzahlen ablegt, und 46:13.390 --> 46:18.550 es immer ungefähr das Doppelte ist vom vorherigen, dann habt ihr schon 46:18.550 --> 46:19.370 ziemlich viele Plätze. 46:19.610 --> 46:22.910 Und vielleicht müsst ihr in 10 Jahren halt mal 50 ablegen oder 60 46:22.910 --> 46:23.270 ablegen. 46:23.330 --> 46:23.810 Das ist doch nicht viel. 46:25.410 --> 46:27.650 Und bei einer Größenänderung, wir hätten einfach die nächstgrößere 46:27.650 --> 46:28.490 Primzahl aus der Tabelle. 46:29.070 --> 46:30.890 Also ich habe hier eine Hash-Tabelle mit 5 Plätzen. 46:31.490 --> 46:33.290 Und jetzt will ich aber 6 Elemente einfügen. 46:33.390 --> 46:33.710 Hier das 6. 46:33.770 --> 46:34.270 Element hier. 46:34.730 --> 46:36.030 Das heißt, ich verdopple jetzt die Größe. 46:36.150 --> 46:36.950 2 x 5 ist 10. 46:37.370 --> 46:38.510 Ich wähle die nächstgrößere Primzahl. 46:38.690 --> 46:40.330 Also habe ich jetzt eine mit 11. 46:41.230 --> 46:45.430 Und jetzt füge ich alle Elemente aus dieser Tabelle hier rein. 46:45.570 --> 46:47.790 Also die 25, dann die 42, dann die 22 und so weiter. 46:48.390 --> 46:50.630 Und habe am Ende die 96, die ich nochmal hier einfügen kann. 46:51.990 --> 46:53.950 Gut, soweit zum praxirelevanten Thema. 46:54.010 --> 46:55.210 Jetzt möchte ich nochmal auf die Theorie eingehen. 46:55.630 --> 46:57.250 Das ist erstmal eine Wiederholung von letzter Woche. 46:57.250 --> 47:00.250 Das geht um die Universalität von Hash-Funktionen. 47:02.830 --> 47:05.850 Und da möchte ich jetzt erstmal wiederholen, was das genau war. 47:06.030 --> 47:06.790 Das möchte ich auch motivieren. 47:07.190 --> 47:09.430 Und am Ende noch ein Beispiel bringen für eine universelle Familie. 47:11.670 --> 47:14.790 Jetzt war es vorhin schon so, wir hatten da den Satz gehört, der wie 47:14.790 --> 47:15.310 folgt lautet. 47:15.870 --> 47:19.370 Für eine zufällige Hash-Funktion, also eine von allen möglichen 47:19.370 --> 47:26.230 zufälligen Hash-Funktionen, ist für eine bestimmte Stelle k in der 47:26.230 --> 47:28.870 Tabelle die erwartete Anzahl von kollidierenden Elementen an dieser 47:28.870 --> 47:30.150 Stelle eben o von 1. 47:31.330 --> 47:34.330 Falls die Anzahl der eingefügten Elemente o von m ist. 47:36.590 --> 47:38.110 Das möchte ich jetzt nochmal kurz noch erweisen. 47:38.230 --> 47:39.670 Das wurde in der Vorlesung auch schon gemacht, aber ich wiederhole es 47:39.670 --> 47:40.010 nochmal kurz. 47:41.330 --> 47:44.250 Immer wenn man irgendwie einen Satz beweisen will über die erwartete 47:44.250 --> 47:47.910 Anzahl, muss man sich zuerst mal, also das ist meistens das Schema, 47:48.150 --> 47:50.650 man stellt sich eine Zufallsvariable auf, die diese Anzahl beschreibt 47:50.650 --> 47:52.330 und berechnet dann den Erwartungswert. 47:53.430 --> 47:54.150 Und das machen wir hier. 47:54.470 --> 47:57.390 Wir definieren diese Zufallsvariable x für ein festes k. 47:57.770 --> 48:00.130 Das ist eben gerade die Anzahl der Elemente, die kollidieren, also die 48:00.130 --> 48:01.710 Kollisionslänge bei diesem k. 48:03.530 --> 48:05.450 Also die Anzahl der Elemente, die auf dem gleichen Slot gehashed 48:05.450 --> 48:05.710 werden. 48:06.590 --> 48:08.290 Und von der müssen wir jetzt den Erwartungswert berechnen. 48:08.870 --> 48:09.850 Das machen wir. 48:10.070 --> 48:11.950 Wir führen ein m' ein. 48:12.250 --> 48:16.350 Das sind gerade die eingefügten Elemente, die als Kollision in Frage 48:16.350 --> 48:16.710 kommen. 48:17.370 --> 48:22.350 Und zwar sind es die, die einen anderen key haben als das, wo die 48:22.350 --> 48:23.170 Kollision entstehen soll. 48:24.030 --> 48:26.630 Und für jedes Element aus dieser Menge führen wir jetzt eine 0,1 48:26.630 --> 48:27.490 Zufallsvariable ein. 48:28.670 --> 48:32.950 Die 1 ist gerade dann, wenn dieses Element eine Kollision erzeugt. 48:34.710 --> 48:37.210 Und der Grund, warum wir das machen, ist, dass wir halt diese 48:37.210 --> 48:40.630 ursprüngliche Zufallsvariable x darstellen können als die Summe über 48:40.630 --> 48:41.530 alle x, e. 48:43.050 --> 48:44.950 Und das nutzen wir jetzt in der folgenden Rechnung aus. 48:47.830 --> 48:51.550 Erwartungswert von x ist gerade Erwartungswert über die Summe von 48:51.550 --> 48:52.890 diesen ganzen 0,1 Zufallsvariablen. 48:54.150 --> 48:56.570 Dann hier nutzen wir aus Linearität des Erwartungswertes. 48:58.330 --> 49:01.230 Hier nutzen wir aus, dass der Erwartungswert von der 0,1 49:01.230 --> 49:03.270 Zufallsvariable gerade die Wahrscheinlichkeit ist, dass die 49:03.270 --> 49:04.990 Zufallsvariable 1 ist. 49:07.870 --> 49:10.830 Dann nutzen wir hier aus, dass jetzt diese Wahrscheinlichkeit 49:10.830 --> 49:12.530 eigentlich unabhängig ist von der Wahl des Es. 49:13.650 --> 49:16.170 Also für alle gleich, das heißt wir können sie ersetzen durch die 49:16.170 --> 49:17.850 Anzahl der Elemente dieser Menge. 49:18.990 --> 49:20.670 Und jetzt rechnen wir diese Wahrscheinlichkeit hier unten aus. 49:22.870 --> 49:26.170 Es ist so, wichtig ist hier, wir betrachten die Wahrscheinlichkeit 49:26.170 --> 49:28.170 über die Wahl der Hash-Funktion. 49:28.970 --> 49:30.930 Also wir rechnen erstmal, wie viele Hash-Funktionen gibt es überhaupt? 49:31.430 --> 49:34.110 Naja, es gibt für jeden Schlüssel M Möglichkeiten. 49:34.970 --> 49:40.930 Das heißt es gibt M, Hochanzahl der Schlüsselmöglichkeiten, 49:41.930 --> 49:42.670 verschiedene Hash-Funktionen. 49:44.050 --> 49:46.510 Und wie viele davon erzeugen eine Kollision an der Stelle e? 49:46.510 --> 49:52.430 Naja, das sind halt genau die, für die der Wert e, also h von e schon 49:52.430 --> 49:53.210 festgelegt ist. 49:53.430 --> 49:55.170 Nämlich auf h von k. 49:55.650 --> 49:59.110 Und hat man für die restlichen Key-Minus-Eins-Möglichkeiten, Key-Minus 49:59.110 --> 50:01.550 -Eins -Keys, immer noch M-Möglichkeiten. 50:01.630 --> 50:05.910 Das heißt hat man M hoch Key-Minus-Eins verschiedene Hash-Funktionen, 50:05.950 --> 50:06.690 die die Kollision erzeugen. 50:07.350 --> 50:10.170 Das rechnen wir jetzt einfach aus, kommen dann auf M' durch M. 50:10.690 --> 50:14.890 M' ist kleiner als M, als Groß-M. 50:15.450 --> 50:18.870 Groß-M ist in O von klein M und deswegen steht hier O von 1. 50:21.390 --> 50:25.430 Wichtig, wir haben hier die Wahrscheinlichkeit über der Wahl der Hash 50:25.430 --> 50:26.030 -Funktionen gehabt. 50:27.270 --> 50:31.370 Und wir haben gesagt, wir wählen Hash-Funktionen aus allen möglichen. 50:32.310 --> 50:35.010 Und das ist aber in der Praxis nicht so gut möglich, denn alle 50:35.010 --> 50:36.110 möglichen Hash-Funktionen sind verdammt viele. 50:36.550 --> 50:38.670 Und sich eine Hash-Funktion, also eine zufällige Hash-Funktion zu 50:38.670 --> 50:40.070 merken, ist eigentlich nicht so gut möglich. 50:40.710 --> 50:44.710 Was man daher macht ist, man kann zeigen, dass dieses Ganze hier auch 50:44.710 --> 50:51.310 gilt, wenn man eine bestimmte Teilmenge von Hash-Funktionen auswählt, 50:51.590 --> 50:52.910 die bestimmte Eigenschaften haben. 50:52.990 --> 50:56.890 Und diese Teilmengen sind eben diese universellen Hash-Funktionen. 51:00.190 --> 51:03.270 Das hier sind alle möglichen Hash-Funktionen, eine Teilmenge davon, 51:03.410 --> 51:09.630 also eine Familie, ist universell, falls für eine zufällig gewählte 51:09.630 --> 51:15.710 Hash -Funktion aus der Familie und die Wahrscheinlichkeit, dass zwei 51:15.710 --> 51:20.030 beliebige Elemente auf die gleiche Stelle gehasht werden, gerade 1 51:20.030 --> 51:20.590 durch m ist. 51:21.390 --> 51:24.050 Und das ist vielleicht für das Übungsblatt auch ziemlich wichtig, dass 51:24.050 --> 51:29.090 man hier sieht, das sind wirklich zwei beliebige x und y, die man 51:29.090 --> 51:29.630 daraus wählt. 51:29.630 --> 51:32.970 Und das Theorium, was ich eben gezeigt habe, gilt eben auch für 51:32.970 --> 51:34.490 universelle Hash-Funktionen. 51:35.290 --> 51:37.810 Das war die Definition, jetzt möchte ich noch ein Beispiel bringen für 51:37.810 --> 51:41.090 eine universelle Familie von Hash-Funktionen. 51:41.710 --> 51:43.330 Wir haben in der Folge schon eines gehört, ich bringe noch etwas 51:43.330 --> 51:43.890 anderes hier. 51:44.610 --> 51:49.410 Und zwar die Hash-Funktionen, die auf Bit-Matrix-Multiplikationen 51:49.410 --> 51:49.690 basieren. 51:51.930 --> 51:56.530 Das funktioniert so, wir betrachten die zu herrschenden Elemente x als 51:56.530 --> 52:03.290 Bit -Vektoren der Länge k, und multiplizieren dann von links eine W 52:03.290 --> 52:13.370 -kreuz -k-Matrix drauf, wobei W gerade die Bit-Länge der Anzahl Plätze 52:13.370 --> 52:15.770 in der Hash-Tabelle ist. 52:16.890 --> 52:19.270 Das heißt, als Ergebnis von dieser Multiplikation kriegen wir eine Bit 52:19.270 --> 52:22.370 -Vektorlänge W und können den gerade interpretieren als Platz in der 52:22.370 --> 52:22.650 Tabelle. 52:24.430 --> 52:29.010 Da wir hier mit Bit-Matrixen rechnen, machen wir hier Arithmetik 52:29.010 --> 52:32.710 Modulo 2, Plus und Minus, das heißt das Plus, könnt ihr euch 52:32.710 --> 52:35.790 überlegen, wird ein XOR und das Mal wird dann ein AND. 52:37.590 --> 52:39.130 Um es zu verdeutlichen, vielleicht ein kleines Beispiel. 52:40.050 --> 52:46.150 Wir haben hier eine 2-kreuz-4-Matrix, weil die Elemente den Bit-Länge 52:46.150 --> 52:48.610 von 4 haben und die Tabelleneinträge den Bit-Länge von 2. 52:49.210 --> 52:51.050 Multiplizieren es hier einfach und dann können wir es einfach 52:51.050 --> 52:51.630 ausrechnen. 52:51.850 --> 52:57.290 Also hier 1 mal 1 gibt 1, 0 mal 0 gibt 0, 0 mal 1 gibt auch 0, 1 mal 1 52:57.290 --> 53:00.330 gibt wieder 1 und dann rechnen wir 1 plus 1, das gibt dann 0, Modulo 53:00.330 --> 53:00.610 2. 53:04.870 --> 53:06.870 Und das ist die Familie, die wir haben. 53:06.970 --> 53:08.710 Und jetzt möchte ich für diese Familie zeigen, dass sie universell 53:08.710 --> 53:08.870 ist. 53:08.970 --> 53:09.590 Was muss ich machen? 53:11.270 --> 53:16.490 Ich muss, wie gesagt, für eine beliebige Hash-Funktion, die aus dieser 53:16.490 --> 53:20.270 Familie gewählt wurde, zeigen, dass die Wahrscheinlichkeit, dass zwei 53:20.270 --> 53:22.830 beliebige Elemente aufeinander gehasht werden, gerade 1 durch m ist. 53:23.430 --> 53:24.190 Das mache ich jetzt. 53:26.050 --> 53:27.130 Also fangen wir mal an. 53:29.170 --> 53:34.850 Wir wollen zeigen, wann sind zwei beliebige Elemente am gleichen 53:34.850 --> 53:36.050 Platz, h von x gleich h von y. 53:36.550 --> 53:39.970 Laut Definition genau dann, wenn mx gleich my ist. 53:40.670 --> 53:44.450 Das laut Definition der Matrizenmultiplikation ist gerade dann der 53:44.450 --> 53:48.710 Fall, wenn hier zeilenweise Gleichheit besteht, also bei jeder Zeile 53:48.710 --> 53:50.730 der Matrizen hier. 53:51.870 --> 53:55.570 Also für alle Einträge 1 bis w, das hier gilt, wobei es hier gerade 53:55.570 --> 53:56.810 das x-Order darstellen soll. 53:59.030 --> 54:00.770 Und das definiert sich dann bei einem Gleichungssystem. 54:01.570 --> 54:04.250 Ein Gleichungssystem, das w Gleichungen hat. 54:04.250 --> 54:15.980 w war die Bitlänge der Anzahl Elemente in der Hashtable. 54:19.940 --> 54:23.060 w Gleichungen und eben w mal k Variablen. 54:23.160 --> 54:27.680 Denn jeder Eintrag in dieser Matrix ist halt einfach eine Variable. 54:28.580 --> 54:30.680 Und das heißt, wir haben mehr Variablen als Gleichungen. 54:30.780 --> 54:32.200 Das heißt, wir haben ein unterbestimmtes Gleichungssystem. 54:33.120 --> 54:33.960 Es gibt mehr als eine Lösung. 54:33.960 --> 54:37.540 Es gibt einen Lösungsraum von Lösungen der Dimension wk-w. 54:39.220 --> 54:42.400 Und da unser Körper halt einfach nur zwei Elemente hat, haben wir 54:42.400 --> 54:44.520 dementsprechend 2 hoch wk-w Lösungen. 54:45.320 --> 54:50.080 Lösungen heißt Wahlen von Matrizen. 54:53.890 --> 55:00.730 Ja, Wahlen von Matrizen, für die eben zwei beliebige Elemente x und y 55:00.730 --> 55:01.810 aufeinander gehasht werden. 55:02.510 --> 55:05.190 Insgesamt gibt es aber 2 hoch wk verschiedene Matrizen. 55:05.190 --> 55:08.350 Das heißt, die Wahrscheinlichkeit, dass wir eine rausnehmen, können 55:08.350 --> 55:09.070 wir einfach ausrechnen. 55:09.130 --> 55:12.170 2 hoch wk-w durch 2 hoch wk. 55:12.990 --> 55:14.970 Rechnen wir aus, gibt 1 durch 2 hoch w. 55:15.610 --> 55:18.230 w ist die Bitlänge von m. 55:18.850 --> 55:22.570 Also ist das hier gerade 1 durch m, was zu beweisen war. 55:23.330 --> 55:25.350 Okay, hallo zusammen. 55:27.010 --> 55:29.830 Ich erzähle euch noch ein bisschen was über Hashing. 55:32.650 --> 55:33.770 Wozu ist Hashing gut? 55:33.770 --> 55:37.010 Also wir haben schon gesehen, Hashing wird für Hashtabellen 55:37.010 --> 55:37.610 eingesetzt. 55:37.730 --> 55:40.890 Und Hashtabellen werden dafür eingesetzt, um erwartet Konstanzzeit zu 55:40.890 --> 55:43.170 bekommen in seinen Algorithmen. 55:43.310 --> 55:44.770 Wofür kann man noch Hashing einsetzen? 55:45.410 --> 55:48.850 Nun, wenn man da irgendwo seinen Webbrowser aufmacht, sieht man auch 55:48.850 --> 55:51.430 irgendwelche Hashes von Zertifikaten oder sowas. 55:52.850 --> 55:56.170 Das sind eigentlich nicht die gleichen Hashfunktionen, von denen wir 55:56.170 --> 55:56.590 hier reden. 55:57.070 --> 55:59.390 Weil die haben ja auch einen viel größeren Wertebereich. 55:59.390 --> 56:01.890 Wenn man sich da in so einem Browser anguckt, dann bekommt man so eine 56:01.890 --> 56:04.570 riesen Hexadezimalzahl und damit will man eigentlich jetzt kein Array 56:04.570 --> 56:05.050 indizieren. 56:06.430 --> 56:09.570 Das ist eine andere Type, es ist zwar auch Hashing, es ist aber eine 56:09.570 --> 56:10.610 andere Type von Hashing. 56:11.230 --> 56:15.430 Die heißen irgendwie kryptographische Hashes und deren Sinn ist quasi 56:15.430 --> 56:17.190 Einwegfunktionen darzustellen. 56:17.350 --> 56:20.430 Ich möchte mein Zertifikat haben, ich möchte das schrumpfen auf wenige 56:20.430 --> 56:23.830 Bytes und ich möchte da nur die Bytes vergleichen. 56:23.830 --> 56:28.950 Und dann mit möglichst wenig Kollision über diese Vergleiche 56:28.950 --> 56:31.530 festzustellen, dass die Zertifikate beispielsweise unterschiedlich 56:31.530 --> 56:31.790 sind. 56:32.710 --> 56:36.510 Das ist nicht das Gleiche, was wir hier mit unseren Hashtabellen 56:36.510 --> 56:37.010 anstellen. 56:38.870 --> 56:42.870 In den Hashtabellen schrumpfen wir die Daten zusammen, um damit in 56:42.870 --> 56:45.590 einem Array irgendwas zu indizieren. 56:48.230 --> 56:50.910 Um da vielleicht Klarheit zu schaffen. 56:52.110 --> 56:56.510 MD5 und SHA sind diese typischen kryptographischen Digest- oder 56:56.510 --> 56:57.670 Hashfunktionen, die man kennt. 56:58.970 --> 57:02.770 Wir haben hier andere Hashfunktionen, der Julian hat zwei gerade 57:02.770 --> 57:03.370 vorgestellt. 57:04.190 --> 57:07.510 Andere Sache ist die Moduloprimzahl, die ihr auf dem Übungsblatt habt. 57:09.690 --> 57:11.550 Wie hasht man den Zeichenketten? 57:12.630 --> 57:13.270 Blöde Frage. 57:15.010 --> 57:18.590 Und jetzt Hashing in dem Sinn, dass wir darin ein Arrayindex haben 57:18.590 --> 57:18.870 wollen. 57:21.010 --> 57:25.030 Nun, die blödste Art und Weise, die jeder sich denken könnte, ist, ich 57:25.030 --> 57:29.410 nehme einfach jeden Buchstaben und rechne die Buchstabenzahlen 57:29.410 --> 57:31.250 zusammen und mache dann Modulo 2 auch irgendwas. 57:31.590 --> 57:33.170 Ich addiere einfach meine Buchstaben bzw. 57:33.930 --> 57:37.190 der Ascii-Wert der Buchstaben und dann Modulo irgendwas. 57:37.350 --> 57:38.030 Das ist schlecht. 57:38.370 --> 57:39.130 Warum ist das schlecht? 57:39.790 --> 57:42.510 Weil der Sinn von so einer Hashfunktion ist, dass ich nicht einfach 57:42.510 --> 57:46.390 irgendwie eine Kollision erzeugen kann, indem ich beispielsweise zwei 57:46.390 --> 57:47.110 Buchstaben tausche. 57:48.250 --> 57:50.010 Das wäre aber in dem Fall schon eine Kollision. 57:50.210 --> 57:54.110 Also auf die nächstdümmere Idee, wie kommt man, man multipliziert das 57:54.110 --> 57:54.830 mit Primzahlen. 57:55.670 --> 57:56.270 Ja, ist doch besser. 57:57.830 --> 58:05.570 Aber wenn man dann richtige Hashfunktionen für Zeichenketten braucht, 58:05.650 --> 58:08.310 wie beispielsweise in irgendwelchen Datenbanken, wo es dann wirklich 58:08.310 --> 58:12.410 um Geld geht, dann haben sich die Leute beispielsweise diese 58:12.410 --> 58:16.710 Hashfunktion ausgedacht, die dann auch in Berkeley DB und sonst wo 58:16.710 --> 58:20.090 überall verwendet wurde, in den alten Domain-Name-Servern und so. 58:20.250 --> 58:22.670 Und die ist schon ganz gut. 58:24.530 --> 58:25.470 Ja, ein Schritt. 58:26.350 --> 58:28.710 Genau, und die haben sich das überlegt, dass man das eigentlich als 58:28.710 --> 58:31.050 Bit -Operation machen kann. 58:32.130 --> 58:33.630 So, das ist schon relativ trickreich. 58:33.630 --> 58:40.610 Wenn ihr Perl programmiert oder Hadoop oder Python, oder in PHP mit so 58:40.610 --> 58:45.430 assoziativen Arrays arbeitet, wo man so eine Zeichenkette einfach in 58:45.430 --> 58:50.870 so ein Hash reintun kann, dann durchläuft eure Zeichenkette MurmurHash 58:50.870 --> 58:55.470 oder diese etwas ältere, wie heißt der, FowlerNullWoHash-Funktion. 58:56.330 --> 58:57.410 Dann durchläuft das so was. 58:57.410 --> 59:01.950 Und wieder multipliziert er irgendwie die Stellen mit irgendetwas und 59:01.950 --> 59:04.290 berechnet halt am Ende einen Array-Wert. 59:05.310 --> 59:09.970 Nur mal so als Info, um Begriffe zu trennen. 59:11.930 --> 59:14.230 Gut, die Zahlen müsst ihr nicht auswendig lernen. 59:16.670 --> 59:17.910 Okay, sortieren. 59:18.710 --> 59:20.590 Nochmal von vorne losgelegt. 59:20.590 --> 59:26.490 Also der Chef hat euch schon zwei oder drei Sortierverfahren gezeigt. 59:28.290 --> 59:29.390 Nochmal von vorne. 59:29.490 --> 59:30.990 Was machen wir beim Sortieren eigentlich? 59:32.130 --> 59:36.670 Beim Sortieren von fünf Elementen suchen wir in dieser Tabelle, 59:37.070 --> 59:41.310 welches alle Permutationen von fünf Elementen darstellt, die richtige 59:41.310 --> 59:41.930 Permutation. 59:43.090 --> 59:44.190 Und davon gibt es nur eine. 59:46.230 --> 59:48.710 Es sei denn, es gibt gleiche Elemente, da wird es dann interessant. 59:52.850 --> 59:55.510 Was wollte man eigentlich mit so einem Sortierverfahren machen? 59:55.670 --> 01:00:00.190 Naja, im Prinzip so eine Art binäre Suche auf diesen Permutationen. 01:00:01.010 --> 01:00:06.730 Am Ende ist alles, was dann in Log N ist, Log 2 N, eine binäre Suche 01:00:06.730 --> 01:00:15.590 aus dieser großen Liste von Permutationen. 01:00:15.690 --> 01:00:20.830 Wenn man sich überlegt, was für Möglichkeiten gibt es, so ein Array zu 01:00:20.830 --> 01:00:25.670 sortieren, die einfachsten Überlegungen, die dann hochkommen, ist 01:00:25.670 --> 01:00:29.050 beispielsweise, ich suche das kleinste Element raus und lege das 01:00:29.050 --> 01:00:29.550 beiseite. 01:00:30.470 --> 01:00:31.290 Das ist Selektion. 01:00:31.610 --> 01:00:35.250 Insertion ist, ich nehme ein Element, tue es an die richtige Stelle in 01:00:35.250 --> 01:00:36.310 einer bereits sortierten. 01:00:39.490 --> 01:00:42.150 Austausch ist, ich gucke mir meine Elemente an und fange an, wild zu 01:00:42.150 --> 01:00:42.550 vertauschen. 01:00:42.610 --> 01:00:45.010 Da brauche ich natürlich eine Strategie, um irgendwann mal zum Ziel zu 01:00:45.010 --> 01:00:45.210 kommen. 01:00:48.070 --> 01:00:52.870 In der Regel muss man diese Strategien trickreich anwenden, um 01:00:52.870 --> 01:00:56.230 tatsächlich diese in Log N untere Schranke zu erreichen, die der Chef 01:00:56.230 --> 01:00:59.730 gerade gezeigt hat oder noch nicht gerade gezeigt hat. 01:01:02.790 --> 01:01:06.010 Der einfachste Algorithmus von diesem Ganzen ist Insertion Sort, 01:01:06.330 --> 01:01:08.890 Selection Sort, bin schon zu schnell. 01:01:08.890 --> 01:01:12.930 Selection Sort ist einfach, es geht durch das Array durch. 01:01:13.850 --> 01:01:17.470 Ich merke mir das Minimum, was ich bisher kenne und suche mir über den 01:01:17.470 --> 01:01:20.050 Rest einfach das Minimum. 01:01:20.110 --> 01:01:21.030 Gehe es mal drüber. 01:01:25.250 --> 01:01:28.710 Das Schöne an diesen ganzen Sortieralgorithmen ist jetzt nicht 01:01:28.710 --> 01:01:35.450 unbedingt das Vorgehen des Algorithmuses, sondern dass man die 01:01:35.450 --> 01:01:37.530 analytisch greifbar machen kann. 01:01:38.290 --> 01:01:42.090 Und was uns jetzt interessiert bei diesen ganzen Sortieralgorithmen 01:01:42.090 --> 01:01:47.270 ist, wie teuer sind die und was man dabei zählt, ist in der Regel die 01:01:47.270 --> 01:01:48.590 Anzahl der Vergleiche. 01:01:50.170 --> 01:01:53.910 Und das Schöne ist, dass man die mit schönen mathematischen Methoden 01:01:53.910 --> 01:01:56.090 dann tatsächlich zählen und greifbar machen kann. 01:01:57.410 --> 01:02:00.390 Obwohl am Anfang diese Tabelle stand. 01:02:01.410 --> 01:02:02.390 Na, die da. 01:02:04.570 --> 01:02:07.490 So, und jetzt, ja, Selection Sort. 01:02:07.910 --> 01:02:11.670 Jetzt stelle ich die Frage, wie viele Vergleiche wird bei N Elementen, 01:02:11.870 --> 01:02:15.170 wie oft wird diese rote Linie, diese rote Anweisung ausgeführt? 01:02:15.250 --> 01:02:17.950 Wie viele Vergleiche wird bei N Elementen ausgeführt? 01:02:19.290 --> 01:02:20.410 Und jetzt muss man nachdenken. 01:02:22.370 --> 01:02:27.990 Nun, diese Schleife, der schleifende Rumpf, weil er keinen Abbruch 01:02:27.990 --> 01:02:29.970 irgendwie enthält, läuft N mal. 01:02:31.790 --> 01:02:38.850 Und dieser innere Teil läuft in der Iten, im Iten-Durchlauf N minus I 01:02:38.850 --> 01:02:39.210 mal. 01:02:41.510 --> 01:02:45.190 N minus I, wir müssen uns überlegen, ob plus 1 oder minus 1, müsste N 01:02:45.190 --> 01:02:46.770 minus I sein, minus 1. 01:02:46.770 --> 01:02:51.330 Und das ist die Anzahl der Male, wie diese rote Anweisung ausgeführt 01:02:51.330 --> 01:02:51.530 wird. 01:02:51.590 --> 01:02:55.810 Das ist die einfachste, die einfachste Analyse, die man sich da 01:02:55.810 --> 01:02:56.490 überlegen kann. 01:03:02.170 --> 01:03:02.570 Genau, 01:03:06.970 --> 01:03:10.110 und dann, ihr kennt das, habt das vielleicht schon im Netz gesehen. 01:03:10.270 --> 01:03:14.130 Ich habe mir letztes Jahr nicht nehmen lassen, ein kleines Programm zu 01:03:14.130 --> 01:03:19.470 schreiben, was dann tatsächlich mal diese Funktion ausführt und zählt, 01:03:19.770 --> 01:03:21.610 wie oft dieser Vergleich auftritt. 01:03:23.370 --> 01:03:26.490 Was wir jetzt erwartet haben, ist, es läuft N mal. 01:03:28.250 --> 01:03:33.050 N mal durch, es läuft immer N mal durch und es läuft immer N minus 1 01:03:33.050 --> 01:03:33.430 mal durch. 01:03:33.550 --> 01:03:35.830 Deswegen habe ich N mal N minus 1. 01:03:37.470 --> 01:03:39.050 Ah ja, wie viele Vergleiche, genau. 01:03:40.030 --> 01:03:42.770 N mal N minus 1, halbe. 01:03:44.090 --> 01:03:45.090 Woher kommt die halbe? 01:03:55.890 --> 01:03:57.190 Ah, jetzt weiß ich es. 01:04:00.150 --> 01:04:01.970 Gucken wir uns mal an, was das Programm macht. 01:04:04.770 --> 01:04:05.370 So. 01:04:06.990 --> 01:04:08.350 Nein, wo ist es? 01:04:11.230 --> 01:04:11.910 Hier ist es. 01:04:14.070 --> 01:04:21.730 Wenn man Selection Sort ausführt auf 100 Elementen, dann sieht das so 01:04:21.730 --> 01:04:22.050 aus. 01:04:22.590 --> 01:04:29.450 Er geht einmal durch, merkt sich immer das Kleinste, was er aktuell 01:04:29.450 --> 01:04:29.690 kennt. 01:04:29.790 --> 01:04:31.950 Das ist das Min, was vorher in diesem Pseudocode war. 01:04:31.950 --> 01:04:34.530 Und schiebt es dann an den Anfang. 01:04:37.660 --> 01:04:39.320 So, wie viele Vergleiche braucht das? 01:04:41.060 --> 01:04:43.060 Nun, wir laufen das erste Mal N mal durch. 01:04:44.440 --> 01:04:46.780 Wir laufen das nächste Mal N minus 1 mal durch. 01:04:47.740 --> 01:04:50.580 Und vergleichen jedes Mal mit dem aktuell Kleinsten. 01:04:51.580 --> 01:04:56.200 Heißt, wir haben N plus N minus 1 plus N minus 2 plus N minus 3, N 01:04:56.200 --> 01:04:58.240 minus 4 und so weiter und so fort. 01:04:58.240 --> 01:05:02.720 Ach ja, da oben zählt es, wie viele Vergleiche er gerade gezählt hat. 01:05:03.620 --> 01:05:05.240 Und bevor das jetzt fertig ist, 01:05:08.460 --> 01:05:11.600 möchte ich jetzt von euch wissen, was da am Ende rauskommt. 01:05:14.160 --> 01:05:18.860 Also N mal, N vergleiche beim ersten Mal, N minus 1 vergleiche beim 01:05:18.860 --> 01:05:21.020 zweiten Mal, N minus 3 vergleiche beim dritten Mal. 01:05:21.020 --> 01:05:26.060 Das ist die Summe von i gleich 0 bis N von i. 01:05:28.080 --> 01:05:28.620 Ist was? 01:05:29.340 --> 01:05:29.340 Ja, 01:05:32.380 --> 01:05:36.240 also eigentlich wollte ich es allgemein, weil nachher kann ich... 01:05:37.800 --> 01:05:39.700 N mal N minus 1... 01:05:40.360 --> 01:05:40.860 Äh, was? 01:05:40.960 --> 01:05:42.180 N mal N minus 1 halbe. 01:05:43.080 --> 01:05:46.580 Das sind 100 N für 1950. 01:05:49.720 --> 01:05:50.840 N ist 100. 01:05:50.940 --> 01:05:53.440 N mal N minus 1 halbe. 01:05:55.380 --> 01:05:58.240 Das ist 100 mal 99 geteilt durch 2. 01:05:59.000 --> 01:06:00.300 Das sind 4950. 01:06:11.790 --> 01:06:13.370 So, gucken wir nochmal zurück. 01:06:13.630 --> 01:06:16.830 Ich habe da von N mal N minus 1 halben geredet. 01:06:18.690 --> 01:06:19.570 Mal zurück. 01:06:20.510 --> 01:06:24.010 Ich habe da irgendwie gerade vorhin behauptet, die Schleife geht N mal 01:06:24.010 --> 01:06:25.590 und das Innere N minus 1 mal. 01:06:26.010 --> 01:06:26.930 Das stimmt irgendwie nicht. 01:06:29.190 --> 01:06:30.770 Was habe ich denn da gerade vorhin erzählt? 01:06:34.590 --> 01:06:36.630 Okay, überlegen wir uns das hier nochmal. 01:06:40.490 --> 01:06:42.710 Eine Schleife, die läuft garantiert N mal. 01:06:45.590 --> 01:06:51.550 Die hier läuft bei i gleich 0 von 1 bis N minus 1. 01:06:55.450 --> 01:07:02.430 Und für i gleich 1 läuft die hier von 2 bis N minus 1. 01:07:05.810 --> 01:07:10.050 Das ist die gleiche Folge, die ich vorher gerade genannt habe. 01:07:11.870 --> 01:07:17.750 Die große Schleife ist die Schleife des kleinen grünen Elementes, was 01:07:17.750 --> 01:07:20.070 dann von links nach rechts lief. 01:07:22.210 --> 01:07:26.030 Die innere Schleife ist die Schleife, wo der dann das nächste Element 01:07:26.030 --> 01:07:26.290 sucht. 01:07:27.770 --> 01:07:31.170 Das erste Mal geht er N mal durch, dann geht er N minus 1 mal durch. 01:07:32.070 --> 01:07:33.270 Das ist, was hier gezeigt ist. 01:07:34.130 --> 01:07:39.130 N mal diese Schleife und innen drin ist es immer die 01:07:39.130 --> 01:07:43.170 Schleifendurchlaufzahl mal die Vergleiche. 01:07:46.730 --> 01:07:50.430 Wenn i die Anzahl der Vergleiche innen drin ist, dann erhöht sich i 01:07:50.430 --> 01:07:52.270 immer um 1, beziehungsweise es verringert sich um 1. 01:07:57.370 --> 01:08:02.070 Das ist der einfachste Algorithmus, an den man sich denken kann. 01:08:02.590 --> 01:08:05.010 Der, den ich vorher schon genannt hatte und was Professor Sander schon 01:08:05.010 --> 01:08:06.910 erzählt hat, ist Insertion Sort. 01:08:07.690 --> 01:08:11.490 Der ist nicht komplizierter in dem Sinn, dass er immer ein Element 01:08:11.490 --> 01:08:14.010 nimmt und an die richtige Stelle einfügt. 01:08:16.210 --> 01:08:20.390 Visuell sieht man das immer am besten, was der dann macht. 01:08:22.070 --> 01:08:22.790 Ist das da? 01:08:28.790 --> 01:08:29.730 Falsche Taste. 01:08:32.210 --> 01:08:32.930 Insertion Sort. 01:08:35.270 --> 01:08:36.670 Macht das da hier. 01:08:44.670 --> 01:08:51.390 Er nimmt sich, der vordere Teil ist sortiert und dann wird ein Element 01:08:51.390 --> 01:08:53.650 genommen, an die richtige Stelle eingefügt. 01:08:53.750 --> 01:08:56.910 Und das wird in dem Fall einfach eingefügt, indem es hingetauscht 01:08:56.910 --> 01:08:59.410 wird, bis es an der richtigen Stelle ist. 01:08:59.410 --> 01:09:00.270 Und wie merkt man das? 01:09:00.330 --> 01:09:05.790 Bei einer sortierten Folge, indem ganz einfach der Wert läuft so weit, 01:09:06.290 --> 01:09:08.810 bis das Element dahinter kleiner ist. 01:09:11.790 --> 01:09:15.170 Das geht ganz an den Anfang, weil es nichts mehr findet, aber das hier 01:09:15.170 --> 01:09:18.150 wird ungefähr bis dahin laufen, weil dieses Element kleiner ist als 01:09:18.150 --> 01:09:18.530 das da. 01:09:19.550 --> 01:09:20.590 Das ist Insertion Sort. 01:09:23.730 --> 01:09:27.050 Jetzt stellt sich natürlich die Preisfrage, wie viele Vergleiche 01:09:27.050 --> 01:09:28.010 braucht Insertion Sort? 01:09:29.410 --> 01:09:31.310 Gucken wir uns noch mal den Pseudocode an. 01:09:34.050 --> 01:09:36.030 Wo treten denn da Vergleiche auf? 01:09:37.290 --> 01:09:37.510 Da. 01:09:39.470 --> 01:09:44.690 Die Schleife läuft wieder einmal durch, weil keine Abbruchbedingung 01:09:44.690 --> 01:09:45.430 innen drin ist. 01:09:45.730 --> 01:09:47.190 Aber wie oft läuft die hier? 01:09:48.000 --> 01:09:54.730 Die läuft so lange nach links, bis das Element, was davor kleiner ist. 01:09:54.830 --> 01:10:00.850 Solange das Element davor kleiner ist als das aktuell zu 01:10:00.850 --> 01:10:01.450 durchsuchende. 01:10:01.730 --> 01:10:05.590 In dem Moment, in dem es größer wird. 01:10:07.750 --> 01:10:14.510 Solange j-1 kleiner ist als x, läuft es nach links. 01:10:17.960 --> 01:10:18.680 Stimmt das? 01:10:20.040 --> 01:10:20.980 Nee, das stimmt nicht. 01:10:23.160 --> 01:10:24.300 Es müsste größer sein, ja? 01:10:25.560 --> 01:10:29.180 Solange das Element links davon größer ist, läuft es nach links. 01:10:29.700 --> 01:10:31.420 Gucken wir doch in den Code rein, was da passiert. 01:10:35.830 --> 01:10:36.870 Also das, was passiert. 01:10:47.670 --> 01:10:48.630 Ja, falsch. 01:11:00.940 --> 01:11:02.020 Ah ja, wunderbar. 01:11:07.320 --> 01:11:11.580 Okay, solange es läuft eine Schleife n-mal durch. 01:11:12.700 --> 01:11:15.760 Es nimmt sich ein Element raus, markiert es blau oder so. 01:11:17.340 --> 01:11:21.240 Und jetzt läuft er nach links, solange, also das j wird immer kleiner, 01:11:21.880 --> 01:11:25.900 solange der Schlüssel, also das link, das Element davor größer ist als 01:11:25.900 --> 01:11:26.400 der Schlüssel. 01:11:27.720 --> 01:11:28.680 Sonst funktioniert die Sache nicht. 01:11:29.400 --> 01:11:31.100 Diese Schleife läuft n-mal. 01:11:32.180 --> 01:11:34.340 Aber wie oft läuft diese Schleife hier innen drin? 01:11:35.600 --> 01:11:36.800 Was ist denn der schlimmste Fall? 01:11:38.760 --> 01:11:41.660 Nun, der schlimmste Fall ist, er muss wieder ganz an den Anfang jedes 01:11:41.660 --> 01:11:41.880 Mal. 01:11:41.960 --> 01:11:42.740 Wann tritt der auf? 01:11:44.940 --> 01:11:45.740 Sagt es mir jemand? 01:11:47.000 --> 01:11:47.120 Ja? 01:11:50.240 --> 01:11:53.400 Ja, also bei welcher Eingabe, meinte ich eigentlich. 01:11:55.000 --> 01:12:01.540 Ja, also das tritt dann auf, wenn die Eingabe sortiert ist, absteigend 01:12:01.540 --> 01:12:04.700 oder aufsteigend, gucken wir mal, also andersrum sortiert ist. 01:12:04.700 --> 01:12:08.320 Weil so ist es bestmöglich. 01:12:12.290 --> 01:12:15.270 Da braucht er nämlich gerade mal 100 oder 101 Vergleiche, 100. 01:12:17.990 --> 01:12:25.570 Aber andersrum ist er damit beschäftigt, das die ganze Zeit nach vorne 01:12:25.570 --> 01:12:26.070 umzusortieren. 01:12:27.770 --> 01:12:29.350 So, wie viele Vergleiche braucht er hier? 01:12:37.510 --> 01:12:39.990 Ja, n-mal n-minus 1 halber, wie üblich, wie vorher. 01:12:41.650 --> 01:12:47.990 Wenn wir das durchlaufen lassen, sind es wieder 4.950 Vergleiche. 01:12:51.990 --> 01:12:54.090 Okay, ich werde das mal hier ändern, das ist falsch rum. 01:12:56.110 --> 01:12:59.630 Ein kleiner Trick, den man bei dieser Implementierung anwenden kann, 01:12:59.710 --> 01:13:01.370 ist ein Sentinel einzufügen. 01:13:02.190 --> 01:13:02.390 Warum? 01:13:03.610 --> 01:13:07.370 Hier, das ist die innerste Schleife und die wird unglaublich oft 01:13:07.370 --> 01:13:07.970 ausgeführt. 01:13:08.710 --> 01:13:12.890 Wenn man auch nur eine von diesen beiden Bedingungen entfernen kann, 01:13:13.070 --> 01:13:14.200 spart man sich sehr viel Rechenzeit. 01:13:16.390 --> 01:13:21.910 Und beispielsweise kann man diese j größer 0 Bedingung entfernen, wenn 01:13:21.910 --> 01:13:25.650 man ein Sentinel einfügt, nämlich ein Minus und Endlich quasi vor 01:13:25.650 --> 01:13:26.610 dieses Array steckt. 01:13:26.970 --> 01:13:29.070 Weil dann breche ich da immer ab. 01:13:30.890 --> 01:13:33.630 Und dadurch spare ich mir eins von diesen zwei Bedingungen. 01:13:34.410 --> 01:13:37.270 Das kommt in der Vorlesung noch ein paar Mal vor, das sind sogenannte 01:13:37.270 --> 01:13:37.770 Sentinels. 01:13:37.970 --> 01:13:40.390 Natürlich hat man eigentlich in der Realität kein Minus und Endlich, 01:13:41.170 --> 01:13:43.170 aber da macht man halt 0 hin. 01:13:43.710 --> 01:13:44.590 Irgendetwas, was passt. 01:13:46.110 --> 01:13:50.510 So, wir haben jetzt schon festgestellt, Insertion Sort hat N mal N-1 01:13:50.510 --> 01:13:51.910 halbe Worst Case. 01:13:52.430 --> 01:13:53.810 Aber was ist der Average Case? 01:13:54.490 --> 01:13:58.270 Und jetzt zurück, was ist eigentlich eine Average Case Analyse? 01:13:59.190 --> 01:14:05.030 Ganz wichtig, Average Case ist, ich gucke mir die durchschnittliche 01:14:05.030 --> 01:14:09.830 Laufzeit an meines Algorithmuses über alle möglichen Eingaben, die er 01:14:09.830 --> 01:14:11.090 haben kann. 01:14:12.090 --> 01:14:15.910 Jetzt stelle ich mir die Frage, bei meinem Algorithmus, was sind denn 01:14:15.910 --> 01:14:17.110 alle möglichen Eingaben? 01:14:20.050 --> 01:14:23.410 Alle möglichen Eingaben sind sämtliche Arten und Weisen, wie die 01:14:23.410 --> 01:14:25.630 Zahlen in dem Array verdreht sein können. 01:14:25.630 --> 01:14:28.930 Denn meine Ausgabe ist klar, da sollen die aufsteigend sein. 01:14:30.450 --> 01:14:34.750 Das heißt, für diesen Algorithmus ist natürlich wichtig, wie viele 01:14:34.750 --> 01:14:37.610 Verdrehungen sozusagen in diesem Array drinstehen. 01:14:38.350 --> 01:14:41.790 Und wenn man sich jetzt in dem Programmchen mal anguckt, was denn 01:14:41.790 --> 01:14:47.630 tatsächlich mal bei so einer zufälligen Permutation passiert. 01:14:50.850 --> 01:14:52.230 Also jetzt wieder zufällig. 01:14:55.720 --> 01:14:56.240 Dann... 01:14:58.460 --> 01:15:04.820 So, was passiert denn, so gefühlsmäßig ist es so, dass wenn dieses 01:15:04.820 --> 01:15:09.420 Element genommen wird, wird es aktuell relativ häufig ganz nach vorne 01:15:09.420 --> 01:15:11.720 geschoben, aber es wird ja auch manchmal gar nicht geschoben. 01:15:12.620 --> 01:15:17.040 Das ist so, das klingt irgendwie so, als ob man das noch analytisch 01:15:17.040 --> 01:15:17.720 greifen könnte. 01:15:18.640 --> 01:15:19.820 Und das ist ungefähr so die Hälfte. 01:15:21.200 --> 01:15:22.320 Das ist nämlich schon die Antwort. 01:15:22.320 --> 01:15:23.360 Aber warum? 01:15:25.400 --> 01:15:28.980 Es riecht so, als ob es ungefähr die Hälfte wäre, weil so die Hälfte 01:15:28.980 --> 01:15:32.900 der Wahlen geht ganz weit nach vorne, manchmal geht es ganz wenig nach 01:15:32.900 --> 01:15:33.120 vorne. 01:15:33.980 --> 01:15:35.820 Und das summiert sich dann auf. 01:15:38.540 --> 01:15:42.400 Der Trick jetzt, jetzt muss ich hier umschalten, gucken wir mal, was 01:15:42.400 --> 01:15:42.760 passiert. 01:15:44.020 --> 01:15:44.460 Der Trick. 01:15:46.560 --> 01:15:49.540 Wie analysiert man jetzt den Average Case von Insertion Sort? 01:15:49.540 --> 01:15:54.680 Der Chef wird die Average Case Analyse von QuickSort zeigen nächste 01:15:54.680 --> 01:15:56.220 Woche, fortsetzen. 01:15:56.660 --> 01:15:58.660 Ich will euch zeigen, wie das mit Insertion Sort geht. 01:15:59.400 --> 01:16:01.580 Dazu vereinfachen wir Insertion Sort ein bisschen. 01:16:02.580 --> 01:16:05.060 Wir wollen eigentlich die Anzahl der Vergleiche hier zählen. 01:16:05.560 --> 01:16:07.280 Das stellt sich aber relativ schwierig heraus. 01:16:07.400 --> 01:16:10.780 Was wir zählen werden, ist die Anzahl der Swaps, die hier innen drin 01:16:10.780 --> 01:16:11.240 passiert. 01:16:11.240 --> 01:16:14.900 Was ich hier jetzt verändert habe, in diesem Code, ist, ich habe 01:16:14.900 --> 01:16:18.260 dieses X quasi hier reingezogen und nicht mehr als temporäre Variable 01:16:18.260 --> 01:16:19.900 gemacht, sondern dass er immer vertauscht. 01:16:21.700 --> 01:16:24.700 Es swappt, es vereinfacht die ganze Sache und wir sehen jetzt die 01:16:24.700 --> 01:16:25.660 Anzahl der Swaps. 01:16:28.100 --> 01:16:30.360 Und Permutationen haben ganz schöne Eigenschaften. 01:16:31.940 --> 01:16:33.260 Permutationen haben schöne Eigenschaften. 01:16:33.640 --> 01:16:40.300 Und eine dieser Eigenschaften ist die Anzahl der Inversionen, die in 01:16:40.300 --> 01:16:42.620 so einer Permutation ist. 01:16:42.720 --> 01:16:46.580 Hier ist so eine Permutation, die ist geschrieben, hier oben steht 01:16:46.580 --> 01:16:50.900 immer 1, 2, 3, 4, 5, 6, 1 bis N und hier unten steht, worauf das 01:16:50.900 --> 01:16:51.940 abgebildet ist. 01:16:52.540 --> 01:16:58.820 So, und eine Kennzahl von Inversionen, die ihr schon kennt, ist, naja, 01:16:59.180 --> 01:17:02.440 eine Kennzahl von Permutationen ist Inversion, ja, und die ist ein 01:17:02.440 --> 01:17:02.880 Paar. 01:17:05.120 --> 01:17:11.820 Ich habe zwei Zahlen, i und j, und das, i ist kleiner als j, und das 01:17:11.820 --> 01:17:12.860 ist eine Inversion, 01:17:17.050 --> 01:17:24.730 wenn der Wert der Permutation größer ist als der Wert, naja, die 01:17:24.730 --> 01:17:31.270 beiden Zahlen in dieser Permutation falsch rumstehen. 01:17:32.110 --> 01:17:34.310 Der Wert links größer ist als der Wert rechts. 01:17:34.550 --> 01:17:38.130 Diese Inversion kennt ihr, weil das braucht man bei den Determinanten 01:17:38.130 --> 01:17:41.470 in linearer Algebra. 01:17:41.470 --> 01:17:47.470 Ja, das ist ein Fehlstand, das ist ein Fehlstand, das ist einer, 01:17:48.970 --> 01:17:53.170 finden wir noch den Rest, das ist einer, es müssten fünf sein, der ist 01:17:53.170 --> 01:17:59.030 richtig rum, der ist richtig rum, der ist nicht, einer fehlt noch, die 01:17:59.030 --> 01:17:59.830 da hier, nein. 01:18:02.270 --> 01:18:05.990 Man muss, um die zu berechnen, muss man von jedem Wert alle anderen 01:18:05.990 --> 01:18:06.430 prüfen. 01:18:07.550 --> 01:18:09.930 4,1 habe ich, ah ja, 4,1. 01:18:12.370 --> 01:18:13.290 Relativ teuer. 01:18:14.150 --> 01:18:19.870 Gut, da wir nicht mehr ganz viel Zeit haben, den Rest mal online. 01:18:23.250 --> 01:18:26.890 Also, was ist die maximale Anzahl von Inversionen in sowas? 01:18:28.530 --> 01:18:36.230 Die minimale Anzahl ist 0, weil die sortierte Folge hat 0 Inversionen. 01:18:36.230 --> 01:18:40.890 Die größte Anzahl von Inversionen ist n mal n minus 1 halbe, ist genau 01:18:40.890 --> 01:18:41.990 umgekehrt sortiert. 01:18:42.830 --> 01:18:43.110 Warum? 01:18:44.030 --> 01:18:47.550 Nun, ich habe das gerade versucht vorzumachen, für jeden Wert muss man 01:18:47.550 --> 01:18:50.010 quasi durchgehen und zählen, ob die falsch rum stehen. 01:18:50.970 --> 01:18:53.730 Das heißt, ich kann zwei auswählen und die sind falsch rum. 01:18:54.130 --> 01:18:57.470 Und deswegen aus n Zahlen zwei ausgewählt ist immer n über zwei 01:18:57.470 --> 01:18:59.270 Möglichkeiten. 01:19:00.350 --> 01:19:02.370 Das heißt, das ist n mal n minus 1 halbe. 01:19:05.070 --> 01:19:10.690 Und jetzt, um Insertion Sort anzugucken, ist der Witz dabei, dass 01:19:10.690 --> 01:19:15.810 Insertion Sort nur Paare vertauscht, die erstens falsch rum stehen und 01:19:15.810 --> 01:19:17.410 zweitens nebeneinander stehen. 01:19:19.410 --> 01:19:25.590 Wenn man das sich nochmal anguckt, Insertion Sort, stehen die Paare, 01:19:26.430 --> 01:19:28.830 diejenigen, die vertauscht werden, stehen immer nebeneinander. 01:19:31.710 --> 01:19:34.890 Und werden nur vertauscht, wenn sie falsch rum stehen. 01:19:35.290 --> 01:19:39.550 Und damit wird in jedem dieser Swaps eine Inversion getauscht und der 01:19:39.550 --> 01:19:42.610 Gesamtzahl in der Permutation um eins verringert. 01:19:43.390 --> 01:19:47.250 Jetzt stellt sich damit die Frage, die erwartete Laufzeit von 01:19:47.250 --> 01:19:51.670 Insertion Sort ist die erwartete Anzahl von Inversionen in einer 01:19:51.670 --> 01:19:52.230 Permutation. 01:19:53.810 --> 01:19:54.790 So, was ist das? 01:19:56.150 --> 01:19:57.670 Das kann man auch ausrechnen. 01:19:58.750 --> 01:20:01.130 Gucken wir uns das mal an. 01:20:03.990 --> 01:20:03.990 Ich 01:20:11.030 --> 01:20:13.690 fürchte, die Zeit läuft davon. 01:20:38.210 --> 01:20:48.020 Gesucht ist die erwartete Anzahl von Inversionen in einer Permutation. 01:20:50.640 --> 01:20:54.920 In einer beliebig gewählten Permutation Sn. 01:20:56.760 --> 01:21:01.460 Dazu definiert man sich eine Indikator-Zufallsvariable, wie wir das in 01:21:01.460 --> 01:21:02.680 der Vorlesung gemacht haben. 01:21:03.820 --> 01:21:09.500 Erstmal eine Zufallsvariable von Sigma, die ist einfach die Anzahl der 01:21:09.500 --> 01:21:09.900 Inversionen. 01:21:13.870 --> 01:21:15.610 Was ist denn eigentlich eine Zufallsvariable? 01:21:16.630 --> 01:21:17.030 Aha. 01:21:18.650 --> 01:21:22.170 Eine Zufallsvariable in dem Fall ist einfach eine Abbildung von der 01:21:22.170 --> 01:21:24.990 Menge der Permutationen in dem Fall. 01:21:25.550 --> 01:21:27.810 Machen wir mal reelle Zahlen, gucken wir mal, wie das rauskommt. 01:21:30.250 --> 01:21:32.070 Und deswegen schreibe ich hier auch ein Sigma hin. 01:21:32.770 --> 01:21:34.730 Und was ich jetzt mache, um das, das weiß ich nicht. 01:21:34.930 --> 01:21:35.790 Das möchte ich berechnen. 01:21:35.910 --> 01:21:38.110 Beziehungsweise den Erwartungswert möchte ich davon berechnen. 01:21:38.530 --> 01:21:44.530 Und was ich mir jetzt dazu definiere, um das als Hilfe zu machen, ist 01:21:44.530 --> 01:21:48.550 so eine Indikator-Zufallsvariable, wie es in der Vorlesung dauernd 01:21:48.550 --> 01:21:51.230 drankommt, die einfach nur die Werte 1 und 0 hat. 01:21:51.310 --> 01:21:54.830 Und die hat jetzt in dem Fall einfach nur den Wert 1, wenn dieses i 01:21:54.830 --> 01:21:57.090 und j eine Inversion ist. 01:22:03.080 --> 01:22:04.160 So, und 0 sonst. 01:22:05.260 --> 01:22:06.040 Warum mache ich das? 01:22:06.080 --> 01:22:06.760 Das ist ganz einfach. 01:22:07.280 --> 01:22:14.160 Mein x Sigma ist dann einfach die Summe der ganzen Werte, wo i kleiner 01:22:14.160 --> 01:22:16.780 als j ist, von diesen Zufallsvariablen. 01:22:23.520 --> 01:22:26.000 Eigentlich müssen wir jetzt nur noch einen Erwartungswert drumherum 01:22:26.000 --> 01:22:26.340 schreiben. 01:22:29.560 --> 01:22:32.620 Nur bringt uns das erstmal nichts, da einfach nur was drumherum zu 01:22:32.620 --> 01:22:35.520 schreiben, sondern wir müssen uns erstmal überlegen, wie können wir 01:22:35.520 --> 01:22:36.880 diesen Wert hier abgreifbar machen. 01:22:40.740 --> 01:22:42.760 Apropos Erwartungswert, was ist eigentlich der Erwartungswert? 01:22:46.850 --> 01:22:52.090 Nun, der Erwartungswert von sowas hier, von der Zufallsvariable, ist 01:22:52.090 --> 01:23:00.210 im Prinzip die Summe aller Objekte, die hier stehen, in dem Fall sind 01:23:00.210 --> 01:23:08.970 es die Permutationen, die Wahrscheinlichkeit dafür mal diesen 01:23:08.970 --> 01:23:11.410 Zufallswert, die Zufallsvariable. 01:23:14.290 --> 01:23:18.970 Wahrscheinlichkeit ist in dem Fall einfach 1 durch n-Fakultät, weil 01:23:18.970 --> 01:23:23.130 jede Permutation ist gleich wahrscheinlich bei meiner Ziehung und 01:23:23.130 --> 01:23:24.970 davon gibt es dann n-Fakultät davon. 01:23:30.840 --> 01:23:34.780 Deswegen kann ich das hier reinziehen. 01:23:36.520 --> 01:23:38.940 Der ist linear, wie man hier sieht. 01:23:40.940 --> 01:23:41.640 Suche i. 01:23:42.660 --> 01:23:49.960 Und jetzt suche ich eigentlich nur noch den Erwartungswert von dieser 01:23:49.960 --> 01:23:52.340 1,0-Variable. 01:23:53.520 --> 01:23:54.800 Und da wird es dann heftig. 01:23:55.360 --> 01:23:57.080 Jetzt muss man einen kleinen Trick anwenden. 01:23:58.200 --> 01:24:02.880 Denn was ist der Erwartungswert dafür, dass zwei Punkte eine Inversion 01:24:02.880 --> 01:24:03.440 sind? 01:24:04.460 --> 01:24:05.400 Jetzt wird es trickreich. 01:24:06.800 --> 01:24:07.780 Gucken wir uns das mal an. 01:24:08.540 --> 01:24:14.600 Wir haben so eine Permutation, die sieht so aus. 01:24:15.820 --> 01:24:16.800 Hier ist i und da ist j. 01:24:19.020 --> 01:24:22.100 Und dann stehen die beiden Buchstaben entweder so rum oder andersrum. 01:24:25.020 --> 01:24:28.780 Und wenn ich mir jetzt irgendeine Permutation rauswähle, dann ist es 01:24:28.780 --> 01:24:31.520 einfach die Wahrscheinlichkeit dafür, dass die so rumstehen oder 01:24:31.520 --> 01:24:32.720 falschrum stehen gleich. 01:24:33.060 --> 01:24:35.860 Weil es gleich viele vom einen Typ wie vom anderen Typ gibt. 01:24:36.980 --> 01:24:41.800 Hier gibt es nochmal die Liste der ganzen Permutationen. 01:24:41.800 --> 01:24:46.240 Und was ich jetzt mal markiert habe oder mich vorbereitet habe, ist 01:24:46.240 --> 01:24:52.900 alle Permutationen von denen, wo an der Stelle 2 eine 5 steht oder an 01:24:52.900 --> 01:24:54.860 der Stelle 3 eine 3 steht oder andersrum. 01:24:56.720 --> 01:24:58.260 Und davon gibt es gleich viele. 01:24:59.440 --> 01:25:03.560 Das heißt, wenn ich mir eine beliebige rauspicke und ein paar 01:25:03.560 --> 01:25:07.020 betrachte, i, j, dann ist die Wahrscheinlichkeit halbe, halbe, dass 01:25:07.020 --> 01:25:08.460 die so rumstehen oder andersrum stehen. 01:25:12.720 --> 01:25:14.940 Und damit setzt man das hier genau ein. 01:25:20.240 --> 01:25:23.380 Das ist genau dieser Erwartungswert, das hier ist ein Halb. 01:25:25.160 --> 01:25:29.580 Und jetzt habe ich hier nur noch dran stehen die Summe von i kleiner j 01:25:29.580 --> 01:25:30.460 ein Halb. 01:25:31.020 --> 01:25:33.300 Wir sollen uns noch überlegen, was mit dem i und dem j hier ist. 01:25:33.380 --> 01:25:38.160 Das ist eigentlich von 1 kleiner gleich i kleiner j kleiner gleich n. 01:25:38.160 --> 01:25:38.980 Ich schreibe nochmal. 01:25:40.380 --> 01:25:45.280 1 kleiner gleich i kleiner j kleiner gleich n ein Halb. 01:25:46.440 --> 01:25:49.860 Das kam mir jetzt schon so häufig vor, dass ich wähle zwei Variablen 01:25:49.860 --> 01:25:50.260 aus. 01:25:52.720 --> 01:25:54.060 Ich habe ein Index. 01:25:55.040 --> 01:25:56.820 Wie viele gibt es davon, die noch größer sind? 01:25:57.860 --> 01:26:02.900 Ich wähle zwei aus, vertausche die so, dass der eine kleiner ist als 01:26:02.900 --> 01:26:03.960 der andere, dann habe ich einen. 01:26:05.440 --> 01:26:07.700 Naja, das ist n mal n minus 1 halbe wie üblich. 01:26:08.280 --> 01:26:11.100 Das ist, ich wähle zwei aus und vertausche die. 01:26:11.940 --> 01:26:14.940 Das ist die Anzahl der Summanden, die hier auftreten. 01:26:15.300 --> 01:26:17.700 Oder anders wieder ausgedrückt, das ist die gleiche Art und Weise wie 01:26:17.700 --> 01:26:18.800 vorher das Selection Sort. 01:26:21.340 --> 01:26:22.080 Mal ein Halb. 01:26:24.720 --> 01:26:28.580 Und das ist n mal n minus 1, n mal n minus 1 Viertel. 01:26:29.600 --> 01:26:35.280 Das ist die erwartete Anzahl von Swaps in meinem Insertion Sort. 01:26:36.660 --> 01:26:46.190 Und für mein n gleich 100 ist es ganz einfach die 4950 durch 2. 01:26:47.310 --> 01:26:48.370 Das ist, was ist das? 01:26:52.190 --> 01:26:52.830 2475. 01:26:54.970 --> 01:26:56.770 Das ist die erwartete Anzahl. 01:26:57.830 --> 01:27:00.150 Dann sage ich euch gleich, das stimmt nicht ganz. 01:27:02.250 --> 01:27:05.550 Jetzt gucken wir noch nach, ob das tatsächlich mein Programm auch 01:27:05.550 --> 01:27:06.030 hergibt. 01:27:07.370 --> 01:27:10.150 Ich sage euch gleich, es stimmt nicht ganz, es fehlt nämlich was? 01:27:11.250 --> 01:27:14.570 Es ist nämlich die erwartete Anzahl der Swaps. 01:27:15.190 --> 01:27:17.350 Es ist aber nicht die erwartete Anzahl der Vergleiche. 01:27:18.190 --> 01:27:22.110 Denn hier muss einer noch auftreten, um die Schleife zu beenden. 01:27:23.370 --> 01:27:26.650 Und diese Schleife wird n mal beendet. 01:27:27.190 --> 01:27:29.290 Weil sonst ist eine Endlosschleife hier irgendwo. 01:27:30.690 --> 01:27:32.510 Aber die kann auch dadurch beendet werden. 01:27:33.730 --> 01:27:34.350 In diesem Fall. 01:27:35.170 --> 01:27:37.810 Das heißt, wir müssen wahrscheinlich die erwartete Anzahl noch 01:27:37.810 --> 01:27:39.650 ungefähr mal 100, aber nicht genau. 01:27:40.290 --> 01:27:41.450 Das ist das Dumme an der Geschichte. 01:27:41.930 --> 01:27:44.490 Jetzt gucken wir uns mal dran an, was das Programm macht. 01:27:45.050 --> 01:27:48.290 Hier ist die Anzahl der Vergleiche. 01:27:50.030 --> 01:27:51.150 Und eine Zufallspermutation. 01:27:55.370 --> 01:27:57.050 2475 ist das, was ich gerne hätte. 01:27:59.570 --> 01:28:00.970 2800, das war viel. 01:28:05.430 --> 01:28:08.630 2475 plus die ungefähr 100, die ich euch gerade noch erklärt habe, 01:28:08.710 --> 01:28:09.050 durch Schleifenaufstieg. 01:28:09.730 --> 01:28:10.690 Das passt ganz gut. 01:28:11.990 --> 01:28:13.770 Wie gesagt, das ist eine Zufallsvariable. 01:28:13.870 --> 01:28:14.650 Jetzt haben wir ein bisschen weniger. 01:28:16.250 --> 01:28:16.870 Ein bisschen mehr. 01:28:18.550 --> 01:28:19.370 Ein bisschen weniger. 01:28:20.870 --> 01:28:22.470 So, jetzt gucken wir uns das nochmal kurz an. 01:28:22.470 --> 01:28:25.410 Hier mein Programm berechnet in der neuen schönen Version die Anzahl 01:28:25.410 --> 01:28:27.910 der Inversionen, die diese Permutation hat. 01:28:29.290 --> 01:28:32.470 Das heißt, wir haben jetzt 2397. 01:28:33.490 --> 01:28:38.950 Ich erwarte 2497 Vergleiche. 01:28:40.210 --> 01:28:41.330 Minus drei. 01:28:42.230 --> 01:28:45.170 Weil diese drei waren Abbruchbedingungen am Anfang. 01:28:47.110 --> 01:28:47.530 Okay. 01:28:49.150 --> 01:28:50.110 Das war's.