WEBVTT 00:10.140 --> 00:12.260 Schönen guten Tag von mir auch. 00:16.240 --> 00:19.120 Peter hat es schon das letzte Mal auch gesagt, also im Vergleich zum 00:19.120 --> 00:21.760 letzten Jahr, die Reihenfolge der Kapitel ist eine andere. 00:24.180 --> 00:28.300 Aber wir permutieren das so, dass keine Abhängigkeiten kaputt gehen. 00:33.760 --> 00:34.960 Und deswegen... 00:34.960 --> 00:38.800 machen wir jetzt erstmal ein Kapitel über randomisierte Algorithmen. 00:39.320 --> 00:42.320 Da haben Sie schon ein bisschen was in Algorithmen 1 auch gesehen. 00:46.240 --> 00:47.120 Und danach... 00:47.120 --> 00:49.720 Randomisierung kommt aber nicht nur in diesem Kapitel. 00:49.920 --> 00:51.160 Sie werden dann sehen, bei... 00:52.900 --> 00:55.800 mindestens bei Approximationsalgorithmen, vielleicht auch bei Online 00:55.800 --> 00:59.540 -Algorithmen, da taucht dann auch Randomisierung wieder auf. 01:00.520 --> 01:03.120 Aber, wie soll ich sagen, steht dann halt nicht so im Vordergrund, ja? 01:06.680 --> 01:07.120 Und... 01:07.820 --> 01:11.340 Jetzt also erstmal Fokus auf Zufall. 01:13.920 --> 01:17.640 Erst nochmal so ein paar einleitende Worte, damit Sie sich vielleicht 01:17.640 --> 01:20.360 nochmal wieder erinnern an einige Dinge, die Sie schon mal gehört 01:20.360 --> 01:20.780 haben. 01:23.000 --> 01:25.380 Und dann ein einfaches Beispiel. 01:26.180 --> 01:28.440 Und dann nehmen wir nochmal randomisierten Quicksort. 01:29.360 --> 01:31.100 Und schauen da so ein bisschen genauer hin. 01:32.060 --> 01:32.540 Und... 01:33.540 --> 01:37.080 Na ja, dann sehen wir mal weiter, wann was kommt. 01:37.960 --> 01:38.180 Gut. 01:38.440 --> 01:40.120 Also was ist ein randomisierter Algorithmus? 01:40.220 --> 01:41.960 Das kann man ein bisschen unterschiedlich sehen. 01:43.340 --> 01:46.240 Das, was Sie sich einfach vorstellen können, ist, Sie dürfen jetzt in 01:46.240 --> 01:48.060 Ihren Algorithmen hinschreiben... 01:48.720 --> 01:53.480 irgendwie so einen Aufruf sozusagen von einer Funktion, randint, da 01:53.480 --> 01:56.180 geben Sie nicht negative ganze Zahlen als Parameter. 01:56.680 --> 01:58.860 Und die liefert Ihnen zufällig gleich verteilt... 02:00.260 --> 02:04.220 eine Zahl zwischen 0 und c-1, wenn Sie mit c aufrufen. 02:04.440 --> 02:07.080 Also randint von 2 liefert Ihnen immer 0 oder 1. 02:08.160 --> 02:10.920 Und zwar mit Wahrscheinlichkeit ein halben Mal dieses, mal jenes. 02:11.260 --> 02:13.940 Und Sie können das aufrufen, so oft Sie wollen. 02:14.140 --> 02:16.940 Sie wissen nie, was das nächste Mal rauskommen wird, sozusagen, im 02:16.940 --> 02:17.540 Idealfall. 02:17.660 --> 02:18.480 Das ist zufällig. 02:20.820 --> 02:24.920 Das ist die Sichtweise, die für uns jetzt hier völlig ausreichend ist. 02:24.920 --> 02:29.700 Man kann sich da auch andere Dinge vorstellen. 02:29.880 --> 02:35.680 Letzten Endes kann man auch immer sagen, ja gut, jede Auswahl... 02:36.420 --> 02:39.140 Stellen wir uns mal vor, es werden nur zufalls Bits tatsächlich 02:39.140 --> 02:40.940 gewürfelt in Ihrem Algorithmus. 02:41.920 --> 02:45.180 Jede Folge von Bits, der Reihe nach, die Sie würfeln, wenn Sie die 02:45.180 --> 02:47.520 festhalten, haben Sie einen deterministischen Algorithmus. 02:48.300 --> 02:51.860 Das heißt, manchmal kann man sich das auch so vorstellen. 02:51.860 --> 02:54.320 Es ist dann auch hilfreich zu sagen, so ein randomisierter 02:54.320 --> 02:58.040 Algorithmus, was man eigentlich macht, ist für die Probleminstanz, die 02:58.040 --> 02:58.300 man hat. 02:58.420 --> 03:02.400 Man würfelt aus einer Menge von Algorithmen, zieht man zufällig einen 03:02.400 --> 03:04.740 heraus, einen deterministischen, und den nimmt man dann halt. 03:05.600 --> 03:07.840 Und das nächste Mal ziehe ich halt wieder zufällig einen 03:07.840 --> 03:09.260 deterministischen Algorithmus. 03:10.460 --> 03:14.020 Aber für uns, stellen Sie sich einfach vor, Sie können in Ihrem 03:14.020 --> 03:18.140 Programm einfach zufällig einen Wert besorgen, der zufällig ist. 03:18.140 --> 03:21.660 Und die Wahrscheinlichkeiten seien harmlos. 03:21.940 --> 03:24.940 Jeder Wert zwischen 0 und 10-1 kommt mit gleicher Wahrscheinlichkeit. 03:26.640 --> 03:28.920 Die Wahrscheinlichkeit ist nicht die Lösung des Halteproblems 03:28.920 --> 03:29.500 reingodiert. 03:32.220 --> 03:37.180 Der Punkt ist aber eben, wenn Sie jetzt den gleichen randomisierten 03:37.180 --> 03:40.940 Algorithmus für die gleiche Eingabe mehrfach ausführen, immer dann, 03:41.040 --> 03:43.680 wenn Sie so eine Zufallsfunktion aufrufen, Sie kriegen 03:43.680 --> 03:44.660 unterschiedliche Werte. 03:45.340 --> 03:47.960 Und wenn das Ganze irgendeinen Sinn haben soll, dann werden Sie ja 03:47.960 --> 03:50.900 wahrscheinlich in Abhängigkeit davon, welcher Wert da gerade kommt, 03:51.020 --> 03:52.040 unterschiedliche Dinge tun. 03:52.940 --> 03:55.300 Das heißt, der gleiche Algorithmus für die gleiche Eingabe mehrfach 03:55.300 --> 03:55.800 ausgeführt. 03:56.500 --> 03:59.200 Es passieren unterschiedliche Programmläufe. 04:00.440 --> 04:02.680 Die können zum Beispiel unterschiedlich lang sein. 04:05.020 --> 04:07.540 Oder womöglich auch unterschiedliche Ergebnisse liefern. 04:07.880 --> 04:12.040 Und das Beispiel, das Sie schon gesehen haben in Algorithmen 1, ist 04:12.040 --> 04:13.220 randomisierter Quicksort. 04:13.760 --> 04:16.920 Also wenn Sie eine Eingabe haben, die ist so eine Liste von N 04:16.920 --> 04:18.300 Elementen. 04:19.740 --> 04:23.580 Wenn die Liste maximal Länge 1 hat, dann müssen Sie gar nichts tun. 04:24.900 --> 04:26.480 Ein Element müssen Sie nicht sortieren. 04:26.560 --> 04:28.780 Und die leere Liste, die können wir ja auch brauchen. 04:29.980 --> 04:31.640 Ist halt auch sortiert per Definition. 04:32.760 --> 04:35.760 Und was macht man ansonsten, wenn die Liste länger ist? 04:35.960 --> 04:41.200 Man würfelt den Index eines Elements und nimmt dieses Element ei als 04:41.200 --> 04:41.920 Pivot -Element. 04:42.800 --> 04:45.080 Und macht dann drei Sublisten. 04:45.380 --> 04:48.180 Die Elemente, die kleiner sind als das Pivot-Element, die, die gleich 04:48.180 --> 04:49.360 sind und die, die größer sind. 04:50.340 --> 04:54.300 Und die, die kleiner sind und die, die größer sind, sortiert man 04:54.300 --> 04:58.160 wieder rekursiv mit dem randomisierten Quicksort-Algorithmus. 04:58.860 --> 05:01.920 Und dann konkretiniert man diese Ergebnisse und dazwischen klebt man 05:01.920 --> 05:04.920 die Liste B mit den Elementen, die alle gleich dem Pivot sind. 05:06.820 --> 05:11.660 Das ist so ein bisschen auch schon in Algorithmen 1 analysiert worden. 05:11.920 --> 05:17.820 Und je nachdem, was Sie auf jeder Rekursionsstufe würfeln, welches 05:17.820 --> 05:20.940 Element Sie als Pivot nehmen, kann das natürlich unterschiedlich lange 05:20.940 --> 05:22.380 dauern, bis das Ding sortiert ist. 05:23.980 --> 05:26.700 Was rauskommt, wird auf jeden Fall immer die richtige sortierte 05:26.700 --> 05:27.600 Reihenfolge sein. 05:28.260 --> 05:31.080 Aber es kann eben offensichtlich unterschiedlich lange dauern. 05:32.700 --> 05:37.400 Und das heißt sozusagen, also gegeben der randomisierte Algorithmus 05:37.400 --> 05:41.200 und eine feste Eingabe, so was wie die Laufzeit, ist eine 05:41.200 --> 05:42.040 Zufallsvariable. 05:42.900 --> 05:44.980 Wer weiß noch, was eine Zufallsvariable ist? 05:46.500 --> 05:47.120 Ja, ja. 05:48.780 --> 05:52.800 Deswegen machen wir kurz zwei Folien, ein bisschen Erinnerung an 05:52.800 --> 05:53.920 Wahrscheinlichkeitstheorie. 05:54.580 --> 05:55.760 Das ist ja alles nicht schwierig. 05:58.280 --> 06:05.040 Also erstens, wir haben immer so eine Sigma-Algebra und da haben wir 06:05.040 --> 06:06.860 eine Menge von Elementarereignissen. 06:07.680 --> 06:10.120 Und ein Standardbeispiel ist immer Würfeln. 06:11.020 --> 06:13.840 Und das andere Standardbeispiel bei uns ist jetzt halt immer den 06:13.840 --> 06:17.500 randomisierten Algorithmus für eine Eingabe immer wieder ausprobieren. 06:18.380 --> 06:23.020 Und die Elementarereignisse sind dann halt, die eine oder andere Seite 06:23.020 --> 06:27.420 beim Würfeln liegt oben oder die eine oder andere Folge von Zuständen 06:27.420 --> 06:28.920 wird von dem Programm durchlaufen. 06:30.200 --> 06:32.740 Und dann möchte man gerne über Ereignisse reden. 06:32.900 --> 06:35.260 Das sind halt Mengen von Elementarereignissen. 06:36.480 --> 06:41.480 Also diese Menge E von Ereignissen, das ist eine Menge von Teilmengen 06:41.480 --> 06:44.440 von Omega, also eine Teilmenge von der Potenzmenge von Omega. 06:44.620 --> 06:46.320 2 hoch Omega soll die Potenzmenge sein. 06:47.620 --> 06:50.420 Also Ereignisse sind Mengen von Elementarereignissen. 06:50.560 --> 06:54.200 Das könnte sowas sein wie, ich habe eine gerade Zahl gewürfelt. 06:58.440 --> 07:02.400 Und der Spezialfall, der für uns weitgehend ausreichend ist, wir 07:02.400 --> 07:06.320 werden das nicht groß vertiefen, ist der Fall, dass tatsächlich jede 07:06.320 --> 07:07.940 Teilmenge ein Ereignis ist. 07:08.120 --> 07:10.760 Und dann muss man an einigen Stellen nicht länger nachdenken, ob alles 07:10.760 --> 07:11.980 in Ordnung ist und gut geht. 07:11.980 --> 07:14.640 Und sowas heißt dann eine diskrete Sigma-Algebra. 07:15.600 --> 07:17.480 Also jede Teilmenge ist ein Ereignis. 07:17.740 --> 07:18.340 Alles ist gut. 07:18.960 --> 07:23.460 Und dann gibt es halt immer ein Wahrscheinlichkeitsmaß, das einem für 07:23.460 --> 07:28.200 jedes Ereignis, also für jede Menge von Elementarereignissen, eine 07:28.200 --> 07:29.160 Wahrscheinlichkeit sagt. 07:29.260 --> 07:31.060 Das ist also eine Zahl zwischen 0 und 1. 07:31.580 --> 07:34.960 Und so ein Wahrscheinlichkeitsmaß muss gewisse Eigenschaften haben. 07:35.520 --> 07:37.860 Die habe ich mir jetzt gespart, die da alle aufzuschreiben. 07:37.980 --> 07:39.920 Dann muss das halt eine Sigma-Algebra sein. 07:40.520 --> 07:46.000 Die Wahrscheinlichkeit dafür, dass für das Ereignis, dass irgendetwas 07:46.000 --> 07:46.860 überhaupt passiert. 07:47.580 --> 07:51.280 Also die Menge Omega aller Elementarereignisse, das muss halt 1 sein. 07:51.740 --> 07:53.240 Irgendwas passiert auf jeden Fall. 07:54.460 --> 07:57.860 Und Sie möchten, dass die Wahrscheinlichkeit von der Vereinigung von 07:57.860 --> 08:00.760 zwei disjunkten Ereignissen einfach die Summe der Wahrscheinlichkeiten 08:00.760 --> 08:01.040 ist. 08:01.240 --> 08:03.460 Und das vielleicht auch für unendliche Vereinigungen und sowas. 08:04.080 --> 08:06.160 So und dann gibt es Zufallsvariablen. 08:06.280 --> 08:10.020 Und eine Zufallsvariable ist eine ganz normale, deterministische 08:10.020 --> 08:14.960 Funktion, Abbildung, die Ihnen für jedes Elementarereignis einen 08:14.960 --> 08:16.040 Funktionswert liefert. 08:17.360 --> 08:19.860 Und der Zufall, der steckt nicht in dieser Abbildung, das ist eine 08:19.860 --> 08:23.220 ganz harmlose Abbildung, sondern der Zufall kommt daher, dass man halt 08:23.220 --> 08:27.440 nicht weiß, was rauskommt, weil man erst das zufällige Argument da 08:27.440 --> 08:28.100 reinstecken muss. 08:28.240 --> 08:30.940 Das ist halt irgendwie Zufall und je nachdem, was man reinsteckt, 08:31.060 --> 08:32.580 kommen halt verschiedene Funktionswerte raus. 08:34.060 --> 08:39.060 Und so eine Zufallsvariable, wenn Sie Mathematik betreiben, muss auch 08:39.060 --> 08:40.600 gewisse schöne Eigenschaften haben. 08:40.740 --> 08:44.400 Und wenn die Sigma Algebra diskret ist, also jede Teilmenge ist 08:44.400 --> 08:46.360 Ereignis, dann muss man da nicht viel nachdenken. 08:47.540 --> 08:50.280 Und man schreibt dann sowas wie Wahrscheinlichkeit dafür, dass eine 08:50.280 --> 08:53.180 Zufallsvariable Groß X einen Wert kleiner gleich X hat. 08:53.300 --> 08:55.740 Also die Funktionswerte stellen wir uns vor, sind einfach irgendwelche 08:55.740 --> 08:56.160 Zahlen. 08:56.820 --> 08:59.140 Sowas wie Laufzeit oder so. 09:00.580 --> 09:04.760 Und das steht dann also, also Wahrscheinlichkeit von Groß X kleiner 09:04.760 --> 09:08.100 gleich klein X steht dann also genau genommen für die 09:08.100 --> 09:13.040 Wahrscheinlichkeit des Ereignisses, aller Elementarereignisse, für die 09:13.040 --> 09:16.700 halt der Funktionswert der Zufallsvariable kleiner gleich X ist. 09:19.300 --> 09:21.580 Und genauso für gleich statt kleiner gleich. 09:22.020 --> 09:25.020 Und also hier muss man halt aufpassen, dass das wirklich immer schöne 09:25.020 --> 09:27.800 Ereignisse sind und so, aber das brauchen wir nicht groß angucken. 09:28.320 --> 09:31.880 Und beim Würfeln, also meinetwegen... 09:35.940 --> 09:37.760 Elementarereignisse sind halt die Zahlen 1 bis 6. 09:38.240 --> 09:41.120 Und dann gibt es vielleicht, ist zum Beispiel ein Ereignis die Menge 09:41.120 --> 09:44.180 2, 4, 6, das wäre das Ereignis, man würfelt eine gerade Zahl. 09:47.000 --> 09:50.220 Und das Wahrscheinlichkeitsmaß, das man normalerweise nimmt, ist, 09:50.300 --> 09:53.100 naja, jede Zahl kommt mit gleicher Wahrscheinlichkeit ein Sechstel. 09:56.080 --> 10:00.960 Als ich mal Kind war und wir im Urlaub viel gespielt haben, habe ich 10:00.960 --> 10:03.320 mich irgendwann gewundert, dass die Würfel, mit denen wir rumhantiert 10:03.320 --> 10:04.060 haben, immer... 10:04.060 --> 10:06.060 Ich hatte das Gefühl, da kommen zu viele Sechsen, da habe ich mal 10:06.060 --> 10:06.980 Strichlisten geführt. 10:07.540 --> 10:09.580 Und siehe da, es war nicht die Wahrscheinlichkeit. 10:10.620 --> 10:13.680 Also höchstwahrscheinlich war das kein fairer Würfel. 10:13.800 --> 10:15.860 Kann ja zufällig alles so passieren, ja. 10:15.860 --> 10:17.460 Aber gut. 10:18.760 --> 10:21.460 Und die Wahrscheinlichkeit für das Ereignis, eine gerade Zahl zu 10:21.460 --> 10:23.020 würfeln, das ist halt ein Halb. 10:24.120 --> 10:28.460 Im Allgemeinen, in diesem harmlosen Fall, die Wahrscheinlichkeit für 10:28.460 --> 10:32.280 ein Ereignis ist halt einfach die Größe geteilt durch 6. 10:32.440 --> 10:34.600 Also Anzahl Elemente mal ein Sechstel. 10:35.940 --> 10:41.320 Und dann können Sie Zufallsvariablen für Ihre Würfelsachen definieren. 10:41.930 --> 10:45.540 Zum Beispiel, die Zufallsvariable ist immer 0 oder 1 und meinetwegen 10:45.540 --> 10:50.200 sie ist 0, wenn das Elementareignis, also die Zahl, die Sie gewürfelt 10:50.200 --> 10:53.540 haben, das Produkt von zwei Primzahlen ist und 1, wenn das nicht der 10:53.540 --> 10:58.320 Fall ist, ist irgendeine Abbildung von den Zahlen 1 bis 6 nach reelle 10:58.320 --> 10:58.780 Zahlen. 11:00.140 --> 11:04.180 Und die Wahrscheinlichkeit, dass diese Zufallsvariable den Wert 1 hat, 11:07.420 --> 11:11.260 da müssen Sie gucken, für wie viele Elementarereignisse, also für 11:11.260 --> 11:14.580 welche Zahl, die man würfeln kann, ist es so, dass da 1 rauskommt, 11:15.140 --> 11:17.840 also dass das nicht Produkt zweier Primfaktoren ist. 11:18.620 --> 11:21.680 Und das ist bei 1, 2, 3 und 5 so. 11:22.520 --> 11:26.300 Also in 4 von 6 Fällen ist die Wahrscheinlichkeit 2 Drittel. 11:26.780 --> 11:27.140 So. 11:29.720 --> 11:33.080 Und solche Gebilde, die tauchen dann aber schon auf, die ganze Zeit. 11:33.180 --> 11:39.000 So, Wahrscheinlichkeit, dass irgendeine Zufallsvariable irgendeinen 11:39.000 --> 11:40.360 Wert hat, ist so und so groß. 11:43.760 --> 11:47.360 Und was man dann halt bei Zufallsvariablen häufig anguckt, ist zum 11:47.360 --> 11:48.780 Beispiel sowas wie Erwartungswert. 11:50.700 --> 11:53.540 Da multiplizieren Sie halt die möglichen Werte, die tatsächlich 11:53.540 --> 11:56.600 rauskommen können, mit der Wahrscheinlichkeit dafür, dass dieser Wert 11:56.600 --> 11:58.220 passiert bei der Zufallsvariable. 11:59.540 --> 12:03.740 Im Allgemeinen muss sowas nicht existieren, aber in den Fällen, die 12:03.740 --> 12:04.940 wir uns angucken, ist das so. 12:08.400 --> 12:11.900 Und immer gilt, also wenn Sie zwei Zufallsvariablen haben, da kommen 12:11.900 --> 12:14.060 immer reelle Zahlen raus, können Sie natürlich immer addieren. 12:14.620 --> 12:17.420 Und es ist immer so, dass der Erwartungswert der Summe zweier 12:17.420 --> 12:21.360 Zufallsvariablen die Summe der Erwartungswerte ist, bei der Summe. 12:21.680 --> 12:23.960 Beim Produkt ist das im Allgemeinen nicht so. 12:24.820 --> 12:28.040 Da brauchen Sie die zusätzliche Eigenschaft, dass die Zufallsvariablen 12:28.040 --> 12:29.140 unabhängig sind. 12:29.840 --> 12:32.980 Und zwei Zufallsvariablen heißen unabhängig, wenn die 12:32.980 --> 12:35.980 Wahrscheinlichkeit dafür, dass gleichzeitig die Variable x einen Wert 12:35.980 --> 12:41.560 x abnimmt und die Variable y einen Wert y, gleich ist dem Produkt 12:41.560 --> 12:45.140 dafür, dass x den Wert x annimmt, mal der Wahrscheinlichkeit, dass y 12:45.140 --> 12:46.760 den Wert y annimmt. 12:48.660 --> 12:54.360 Und wenn zwei Zufallsvariablen unabhängig sind, dann ist auch der 12:54.360 --> 12:57.180 Erwartungswert vom Produkt gleich dem Produkt der Erwartungswerte. 12:58.400 --> 13:00.760 Das erwähne ich, weil wir es halt auch brauchen werden. 13:00.760 --> 13:05.080 Und dann gibt es eine Sorte Zufallsvariablen, die kaufen ganz oft auf, 13:05.220 --> 13:08.140 die liefern immer nur den Funktionswert 0 oder 1. 13:08.640 --> 13:09.880 Etwas anderes kommt da gar nicht vor. 13:11.140 --> 13:14.180 Da ist dann zum Beispiel der Erwartungswert ganz einfach auszurechnen. 13:14.400 --> 13:18.960 0 mal der Wahrscheinlichkeit, dass 0 rauskommt, ist einfach 0, plus 1 13:18.960 --> 13:21.020 mal Wahrscheinlichkeit, dass 1 rauskommt. 13:21.540 --> 13:23.940 Also der Erwartungswert ist dann einfach die Wahrscheinlichkeit dafür, 13:24.060 --> 13:24.940 dass das Ding 1 wird. 13:28.010 --> 13:29.180 Nochmal kurz zu Unabhängigkeiten. 13:29.910 --> 13:33.180 Beim Würfeln nehmen wir zwei 0,1 Zufallsvariablen. 13:33.970 --> 13:37.450 Die eine soll 1 sein, wenn die gewürfelte Zahl eine Primzahl ist. 13:37.570 --> 13:40.350 Die andere soll 1 sein, wenn die Zahl gerade ist. 13:41.770 --> 13:43.850 Primzahlen gibt es da 3, 2, 3 und 5. 13:43.970 --> 13:48.550 Das heißt, die Wahrscheinlichkeit, dass diese Variable x 1 wird, ist 13:48.550 --> 13:49.210 gerade 1,5. 13:50.370 --> 13:52.830 Und die Wahrscheinlichkeit, dass man eine gerade Zahl würfelt, ist 13:52.830 --> 13:53.410 auch 1,5. 13:54.080 --> 13:59.450 Und das Produkt von beidem, also Wahrscheinlichkeit x gleich 1 mal 13:59.450 --> 14:01.470 Wahrscheinlichkeit y gleich 1, ist dann ein Viertel. 14:03.050 --> 14:06.690 Aber wenn Sie sich angucken, das ist die Wahrscheinlichkeit, dass bei 14:06.690 --> 14:12.350 einem Elementarereignis gleichzeitig x den Wert 1 hat und auch y den 14:12.350 --> 14:13.070 Wert 1 hat. 14:13.850 --> 14:16.870 Das muss also eine Zahl sein, die sowohl gerade als auch prim zahlt. 14:16.990 --> 14:17.990 Da gibt es nur die 2. 14:18.810 --> 14:20.010 Es gibt nur eine Möglichkeit. 14:20.730 --> 14:22.290 Das heißt, die Wahrscheinlichkeit ist ein Sechstel. 14:22.290 --> 14:25.630 Das heißt, diese beiden Zufallsvariablen sind nicht unabhängig 14:25.630 --> 14:26.130 voneinander. 14:27.530 --> 14:29.630 Anschaulich, Hände wedelnd. 14:30.330 --> 14:33.090 Wenn man eine Primzahl würfelt, dann ist das eben, salopp gesprochen, 14:33.270 --> 14:34.590 meistens keine gerade Zahl. 14:41.050 --> 14:45.690 Und bei randomisierten Algorithmen stellen sich vor, diese 14:45.690 --> 14:50.450 Elementarereignisse, das sind die Läufe für eine konkrete Eingabe, die 14:50.450 --> 14:54.430 Möglichkeiten, welche Folge von globalen Speicherzuständen kann ich 14:54.430 --> 14:55.050 dann beobachten. 14:56.690 --> 15:00.150 Und dann können Sie da alle möglichen Zufallsvariablen angucken. 15:00.370 --> 15:03.290 Zum Beispiel, wie viele Schritte sind es denn, bis das Ergebnis da 15:03.290 --> 15:03.510 ist. 15:04.990 --> 15:06.290 Das kann variieren. 15:06.570 --> 15:08.130 Beim Quicksort gucken wir es gleich nochmal an. 15:09.250 --> 15:13.050 Und es kann aber auch sein, dass tatsächlich das Ergebnis variiert. 15:14.210 --> 15:16.730 Sie stecken immer die gleiche Eingabe rein, es kommen unterschiedliche 15:16.730 --> 15:17.490 Ergebnisse raus. 15:20.010 --> 15:22.990 Oder der Speicherplatzbedarf variiert oder was auch immer. 15:25.490 --> 15:27.830 Und dann kann man sich natürlich erst mal fragen, will man das 15:27.830 --> 15:28.190 überhaupt? 15:29.110 --> 15:30.730 Und warum will man das vielleicht? 15:31.470 --> 15:34.370 Also zum Beispiel Algorithmen, wo man salopp gesagt nicht weiß, wie 15:34.370 --> 15:35.130 lange er dauert. 15:38.570 --> 15:41.990 Na ja, ist die Frage, ob man nicht vielleicht doch eben so ein 15:41.990 --> 15:43.210 bisschen was sagen kann. 15:44.490 --> 15:47.870 Also bei randomisierten Quicksorten, man sieht zumindest in einem 15:47.870 --> 15:51.850 schlimmsten Fall, ist das halt der schlimmste Fall, der passieren 15:51.850 --> 15:52.050 kann. 15:52.130 --> 15:54.030 Das sind halt N-Quadrat-Vergleiche. 15:56.130 --> 15:58.470 Also der Erwartungswert kann dann auch nicht schlimmer sein. 16:01.350 --> 16:04.030 Vielleicht der Erwartungswert, ich kann mal über den was sagen. 16:05.330 --> 16:08.350 Also kann man, auch wenn man es nicht genau weiß, konkret, wenn das 16:08.350 --> 16:11.110 eine Zufallsvariable ist, kann man halt irgendwas quantifizieren. 16:11.310 --> 16:13.590 Zum Beispiel einfach den Erwartungswert ausrechnen. 16:14.290 --> 16:17.550 Oder noch schärfere Aussagen machen über die Laufzeit. 16:17.630 --> 16:19.330 Nicht nur der Erwartungswert ist so und so viel. 16:24.090 --> 16:25.770 Die Ausgabe kann auch variieren. 16:29.110 --> 16:32.670 Bei Optimierungsproblemen ist man vielleicht am ehesten geneigt zu 16:32.670 --> 16:36.330 sagen, ja okay, ich möchte halt ein möglichst gutes Ergebnis. 16:37.150 --> 16:39.070 Da kommt nicht immer das Optimum raus. 16:39.790 --> 16:42.550 Ich kriege sowieso immer nur Näherungen, weil das Problem so schwierig 16:42.550 --> 16:42.790 ist. 16:42.850 --> 16:45.010 Aufs Optimum bin ich gar nicht scharf. 16:46.170 --> 16:48.950 Wenn das dann mal ein bisschen besser, mal ein bisschen schlechter 16:48.950 --> 16:51.550 ist, macht mir nichts aus. 16:51.650 --> 16:56.370 Hauptsache, ich kann beweisen, in der überwiegenden Zahl der Fälle 16:56.370 --> 17:01.690 oder womöglich immer, das was rauskommt, ist bis auf einen Faktor so 17:01.690 --> 17:03.410 und so nah am Optimum dran. 17:03.970 --> 17:04.910 Könnte ja sein. 17:07.030 --> 17:10.250 Und zwar vielleicht bei gleichzeitig nicht allzu schlimmer Laufzeit. 17:11.230 --> 17:12.630 Oder erwarteter Laufzeit. 17:14.590 --> 17:18.350 Ein anderes Beispiel, wo man vielleicht tatsächlich will, dass 17:18.350 --> 17:24.650 unterschiedliche Dinge rauskommen, ist, wenn Sie sich eben sozusagen 17:24.650 --> 17:28.010 in Anführungszeichen zufällig irgendwelche Objekte erzeugen wollen. 17:28.310 --> 17:31.450 Ich meine Würfeln, so eine Zahl von 1 bis 6, das ist harmlos. 17:32.710 --> 17:34.910 Aber was machen Sie denn, wenn Sie sich... 17:35.870 --> 17:38.650 Also denken Sie ja an Algorithm Engineering. 17:39.270 --> 17:42.390 Sie wollen Ihren Algorithmus ausprobieren. 17:42.670 --> 17:45.710 Der braucht irgendwelche Grafen, macht der irgendwas? 17:45.710 --> 17:49.810 Da wollen Sie jetzt vielleicht auch mal irgendwelche zufälligen Grafen 17:49.810 --> 17:50.470 reinstecken. 17:51.530 --> 17:53.630 Woher kriegen Sie denn einen zufälligen Grafen? 17:54.530 --> 17:57.610 Irgendwie erzeugen vielleicht mit einem randomisierten Algorithmus. 18:00.190 --> 18:03.410 Die einfachen Fälle sind einfach, kompliziertere sind komplizierter. 18:04.630 --> 18:07.590 Also vielleicht wollen Sie nicht irgendwelche Grafen, sondern Grafen 18:07.590 --> 18:09.730 mit gewissen zusätzlichen Eigenschaften. 18:10.090 --> 18:11.490 Wie auch immer die aussehen mögen. 18:11.490 --> 18:16.390 Die Verteilung der Knotengrade ist so und so und so und so. 18:17.690 --> 18:20.670 Dann ist das vielleicht gar nicht so einfach, solche Grafen zu 18:20.670 --> 18:22.830 erzeugen, solche zufälligen Objekte. 18:22.950 --> 18:26.610 Aber dafür ist es dann halt tatsächlich auch hilfreich. 18:27.750 --> 18:31.310 Man erzeugt sich Probleminstanzen, für die man dann irgendeinen 18:31.310 --> 18:32.850 anderen Algorithmus ausprobiert. 18:35.470 --> 18:40.390 Aber es gibt auch tatsächlich den Fall sozusagen, es ist kein 18:40.390 --> 18:44.810 Optimierungsproblem oder irgendwas, es ist völlig klar, das Problem, 18:44.890 --> 18:47.670 das ich lösen will, ist so, wenn ich diese Eingabe habe, die richtige 18:47.670 --> 18:48.990 Antwort ist 1. 18:50.410 --> 18:54.770 Und der randomisierte Algorithmus ist aber so, manchmal sagt er für 18:54.770 --> 18:58.130 die gleiche Eingabe schon 1, aber manchmal halt auch 0. 19:00.210 --> 19:01.990 Ist die Frage, will man damit leben? 19:05.930 --> 19:07.510 Naja, steht da ja schon. 19:07.510 --> 19:12.290 Sie sitzen hier alle ganz ruhig, keiner will weglaufen. 19:13.290 --> 19:16.330 Könnte ja sein, dass hier ein Meteorit einschlägt oder vielleicht 19:16.330 --> 19:20.190 schon eingeschlagen hätte im Laufe der letzten knapp anderthalb 19:20.190 --> 19:20.570 Stunden. 19:21.330 --> 19:22.890 Das scheint Sie nicht so zu stören. 19:23.490 --> 19:25.070 Die Gefahr besteht. 19:28.850 --> 19:32.150 Kann man versuchen so abzuschätzen, die ist vielleicht so bei 2 hoch 19:32.150 --> 19:35.570 minus 100 oder 2 hoch minus 95 oder ich weiß nicht, 19:40.310 --> 19:45.510 es gibt ein Programm, das ist einer der ganz alten randomisierten 19:45.510 --> 19:50.710 Algorithmen, da stecken Sie die obere Schranke rein, da können Sie 19:50.710 --> 19:54.110 sagen, hier 2 hoch 400 ist die obere Schranke und was ich wissen will, 19:54.530 --> 19:56.950 ist die größte Primzahl kleiner gleich dieser Zahl. 19:57.630 --> 20:00.630 Und da läuft das Programm ein paar Sekunden und sagt dann 2 hoch 400 20:00.630 --> 20:04.730 minus 593, das ist die größte Primzahl kleiner gleich 2 hoch 400. 20:06.670 --> 20:07.150 Problem? 20:07.890 --> 20:10.130 Ja, man weiß nicht genau, ob die Antwort richtig ist. 20:11.370 --> 20:14.590 Es gibt da so eine allerdings eben sehr kleine Wahrscheinlichkeit, 20:14.670 --> 20:17.230 dass die Antwort des Programms falsch ist und die ist so bei 2 hoch 20:17.230 --> 20:17.950 minus 100. 20:19.410 --> 20:22.070 Jetzt können Sie sich wieder fragen, glauben Sie, dass das die größte 20:22.070 --> 20:23.590 Primzahl ist oder glauben Sie es nicht? 20:27.850 --> 20:30.070 Vielleicht kommt es ja manchmal auch auf die Anwendung an. 20:30.910 --> 20:35.270 Also wenn Sie eine Ampelsteuerung haben, wie fühlen Sie sich, wenn das 20:35.270 --> 20:38.270 ein randomisierter Algorithmus macht, der mit Wahrscheinlichkeit 2 20:38.270 --> 20:42.090 hoch minus 100 auf einmal für alle Richtungen gleichzeitig grün macht? 20:43.310 --> 20:46.030 Würden Sie das tun oder würden Sie es nicht tun? 20:48.830 --> 20:50.390 Können Sie mal darüber nachdenken. 20:53.190 --> 20:57.210 Also der Punkt ist, es kommt vielleicht manchmal die falsche Antwort, 20:57.350 --> 20:59.930 aber wenn die Fehlerwahrscheinlichkeit klein ist, dann ist das ja 20:59.930 --> 21:00.670 vielleicht auch okay. 21:04.550 --> 21:05.110 Gut. 21:09.470 --> 21:11.390 Nehmen wir mal an, man kann damit leben. 21:12.730 --> 21:14.390 Warum macht man es dann trotzdem? 21:15.290 --> 21:18.590 Also tatsächlich, manchmal ist es vielleicht einfach schöner, 21:18.750 --> 21:21.110 hinzuschreiben, also so ein randomisierter QuickSort-Algorithmus 21:21.110 --> 21:24.410 vielleicht wirklich leicht hinzuschreiben und hat schöne 21:24.410 --> 21:27.210 Eigenschaften, wie wir irgendwann noch mal ein bisschen nachrechnen 21:27.210 --> 21:27.490 wollen. 21:30.210 --> 21:35.610 Manchmal ist man mit randomisierten Algorithmen besser oder schneller 21:35.610 --> 21:37.670 als deterministisch. 21:38.930 --> 21:41.610 Oder sagen wir mal, jedenfalls schneller als alles, was man so an 21:41.610 --> 21:43.330 deterministischen Algorithmen kennt. 21:46.390 --> 21:49.830 Es gibt auch Fälle, ganz offensichtlich, da können Sie deterministisch 21:49.830 --> 21:51.670 gar nichts erreichen. 21:51.790 --> 21:53.630 Da müssen Sie Zufall einsetzen. 21:55.470 --> 22:04.190 Aber das eine ist, man zahlt einen Preis, das funktioniert ganz 22:04.190 --> 22:07.430 schnell, ganz toll, aber nur mit einer gewissen Wahrscheinlichkeit. 22:08.110 --> 22:11.850 Oder es ist ganz schnell, aber es ist der Erwartungswert. 22:13.430 --> 22:16.350 Und was man dann halt macht, das müssen Sie sich auch immer klar 22:16.350 --> 22:16.610 machen. 22:17.230 --> 22:20.710 Man vergleicht dann vielleicht den Erwartungswert des randomisierten 22:20.710 --> 22:24.290 Algorithmus und der Erwartungswert ist ganz schön und vergleicht es 22:24.290 --> 22:27.610 mit deterministischen Algorithmen und da typischerweise mit dem Worst 22:27.610 --> 22:28.130 Case. 22:29.190 --> 22:32.050 Das ist natürlich auch so ein bisschen ein Vergleich von Äpfel mit 22:32.050 --> 22:37.170 Birnen und vielleicht auch nicht der Weisheit allerletzter Schluss. 22:38.670 --> 22:47.950 Also jedenfalls, es gibt vielleicht Vorteile, aber meistens gibt man 22:47.950 --> 22:52.050 halt auch ein großes oder vielleicht auch relativ kleines Risiko ein, 22:52.170 --> 22:54.330 das, was nicht so schön läuft, wie man es gerne hätte. 22:55.070 --> 22:57.670 Aber wenn die Wahrscheinlichkeit klein ist, prima. 23:06.900 --> 23:10.540 Damit ich hier nicht die ganze Zeit die gleichen zwei Wörter sage, die 23:10.540 --> 23:13.480 ich dann im nächsten Abschnitt auch gleich wieder sage, gucken wir uns 23:13.480 --> 23:18.840 erst mal einen anderen randomisierten Algorithmus an, um auch schon 23:18.840 --> 23:21.340 nochmal so ein paar prinzipielle Dinge zu sehen. 23:23.500 --> 23:26.420 Nämlich tatsächlich einen Algorithmus, der manchmal die gleiche 23:26.420 --> 23:35.160 Antwort liefert und die Motivation ist jetzt nicht so toll, aber sie 23:35.160 --> 23:37.900 sei erwähnt, vielleicht reicht es Ihnen ja. 23:38.900 --> 23:42.400 Stellen Sie sich vor, Sie haben zwei Listen und Sie wollen 23:42.400 --> 23:46.840 herausfinden, also sie seien gleich lang und Sie wollen herausfinden, 23:47.080 --> 23:49.920 ob in beiden Listen die gleichen Werte drinstehen. 23:50.400 --> 23:52.200 Vielleicht in unterschiedlicher Reihenfolge. 23:54.140 --> 23:54.860 Also sozusagen... 23:55.620 --> 23:58.100 Sie haben jemanden, der sagt, ja hier, ich habe einen tollen 23:58.100 --> 24:02.260 Sortieralgorithmus und wenn Sie da die Liste E1 bis EN reinstecken, da 24:02.260 --> 24:04.040 kommt A1 bis AN raus. 24:05.320 --> 24:08.380 Und damit das ein Sortieralgorithmus ist, die Werte, die rauskommen, 24:08.480 --> 24:10.340 sollten die sein, die auch in der Eingabe standen. 24:10.660 --> 24:12.740 Die sollten nicht nur sortiert sein, es sollten auch immer noch die 24:12.740 --> 24:13.600 gleichen Werte sein. 24:22.200 --> 24:24.680 Und schauen, ist es bei E1 bis EN dabei? 24:26.020 --> 24:28.780 Und vielleicht der Einfachheit halber stellen wir uns immer vor, die 24:28.780 --> 24:32.640 Werte sind alle paarweise verschieden, damit wir nicht so viel noch 24:32.640 --> 24:33.840 zusätzlich argumentieren müssen. 24:34.700 --> 24:36.420 Da haben Sie natürlich quadratische Laufzeit. 24:37.700 --> 24:40.760 Da gibt es natürlich Schlaueres, um das deterministisch schneller zu 24:40.760 --> 24:40.960 machen. 24:41.160 --> 24:43.660 Also Sie könnten einen Sortieralgorithmus, der wirklich funktioniert, 24:43.780 --> 24:46.640 nehmen, beide Listen sortieren und dann schauen, es ist einfach die 24:46.640 --> 24:47.180 gleiche Liste, 24:52.200 --> 24:53.780 dann würden wir das mal randomisiert. 24:54.120 --> 24:58.000 Sie haben zwei Listen, E1 bis EN, A1 bis AN. 24:58.740 --> 25:01.500 Und wir gehen mal davon aus, die Elemente stammen aus einem Körper. 25:02.280 --> 25:06.680 Also Sie können multiplizieren, dividieren, alles was man so braucht. 25:09.180 --> 25:12.460 Und wir wollen herausfinden, enthalten die die gleichen Werte 25:12.460 --> 25:14.100 vielleicht mit unterschiedlicher Reihenfolge. 25:16.360 --> 25:16.560 So. 25:18.440 --> 25:19.520 Was machen wir? 25:23.380 --> 25:25.260 Im ersten Schritt beachten wir das, was der Versuch angeht. 25:25.260 --> 25:28.040 Und dann machen wir des zu. 25:28.140 --> 25:35.380 wenn wir verschiedene Reihenfolge haben, dann versuchen wir, die 25:35.380 --> 25:43.520 Verteile am Ende zu identifizieren, weil wir dann nicht die gleiche 25:43.520 --> 25:44.280 Menge drin haben. 25:44.340 --> 25:48.020 Die Reihenfolgen haben wir unbedingt miteinander. 25:48.020 --> 25:50.000 Natürlich können wir dann auch offensichtlich verschiedene Reihenfolge 25:50.000 --> 25:55.160 haben, Hier ist es dann, wie Sie gleich sehen werden, offensichtlich 25:55.160 --> 25:57.500 manchmal falsch, diese Schlussfolgerung. 25:58.300 --> 26:01.180 Ich kenne übrigens auch, also so viel ich weiß, es gibt keine 26:01.800 --> 26:03.720 systematische wissenschaftliche Arbeit, die belegt, dass 26:03.720 --> 26:08.420 Fingerabdrücke von Menschen tatsächlich so zuverlässig, einzigartig 26:08.420 --> 26:09.580 sind, wie man immer tut. 26:10.780 --> 26:11.020 Aber gut. 26:12.120 --> 26:14.320 Also Fingerabdrücke, was tut man? 26:15.660 --> 26:19.300 Also Sie haben die Liste der Werte e i, die Liste der Werte a i. 26:19.420 --> 26:22.120 Da können Sie locker die zwei Polynome hinschreiben. 26:22.240 --> 26:23.620 e von z und a von z. 26:24.040 --> 26:27.920 Einfach das Produkt der z-minus-e i, beziehungsweise das Produkt der z 26:27.920 --> 26:28.740 -minus -a i. 26:34.520 --> 26:39.400 Wenn die e i und die a i die gleichen Werte sind, dann die Differenz 26:39.400 --> 26:41.840 von diesen beiden Polynomen ist einfach das Nullpolynom. 26:43.300 --> 26:44.400 Einfach konstant Null. 26:46.500 --> 26:50.780 Wenn es einen Wert gibt, der in der einen Liste ist, aber nicht in der 26:50.780 --> 26:57.020 anderen, und dann umgekehrt natürlich auch, dann ist das nicht das 26:57.020 --> 26:57.700 Nullpolynom. 26:58.760 --> 27:02.120 Denn wenn Sie dann einen Wert nehmen, der nur bei den e's vorkommt, 27:02.180 --> 27:06.660 wenn Sie den bei den a's einsetzen, die Differenzen, dieses besondere 27:06.660 --> 27:09.080 e, das ist keinem a i gleich. 27:09.180 --> 27:10.880 Die Differenzen sind alle ungleich Null. 27:11.160 --> 27:12.760 Und das Produkt ist dann auch ungleich Null. 27:12.980 --> 27:14.660 Also das kann nicht das Nullpolynom sein. 27:16.820 --> 27:20.640 Das heißt, die Frage, die wir eigentlich haben, dann ist die Differenz 27:20.640 --> 27:23.300 von diesen beiden Polynomen, ist das das Nullpolynom oder nicht? 27:26.020 --> 27:30.020 Jetzt machen Sie mal einen Vorschlag für einen simplen, randomisierten 27:30.020 --> 27:33.280 Algorithmus, um herauszufinden, ob das Polynom das Nullpolynom ist. 27:35.620 --> 27:36.720 Ganz plump. 27:37.620 --> 27:39.320 Das ist das Einfachste, was Ihnen einfällt, ja? 27:41.680 --> 27:43.540 Ja, viel zu kompliziert. 27:44.100 --> 27:45.940 Nicht ganz viele Werte einsetzen. 27:46.420 --> 27:47.640 Einen Wert einsetzen. 27:48.960 --> 27:52.920 Also, großartiger Algorithmus, zufällig. 27:53.020 --> 27:57.800 Wir nehmen einfach irgendein Element aus unserem Körper und setzen das 27:57.800 --> 27:58.160 ein. 27:59.020 --> 28:00.480 Da kommt irgendwas raus. 28:01.480 --> 28:03.300 Also der Wert, den wir einsetzen, nennen wir den mal c. 28:03.420 --> 28:06.020 Der Wert, der rauskommt, ist dann halt e von c minus a von c, nennen 28:06.020 --> 28:06.420 wir den y. 28:07.560 --> 28:12.920 Und wenn da Null rauskommt, wenn das also auf gut Deutsch eine 28:12.920 --> 28:17.080 Nullstelle dieses Polynoms war, dann sagen Sie, ach, bestimmt, die 28:17.080 --> 28:19.160 ganze Liste e ist gleich der ganzen Liste a. 28:20.420 --> 28:23.040 Und wenn da nicht Null rauskommt, sagen Sie, nee, die sind verschieden 28:23.040 --> 28:23.420 voneinander. 28:25.320 --> 28:25.480 So. 28:30.020 --> 28:30.460 Jetzt. 28:34.060 --> 28:37.020 Es gibt jetzt, da muss man immer ein bisschen aufpassen, zwei Arten 28:37.020 --> 28:40.680 das anzugucken und da klappt was um und passen Sie auf, dass Sie das 28:40.680 --> 28:41.540 immer nicht durcheinander bringen. 28:42.340 --> 28:45.440 Einerseits können wir davon ausgehen, also wenn die beiden Listen 28:45.440 --> 28:50.460 gleich sind, also wenn das wirklich das Nullpolynom ist, was wird der 28:50.460 --> 28:51.320 Algorithmus machen? 28:51.540 --> 28:54.080 Naja, da können Sie einsetzen, was Sie wollen, da wird natürlich immer 28:54.080 --> 28:54.820 Null rauskommen. 28:56.380 --> 28:58.760 Und dann würde er sagen, ja, die beiden Listen sind gleich und die 28:58.760 --> 28:59.780 Antwort stimmt. 29:00.580 --> 29:03.140 Also wenn die beiden Listen gleich sind, die Antwort, die Sie kriegen, 29:03.240 --> 29:03.880 ist die richtige. 29:04.840 --> 29:06.220 Ja, die Listen sind gleich. 29:07.680 --> 29:10.420 Allerdings diese Antwort, ja, die Listen sind gleich, die kann auch 29:10.420 --> 29:12.920 falsch sein, weil die manchmal auch rauskommt, wenn die Polynome nicht 29:12.920 --> 29:13.480 gleich sind. 29:14.960 --> 29:19.160 Aber wenn Sie sich die Ergebnisse angucken, die Antwort, die Polynome 29:19.160 --> 29:24.200 sind verschieden, ja, die Listen sind verschieden, die Antwort stimmt 29:24.200 --> 29:29.160 auf jeden Fall, denn die kommt nur, wenn offensichtlich da nicht Null 29:29.160 --> 29:29.980 rausgekommen ist. 29:30.420 --> 29:34.400 Also die richtige Antwort kommt auf jeden Fall, wenn E gleich A ist 29:34.400 --> 29:38.040 und die Antwort, die immer richtig ist, ist, die beiden sind 29:38.040 --> 29:38.620 verschieden. 29:40.200 --> 29:42.000 Aber es gibt eben den Fehlerfall. 29:43.680 --> 29:48.220 Man erwischt zu, also E von Z minus A von Z ist nicht das Nullpolynom, 29:48.460 --> 29:51.720 aber man erwischt hier zufällig eine Nullstelle des Polynoms und 29:51.720 --> 29:55.040 denkt, oh, Y ist Null, wir behaupten mal. 29:57.760 --> 30:01.900 So, das ist der Fehlerfall und das ist auch der einzige Fehlerfall. 30:02.820 --> 30:05.360 Wie groß ist die Wahrscheinlichkeit für den Fehlerfall? 30:07.780 --> 30:12.620 Naja, wir ziehen zufällig gleichverteilt ein Element aus dem Körper, 30:12.760 --> 30:15.520 da gibt es halt so viele Möglichkeiten, wie der Körper Elemente 30:15.520 --> 30:15.900 enthält. 30:18.180 --> 30:19.660 Und was muss passieren? 30:19.720 --> 30:23.780 Wir müssen zufällig eine Nullstelle dieses Polynoms erwischen, dass da 30:23.780 --> 30:26.360 Null rauskommt, obwohl das gar nicht das Nullpolynom ist. 30:28.180 --> 30:31.860 Diese beiden Polynome haben Grad N, die Differenz auch. 30:32.280 --> 30:34.380 Auch ein Polynom hat höchstens Grad N. 30:41.700 --> 30:46.460 Ein Fehlerwahrscheinlichkeit, das ist, naja, man muss zufällig eine 30:46.460 --> 30:50.760 von kleinen Nullstellen erwischt haben, wenn man in den großen Sack 30:50.760 --> 30:53.860 mit Anzahl Körper Elemente reingreift. 30:55.280 --> 30:55.920 Punkt. 30:56.920 --> 31:00.280 Und wenn Sie jetzt es sich leisten können, als Körper etwas zu nehmen 31:00.280 --> 31:05.140 mit vielen Elementen, also viele im Vergleich zum Grad des Polynoms, 31:06.100 --> 31:06.840 dann haben Sie ja gewonnen. 31:06.980 --> 31:11.280 Da steht halt dann irgendwie ein halb oder zwei hoch minus 100 oder je 31:11.280 --> 31:13.260 nachdem, wo Sie halt rechnen, was Sie halt tun. 31:17.460 --> 31:17.940 Fertig. 31:21.670 --> 31:27.010 Also es gibt hier solche Algorithmen, da kommt tatsächlich eine binäre 31:27.010 --> 31:28.390 Antwort raus, ja oder nein. 31:29.230 --> 31:33.250 Und in diesem Beispiel, die eine Antwort ist immer richtig, die beiden 31:33.250 --> 31:35.790 sind verschieden, diese Antwort stimmt immer, nur die andere Antwort 31:35.790 --> 31:36.810 kann verkehrt sein. 31:37.370 --> 31:40.730 Da spricht man auch von der Möglichkeit eines einseitigen Fehlers. 31:41.110 --> 31:45.750 Es gibt auch so Algorithmen, können beide Antworten mit kleiner 31:45.750 --> 31:46.870 Wahrscheinlichkeit falsch sein. 31:48.290 --> 31:50.870 Und die Fehlerwahrscheinlichkeit kann man irgendwie abschätzen. 31:51.890 --> 31:55.470 Und wenn der Körper groß ist, ist die Fehlerwahrscheinlichkeit aber 31:55.470 --> 31:55.970 klein. 31:56.210 --> 31:58.750 Und es gibt dann auch noch Möglichkeiten, die Fehlerwahrscheinlichkeit 31:58.750 --> 31:59.470 kleiner zu machen. 31:59.590 --> 32:02.050 Das haben Sie schon angedeutet eben. 32:02.850 --> 32:05.830 Probiert man halt nicht einen Wert aus, sondern mehrere, dann ist das 32:05.830 --> 32:06.650 wahrscheinlich besser. 32:08.870 --> 32:11.370 Das werden Sie dann in der Übung so ein bisschen nachrechnen. 32:13.030 --> 32:17.970 Das ist jetzt relativ plump, aber um Ihnen so als Ausblick zu zeigen, 32:18.090 --> 32:22.270 warum diese Idee auch noch so ein bisschen weiterhilft, stellen Sie 32:22.270 --> 32:27.150 sich vor, vergessen Sie jetzt diese Motivation mit den Listen und man 32:27.150 --> 32:28.330 will vergleichen, ob die gleich sind. 32:28.410 --> 32:32.090 Stellen Sie sich vor, Sie haben einfach zwei Polynome und wollen 32:32.090 --> 32:33.950 herausfinden, ob die gleich sind. 32:34.290 --> 32:36.510 Und das sind aber Polynome in mehreren veränderlichen. 32:39.270 --> 32:43.730 Und da gibt es tatsächlich Anwendungen, da wäre es schön, wenn man das 32:43.730 --> 32:45.570 schnell herausfinden könnte. 32:47.890 --> 32:49.790 Zumindest mit großer Wahrscheinlichkeit. 32:51.350 --> 32:55.430 Und da kann man so eine Idee, wie eben, tatsächlich wieder machen, 32:55.850 --> 33:01.070 irgendwie zufällig Werte einsetzen und gucken, habe ich dann 33:01.070 --> 33:02.530 Nullstelle erwischt oder nicht. 33:04.650 --> 33:12.530 Und wenn Sie jetzt sich vorstellen, diese Polynome, also das muss 33:12.530 --> 33:14.810 jetzt irgendwie in mehreren veränderlichen, das muss nicht alles 33:14.810 --> 33:17.050 vollständig ausmultipliziert sein, da können also irgendwie so 33:17.050 --> 33:23.250 Produkte von einzelnen Gebilden stehen, also vielleicht so Summen von 33:23.250 --> 33:25.070 zwei Variablen. 33:26.630 --> 33:30.270 Und da könnte zum Beispiel sowas stehen, wie für ein Polynom Z1 plus 33:30.270 --> 33:37.030 Z2 mal Z2 plus Z3 mal Z3 plus Z4 bis Zn minus 1 plus Zn. 33:37.570 --> 33:42.070 Da haben Sie also N Summen und in jeder Summe stehen zwei Summanden. 33:42.170 --> 33:45.590 Das ist also eine Eingabe, die hat eine Länge proportional zu N. 33:48.780 --> 33:51.040 Und Q ist vielleicht auch irgendwie sowas von der Bauart. 33:52.000 --> 33:54.680 Und jetzt können Sie sagen, naja, Gleichheit von Polynomen ist doch 33:54.680 --> 33:55.140 ganz einfach. 33:55.220 --> 33:57.300 Ich multipliziere alles aus und vergleiche die beiden. 33:58.180 --> 34:00.980 Aber wenn Sie jetzt gerade sowas hier ausmultiplizieren, dann stellen 34:00.980 --> 34:04.440 Sie fest, das gibt exponentiell viele Summanden. 34:05.040 --> 34:07.500 Das wollen Sie nicht alles ausmultiplizieren. 34:08.580 --> 34:09.860 Das dauert viel zu lange. 34:11.960 --> 34:16.520 Und tatsächlich, man kennt keinen deterministischen 34:16.520 --> 34:19.240 Polynomialzeitalgorithmus, um das herauszufinden. 34:20.600 --> 34:25.300 Aber randomisiert mit gewisser Fehlerwahrscheinlichkeit, indem Sie so 34:25.300 --> 34:32.500 eine Idee so ähnlich wie eben machen, kriegen Sie eben oft die 34:32.500 --> 34:34.340 richtige Antwort und Sie können die Fehlerwahrscheinlichkeit 34:34.340 --> 34:35.700 systematisch noch kleiner machen. 34:36.320 --> 34:40.100 Also solche Ideen helfen schon manchmal so ein bisschen weiter noch. 34:41.400 --> 34:41.720 Gut. 34:43.060 --> 34:46.500 Das war jetzt erstmal noch so ein erstes, einfaches Beispiel. 34:52.760 --> 34:56.720 Also wir merken Sie sich eben manchmal, man spricht so über 34:56.720 --> 34:58.480 einseitigen und zweiseitigen Fehler. 35:00.120 --> 35:04.180 Es interessiert plausiblerweise, wie groß ist die Wahrscheinlichkeit, 35:04.240 --> 35:08.700 eine falsche Antwort zu bekommen, wenn denn klar ist, was die richtige 35:08.700 --> 35:10.760 Antwort ist und was falsche Antworten sind. 35:13.480 --> 35:16.400 Und hier haben wir jetzt aber gerade ansonsten noch nicht groß mit 35:16.400 --> 35:18.780 Erwartungswerten oder so rumhantiert. 35:18.920 --> 35:24.180 Das machen wir jetzt beim nächsten Blick auf randomisierten Quicksort. 35:24.180 --> 35:25.520 Ja. 35:30.740 --> 35:35.300 Das ist nochmal der Code von vorhin und den habe ich im Wesentlichen 35:35.300 --> 35:36.740 aus Algorithmen 1 abgeschrieben. 35:36.920 --> 35:38.120 Also das ist das Standardding. 35:38.840 --> 35:47.840 Und was Sie damals im ersten, im zweiten Semester gesehen haben, ist 35:47.840 --> 35:49.200 eine Abschätzung. 35:50.200 --> 35:53.420 Was ist denn der Erwartungswert für die Anzahl Vergleiche? 35:53.560 --> 35:57.700 Der Erwartungswert für die Anzahl Vergleiche, die passieren, wenn man 35:57.700 --> 36:00.880 diesen Algorithmus für eine Eingabe der Länge n durchführt. 36:03.440 --> 36:05.560 Das kann halt gut und schlecht laufen. 36:05.720 --> 36:08.900 Auf jeder Rekursionsstufe, jedes Mal, wenn Sie hier zufällig Ihr Pivot 36:08.900 --> 36:12.520 -Element wählen, wenn Sie Pech haben, erwischen Sie zum Beispiel im 36:12.520 --> 36:15.280 Extremfall immer das kleinste oder das größte Element. 36:15.880 --> 36:19.960 Und bei der Partitionierung immer eine Liste ist leer und die andere 36:19.960 --> 36:21.760 enthält nur ein Element weniger. 36:22.440 --> 36:25.720 Und dann haben Sie n minus 1 plus n minus 2 plus n minus 3 plus plus 36:25.720 --> 36:27.140 plus plus plus 2 Vergleiche. 36:27.220 --> 36:28.960 Das sind quadratisch viele Vergleiche. 36:29.560 --> 36:32.940 Es gibt auch die Chance natürlich immer zufällig den Median zu 36:32.940 --> 36:38.760 erwischen und dann jedes Mal beide Listen A und C haben genau nur noch 36:38.760 --> 36:41.100 n minus 1 halbe Elemente. 36:41.200 --> 36:45.280 Und das ist der ganz schöne Fall und dann offensichtlich, also mit 36:45.280 --> 36:50.000 Master -Theorem oder so, sieht man, dass man größenordnungsmäßig n log 36:50.000 --> 36:51.200 n Vergleiche nur hat. 36:54.300 --> 36:56.760 Und wenn man ein bisschen länger drüber nachdenkt oder sich das ein 36:56.760 --> 36:59.740 bisschen nochmal die Analyse anguckt, stellt man fest, es muss nicht 36:59.740 --> 37:03.360 genau der Median sein, damit da sowas wie n log n rauskommt. 37:03.840 --> 37:07.200 Es reicht, wenn Sie immer ein Pivot-Element erwischen, das salopp 37:07.200 --> 37:08.720 gesprochen so irgendwo in der Mitte ist. 37:09.640 --> 37:13.620 Also sagen wir mal in der mittleren Hälfte, nicht im kleinsten Viertel 37:13.620 --> 37:14.980 und nicht im größten Viertel. 37:15.400 --> 37:18.460 Wenn Sie in dem Bereich immer ein Pivot-Element erwischen, dann haben 37:18.460 --> 37:21.240 Sie auch größenordnungsmäßig nur n log n Vergleiche. 37:23.680 --> 37:29.640 So und um das abzuschätzen, das ist fast alles, was man braucht. 37:31.260 --> 37:35.480 Man guckt zum, also jetzt Anzahl Vergleiche abzuschätzen. 37:35.860 --> 37:41.560 Man definiert einen Haufen solcher 0,1 Zufallsvariablen und sagt jetzt 37:41.560 --> 37:49.120 zum Beispiel, okay, also für alle Kombinationen von i und j, für alle 37:49.120 --> 37:53.280 Kombinationen, Werte, Positionen i und j, zum Beispiel in der 37:53.280 --> 37:58.560 Ergebnisliste, die Zufallsvariable xij ist 1, wenn die Elemente, die 37:58.560 --> 38:05.590 am Ende an den Positionen i und j landen, im Verlauf der Ausführung 38:05.590 --> 38:06.970 miteinander verglichen wurden. 38:11.670 --> 38:14.730 So und wenn Sie dann wissen wollen, wie viele Vergleiche sind es 38:14.730 --> 38:19.490 insgesamt, dann müssen Sie die xij einfach alle aufaddieren, über alle 38:19.490 --> 38:24.210 Paare i, j und dann halt jedes Paar nur einmal aufaddieren, also obda 38:24.210 --> 38:25.130 immer i kleiner j. 38:26.470 --> 38:30.570 Und der Erwartungswert davon, das ist die erwartete Anzahl Vergleiche. 38:32.290 --> 38:35.330 Und der Erwartungswert von der Summe ist immer gleich Summe der 38:35.330 --> 38:36.210 Erwartungswerte. 38:36.570 --> 38:37.470 Sie erinnern sich, Dunkel. 38:38.090 --> 38:42.650 Und für so eine 0,1 Zufallsvariable, der Erwartungswert von so einer 38:42.650 --> 38:45.050 Zufallsvariable ist einfach die Wahrscheinlichkeit, dass die Variable 38:45.050 --> 38:46.090 den Wert 1 annimmt. 38:47.050 --> 38:51.290 Und das heißt, Sie müssen sich in Anführungszeichen nur überlegen, für 38:51.290 --> 38:56.570 jedes Paar i, j von Positionen in der Ergebnisliste, was ist die 38:56.570 --> 38:59.290 Wahrscheinlichkeit, dass diese beiden Elemente irgendwann miteinander 38:59.290 --> 38:59.970 verglichen wurden. 39:02.950 --> 39:06.930 Und das Einzige, was man sich dann überlegen muss, ist, was sind die 39:07.370 --> 39:07.770 Wahrscheinlichkeiten. 39:07.930 --> 39:10.410 Und das Erste, was man merkt, ist, die sind nicht alle gleich. 39:11.550 --> 39:13.450 Extremfall, stellen Sie sich vor, in der Ergebnisliste das 39:13.450 --> 39:16.450 allerkleinste und das allergrößte Element, 1 und n. 39:16.950 --> 39:19.830 Was ist die Wahrscheinlichkeit, dass die beiden Elemente irgendwann 39:19.830 --> 39:21.790 mal miteinander verglichen wurden? 39:23.950 --> 39:28.690 Naja, das allererste Mal als ein Pivot-Element ausgewählt wurde. 39:29.770 --> 39:33.470 Wenn Sie da eins wählen, was nicht das kleinste und nicht das größte 39:33.470 --> 39:36.770 ist, dann landet das kleinste in der einen Teilliste, das größte in 39:36.770 --> 39:39.610 der anderen Teilliste und die werden nie miteinander verglichen. 39:40.790 --> 39:41.130 Null. 39:44.070 --> 39:47.010 Die beiden werden nur miteinander verglichen, wenn Sie genau das 39:47.010 --> 39:50.210 kleinste oder genau das größte zufällig als Pivot-Element nehmen. 39:50.310 --> 39:52.390 Das wird dann nämlich garantiert mit dem anderen verglichen. 39:52.870 --> 39:56.390 Das heißt, von den n Elementen, die Sie ganz am Anfang zur Auswahl 39:56.390 --> 40:00.530 haben, um ein Pivot-Element zu wählen, nur zwei Möglichkeiten sind so, 40:01.190 --> 40:04.070 dass das größte und das kleinste Element miteinander verglichen 40:04.070 --> 40:04.290 werden. 40:05.290 --> 40:12.330 Also zwei durch n, wenn i und i gleich eins ist und j gleich n. 40:12.810 --> 40:17.930 Und allgemein können Sie sich überlegen, naja, es ist immer so in dem 40:17.930 --> 40:22.950 Bereich, zwei durch Länge dieses Intervalls von i bis j, das ist die 40:22.950 --> 40:25.590 Wahrscheinlichkeit, dass die beiden miteinander verglichen werden. 40:26.610 --> 40:31.290 Und dann müssen Sie das noch aufsummieren Also, 40:35.470 --> 40:40.270 das einfach zur Erinnerung nochmal, das war aus Berechnung 40:40.270 --> 40:43.150 erwartungswert, Anzahlvergleiche und Anzahlvergleich ist im 40:43.150 --> 40:44.150 Wesentlichen die Laufzeit. 40:44.270 --> 40:47.730 Die Frage war jetzt noch, wozu zufällig wählen? 40:49.030 --> 40:51.910 Ich weiß ja sowieso nicht, was da in der Eingabe wo steht. 40:52.010 --> 40:54.330 Wenn ich einfach immer das erste nehme, ist das sozusagen auch immer 40:54.330 --> 40:55.050 ein zufälliges. 40:57.010 --> 41:01.790 Ja, aber, also wenn Sie sich zum Beispiel entscheiden, deterministisch 41:01.790 --> 41:06.250 immer das erste Element als pivot zu nehmen, dann gibt es halt 41:06.250 --> 41:12.090 Eingaben, da werden Sie garantiert Laufzeit n² haben. 41:18.450 --> 41:22.830 Wenn Sie jedesmal zufällig eins herauswählen, können Sie natürlich... 41:22.830 --> 41:25.990 Achso, und es gibt bei dieser Wahl, ich nehme immer das erste, gibt es 41:25.990 --> 41:28.530 andere Eingaben, da werden Sie Laufzeit nlogn haben. 41:31.970 --> 41:35.890 Wenn Sie das so machen, immer zufällig ein Pivot-Element rausnehmen, 41:36.570 --> 41:40.450 dann haben Sie einerseits den Nachteil, für jede Eingabe, es kann 41:40.450 --> 41:45.470 Ihnen Laufzeit n² passieren, aber auch für jede Eingabe, es kann Ihnen 41:45.470 --> 41:46.530 nlogn passieren. 41:48.230 --> 41:53.690 Und der Erwartungswert ist nlogn, also für jede Eingabe jetzt, für 41:53.690 --> 41:59.370 jede, der Erwartungswert, nur der Erwartungswert, aber immerhin der 41:59.370 --> 42:02.330 erst mal, ist nlogn und nicht n². 42:03.010 --> 42:05.730 Egal, ob das sortiert ist oder nicht oder sonst irgendwie. 42:06.850 --> 42:11.410 Also, so böse Wichte, Widersacher, die dann vielleicht versuchen 42:11.410 --> 42:15.150 könnten, gemeine Eingaben zu präparieren für den Sortieralgorithmus, 42:15.190 --> 42:18.350 damit er schlecht aussieht, die haben halt schwierig, weil sie nicht 42:18.350 --> 42:21.770 wissen, was werden wir tun, was wird das Pivot-Element sein. 42:23.790 --> 42:25.550 Also, bis hierher erstmal. 42:27.070 --> 42:30.630 Schönen Dank und dann sehen wir uns wieder nächste Woche Montag.