WEBVTT 00:10.450 --> 00:11.470 So, schönen Tag. 00:11.610 --> 00:14.990 Ich begrüße Sie zur Vorlesung effizienter Algorithmen. 00:15.970 --> 00:20.070 Ich hoffe die Qualität hier in der Tonalwand ist ausreichend, dass ihr 00:20.070 --> 00:20.510 das sehen könnt. 00:20.530 --> 00:22.610 Wir müssen eventuell die ein bisschen verdunkeln. 00:22.710 --> 00:23.910 Das sollte ich vielleicht mal kurz machen. 00:25.530 --> 00:30.450 Das reicht wahrscheinlich, wenn ich hier das runter mache. 00:40.140 --> 00:41.140 Das reicht schon. 00:41.560 --> 00:42.140 Ich brauche nichts mehr. 00:45.650 --> 00:46.990 So, ich denke das genug. 00:49.350 --> 00:53.130 Also, wir sind im Kapitel Algebraische Probleme. 00:54.070 --> 00:55.310 Letzte Woche war ich ja nicht da. 00:55.630 --> 01:01.050 Ich habe bei einem interessanten Seminar im Dachstuhl gesessen und 01:01.050 --> 01:02.770 mitgewirkt über Organic Computing. 01:03.670 --> 01:05.450 Interessante Algorithmen, aber nicht so richtig. 01:05.610 --> 01:07.990 Da geht es nicht um Effizienz, sondern um andere Themen, die man mit 01:07.990 --> 01:11.830 überraschenden Situationen zurechtkommt und Systeme darauf 01:11.830 --> 01:12.430 vorbereitet. 01:13.130 --> 01:15.630 Hier geht es um effiziente Algorithmen. 01:15.850 --> 01:17.090 Probleme wollen wir uns angucken. 01:17.210 --> 01:18.810 Wir haben Marktesmultiplikation angeschaut. 01:18.990 --> 01:21.330 Das hatte ich noch gemacht, mal davor. 01:21.990 --> 01:28.290 Da ging es um im Prinzip die Datenstrukturen für zunächst mal und dann 01:28.290 --> 01:29.630 die Algorithmen. 01:30.170 --> 01:31.390 Schulmethode kannten wir schon. 01:31.510 --> 01:33.790 Wir hatten gesehen, welchen Aufwand wir treiben müssen. 01:33.950 --> 01:39.590 Wir hatten dann gesehen, wie man die Berechnungen manipulieren kann in 01:39.590 --> 01:41.990 einer etwas unerwarteten Art und Weise. 01:42.630 --> 01:46.430 Einfach unsere Fantasie anzuregen, was man machen kann, wenn man sich 01:46.430 --> 01:47.530 mit Berechnungen beschäftigt. 01:47.570 --> 01:49.270 Wenn man versuchen will, etwas zu verbessern. 01:49.270 --> 01:52.330 Wir hatten gesehen, dass man in der Lage ist, zumindest einen 01:52.330 --> 01:59.210 konstanten Faktor einzusparen, sofern der Zeitaufwand für 01:59.210 --> 02:01.910 Multiplikation höher ist als der für Addition. 02:02.350 --> 02:05.910 Dann hatten wir uns das Verfahren von Strassen angeschaut, wo ein 02:05.910 --> 02:10.530 Divide -and-Conquer-Ansatz systematisch verfolgt wurde, bei dem die 02:10.530 --> 02:19.010 Multiplikation von Matrizen in dem man ein Verfahren für zunächst mal 02:19.010 --> 02:23.230 allgemein k-Kreuz-k-Matrizen genommen hat, als Muster für die 02:23.230 --> 02:28.150 Ausführung von Matrix-Multiplikationen und jede Multiplikation der 02:28.150 --> 02:35.070 dann auftauchenden n-durch-k-Kreuz-n-durch-k-Matrizen dann halt 02:35.070 --> 02:38.090 rekursiv wieder nach der gleichen Art und Weise gemacht hat. 02:38.350 --> 02:43.170 Daraus ergab sich dann erstaunlicherweise ein Verfahren, das diese 02:43.170 --> 02:49.430 Komplexität hat, hier steht es an diesem Satz, Groß O von n hoch log 02:49.430 --> 02:53.970 zur Basis k von klein m von k und klein m von k ist die Anzahl der 02:53.970 --> 02:57.610 Multiplikationen, was schon erstaunlich ist, dass allein die Anzahl 02:57.610 --> 03:01.210 der Multiplikationen die Komplexität des gesamten Verfahrens bestimmt. 03:02.150 --> 03:07.810 Und da Herr Strassen dann dieses Verfahren für 2-Kreuz-2-Matrizen 03:07.810 --> 03:11.730 entwickelt hatte mit sieben Multiplikationen, also eine Multiplikation 03:11.730 --> 03:16.810 eingespart bei 2-Kreuz-2-Matrizen, führt zu einem asymptotischen 03:16.810 --> 03:22.010 Zeitgewinn, der die asymptotische Zeit von n hoch 3 runterdrückt auf n 03:22.010 --> 03:23.130 hoch 2.81. 03:24.030 --> 03:29.150 Das war damals eine Revolution in den Annahmen über die Optimalität 03:29.150 --> 03:34.870 von Algorithmen, insbesondere weil dann Strassen eben auch noch 03:34.870 --> 03:37.890 gezeigt hat, dass der Rechenaufwand, also die Anzahl der 03:37.890 --> 03:42.250 arithmetischen Operationen für die Matrixmultiplikation genauso groß 03:42.250 --> 03:46.410 ist, beziehungsweise in der gleichen Komplexitätsklasse wie der 03:46.410 --> 03:50.790 Aufwand für die Inversion und damit der Aufwand, um Gleichheitssysteme 03:50.790 --> 03:54.630 zu lösen, auch in der Größenordnung wie Matrixmultiplikation, was die 03:54.630 --> 03:59.050 Anzahl der arithmetischen Operationen angeht und deswegen eben die 03:59.050 --> 04:02.130 klare Aussage, die gaussische Elimination ist nicht optimal. 04:02.290 --> 04:05.210 Und das war in der Numerik davor bei den Mathematikern die klassische 04:05.210 --> 04:07.690 Annahme, selbstverständlich ist das optimal, wie kann man das besser 04:07.690 --> 04:08.390 hinkriegen. 04:08.990 --> 04:11.770 Und von dem Augenblick an wurde auf einmal das Gebiet effizienter 04:11.770 --> 04:12.830 Algorithmen ernst genommen. 04:13.270 --> 04:15.970 Davor war das eigentlich, naja, die fummeln da so ein bisschen mit 04:15.970 --> 04:19.310 Algorithmen rum und machen etwas ein bisschen besser, was bringt das 04:19.310 --> 04:19.530 schon. 04:19.530 --> 04:22.910 Ja, das ist eines der Matrixmultiplikationen. 04:23.150 --> 04:26.750 Alleine ist das noch nicht so spannend, aber es bestimmt halt eine 04:26.750 --> 04:31.370 ganze Klasse von Problemen, die im Kern liegen von numerischen 04:31.370 --> 04:31.910 Verfahren. 04:32.410 --> 04:34.910 Und deswegen hat das so eine starke Auswirkung gehabt. 04:35.310 --> 04:38.250 Da haben sich viele Leute mit beschäftigt und eben es geschafft, bis 04:38.250 --> 04:42.190 auf 2.37 runterzukommen, aber nicht mit diesem Ansatz, mit anderen 04:42.190 --> 04:45.330 Ansätzen, nur die hätten sich alle nicht damit beschäftigt, wenn nicht 04:45.330 --> 04:47.350 dieser Durchbruch von Straßen gekommen wäre. 04:47.350 --> 04:50.210 Dann ging es weiter, das hat letztes Mal Herr Schubler Ihnen 04:50.210 --> 04:50.730 vorgestellt. 04:51.510 --> 04:55.110 Parallelisierung, das ist das Thema, was ich dazu bringe jetzt in 04:55.110 --> 04:59.510 dieser Vorlesung, dass man sich anguckt, wie kann ich eigentlich durch 04:59.510 --> 05:01.190 Parallelrechner, z.B. 05:01.330 --> 05:03.110 auf einem Multicore-Rechner oder Minicore-Rechner, 05:03.470 --> 05:05.910 Matrixmultiplikationen vernünftig machen, z.B. 05:06.070 --> 05:08.830 so wie das hier, aber da sieht man natürlich nicht viel, da sieht man, 05:09.030 --> 05:13.170 weil die Animation hier praktisch mit drinsteckt, sieht man nur, dass 05:13.170 --> 05:16.270 wir hier so ein zweidimensionales Feld haben, durch das die Daten dann 05:16.270 --> 05:19.870 so von links nach rechts und von oben nach unten durchgeschoben werden 05:19.870 --> 05:24.630 und dann entsteht halt in den einzelnen Zellen jeweils ein 05:24.630 --> 05:28.850 Skalarprodukt, sodass am Ende der Berechnung dann in den einzelnen 05:28.850 --> 05:33.550 Zellen die Werte der Matrix C drinstehen, die man dann natürlich nur 05:33.550 --> 05:38.270 ausgeben kann und eben eine Verbesserung um den Faktor n². 05:39.210 --> 05:42.430 Das heißt, wir kommen von n hoch 3 auf n runter. 05:43.130 --> 05:47.910 Nicht optimal, was das optimale sequentielle Verfahren angeht. 05:48.270 --> 05:52.030 Wenn wir aber zugestehen, dass die Größenordnung der Matrizen, die wir 05:52.030 --> 05:55.830 hier haben, in dem Bereich liegt, in dem das Verfahren von Strassen 05:55.830 --> 06:03.730 und auch die anderen, wo die Verfahren deutlich langsamer sind als die 06:03.730 --> 06:10.090 Schuhmethode, können wir schon sagen, in dem Bereich der Problemgrößen 06:10.090 --> 06:12.890 ist das hier ein optimaler Zeitgewinn. 06:13.270 --> 06:16.450 Und dann das andere Beispiel war das von Kramer und von Löwen, hier 06:16.450 --> 06:21.490 diese etwas andere Anordnung, wo die drei Matrizen wandern, nämlich 06:21.490 --> 06:25.590 die Matrizen A von oben nach unten, B von unten nach oben und C hier 06:25.590 --> 06:28.110 von links nach rechts dadurch wandern und das war hier durch eine 06:28.110 --> 06:31.370 Folge von Folien animiert, deswegen etwas einfacher, hier nochmal kurz 06:31.370 --> 06:39.150 durchzuspielen, die Art, wie hier die Berechnungen durchläuft. 06:39.770 --> 06:43.550 Und was man hier eben auch sieht, ist, dass wir einerseits eine Zeit 06:43.550 --> 06:47.370 haben von 4n-2, das ist genau die Anzahl der Takte vom Beginn bis zum 06:47.370 --> 06:48.190 Ende der Berechnung. 06:48.990 --> 06:55.190 Wir haben deswegen Speedup Größe n² mit n²-Prozessoren, ist also 06:55.190 --> 06:59.850 asymptotisch optimal, Wiederausgehen von n³ als der Ausgangsbasis, 07:00.010 --> 07:01.510 Effizienz ist in Omega von 1. 07:01.630 --> 07:05.730 Was man dazu sagen kann, ist ähnlich wie das, was ich Ihnen bei dem 07:05.730 --> 07:10.790 ersten Beispiel mit diesem anderen systolischen Verfahren mit dem 07:10.790 --> 07:14.630 hexagonalen Feld schon gesagt habe, man kann auch hier zwei 07:14.630 --> 07:17.470 Berechnungen ineinander verschränken und kann im Prinzip zwei 07:17.470 --> 07:21.430 Berechnungen nebenläufig nacheinander ausführen, also mit einem Takt 07:21.430 --> 07:22.030 Abstand. 07:22.310 --> 07:25.970 Und dann hat man nicht nur jeden zweiten Prozessor ausgenutzt, was man 07:25.970 --> 07:29.210 hier sieht in diesen Animationen, dass dort jeweils die Hälfte der 07:29.210 --> 07:30.390 Prozessoren gerade nichts tut. 07:30.750 --> 07:33.310 Wenn man eine zweite Berechnung dazwischen schiebt, ist jeder 07:33.310 --> 07:35.790 Prozessor, jedes Element ausgenutzt und ich habe praktisch 07:35.790 --> 07:39.910 gleichzeitig mit einem Takt Versatz zwei Matrix-Modifikationen 07:39.910 --> 07:40.970 ausgeführt. 07:41.050 --> 07:46.610 Also das ist ein sehr effizientes Verfahren und kann also so 07:46.610 --> 07:50.630 eingesetzt werden in hochparallelen Systemen, wobei man natürlich 07:50.630 --> 07:55.650 aufpassen muss, dass hier der Aufwand, um jetzt zu kommunizieren, 07:55.730 --> 07:57.390 nicht zu groß sein darf, da habe ich auch schon mal darauf 07:57.390 --> 08:00.990 hingewiesen, das geht nur in solchen sehr engen, massiv parallelen 08:00.990 --> 08:05.150 Systemen, eng verbundenen, oder man muss eben die Größe der einzelnen 08:05.150 --> 08:08.490 Elemente, die modifiziert werden, einfach deutlich erhöhen, indem man 08:08.490 --> 08:13.110 da halt Teilmatrizen jeweils weitergibt, das sind dann halt nicht die 08:13.110 --> 08:16.850 einzelnen Skala-Elemente, sondern irgendwelche größeren Matrizen. 08:17.250 --> 08:19.850 Hier haben wir mit der Kommutativität kein Problem, das läuft ja alles 08:19.850 --> 08:20.730 ganz klassisch ab. 08:21.170 --> 08:26.270 Insofern ist das ein einfacher Ansatz, um etwas zu parallelisieren. 08:26.630 --> 08:30.610 Und dann war die Idee, dass wir jetzt verschiedene Sachen gesehen 08:30.610 --> 08:34.290 haben, bei denen sich so Matrizen, Daten bewegen, in verschiedenen 08:34.290 --> 08:37.630 Richtungen, solche Prozessorfelder, und die Frage ist, wie man sowas 08:37.630 --> 08:41.590 systematisch machen kann, wie kommt man darauf, ein hexagonales Feld 08:41.590 --> 08:44.230 oder ein zweidimensionales Feld in der einen oder anderen Art 08:44.230 --> 08:48.910 anzusehen, und vor allen Dingen, warum müssen hier die Matrizen so von 08:48.910 --> 08:51.410 oben nach unten, unten nach oben und links nach rechts laufen. 08:52.110 --> 08:53.250 Das könnten wir doch anders machen. 08:53.530 --> 08:56.330 Ja, bei einem anderen Verfahren hatten wir die von links nach rechts, 08:56.450 --> 08:57.890 oben, unten, eine blieb konstant. 08:58.390 --> 09:01.450 Und dann war eben die Idee, dass man systematisch daran geht, sich 09:01.450 --> 09:03.170 anguckt, was sind das eigentlich für Probleme. 09:03.750 --> 09:06.090 In diesem Fall hatten wir immer als Ausgangspunkt bei der Matrix 09:06.090 --> 09:10.790 -Modifikation diese iterativen Algorithmen, so ein dreifach 09:10.790 --> 09:14.670 geschachteltes Schleifen, das iterative Algorithmus, und das kann man 09:14.670 --> 09:16.890 auch als System- oder Rekurrenzgleichung angeben, und da nimmt man 09:16.890 --> 09:19.830 halt systematisch, guckt man sich an, die Datenabhängigkeiten, 09:19.990 --> 09:23.490 analysiert das, macht sich daraus einen Graphen und sieht dann, wie 09:23.490 --> 09:26.070 die Berechnungen voneinander abhängen, das ist das, was wir hier dann 09:26.070 --> 09:29.530 auf dieser Folie sehen, beziehungsweise auf der nächsten Folie. 09:30.250 --> 09:34.630 Da war dieser Datenabhängigkeitsgraph dargestellt, wo jeder Knoten 09:34.630 --> 09:37.070 eine Berechnung ist, die ausgeführt werden muss. 09:37.790 --> 09:42.470 Also eine dieser Skalarprodukt-Operationen, die hier angegeben waren, 09:42.590 --> 09:50.770 da an dieser Stelle, dieses C ikj-3C ik-1j plus A ikj-1 mal B i-1kj, 09:51.430 --> 09:54.570 und die drei Indizes brauchte man halt, um geeignet durch ein 09:54.570 --> 09:57.570 dreidimensionales Gitter die ganzen Sachen durchschieben zu können. 09:57.910 --> 10:01.130 Dann haben wir also so ein dreidimensionales Gitter für die einzelnen 10:01.130 --> 10:04.150 Berechnungen, und die Frage ist dann, wie man das auf konkrete 10:04.150 --> 10:06.730 Ressourcen abbildet, das heißt zum Beispiel auch so ein 10:06.730 --> 10:09.730 zweidimensionales Feld, das geschieht halt über Projektionsmatrizen, 10:10.310 --> 10:14.810 über lineare Transformationen, bei denen man dann halt einen Teil als 10:14.810 --> 10:17.850 Zeittransformation betrachtet und den anderen Teil als 10:17.850 --> 10:21.670 Ortstransformation, und dadurch dann ein Schedule hat für die 10:21.670 --> 10:25.210 Berechnungen, also die Einzelberechnungen auf Zeit und Ort abbildet 10:25.210 --> 10:27.110 und damit einen Algorithmus bekommt. 10:27.210 --> 10:29.670 Und je nachdem, welche Matrix man verwendet, kann man dann eben 10:29.670 --> 10:31.090 Algorithmen erzeugen. 10:31.190 --> 10:33.470 Also ich erzeuge jetzt, generiere Algorithmen und dann erzeuge ich 10:33.470 --> 10:34.750 mathematische Transformationen. 10:35.030 --> 10:37.410 Und da ich von einer mathematischen Beschreibung des Problems 10:37.410 --> 10:40.530 ausgegangen bin und damit mathematische Transformationen Algorithmen 10:40.530 --> 10:43.910 erzeuge, habe ich garantiert korrekte Algorithmen und ich kann da 10:43.910 --> 10:46.270 beliebig mit rumspielen, bekomme verschiedene Varianten dieser 10:46.270 --> 10:49.530 Algorithmen, dadurch quasi frei Haus geliefert. 10:50.110 --> 10:52.830 Also dieser Schedule, der dann rauskommt, den kann ich ja systematisch 10:52.830 --> 10:55.150 überführen in ein Programm, das braucht man nicht selbst zu schreiben, 10:55.310 --> 10:59.190 das kann man sich eine Methode für schreiben, die einem das Programm 10:59.190 --> 11:00.670 dazu erzeugt. 11:00.670 --> 11:04.330 Dann habe ich also ein paralleles Programm, das ist eine systematische 11:04.330 --> 11:08.530 Art, solche Programme zu entwerfen, allerdings natürlich eingeschränkt 11:08.530 --> 11:14.210 auf diese Art von Berechnungen, solche iterativen Algorithmen oder 11:14.210 --> 11:17.350 Berechnungen, die durch Rekurrenzgleichungen beschrieben sind, das 11:17.350 --> 11:21.410 muss man sich anschauen, das sind dann Teile von Berechnungen, die so 11:21.410 --> 11:24.050 dargestellt sind und alles, was dazwischen ist, wird halt irgendwie 11:24.050 --> 11:24.770 anders gemacht. 11:25.470 --> 11:31.350 Nur kann man dann eben gewisse Teile auf solchen parallelen Strukturen 11:31.350 --> 11:37.570 sehr effizient ausführen und das eben auf eine Art, die die 11:37.570 --> 11:42.250 Kreativität an eine andere Stelle steckt, nämlich wie baue ich meine 11:42.250 --> 11:43.210 Transformationsmatrix. 11:43.790 --> 11:48.730 Und damit man damit geeignet umgehen kann, hatten wir, ich weiß nicht, 11:48.790 --> 11:50.730 hatten Sie das Werkzeug gezeigt? 11:51.250 --> 11:52.530 Nein, das hat nicht funktioniert. 11:53.350 --> 11:54.150 Hat nicht funktioniert? 11:54.450 --> 11:55.670 Aha, mal sehen, ob es jetzt funktioniert. 11:55.670 --> 11:59.470 Okay, dann gucken wir mal, ob ich da jetzt rankomme. 11:59.610 --> 12:01.230 Ich habe das gestern Abend probiert, das hat noch funktioniert, 12:01.390 --> 12:02.930 deswegen müsste es jetzt eigentlich auch funktionieren. 12:03.490 --> 12:07.490 Das ist also hier unser, erstmal nur der Webbrowser und da kommt unser 12:07.490 --> 12:09.170 Werkzeug. 12:09.510 --> 12:11.230 Haben Sie das schon mal ausprobiert, zwischendurch? 12:12.410 --> 12:13.350 Sind Sie da dran gewesen? 12:13.590 --> 12:14.730 Keiner von Ihnen war da dran. 12:16.170 --> 12:21.110 Also, das ist hier ein Modul oder eine Java-Anwendung, ein Applet, mit 12:21.110 --> 12:28.210 dem man verschiedene Varianten, verschiedene Probleme, solche Graphen, 12:28.330 --> 12:32.290 erstmal Datenabhängigkeitsgrafen darstellt und daraus dann eine Lage 12:32.290 --> 12:34.690 ist, verschiedene Algorithmen zu erzeugen. 12:34.990 --> 12:37.930 Und hier sind also mehrere dargestellt. 12:38.390 --> 12:42.330 Ich wähle jetzt mal, machen wir das so, da haben wir alles auf der 12:42.330 --> 12:43.350 Folie drauf hier. 12:43.850 --> 12:46.630 Das ist also verschiedene Probleme, sortieren, Matrix-Vektor 12:46.630 --> 12:50.130 -Multiplikation und Matrix-Multiplikation, nebenher haben wir genau 12:50.130 --> 12:51.910 das Bild, was ich vorher auch auf der Folie hatte. 12:53.510 --> 12:55.890 Und das ist also ein Produkt, das im Rahmen der Wissens-Werkstatt 12:55.890 --> 12:58.810 -Rechen -Systeme vor Jahren entstanden war, was Sie immer noch schön 12:58.810 --> 12:59.510 einsetzen können. 13:00.030 --> 13:01.750 Und jetzt muss man sich anschauen, was ist denn hier eigentlich 13:01.750 --> 13:02.290 dargestellt. 13:02.510 --> 13:05.990 Hier ist eine Erläuterung, ich will gar nicht zu viel Zeit darauf 13:05.990 --> 13:10.430 verwenden jetzt, also hier sind verschiedene Sachen dargestellt, Blau, 13:10.790 --> 13:17.070 Wartungselement B, B ist hier angedeutet von links nach rechts, Rot, 13:17.070 --> 13:22.650 Wartungselement Aij, J, das läuft also hier so diagonal durch, links 13:22.650 --> 13:27.670 unten nach rechts oben, und die Zwischensumme C läuft also grün, läuft 13:27.670 --> 13:28.510 von oben nach unten. 13:29.810 --> 13:35.090 So, und jetzt müssen wir uns hier angucken, hier steht im Prinzip die 13:35.090 --> 13:41.410 Matrix, aufgespalten in die Zeit-Transformation, die oberste Zeile, 13:41.910 --> 13:44.810 zuständig für die Zeit, und die Prozessor-Zuordnungen sind die 13:44.810 --> 13:46.990 restlichen Zeilen der Matrix. 13:48.890 --> 13:50.730 Und jetzt schauen wir mal, was hier passiert. 13:50.830 --> 13:53.830 Hier ist übrigens noch angedeutet, was in den Knoten passiert, also in 13:53.830 --> 13:59.630 so einem Knoten wird halt das, was von oben kommt, addiert auf das 13:59.630 --> 14:04.050 Ergebnis dieser Modifikation. 14:04.110 --> 14:09.630 In die Modifikation geht also ein, das was von links kommt, die blaue 14:09.630 --> 14:13.670 Linie geht da rein, und was von links unten kommt, geht dort auch 14:13.670 --> 14:17.290 rein, und die beiden Werte, blauen und roten Werte, werden außerdem 14:17.290 --> 14:20.710 weitergegeben nach rechts oben, beziehungsweise nach rechts. 14:21.690 --> 14:24.610 Und das Ergebnis der Addition wird halt dann nach unten weitergegeben. 14:24.730 --> 14:27.390 Und da steckt halt genau die Berechnung drin, in dem einzelnen Knoten. 14:27.790 --> 14:29.770 Jetzt müssen wir spielen damit, oder können wir damit spielen. 14:30.170 --> 14:32.850 Wenn ich jetzt einfach sagen würde, retime, da wird natürlich jetzt 14:32.850 --> 14:35.970 Unsinn passieren, nee, nicht retime, apply, wenn ich das sagen würde, 14:36.550 --> 14:41.410 alles mit 0, Transformationsmatrix ist natürlich singulär, also jede 14:41.410 --> 14:43.650 Matrix konnte man nicht nehmen, da hat der Herr Fugler auch drauf 14:43.650 --> 14:47.050 hingewiesen, stand auch auf den Folien drauf, es kann sich ein 14:47.050 --> 14:50.570 ungültiger Signalflussgraf ergeben, der sieht jetzt einfach so aus. 14:51.710 --> 14:53.690 Alles, warum kommt der raus? 14:54.250 --> 14:55.930 Weil ich alles auf den gleichen Punkt abbilde. 14:56.450 --> 15:00.490 Ich habe keinerlei Zeitverzögerung drin, und deswegen ist alles, ich 15:00.490 --> 15:05.030 habe keine Ortsabhängigkeiten irgendwie drin, alles auf einem Punkt, 15:05.330 --> 15:07.490 wird alles zum gleichen Zeitpunkt berechnet. 15:08.430 --> 15:09.470 Das geht natürlich nicht. 15:10.010 --> 15:11.310 Wir haben eine gewisse logische Abhängigkeit. 15:11.310 --> 15:15.210 Machen wir mal hier irgendeine, also Zeitvektor, da mache ich jetzt 15:15.210 --> 15:16.750 mal einfach 1, 1, 1, 15:19.890 --> 15:23.550 und also immer einen Takt Verzögerung zwischen den einzelnen 15:23.550 --> 15:28.290 Berechnungen, und Prozessorzuordnung, da nehmen wir einfach mal hier 15:28.290 --> 15:33.050 eine 1, mal sehen was passiert, da eine 1, und machen wir hier 15:33.050 --> 15:37.250 vielleicht mal eine 1, und da auch eine 1. 15:38.290 --> 15:41.630 So, jetzt schauen wir nochmal kurz, wir haben hier angedeutet, da 15:41.630 --> 15:47.910 oben, in Rot jeweils die Richtung, die Datenrichtung, für die der 15:47.910 --> 15:51.630 jeweilige Vektor zuständig ist, die jeweilige Spalte zuständig ist. 15:52.730 --> 15:57.690 So, das ist also für horizontal, vertikal, diagonal. 15:58.910 --> 16:03.970 Also, schauen wir mal was passiert, da haben wir so ein schönes Feld. 16:04.830 --> 16:09.210 Das ist jetzt unser zweidimensionales Feld, und hier sehen Sie, läuft 16:09.210 --> 16:19.850 jetzt die blaue Matrix, blau, ist die horizontale, 1, 0, genau. 16:20.250 --> 16:25.750 Jeweils ein Takt horizontal verschoben, 0 vertikal verschoben. 16:26.230 --> 16:27.190 Das ist das was hier steht. 16:28.210 --> 16:35.870 Die nächste Zeile, vertikal, war das grüne Element, 0 um 0, horizontal 16:35.870 --> 16:38.310 verschoben, 1 vertikal verschoben. 16:38.690 --> 16:40.370 Also, von oben nach unten. 16:41.750 --> 16:46.330 Und Prozessor zu, also Quatsch, die Diagonale ist hier auch genauso 16:46.330 --> 16:51.070 dargestellt, allerdings um 1, jeweils positiv verschoben, in x- und y 16:51.070 --> 16:54.310 -Richtung, deswegen diagonal von links oben nach rechts unten. 16:55.690 --> 16:59.090 Das ist also jetzt im Prinzip eine, oder ist eine 16:59.090 --> 16:59.990 Matrixmultiplikation. 17:00.650 --> 17:03.470 Ich könnte das verändern, ich könnte hier zum Beispiel hinschreiben, 17:03.470 --> 17:05.290 eine Minus 1. 17:06.310 --> 17:07.530 Dann sieht das so aus. 17:08.850 --> 17:13.870 Oder, ich könnte sagen, machen wir doch hier raus eine 1. 17:14.510 --> 17:16.590 Ah, Singulär. 17:18.230 --> 17:19.130 Pech gehabt. 17:19.290 --> 17:20.030 Geht so nicht. 17:20.610 --> 17:26.650 Dann machen wir doch mal vielleicht hier raus, was ist das denn jetzt? 17:27.770 --> 17:29.650 Ich habe nicht auf OK gedrückt, genau. 17:31.170 --> 17:32.090 Ah, danke. 17:32.090 --> 17:33.930 Hat er immer noch nicht gemacht. 17:35.490 --> 17:36.350 Da ist er. 17:36.710 --> 17:37.170 Genau. 17:38.790 --> 17:39.610 Da muss ich auf OK gehen. 17:39.730 --> 17:41.890 Ah, jetzt hat er es trotzdem gemacht. 17:41.970 --> 17:43.150 Sieht doch seltsam aus. 17:43.370 --> 17:47.010 Das ist also jetzt mit 1, 1 und Minus 1. 17:47.350 --> 17:48.870 Das macht er. 17:49.270 --> 17:50.510 Das ist auch Singulär. 17:52.110 --> 17:53.750 Okay, das war das hier. 17:53.910 --> 17:55.750 Dann machen wir mal hier raus. 17:56.930 --> 17:57.610 Wie ist das denn? 17:58.110 --> 17:58.410 Ups. 18:01.860 --> 18:02.300 So. 18:03.180 --> 18:04.640 Also, man kann hier beliebig rumspielen. 18:05.160 --> 18:06.180 Können Sie einfach verwenden. 18:06.520 --> 18:08.920 Gehen Sie auf den Link, dann können Sie damit verschiedene Sachen 18:08.920 --> 18:09.200 machen. 18:09.660 --> 18:13.240 Es ist einfach interessant, sich anzugucken, wie hier die Berechnungen 18:13.240 --> 18:15.400 unterschiedlich erzeugt werden können. 18:16.120 --> 18:18.780 Das geht eben dann, wie gesagt, einfach durch mathematische 18:18.780 --> 18:19.740 Transformationen. 18:20.080 --> 18:22.860 Dann sehen Sie solch eine Abbildung hier auf die Prozessoren. 18:22.960 --> 18:24.240 Das ist einfach nur visuell dargestellt. 18:24.380 --> 18:25.560 Daraus können Sie natürlich ein Schedule machen. 18:25.680 --> 18:29.180 Und wie gesagt, im Prinzip kann man dadurch daraus dann automatisch 18:29.180 --> 18:29.740 ein Programm erzeugen. 18:30.840 --> 18:32.160 Und das ist eine ganz wichtige Sache. 18:32.340 --> 18:36.240 Schreiben Sie mal ein paralleles Programm selber, bis Sie das korrekt 18:36.240 --> 18:38.860 hinbekommen in den entsprechenden Programmiersprachen und so weiter, 18:39.080 --> 18:40.000 ist gar nicht so einfach. 18:40.760 --> 18:43.440 Hier haben Sie das dann automatisch korrekt. 18:43.820 --> 18:46.360 Und das ist ja das, was man als Ingenieur machen am liebsten hat. 18:46.680 --> 18:49.620 Dass man irgendein Verfahren hat, wie man systematisch irgendwelche 18:49.620 --> 18:50.920 schönen Produkte entwerfen kann. 18:51.740 --> 18:54.360 Gut, das können Sie dann auch sich für andere Sachen angucken, also 18:54.360 --> 18:57.180 für Sortierproblemen und ähnliche Dinge. 18:57.420 --> 18:58.800 Will ich jetzt gar nicht näher darauf eingehen. 18:58.920 --> 18:59.680 Können Sie mit rumspielen. 18:59.760 --> 19:03.440 Es ist jeweils eine Erläuterung dazu, wer das gemacht hat. 19:03.500 --> 19:05.820 Stefan Leppert vor... war ja gar nicht so lange her. 19:05.920 --> 19:06.560 Zwölf Jahre her. 19:08.140 --> 19:11.700 Und dann... 19:12.480 --> 19:14.500 Das war mir gar nicht klar, dass es schon so lange her ist. 19:15.100 --> 19:17.300 Und es ist ja auch irgendwo eine Erläuterung dazu. 19:18.620 --> 19:23.300 Genau, da steht dann drin, was man dort machen muss. 19:23.880 --> 19:29.220 Und schauen Sie es einfach selbst mal an. 19:29.420 --> 19:31.520 Dann sehen Sie, wie man damit umgehen kann. 19:32.100 --> 19:33.680 Also, das zu dieser Anwendung. 19:33.780 --> 19:35.060 Ich denke, die ist ganz nett. 19:36.260 --> 19:40.880 Dass man sieht, welche Hilfsmittel hat man, um diesen Ansatz 19:40.880 --> 19:42.480 tatsächlich umzusetzen. 19:43.020 --> 19:46.680 Es ist so, dass ich Ihnen nur einen kleinen Einblick gegeben habe, was 19:46.680 --> 19:48.500 man mit dieser Transformationsmethode machen kann. 19:49.180 --> 19:53.140 Es gibt darüber sehr viel grundlegende Untersuchungen. 19:53.800 --> 19:56.880 Nicht nur für diese einfachen, dreifach geschafften Schleifen, wie 19:56.880 --> 19:59.360 Matrixmultiplikation, sondern auch für eine ganze Reihe anderer 19:59.360 --> 19:59.980 Anwendungen. 20:00.460 --> 20:02.820 Da gibt es also verschiedenste Arten von Transformationen, die man 20:02.820 --> 20:03.480 ausführen kann. 20:03.900 --> 20:05.660 Da hat der Herr Schukler sich auch darauf hingewiesen. 20:05.760 --> 20:08.860 Das Buch von Herrn Zehentner hat darüber habilitiert und ein dickes 20:08.860 --> 20:12.860 Buch geschrieben, in dem man eine sehr umfassende Darstellung hat 20:12.860 --> 20:13.540 dieser Methode. 20:14.080 --> 20:19.180 Diese ganzen Verfahren sind in den Mitte der 80er, Anfang der 90er 20:19.180 --> 20:19.900 gemacht worden. 20:20.680 --> 20:24.960 Und dann war so die Entwicklung, dass die Parallelrechner, gerade die 20:24.960 --> 20:28.960 Massivparallelrechner, nicht mehr so richtig im Fokus waren, weil die 20:28.960 --> 20:30.940 anderen Rechner so schnell wurden, die Einzelprozessoren. 20:31.600 --> 20:35.100 Und diese Methodik ist nach wie vor wichtig. 20:35.220 --> 20:39.560 Kann man jetzt auch umsetzen, anwenden oder umbauen für Multicore 20:39.560 --> 20:40.100 -Verfahren. 20:40.620 --> 20:45.140 Und das wäre also auch eine interessante Sache, wie man direkt diese 20:45.140 --> 20:48.520 Ansätze, was ich sagte, daraus direkt Algorithmen erzeugen für 20:48.520 --> 20:49.320 Parallelrechner. 20:49.720 --> 20:52.700 Hier kann man einfach ein Werkzeug dransetzen, um Algorithmen zu 20:52.700 --> 20:56.100 erzeugen für Multicore- oder Manicore-Rechner, die eine etwas andere 20:56.100 --> 20:57.640 Speicherstruktur haben. 20:57.760 --> 21:01.140 Die sind normalerweise nicht so einfache zweidimensionale Felder. 21:01.580 --> 21:03.920 Wäre ja auch zu einfach, wenn man die Strukturen einfach machen würde, 21:03.960 --> 21:05.240 sodass man sie einfach programmieren kann. 21:06.540 --> 21:10.640 Das war jetzt etwas sarkastisch, aber die Manicore-Rechner sind nicht 21:10.640 --> 21:14.180 unbedingt immer für aus algorithmischer Sicht optimal gebaut. 21:15.160 --> 21:17.760 Also, das heißt dann aber, das ist eine Herausforderung für uns und 21:17.760 --> 21:20.800 wir müssen sehen, wie wir die trotzdem effizient programmieren können 21:20.800 --> 21:25.260 und das kann man eben mit solchen Ansätzen auf jeden Fall auch ganz 21:25.260 --> 21:25.860 gut voranbringen. 21:27.140 --> 21:29.720 Das also zu dem Mapping-Ansatz. 21:30.100 --> 21:31.900 Wichtige Geschichte. 21:34.120 --> 21:35.000 Und dann... 21:36.020 --> 21:38.240 Sie werden auch Gelegenheit haben, das in den Übungen noch 21:39.020 --> 21:39.460 weiterzumachen. 21:39.720 --> 21:41.580 Dann ging es um die Auswertung von Polynomen. 21:41.660 --> 21:43.580 Das hat ich Ihnen letzte Woche auch schon erzählt. 21:43.920 --> 21:48.540 Wie man Polynome auswertet, also Werte berechnet. 21:49.260 --> 21:52.980 Und da ist halt die Idee gewesen, ich geh gleich mal wieder hier raus, 21:54.020 --> 21:57.780 damit das schneller geht, dass man einfach sich anguckt. 21:58.160 --> 22:03.840 Ich habe im Prinzip hier eine Problemstellung, bei der ich es zu tun 22:03.840 --> 22:07.160 habe mit Operationen auf Körpern, das heißt mit einfachen 22:07.160 --> 22:08.480 arithmetischen Operationen. 22:09.100 --> 22:12.680 Ich habe Addition, Subtraktion, Multiplikation, Division und ich habe 22:12.680 --> 22:14.060 auch noch die... 22:14.060 --> 22:19.080 Ich habe halt keine Kenntnis über die einzelnen Parameter, deswegen 22:19.080 --> 22:21.540 diese mathematische Darstellung. 22:22.480 --> 22:27.120 Ein Körper, beziehungsweise ich arbeite in Körpererweiterungen, in 22:27.120 --> 22:29.120 transcendenten Körpererweiterungen. 22:29.240 --> 22:31.920 Etwas, was Ihnen vielleicht von Ihrer Vorbildung hier, von der 22:31.920 --> 22:33.760 Mathematikausbildung nicht so präsent ist. 22:34.040 --> 22:35.720 Eine kurze Frage an den, die hier sind. 22:36.020 --> 22:39.160 Wer von Ihnen hat etwas von solchen Dingen gehört, von 22:39.160 --> 22:41.340 Körpererweiterungen, Galowerfeldern und solchen Dingen? 22:43.000 --> 22:44.240 Hat keiner von Ihnen gehört? 22:44.680 --> 22:45.700 Defizit der Ausbildung. 22:46.120 --> 22:50.480 Eindeutig, weil Arbeiten auf Galowerfeldern, auf endlichen Körpern ein 22:50.480 --> 22:53.960 ganz wichtiges Gebiet ist für die Informatik, für alle Anwendungsweise 22:53.960 --> 22:54.840 im Sicherheitsbereich. 22:54.960 --> 22:58.160 Die interessanten cryptographischen Verfahren arbeiten alle mit 22:58.160 --> 23:00.940 Operationen in Galowerfeldern, in endlichen Körpern. 23:01.380 --> 23:03.120 Und deswegen sollte man sich sowas angucken. 23:03.720 --> 23:04.720 Gibt es schöne Bücher drüber. 23:05.360 --> 23:08.000 Das, was ich hier mache, kann man trotzdem verstehen, auch wenn man 23:08.000 --> 23:09.160 keine Galowerfelder kennt. 23:09.960 --> 23:12.440 Ja, aber übrigens, Sie haben hier Galios geschrieben. 23:12.960 --> 23:15.860 Das ist nicht Galios, sondern Galois. 23:16.840 --> 23:19.960 Also das ist L-O-I-S. 23:20.380 --> 23:23.300 Galower war halt ein junger Wissenschaftler, der leider sehr jung 23:23.300 --> 23:28.400 verstorben ist, aufgrund eines Duells in den Zwanzigern war er. 23:28.520 --> 23:32.560 Und seine ganzen Notizen hatte er halt irgendwo zu Hause auf dem 23:32.560 --> 23:33.140 Schreibtisch liegen. 23:33.300 --> 23:34.740 Und das war die Theorie der Galowerfelder. 23:35.320 --> 23:37.780 Ganz toller, genialer Mensch, der leider zu früh gestorben ist. 23:38.260 --> 23:42.760 So, dann die Idee, wie kann ich also jetzt die Kenntnis über meinen 23:42.760 --> 23:46.640 Input, über die Problemstellung ausnutzen, um geeignet zu berechnen. 23:47.360 --> 23:50.580 Und da war eben die Idee, genau, so weit sind Sie gekommen letztes 23:50.580 --> 23:50.840 Mal. 23:51.520 --> 23:59.500 Da war die Idee, dass ich mir angucke, was weiß ich über meine 23:59.500 --> 24:00.260 Problemstellung? 24:00.260 --> 24:02.380 Was muss ich eigentlich berechnen? 24:02.460 --> 24:04.920 Da waren hier unterschiedliche Dinge dargestellt. 24:05.700 --> 24:09.200 Und das heißt immer, ich muss mir angucken, welche Informationen 24:09.200 --> 24:10.160 liegen schon vor? 24:10.720 --> 24:12.700 Und was muss ich noch zusätzlich berechnen? 24:13.640 --> 24:20.100 Und deswegen, wenn die Eingabemenge, die Menge an Informationen, die 24:20.100 --> 24:24.580 mir zur Verfügung steht, bereits alle Kombination von Elementen 24:24.580 --> 24:28.960 enthält, von X und A0 bis AN, dann brauche ich gar nichts zu tun, dann 24:28.960 --> 24:31.200 ist das nur ein Suchproblem. 24:32.000 --> 24:35.040 Dann suche ich nur das geeignete Element, ich greife auf das geeignete 24:35.040 --> 24:39.460 Element zu und das geeignete Element in dem Fall wäre eben das ANXON 24:39.460 --> 24:41.780 plus und so weiter, also Summe AIXOI. 24:42.200 --> 24:44.600 Das ist dann einfach ein Element meines Datenraumes. 24:45.880 --> 24:47.740 Da muss ich nur drauf zugreifen, das ist ein Zugriffsproblem. 24:48.480 --> 24:51.360 Wenn ich weniger Informationen habe, wie hier zum Beispiel, da habe 24:51.360 --> 24:57.820 ich im Prinzip alle Skalaroperationen, alle Zahlen zur Verfügung und 24:57.820 --> 25:02.640 ich habe die Variablen, die werden mir aufgegeben, X, A0 bis AN, aber 25:02.640 --> 25:06.700 ich habe keine Kombination von denen zur Verfügung, dann muss ich 25:06.700 --> 25:08.060 diese Kombination berechnen. 25:08.620 --> 25:12.820 Und da gab es dann halt verschiedene Arten das zu tun und wenn man 25:12.820 --> 25:16.100 eben sagt, hier hat man eben ein Verfahren, das auch noch ein bisschen 25:16.100 --> 25:20.320 ungewöhnlich ist, da berechne ich halt diese Potenzen mit N-1 25:20.320 --> 25:27.100 Modifikation und dann die einzelnen Produkte A, I, X hoch I, die Summe 25:27.100 --> 25:31.500 des Ganzen kommt dann auf 3N-1 arithmetische Operationen und wenn man 25:32.380 --> 25:35.620 davon ausgeht, dass wir alle Potenzen von X schon zur Verfügung haben, 25:35.700 --> 25:39.260 brauche ich nur drauf zuzugreifen, irgendwo im Datenspeicher, dann 25:39.260 --> 25:42.220 habe ich den ersten Schritt, hier den Schritt A, kostenlos und kann, 25:42.380 --> 25:42.620 bzw. 25:42.960 --> 25:46.500 ich habe nur die Zugriffe zu machen, kann einfach drauf zugreifen und 25:46.500 --> 25:48.720 habe dann 2N arithmetische Operationen. 25:49.540 --> 25:53.260 Und wenn ich eben ein anderes Verfahren nehme, das ich Ihnen zu Anfang 25:53.260 --> 25:56.620 schon mal vorgestellt hatte, dann geht es eben auch mit 2N 25:56.620 --> 25:59.480 arithmetischen Operationen und das hier dient einfach nur dazu, Ihnen 25:59.480 --> 26:02.100 zu zeigen, wie die Vielfalt ist von Berechnungen. 26:02.740 --> 26:05.220 Man muss immer sehen, was ist eigentlich meine Ausgangsbasis. 26:05.680 --> 26:07.940 Jetzt kommen die unteren Schranken und da gibt es eben diesen schönen 26:07.940 --> 26:14.020 Satz von Ostrowski und ich muss Ihnen einfach an dieser Stelle das mal 26:14.020 --> 26:17.640 kurz machen, ein bisschen Mathematik machen, weil ich Ihnen zeigen 26:17.640 --> 26:22.640 will, es gibt Probleme, bei denen wir exakt zeigen können, das ist 26:22.640 --> 26:27.360 nicht nur asymptotisch ein optimaler Algorithmus, sondern exakt ein 26:27.360 --> 26:28.560 optimaler Algorithmus. 26:29.000 --> 26:32.240 Ich kann die untere Schranke 2N zeigen und ich weiß, die obere 26:32.240 --> 26:36.840 Schranke ist auch 2N, das heißt ich habe genau einen Algorithmus, der 26:36.840 --> 26:37.660 optimal ist. 26:38.820 --> 26:43.000 Selbst wenn ich keine Information habe über die Problemstellung, also 26:43.000 --> 26:47.460 ich weiß nichts über X und A0 bis AN, sondern habe das alles in der 26:47.460 --> 26:49.420 Eingabe drin und kann dann anfangen zu rechnen. 26:50.260 --> 26:56.720 Und der Satz von Ostrowski, der sagt halt aus, dass jeder Algorithmus 26:56.720 --> 27:02.060 für die Auswertung von P von A wissen Sie, das ist das allgemeine 27:02.060 --> 27:05.260 Polynom endengerades, in, nun welcher Bereich ist das hier? 27:05.920 --> 27:07.580 X, A0 bis AN. 27:09.420 --> 27:14.660 Also ich darf in diesem Bereich arbeiten, aber ich arbeite nur, und 27:14.660 --> 27:17.880 das ist auch einfach nur Notationsgeschichte, wenn ich dieses X, A0 27:17.880 --> 27:22.560 bis AN in eckigen Klammern schreibe, dann ist das keine 27:22.560 --> 27:27.820 Körpererweiterung, sondern ist das ein Polynomring über F durch 27:27.820 --> 27:29.680 Erweiterung mit X, A0 bis AN. 27:29.780 --> 27:31.460 Da kann ich alle Polynome darüber hinschreiben. 27:32.280 --> 27:35.240 Aber ich kann eben keine Division hinschreiben, bzw. 27:35.660 --> 27:38.920 ich habe nicht notwendigerweise die Körpereigenschaft, das heißt ich 27:38.920 --> 27:44.200 habe nicht notwendigerweise inverse Elemente zur Verfügung. 27:44.700 --> 27:48.760 Und deswegen bezieht sich dieser Satz darauf, dass ich, ich könnte es 27:48.760 --> 27:53.060 anders formulieren, wenn ich nur Addition, Subtraktion und 27:53.060 --> 27:56.900 Multiplikation zur Verfügung habe, und Divisionen nicht erlaubt sind, 27:57.320 --> 28:01.160 dann benötigt jeder Algorithmus für die Auswertung des allgemeinen 28:01.160 --> 28:03.740 Polynom endengerades mindestens eine Addition. 28:04.200 --> 28:04.980 Das ist die Aussage. 28:05.800 --> 28:09.140 Ich habe es einfach so mathematisch formuliert, damit Sie sehen, was 28:09.140 --> 28:12.820 man, wenn man hier hinschreibt, das ist ein Polynomring, dann weiß 28:12.820 --> 28:15.940 man, aha, da kann ich nachgucken, was ist ein Polynomring, was hat der 28:15.940 --> 28:18.740 alles für Eigenschaften, das kann man ausnutzen. 28:18.780 --> 28:21.680 Und das ist das, was wir machen müssen, wir müssen Eigenschaften von 28:21.680 --> 28:24.380 den Bereichen, in denen wir arbeiten, der eigenen ausnutzen können. 28:25.320 --> 28:28.900 Und darum geht es eigentlich, dass man die Information sinnvoll nutzt. 28:29.420 --> 28:33.000 So, und dann gibt es noch einen zweiten Satz von Pan, ein paar Jahre 28:33.000 --> 28:38.440 später, zwölf Jahre später, der dann gesagt hat, dass das Horner 28:38.440 --> 28:42.400 Schema tatsächlich ein optimaler Algorithmus ist, in Bezug auf die 28:42.400 --> 28:46.220 Anzahl der Multiplikationen-Divisionen, selbst wenn man also hier 28:46.220 --> 28:48.580 natürlich auch Divisionen tatsächlich machen kann. 28:48.680 --> 28:52.060 Also diese Einschränkung von Ostrowski ist gar nicht erforderlich, man 28:52.060 --> 28:55.160 kann es auch ohne, auch mit Divisionen tatsächlich hinbekommen. 28:55.320 --> 28:58.360 Ich will Ihnen den Satz von Pan nicht zeigen, aber das, was der 28:58.360 --> 29:00.900 Ostrowski gemacht hat, will ich Ihnen kurz darstellen. 29:01.680 --> 29:02.900 Corolla noch kurz dazu. 29:03.020 --> 29:05.720 Wenn ich also diesen Satz habe, dann weiß ich, dass das Horner Schema 29:05.720 --> 29:11.520 optimal ist für die Auswertung von Polynomen, weil ich da genau diese 29:11.520 --> 29:13.420 2N -Operationen brauche. 29:15.420 --> 29:20.020 Also das steht, das steht doch eigentlich hier schon drin, für die 29:20.020 --> 29:21.160 Berechnung des Polynomens Ausgehen. 29:21.280 --> 29:23.140 So wird das Horner Schema ein optimaler Algorithmus in Bezug auf die 29:23.140 --> 29:24.720 Anzahl der Multiplikationen-Divisionen. 29:30.220 --> 29:34.220 Ja, also Ausgehen von f von x vereinigt a0 bis an. 29:36.700 --> 29:47.820 Und selbst wenn ich hier ausgehen würde, nur von f und x, bin im 29:47.820 --> 29:50.620 Augenblick etwas irritiert, weil das ja eigentlich hier oben schon 29:50.620 --> 29:52.120 drin steht. 29:54.480 --> 29:57.500 Ist das Horner Schema ein optimaler Algorithmus in Bezug auf die 29:57.500 --> 29:59.160 Anzahl der Multiplikationen-Divisionen? 29:59.200 --> 30:00.040 Ach so, Entschuldigung. 30:01.140 --> 30:02.960 Die beiden Sätze zusammen natürlich nur. 30:03.060 --> 30:05.520 Hier geht es nur um die Anzahl der Multiplikationen-Divisionen, hier 30:05.520 --> 30:07.160 geht es um die Additionen. 30:07.220 --> 30:08.740 Beides zusammen bringt uns das Korrelativ. 30:11.660 --> 30:13.860 Also, schauen wir uns die Additionen an. 30:14.040 --> 30:17.840 Multiplikationen-Divisionen überlasse ich Ihrem Wissensdrang. 30:18.000 --> 30:20.820 Schauen Sie sich entsprechend Literatur an dazu, suchen Sie nach dem 30:20.820 --> 30:22.440 Satz von Hahn, dann finden Sie den Beweis. 30:23.460 --> 30:27.160 Wie kann man sowas zeigen, dass sich eine gewisse Anzahl von 30:27.160 --> 30:28.360 Additionen mindestens brauchen? 30:29.920 --> 30:31.680 Und die Idee ist einfach folgende. 30:31.740 --> 30:34.740 Wir gucken uns an, einen beliebigen Algorithmus, wenn wir eine untere 30:34.740 --> 30:35.440 Schranke haben. 30:36.220 --> 30:38.000 Untere Schranken zu zeigen ist schwer. 30:38.820 --> 30:42.980 Da mache ich eine Aussage über beliebige Algorithmen, die angewandt 30:42.980 --> 30:43.520 werden können. 30:44.860 --> 30:48.920 Und das heißt, wenn wir irgendeinen Algorithmus sehen, A, der dieses 30:48.920 --> 30:51.760 Polynom, das allgemeine Polynom endgerades auswertet. 30:52.380 --> 30:54.440 Und jetzt mache ich einen kleinen Trick. 30:54.640 --> 30:57.920 Ich substituiere in diesem Algorithmus überall x durch 1. 30:59.080 --> 31:01.140 Ich verändere den Algorithmus überhaupt nicht. 31:01.860 --> 31:07.000 Bis auf die Tatsache, dass ich überall, wo dort ein x auftritt, eine 1 31:07.000 --> 31:07.540 hinschreibe. 31:08.640 --> 31:12.060 Das vereinfacht natürlich, was berechnet der jetzt eigentlich? 31:12.840 --> 31:17.460 Der berechnet diesen Algorithmus A', berechnet dann das gleiche wie A, 31:17.600 --> 31:19.980 allerdings für den Fall, dass x gleich 1 ist. 31:21.300 --> 31:25.760 Und das heißt, der berechnet im Prinzip diese Summe der Ai. 31:26.840 --> 31:27.620 Mehr nicht. 31:29.380 --> 31:30.380 Das ist ja viel einfacher. 31:32.200 --> 31:34.220 Und jetzt sage ich, das ist ein einfacheres Problem, vielleicht kann 31:34.220 --> 31:36.720 ich ja für dieses einfachere Problem, wenn ich mit die beiden hier 31:36.720 --> 31:39.440 vergleiche, da stehen noch diese xoi mit dabei. 31:40.960 --> 31:42.500 Jetzt habe ich hier nur die Summe der Ai. 31:42.560 --> 31:44.900 Ich habe es also reduziert auf ein einfaches Problem und möchte jetzt 31:44.900 --> 31:45.740 dafür zahlen. 31:46.440 --> 31:49.640 Ich brauche dafür mindestens n Additionen. 31:49.900 --> 31:52.200 Das sind n plus 1 Terme, A0 bis An. 31:53.440 --> 31:54.540 Mindestens n Additionen. 31:54.540 --> 31:58.200 Ich kann also nicht irgendwas mir ersparen und ich weiß, ich habe 31:58.200 --> 32:00.720 vorher keine Informationen über diese Ai. 32:01.500 --> 32:06.200 Die Aussage ist also, ich brauche sicherlich nicht mehr Additionen als 32:06.200 --> 32:08.060 A, vielleicht kann man welche einsparen. 32:08.980 --> 32:11.920 Wenn ich zeigen kann, ich brauche auch mit dem mindestens n 32:11.920 --> 32:14.040 Additionen, braucht A das sowieso. 32:17.300 --> 32:24.460 Und die Behauptung ist, ich brauche für beliebige Größen hierfür 32:24.460 --> 32:26.080 mindestens n Additionen. 32:26.100 --> 32:28.600 Also für die Auswertung dieser Summe. 32:29.300 --> 32:32.640 Man macht das einfach durch Induktion, dass es für jedes n gelten 32:32.640 --> 32:32.860 soll. 32:32.940 --> 32:34.000 Ich fange an mit n gleich 0. 32:35.320 --> 32:37.100 Da brauche ich das alles nur A0. 32:37.600 --> 32:39.040 Brauche 0 Additionen. 32:39.160 --> 32:39.700 Bin schon fertig. 32:40.000 --> 32:40.880 Das Element ist schon gegeben. 32:42.740 --> 32:45.060 Wir nehmen also an, das Ganze ist gezeigt für n. 32:45.120 --> 32:48.060 Wir müssen zeigen, dass es für n plus 1 auch gilt. 32:49.320 --> 32:53.460 Schauen wir uns also an, die Situation für n plus 1 und wir nehmen 32:53.460 --> 33:00.400 einfach an, dass es für die Problemgröße n plus 1 nicht gilt. 33:00.980 --> 33:07.660 Wir nehmen an, wir haben ein Algorithmus B, der die Summe bis n plus 1 33:08.680 --> 33:12.760 mit weniger als n plus 1 Additionen berechnet. 33:14.300 --> 33:15.800 Das nehmen wir einfach an. 33:16.660 --> 33:19.380 Dann müssen wir zeigen, das führt zu einem Widerspruch. 33:19.680 --> 33:24.680 Wir wollen also zeigen, wenn das für n plus 1 nicht gilt, dann kann 33:24.680 --> 33:25.780 das auch für n nicht gelten. 33:25.860 --> 33:26.520 Das wollen wir zeigen. 33:28.320 --> 33:32.740 Da müsste ich die Summe bis n mit n minus 1 Additionen berechnen 33:32.740 --> 33:33.000 können. 33:34.760 --> 33:39.500 Und die Annahme ist ja, die Induktionsannahme ist natürlich, dass es 33:39.500 --> 33:40.600 für n gezeigt ist. 33:41.180 --> 33:43.100 Da wollen wir schließen, dass n plus 1 auch gilt. 33:43.220 --> 33:44.060 Wir machen das andersrum. 33:44.200 --> 33:47.000 Wir nehmen an, n plus 1 gilt nicht, n gilt auch für n nicht. 33:48.380 --> 33:48.480 So. 33:50.280 --> 33:52.900 Jetzt schauen wir uns an, wann tritt die erste Addition auf in dem 33:52.900 --> 33:53.340 Vertrag. 33:54.680 --> 34:00.260 Algorithmus B hat irgendwann die erste Addition. 34:00.720 --> 34:03.700 Die erste Addition heißt, davor können irgendwelche anderen 34:03.700 --> 34:05.120 Operationen aufgetaucht sein. 34:05.880 --> 34:07.580 Kann irgendwas anderes gemacht worden sein. 34:08.400 --> 34:10.680 Was kann davor gemacht worden sein, wenn ich nicht addiere? 34:11.300 --> 34:12.920 Irgendeine der anderen Operationen. 34:12.920 --> 34:14.860 Ich darf keine Division ausführen. 34:15.960 --> 34:18.220 Also, das einzige, was ich machen kann, ist multiplizieren. 34:19.640 --> 34:24.960 Ich habe also irgendein Produkt meiner Koeffizienten und noch 34:24.960 --> 34:29.560 irgendein zweites Produkt der Koeffizienten, die addiert werden soll. 34:29.580 --> 34:30.620 Das ist die erste Addition. 34:31.160 --> 34:32.640 Alles andere sind Multiplikationen. 34:33.760 --> 34:37.180 Und Sie wissen, wenn man so eine Aussage machen will, die Leute kommen 34:37.180 --> 34:39.780 ja auf irgendwelche seltsamen Ideen. 34:39.780 --> 34:43.440 Wie der Vinograd, der da irgendeinen komischen Term sich ausgedacht 34:43.440 --> 34:46.520 hat, um dieses einfache Skalarprodukt darzustellen. 34:47.060 --> 34:49.520 Also es kann tatsächlich sein, dass man durch irgendwelche wilden 34:49.520 --> 34:53.460 Multiplikationen vielleicht nachher irgendwelche Operationen einsparen 34:53.460 --> 34:53.640 kann. 34:55.140 --> 34:56.600 Also, schauen wir uns an. 34:57.080 --> 35:01.740 Das erste Produkt, die 1 von a quer, ist also irgendein Produkt von 35:01.740 --> 35:02.500 Koeffizienten. 35:02.580 --> 35:07.480 Irgendein Produkt von Koeffizienten in dieser... 35:07.480 --> 35:14.000 also in dem Bereich f von und so weiter da über den Skalaren im Körper 35:14.000 --> 35:14.900 f. 35:15.100 --> 35:21.340 Heißt, ich habe meine ai, die vielleicht irgendwie mehrfach 35:21.340 --> 35:25.500 auftauchen, deswegen jeweils hoch ein ri, mit irgendwelchen Exponenten 35:25.500 --> 35:26.300 können die auftauchen. 35:27.780 --> 35:31.060 Also kann ein Koeffizient mehrfach da drin vorkommen. 35:31.260 --> 35:36.060 Und ich habe für jeden einzelnen Koeffizienten, von i gleich 0 bis n 35:36.060 --> 35:41.400 plus 1, habe ich irgendein Produkt dieses Koeffizienten und das Ganze 35:41.400 --> 35:43.140 noch mit irgendeinem Skalar modifiziert. 35:43.260 --> 35:44.960 Das c1 ist also aus irgendeinem Skalar. 35:48.520 --> 35:51.660 Und, also dieses mit c1, c2 aus f und so weiter, bezieht sich hier auf 35:51.660 --> 35:52.940 diese Formel hier hinten. 35:53.520 --> 35:54.560 Die beiden Formeln. 35:55.840 --> 35:57.960 Und das ri kann natürlich auch 0 sein. 35:58.060 --> 36:02.000 Wenn es 0 ist, heißt das, dieser Koeffizient tritt nicht auf in dem 36:02.000 --> 36:02.380 Produkt. 36:02.380 --> 36:10.560 Also alle ri ungleich 0 sagen, dieser Koeffizient tritt jeweils auf, 36:10.740 --> 36:13.060 mindestens einmal, vielleicht sogar mehrfach. 36:14.480 --> 36:19.860 Und das gleiche für das zweite Produkt, irgendwelche Exponenten si. 36:21.320 --> 36:22.660 Und jetzt kommt der nächste Trick. 36:25.480 --> 36:31.000 Ich nehme an, dass rn plus 1 ungleich 0 ist. 36:31.140 --> 36:35.800 Beziehungsweise ich nehme an, mindestens ein Koeffizient, äh Quatsch, 36:35.880 --> 36:40.740 mindestens ein Exponent in diesen beiden Produkten ist, oder in jedem 36:40.740 --> 36:43.180 dieser beiden Produkte, ist ungleich 0. 36:44.320 --> 36:48.580 Insbesondere hier in p1 nehme ich an, dass rn plus 1 ungleich 0 ist. 36:51.000 --> 36:54.120 Es könnte, und das ist ohne Beschränkung der Allgemeinheit, die 36:54.120 --> 36:56.220 Anordnung der Koeffizienten ist ja völlig beliebig. 36:57.420 --> 37:00.320 Ja, deswegen sage ich, ich nehme einfach, ich greife mir zufällig eins 37:00.320 --> 37:04.100 raus und ich nehme an, wie es zufällig ist, ist das rn plus 1. 37:05.120 --> 37:07.960 Das heißt, rn plus 1 kommt in p1 vor. 37:08.400 --> 37:09.120 In dem ersten Produkt. 37:09.220 --> 37:10.420 Ich könnte irgendein anderes nehmen. 37:12.500 --> 37:14.960 Und jetzt mache ich eine weitere Vereinfachung. 37:16.200 --> 37:20.240 Ich ersetze einfach rn plus 1 durch 0. 37:23.150 --> 37:25.110 Ich weiß doch gar nichts über rn plus 1. 37:26.010 --> 37:26.910 Wieso kann ich das machen? 37:27.890 --> 37:30.390 Ich mache einfach die weitere Vereinfachung. 37:30.970 --> 37:35.070 Für den Fall, dass rn plus 1 gleich 0 ist, muss das Verfahren ja auch 37:35.070 --> 37:35.610 funktionieren. 37:37.150 --> 37:40.290 Ich ändere ansonsten an dem Ablauf des Algorithmus gar nichts. 37:40.770 --> 37:42.530 Ich ändere nur den Wert, der dort auftritt. 37:43.410 --> 37:44.910 In den einzelnen Berechnungen. 37:46.470 --> 37:46.630 So. 37:47.430 --> 37:51.790 Und wenn ich jetzt rn plus 1 durch 0 ersetze, und das darf ich nur, 37:52.070 --> 37:55.290 weil keine Divisionen vorkommen, es könnte ja ansonsten sein, dass 37:55.290 --> 38:00.850 irgendwo bis dahin schon irgendwelche Divisionen gewesen sind, wo rn 38:00.850 --> 38:02.150 plus 1 im Nenner steht. 38:02.830 --> 38:04.850 Und dann wäre der Nenner gleich 0. 38:04.910 --> 38:05.610 Das darf ich ja nicht. 38:05.670 --> 38:08.130 Deswegen darf ich keine Divisionen haben in dem Verfahren. 38:09.730 --> 38:10.870 Was wird denn dann noch berechnet? 38:12.190 --> 38:17.530 Für diesen Fall x gleich 1, das war die erste Annahme, und die zweite 38:18.310 --> 38:26.330 rn plus 1 gleich 0, hätte ich dann ja, folgendes erreicht, dass dieses 38:26.330 --> 38:33.750 erste Produkt, p1 von a quer, dieses Produkt hier, wenn das rn plus 1 38:33.750 --> 38:41.470 gleich 0 ist, das tritt auf mit einem Nicht-Null-Exponenten, dann ist 38:41.470 --> 38:42.410 das Produkt gleich 0. 38:43.050 --> 38:47.650 Wenn das Produkt gleich 0 ist, dieses erste Produkt p1, dann kann ich, 38:47.790 --> 38:49.330 dann brauche ich diese Addition ja gar nicht. 38:50.330 --> 38:51.370 Dann ist die ja überflüssig. 38:52.930 --> 38:53.930 Das heißt, die hat keine Wirkung. 38:54.570 --> 38:59.370 Die könnte ich rausstreichen aus dem Algorithmus B und ich würde 38:59.370 --> 39:04.090 nichts anderes berechnen für x gleich 1 und rn plus 1 gleich 0. 39:05.870 --> 39:12.910 Für diese Situation würde Algorithmus B deswegen nichts anderes 39:12.910 --> 39:15.170 berechnen, wenn ich diese eine Addition rausstreiche. 39:15.310 --> 39:18.530 Ich kann also einfach sagen, ich streiche diese eine Addition raus. 39:19.930 --> 39:26.010 Ich hatte gesagt, ich kann das Ganze mit k kleiner als n plus 1 39:26.010 --> 39:26.890 Addition berechnen. 39:27.490 --> 39:29.330 Das war die Annahme über den Algorithmus B. 39:30.430 --> 39:33.230 Jetzt habe ich eine Addition gestrichen, bin also bei k minus 1 39:33.230 --> 39:33.710 Addition. 39:34.830 --> 39:36.690 k minus 1 ist also kleiner als n. 39:37.810 --> 39:38.850 Und was berechne ich? 39:39.570 --> 39:46.830 In dem Algorithmus B für rn plus 1 gleich 0, der berechnet diese Summe 39:47.430 --> 39:53.310 i gleich 0 bis n plus 1 ai für die Situation rn plus 1 gleich 0. 39:54.030 --> 39:56.530 Und das ist gerade die Summe i gleich 0 bis n ai. 39:57.870 --> 40:02.810 Und das heißt, wir können mit dem Algorithmus B die Summe i gleich 0 40:02.810 --> 40:07.490 bis n ai mit k minus 1, also weniger als n Addition berechnen. 40:08.330 --> 40:11.870 Und damit haben wir gezeigt, wenn das für n plus 1 nicht gilt, dann 40:11.870 --> 40:13.070 gilt es auch nicht für n. 40:14.590 --> 40:19.290 Diese Aussage, ich brauche mindestens n Addition für die Berechnung 40:19.290 --> 40:22.970 der Summe ai für i gleich 0 bis n. 40:23.590 --> 40:25.510 Kann ich jetzt mit n minus 1, d.h. 40:25.610 --> 40:28.590 damit habe ich gezeigt, diese Behauptung gilt. 40:30.130 --> 40:33.790 Aus nicht n plus 1 folgt nicht n, also haben wir damit die 40:33.790 --> 40:39.050 Kontraposition aus n folgt n plus 1 gezeigt. 40:40.330 --> 40:46.190 Was wir also zu zeigen wollten und damit sind wir mit dem Beweis 40:46.190 --> 40:46.510 durch. 40:47.050 --> 40:50.850 Sie sehen einfach, für eine untere Schranke muss man genau aufpassen, 40:50.910 --> 40:51.450 was man macht. 40:52.150 --> 40:56.010 Ich habe keine einzige besondere Eigenschaft des Algorithmus B 40:56.010 --> 40:56.770 ausgenutzt. 40:57.910 --> 41:01.750 Ich habe nur gesagt, ich lasse den völlig unberührt, bis auf den einen 41:01.750 --> 41:03.830 Punkt, dass ich sage, ich streiche die erste Addition. 41:04.910 --> 41:09.170 Und das mache ich, weil ich durch eine bestimmte Annahme über die Art 41:09.170 --> 41:15.850 der Eingaben zeigen konnte, die ist unnötig für diese Annahme a n plus 41:15.850 --> 41:16.570 1 gleich 0. 41:16.930 --> 41:19.610 Da kann ich die streichen, ohne dass sich der Wert, der ausgerechnet 41:19.610 --> 41:20.210 wird, verändert. 41:20.870 --> 41:21.310 So. 41:22.150 --> 41:25.210 Ich wollte das sehr ausführlich beschreiben, damit Sie sehen, was man 41:25.210 --> 41:25.950 hier eigentlich macht. 41:26.590 --> 41:30.410 Wir werden in dieser Vorlesung nicht viele Beweise der Laufzeit von 41:30.410 --> 41:31.270 Algorithmen machen. 41:31.710 --> 41:33.930 Könnte man auch wesentlich formaler machen, aber ich denke, das ist 41:33.930 --> 41:34.810 schon formal genug. 41:34.950 --> 41:37.430 An dieser Stelle würde ich es einmal tun, weil es einfach ein 41:37.430 --> 41:40.430 instruktives Beispiel ist zu sehen, hier habe ich tatsächlich die 41:40.430 --> 41:44.270 Möglichkeit exakt zu zeigen, dass eine bestimmte Anzahl von 41:44.270 --> 41:47.370 Operationen erforderlich ist und ich kann auch genau die Zahl 41:47.370 --> 41:47.730 erreichen. 41:48.050 --> 41:50.570 Ein seltener Fall bei Algorithmen. 41:51.150 --> 41:55.230 Und schon kommt hier die Frage, ist das tatsächlich alles wahr? 41:55.670 --> 41:56.490 Natürlich ist das wahr. 41:57.030 --> 42:00.710 Aber nur, wenn ich genau diese Annahme habe. 42:01.550 --> 42:06.630 Wenn Sie also ein Programm schreiben und Sie haben in Ihrem Programm 42:06.630 --> 42:14.130 ein spezielles Polynom, dann wissen Sie zum Zeitpunkt des Entwurfs des 42:14.130 --> 42:16.850 Programms, was für ein Polynom berechnet werden muss. 42:16.910 --> 42:20.930 Dann kennen Sie die Koeffizienten und es ist nicht so, dass Sie jedes 42:20.930 --> 42:24.450 Mal, wenn das Programm aufgerufen wird, neue Koeffizienten geliefert 42:24.450 --> 42:26.310 bekommen und ein unbekanntes x dazu. 42:28.110 --> 42:32.550 Wenn also zum Beispiel diese Koeffizienten bekannt sind, wäre nur das 42:32.550 --> 42:33.730 x nicht bekannt. 42:34.970 --> 42:36.570 Und dann können Sie natürlich viel mehr machen. 42:37.970 --> 42:45.750 Also, wir hatten ganz zu Anfang ein Beispiel, da war dieses einfach 42:45.750 --> 42:48.730 nur Summe xoi zu berechnen. 42:48.810 --> 42:51.370 Wenn alle Koeffizienten 1 sind, hat man gesehen, das geht mit 3 42:51.370 --> 42:51.830 Berechnungen. 42:52.230 --> 42:54.050 Quatsch, mit log n Berechnungen. 42:54.290 --> 42:56.850 Log n plus 2 oder 3 oder sowas. 42:58.070 --> 43:01.830 Das war die Summe xoi, ist einfach durch eine Formel zu berechnen. 43:02.430 --> 43:03.390 Ganz einfach zu machen. 43:03.550 --> 43:05.190 Dann weiß ich etwas über die Koeffizienten. 43:05.610 --> 43:07.270 Hier ist ein etwas komplizierteres Polynom. 43:07.890 --> 43:09.030 Was kann ich denn da machen? 43:10.190 --> 43:14.550 Da habe ich irgendwelche Koeffizienten gegeben und jetzt manipuliere 43:14.550 --> 43:15.490 ich diesen Ausdruck. 43:16.630 --> 43:19.450 Ganz ähnlich, wie das der Winograd gemacht hat mit der 43:19.450 --> 43:20.250 Matrixmultiplikation. 43:20.330 --> 43:24.290 In diesem Fall spalte ich einen Term zweiter Ordnung ab. 43:24.290 --> 43:26.430 Also, die x²-4. 43:27.210 --> 43:32.530 Ich stelle also fest, ich kann dieses Polynom P6 von x, Polynom 43:32.530 --> 43:36.710 sechsten Grades, darstellen durch ein Produkt von zwei Polynomen. 43:37.430 --> 43:43.730 Das erste Polynom ist also einfach dieses x²-4 und das zweite ist ein 43:43.730 --> 43:46.370 Polynom vierten Grades plus irgendein Rest. 43:47.030 --> 43:50.470 Das heißt, ich habe einfach gesagt, ich mache dieses Problem sechster 43:50.470 --> 43:51.790 Ordnung, ist mir zu schwer. 43:52.770 --> 43:56.050 Ich mache daraus ein Produkt von zwei, die einen kleineren Grad haben. 43:56.370 --> 43:59.130 Eins hat den Grad 2, das andere hat den Grad 4 in dem Fall. 43:59.570 --> 44:02.410 Und das geht nicht genau auf, da habe ich irgendeinen Rest, das sind 44:02.410 --> 44:03.430 hier die 53 da. 44:05.650 --> 44:09.870 Und dann sage ich, naja, also dieses Polynom vierten Grades, das ist 44:09.870 --> 44:10.550 mir viel zu schwer. 44:11.490 --> 44:15.850 Ich mache daraus ein Produkt von einem Polynom zweiten Grades, wieder 44:15.850 --> 44:18.330 der gleichen Art, wie ich das vorher auch schon gemacht habe, so ein 44:18.330 --> 44:23.390 x², in diesem Fall plus 9 und dann bleibt hier natürlich beim Polynom 44:23.390 --> 44:27.650 vierten Grades ein Polynom zweiten Grades übrig und noch wieder 44:27.650 --> 44:33.150 irgendein Skalar als Rest und ich habe jetzt ein Produkt von zwei 44:33.150 --> 44:34.450 Polynomen zweiten Grades. 44:35.830 --> 44:41.310 Und jetzt rechne ich endlich den Wert des Polynoms. 44:41.990 --> 44:48.130 Jetzt habe ich mein Polynom dargestellt als das Produkt von zwei 44:48.130 --> 44:54.030 Polynomen x²-4 mal x² plus 9 mal diesen P2 von x plus 4. 44:55.510 --> 44:59.450 Ich muss sicherlich x² berechnen. 45:01.010 --> 45:04.770 Ja, das brauche ich um zum Beispiel hier, da steht 2x², da steht auch 45:04.770 --> 45:05.530 x² drin. 45:06.310 --> 45:08.230 Das muss ich berechnen, das ist eine Modifikation. 45:09.370 --> 45:11.590 Dann möchte ich gerne P2 von x berechnen. 45:11.650 --> 45:16.730 P2 von x, das ist dieses Polynom hier, 2x² plus 8x plus 1. 45:17.290 --> 45:21.770 Da habe ich zwei Modifikationen drin, Skalare mit x und zwei 45:21.770 --> 45:23.730 Additionen. 45:24.270 --> 45:27.290 Dann muss ich P4 berechnen. 45:28.390 --> 45:36.050 Um P4 zu berechnen, muss ich P2 von x multiplizieren mit x² plus 9. 45:36.690 --> 45:41.330 Dazu muss ich das mal ausrechnen, das ist eine Addition und eine 45:41.330 --> 45:43.770 Modifikation, um das Produkt dieser beiden zu berechnen. 45:43.770 --> 45:46.630 Und plus noch mal eine Addition obendrauf, das ist plus 4. 45:48.370 --> 45:51.290 Das steht hier, eine Modifikation, zwei Additionen noch dazu. 45:52.230 --> 45:53.910 Und schließlich muss ich P6 berechnen. 45:54.610 --> 45:55.690 Da habe ich wieder das gleiche. 45:56.430 --> 46:04.310 Ich habe P4 mal diesem Polynom hier, x² minus 4 und dann noch ein 46:04.310 --> 46:05.310 Skalar obendrauf. 46:05.910 --> 46:08.230 Das heißt noch mal eine Modifikation und zwei Additionen. 46:09.070 --> 46:16.290 Und das Ganze hat mich jetzt etwas erleichtert oder etwas hat mir den 46:16.290 --> 46:17.530 Aufwand etwas erleichtert. 46:18.590 --> 46:22.950 Ich habe statt 6 Multiplikationen, habe ich 5 Multiplikationen und 6 46:22.950 --> 46:23.630 Additionen. 46:24.050 --> 46:26.590 War das den Aufwand wert, diese Aufteilung zu machen? 46:27.430 --> 46:30.570 Nun, für diesen Fall eines Polynoms sechsten Grades lohnt sich das 46:30.570 --> 46:31.290 sicherlich nicht. 46:32.930 --> 46:35.190 Aber wir sehen es besser als das Vorderschema. 46:35.790 --> 46:39.130 Das heißt eben, da wir in diesem Fall Informationen über die 46:39.130 --> 46:43.090 Koeffizienten haben, können wir die ausnutzen und können dann etwas 46:43.090 --> 46:46.610 machen, was hier in diesem Fall zeigt, wir können dann besser sein als 46:46.610 --> 46:49.510 das Vorderschema, können die Anzahl der Modifikationen reduzieren, 46:49.730 --> 46:52.830 obwohl wir wissen, aufgrund des Satzes von Pan, den ich Ihnen nicht 46:52.830 --> 46:58.830 bewiesen habe, dass wir für ein allgemeines Polynom mindestens 6 46:58.830 --> 46:59.730 Modifikationen brauchen. 47:00.670 --> 47:03.230 Wenn wir das jetzt ein bisschen allgemeiner machen, dann heißt das, 47:03.330 --> 47:08.510 zur Entwurfszeit des Algorithmus entwickeln wir einfach eine 47:08.510 --> 47:12.390 Aufteilung unseres Polynoms. 47:12.550 --> 47:15.370 Wir haben ein allgemeines Polynom endengerades gegeben, nicht ganz 47:15.370 --> 47:17.150 allgemein, wir kennen die Koeffizienten. 47:17.890 --> 47:22.230 Und dann machen wir jeweils eine Aufteilung x² minus irgendein alpha n 47:22.230 --> 47:25.890 mal Polynome Pn-2 von x plus Rn und so weiter. 47:26.390 --> 47:29.450 Ich habe also eine Folge solcher Polynome, die ich hier dargestellt, 47:30.890 --> 47:33.830 bis ich runterkomme auf so ein Restpolynom P2 von x. 47:34.470 --> 47:40.310 Und dann muss ich dieses so dargestellte Produkt von Polynomen zweiten 47:40.310 --> 47:41.750 Grades geeignet auswerten. 47:42.370 --> 47:44.530 Und das geht ganz genauso wie vorher auch. 47:44.670 --> 47:50.390 Ich habe x² zu berechnen, ich muss P2 von x berechnen und danach 47:50.390 --> 47:54.870 rattert das durch die anderen Polynome jeweils das gleiche Schema. 47:55.410 --> 48:03.510 Ich habe mein x² minus alpha 2i zu berechnen für i gleich 2 bis n 48:03.510 --> 48:14.890 halbe und muss dann hier mal dieses P2i minus 2 von x plus R2i noch 48:14.890 --> 48:17.050 dann ausrechnen. 48:17.610 --> 48:27.310 Und das sind dann gerade n halbe minus 1 mal den Schritt 3 plus die 48:27.310 --> 48:31.770 anderen Schritte insgesamt n halbe plus 2 Modifikation und n Addition. 48:31.910 --> 48:34.210 Wenn Sie alles genau aufaddieren und das hier angucken, wie viele 48:34.210 --> 48:41.110 Operationen ich hier habe, dann sind das gerade solche gerade diese n 48:41.110 --> 48:42.170 halbe plus 2 Modifikation. 48:42.270 --> 48:45.670 Das heißt, wir haben im Prinzip für großes n die Anzahl der 48:45.670 --> 48:46.690 Modifikationen halbiert. 48:47.410 --> 48:51.770 Und das kann für ein Programm, bei dem Sie wirklich sehen müssen, ich 48:51.770 --> 48:52.990 muss die Zeit reduzieren. 48:53.770 --> 48:56.950 Sie haben hier durchaus etwas eingespart. 48:56.950 --> 49:02.890 Das ist also eine Verbesserung, die man für ein effizientes Programm 49:02.890 --> 49:03.590 machen sollte. 49:04.150 --> 49:08.650 Ich habe Ihnen nicht gezeigt, wie man diese Voreinstellung macht, das 49:08.650 --> 49:09.490 Pre -Conditioning. 49:10.410 --> 49:13.830 Das heißt, wie kann ich tatsächlich solch eine Aufteilung machen? 49:13.930 --> 49:15.930 Wie finde ich diese Alpha-n bis Alpha-4? 49:18.030 --> 49:21.790 Das ist wieder etwas, da will ich gar nicht näher einsteigen, das 49:21.790 --> 49:26.350 steht in dem Buch von Borodin und Monroe drin. 49:27.090 --> 49:29.690 Können Sie sich angucken, gibt es Veröffentlichungen darüber. 49:29.870 --> 49:31.550 Schauen Sie sich das an, wie man das konkret macht. 49:31.630 --> 49:35.770 Ich wollte nur einfach die Tatsache darstellen, wenn ich mehr weiß 49:35.770 --> 49:41.070 über die Problemstellung zur Entwurfszeit des Algorithmus, dann kann 49:41.070 --> 49:45.730 ich dieses Wissen reinstecken und habe dann zur Laufzeit des 49:45.730 --> 49:50.910 Algorithmus Vorteile bei der Effizienz, bei den Kosten, die den 49:50.910 --> 49:54.870 Aufwand, den ich in diese Voreinstellung stecken musste, aufwiegen 49:54.870 --> 49:57.630 können, wenn ich genügend häufig das Programm anwende. 49:58.670 --> 50:01.750 Und wenn Sie davon ausgehen, Sie müssen so etwas nicht nur einmal 50:01.750 --> 50:04.810 anwenden, sonst würden Sie ja auch kein Programm schreiben dafür, dann 50:04.810 --> 50:06.770 ist das ein sinnvoller Aufwand. 50:06.970 --> 50:10.750 Also, das, was Sie lernen sollten an der Stelle ist, man muss genau 50:10.750 --> 50:15.250 gucken, was weiß ich über die Problemstellung und alles, was ich weiß, 50:15.370 --> 50:18.150 nutze ich aus und mache daraus einen effizienten Algorithmus. 50:18.710 --> 50:20.550 Und das führt zu reduzierten Kosten. 50:22.910 --> 50:28.990 Jetzt gibt es eine interessante andere Geschichte, wenn ich also jetzt 50:28.990 --> 50:37.890 ein Polynom für viele verschiedene Stellen auswerten möchte. 50:38.550 --> 50:42.670 Also hier oben hatten wir angenommen, wir haben ein Polynom, bei dem 50:42.670 --> 50:44.990 ich die Koeffizienten kenne zur Laufzeit. 50:46.050 --> 50:47.370 Quatsch, zur Entwurfszeit. 50:47.370 --> 50:49.730 Und ich kann diese Kenntnis einsetzen. 50:50.790 --> 50:53.490 Jetzt kommt eine andere Idee. 50:54.270 --> 51:00.570 Ich weiß, ich habe eine bestimmte Menge von Werten von x, für die ich 51:00.570 --> 51:04.890 ein Polynom, allgemeines Polynom, ich habe also keine Kenntnis über 51:04.890 --> 51:09.650 meine Koeffizienten vorher, für die ich das auswerten kann. 51:11.430 --> 51:14.250 Und zwar die Enteneinheitswurzel. 51:14.250 --> 51:17.830 Da wissen Sie jetzt noch nicht, was das ist, vielleicht, werden Sie 51:17.830 --> 51:18.610 gleich kennenlernen. 51:19.610 --> 51:21.130 N verschiedene Werte für x. 51:22.610 --> 51:27.550 Und hier behaupte ich, für diese spezielle Wahl von Werten, für die 51:27.550 --> 51:32.090 ich mein Polynom auswerte, n mal Polynom auswerten, wir wissen, wir 51:32.090 --> 51:35.230 brauchen auch das, diese Voreinstellung hier braucht ja immer noch 51:35.230 --> 51:40.310 Aufwand von n, also linearen Aufwand für die Auswertung, für n Werte. 51:40.410 --> 51:44.370 Das Auswerten braucht ja mindestens n² Operationen. 51:45.630 --> 51:49.770 Und hier ist die Behauptung, wir können mit n log n arithmetischen 51:49.770 --> 51:55.430 Operationen ein Polynom, ein allgemeines Polynom, auswerten an n 51:55.430 --> 51:59.050 verschiedenen Stellen, wenn das gerade diese Enteneinheitswurzel sind. 51:59.650 --> 52:01.270 Eine interessante Idee. 52:02.130 --> 52:04.530 Das ist die sogenannte schnelle Fourier-Transformation, zu der wir 52:04.530 --> 52:05.310 jetzt gleich kommen werden. 52:07.030 --> 52:08.810 Auch ein sehr interessanter Ansatz. 52:09.610 --> 52:11.450 Wie kann man Zeit sparen? 52:12.010 --> 52:16.870 Und hier zu erwarten wäre eben n² bei Auswertung eines Polynoms an n 52:16.870 --> 52:17.210 Stellen. 52:17.410 --> 52:20.830 Ich kann es aber, wenn ich weiß, welche Speziellen das sind, wirklich 52:20.830 --> 52:24.790 sehr spezielle in dem Fall, kann ich den Aufwand reduzieren auf n mal 52:24.790 --> 52:25.190 log n. 52:25.970 --> 52:29.550 Das hätte ich also eine log n Operation pro Auswertung. 52:31.030 --> 52:37.370 Ganz kurz davor noch der Weg oder der Schritt zur Fragestellung, was 52:37.370 --> 52:40.370 kann ich denn machen, wenn ich das Ganze parallelisieren möchte. 52:42.030 --> 52:43.150 Polynomauswertung parallelisieren. 52:44.330 --> 52:45.430 Wie geht denn das? 52:45.490 --> 52:47.150 Was wir bisher gemacht haben, war Horner-Schema. 52:48.510 --> 52:52.890 Inherent sequenziell, also wenn ich mir das anschaue, hier meine 52:52.890 --> 53:00.910 vielen Klammern und dann meinen x plus a n minus 1 und so weiter mal x 53:00.910 --> 53:08.610 und so weiter und so weiter plus a 1 plus x plus a 0 das ist ja 53:08.610 --> 53:09.630 schrecklich sequenziell. 53:11.090 --> 53:15.290 Ich muss hier drin anfangen, ich kann keine Reihenfolgen irgendwie 53:15.290 --> 53:18.230 verändern, was soll ich da schon machen, da kann ich nichts 53:18.230 --> 53:18.870 parallelisieren. 53:18.990 --> 53:21.870 Ich muss anfangen mit der ersten Modifikation. 53:22.610 --> 53:26.810 So kann ich also nicht daran gehen, ich muss mein Verfahren verändern 53:27.950 --> 53:33.730 und ich könnte natürlich mein Polynom einfach anders darstellen. 53:34.810 --> 53:42.530 Ich kann es darstellen als eine Summe von zwei Polynomen halben 53:42.530 --> 53:43.010 Gerades. 53:43.990 --> 53:45.590 p in halbe und q in halbe. 53:46.610 --> 53:49.810 Und das p in halbe muss ich noch mit x hoch in halbe modifizieren. 53:51.090 --> 53:53.010 Dann habe ich also praktisch die linke Hälfte. 53:53.270 --> 53:56.930 Also im Prinzip ist das, wenn das hier mein großes Polynom ist, dann 53:56.930 --> 54:01.330 mache ich halt hier raus so etwas mal x hoch in halbe und hier ist der 54:01.330 --> 54:01.630 Rest. 54:03.970 --> 54:05.290 Das ist einfach die Idee. 54:05.350 --> 54:06.630 Ich brauche das ja noch anders darzustellen. 54:06.710 --> 54:10.670 Wir kennen die Eigenschaften der Arithmetik distributiv. 54:11.390 --> 54:14.570 Ich kann also die Reihenfolge der Klammern beliebig verändern. 54:15.090 --> 54:20.530 Ich klammere jetzt einfach so, wie hier dargestellt und habe dann zwei 54:20.530 --> 54:25.010 Polynomen halben Gerades und die kann ich natürlich jetzt parallel 54:25.010 --> 54:25.930 auswählen. 54:27.410 --> 54:31.550 Wobei das genau so zu machen nicht ganz sinnvoll ist. 54:32.030 --> 54:34.850 Ich hätte dann ja den gleichen Aufwand für zwei Polynome halben 54:34.850 --> 54:38.330 Gerades und müsste dann noch zwei Schritte obendrauf machen. 54:38.430 --> 54:40.010 Eine Multiplikation und eine Addition. 54:41.870 --> 54:46.510 Vielleicht wäre es sinnvoller, das leicht unsymmetrisch aufzuteilen, 54:47.230 --> 54:51.290 sodass ich nicht erst noch hier diese eine Multiplikation machen muss 54:51.290 --> 54:54.190 und dann addieren, sondern dass ich in der Zeit, in der ich das q in 54:54.190 --> 54:59.090 halbe oder die rechte Seite auswerte, schon die linke und die 54:59.090 --> 55:00.190 Multiplikation machen kann. 55:00.370 --> 55:01.370 Das ist ein bisschen zu verschieden. 55:01.850 --> 55:05.170 Aber auch wenn ich das so einfach mache, habe ich also bei meiner 55:05.170 --> 55:12.750 Zeitabschätzung die Zeit aufzuwenden, um zwei Polynome halben Gerades 55:12.750 --> 55:13.510 auszuwerten. 55:14.190 --> 55:16.750 Das kann ich parallel machen, die sind unabhängig voneinander. 55:17.390 --> 55:20.990 Zwei Schritte obendrauf und wenn man sich das hier anguckt, sieht man 55:20.990 --> 55:25.130 sofort, dass man ein bisschen geschultes Auge hat und ich werde Ihnen 55:25.130 --> 55:28.470 etwas später zeigen, wie man das Auge schulen kann, um solche 55:28.470 --> 55:31.150 Rekurrenzgleichungen einfach auszuwerten. 55:31.190 --> 55:32.010 Das sieht man aber sofort. 55:32.510 --> 55:35.950 Das ist einfach eine fortlaufende Halbierung der Problemgröße, immer 55:35.950 --> 55:38.230 nur konstanter Aufwand in jeder Schicht. 55:38.670 --> 55:44.130 Das heißt, ich habe zwei log n Schritte insgesamt hier zu machen und 55:44.130 --> 55:48.670 das ist ein Aufwand von log n, wenn ich also parallel arbeiten kann 55:49.850 --> 55:55.690 und habe dann natürlich, wenn ich mir die Ursprungsgröße angucke, das 55:55.690 --> 55:59.970 mache ich jetzt hier parallel, da natürlich auch parallel, parallel 55:59.970 --> 56:00.490 und so weiter. 56:00.590 --> 56:05.030 Ich habe also hier unten irgendwo viele Operationen parallel zu machen 56:05.030 --> 56:09.070 und danach wird das alles schön zusammengetröselt mit jeweils sehr 56:09.070 --> 56:11.730 wenigen zusätzlichen Operationen. 56:12.450 --> 56:16.950 Also ähnlich wie bei Skalarprodukt, schöne rekursive Aufteilung über 56:16.950 --> 56:21.870 einen Baum und damit kriege ich dann genau diese Aufteilung in log n 56:21.870 --> 56:27.490 Schritte, bei denen halt mehrere Operationen parallel ausgeführt 56:27.490 --> 56:27.750 werden. 56:29.270 --> 56:30.550 Das war zur Parallelisierung. 56:31.410 --> 56:33.350 Vielmehr lohnt sich nicht dazu zu erzählen. 56:33.830 --> 56:37.190 Kann man also Zeitgewinn kriegen von runter auf log n. 56:37.910 --> 56:40.510 Wenn man jetzt hier sagt, ich will aber nicht n Prozessoren nehmen, 56:40.590 --> 56:43.890 sondern ich nehme n durch log n, dann habe ich immer noch log n 56:43.890 --> 56:45.950 Aufwand und habe dann optimalen Zeitgewinn. 56:46.270 --> 56:47.650 Das hatte ich Ihnen auch schon mal vorgestellt. 56:47.770 --> 56:49.710 Das kann ich Ihnen noch kurz dazuschreiben. 56:51.070 --> 57:04.190 Also das wäre u von log n und mit n durch log n Prozessoren optimal zu 57:04.190 --> 57:04.350 machen. 57:05.190 --> 57:09.010 Das ist der übliche Ansatz, den ich Ihnen schon mal bei der Matrix 57:09.010 --> 57:10.410 -Modifikation dargestellt habe. 57:11.490 --> 57:14.370 Jetzt kommen wir zur versprochenen schnellen Fourier-Transformation. 57:15.790 --> 57:20.930 Auch ein klassisches Problem in technischen Anwendungen. 57:21.530 --> 57:25.350 Die Fourier-Transformation tritt dort sehr häufig auf und die schnelle 57:25.350 --> 57:29.630 Fourier -Transformation war auch ein ganz wichtiger Schritt, um eben 57:29.630 --> 57:31.570 solche Berechnungen deutlich schneller zu machen. 57:32.110 --> 57:36.290 Von einem Aufwand, der davor immer quadratisch angesehen wurde, auf 57:36.290 --> 57:38.170 einmal runter auf n log n. 57:38.170 --> 57:41.730 Das ist wirklich ein drastischer Zeitgewinn, den man da hat. 57:42.790 --> 57:44.950 Die Motivation, die ich Ihnen jetzt bringe, ist ein bisschen anders 57:44.950 --> 57:47.190 als das, was man in technischen Anwendungen unter der Fourier 57:47.190 --> 57:48.130 -Transformation versteht. 57:48.210 --> 57:49.730 Das ist eine Behaltung von Funktionen. 57:49.890 --> 57:53.170 Diskrete Fourier-Transformation ist halt ein bisschen... 57:54.450 --> 57:57.190 Das sehen Sie gleich, eine Transformation der Darstellung. 57:58.110 --> 58:01.310 Und ist jedenfalls eine wichtige Operation. 58:01.870 --> 58:04.250 Und die Motivation bei mir geht ein bisschen anders. 58:04.370 --> 58:06.890 Ich möchte das Produkt von zwei Polynomen berechnen. 58:08.410 --> 58:10.510 Zwei Polynome p vor nix und q vor nix. 58:10.990 --> 58:12.090 Beide Enten gratis. 58:12.970 --> 58:13.810 Was kommt da raus? 58:13.910 --> 58:18.170 Ein Produktpolynom, das natürlich, wenn ich zwei Polynome entengratis 58:18.170 --> 58:21.510 modifiziere, ein Polynom, das gratis 2n ist. 58:22.570 --> 58:28.590 Ein Polynom, das gratis 2n, hat also 2n plus 1 Koeffizienten ck. 58:30.370 --> 58:36.710 Und jedes ck ist halt irgendeine Kombination von Produkten von 58:36.710 --> 58:39.810 Koeffizienten der Polynome p und q. 58:41.630 --> 58:49.390 Und zwar, gut, das oberste, also das Glied Höchsterordnung mit x2n hat 58:49.390 --> 58:51.890 gerade an mal bn als Koeffizient. 58:52.690 --> 58:55.090 Unten bei a0 steht gerade a0 mal b0. 58:55.830 --> 58:59.290 Aber sobald Sie dann auf die anderen gehen, haben Sie immer mehr 58:59.290 --> 59:02.050 Produkte von einzelnen Komponenten drin. 59:02.590 --> 59:07.750 Und wenn Sie sich cn anschauen, dann haben Sie da an mal b0 plus an 59:07.750 --> 59:16.870 minus 1 mal also da steht dann an mal b0 plus an minus 1 mal b1 plus 59:16.870 --> 59:20.330 an minus 2 mal b2 und so weiter. 59:21.270 --> 59:22.210 Ein großer Teil. 59:23.050 --> 59:28.370 n Elemente stehen dort drin. 59:29.790 --> 59:34.730 Und das heißt, Sie haben hier ziemlich einen Aufwand zu treiben, um 59:34.730 --> 59:35.970 diese ck zu berechnen. 59:36.050 --> 59:38.610 Sie haben also Prinzip Größenordnung n Elemente, die jeweils 59:38.610 --> 59:42.170 Größenordnung n Operationen erfordern und damit haben Sie sofort einen 59:42.170 --> 59:43.530 Aufwand, der quadratisch ist. 59:43.910 --> 59:46.110 Nur um die Koeffizienten zu berechnen des Produktpolynoms. 59:47.450 --> 59:50.850 Und jetzt ist die Idee, wie kann ich das verbessern? 59:50.930 --> 59:53.730 Ich muss ja, wenn ich das Produktpolynom darstellen möchte, muss ich 59:53.730 --> 59:54.810 diese Koeffizienten kennen. 59:55.410 --> 01:00:00.590 Das ist, wenn ich es im kontinuierlichen Bereich betrachte, ist es das 01:00:00.590 --> 01:00:03.430 Problem der Faltung von zwei Funktionen. 01:00:03.470 --> 01:00:07.910 Hier habe ich im Prinzip die Produkte von Polynomen zu berechnen und 01:00:09.430 --> 01:00:11.930 die diskrete Darstellung von Funktionen. 01:00:12.390 --> 01:00:15.350 Und das, was ich jetzt hier im Prinzip mache, ist folgendes. 01:00:15.650 --> 01:00:20.050 Ich zeige Ihnen eine Idee der Fourier-Transformation. 01:00:21.170 --> 01:00:24.990 Ich möchte zwei Polynome modifizieren. 01:00:25.530 --> 01:00:28.170 Das ist das Problem, was ich Ihnen gerade dargestellt habe. 01:00:28.770 --> 01:00:35.150 Zwei Polynome p und q, beide haben n plus 1 Koeffizienten und ich 01:00:35.150 --> 01:00:38.910 möchte die 2n plus 1 Koeffizienten des Produktpolynoms ausrechnen. 01:00:40.150 --> 01:00:41.390 Dann habe ich das Produkt berechnet. 01:00:43.070 --> 01:00:46.350 Und jetzt ist die Idee, ich weiß, dass diese Operation hier braucht 01:00:46.350 --> 01:00:50.110 Größenordnung n² Operation, wenn ich es direkt mache mit dem naiven 01:00:50.110 --> 01:00:50.610 Ansatz. 01:00:50.610 --> 01:00:54.310 Jetzt kann ich Polynome auf unterschiedliche Art und Weise darstellen. 01:00:55.370 --> 01:00:59.670 Und die Idee bei der Fourier-Transformation ist, ich stelle das 01:00:59.670 --> 01:01:05.310 Polynom dar durch die Werte an einer Reihe von Werten von x. 01:01:05.850 --> 01:01:10.330 Also ich werte das Polynom aus, in diesem Fall, weil ich 2n plus 1 01:01:10.330 --> 01:01:13.890 Koeffizienten brauche, an 2n plus 1 01:01:17.030 --> 01:01:17.710 Position. 01:01:18.930 --> 01:01:24.910 Ich brauche diese Koeffizienten eines Polynoms n² und ich mache jetzt, 01:01:24.970 --> 01:01:30.250 also 2n², und das mache ich eine Wertedarstellung für 2n plus 1 01:01:30.250 --> 01:01:31.130 Punkte. 01:01:31.570 --> 01:01:32.930 x0 bis x2n. 01:01:34.330 --> 01:01:36.650 Meines Polynoms p und meines Polynoms q. 01:01:37.310 --> 01:01:42.850 Wenn ich eine solche Darstellung habe, der beiden Polynome, an diesen 01:01:42.850 --> 01:01:48.270 Positionen x0 bis x2n, dann ist die Berechnung des Produkts ganz 01:01:48.270 --> 01:01:48.710 einfach. 01:01:49.170 --> 01:01:51.830 Jetzt ist das hier meine Problemstellung. 01:01:52.050 --> 01:01:55.590 Ich möchte 2 Polynome modifizieren. 01:01:56.150 --> 01:01:57.830 Ich habe sie eindeutig dargestellt. 01:01:58.990 --> 01:02:02.590 Die Darstellung von Polynomen an 2n plus... 01:02:02.590 --> 01:02:10.410 an diesen Punkten ist eindeutig und ich kann das jetzt modifizieren, 01:02:11.290 --> 01:02:15.830 bekomme ein Polynom oder eine Wertedarstellung raus. 01:02:16.610 --> 01:02:21.910 Produkte der Werte, also R von x0 ist gerade p von x0 mal q von x0. 01:02:23.050 --> 01:02:28.870 Das O3 hier, diese Operation, der Aufwand dafür, sind gerade 2n plus 1 01:02:28.870 --> 01:02:29.750 Multiplikation. 01:02:31.470 --> 01:02:32.890 Das geht in linearer Zeit. 01:02:34.150 --> 01:02:37.590 Und dann muss ich, wenn ich sage, die Wertedarstellung reicht mir 01:02:37.590 --> 01:02:40.730 nicht, muss ich wieder auf die Komponentendarstellung kommen. 01:02:40.730 --> 01:02:46.590 Hier zurückzulaufen ist eine Interpolation. 01:02:47.290 --> 01:02:50.190 Aus einer Wertedarstellung eine Komponentendarstellung zu gewinnen, 01:02:50.630 --> 01:02:52.570 ist möglich. 01:02:52.730 --> 01:02:57.770 Ich habe 2n plus 1 Punkte, daraus kann ich eindeutig ein Polynom in 2n 01:02:57.770 --> 01:03:05.010 gradis erzeugen, dass genau diese 2n plus 1 Werte hat. 01:03:06.320 --> 01:03:07.810 Das ist eine eindeutige Darstellung. 01:03:07.810 --> 01:03:11.110 Eine besondere Transformation von Wertedarstellung auf 01:03:11.770 --> 01:03:12.150 Komponentendarstellung. 01:03:13.770 --> 01:03:16.070 Kennen Sie aus der Mathematik vielleicht noch. 01:03:17.390 --> 01:03:26.990 Und der Aufwand für O1 und O4 der ist, das ist nun die Behauptung, n 01:03:26.990 --> 01:03:30.170 log n, wenn ich die schnelle Fourier-Transformation dafür nehme. 01:03:30.270 --> 01:03:35.950 Wenn ich also spezielle Werte x0 bis x2n nehme, dann kann ich diese 01:03:35.950 --> 01:03:43.550 Transformation O1 und O4 jeweils sehr schnell machen mit Aufwand n log 01:03:43.550 --> 01:03:43.790 n. 01:03:44.730 --> 01:03:49.590 Der naive Aufwand wäre ein Polynom an 2n Stellen oder 2n plus 1 01:03:49.590 --> 01:03:51.930 Stellen auswerten, jeweils Aufwand n. 01:03:52.770 --> 01:03:54.150 Dann habe ich quadratischen Aufwand. 01:03:54.370 --> 01:03:57.170 Dann wäre O1 und O4 jeweils quadratischer Aufwand. 01:03:57.690 --> 01:03:59.190 O3 ist linearer Aufwand. 01:03:59.710 --> 01:04:03.550 Naja, dann habe ich halt insgesamt wieder quadratischen Aufwand. 01:04:03.550 --> 01:04:04.410 Das bringt mir nichts. 01:04:04.930 --> 01:04:07.090 Aber die Tatsache, dass ich diese Transformation von 01:04:07.090 --> 01:04:10.790 Koeffizientendarstellung in Wertedarstellung schnell machen kann mit 01:04:10.790 --> 01:04:15.150 einer Fourier-Transformation für spezielle Werte dieser x0 bis x2n, 01:04:15.790 --> 01:04:22.110 führt dann zu einer Möglichkeit, zwei Polynome zu modifizieren inside 01:04:22.110 --> 01:04:22.790 n log n. 01:04:24.170 --> 01:04:30.210 Und das ist ein sehr interessantes Ergebnis, was dann auch angewendet 01:04:30.210 --> 01:04:32.190 werden kann in verschiedenen anderen Bereichen. 01:04:33.070 --> 01:04:37.470 Ich habe also hier meine diskrete Fourier-Transformation zu berechnen. 01:04:38.630 --> 01:04:42.390 Ich weiß gar nicht, ob die 3.13, warum eigentlich da noch die 13 01:04:42.390 --> 01:04:42.730 steht. 01:04:42.830 --> 01:04:45.090 Ich habe die Nummerierung eigentlich gar nicht durchgezogen durch die 01:04:45.090 --> 01:04:45.790 anderen Folien. 01:04:45.950 --> 01:04:48.510 Müssen wir mal überprüfen, ob die Nummerierung eigentlich noch so 01:04:48.510 --> 01:04:49.190 erforderlich ist. 01:04:49.790 --> 01:04:51.050 Nennen wir sie einfach 3.13. 01:04:51.170 --> 01:04:51.590 Warum nicht? 01:04:51.910 --> 01:04:52.370 Schöne Nummer. 01:04:53.650 --> 01:04:59.270 Also, ist also so, bei der diskreten Fourier-Transformation wertet man 01:04:59.270 --> 01:05:02.290 ein Polynom an geeignet gewählten Stellen aus, an den Enten 01:05:02.290 --> 01:05:02.990 -Einheitswurzeln. 01:05:03.270 --> 01:05:06.750 Ist Ihnen das Konzept bekannt, der Enten-Einheitswurzel? 01:05:08.670 --> 01:05:09.810 Sie kennen das? 01:05:10.030 --> 01:05:10.770 Aha, zum Teil. 01:05:11.530 --> 01:05:11.650 Okay. 01:05:12.630 --> 01:05:13.230 Nur zum Teil. 01:05:13.810 --> 01:05:17.590 Viele, die zuhören, irgendwann in der Cyberwelt, die kennen es 01:05:17.590 --> 01:05:18.150 vielleicht noch nicht. 01:05:19.090 --> 01:05:23.050 Es geht um Nullstellen eines Polynoms x hoch n minus 1. 01:05:24.450 --> 01:05:28.590 Beliebiges Polynom, deswegen Einheitswurzel, Wurzel aus 1, bzw. 01:05:29.650 --> 01:05:35.550 ich muss Elemente haben, sodass die Ente-Wurzel aus 1 möchte ich gerne 01:05:35.550 --> 01:05:36.030 berechnen. 01:05:37.410 --> 01:05:40.110 Das wäre x in dem Fall, damit x hoch n gleich 1 ist. 01:05:40.450 --> 01:05:44.350 Sie haben sofort eine Nullstelle dieses Polynoms, x gleich 1 ist 01:05:44.350 --> 01:05:45.050 natürlich eine Nullstelle. 01:05:45.310 --> 01:05:45.890 Ganz einfach. 01:05:46.630 --> 01:05:50.850 1 hoch n ist 1, also für x gleich 1 ist das Polynom 0. 01:05:52.050 --> 01:05:56.930 Das interessante ist, es kann Mehrwerte geben, als nur die 1. 01:05:58.550 --> 01:06:03.130 Und die alle rauszufinden, und es ist tatsächlich so, dass man über 01:06:03.130 --> 01:06:08.510 einem geeigneten Körper N solche Einheitswurzeln finden kann. 01:06:10.490 --> 01:06:14.570 Also, jede Nullstelle, zunächst mal wissen Sie nicht, wie viele das 01:06:14.570 --> 01:06:20.030 sind, des Polynoms x hoch n minus 1 über einem geeigneten Körper, über 01:06:20.030 --> 01:06:23.350 c, eigentlich müsste ich hier einen Strich rein machen, Körper der 01:06:23.350 --> 01:06:26.890 komplexen Zahlen, oder über einem endlichen Körper. 01:06:28.430 --> 01:06:30.730 Ist also eine N-Einheitswurzel. 01:06:31.490 --> 01:06:35.450 Und eine N-Einheitswurzel Omega, die nennen wir jetzt immer so, heißt 01:06:35.450 --> 01:06:43.670 primitiv, genau dann, wenn für alle Potenzen von Omega, die kleiner 01:06:43.670 --> 01:06:48.750 sind als n, gilt Omega hoch j ist ungleich 1. 01:06:51.450 --> 01:06:57.490 Das heißt, ich muss tatsächlich Omega hoch n berechnen, damit da 1 01:06:57.490 --> 01:06:58.110 rauskommt. 01:06:58.530 --> 01:07:01.310 Wenn ich eine kleinere Potenz nehme, habe ich einen Wert, der ist 01:07:01.310 --> 01:07:02.250 ungleich 1. 01:07:04.790 --> 01:07:08.610 Und die heißt deswegen primitiv, weil ich auf dieser primitiven, man 01:07:08.610 --> 01:07:13.150 könnte auch sagen, atomar, alle anderen im Prinzip erzeugen kann. 01:07:13.590 --> 01:07:17.430 Wenn nämlich für alle j aus n minus 1 gilt, Omega hoch j ist ungleich 01:07:17.430 --> 01:07:24.110 1, dann sind also alle diese Omega hoch j im Prinzip auch in der 01:07:24.110 --> 01:07:24.710 Einheitswurzel. 01:07:26.030 --> 01:07:29.730 Weil ich sie ja nur genügend oft mit sich selbst modifizieren muss, 01:07:30.050 --> 01:07:32.830 damit ein Vielfaches von n im Exponent entsteht. 01:07:33.910 --> 01:07:34.750 Und dann ist es 1. 01:07:36.130 --> 01:07:37.230 Also ist das ganz einfach. 01:07:37.850 --> 01:07:42.490 Ich muss also nur eine Einheitswurzel finden, die primitiv ist, aus 01:07:42.490 --> 01:07:45.850 der kann ich alle anderen Einheitswurzeln, alle anderen Nullstellen, 01:07:45.850 --> 01:07:48.590 die über diesem Körper möglich sind, erzeugen. 01:07:49.790 --> 01:07:51.670 Also, das ist genau dieses Lemma. 01:07:52.210 --> 01:07:55.890 Wenn Omega eine primitive Enteneinheitswurzel ist, so ist Omega hoch i 01:07:55.890 --> 01:07:58.690 mit i aus n die Menge aller Enteneinheitswurzeln. 01:07:59.250 --> 01:08:02.370 Der Beweis ist natürlich trivial, weil, das hatte ich Ihnen gerade 01:08:02.370 --> 01:08:07.170 schon angedeutet, wenn Omega hoch i, wenn ich das mir hernehme, das 01:08:07.170 --> 01:08:08.390 weiß ich, das ist ungleich 1. 01:08:08.870 --> 01:08:13.650 Aber Omega hoch i hoch n ist natürlich Omega hoch n hoch i und das ist 01:08:13.650 --> 01:08:14.110 gleich 1. 01:08:14.370 --> 01:08:14.930 Ganz einfach. 01:08:15.610 --> 01:08:17.410 Sofort zu sehen. 01:08:18.210 --> 01:08:25.590 Wenn wir uns hier Beispiele angucken, für das Polynom x² minus 1 01:08:26.570 --> 01:08:31.350 wissen wir, wir haben zwei verschiedene Werte im ganz normalen 01:08:31.350 --> 01:08:33.490 Zahlbereich, nämlich minus 1 und 1. 01:08:34.550 --> 01:08:37.190 Also ist natürlich klar, für eine gerade Potenz habe ich natürlich 01:08:37.190 --> 01:08:39.350 gerade immer positive und negative Werte. 01:08:40.550 --> 01:08:45.090 Wenn ich jetzt die vierten Einheitswurzel haben möchte, dann brauche 01:08:45.090 --> 01:08:48.490 ich dazu noch die Wurzel aus minus 1. 01:08:51.410 --> 01:08:54.370 Das heißt, Wurzel aus minus 1 wissen wir ist i. 01:08:55.230 --> 01:08:57.270 Dann kann ich aber minus i auch noch dazunehmen. 01:08:58.670 --> 01:09:00.630 i mit i modifiziert gibt minus 1. 01:09:01.290 --> 01:09:03.450 Dann habe ich noch minus i und ich habe 1. 01:09:04.370 --> 01:09:11.390 Und i, minus 1 und minus i sind eben alles Potenzen von i, die 01:09:11.390 --> 01:09:12.250 ungleich 1 sind. 01:09:14.650 --> 01:09:17.410 Dann die achten Einheitswurzel und so weiter, das wäre dann Wurzel aus 01:09:17.410 --> 01:09:18.930 i, was immer das ist. 01:09:19.390 --> 01:09:26.230 In bestimmten endlichen Körpern gibt es solche Wurzeln aus, oder gibt 01:09:26.230 --> 01:09:28.590 es solche primitiven Einheitswurzeln. 01:09:29.410 --> 01:09:32.650 Das hat was mit Körpertheorien zu tun, will ich jetzt auch im 01:09:32.650 --> 01:09:33.770 Einzelnen nicht drauf eingehen. 01:09:33.930 --> 01:09:37.850 Das sind also Dinge, die gelten in endlichen Körpern oder eben auch im 01:09:37.850 --> 01:09:39.010 Bereich der komplexen Zahlen. 01:09:39.950 --> 01:09:42.230 Da kann man genau solche Enten-Einheitswurzeln finden. 01:09:43.590 --> 01:09:46.530 Und in diesem Fall wäre also Wurzel-i hier die primitive Enten 01:09:46.530 --> 01:09:49.930 -Einheitswurzel und dann entsprechend die Potenzen sind hier drunter 01:09:49.930 --> 01:09:50.350 geschrieben. 01:09:50.790 --> 01:09:54.910 Das wären dann alle meine Enten-Einheitswurzeln in dem Fall. 01:09:56.010 --> 01:09:58.850 Und was ist jetzt das Schöne dieser Enten-Einheitswurzeln? 01:09:59.370 --> 01:10:05.290 Sie sehen hier schon mal gewisse Dinge, dass Sie hier einen Bereich 01:10:05.290 --> 01:10:13.630 haben, Wurzel-i bis minus 1 und der tritt hier nochmal auf, nur 01:10:13.630 --> 01:10:15.690 jeweils modifiziert mit minus 1. 01:10:18.290 --> 01:10:23.530 Das heißt, eigentlich muss ich ja nur die Hälfte kennen. 01:10:24.810 --> 01:10:27.790 Dann kann ich die andere Hälfte einfach nur negativ. 01:10:28.930 --> 01:10:30.350 Das ist ja ganz einfach. 01:10:31.930 --> 01:10:36.570 Minus 1 mal Omega, minus 1 mal Omega-Quadrat und so weiter. 01:10:37.910 --> 01:10:40.530 Das heißt, ich muss gar nicht, wenn ich alle Enten-Einheitswurzeln 01:10:40.530 --> 01:10:46.130 haben möchte, gar nicht Omega bis Omega hoch n berechnen, oder Omega 01:10:46.130 --> 01:10:51.410 hoch n minus 1, sondern es reicht, die Hälfte zu berechnen. 01:10:51.450 --> 01:10:53.350 Und die anderen bekomme ich durch Negation. 01:10:54.710 --> 01:10:58.650 Und das ist ein wesentlicher Schritt bei der schnellen Fourier 01:10:58.650 --> 01:11:02.450 -Transformation, dass man sagt, ich muss gar nicht unbedingt alle, 01:11:03.410 --> 01:11:09.790 also wenn ich etwas machen will, alle Einheitswurzeln, die sind gar 01:11:09.790 --> 01:11:10.690 nicht so unterschiedlich. 01:11:11.470 --> 01:11:14.450 Die Hälfte unterscheidet sich von der ersten, die zweite Hälfte 01:11:14.450 --> 01:11:17.430 unterscheidet sich von der ersten nur dadurch, dass ich minus 1 01:11:21.110 --> 01:11:22.350 nur negieren muss. 01:11:23.530 --> 01:11:25.390 Jetzt sind hier ein paar Eigenschaften angegeben. 01:11:25.830 --> 01:11:28.090 Es ist klar, Omega hoch n halbe ist immer minus 1. 01:11:28.550 --> 01:11:30.030 Das ist sofort klar. 01:11:30.610 --> 01:11:32.790 Omega hoch n halber Quadrat ist ja Omega hoch n. 01:11:33.790 --> 01:11:36.650 Und für alle i aus n halber, das ist das, was ich gerade eben gesagt 01:11:36.650 --> 01:11:41.190 habe, Omega hoch n halber plus i ist gerade minus Omega hoch i, weil 01:11:41.190 --> 01:11:42.750 Omega hoch n halber halb minus 1 ist. 01:11:43.550 --> 01:11:44.790 Ganz einfache Aussage. 01:11:45.750 --> 01:11:49.910 Omega Quadrat ist auch eine Einheitswurzel, auch eine primitive 01:11:49.910 --> 01:11:54.110 Einheitswurzel, aber nicht eine primitive Ente, sondern primitive n 01:11:54.110 --> 01:11:56.030 halbte Einheitswurzel. 01:11:57.370 --> 01:12:01.350 Sofort kriegt man die Idee, wenn ich etwas von n auf n halbe 01:12:01.350 --> 01:12:05.250 reduzieren kann, dann muss ich doch etwas irgendwie mit die Weide an 01:12:05.250 --> 01:12:06.570 Conquer rekursiv machen können. 01:12:07.550 --> 01:12:11.050 Und das ist genau das, was hier dann gemacht wird. 01:12:12.830 --> 01:12:19.510 Dann ist es so, wenn ich ein Polynom berechnen möchte für alle Enten 01:12:19.510 --> 01:12:23.050 -Einheitswurzeln, kann ich das im Prinzip so darstellen, wie das hier 01:12:23.050 --> 01:12:23.730 gemacht wird. 01:12:23.810 --> 01:12:27.270 Das hilft uns noch nicht sehr viel auf dem Weg zu der schnellen 01:12:27.270 --> 01:12:29.070 Fourier -Transformation, nur mal zur Darstellung. 01:12:29.830 --> 01:12:32.630 Ich habe also hier meine Koeffizienten an 0 bis an n-1. 01:12:32.750 --> 01:12:36.150 Jetzt möchte ich die meinetwegen nur an den Enten-Einheitswurzeln 01:12:36.150 --> 01:12:36.930 auswerten. 01:12:37.910 --> 01:12:43.410 Dann würde ich also eine primitive Ente-Einheitswurzel Omega nehmen. 01:12:45.370 --> 01:12:49.450 Würde die mit Omega hoch für Omega hoch 0 auswerten. 01:12:49.710 --> 01:12:50.870 Das werden also hier alles 1. 01:12:50.870 --> 01:12:53.990 Dann für Omega hoch 1. 01:12:54.330 --> 01:12:57.030 Dann hätte ich diese im Prinzip alle zu berechnen. 01:12:57.130 --> 01:13:01.110 Also a0 mal 1, a1 mal Omega, a2 mal Omega-Quadrat und so weiter. 01:13:01.250 --> 01:13:03.570 Diese Zeile mal entsprechend in die jeweiligen Spalten. 01:13:04.130 --> 01:13:09.590 Und ich hätte also diese Matrix im Prinzip als Darstellung der 01:13:09.590 --> 01:13:15.210 diskreten Fourier-Transformation, bei der ich ein Polynom für alle 01:13:15.210 --> 01:13:17.410 Enten -Einheitswurzeln auswerte. 01:13:17.530 --> 01:13:18.590 Das ist also diese Darstellung. 01:13:18.590 --> 01:13:22.250 Die liefert mir y0 bis yn-1. 01:13:22.510 --> 01:13:35.670 Die Werte also von also y0 bis yn-1 sind gerade die yi ist also gleich 01:13:36.870 --> 01:13:41.970 p von Omega hoch i. 01:13:43.350 --> 01:13:47.990 Das ist jeweils der Wert an der Enten-Einheitswurzel. 01:13:50.840 --> 01:13:51.160 So. 01:13:52.140 --> 01:13:53.220 Das sollte ein y sein. 01:13:54.400 --> 01:14:00.340 Und das Interessante ist, die Inversetransformation kann ich ganz 01:14:00.340 --> 01:14:01.100 ähnlich darstellen. 01:14:02.840 --> 01:14:08.420 Wenn ich diese Werte habe, y0 bis yn-1, dann kann ich die 01:14:08.420 --> 01:14:13.120 Koeffizienten an 0 bis yn-1 bekommen, indem ich eine ähnliche 01:14:13.120 --> 01:14:21.900 Operation ausführe, nämlich gerade die Auswertung mache für Omega hoch 01:14:21.900 --> 01:14:22.620 minus 1. 01:14:23.440 --> 01:14:28.260 Also praktisch die Inversen der Enten-Einheitswurzel. 01:14:28.500 --> 01:14:32.620 Da ich mich in Körpern bewege, habe ich zu jedem Element auch ein 01:14:32.620 --> 01:14:33.020 Inverse. 01:14:33.160 --> 01:14:36.120 Ich brauche also nur die Inversen der Enten-Einheitswurzel zu nehmen. 01:14:37.480 --> 01:14:41.160 Mache diese Transformation, muss noch mit 1 durch n modifizieren, also 01:14:41.160 --> 01:14:45.740 durch n dividieren, und bekomme dann gerade jeweils die Koeffizienten. 01:14:46.140 --> 01:14:48.660 Kann man sich ausrechnen, gehe ich nicht im Einzelnen darauf ein, 01:14:48.740 --> 01:14:50.480 wollte ich nur einfach so darstellen. 01:14:51.500 --> 01:14:55.040 Und man sieht eben sofort, dann ist offensichtlich, dass eine 01:14:55.040 --> 01:15:00.500 gleichartige Transformation, und das heißt, ich habe in beiden 01:15:00.500 --> 01:15:03.520 Richtungen von Koeffizienten-Darstellung auf Werte-Darstellung und von 01:15:03.520 --> 01:15:06.600 Werte -Darstellung auf Koeffizienten-Darstellung nur eine solche 01:15:06.600 --> 01:15:08.660 diskrete Fourier-Transformation auszuführen. 01:15:10.420 --> 01:15:12.940 So, und jetzt ist die Frage, wie kann ich die diskrete Fourier 01:15:12.940 --> 01:15:14.640 -Transformation schnell machen? 01:15:15.980 --> 01:15:21.640 Und dazu verwende ich jetzt diese Eigenschaften, die ich angegeben 01:15:21.640 --> 01:15:23.520 habe, in einer sinnvollen Art und Weise. 01:15:24.780 --> 01:15:30.060 Ich nehme mir mein Polynom her, p von x, das möchte ich auswerten an 01:15:30.660 --> 01:15:32.180 den Enten-Einheitswurzeln. 01:15:34.440 --> 01:15:38.200 Beziehungsweise in dem Fall, ja, genau an den Enten-Einheitswurzeln. 01:15:39.200 --> 01:15:44.680 Und jetzt habe ich also, das teile ich jetzt einfach auf, ich möchte 01:15:44.680 --> 01:15:47.460 das Ganze wie üblich rekursiv machen. 01:15:48.200 --> 01:15:50.280 Ich teile auf in zwei Polynomen. 01:15:51.600 --> 01:15:54.700 Anders als ich das vorhin gemacht habe bei der Parallelisierung. 01:15:55.780 --> 01:16:02.780 In diesem Fall teile ich auf in ein Polynom, wo ich nur die geraden 01:16:02.780 --> 01:16:08.580 Koeffizienten nehme, und ein anderes Polynom, wo ich nur die ungeraden 01:16:08.580 --> 01:16:09.460 Koeffizienten nehme. 01:16:10.980 --> 01:16:16.720 Das heißt, ich habe hier meine Reihe von Koeffizienten, das nehme ich 01:16:16.720 --> 01:16:24.900 für ein Polynom, nehme ich das Element, dann das Element, dann nehme 01:16:24.900 --> 01:16:27.940 ich hier noch irgendein weiteres, das Element, und dann dahinten 01:16:27.940 --> 01:16:28.780 vielleicht noch das Element. 01:16:29.720 --> 01:16:33.340 Und die nächsten kommen dann von da. 01:16:33.620 --> 01:16:37.780 Das Element, das Element, das Element, und so weiter. 01:16:39.120 --> 01:16:40.880 Das heißt, ich mache so eine Verschränkung. 01:16:42.180 --> 01:16:45.480 Oder wenn ich meine, ich nehme das einfach so als, wenn ich meine 01:16:45.480 --> 01:16:49.180 Finger ineinander lege, das sind jetzt die Fingerspitzen, die 01:16:49.180 --> 01:16:52.320 einzelnen Koeffizienten, dann ziehe ich die einfach so auseinander, 01:16:53.100 --> 01:16:55.800 und ich habe die geraden Position und die ungeraden Position. 01:16:58.760 --> 01:17:01.340 Und das ist im Wesentlichen die Operation, die ich hier mache. 01:17:02.360 --> 01:17:07.500 Meine beiden Polynome a0 plus a2x² plus a4xo4 und so weiter, 01:17:07.780 --> 01:17:13.020 beziehungsweise a1 plus a3x² plus a5xo4 und so weiter. 01:17:16.000 --> 01:17:17.460 Das ist Pu von x². 01:17:19.140 --> 01:17:23.860 Und wenn ich das Polynom jetzt bilden möchte, dann muss ich nur Pu von 01:17:23.860 --> 01:17:29.740 x² mit x modifizieren, um die richtigen Polynome a, i, x, o, i zu 01:17:29.740 --> 01:17:30.040 bekommen. 01:17:30.400 --> 01:17:32.840 Ich habe ja hier a3x² stehen. 01:17:33.100 --> 01:17:35.840 Da muss aber a3x³ im Polynom drinstehen. 01:17:35.940 --> 01:17:39.500 Deswegen Pu von x² mal x. 01:17:40.620 --> 01:17:43.600 Und jetzt habe ich also das, was ich rekursiv machen möchte. 01:17:44.560 --> 01:17:52.500 Ich muss jetzt zwei Polynome auswerten, Pg und Pu, jeweils für x². 01:17:54.060 --> 01:17:59.140 Und das sind Polynome, die haben das Polynome vom Grad in halbe. 01:18:01.940 --> 01:18:08.620 Ich habe also hier im Prinzip jetzt zwei Probleme der Größe in halbe. 01:18:09.520 --> 01:18:11.280 Weil ich für x² auswerte. 01:18:12.760 --> 01:18:17.920 Ich muss ja nur x² bis x² hoch in halbe auswerten. 01:18:19.100 --> 01:18:21.640 Das ist ja einfach. 01:18:22.660 --> 01:18:24.820 Oder es ist halt dann auch ein rekursiver Ansatz. 01:18:25.560 --> 01:18:27.000 Und jetzt müssen wir gucken, wie können wir das machen. 01:18:27.100 --> 01:18:28.800 Ich kann natürlich das rekursiv berechnen. 01:18:29.660 --> 01:18:33.800 Das ist ja der übliche rekursive Ansatz. 01:18:34.320 --> 01:18:42.460 Und wenn ich die beiden berechnet habe, dann muss ich jetzt für jede 01:18:43.460 --> 01:18:46.940 Einheitswurzel x das ausrechnen. 01:18:48.140 --> 01:18:52.160 Ich habe also das berechnet für die quadratischen Einheitswurzeln. 01:18:52.600 --> 01:18:55.340 Und dann muss ich diese Werte nochmal ausrechnen. 01:18:56.500 --> 01:19:01.900 Das heißt, für P von w hoch 0 muss ich Pg von w hoch 0 ausrechnen plus 01:19:01.900 --> 01:19:03.660 Pu von w hoch 0. 01:19:04.480 --> 01:19:09.860 Beziehungsweise P von w1, Pg von w² plus Pu von w² mal w. 01:19:10.540 --> 01:19:12.360 Oder ja nicht w, Omega natürlich jeweils. 01:19:13.480 --> 01:19:18.920 Entsprechend P von Omega hoch in halbe minus 1 ist Pg von Omega hoch 01:19:18.920 --> 01:19:25.440 in halbe Pg von Omega hoch in halbe mal Omega hoch in halbe minus 1. 01:19:27.960 --> 01:19:35.280 Das ist also genau ein Prinzip dieser Termen jeweils für die einzelnen 01:19:35.280 --> 01:19:36.520 Einheitswurzeln angewandt. 01:19:37.800 --> 01:19:41.360 Dann habe ich das gemacht bis Omega hoch in halbe minus 1. 01:19:42.100 --> 01:19:44.420 Ich muss natürlich für die restlichen das auch noch berechnen. 01:19:45.500 --> 01:19:51.860 Und das interessante ist, hier nutze ich jetzt aus die Tatsache, dass 01:19:52.700 --> 01:20:00.660 Omega hoch in halbe plus i ist gleich minus Omega hoch i. 01:20:03.440 --> 01:20:07.880 Für Omega hoch in halbe muss ich nur Pg von Omega hoch 0 minus Pu von 01:20:07.880 --> 01:20:09.100 Omega hoch 0 auswählen. 01:20:11.540 --> 01:20:16.360 Ich habe ja hier Omega hoch, da tritt das also auf, das Omega hoch 1 01:20:16.360 --> 01:20:18.080 mit Omega hoch in halbe minus 1. 01:20:19.540 --> 01:20:23.880 Das Minus ist gerade das entsprechende Omega hoch in halbe plus 0. 01:20:25.560 --> 01:20:30.180 Und diese Werte hier habe ich ja alle schon mal berechnet gehabt. 01:20:30.320 --> 01:20:35.540 Das heißt, ich brauche ja jetzt nur das, was ich hier addiert habe, 01:20:35.620 --> 01:20:39.000 muss ich hier nur subtrahieren. 01:20:40.220 --> 01:20:44.940 Das heißt, ich muss diese Multiplikationen meines ungeraden Polynoms 01:20:44.940 --> 01:20:50.800 mit Omega hoch in halbe mit Omega, Omega hoch irgendwas, Omega hoch j, 01:20:51.440 --> 01:20:53.500 muss ich nur in der oberen Hälfte machen. 01:20:54.000 --> 01:20:58.420 Und hier unten muss ich diese Terme für diese Terme nicht nochmal in 01:20:58.420 --> 01:20:59.420 die Multiplikationsspende hier. 01:21:01.020 --> 01:21:03.540 Denn eigentlich ist ja der Aufwand, wenn wir uns das anschauen, 01:21:03.620 --> 01:21:05.180 Entschuldigung, ich mach das direkt hier. 01:21:05.660 --> 01:21:09.280 Wenn ich mir den Aufwand angucke, dann habe ich jeweils diesen 01:21:09.280 --> 01:21:10.400 Ausdruck hier zu bewerten. 01:21:10.640 --> 01:21:15.460 Das ist eine Multiplikation plus eine Addition. 01:21:17.420 --> 01:21:21.220 Und wenn ich mir das jetzt hier insgesamt anschaue, dann habe ich hier 01:21:21.220 --> 01:21:25.380 natürlich n halbe Multiplikation bzw. 01:21:25.980 --> 01:21:29.620 sogar nur n halbe minus 1, weil ich da nichts multiplizieren muss. 01:21:31.020 --> 01:21:34.360 Plus natürlich n halbe Addition. 01:21:35.020 --> 01:21:40.480 Und hier habe ich 0 Multiplikation plus n halbe Addition. 01:21:40.840 --> 01:21:43.160 Ich spare mir hier die Hälfte der Multiplikation. 01:21:45.880 --> 01:21:50.460 Und das heißt, wenn ich mir das jetzt hier nochmal allgemein angucke, 01:21:51.120 --> 01:21:54.720 insgesamt, sehen Sie gleich hier drin, da steht es nochmal, dass also 01:21:54.720 --> 01:22:00.080 hier n halbe minus 1 Multiplikation, n Addition, Subtraktion, Schritt 01:22:00.080 --> 01:22:04.400 3, den ich gerade dargestellt habe, wenn ich mir die anderen Schritte 01:22:04.400 --> 01:22:09.020 angucke, der erste Schritt war ja diese Perfect Unshuffle, was ich 01:22:09.020 --> 01:22:10.600 Ihnen gerade dargestellt habe mit meinen Fingern. 01:22:11.540 --> 01:22:14.120 Ein Perfect Shuffle, wissen Sie alle, wenn Sie zwei Kartenstapel 01:22:14.120 --> 01:22:18.640 haben, Sie wollen die perfekt mischen, dann werden die genau 01:22:18.640 --> 01:22:19.560 ineinander verschränkt. 01:22:21.100 --> 01:22:24.420 Und Perfect Unshuffle ist eben genau die Gegenteil der Operation, 01:22:24.640 --> 01:22:25.840 nicht ganz so leicht auszuführen. 01:22:26.640 --> 01:22:27.760 Einfach alle auseinanderziehen. 01:22:28.480 --> 01:22:30.240 Algorithmisch schon genauso leicht auszuführen. 01:22:30.760 --> 01:22:35.120 Sie müssen halt nur, also das Perfect Unshuffle in dieser Richtung 01:22:35.120 --> 01:22:38.980 machen, da ziehen Sie jede zweite Position raus, nebeneinander, und 01:22:38.980 --> 01:22:41.340 bei Perfect Shuffle verschränken Sie die miteinander. 01:22:42.480 --> 01:22:45.020 Das ist eine ganz wichtige Operation, die man an vielen Stellen 01:22:45.020 --> 01:22:49.240 findet, in Algorithmen, diese Shuffle- und Unshuffle-Operation. 01:22:50.600 --> 01:22:53.020 Werden Sie noch später beim Sortierverfahren auch nochmal 01:22:53.020 --> 01:22:53.420 kennenlernen. 01:22:54.760 --> 01:22:58.100 Dann habe ich also natürlich den Aufwand für die rekursive Ausführung 01:22:58.100 --> 01:22:59.260 der schnellen Fourier-Transformation. 01:22:59.260 --> 01:23:03.120 Und wenn ich mir jetzt anschaue, den Aufwand insgesamt abgeschätzt, 01:23:03.380 --> 01:23:07.520 die Anzahl der Multiplikationen für die Fourier-Transformation nach 01:23:07.520 --> 01:23:11.860 diesem Verfahren ist also dann zweimal, weil ich es ja nicht parallel 01:23:11.860 --> 01:23:16.800 mache, der Aufwand für die Auswertung eines Polynoms halben Grades, 01:23:17.740 --> 01:23:22.660 das war diese Auswertung von Pu und Pg, plus die n halben minus 1 01:23:23.260 --> 01:23:26.320 Multiplikationen, und das gleiche hier mit der Anzahl der Additionen. 01:23:26.320 --> 01:23:35.360 Und damit habe ich bei den Multiplikationen etwa n halbe mal log n und 01:23:35.360 --> 01:23:40.120 bei den Additionen habe ich n mal log n als Aufwand, was ich hier 01:23:40.120 --> 01:23:43.040 nicht einst nicht explizit zeige, sondern man sieht das relativ 01:23:43.040 --> 01:23:49.320 schnell, wenn ich eine solche rekursive Darstellung habe, über eine 01:23:49.320 --> 01:23:52.200 Baumstruktur jeweils schön aufgeteilt. 01:23:52.760 --> 01:23:57.720 Der Aufwand in jeder Ebene ist genau n, das steht da, Größenordnung n, 01:23:58.060 --> 01:24:03.000 log n Schichten, jeweils Aufwand n, habe ich also insgesamt Aufwand n 01:24:03.000 --> 01:24:04.140 mal log n, sieht man sofort. 01:24:05.780 --> 01:24:09.060 Und insgesamt also ein Aufwand n log n für die schnelle 01:24:09.060 --> 01:24:09.660 Polynomialtransformation. 01:24:10.920 --> 01:24:14.400 Geht aber eben nur durch Ausnutzung dieser Eigenschaften, dass ich nur 01:24:14.400 --> 01:24:18.940 die Hälfte oder für die Hälfte der Werte tatsächlich diese 01:24:18.940 --> 01:24:21.040 Multiplikation machen muss, für die andere Hälfte brauche ich es 01:24:21.040 --> 01:24:23.760 nicht, dann muss ich nur den Wert, den ich vorberechnet habe, negieren 01:24:23.760 --> 01:24:24.420 und ich bin fertig. 01:24:25.680 --> 01:24:28.820 Und damit habe ich hier diesen Satz, schnelle Polynomialtransformation 01:24:28.820 --> 01:24:30.920 benötigt O von n log n arithmetische Operation. 01:24:32.360 --> 01:24:37.200 Und wenn wir uns jetzt anschauen, was da eigentlich abgelaufen ist von 01:24:37.200 --> 01:24:40.200 der Struktur des Algorithmus, dann kommt man zu einer sehr 01:24:40.200 --> 01:24:41.080 interessanten Struktur. 01:24:42.040 --> 01:24:46.580 Nämlich zu dem sogenannten Butterfly-Netzwerk, das ist hier 01:24:46.580 --> 01:24:49.280 dargestellt, für n gleich 8. 01:24:52.120 --> 01:24:55.340 Hier sehen Sie die allgemeine Struktur in diesem Bild. 01:24:56.340 --> 01:25:01.200 Ich möchte berechnen, die Fourier-Transformation für Grad n. 01:25:02.880 --> 01:25:07.460 Ich habe also Polynomialgrad n-1, also n Koeffizienten. 01:25:09.500 --> 01:25:14.460 Und dann muss ich für n Werte das auswerten. 01:25:15.680 --> 01:25:18.780 Und da ist jetzt genau dieser Trick, dass ich eben die Auswertung 01:25:18.780 --> 01:25:20.780 mache für pg und für pu. 01:25:21.860 --> 01:25:25.640 Und das ist eine FFT gerade für halbe Größe. 01:25:26.860 --> 01:25:29.700 Und es gehen die Koeffizienten, gerade mit diesem Perfect-anshuffle 01:25:29.700 --> 01:25:33.480 dort rein, hier oben habe ich das Gerade-Polynom mit Koeffizienten a0, 01:25:33.600 --> 01:25:38.680 a2 und so weiter bis an-2 und hier unten in das andere gehen rein die 01:25:38.680 --> 01:25:43.400 Koeffizienten a1 und so weiter, a3 bis unten an-1. 01:25:44.140 --> 01:25:48.800 Dann habe ich hier unter der Annahme, dass n gerade ist natürlich. 01:25:49.400 --> 01:25:50.840 Habe ich dann hier diese Aufteilung. 01:25:51.280 --> 01:25:53.060 Nehmen wir sogar an, dass n 2er Potenz ist. 01:25:53.580 --> 01:25:55.900 Dann habe ich eine schöne regressive Aufteilung. 01:25:56.520 --> 01:25:59.660 Und anschließend muss ich dann die Werte, die ich rausbekommen habe, 01:26:00.820 --> 01:26:05.620 die n halben Werte jeweils, geeignet kombinieren und multiplizieren 01:26:05.620 --> 01:26:09.520 mit Omega bis Omega in halbe minus 1 und hier unten das gleiche 01:26:09.520 --> 01:26:10.520 nochmal. 01:26:10.780 --> 01:26:15.340 Wobei ich jetzt sogar sage, hier habe ich sogar die Operation nochmal 01:26:15.340 --> 01:26:15.760 mit drin. 01:26:18.060 --> 01:26:21.520 Ich kann auf jeden Fall, muss auf jeden Fall diese Kombination so 01:26:21.520 --> 01:26:24.500 einfach bilden und ich kann eben diese Werte, die ich hier berechnet 01:26:24.500 --> 01:26:28.660 habe, dort unten und dort oben geeignet verwenden und komme dann genau 01:26:28.660 --> 01:26:29.460 auf eine solche Struktur. 01:26:29.580 --> 01:26:34.060 Wenn ich also das hier weiter aufspalte, komme ich am Ende auf solch 01:26:34.060 --> 01:26:34.720 eine Struktur. 01:26:36.360 --> 01:26:40.780 Und dies ist eine sehr interessante Struktur, Verbindungsnetzwerk 01:26:40.780 --> 01:26:44.500 sondern es ist ein Permutationsnetzwerk, bei dem Sie folgende 01:26:44.500 --> 01:26:48.860 Eigenschaft haben, bei dem Sie folgende Eigenschaft haben, wenn Sie 01:26:48.860 --> 01:26:54.940 irgendeine Permutation machen wollen, also irgendeine Abbildung von 01:26:54.940 --> 01:26:59.000 irgendwelchen Positionen hier auf irgendwelche Positionen hier, dann 01:26:59.000 --> 01:27:03.820 finden Sie, egal von wo nach wo Sie gehen wollen, Sie finden immer 01:27:03.820 --> 01:27:04.500 irgendeinen Weg. 01:27:04.560 --> 01:27:11.860 Wenn wir also von dort nach dort wollen, dann müssen wir in dem Fall 01:27:11.860 --> 01:27:12.320 laufen. 01:27:24.180 --> 01:27:27.020 Wo muss ich denn da hinkommen? 01:27:27.760 --> 01:27:28.480 Ja, natürlich. 01:27:28.860 --> 01:27:31.560 So, so und so. 01:27:32.420 --> 01:27:35.140 Und damit das ein bisschen einfacher geht, haben wir auch dafür ein 01:27:35.140 --> 01:27:39.820 Werkzeug, das ich Ihnen noch kurz zeigen möchte, und dann sind wir für 01:27:39.820 --> 01:27:40.680 heute durch. 01:27:42.180 --> 01:27:44.700 Wieder so ein schönes Werkzeug, auch entstanden bei der 01:27:44.700 --> 01:27:46.080 Wissenswerkstatt Rechensysteme. 01:27:46.560 --> 01:27:48.680 Hier haben wir eine ganze Reihe von Verbindungsstrukturen. 01:27:49.980 --> 01:27:52.540 In dem Fall nicht nur so ein Butterfly-Netzwerk, sondern noch eine 01:27:52.540 --> 01:27:53.020 Reihe anderer. 01:27:54.160 --> 01:27:56.820 Also, was denn jetzt los? 01:28:00.300 --> 01:28:01.360 Jetzt will das nicht. 01:28:02.580 --> 01:28:03.440 Das ist ja witzig. 01:28:07.680 --> 01:28:08.760 Kann ja denn was anderes passieren? 01:28:17.810 --> 01:28:20.110 Das Applet läuft ja nicht so, wie ich das will. 01:28:22.130 --> 01:28:23.010 Was ist das denn hier? 01:28:24.830 --> 01:28:26.490 Verbindet mich mit irgendwas Komischem. 01:28:28.230 --> 01:28:29.090 Sehr seltsam. 01:28:29.670 --> 01:28:30.850 Also eigentlich soll das funktionieren. 01:28:30.890 --> 01:28:32.130 Ich habe keine Ahnung, was hier passiert. 01:28:32.770 --> 01:28:34.110 Irgendwas läuft hier im Hintergrund. 01:28:34.810 --> 01:28:38.270 Sie kam die URL auf der Folie drauf. 01:28:39.030 --> 01:28:40.610 Machen wir das dann heute hier Schluss. 01:28:41.130 --> 01:28:46.810 Hier ist das Applet und Sie können bei diesem Applet Folgendes machen. 01:28:46.930 --> 01:28:50.130 Sie können beliebige Punkte sich hier entnehmen und kriegen kürzeste 01:28:50.130 --> 01:28:50.930 Wege angegeben. 01:28:51.390 --> 01:28:55.070 Oder Sie können sich angucken, wie kann ich von irgendeinem Punkt aus 01:28:55.070 --> 01:29:01.310 wie kann ich von irgendeinem Punkt aus alle anderen erreichen. 01:29:02.750 --> 01:29:04.370 Das ist ein Broadcast-Problem. 01:29:04.850 --> 01:29:08.610 Ich möchte gerne von einem Punkt aus eine Information an alle anderen 01:29:08.610 --> 01:29:08.910 schicken. 01:29:09.530 --> 01:29:11.550 Wie kann ich das in einem solchen Verfahren machen? 01:29:11.550 --> 01:29:14.870 Sie haben hier eine Information, wollen alle anderen informieren. 01:29:15.210 --> 01:29:16.070 Alle anderen Knoten. 01:29:16.470 --> 01:29:18.650 Wie viele Operationen brauchen oder wie viele Schritte brauchen Sie 01:29:18.650 --> 01:29:19.030 dafür? 01:29:19.190 --> 01:29:22.250 Ausgehend davon, Sie können in einem Schritt alle Ihre Nachbarn 01:29:22.250 --> 01:29:22.730 informieren. 01:29:23.290 --> 01:29:25.570 Das sind so Broadcast-Probleme in Netzwerken. 01:29:26.470 --> 01:29:28.530 Und da gibt es sehr interessante Sachen. 01:29:28.870 --> 01:29:30.630 Eine ganz interessante Sache ist Folgendes. 01:29:31.290 --> 01:29:32.730 Lassen Sie mich das noch kurz ausführen. 01:29:33.330 --> 01:29:35.890 Wenn ich mir das hier angucke, eine beliebige Permutation möchte ich 01:29:35.890 --> 01:29:36.410 ausführen. 01:29:37.870 --> 01:29:41.250 Ich kann also hier beliebige Zuordnungen finden. 01:29:41.810 --> 01:29:47.190 Wenn ich aber hier Pech habe, dann sind bei zum Beispiel, dann wird 01:29:47.190 --> 01:29:49.350 vielleicht hier diese Kante mehrfach benötigt. 01:29:50.170 --> 01:29:54.370 Weil ich vielleicht sowohl von dort als auch von dort über diese Kante 01:29:54.370 --> 01:29:57.150 laufen muss, weil ich einmal da hin muss und der andere geht da unten 01:29:57.150 --> 01:29:57.390 hin. 01:29:59.170 --> 01:30:02.070 Dann laufen also zwei Informationen über diese Kante, das geht nun 01:30:02.070 --> 01:30:02.550 nacheinander. 01:30:03.170 --> 01:30:06.630 Wenn ich ein genügend großes Netz habe, kann es sein, dass Wurzeln 01:30:07.330 --> 01:30:09.390 Elemente über die gleiche Kante laufen müssen. 01:30:10.210 --> 01:30:13.570 Und da das so nacheinander gehen kann, ist dann die Laufzeit meines 01:30:13.570 --> 01:30:17.230 Verfahrens leider nicht Anzahl der Stufen von links nach rechts, was 01:30:17.230 --> 01:30:22.890 nämlich log n ist, für n Knoten, sondern wäre doch immer Wurzeln mal, 01:30:24.410 --> 01:30:26.510 wäre insgesamt nur Wurzeln. 01:30:26.870 --> 01:30:30.430 Und das Interessante ist, wenn ich das Ganze jetzt randomisiere, 01:30:31.370 --> 01:30:35.570 nämlich ich ziehe hier zufällig noch irgendwelche weiteren Kanten ein. 01:30:36.430 --> 01:30:38.350 Ich mache daraus einen randomisierten Graph. 01:30:40.150 --> 01:30:42.310 Dann habe ich eine bessere Struktur. 01:30:42.750 --> 01:30:43.970 Oder ich mache folgendes. 01:30:45.530 --> 01:30:47.490 Statt eine Permutation möchte ich ausführen. 01:30:49.090 --> 01:30:59.550 Die führe ich aus durch eine randomisierte Permutation plus eine 01:31:01.930 --> 01:31:04.510 praktisch wiederrandomisierte Permutation. 01:31:07.410 --> 01:31:10.130 Und das Interessante ist, wenn ich eine randomisierte Permutation 01:31:10.130 --> 01:31:13.830 mache, wenn ich von jedem Knoten aus zu einem zufälligen Ort gehe, auf 01:31:13.830 --> 01:31:18.710 der rechten Seite, dann habe ich eine erwartete Laufzeit von log n. 01:31:20.330 --> 01:31:22.510 Dann tritt dieser Fall mit Wurzeln nicht auf. 01:31:23.150 --> 01:31:24.670 Die erwartete Laufzeit ist log n. 01:31:26.310 --> 01:31:30.770 Und wenn ich also zwei solche randomisierte Permutationen mache, im 01:31:30.770 --> 01:31:34.690 Prinzip von rechts nach links, habe ich jedes Mal eine erwartete 01:31:34.690 --> 01:31:37.730 Laufzeit von log n, habe also insgesamt eine erwartete Laufzeit von 01:31:37.730 --> 01:31:38.090 log n. 01:31:38.930 --> 01:31:42.010 Wenn ich das ohne die Randomisierung mache und mir angucke, wie ist 01:31:42.010 --> 01:31:45.670 die erwartete Laufzeit für Permutationen, kriege ich es leider heraus, 01:31:45.690 --> 01:31:47.890 für dieses Netzwerk. 01:31:48.750 --> 01:31:53.550 Und das heißt, ganz kleine Idee, wie Sie die Staus im Urlaubsverkehr 01:31:53.550 --> 01:31:55.510 bearbeiten oder lösen können. 01:31:56.110 --> 01:31:59.770 Sie schicken alle Leute, die in den Urlaub fahren wollen, erstmal an 01:31:59.770 --> 01:32:02.350 beliebige randomisierte Orte, die lassen sich einfach an irgendeinem 01:32:02.350 --> 01:32:06.830 Urlaubsort ziehen, werden dahin geschickt, an ein Zufallsziel, und 01:32:06.830 --> 01:32:09.410 dürfen von dort an ihr eigentliches Urlaubsziel fahren. 01:32:09.890 --> 01:32:11.730 Dann haben Sie alle Staus beseitigt. 01:32:12.350 --> 01:32:15.050 Weil das schön gleichmäßig verteilt wird. 01:32:15.750 --> 01:32:16.270 Nette Idee. 01:32:16.350 --> 01:32:19.630 Ist tatsächlich in Rechnern so eingesetzt worden, dass alle 01:32:19.630 --> 01:32:22.150 Nachrichten, die verschickt werden, erstmal an zufällige Prozessoren 01:32:22.150 --> 01:32:24.710 geschickt werden und von da erst an die eigentliche Adresse. 01:32:25.070 --> 01:32:26.890 Geht deutlich schneller, als wenn man die direkt schickt. 01:32:27.830 --> 01:32:30.050 Das also nur als kleine Idee noch dahinter. 01:32:30.170 --> 01:32:31.710 Damit sind wir am Ende dieser Vorlesung. 01:32:32.210 --> 01:32:36.310 Am Ende des Kapitels geht nächstes Mal weiter mit einem kleinen 01:32:36.310 --> 01:32:39.690 Ausflug in Rekurrenzgleichung und danach im Such- und 01:32:39.690 --> 01:32:40.250 Sortierverfahren. 01:32:40.330 --> 01:32:40.670 Vielen Dank.