WEBVTT

00:00.680 --> 00:01.780
So, schönen guten Tag.

00:02.060 --> 00:04.040
Ich begrüße Sie zur Fortsetzung der Vorlesung des effizienten

00:04.040 --> 00:04.580
Algorithmen.

00:04.740 --> 00:06.440
Heute klappt alles perfekt anscheinend.

00:07.040 --> 00:10.180
Was die Technik angeht, letztes Mal war das irgendwie ein schlechtes

00:10.180 --> 00:10.700
Vorzeichen.

00:11.360 --> 00:12.820
Aber die Aufzeichnung hat ja funktioniert.

00:15.120 --> 00:18.500
Mittlerweile ist es so, dass wir ja wieder in der Zeit sind, wo die

00:18.500 --> 00:19.800
Vorlesungen evaluiert werden.

00:20.720 --> 00:24.480
Und bei dieser Vorlesung tritt der übliche Effekt auf, dadurch, dass

00:24.480 --> 00:29.400
ich die Vorlesung aufzeichne, sagen sich viele von Ihnen, dass Sie

00:29.400 --> 00:32.100
eigentlich andere Dinge zu tun haben, vielleicht andere Vorlesungen

00:32.100 --> 00:32.360
oder so.

00:32.420 --> 00:34.880
Es gibt viele Gründe, warum man dann nicht in der Vorlesung auftaucht,

00:34.940 --> 00:38.120
sondern zu Hause sitzt und irgendwann die Vorlesung anhört.

00:39.240 --> 00:42.280
Wenn es um die Bewertung der Vorlesung geht, möchte ich natürlich

00:42.280 --> 00:47.100
erreichen, dass Sie trotzdem vernünftig in der Lage sind, das zu

00:47.100 --> 00:47.380
machen.

00:47.600 --> 00:50.600
Allerdings ist ja das eine Bewertung, die auf Papier platziert.

00:50.800 --> 00:52.080
Das heißt, Sie können sie nicht zu Hause machen.

00:52.520 --> 00:55.520
Bei anderen Vorlesungen haben wir das so gemacht, dass Sie bei der

00:55.520 --> 00:59.300
Bonusklausur zu Beginn die Bewertung machen.

00:59.920 --> 01:02.200
Das können wir hier nicht oder keine Bonusklausur anbieten.

01:03.140 --> 01:05.000
Man könnte natürlich sagen, wir machen das in den Übungen.

01:05.220 --> 01:06.260
Das wäre auch eine Möglichkeit.

01:06.600 --> 01:08.920
Ist vielleicht das Sinnvollste, dass wir das in den Übungen machen.

01:09.280 --> 01:11.000
Da sind eigentlich die meisten von Ihnen da.

01:11.560 --> 01:15.320
Denn hier das zu machen, das halte ich nicht für wirklich sinnvoll,

01:15.320 --> 01:21.320
weil halt doch nur ein gewisser Teil derjenigen da ist.

01:21.460 --> 01:24.700
Die Vorlesungen sind ja durchaus die größere Zahl.

01:25.580 --> 01:31.400
Und hier sitzen halt heute 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, naja

01:31.400 --> 01:37.680
zwischen 10 und je nachdem 20 Leuten unterschiedlich, aber es sind

01:37.680 --> 01:41.180
halt circa dreifache Zahlen, glaube ich, sind bei den Übungen dabei.

01:42.380 --> 01:44.820
Und dann machen wir das so.

01:45.260 --> 01:48.180
Das heißt, Herr Schukler kümmert sich darum, dass in den Übungen dann

01:48.180 --> 01:49.640
die Vorlesung auch bewertet wird.

01:50.880 --> 01:58.360
Wir sind letztes Mal gewesen beim Punkt Effizient Algorithmen,

01:58.440 --> 01:59.420
algebraische Probleme.

02:00.120 --> 02:02.500
Ich habe Ihnen nochmal einiges erzählt.

02:02.620 --> 02:05.560
Eines habe ich Ihnen nicht erzählt, nicht gezeigt.

02:05.660 --> 02:08.920
Da hatte ich gedacht, dass das schon erledigt gewesen wäre.

02:08.920 --> 02:10.080
Es war es aber nicht.

02:11.600 --> 02:17.740
Und deswegen muss ich ein paar Kleinigkeiten nochmal kurz machen.

02:18.000 --> 02:23.680
Nicht diese Matrix-Modifikation, sondern wir hatten gesagt, Sie sollen

02:23.680 --> 02:26.340
sich auch beschäftigen mit diesen Werkzeugen.

02:26.520 --> 02:31.100
Gehen wir nochmal ganz kurz in den Präsentationsmodus.

02:31.140 --> 02:34.440
Da kann ich nämlich ganz kurz draufklicken auf diesen Link.

02:35.700 --> 02:40.780
Wer von Ihnen hat sich das schon mal angeguckt, dieses Applet für den

02:40.780 --> 02:41.600
Mapping -Ansatz?

02:43.100 --> 02:43.500
Keiner.

02:43.620 --> 02:44.540
Dann sehen Sie das jetzt.

02:46.200 --> 02:48.460
Gut, schauen wir mal, das müsste eigentlich...

02:48.460 --> 02:50.560
Eigentlich sollte das jetzt einfach umschalten.

02:52.120 --> 02:53.940
Na, was sagt er jetzt?

02:54.980 --> 02:55.940
Gehen wir das mal hier rauf.

02:56.020 --> 02:56.620
Da ist es ja schon.

02:56.700 --> 02:57.920
Sehen Sie, jetzt funktioniert alles.

02:58.300 --> 03:00.520
Letztes Mal habe ich gesagt, ich hätte Schwierigkeiten gehabt, im

03:00.520 --> 03:02.920
Firefox dieses Applet aufzusuchen.

03:02.920 --> 03:04.080
Da wäre irgendwas nicht in Ordnung.

03:04.180 --> 03:05.120
Es war was nicht in Ordnung.

03:05.640 --> 03:07.220
Was nicht in Ordnung war, war Folgendes.

03:07.820 --> 03:12.040
Dass bei den Plugins von Firefox, bei der neuen, beim Update von

03:12.040 --> 03:15.260
Firefox, nicht alle Plugins automatisch installiert werden.

03:15.900 --> 03:19.020
Und Firefox sieht Java-Programme als schädlich an.

03:19.600 --> 03:22.280
Und geht deshalb davon aus, dass man die nicht haben möchte.

03:22.940 --> 03:25.320
Deswegen war Java nicht aktiviert.

03:25.500 --> 03:27.440
Hab ich aktiviert, jetzt ist natürlich alles da.

03:28.120 --> 03:30.740
Also falls Sie das gleiche Problem haben, muss man darauf achten, was

03:30.740 --> 03:32.820
aktiviert ist, was nicht aktiviert ist von den Plugins.

03:33.380 --> 03:36.640
Und entsprechend wird das dann besser funktionieren.

03:36.980 --> 03:38.320
Jetzt schauen wir uns das mal an.

03:38.460 --> 03:41.340
Das ist jetzt offensichtlich etwas zu groß.

03:41.840 --> 03:43.460
Weil ich das so kleiner kriege.

03:44.420 --> 03:45.380
Ja, das ist ja perfekt.

03:46.300 --> 03:47.000
Das ist das Wichtige.

03:47.260 --> 03:49.080
Aber jetzt ist das sehr witzig.

03:49.160 --> 03:50.460
Er ist in dem Fenster nicht richtig drin.

03:51.040 --> 03:52.700
Hier passt die Auflösung leider nicht.

03:52.800 --> 03:53.500
Das ist aber dumm.

03:55.980 --> 03:57.580
Das gefällt mir nun gar nicht.

03:58.260 --> 03:59.800
Machen wir das mal wieder rückgängig.

04:02.980 --> 04:03.920
Das wundert mich.

04:03.960 --> 04:06.280
Das ist ein Problem mit der Auflösung.

04:06.380 --> 04:07.880
Ich mach das Ding mal ganz aus.

04:09.260 --> 04:12.080
Vielleicht kommt es dann gleich nochmal auf.

04:12.980 --> 04:16.160
Das ist mir noch nie passiert, dass das von der Auflösung nicht passt.

04:17.800 --> 04:19.220
Geh ich mal ganz raus hier.

04:20.460 --> 04:21.660
Klick das nochmal an.

04:26.890 --> 04:27.770
Jetzt müsste es kommen.

04:30.470 --> 04:32.590
Es ist nicht richtig da.

04:33.110 --> 04:33.590
Seltsam.

04:34.030 --> 04:37.090
Ich kann das trotzdem nicht bedienen.

04:37.810 --> 04:38.810
Nehme ich jedenfalls an.

04:40.270 --> 04:41.710
Das ist ja nun wirklich seltsam.

04:41.790 --> 04:45.830
Jetzt muss ich das doch nochmal mit dem Internet Explorer versuchen.

04:47.210 --> 04:48.050
Das habe ich noch nie gehabt.

04:48.750 --> 04:50.430
Das ist doch immer nicht alles so einfach.

04:50.610 --> 04:51.930
Das ist technisch alles kein Problem.

04:52.690 --> 04:55.610
Auf einmal macht er hier Sachen, die er sonst noch nie getan hat.

04:56.350 --> 04:58.970
Und zeigt das Applet nicht im vollen Umfang.

05:02.750 --> 05:04.130
Mal sehen, was er hier zeigt.

05:05.370 --> 05:06.730
Das sieht hier schon besser aus.

05:07.550 --> 05:08.750
Ich muss aber das hier auch...

05:10.490 --> 05:10.970
Steuerung...

05:13.550 --> 05:14.030
Minus...

05:14.030 --> 05:16.150
Das hat er auch nicht voll drin.

05:21.630 --> 05:23.530
Jetzt ist alles da.

05:24.430 --> 05:25.390
Jetzt habe ich es.

05:25.530 --> 05:27.170
Jetzt können wir hier weitermachen.

05:28.030 --> 05:29.070
Matrix-Modifikation.

05:29.170 --> 05:31.390
Sie erinnern sich an die Matrix-Modifikation?

05:31.710 --> 05:35.370
Im Mapping-Ansatz, da ging es darum, alle Berechnungen, die ausgeführt

05:35.370 --> 05:37.910
werden, erstmal im Datenflussgraf zu zeigen.

05:38.350 --> 05:40.070
Das ist das, was wir hier sehen.

05:40.410 --> 05:41.690
Das ist dieser Datenflussgraf.

05:41.810 --> 05:43.410
Dieser Datenabhängigkeitsgraf.

05:43.910 --> 05:47.030
Der genau zeigt, welche Berechnungen gemacht werden müssen.

05:47.130 --> 05:49.130
An jedem Knotenpunkt findet eine Berechnung statt.

05:49.750 --> 05:53.970
Jede einzelne Berechnung ist so wie hier unten in diesem Fenster

05:53.970 --> 05:54.610
angedeutet.

05:54.610 --> 05:56.390
Auf diesem Bild.

05:56.630 --> 06:00.810
Es wird so mit den Farben, wie ich das in der Vorlesung auch hatte.

06:01.550 --> 06:03.010
Rot, die Matrix A.

06:04.150 --> 06:05.590
Blau, die Matrix B.

06:07.170 --> 06:10.210
Und grün, die Ergebnismatrix C.

06:11.550 --> 06:13.010
Die wandern also durch das Feld.

06:13.990 --> 06:16.430
Und hier sind die Abhängigkeiten halt dargestellt.

06:16.610 --> 06:20.410
Und in diesem Fall ist das so dargestellt, dass die Datenflussrichtung

06:20.410 --> 06:23.610
von A so diagonal hier drin ist.

06:23.610 --> 06:26.770
Die Datenflussrichtung von B ist horizontal.

06:27.590 --> 06:30.730
Und die Datenflussrichtung von C ist vertikal.

06:30.870 --> 06:31.810
Hier so angedeutet.

06:31.910 --> 06:34.190
In irgendeinem Koordinatensystem.

06:34.670 --> 06:35.110
Dreidimensional.

06:35.310 --> 06:37.210
Das sind ja die drei Indizes, von denen das abhängt.

06:38.150 --> 06:41.870
Und jetzt, wissen Sie, kann ich so einen Datenflussgraf abbilden auf

06:41.870 --> 06:44.670
Zeit und Ort.

06:45.210 --> 06:46.990
Indem ich eine Transformation vornehme.

06:47.430 --> 06:50.110
Und diese Transformationsmatrix ist hier angegeben in der Mitte.

06:50.810 --> 06:52.870
Die oberste Zeile ist die Zeitzuordnung.

06:52.870 --> 06:59.350
Wir wollen also, dass hier in jeder Richtung immer ein Takt

06:59.350 --> 07:00.110
Verzögerung ist.

07:00.130 --> 07:02.670
Deswegen schreiben wir hier standardmäßig 1 rein.

07:03.090 --> 07:05.830
Wenn man mehr Verzögerungen haben möchte, kann man größere Zahlen

07:05.830 --> 07:06.330
reinschreiben.

07:06.410 --> 07:09.650
Wenn man 0 reinschreibt, heißt das, der Wert muss zum gleichen

07:09.650 --> 07:12.030
Zeitpunkt an verschiedenen Orten zur Verfügung stehen.

07:13.050 --> 07:14.890
Das ist in der Regel nicht so einfach möglich.

07:15.010 --> 07:17.530
Deswegen ist also den 0 da reinzuschreiben etwas kritisch.

07:19.410 --> 07:21.210
Das sind die drei Takte.

07:21.350 --> 07:23.290
Es soll jeweils ein Takt Verzögerung sein.

07:23.790 --> 07:28.090
Also mindestens ein Takt dauert es, um von einem vorherigen Ort zum

07:28.090 --> 07:29.070
nächsten Ort zu kommen.

07:29.510 --> 07:34.350
Jetzt ist hier oben angedeutet, mit den roten Balken, jeweils auf

07:34.350 --> 07:38.870
welche Datenflussrichtung sich der entsprechende Vektor bezieht.

07:39.830 --> 07:43.770
Hier sehen Sie, horizontal ist die erste Spalte.

07:43.770 --> 07:47.590
Horizontal heißt also, das ist in dem Bild daneben, blau.

07:48.410 --> 07:50.970
Das heißt, das ist hier die Matrix B.

07:53.010 --> 07:57.970
Vertikal ist hier also die mittlere Spalte.

07:58.390 --> 08:00.750
Das ist die Ergebnismatrix C.

08:01.130 --> 08:06.630
Und diagonal ist die dritte Spalte, das ist unsere Matrix A.

08:07.570 --> 08:10.650
Und jetzt schauen wir mal an, was passiert, wenn ich sage, die

08:10.650 --> 08:11.770
Prozessorzuordnung...

08:12.410 --> 08:20.490
Das gibt an, in welcher Richtung jeweils die Daten wandern sollen, in

08:20.490 --> 08:21.230
einem Takt.

08:21.770 --> 08:27.770
Wenn ich also sage, das, was hier horizontal ist, also das ist die

08:27.770 --> 08:32.670
Matrix B, die soll in einem Takt sich nicht bewegen in x-Richtung,

08:33.310 --> 08:38.050
sondern zum Beispiel mit einem Takt...

08:38.050 --> 08:41.810
Oder ich mache es mal so, wie wir das in... also Matrix B soll von

08:41.810 --> 08:42.950
oben nach unten laufen, genau.

08:43.770 --> 08:46.910
Keine Bewegung in x-Richtung, eine Bewegung in y-Richtung.

08:48.130 --> 08:52.410
Matrix C, könnten wir mal sagen, die soll einfach stehen bleiben.

08:53.010 --> 08:55.470
Die bleibt am Ort, wo sie war.

08:56.250 --> 09:01.590
Und die Matrix A, die soll sich um einen Takt von links nach rechts

09:01.590 --> 09:03.810
bewegen und ansonsten nicht.

09:06.110 --> 09:10.050
Dann versuchen wir jetzt mal, diese Zuordnung zu machen.

09:10.210 --> 09:17.890
Sagen wir Apply und Sie sehen, wir haben jetzt ein zweidimensionales

09:17.890 --> 09:22.370
Feld erzeugt, in das die jeweiligen Datenflussrichtungen eingezeichnet

09:22.370 --> 09:24.310
sind, so wie wir sie gerade definiert haben.

09:24.770 --> 09:29.490
Nämlich blau, B, das war die erste Spalte, geht von Norden nach Süden.

09:30.530 --> 09:34.690
Rot, das war die dritte Spalte, geht von links nach rechts.

09:35.310 --> 09:39.770
Und grün bleibt, da sehen Sie so eine kleine Schleife da drin, geht

09:39.770 --> 09:42.410
nicht weiter, sondern bleibt an dem Ort, wo es war.

09:42.970 --> 09:46.430
Wenn ich sage, das soll nicht stehen bleiben, sondern ich möchte

09:46.430 --> 09:50.610
gerne, dass das Ganze hier diagonal durchwandert, dann schreibe ich

09:50.610 --> 09:54.790
hier 1,1 hin, darf anwenden und dann sehen Sie, das sieht das Feld so

09:54.790 --> 09:55.110
aus.

09:56.270 --> 10:01.150
Jetzt wandert also die Ergebnismatrix C von links oben nach rechts

10:01.150 --> 10:02.570
unten durch dieses Feld hindurch.

10:03.310 --> 10:07.330
Ich könnte auch sagen, das soll meinetwegen hier mal minus 1 sein.

10:08.190 --> 10:09.370
Was passiert denn dann?

10:09.930 --> 10:11.310
Dann sieht die Matrix so aus.

10:12.890 --> 10:15.730
Das heißt, die Berechnungen werden jeweils entsprechend diesem

10:15.730 --> 10:20.150
Transformationsschema angeordnet und es ergeben sich dann andere

10:20.150 --> 10:24.490
Zuordnungen von Einzelberechnungen auf Orte und Zeiten.

10:25.870 --> 10:29.890
Und Sie können also hier beliebig damit rumspielen.

10:30.030 --> 10:34.110
Man kann auch sagen, ich möchte jetzt also, dass meinetwegen hier die

10:34.110 --> 10:37.410
Matrix dieser Wert so rumläuft.

10:38.130 --> 10:40.490
Und ja, das geht nun leider nicht.

10:41.950 --> 10:42.330
Warum?

10:43.210 --> 10:46.110
Weil die Transformationsmatrix, die ist singulär.

10:47.210 --> 10:51.670
Und Sie erinnern sich, damit das Ganze eine gültige Abbildung wird,

10:52.090 --> 10:54.410
darf ich keine singuläre Transformationsmatrix verwenden.

10:55.250 --> 10:56.850
Ja, ich kann sie trotzdem anwenden.

10:58.150 --> 10:59.270
Und was passiert dann?

10:59.830 --> 11:01.430
Dann sehen Sie, das sieht ja ganz anders aus.

11:02.110 --> 11:04.510
Und den können Sie so nicht ausführen.

11:04.750 --> 11:08.050
Ja, da sind Datenabhängigkeiten drin, die sind so nicht erfüllbar.

11:08.530 --> 11:09.450
Das funktioniert nicht.

11:10.530 --> 11:15.050
Also es wird trotzdem was ausgerechnet, aber das ist kein vernünftiger

11:15.050 --> 11:18.890
Signalflussgraf.

11:19.170 --> 11:21.310
Da kann man auch ein Retime machen, das bringt hier aber in diesem

11:21.310 --> 11:21.870
Fall nichts.

11:24.730 --> 11:28.430
Also insofern, man kann hier damit rumspielen, ziemlich viel.

11:29.530 --> 11:35.230
Ich könnte hier sagen, wenn ich hier sage "-1", und meinetwegen hier

11:35.230 --> 11:35.450
oben...

11:36.370 --> 11:38.050
Nee, da ist keine Null, das wäre schlecht.

11:38.150 --> 11:39.450
Hier oben sage ich mal "-1".

11:40.390 --> 11:43.850
Und ich sage hier Null, dann sieht das wieder besser aus.

11:44.270 --> 11:45.630
Das müsste also ausführen können.

11:45.750 --> 11:48.290
Sie sehen, das ist ja auch etwas, was machbar wäre.

11:48.370 --> 11:51.190
Hier läuft jetzt aber die Matrix A nicht von links nach rechts,

11:51.210 --> 11:52.150
sondern von rechts nach links.

11:53.370 --> 11:53.970
Auch das ist möglich.

11:54.570 --> 11:58.350
Sie können also alle möglichen beliebigen Anordnungen oder

11:58.350 --> 12:02.270
Datenflussrichtungen definieren, mit einer nicht-singulären Matrix,

12:02.430 --> 12:05.810
und es kommt immer dann ein gültiger Graf heraus, der genau diese

12:05.810 --> 12:06.640
Berechnung so abbildet.

12:07.390 --> 12:10.510
Und in der Aufgabe, die Sie haben, müssen Sie halt entsprechend das

12:10.510 --> 12:11.410
anwenden.

12:11.510 --> 12:13.490
Okay, das also ganz kurz zu diesem Applet.

12:13.870 --> 12:17.210
Dann gibt es nur noch mal zur Vollständigkeit, es gibt halt hier auch

12:17.210 --> 12:23.810
ein paar andere Datenabhängigkeitsgrafen für ein Sortierproblem oder

12:23.810 --> 12:25.520
für Matrix-Vektor-Multiplikationen.

12:27.240 --> 12:31.720
Und da sind dann auch noch einige Informationen abrufbar.

12:31.800 --> 12:34.980
Hier ist so ein About, da steht also, wer das gemacht hat, schon eine

12:34.980 --> 12:35.460
Weile her.

12:36.200 --> 12:39.960
Und das war so ein Kollege von Ihnen, der das mal vor langer Zeit

12:39.960 --> 12:40.540
gemacht hat.

12:40.980 --> 12:43.900
Und hier sehen Sie ein bisschen Erläuterungen, wie man das Ding

12:43.900 --> 12:44.580
anwenden kann.

12:45.820 --> 12:53.080
Also, das ist dieses Applet für die Anwendung der Abbildungen oder die

12:53.080 --> 12:56.720
Definition von Transformationen auf Datenabhängigkeitsgrafen.

12:57.880 --> 12:58.860
Das also dazu.

12:59.660 --> 13:06.120
Dann gehen wir mal wieder zurück zur Präsentation hier.

13:06.300 --> 13:10.180
Das waren die Dinge, die wir schon vor zwei Wochen gemacht haben.

13:10.180 --> 13:14.280
Dann hatten wir letztes Mal einiges getan, was sich mit Polynomen

13:14.280 --> 13:15.000
beschäftigt.

13:15.440 --> 13:18.700
Ich hatte Ihnen gezeigt, dass das Horner-Schema ein optimales

13:18.700 --> 13:21.600
Verfahren ist für die Auswertung von Polynomen oder von allgemeinen

13:21.600 --> 13:22.820
Polynomen endengrades.

13:23.440 --> 13:28.560
Man braucht halt gerade 2n Additionen und Multiplikationen.

13:29.080 --> 13:33.300
Wobei wir natürlich davon ausgehen, dass wir nicht schon beliebig

13:33.300 --> 13:35.840
viele komplexe Terme verwenden dürfen.

13:35.840 --> 13:39.380
Also ausgehen davon, dass wir Skalare als Eingabe haben.

13:39.900 --> 13:43.820
Sogar irgendwelche Potenzen von x, dass dieses f von x in Runden

13:43.820 --> 13:46.940
klammern und halt die Koeffizienten unbekannt sind.

13:47.500 --> 13:50.140
Und dann kam hier noch ein Beweis dazu.

13:50.480 --> 13:52.400
Da brauche ich jetzt nicht mehr darauf einzugehen.

13:52.460 --> 13:55.640
Wir hatten dann gesehen, dass man das Ganze auch allgemeiner machen

13:55.640 --> 13:55.880
kann.

13:56.020 --> 13:59.480
Da war hier dieses Beispiel, dass man ein Polynomen einfach aufteilt

13:59.480 --> 14:03.080
in so quadratische Faktoren, sofern man die Koeffizienten kennt.

14:03.080 --> 14:09.000
Und dann in der Lage ist, die Hälfte der Multiplikationen einzusparen,

14:09.060 --> 14:09.880
so etwa die Hälfte.

14:10.980 --> 14:13.250
Und wir hatten uns kurz mit der Parallelisierung beschäftigt.

14:13.860 --> 14:16.780
Dann kam die Schnelle-Bouillet-Transformation, bei der es eben darum

14:16.780 --> 14:21.140
geht, dass man eine Aufgabe, nämlich das Multiplizieren von Polynomen,

14:21.780 --> 14:23.820
einfach transformiert in eine andere Darstellung.

14:23.900 --> 14:28.160
Und das ist eigentlich hier der wichtige Effekt, den Sie sich hier

14:28.160 --> 14:29.160
vergegenwärtigen müssen.

14:29.160 --> 14:33.220
Dass ich hier ein Problem gegeben habe in einer gewissen Darstellung.

14:34.360 --> 14:36.320
Also ich habe das gegeben als Koeffizienten.

14:36.780 --> 14:37.880
Das war hier das Wesentliche.

14:37.920 --> 14:39.940
Ich habe die Koeffizienten-Darstellung für ein Polynomen.

14:40.760 --> 14:43.400
Und wenn ich in der Koeffizienten-Darstellung ein Produkt berechne,

14:44.180 --> 14:47.460
habe ich zwangsläufig eine gewisse Anzahl von Berechnungen zu machen.

14:48.900 --> 14:51.980
Zumindest wenn ich so naiv einfach die ausmodifiziere.

14:51.980 --> 14:56.780
Wenn ich aber eine andere Darstellung wähle, also jetzt die

14:56.780 --> 15:00.680
Wertedarstellung, dann kann ich das Produkt ganz einfach berechnen.

15:00.760 --> 15:04.600
Einfach indem ich die einzelnen Wertepaare multipliziere und dann das

15:04.600 --> 15:06.340
Wertepaar für das Produkt bekomme.

15:06.680 --> 15:07.460
Ganz einfach.

15:07.880 --> 15:09.140
Ich muss eben nur transformieren.

15:09.920 --> 15:11.240
Ich muss auch wieder rücktransformieren.

15:11.760 --> 15:15.200
Und die Schnelle-Bouillet-Transformation ist eine Art, wie ich schnell

15:15.200 --> 15:16.860
transformieren kann.

15:16.860 --> 15:20.960
Schneller, als ich vorher bei der direkten Multiplikation von

15:20.960 --> 15:23.860
Polynomen das Produkt berechnen konnte.

15:24.480 --> 15:30.200
Also hier ist praktisch der wesentliche Gehalt dieses Teiles ist, man

15:30.200 --> 15:34.280
soll sich sehr genau angucken, wie man ein Problem repräsentiert.

15:34.800 --> 15:40.160
Weil je nachdem, wie man es repräsentiert, die Möglichkeiten, das

15:40.160 --> 15:42.660
Problem zu lösen, völlig unterschiedlich sein können.

15:43.020 --> 15:44.620
Und auf einmal ganz einfach sein können.

15:44.620 --> 15:47.600
Man muss dann eben nur sehen, wie kann man Repräsentation ineinander

15:47.600 --> 15:48.200
überführen.

15:49.660 --> 15:52.760
Ein anderes Beispiel aus dem anderen Bereich ist, wenn Sie zwei Zahlen

15:52.760 --> 15:56.580
addieren wollen, zwei binär dargestellte Zahlen, dann haben Sie immer

15:56.580 --> 16:00.640
das Problem, dass Sie dort einen Übertrag durchlaufen lassen müssen.

16:01.320 --> 16:06.800
Wenn Sie eine Darstellung von Zahlen nehmen, nicht in der normalen

16:06.800 --> 16:11.200
Binärdarstellung, sondern in einer redundanten Zahlendarstellung, mit

16:11.200 --> 16:15.800
dreiwertigen Bits, minus 1, 0 und 1, dann können Sie in konstanter

16:15.800 --> 16:16.520
Zeit agieren.

16:17.040 --> 16:18.700
Dann brauchen Sie keinen durchlaufen Übertrag.

16:18.800 --> 16:21.340
Sie müssen eben nur transformieren können.

16:22.700 --> 16:25.440
Also dieses Prinzip der Transformation ist ganz wichtig.

16:26.200 --> 16:31.860
Und noch kurze Anmerkung dazu, also hier zu diesen Beispielen dafür,

16:32.000 --> 16:37.320
wo das wichtig ist, es gibt so Ansätze im Bereich Optimierung, dass

16:37.320 --> 16:42.080
man sagt, ich habe ein komplexes Problem, das ich optimieren möchte

16:42.080 --> 16:45.960
und ich stelle das mal in einer natürlichen Darstellung gegeben.

16:47.480 --> 16:50.660
Und dann verwende ich diese Darstellung und wende zum Beispiel einen

16:50.660 --> 16:51.840
genetischen Algorithmus an.

16:52.240 --> 16:53.980
Oder ich wende irgendeine andere Heuristik an.

16:54.920 --> 17:00.260
Und dann kann es sein, dass eine andere Darstellung des Problems zu

17:00.260 --> 17:03.600
einem völlig anderen Optimierungsverhalten führt, einem besseren

17:03.600 --> 17:04.500
Optimierungsverhalten.

17:04.600 --> 17:07.080
Sie müssen eben nur erstmal sehen, was ist die sinnvollste

17:07.080 --> 17:08.360
Repräsentation des Problems.

17:08.460 --> 17:11.540
Und das ist ein ganz wichtiger Punkt, sich erstmal klar darüber zu

17:11.540 --> 17:15.140
werden, wie muss ich eigentlich mein Problem beschreiben, damit ich es

17:15.140 --> 17:20.180
effizient auf der geeigneten Rechnerstruktur dann lösen kann.

17:20.180 --> 17:22.540
Also das hatten wir dann gemacht bei der schnellen Fourier

17:22.540 --> 17:26.500
-Transformation und da war ja die wesentliche Idee, dass wir die

17:26.500 --> 17:31.480
Polynome auswerten an einer Reihe von Stellen, nämlich an den Enden

17:31.480 --> 17:32.300
Einheitswurzeln.

17:33.300 --> 17:37.800
Und die wesentliche Idee war dann halt, dass wir in der Lage sind,

17:37.940 --> 17:48.760
diese Werte an den Enden Einheitswurzeln, die konnten wir halt sehr

17:48.760 --> 17:51.800
einfach berechnen.

17:52.580 --> 17:55.740
Dadurch, dass wir gewisse Eigenschaften der Enden Einheitswurzeln

17:55.740 --> 17:59.260
ausgenutzt haben, hier waren so ein paar Eigenschaften angegeben, dass

17:59.260 --> 18:05.540
eben die erste Hälfte gerade die negative Version der zweiten Hälfte

18:05.540 --> 18:10.580
der Enden Einheitswurzeln ist und dass das Quadrat einer

18:10.580 --> 18:13.620
Einheitswurzel, einer Enden Einheitswurzel, gerade die Enthalt der

18:13.620 --> 18:14.520
Einheitswurzel ist.

18:14.520 --> 18:17.420
Und das wurde ausgenutzt, um dann eben dieses Schema hier zu machen,

18:17.480 --> 18:23.520
bei dem man die Polynome zur Auswertung aufgeteilt hat, in zwei

18:23.520 --> 18:26.960
Polynome, eines mit den geraden Koeffizienten, eins mit den ungeraden

18:26.960 --> 18:32.660
Koeffizienten und dann entsprechend Polynomen bekam, die man von x²

18:32.660 --> 18:33.620
jeweils berechnete.

18:33.800 --> 18:37.640
Das heißt, da hat man entsprechend eine Einheitswurzel zum Quadrat

18:37.640 --> 18:41.020
genommen und dann den Wert berechnet und konnte daraus sehr einfach

18:41.020 --> 18:44.740
mit diesem Schema dann die Werte an den N verschiedenen

18:44.740 --> 18:46.510
Einheitswurzeln tatsächlich ausrechnen.

18:47.280 --> 18:51.160
Wir hatten gesehen, das geht dann mit einem Berechnungsaufwand, der

18:51.160 --> 19:00.820
halt bei zweimal Zeit von N½ plus Linearzeit läuft und das führt zu

19:00.820 --> 19:02.500
einer Ausführungszeit von NlogN.

19:03.060 --> 19:04.260
Dazu kommen wir jetzt gleich nochmal.

19:04.840 --> 19:08.640
Und das, was wir am Ende, was ich Ihnen dann kurz gezeigt habe, war

19:08.640 --> 19:10.980
diese Folie, das war ein bisschen sehr schnell, deswegen gehe ich

19:10.980 --> 19:12.060
darauf nochmal kurz ein.

19:13.000 --> 19:16.440
Das, was wir bei der FFT als Kommunikationsgraf haben, sieht so aus,

19:16.500 --> 19:17.120
wie hier angedeutet.

19:17.260 --> 19:18.180
Warum sieht das so aus?

19:19.200 --> 19:25.780
Wir haben unsere Koeffizienten A0, hier muss ich nochmal kurz den

19:25.780 --> 19:32.160
Stift aufmachen, wir haben unsere Koeffizienten A0, A1 und so weiter

19:32.160 --> 19:33.300
bis An-1.

19:33.380 --> 19:36.160
Das ist unser Polynom, das wir transformieren wollen in die

19:36.160 --> 19:36.900
Wertedarstellung.

19:38.160 --> 19:40.440
Wir wollen diese in Werte berechnen.

19:41.460 --> 19:47.440
Und um diese Werte zu berechnen, wenden wir also die schnelle Fouillet

19:47.440 --> 19:48.280
-Transformation an.

19:48.380 --> 19:52.620
Wir teilen das Polynom auf in das Polynom mit den geraden

19:52.620 --> 19:55.160
Koeffizienten und das Polynom mit den ungeraden Koeffizienten.

19:55.160 --> 19:57.800
Das sind jeweils Polynome halben Grades.

19:59.440 --> 20:08.740
Und da kommen raus Werte für einmal die geraden Koeffizienten und

20:08.740 --> 20:11.160
unten für die ungeraden Koeffizienten.

20:14.260 --> 20:18.200
Und jetzt müssen wir die Ergebnisse, die daraus kommen, geeignet

20:18.200 --> 20:18.740
verknüpfen.

20:18.860 --> 20:24.060
Das war ja immer gerade das Ergebnis für das gerade Polynom.

20:24.060 --> 20:31.560
Und dazu mussten wir drauf addieren, diese Einheitswurzel mal, oder

20:31.560 --> 20:37.760
das aktuelle Argument, mal Wert des ungeraden Polynoms.

20:38.240 --> 20:43.960
Deswegen haben wir immer hier so zwei Werte verknüpft.

20:44.260 --> 20:47.260
Ein Wert des geraden Polynoms mit dem entsprechenden Wert des

20:47.260 --> 20:48.440
ungeraden Polynoms.

20:48.440 --> 20:52.000
Und das Ungerade dann multipliziert mit Omega, damit wir die

20:52.000 --> 20:56.460
Koeffizienten richtig zu den Potenzen zuordnen.

20:57.880 --> 21:02.960
Und bei den anderen hier unten, da tauchen eben nur die negativen

21:02.960 --> 21:03.580
Werte auf.

21:04.080 --> 21:06.460
Das heißt, man könnte sich die Multiplikation hier sogar sparen.

21:07.360 --> 21:10.900
Wir haben also so ein Schema, bei dem wir diese sehr einfache Struktur

21:10.900 --> 21:11.340
haben.

21:11.880 --> 21:16.240
Hier vorne gehen irgendwelche Werte rein, in diese Kästen jeweils.

21:16.240 --> 21:23.420
Und dann wird immer paarweise die einzelnen Ausgänge vom oberen und

21:23.420 --> 21:26.340
vom geraden und vom ungeraden Teil kombiniert.

21:27.140 --> 21:32.220
Und das, was rauskommt, wenn man es prekursiv auftrüselt, zum Beispiel

21:32.220 --> 21:40.100
für ein Butterfly-Netzwerk für n gleich 8, ist dann dieses Polynom,

21:40.480 --> 21:46.660
Quatsch, dieser Verbindungsgraf und die typische Struktur eines

21:46.660 --> 21:48.400
sogenannten Butterfly-Netzwerks.

21:48.500 --> 21:49.740
Warum Butterfly-Netzwerk?

21:50.220 --> 21:53.620
Weil Sie halt, wenn Sie sich das hier anschauen, das ist so wie ein

21:53.620 --> 21:57.260
Körper hier eines Schmetterlings und da sind die beiden Flügel.

21:57.380 --> 21:58.500
Das sind Flügel, das sind Flügel.

21:58.580 --> 21:59.420
Deswegen Butterfly.

21:59.420 --> 22:04.340
Also das ist so ein Körper mit zwei großen Flügeln und diese Struktur

22:04.340 --> 22:05.520
setzt sich rekursiv fort.

22:05.720 --> 22:09.500
Also hier das nochmal, da auch so ein Körper und dann die beiden

22:09.500 --> 22:09.840
Flügel.

22:09.960 --> 22:10.760
Da kommt der Name hin.

22:11.560 --> 22:16.840
Und diese Struktur ist eine Struktur, die sehr interessant ist, weil

22:16.840 --> 22:23.100
wir hier ein sogenanntes Permutationsnetzwerk vorliegen haben.

22:24.460 --> 22:28.940
Permutationsnetzwerk heißt, ich kann von jedem Punkt am Eingang zu

22:28.940 --> 22:30.420
jedem Punkt am Ausgang gelangen.

22:31.320 --> 22:34.260
Und jetzt will ich das auch an dem Applet Ihnen kurz nochmal

22:34.260 --> 22:34.860
darstellen.

22:36.220 --> 22:39.980
Dazu muss ich jetzt den Stift rausnehmen.

22:40.100 --> 22:43.480
Jetzt können wir darauf gehen und Sie sehen hier verschiedene

22:43.480 --> 22:47.340
Strukturen, verschiedene Verbindungsstrukturen, die unter gewissen

22:47.340 --> 22:50.300
Aspekten, unter Kommunikationsaspekten angeguckt werden.

22:50.300 --> 22:52.680
Und gehen wir jetzt mal hier auf, Sie sehen das ist eine ganze Reihe

22:52.680 --> 22:53.940
von verschiedenen Strukturen.

22:54.300 --> 22:55.560
Gehen wir auf das Butterfly-Netz.

22:57.180 --> 22:58.140
Was sehe ich hier?

22:58.800 --> 23:01.080
Hier kann ich mir jetzt beste Pfade angucken.

23:01.200 --> 23:04.600
Ich kann also hier irgendeinen Knoten mir hernehmen und in irgendeinem

23:04.600 --> 23:05.620
Knoten hier rechts.

23:05.740 --> 23:07.500
Und Sie sehen, da gibt es jetzt eine Verbindung.

23:08.560 --> 23:11.560
Und es ist so, ich finde nicht nur von jedem Punkt auf der linken

23:11.560 --> 23:16.380
Seite eine Verbindung zu einem Punkt auf der rechten Seite, sondern

23:16.380 --> 23:21.080
ich kann sogar jede Permutation realisieren.

23:21.200 --> 23:26.820
Das heißt, ich kann gleichzeitig hier alle Punkte auf der linken Seite

23:26.820 --> 23:29.000
jeweils mit einem...

23:29.000 --> 23:31.260
Achso, da muss ich erstmal hier wieder raufklicken auf beste Pfade.

23:31.980 --> 23:34.480
Dann kann ich hier wieder raufklicken und sagen, wir gehen da hin.

23:35.200 --> 23:36.220
Und da gibt es ein Pfad.

23:36.940 --> 23:40.980
Das heißt, ich finde für jede Zuordnung von Punkten auf der linken

23:40.980 --> 23:43.400
Seite zu Punkten auf der rechten Seite, also für jede Permutation,

23:44.360 --> 23:49.920
genau diese Pfade durch dieses Netz, sodass ich also diese Permutation

23:49.920 --> 23:51.620
ausführen kann von links nach rechts.

23:53.380 --> 23:57.440
Ich kann also hieraus ein Kommunikationsnetzwerk machen, wo ich zum

23:57.440 --> 24:01.800
Beispiel dafür sorge, dass N Prozessoren mit N Prozessoren reden und

24:01.800 --> 24:03.240
ich kann jede Verbindung realisieren.

24:05.340 --> 24:11.360
Und wie man sieht, habe ich hier ja nur eins, zwei, drei Schritte.

24:11.480 --> 24:12.360
Das geht ja ganz schnell.

24:14.220 --> 24:22.820
Ich kann also hier mit der Durchmesser, die Länge, der Durchmesser

24:22.820 --> 24:23.560
stimmt nicht ganz.

24:24.840 --> 24:26.660
Also von links nach rechts habe ich Lockendstufen.

24:26.660 --> 24:32.480
Wenn ich ein Butterfly-Netzwerk habe mit 8, also für N gleich 8, habe

24:32.480 --> 24:33.300
ich halt drei Stufen.

24:33.980 --> 24:35.940
Da muss man sich nur Folgendes überlegen.

24:36.980 --> 24:40.720
Wenn ich mir anschaue, den Weg, den wir hier gerade andeuten, und

24:40.720 --> 24:48.920
jetzt möchte ich zum Beispiel von, machen wir nochmal einen Pfad, von

24:48.920 --> 24:53.980
diesem hier zu diesem Knoten, dann stellen Sie fest, die Kante hier in

24:53.980 --> 24:58.340
der Mitte, die wird von beiden Pfaden benötigt.

25:00.140 --> 25:04.180
Und wenn ich mir jetzt ein Rechnungsmodell überlege, bei dem von jedem

25:04.180 --> 25:10.680
Knoten ich in der Lage bin, in einem Takt eine Nachricht

25:10.680 --> 25:15.600
rauszuschicken über eine Verbindung, dann hätte ich hier ein Problem.

25:15.600 --> 25:18.960
Bei diesem Knoten kommen jetzt zwei Nachrichten an.

25:19.120 --> 25:22.600
Wenn die beiden Knoten hier entsprechend, der eine wollte dorthin, der

25:22.600 --> 25:25.500
andere dorthin, schicken die beide irgendwelche Informationen los.

25:26.100 --> 25:28.140
Die müssen beide über diese eine Kante laufen.

25:29.780 --> 25:31.960
Damit die darüber laufen können, müssen sie nacheinander geschickt

25:31.960 --> 25:32.280
werden.

25:33.660 --> 25:36.600
Das heißt, wir haben dann hier schon zwei Takte, Verarbeitungstakte,

25:36.780 --> 25:39.960
um Informationen von der zweiten Schicht zur dritten Schicht zu

25:39.960 --> 25:40.180
schicken.

25:41.900 --> 25:46.200
Und Sie können sich vorstellen, wenn der Butterfly jetzt größer wird,

25:48.500 --> 25:53.640
dann kann es passieren, dass hier eine ganze Reihe von Pfaden eine

25:53.640 --> 25:54.700
gemeinsame Kante haben.

25:56.260 --> 25:59.780
Man kann sich überlegen, können Sie sich gerne selbst überlegen, dass

25:59.780 --> 26:05.740
das im schlimmsten Fall Wurzeln-Pfade sind, die eine gemeinsame Kante

26:05.740 --> 26:06.060
haben.

26:06.780 --> 26:10.560
Das heißt, Sie brauchen auf einmal Wurzeln in Takte, um von über

26:10.560 --> 26:13.640
dieser eine Kante die ganzen Knoten rüberzuschieben.

26:14.760 --> 26:17.480
Und Sie brauchen demnach hier ganz viel Zeit.

26:17.660 --> 26:21.440
Und der schöne Vorteil eines Permutationsnetzwerks mit Log N solchen

26:21.440 --> 26:26.820
Pfaden, Log N solchen Ebenen, geht Ihnen verloren.

26:29.880 --> 26:31.180
Sie schütteln den Kopf.

26:31.580 --> 26:32.760
Ich weiß nicht, warum Sie den Kopf schütteln.

26:38.340 --> 26:41.740
Also, was ich Ihnen jetzt noch, Sie können damit auch rumspielen, nur

26:41.740 --> 26:44.500
noch kurz, ich komme gleich wieder auf diese Probleme mit diesem

26:44.500 --> 26:48.140
Wurzeln zurück, nur um Ihnen zu zeigen, was man hier noch machen kann,

26:48.500 --> 26:51.960
wenn man ein solches Netzwerk hat, wenn man irgendeine Anordnung von

26:51.960 --> 26:54.500
Knoten hat, Sie können sich also überlegen, wir haben jetzt hier

26:54.500 --> 26:56.780
irgendeinen Knoten, der will eine Information an alle anderen

26:56.780 --> 26:57.060
schicken.

26:58.120 --> 27:02.580
Dann möchte ich jetzt wissen, wie lange dauert das, wenn jeder Knoten

27:02.580 --> 27:06.260
in jedem Takt an seine Nachbarinformationen schicken kann, an alle

27:06.260 --> 27:09.480
seine Nachbarn, wie lange dauert das, um alle Knoten zu informieren.

27:09.560 --> 27:14.140
Dann kann ich hier raufklicken und kann mir angucken, wie lange das

27:14.140 --> 27:17.780
dauert, bis also eine Information ganz verteilt ist im Netz.

27:18.360 --> 27:19.440
Das ist hier relativ einfach.

27:19.680 --> 27:21.680
Ich muss halt den längsten Pfad von da aus mir angucken.

27:22.380 --> 27:24.380
Aber so kann man das hier, ist hier visualisiert.

27:24.380 --> 27:31.860
Und in diesem Werkzeug können Sie das eben auch für andere Strukturen

27:31.860 --> 27:34.980
machen, zum Beispiel für zweidimensionales Gitter.

27:35.640 --> 27:38.880
Da können Sie also jetzt hier, wenn wir hier sagen Broadcast, Sie

27:38.880 --> 27:42.200
wollen sich angucken, wie sieht das aus mit Broadcast hier, dann sehen

27:42.200 --> 27:45.000
Sie, wie hier Information sich verteilt über solch ein

27:45.000 --> 27:46.420
zweidimensionales Gitter.

27:46.860 --> 27:52.080
Das heißt, Kommunikationsstrukturen in Parallelrechnern sind ein

27:52.080 --> 27:56.400
wichtiges Thema und man muss sich genau angucken, wie lange dauert es

27:56.400 --> 28:00.920
eigentlich, über einen besten Pfad Informationen zu schicken in so

28:00.920 --> 28:05.100
einem Netzwerk und wie lange dauert es, um alle Knoten zu informieren

28:05.100 --> 28:08.580
über eine Nachricht, die von einem Knoten rausgeschickt wurde.

28:09.320 --> 28:13.680
Das also sind diese beiden Applets, die wir Ihnen hier zur Ansicht

28:13.680 --> 28:16.120
empfehlen oder zum Durchprobieren empfehlen.

28:17.060 --> 28:18.920
Ups, das war falsch.

28:19.440 --> 28:22.900
Ich möchte jetzt noch eine Sache zusätzlich Ihnen erzählen.

28:23.040 --> 28:27.520
Und zwar nochmal zurückkommen zu diesem Problem mit dem Butterfly

28:27.520 --> 28:32.720
-Netz, das nicht in der Lage ist, wirklich jede Permutation in

28:32.720 --> 28:37.720
Zeitlogin auszuführen, weil es eben sein kann, dass hier irgendeine

28:37.720 --> 28:42.500
Kante von mehreren Permutationen belegt wird.

28:43.720 --> 28:46.660
Das Problem ist, wenn Sie sich die Menge aller Permutationen

28:46.660 --> 28:52.820
anschauen, dann gibt es in der Menge aller Permutationen, die hier

28:52.820 --> 28:59.380
möglich sind, einige, die schlechte Eigenschaften haben.

29:02.630 --> 29:05.730
Also schlechte Eigenschaften in dem Sinne, dass es lange dauert, um

29:05.730 --> 29:07.210
hier Informationen rüberzuschicken.

29:09.610 --> 29:13.450
Und viele Permutationen, die wir in irgendwelchen Anwendungen

29:13.450 --> 29:18.570
verwenden, fallen leider genau in diese Teilmenge rein, bei denen wir

29:18.570 --> 29:21.530
solche großen Verzögerungen haben.

29:22.190 --> 29:27.170
Also in vielen Anwendungen verwenden wir reguläre Strukturen für die

29:27.170 --> 29:30.330
Kommunikation und dann passiert so etwas.

29:31.290 --> 29:33.630
Wenn wir aber randomisierte Permutationen nehmen, als

29:33.630 --> 29:38.210
Zufallspermutationen, dann liegen die irgendwo, ab und zu auch mal da

29:38.210 --> 29:38.450
drin.

29:39.590 --> 29:40.550
Aber in der Regel nicht.

29:41.710 --> 29:46.490
Wenn ich mal so anschaue, wie lange die Zeit ist, um eine

29:46.490 --> 29:52.630
Zufallspermutation hier auszuführen, dann ist die erwartete Zeit Log

29:52.630 --> 29:52.930
N.

29:54.630 --> 29:57.570
Der Erwartungswert für die Ausführung von Permutationen mit einem

29:57.570 --> 29:58.850
Patternfly -Netzwerk ist Log N.

29:58.850 --> 30:03.870
Ich kann immer noch Pech haben und es dauert ganz lange für eine

30:03.870 --> 30:06.330
bestimmte Permutation, die ich ausführen möchte.

30:06.730 --> 30:07.590
Jetzt kommt der Trick.

30:09.590 --> 30:15.390
Ich mache es einfach so, dass ich zufällig Kanten einfüge oder

30:15.390 --> 30:15.910
verdoppel.

30:16.050 --> 30:20.370
Oder irgendwie hier noch mal eine Kante mache oder da noch mal eine.

30:21.490 --> 30:23.310
Ich baue daraus ein Zufallsnetzwerk.

30:25.130 --> 30:31.590
Und auf einmal habe ich zufällig hier einige, oder es sind zwei

30:31.590 --> 30:31.870
Schritte.

30:32.810 --> 30:36.210
Ein Schritt ist, dass ich ein Zufallsnetzwerk mache, randomisierten

30:36.210 --> 30:37.030
paar Kanten dazu.

30:37.750 --> 30:42.450
Dann habe ich randomisiert ein anderes Netzwerk und es hat auf einmal

30:42.450 --> 30:43.390
bessere Eigenschaften.

30:44.130 --> 30:48.750
Und ich kann mit dem randomisierten Netzwerk auf einmal in einer

30:48.750 --> 30:56.110
günstigeren Zeit durchlaufen für alle Permutationen.

30:57.030 --> 30:59.090
Jetzt kommt noch ein Trick und den wollte ich Ihnen eigentlich hier an

30:59.090 --> 30:59.950
dieser Stelle erzählen.

31:00.950 --> 31:04.330
Der andere Trick ist so, ich möchte eine Permutation Pi ausführen.

31:05.770 --> 31:07.430
Und es kann sein, dass die schlecht ist.

31:08.450 --> 31:15.110
Jetzt wähle ich einfach eine randomisierte Permutation Pi r und führe

31:15.110 --> 31:16.170
die zuerst aus.

31:19.610 --> 31:23.770
Wenn ich eine randomisierte, eine Zufallspermutation nehme und die

31:23.770 --> 31:24.370
ausführe.

31:25.270 --> 31:29.010
Und anschließend die eigentlich gewünschte Permutation.

31:30.910 --> 31:33.570
Ja, das muss dann also eine Permutation Pi' sein.

31:35.290 --> 31:38.430
Damit insgesamt meine Permutation Pi rauskommt.

31:39.650 --> 31:43.250
Ich muss also von dem zufälligen Zielort wieder dann auf den

31:43.250 --> 31:44.610
eigentlich gewünschten Ort kommen.

31:46.810 --> 31:50.410
Dann habe ich insgesamt eine Zufallspermutation, zweimal.

31:51.950 --> 31:54.750
Nicht insgesamt, ich habe zweimal eine Zufallspermutation zu machen.

31:55.650 --> 31:58.530
Und ich habe beide Male eine erwartete Laufzeit von Log N.

31:59.470 --> 32:09.770
Das heißt, der schlechteste Fall geht von O von Wurzel N, Log N runter

32:09.770 --> 32:13.870
auf O von Log N.

32:14.770 --> 32:20.670
Weil ich zweimal diese Zufallspermutation mache, um die eigentliche

32:20.670 --> 32:21.670
Permutation auszuführen.

32:22.390 --> 32:25.590
Und damit haben Sie die Idee für die Vermeidung von Staus auf

32:25.590 --> 32:26.910
Autobahnen in der Urlaubszeit.

32:28.510 --> 32:31.490
Wenn Sie Staus auf Autobahnen sehen, genau das, was wir hier haben.

32:32.570 --> 32:33.850
Also kleiner Scherz am Rande.

32:34.870 --> 32:37.990
Eine Idee, wie man Staus vermeiden kann, ist ganz einfach.

32:38.570 --> 32:41.470
Zu Beginn der Urlaubszeit zieht jeder einen zufälligen Zielort.

32:42.490 --> 32:44.770
Muss erstmal zu diesem zufälligen Zielort fahren.

32:45.710 --> 32:48.690
Und von dem zufälligen Zielort darf er dann an den eigentlichen Ort

32:48.690 --> 32:50.490
fahren, zu dem er fahren möchte.

32:51.290 --> 32:54.630
Dadurch sind die Fahrzeuge alle zufällig verteilt über das

32:54.630 --> 32:55.250
Straßennetz.

32:55.250 --> 32:56.750
Sie haben keine Staus mehr.

32:57.310 --> 32:59.810
Dauert zwar ein bisschen länger, aber nur etwas.

33:00.730 --> 33:01.950
Doppelte Zeit, das ist nicht so schlimm.

33:03.930 --> 33:06.450
Also nur, dass man sieht, das ist so eine Idee.

33:06.590 --> 33:11.030
Und diese Idee wird tatsächlich angewandt in Rechnerinfrastrukturen.

33:11.850 --> 33:15.630
Also in der Connection Machine ist das tatsächlich eingesetzt worden.

33:16.650 --> 33:21.370
Und da hat man also bei Kommunikation, die dort gemacht werden, werden

33:21.370 --> 33:24.230
die Nachrichten erstmal an zufällige Orte geschickt und von dort an

33:24.230 --> 33:24.930
den eigentlichen Ort.

33:25.490 --> 33:28.750
Und dadurch hat man Engpässe in der Kommunikation verbieten.

33:29.210 --> 33:31.990
Und ein ausgeglichenes Verhalten für das Kommunikationsnetz.

33:33.350 --> 33:36.890
Also das ist inzwischen ein Standardansatz, um Kommunikation zu

33:36.890 --> 33:37.070
machen.

33:37.710 --> 33:42.190
Gut, ich gehe auf dieses Thema nicht groß weiter ein.

33:42.290 --> 33:47.670
Man könnte da sehr viel mehr Zeit dafür einsetzen, um über

33:47.670 --> 33:50.230
Auswirkungen von Kommunikationsnetzen zu reden.

33:50.230 --> 33:53.210
Aber ich wollte es doch zumindest erwähnt haben, dass man so etwas

33:53.210 --> 33:53.550
macht.

33:54.450 --> 34:04.790
Also die randomisierte Kommunikation ist also hier etwas sehr

34:04.790 --> 34:05.330
Wichtiges.

34:06.110 --> 34:08.590
So, das ist der Teil algebraische Probleme.

34:09.250 --> 34:15.630
Und jetzt kommen wir zu dem nächsten Teil, dem nächsten Abschnitt.

34:15.630 --> 34:23.930
Das ist ganz kurz ein sehr kurzes Kapitel, in dem ich ein paar

34:23.930 --> 34:28.450
Techniken einfach ganz kurz ansprechen möchte, die man braucht, um so

34:28.450 --> 34:32.650
typische Abschätzungen von Laufzeiten schnell zu lösen.

34:33.850 --> 34:36.350
Und zwar geht es um Rekurrenzgleichungen, die Sie schon mehrfach

34:36.350 --> 34:37.250
gesehen haben.

34:37.250 --> 34:39.970
Das kennen Sie wahrscheinlich auch schon eventuell schon aus

34:39.970 --> 34:44.290
Grundlageninformatik 1 oder aus irgendwelchen anderen Quellen,

34:44.390 --> 34:46.430
vielleicht auch aus Operations Research.

34:47.170 --> 34:52.410
Es geht darum, dass wir die Standardvorgehensweise der Informatiker

34:52.410 --> 34:55.050
oder auch überhaupt bei der Problemlösung uns anschauen.

34:55.190 --> 34:59.030
Eine der Standardvorgehensweisen ist ein Dividend-Conquer-Ansatz.

35:00.390 --> 35:05.430
Dividend-Conquer, wissen Sie, heißt, ich teile mein Problem auf in

35:05.430 --> 35:06.670
eine Reihe von Teilproblemen.

35:06.670 --> 35:07.950
Wir haben das jetzt schon ein paar Mal gemacht.

35:08.550 --> 35:12.310
Wir haben das gemacht bei dem Straßenverfahren und haben das auch

35:12.310 --> 35:17.050
gemacht bei paralleler Auswertung von Polynomen.

35:17.610 --> 35:20.770
Man teilt sein Problem auf in mehrere Teilprobleme.

35:20.970 --> 35:24.350
Also in Probleme P1, P2 bis PK.

35:24.850 --> 35:25.970
K-Teilprobleme.

35:27.310 --> 35:30.690
Und diese Teilprobleme haben jeweils eine Größe N durch C.

35:31.250 --> 35:33.770
Nicht notwendigerweise die Größe N durch K.

35:35.150 --> 35:38.910
Erinnern Sie sich an unseren Algorithmus von Straßen.

35:40.070 --> 35:45.550
Da hatten wir sieben Teilprobleme der Größe N halb.

35:47.990 --> 35:52.730
Das war ja gerade diese Idee gewesen, da hatten wir sieben

35:52.730 --> 35:53.090
Teilprobleme.

35:53.750 --> 35:56.310
Bei Straßen war K gleich 7 und C gleich 2.

35:57.770 --> 35:59.070
Schreibe ich hier nochmal kurz hin.

36:04.360 --> 36:06.120
C gleich 2.

36:06.120 --> 36:13.200
Dann lösen wir die Teilprobleme rekursiv nach diesem Verfahren.

36:13.920 --> 36:16.360
Also jedes Teilproblem, wenn ich das gleiche Verfahren habe.

36:18.180 --> 36:23.900
Wenn die Problemgröße überhaupt noch relevant ist.

36:24.520 --> 36:27.420
Wenn ich bei einer gewissen Schranke angekommen bin, schalte ich um

36:27.420 --> 36:28.340
und mache das direkt.

36:29.220 --> 36:32.020
Und dann muss ich natürlich die Lösungen der Teilprobleme, die ich

36:32.020 --> 36:35.880
jetzt hier erzeugt habe, alle geeignet kombinieren zu der

36:35.880 --> 36:36.660
Gesamtlösung.

36:37.980 --> 36:41.520
Bei einigen Algorithmen ist das der wesentliche Aufwand.

36:42.040 --> 36:43.620
Das Zusammensetzen von Teillösungen.

36:43.780 --> 36:47.560
Da ist das Erzeugen der Lösungen rekursiv eigentlich erstmal trivial.

36:48.260 --> 36:50.740
Und dann müssen Sie Aufwand reinstecken, um die Lösungen zu

36:50.740 --> 36:51.240
kombinieren.

36:51.360 --> 36:53.880
Bei anderen ist es so, dass Sie ganz viel Aufwand reinstecken, um die

36:53.880 --> 36:54.780
Aufteilung zu machen.

36:55.660 --> 36:57.780
Das ist also unterschiedlich.

36:58.460 --> 37:00.640
Auf jeden Fall habe ich eben diese verschiedenen Aufwände mir

37:00.640 --> 37:01.220
anzugucken.

37:01.860 --> 37:05.820
Das heißt, ich habe den Aufwand für Probleme, ich sage jetzt Größe 1

37:05.820 --> 37:09.320
oder irgendwie konstante Anfangsgröße.

37:09.900 --> 37:12.660
Dann habe ich den Aufwand für die Schritte A und C.

37:14.620 --> 37:19.280
Und bekomme daraus eine Rekursionsgleichung oder eine

37:19.280 --> 37:25.460
Rekurrenzgleichung für den Aufwand, den ich habe für die Lösung des

37:25.460 --> 37:26.620
Problems.

37:26.720 --> 37:29.080
Bei Problemgröße 1 ist gerade der Aufwand A.

37:29.940 --> 37:34.420
Bei Problemgröße N muss ich K mal das Problem der Größe N durch C

37:34.420 --> 37:39.940
bearbeiten und habe dann noch einen Aufwand von D von N oben drauf für

37:39.940 --> 37:42.180
die Aufteilung und für das Zusammensetzen.

37:42.760 --> 37:44.960
Das ist ein Ding, das kennen Sie eigentlich alle aus dem MF.

37:44.960 --> 37:48.980
Ist aber vielleicht so gar nicht präsentiert worden, in dieser Art,

37:49.120 --> 37:50.340
das so systematisch anzugucken.

37:50.800 --> 37:53.000
Für wen ist das neu, das so anzugucken?

37:54.400 --> 37:55.160
Für niemanden.

37:55.280 --> 37:56.180
Ich erzähle Ihnen olle Kamel.

37:57.360 --> 37:58.300
Nein, nicht ganz.

37:59.020 --> 38:00.980
Und jetzt kommt eben die Rekurrenzgleichung.

38:01.040 --> 38:01.920
Jetzt kommt das nochmal.

38:02.120 --> 38:03.080
Wir wollen die jetzt lösen.

38:03.720 --> 38:06.360
Und wir haben das auch schon gesehen, als wir Straßen uns angeguckt

38:06.360 --> 38:06.720
haben.

38:07.120 --> 38:10.400
Wenn man das versucht, jetzt aufzulösen, dann kriegt man raus, eine

38:10.400 --> 38:15.120
Formel für T von N aus dieser Rekurrenzgleichung.

38:15.720 --> 38:23.380
Da steht A mal K hoch M plus Summe J gleich 1 bis M minus 1 K hoch J

38:23.380 --> 38:26.000
mal D von N durch C hoch J.

38:27.160 --> 38:30.280
Jetzt werden die Problemgrößen sukzessive kleiner, immer um den Faktor

38:30.280 --> 38:30.560
C.

38:30.740 --> 38:32.400
Deswegen steht hier immer N durch C und J.

38:33.060 --> 38:36.940
Wir haben jeweils ein Aufwand K, oder wir haben jeweils K

38:36.940 --> 38:40.420
Teilprobleme, also werden das aus K, K², K hoch 3 usw.

38:41.640 --> 38:47.240
Und wir haben ganz unten für die kleinsten Problemgrößen den Aufwand A

38:47.240 --> 38:49.380
und das K hoch M mal zu machen.

38:50.640 --> 38:59.000
Und das M in diesem Fall ist der Logarithmus zur Basis C von N.

39:00.820 --> 39:03.960
So, das ist also unsere Gleichung.

39:04.520 --> 39:08.660
Und mit so einer Formel kann man nicht viel anfangen.

39:08.800 --> 39:10.480
Wir wollen das ein bisschen einfacher im Sinn schreiben.

39:11.080 --> 39:13.560
Dass das so ist, kann man sich einfach überlegen, das kennen Sie,

39:13.720 --> 39:15.700
hatte ich im Prinzip an einem Beispiel schon mal gemacht.

39:16.320 --> 39:17.680
Jetzt schauen wir uns Spezialfälle an.

39:17.780 --> 39:20.820
Wir wollen das für gewisse Spezialfälle einfacher lösen können.

39:21.660 --> 39:28.300
Wenn der Aufwand konstant ist, immer der gleiche Aufwand, dann heißt

39:28.300 --> 39:30.660
also dieser Aufwand hier hinten ist konstant.

39:33.930 --> 39:35.630
Und das K ist 1.

39:36.950 --> 39:37.750
Wie kann das sein?

39:37.830 --> 39:39.530
Ein Teilproblem, konstanter Aufwand?

39:40.150 --> 39:43.790
Es kann auch sein, dass Sie mehr Teilprobleme haben, aber Sie können

39:43.790 --> 39:45.470
die alle parallel lösen.

39:46.770 --> 39:49.190
Das sind Fälle, die wir uns später mehrfach haben werden.

39:49.930 --> 39:52.250
Wenn Sie die alle parallel machen, brauchen Sie die Zeit ja nur einmal

39:52.250 --> 39:52.830
zu rechnen.

39:53.670 --> 39:56.630
Dann haben Sie also hier eine Formel, wo K gleich 1 ist.

39:57.470 --> 40:02.950
Dann ist es so, dass der Aufwand, wenn Sie sich diese Summe anschauen,

40:04.630 --> 40:13.130
dass D ist konstant, K ist 1, dann steht hier A plus, naja, eine

40:13.130 --> 40:17.410
Summe, Fj gleich 1 bis M minus 1, der Aufwand ist 1, das ist konstant,

40:17.510 --> 40:23.130
das K over J ist 1, das heißt hier steht log N, log zur Basis C von N

40:24.870 --> 40:27.830
mal konstanter Aufwand, das heißt der Aufwand ist O von log N.

40:28.990 --> 40:35.070
Wenn das K größer als 1 ist, dann passiert folgendes, so intuitiv

40:35.070 --> 40:38.930
gesagt, das K ist größer als 1.

40:39.670 --> 40:43.830
Das heißt, Sie haben natürlich den Aufwand hier unten A mal K hoch N.

40:45.970 --> 40:48.530
Und dann kommt dazu das, was hier in dieser Summe steht.

40:48.530 --> 40:56.450
In der Summe steht hier K hoch J mal D, das ist konstant.

40:57.570 --> 41:00.850
Das heißt, wir haben hier die Summe K hoch J, J gleich 1 bis M minus

41:00.850 --> 41:01.330
1.

41:02.870 --> 41:07.090
Da wissen Sie aber, das ist der Wert einer geometrischen Reihe, der

41:07.090 --> 41:15.330
ist gleich K hoch M minus 1 durch K minus 1.

41:15.330 --> 41:19.190
Da das von 1 anfängt und nicht von 0, müssen Sie noch 1 abziehen.

41:20.890 --> 41:22.330
Das ist der Wert einer geometrischen Reihe.

41:24.130 --> 41:27.630
So, das heißt, hier steht nochmal das K hoch M im Prinzip drin.

41:28.670 --> 41:31.370
Der Rest ist ja konstant immer K hoch M.

41:32.130 --> 41:35.210
Wir haben also A mal K hoch M plus noch irgendwas mal K hoch M.

41:35.630 --> 41:41.370
Das heißt, insgesamt kriegen Sie raus, das Ganze ist dann O von K hoch

41:41.370 --> 41:41.930
M.

41:42.710 --> 41:47.190
Es steht hier aber N hoch log zur Basis C von K.

41:48.790 --> 41:52.210
Sie wissen aber aus unserem Beweis, den wir bei Strassen schon gemacht

41:52.210 --> 42:02.310
haben, dass das gleich ist O von N hoch log zur Basis C von K.

42:03.430 --> 42:05.130
Haben wir das schon uns überlegt?

42:06.090 --> 42:12.730
Also die Behauptung ist, K hoch M ist im Prinzip gleich N hoch log zur

42:12.730 --> 42:13.730
Basis C von K.

42:14.190 --> 42:19.770
Können Sie sich ganz einfach überlegen, indem Sie zeigen, dass

42:19.770 --> 42:28.670
folgendes gilt, das Logarithmus von K hoch M gleich ist das

42:28.670 --> 42:36.230
Logarithmus von N hoch log zur Basis C von K.

42:37.630 --> 42:39.230
Schauen Sie sich diese Gleichung an.

42:39.310 --> 42:42.610
Sie können ganz einfach durch ein einfaches Logarithmus ausrechnen.

42:43.590 --> 42:46.010
Sie können hieraus sofort machen, das ist log von K hoch M.

42:46.570 --> 42:48.210
Wissen Sie, das ist M mal log von K.

42:48.350 --> 42:50.430
Das M ist Logarithmus von N.

42:50.910 --> 42:53.150
Und zur Basis C.

42:53.770 --> 42:57.430
Und da können Sie es einfach vertauschen und dann wieder

42:57.430 --> 42:58.710
reinmultifizieren.

42:58.810 --> 43:00.090
Und Sie haben die andere Darstellung.

43:00.190 --> 43:01.250
Das ist ganz einfach zu überlegen.

43:02.290 --> 43:05.810
Also das, was hier steht, ist im Prinzip, dass das ganze Größenordnung

43:05.810 --> 43:06.590
K hoch M ist.

43:07.810 --> 43:11.690
So, und jetzt wissen wir also für konstanten Aufwand ganz einfach

43:11.690 --> 43:12.370
abzuschätzen.

43:12.610 --> 43:18.230
Für linearen Aufwand, häufiger Fall, den wir ganz oft haben, lineare

43:18.230 --> 43:21.910
Aufwand für das Aufteilen und wieder Zusammensetzen.

43:22.930 --> 43:27.350
Und da haben Sie abhängig von dem Verhältnis zwischen K und C

43:27.350 --> 43:28.650
unterschiedliche Ergebnisse.

43:29.230 --> 43:33.650
Wenn das K kleiner als C ist, haben Sie lineare Zeit, also gleiche

43:33.650 --> 43:34.910
Zeitaufwand wie das D.

43:35.910 --> 43:41.150
Wenn K und C gleich sind, also zwei Probleme der Größe in halbe plus

43:41.150 --> 43:47.650
lineare Aufwand, dann haben Sie N log N, weil Sie im Prinzip in jeder

43:47.650 --> 43:52.510
Ebene der Rekursion, wenn Sie sich das hier anschauen, wie das

43:52.510 --> 43:58.590
aufgeteilt wird, der Aufwand in jedem Teilproblem ist linear.

43:59.290 --> 44:02.450
Sie haben aber das jeweils verkürzt, also haben Sie insgesamt linearen

44:02.450 --> 44:03.590
Aufwand in jeder Ebene.

44:03.730 --> 44:05.370
Sie haben log N Ebenen, also N log N.

44:06.170 --> 44:09.930
Und wenn das K größer als C ist, dann dominiert in diesem Fall wieder

44:09.930 --> 44:10.730
das K hoch M.

44:11.230 --> 44:14.790
Dann haben Sie also N hoch log zur Basis C von K.

44:16.410 --> 44:20.190
Wieder diese Abschätzungen, das heißt, wir brauchen nicht mehr

44:20.190 --> 44:24.190
explizit uns anzugucken, wer kriegen wir dann da raus aus einer

44:24.190 --> 44:26.190
Rekursion, sondern wir sehen das sofort.

44:28.050 --> 44:31.190
Ich habe das praktisch hier schon bewiesen gerade eben, wie man darauf

44:31.190 --> 44:31.530
kommt.

44:32.270 --> 44:34.290
Jetzt sind das zwei einfache Fälle.

44:35.110 --> 44:37.270
Man kann das, also hier in die Folge auch nochmal kurz,

44:38.370 --> 44:40.590
Zeitkomplexität von divide-and-conquer-Verfahren hängt natürlich ab.

44:40.990 --> 44:43.470
Das ist klar, Aufwand für die direkte Lösung bei Abbruch des

44:43.470 --> 44:48.970
Verfahrens und Aufwand D von N für das Aufteilen in Teilprobleme und

44:48.970 --> 44:50.350
für das Zusammensetzen der Lösungen.

44:50.470 --> 44:51.690
Das habe ich Ihnen gerade eben gezeigt.

44:52.630 --> 44:54.890
Jetzt sind das hier nur zwei verschiedene Fälle, die wir angucken.

44:55.010 --> 44:56.150
Man kann das allgemeiner machen.

44:57.190 --> 45:00.310
Noch etwas, was hier eine Rolle spielt, Verhältnis, das ist natürlich

45:00.310 --> 45:04.650
wichtig, dass wir diese Sache hier, Anzahl der Teilprobleme und Größe

45:04.650 --> 45:05.870
N durch C, spielt auch eine Rolle.

45:06.670 --> 45:09.350
So, und jetzt schauen wir uns das Ganze ein bisschen allgemeiner an

45:09.350 --> 45:12.910
und sehen uns das sogenannte Master-Theorem an.

45:13.690 --> 45:16.330
Das Master-Theorem ist eine Verallgemeinerung dessen, was ich gerade

45:16.330 --> 45:18.810
gezeigt habe, was man eigentlich so in den üblichen Vorlesungen sofort

45:18.810 --> 45:19.570
vorgesetzt kriegt.

45:20.770 --> 45:23.730
Das Master-Theorem, auch da schauen Sie rein, oder können Sie

45:23.730 --> 45:26.410
reinschauen, in das Buch von Coleman, Leiser & Rivas.

45:26.790 --> 45:29.110
Sie können auch woanders reinschauen, gibt es an vielen Stellen.

45:30.490 --> 45:31.990
Das sagt jetzt Folgendes aus.

45:32.210 --> 45:34.770
Hier wird jetzt D von N ein bisschen allgemeiner betrachtet.

45:35.690 --> 45:42.150
Also bei unserer Matrix-Modifikation zum Beispiel, da wissen wir ja,

45:42.370 --> 45:48.290
da war das doch so, dass wir T, sagen wir mal, Strassen von N, das war

45:48.290 --> 45:56.050
gleich 7 mal T von N-Halbe plus O von N-Quadrat.

45:56.650 --> 45:57.880
Das ist die Strassenrekursion.

45:58.430 --> 46:01.750
Wir hatten das aufgeteilt auf Modifikation und Addition, aber das sind

46:01.750 --> 46:04.590
gerade hier, das O von N-Quadrat sind gerade die Additionen, die wir

46:04.590 --> 46:07.170
machen müssen, um das Verfahren auszuführen.

46:08.930 --> 46:10.870
Also das ist hier der Aufwand.

46:11.370 --> 46:16.930
Im Prinzip für das Zusammensetzen der Lösungen, der rekursiven

46:16.930 --> 46:19.610
Lösungen zu einer Lösung des Gesamtproblems.

46:21.170 --> 46:24.990
So, das ist also hier dieser Aufwand.

46:25.790 --> 46:30.330
Das ist also nicht linear in diesem Fall.

46:31.130 --> 46:36.250
Jetzt haben wir hier D von N aus O von N hoch log zur Basis C von K

46:36.250 --> 46:39.390
minus Epsilon für ein Epsilon größer 0.

46:41.250 --> 46:42.950
Wie ist denn das in dem Fall hier oben?

46:44.110 --> 46:45.850
Das D von N ist quadratisch.

46:46.810 --> 46:54.550
N hoch log zur Basis C von K, das wäre N hoch log zur Basis C von K.

46:54.750 --> 47:01.230
C ist 2, K ist 7, das ist also unser 2.81.

47:02.630 --> 47:16.390
Und natürlich ist O von N-Quadrat, also O von N-Quadrat ist Teilmenge

47:16.390 --> 47:19.270
von O von N hoch 2.81.

47:21.430 --> 47:26.110
Also jedes Element, das maximal mit N-Quadrat wächst, wächst maximal

47:26.110 --> 47:27.330
mit N hoch 2.81.

47:27.530 --> 47:30.510
Das heißt, wir haben hier diese Funktion ist erfüllt.

47:30.510 --> 47:34.230
Diese Abschätzung ist erfüllt, das heißt in dem Fall ist N hoch log

47:34.230 --> 47:35.370
zur Basis C von K.

47:35.890 --> 47:38.670
Hätte ich Ihnen das Mastertheorien gleich zu Anfang gezeigt, hätten

47:38.670 --> 47:43.070
wir das mit diesem ersten Fall erledigen können, was wir da explizit

47:43.070 --> 47:43.790
gezeigt haben.

47:45.430 --> 47:47.770
Das heißt, hier haben wir sofort diese Abschätzung.

47:49.410 --> 47:52.350
Und der Beweis ist ähnlich zu machen wie das, was ich Ihnen da beim

47:52.350 --> 47:53.930
Straßenverfahren gezeigt habe.

47:54.830 --> 47:59.130
Jetzt haben wir hier in der Abschätzung wieder das Verhältnis von D

47:59.130 --> 48:03.210
von N und N hoch N hoch log zur Basis C von K.

48:03.790 --> 48:11.610
Wenn das gleichartig wächst, also D von N und das N hoch log zur Basis

48:11.610 --> 48:16.690
C von K oder das K hoch M wachsen gleichmäßig, dann habe ich dieses

48:16.690 --> 48:18.170
hier mal log...

48:19.290 --> 48:22.450
Also dann habe ich den Faktor log N noch hinten dran.

48:23.770 --> 48:29.830
Und wenn das D von N größer, also stärker wächst, mindestens so stark

48:29.830 --> 48:34.050
wächst wie N hoch log zur Basis C von K oder eben dieses K hoch M,

48:34.830 --> 48:41.590
plus irgendein Epsilon und dabei aber der Aufwand insgesamt, also der

48:41.590 --> 48:48.530
Aufwand für das Zusammensetzen und Aufteilen, also K mal D von N durch

48:48.530 --> 48:53.770
C, das soll weniger Aufwand sein als das D von N.

48:55.070 --> 49:00.250
Das heißt, wenn ich mir so eine Aufteilung anschaue, so, um die

49:00.250 --> 49:05.870
Aufteilung hier zu machen, hier unten drin, K mal diese Sachen

49:05.870 --> 49:12.090
aufzuteilen und wieder zusammenzusetzen, soll kleiner gleich Alpha mal

49:12.090 --> 49:12.950
D von N sein.

49:13.070 --> 49:16.730
Das heißt, der Aufwand, der hier oben ist, um das aufzuteilen und

49:16.730 --> 49:24.530
zusammenzusetzen, soll größer sein als der Aufwand hier unten.

49:24.530 --> 49:31.250
Das heißt, das ist so eine Beschränkung oder eine Aussage über den

49:31.250 --> 49:35.410
Aufwand, den ich habe, für das Aufteilen und Zusammensetzen der

49:35.410 --> 49:36.410
Lösungen.

49:37.350 --> 49:42.870
Und wenn das so ist, dann ist der Gesamtzeitaufwand angegeben durch

49:42.870 --> 49:45.470
den Aufwand für das Zusammensetzen und Aufteilen.

49:45.630 --> 49:47.310
Dann ist er also Theta von D von N.

49:47.930 --> 49:55.410
Und das heißt, dass die Lösung davon abhängt, wie das Verhältnis ist

49:55.410 --> 50:00.170
zwischen D von N und N von log zur Basis C von K, beziehungsweise,

50:00.490 --> 50:03.630
könnt ihr auch hinschreiben, K hoch M.

50:06.010 --> 50:10.170
Das ist also, ich muss mir anschauen, wie sehen die beiden Funktionen

50:10.170 --> 50:10.450
aus.

50:10.450 --> 50:17.130
Und wenn das D von N deutlich stärker wächst, dann ist das stärker von

50:17.130 --> 50:17.930
D abhängig.

50:18.230 --> 50:22.830
Wenn es weniger wächst, ist es stärker von dem K hoch M abhängig.

50:24.790 --> 50:28.910
Und auf die Art und Weise bekomme ich also jetzt einfach Lösungen für

50:28.910 --> 50:29.450
Rekurrenzgleichungen.

50:30.790 --> 50:33.170
Hier sind ein paar Beispiele angegeben.

50:33.530 --> 50:38.190
Nochmal hier oben die Formel, die wir ja hier drin haben.

50:38.190 --> 50:42.410
Schauen wir uns das mal an bei einer Funktion 9 mal T von N Drittel

50:42.410 --> 50:43.530
plus N.

50:44.290 --> 50:45.670
Wie sieht das in dem Fall aus?

50:46.650 --> 50:50.210
3, C ist 3, K ist 9.

50:51.010 --> 51:00.570
Das heißt, in dem Fall wäre N hoch log zur Basis C von K wäre gleich N

51:00.570 --> 51:01.370
Quadrat.

51:02.470 --> 51:06.710
Und Sie sehen, dass N, also das D ist linear.

51:06.710 --> 51:11.770
Das heißt, in dem Fall haben wir den ersten Fall.

51:13.050 --> 51:16.570
Das Ganze ist also in Größenordnung N Quadrat.

51:16.690 --> 51:24.290
Das heißt, hier folgt sofort daraus, dass D von N aus O von N Quadrat

51:24.290 --> 51:24.530
ist.

51:29.550 --> 51:32.250
Und wenn wir uns das nächste anschauen.

51:32.530 --> 51:39.870
Hier T von N, das hier ist also einmal T von 2 N Drittel.

51:40.630 --> 51:41.530
Was steht denn da?

51:41.690 --> 51:45.390
Das steht also, in dem Fall ist K gleich 1.

51:46.770 --> 51:50.690
Und C ist in dem Fall gleich 1,5.

51:51.470 --> 51:52.710
Also 3,5.

51:54.250 --> 51:57.430
Was ist dann log zur Basis C von K?

51:59.490 --> 52:02.730
Log zur Basis C von K ist in dem Fall gleich 0.

52:04.590 --> 52:06.790
Der Aufwand ist 1.

52:08.990 --> 52:14.790
Das ist also der Aufwand, D von N ist aus O von 1.

52:15.430 --> 52:18.110
Und das ist natürlich gleich O von N hoch 0.

52:20.530 --> 52:23.310
Das heißt, das liegt in der gleichen Größenordnung.

52:25.250 --> 52:29.750
Und in dem Fall, wenn das in der gleichen Größenordnung ist, dann ist

52:29.750 --> 52:33.250
also der Gesamtaufwand, haben wir diese Formel hier.

52:34.130 --> 52:38.750
Das heißt, in dem Fall ist das aus Theta von N hoch log zur Basis C

52:38.750 --> 52:39.770
von K log N.

52:39.770 --> 52:45.570
Log zur Basis C von N hoch 0 ist 1.

52:45.750 --> 52:51.910
Also ist dann hier in dem Fall das T von N aus O von log N.

52:53.650 --> 52:55.910
So, das waren kurze Beispiele dafür.

52:56.390 --> 52:58.430
Mit dem Beispiel dürfen Sie sich selbst vergnügen.

52:58.890 --> 53:00.790
Da muss man ein bisschen mehr angucken, das laufe jetzt zu lang.

53:02.250 --> 53:04.710
Ist ein bisschen schwieriger, das hier einzuschätzen.

53:05.790 --> 53:09.890
Also nur zu, wie man solche Rekurrenzgleichungen einsetzt.

53:10.830 --> 53:13.910
Und wir werden uns im Weiteren eben nicht mehr damit beschäftigen, wie

53:13.910 --> 53:16.990
wir Rekurrenzgleichungen explizit lösen, sondern gucken einfach auf

53:16.990 --> 53:20.470
die Fälle von Mastertheorien und wenden die entsprechend an.

53:22.730 --> 53:25.890
Wenn Sie mehr darüber wissen wollen, man kann sehr viel noch dazu

53:25.890 --> 53:28.970
machen, über Rekurrenzgleichungen, schauen Sie sich das entsprechende

53:28.970 --> 53:32.230
Buch von Korman, da steht sehr viel dazu drin.

53:32.870 --> 53:35.530
Und alles, was ich Ihnen erzählen wollte zur Rekurrenzgleichung.

53:36.530 --> 53:37.810
Haben Sie Fragen dazu?

53:38.010 --> 53:39.390
Sie sehen alle so konsterniert aus.

53:42.230 --> 53:47.870
War das zu langweilig oder keine Antwort?

53:48.250 --> 53:48.410
Okay.

53:49.310 --> 53:49.990
Machen wir weiter.

53:50.630 --> 53:56.350
Jetzt wenden wir genau diese Sachen an und gucken uns an die nächsten

53:56.350 --> 53:59.730
interessanten Probleme, die Sie eigentlich in Vorlesungen schon öfter

53:59.730 --> 54:03.510
mal gesehen haben, nämlich Such- und Sortierprobleme.

54:04.450 --> 54:07.130
Das sind die Standardprobleme, die man sich anschaut, wenn man

54:07.130 --> 54:08.610
effiziente Algorithmen anschaut.

54:09.270 --> 54:11.890
Und da müssen wir uns überlegen, wie kann man das denn jetzt

54:11.890 --> 54:13.070
tatsächlich machen?

54:16.710 --> 54:18.530
Wie kann man suchen und sortieren?

54:18.670 --> 54:24.010
Das Problem kennen Sie alle, falls Sie es nicht geschafft haben, heute

54:24.010 --> 54:26.410
Morgen die Folien sich runterzuladen.

54:26.410 --> 54:28.150
Ich hatte sie gestern Abend erst reingestellt.

54:29.550 --> 54:30.930
Das hier kennen Sie im Prinzip alles.

54:31.090 --> 54:34.070
Das ist einfach die Überlegung, was heißt es eigentlich, wenn ich

54:34.070 --> 54:35.010
suche und sortiere.

54:36.690 --> 54:40.290
Ich gehe also um mit Elementen einer geordneten Menge.

54:40.510 --> 54:42.990
Dazu muss ich erstmal den Stift wieder hier einschalten.

54:43.570 --> 54:45.830
Ich habe also Elemente einer geordneten Menge.

54:45.950 --> 54:50.310
Das heißt, ich habe eine Menge U und je zwei Elemente von U sind

54:50.310 --> 54:52.390
vergleichbar bezüglich ihrer Größe.

54:52.950 --> 54:54.970
Ich habe also eine lineare Ordnung angegeben.

54:54.970 --> 54:59.110
Und das können also sein, irgendwelche Werte, Such-Sortierschlüssel,

54:59.450 --> 55:02.530
Namen, Zahlen, größere Objekte, die ich aber bezüglich eines

55:02.530 --> 55:04.270
Charakteristikums vergleichen kann.

55:05.010 --> 55:05.410
Ein Fake.

55:06.650 --> 55:10.290
Die Länge der Liste ist das Wesentliche, was wir uns anschauen.

55:10.790 --> 55:13.450
Die Größe der Listenelemente interessiert uns überhaupt nicht.

55:13.550 --> 55:14.910
Das können Riesenelemente sein.

55:15.470 --> 55:18.690
Was für uns interessiert, ist die Eigenschaft, bezüglich der sie

55:18.690 --> 55:19.510
verglichen werden.

55:19.930 --> 55:23.470
Und das können wir normalerweise sehr knapp darstellen.

55:26.230 --> 55:26.930
Gut.

55:28.970 --> 55:32.410
Datenstruktur ist also irgendwie eine Möglichkeit, eine Liste

55:32.410 --> 55:33.190
darzustellen.

55:33.330 --> 55:38.930
Also hier irgendwas, Elemente S1, S2, S3 und so weiter.

55:39.650 --> 55:44.010
Wenn Sie so eine Anordnung haben, können Sie das machen als zum

55:44.010 --> 55:47.250
Beispiel ein Array oder Vektor.

55:47.330 --> 55:49.510
Da können Sie jeweils beliebig darauf zugreifen.

55:50.590 --> 55:53.470
Es kann sein, dass Sie eine linear verkettete Liste haben.

55:53.470 --> 55:57.770
Das heißt, Sie hätten hier jeweils die Möglichkeit, von einem Element

55:57.770 --> 55:59.270
sich zum nächsten durchzuhangeln.

55:59.750 --> 56:02.630
Solche Strukturen wendet man manchmal an.

56:03.750 --> 56:06.650
Um etwa so aufzumalen.

56:06.990 --> 56:11.470
Wenn Sie physikalisch ein Bandspeicher haben, haben Sie eine solche

56:11.470 --> 56:12.670
Struktur oder so ähnlich.

56:13.570 --> 56:15.530
Es kann sein, dass Sie eine doppelt verkettete Liste haben.

56:15.630 --> 56:19.410
Das heißt, Sie könnten jeweils zurücklaufen, vorwärts und rückwärts.

56:20.170 --> 56:24.130
Oder es könnte sein, dass Sie einen Baum haben, durch den Sie laufen.

56:24.850 --> 56:30.430
Sie haben hier auch jeweils die Anordnungen, dass Sie Elemente

56:30.430 --> 56:31.290
vergleichen können.

56:31.410 --> 56:34.410
Und die sind in irgendeiner Form hier abgelegt.

56:35.310 --> 56:39.110
Also, das sind so übliche Möglichkeiten, Listen von Elementen

56:39.110 --> 56:39.770
anzuordnen.

56:40.470 --> 56:43.450
Die auch alle in der Praxis sehr häufig auftauchen.

56:44.230 --> 56:47.650
In der Praxis finden Sie halt sehr oft Bäume, insbesondere wenn es um

56:47.650 --> 56:48.670
Suchverfahren geht.

56:48.670 --> 56:51.150
Oder eben Arrays oder Vektoren.

56:51.230 --> 56:53.890
Wenn Sie Pech haben, haben Sie eine linear verkettete Liste.

56:54.110 --> 56:54.570
Warum Pech?

56:54.970 --> 56:58.070
Weil Sie dann nämlich nur linear darauf zugreifen können.

56:58.190 --> 57:01.430
Das heißt, der Aufwand, um auf ein Element zu kommen hier drin, der

57:01.430 --> 57:03.430
kann schon linear sein in der Größe der Liste.

57:04.710 --> 57:06.490
Das sind also mögliche Datenstrukturen.

57:07.090 --> 57:09.370
Und welche Operationen führen wir durch?

57:10.110 --> 57:12.750
Wir wollen auf irgendeine Komponente zugreifen.

57:12.910 --> 57:14.190
Das hier ist unsere Liste.

57:14.190 --> 57:17.950
Wir wollen gerne das Element, das ist unsere Liste L.

57:18.690 --> 57:21.170
Wir wollen auf die Ite Komponente zugreifen.

57:21.710 --> 57:22.830
Da steht hier irgendein Li.

57:23.990 --> 57:28.430
Wir müssen das in einer vernünftigen Zeit machen können.

57:29.350 --> 57:31.950
Es kann sein, dass wir Komponenten vergleichen wollen, in Bezug auf

57:31.950 --> 57:32.690
ihre Größe.

57:35.630 --> 57:39.850
Und der Aufwand, den wir hier haben, der kann also unterschiedlich

57:39.850 --> 57:42.150
groß sein oder ist abhängig von der Datenstruktur.

57:42.590 --> 57:46.710
Wenn ich eine Array habe, ist der Aufwand für den Zugriff konstant,

57:46.810 --> 57:48.110
auch der Aufwand für den Vergleich.

57:48.390 --> 57:49.790
Ich muss nur die beiden Werte vergleichen.

57:50.410 --> 57:54.210
Wenn ich einen Baum habe, dann kann es sein, dass ich erstmal den Ort

57:54.210 --> 57:56.810
finden muss, an dem mein Element liegt.

57:57.390 --> 58:00.330
Dann laufe ich halt hier durch den Pfad irgendwie durch und komme dann

58:00.330 --> 58:02.770
hier zu dem Element, auf das ich zugreifen wollte.

58:02.830 --> 58:03.910
Dann habe ich den Aufwand Log N.

58:04.870 --> 58:09.050
Der Aufwand kann linear sein, wenn Sie eine verkettete Liste haben.

58:09.150 --> 58:09.970
Da hat es schon darauf hingewiesen.

58:11.110 --> 58:16.570
Jetzt schauen wir uns die Probleme an, die wir üblicherweise lösen

58:16.570 --> 58:16.970
wollen.

58:17.690 --> 58:21.430
Ein Problem wäre, wir wollen das k-größte Element haben, das größte,

58:21.530 --> 58:24.430
zweitgrößte oder vielleicht das mittlere.

58:25.210 --> 58:30.010
Dann sagen wir, wir haben also das K von S zu berechnen, das k-größte

58:30.010 --> 58:35.130
Element unserer Liste S, Sequence S.

58:35.790 --> 58:37.350
Oder wir wollen sortieren.

58:38.490 --> 58:41.470
Das heißt, wir wollen eine Permutation vornehmen unserer eingegebenen

58:41.470 --> 58:46.230
Liste und wollen, wenn wir es aufsteigend machen, wollen wir das

58:46.230 --> 58:52.630
kleinste Element ganz vorne haben, das größte ganz hinten oder

58:52.630 --> 58:55.850
andersherum das größte ganz vorne und das kleinste ganz hinten.

58:56.910 --> 59:01.330
Das ist also eine Art, jetzt zu beschreiben, über den Rang des

59:01.330 --> 59:03.710
jeweiligen Elementes, die gleich zu anzuordnen.

59:03.710 --> 59:04.810
Das heißt, wir brauchen eine Permutation.

59:05.150 --> 59:10.070
Unsere Eingabefolge S1 bis Sn sind so umzuordnen, dass die in dieser

59:10.070 --> 59:11.310
Reihenfolge dort stehen.

59:13.490 --> 59:16.010
Das heißt, wir müssen beliebige Permutationen ausführen können.

59:16.590 --> 59:18.210
Das Permutationsnetzwerk erlaubt uns das.

59:18.290 --> 59:19.030
Können wir darüber machen.

59:19.590 --> 59:20.610
Ist auch eine Möglichkeit.

59:20.870 --> 59:24.130
Mit dem Butterschlein-Netzwerk kann man sortieren.

59:24.970 --> 59:25.570
Ist durchaus möglich.

59:28.690 --> 59:32.450
Und eine andere Sache, die wir vielleicht machen wollen, ist, wir

59:32.450 --> 59:37.490
haben zwei sortierte Listen und wollen diese zwei Listen verschmelzen

59:37.490 --> 59:39.730
zu einer längeren sortierten Liste.

59:41.370 --> 59:43.210
Sie kennen das Reißverschlussverfahren.

59:43.930 --> 59:46.670
Beim Reißverschlussverfahren, wenn zwei Fachspuren sich auf eine

59:46.670 --> 59:51.650
verengen, perfekter Reißverschluss macht immer Abwechslung, ein

59:51.650 --> 59:53.810
Element hier, eins da, eins da, eins da.

59:54.670 --> 59:57.930
Wenn wir das in Bezug auf eine lineare Ordnung machen, dann geht das

59:57.930 --> 01:00:03.830
so, zunächst mal dürfen alle BMWs aus der Spur laufen, dann dürfen

01:00:03.830 --> 01:00:07.310
alle BMWs aus der Spur laufen und so weiter, danach die VWs und danach

01:00:07.310 --> 01:00:07.990
noch irgendjemand.

01:00:08.330 --> 01:00:11.630
Also das heißt, wir haben irgendeine Anordnung, irgendeine

01:00:11.630 --> 01:00:12.290
Rangordnung.

01:00:14.090 --> 01:00:18.150
Wir dürfen hier so lange durchlaufen, bis wir ein Element erreichen,

01:00:18.550 --> 01:00:21.510
das eine niedrigere Priorität hat als das Element, das da vorne

01:00:21.510 --> 01:00:21.930
wartet.

01:00:22.490 --> 01:00:25.830
Dann dürfen die alle laufen, so lange, bis hier ein Element ist, das

01:00:25.830 --> 01:00:27.770
eine niedrigere Priorität hat als dieses hier.

01:00:27.870 --> 01:00:29.510
Dann laufen die dort wieder weiter und so weiter.

01:00:30.090 --> 01:00:33.750
Das heißt, das ist ein Reißverschlussverfahren mit Prioritäten.

01:00:35.110 --> 01:00:37.530
Und was Sie hier sofort sehen ist, so ein Verschmelzen kann ich in

01:00:37.530 --> 01:00:38.950
linearer Zeit machen, ganz einfach.

01:00:38.950 --> 01:00:42.870
Ich muss jedes Element nur einmal anschauen und kann sofort diese

01:00:42.870 --> 01:00:44.110
Verschmelzung machen.

01:00:44.470 --> 01:00:48.450
Also das ist die Aufgabe, zwei Listen zu verschmelzen zu einer

01:00:48.450 --> 01:00:53.850
Ergebnisliste, in der jedes Element vorkommt, in der richtigen

01:00:53.850 --> 01:00:54.870
Reihenfolge.

01:00:55.850 --> 01:01:00.130
Dann kann es sein, dass ich feststellen möchte, ob ein bestimmtes

01:01:00.130 --> 01:01:02.570
Element in der Menge drin ist, in der Liste.

01:01:03.810 --> 01:01:06.070
Das heißt, ich will nur wissen, ist das Element da?

01:01:06.070 --> 01:01:10.490
Gibt es einen Eintrag für irgendein Datum in einer Datenbank?

01:01:11.150 --> 01:01:12.710
Kommt also nur wahr oder falsch raus.

01:01:13.430 --> 01:01:17.250
Es kann auch sein, dass ich ein Element tatsächlich haben möchte.

01:01:17.670 --> 01:01:19.170
Möchte zugreifen auf meine Datenbank.

01:01:20.710 --> 01:01:21.930
Mache ein Search.

01:01:23.470 --> 01:01:26.690
Das heißt, da muss ich nicht nur wissen, ist das Element drin, sondern

01:01:26.690 --> 01:01:30.630
wenn es drin ist, soll auch rauskommen, der entsprechende Wert.

01:01:30.630 --> 01:01:34.310
Das heißt, wenn ich suche nach einem Rekord, nach einem Datensatz,

01:01:35.350 --> 01:01:40.590
meine Liste ist angeordnet irgendwie entsprechend eines Feldes, dann

01:01:40.590 --> 01:01:45.350
will ich das ganze Objekt haben, das zu diesem Datenfeld A gehört.

01:01:47.110 --> 01:01:48.870
Oder ich möchte etwas einfügen.

01:01:49.850 --> 01:01:51.070
Oder ich möchte etwas löschen.

01:01:53.130 --> 01:01:57.510
Oder ich möchte das kleinste oder größte Element aus der Menge

01:01:57.510 --> 01:02:00.530
entfernen.

01:02:01.690 --> 01:02:04.570
Dafür ist es praktisch, wenn man eine Hiebstruktur hat, bei der immer

01:02:04.570 --> 01:02:07.450
das Maximum hier oben ist und alle anderen unten drunter.

01:02:07.870 --> 01:02:10.910
Hier habe ich also immer größer gleich, größer gleich.

01:02:11.550 --> 01:02:14.850
Das heißt, wir haben hier immer das maximale Element oben.

01:02:14.850 --> 01:02:18.750
Dann wissen Sie, wenn Sie das maximale Element haben wollen, brauchen

01:02:18.750 --> 01:02:20.750
Sie nur das oberste Element rauszuholen.

01:02:21.070 --> 01:02:23.850
Sie müssen dann eventuell den Baum ein bisschen umbauen, damit wieder

01:02:23.850 --> 01:02:25.090
das maximale Element drin ist.

01:02:25.150 --> 01:02:26.710
Aber das ist dann eins von diesen beiden.

01:02:27.830 --> 01:02:28.290
Und so weiter.

01:02:28.730 --> 01:02:30.750
Heaps kennen Sie aus Grundlageninformatik 1.

01:02:33.930 --> 01:02:37.910
Das sind auch übliche, eine andere Statistruktur dort sind

01:02:37.910 --> 01:02:40.470
Prioritätswarteschlangen, bei denen das auch sehr einfach geht.

01:02:41.050 --> 01:02:44.690
Es könnte sein, dass Sie gar nicht wissen, ob das Element drin ist.

01:02:45.370 --> 01:02:48.170
Und Sie wollen aber auf jeden Fall ein Element haben, das dem, was Sie

01:02:48.170 --> 01:02:49.750
suchen, möglichst nahe kommt.

01:02:50.610 --> 01:02:52.550
Dann machen Sie so eine Nierabfrage.

01:02:53.410 --> 01:02:57.310
Dann brauchen Sie also eine gewisse Distanzfunktion auf den Elementen

01:02:57.310 --> 01:02:57.810
in der Menge.

01:02:58.730 --> 01:03:03.290
Und Sie suchen dann praktisch dasjenige, das möglichst nah dran ist.

01:03:04.190 --> 01:03:05.530
Sie könnten sagen, das nächstliegende.

01:03:05.530 --> 01:03:06.570
Sie können eine Grenze machen.

01:03:06.670 --> 01:03:09.710
Sie können sagen, das darf einen Abstand von maximal so und so viel

01:03:09.710 --> 01:03:09.970
haben.

01:03:10.150 --> 01:03:12.630
Es gibt zig verschiedene Varianten so einer Nierfunktion.

01:03:13.590 --> 01:03:16.750
Was Sie sehen, ist, dass es eben eine Vielfalt von Operationen gibt,

01:03:17.090 --> 01:03:18.810
oder von Problemen, die man ausführen möchte.

01:03:19.650 --> 01:03:22.830
Und wir werden uns mit denen zum Teil beschäftigen.

01:03:22.910 --> 01:03:23.350
Nicht alles.

01:03:23.850 --> 01:03:28.230
Auf jeden Fall ist es so, dass die Rechenzeit sehr, sehr hoch ist, um

01:03:28.230 --> 01:03:28.530
solche...

01:03:29.230 --> 01:03:32.970
Nicht weil es schwierige Probleme sind, sondern weil einfach viele

01:03:32.970 --> 01:03:36.530
Aufgaben damit zu tun haben, solche Probleme zu lösen.

01:03:38.230 --> 01:03:41.590
Das systematische Zugreifen auf Daten ist ein wesentlicher Punkt.

01:03:41.690 --> 01:03:46.290
Sie wissen, heutzutage gibt es ja noch wesentlich andere Sachen ganz

01:03:46.290 --> 01:03:46.810
allgemein.

01:03:46.890 --> 01:03:51.870
Die Suchmaschinen, bei denen Sie im Prinzip diese Operation ausführen

01:03:51.870 --> 01:03:54.430
auf den weltweit gespeicherten Informationen.

01:03:54.430 --> 01:03:59.350
Dafür haben wir Suchmaschinen, die ganz wesentlichen Anteil haben am

01:03:59.350 --> 01:04:01.350
Energieverbrauch für Informationsverarbeitung.

01:04:01.690 --> 01:04:05.510
Weil halt dort ständig irgendwelche Suchanfragen laufen.

01:04:06.170 --> 01:04:08.350
Das ist noch eine deutliche Zweigemeinderung dessen, was ich hier in

01:04:08.350 --> 01:04:12.370
einem sehr begrenzten Szenario behandeln werde.

01:04:15.010 --> 01:04:19.990
Jetzt ist es so, dass wir einige dieser Operationen charakterisieren

01:04:19.990 --> 01:04:22.770
als Lexikon-Operationen oder Dictionary-Operations.

01:04:22.770 --> 01:04:25.090
Also einfügen, suchen und löschen.

01:04:25.450 --> 01:04:28.290
Das Typische, was Sie mit einem Lexikon machen, da stehen irgendwelche

01:04:28.290 --> 01:04:28.990
Einträge drin.

01:04:29.670 --> 01:04:32.430
Da machen Sie auch ab und zu mal ein Update.

01:04:33.410 --> 01:04:36.030
Dann kann es sein, dass Sie Prioritätswarteschlangen sich anschauen,

01:04:36.090 --> 01:04:38.930
wo Sie immer das minimale Element rausgreifen wollen.

01:04:39.570 --> 01:04:41.810
Oder Sie wollen etwas einfügen und etwas löschen.

01:04:43.150 --> 01:04:46.470
Und es gibt noch eine ganze Reihe anderer solcher Klassifizierungen,

01:04:46.810 --> 01:04:48.490
die uns jetzt aber nicht weiter interessieren.

01:04:49.970 --> 01:04:52.530
Mit Prioritätswarteschlangen haben Sie beim Reißenschlüssel häufig

01:04:52.530 --> 01:04:53.090
auch zu tun.

01:04:55.070 --> 01:04:56.890
Komplexitätsmaß hier drin hat ich schon zur Antwort darauf

01:04:56.890 --> 01:04:57.410
hingewiesen.

01:04:57.530 --> 01:05:00.990
Bei solchen Problemen geht es um die Vergleiche von Elementen.

01:05:01.270 --> 01:05:05.790
Und das heißt, da wir nur Schlüsselvergleiche oder Attribute

01:05:05.790 --> 01:05:10.290
vergleichen, ist der Aufwand, den wir hier abschätzen müssen, im

01:05:10.290 --> 01:05:12.290
Prinzip die Pfadlänge im Entscheidungsbaum.

01:05:12.390 --> 01:05:15.050
Sie erinnern sich, wir haben hier immer irgendwelche Entscheidungen zu

01:05:15.050 --> 01:05:15.410
treffen.

01:05:15.410 --> 01:05:17.450
In jedem Knoten bei einem Entscheidungsbaum.

01:05:18.130 --> 01:05:21.350
Und je nachdem, was dort rauskommt bei diesen Entscheidungen, haben

01:05:21.350 --> 01:05:22.430
wir eine Verzweigung im Baum.

01:05:23.150 --> 01:05:28.150
Und wenn wir uns über Rechenzeiten unterhalten, geht es darum, wie

01:05:28.150 --> 01:05:31.390
sind die Pfade in diesem Baum?

01:05:31.990 --> 01:05:33.050
Wie lang sind die?

01:05:33.510 --> 01:05:36.930
Und die maximale Rechenzeit, also Rechenzeit im schlechtesten Fall,

01:05:37.010 --> 01:05:38.250
wäre die maximale Pfadlänge.

01:05:38.670 --> 01:05:41.190
Und die mittlere Rechenzeit ist die mittlere Pfadlänge im

01:05:41.190 --> 01:05:44.710
Entscheidungsbaum, der zu einem Algorithmus gehört für die Lösung

01:05:44.710 --> 01:05:48.430
eines solchen Problems.

01:05:49.170 --> 01:05:51.910
Natürlich muss ich mir anschauen, wie der Aufwand für den Zugriff auf

01:05:51.910 --> 01:05:52.670
Komponenten ist.

01:05:52.750 --> 01:05:55.070
Das war das, was wir mal mit Datenstrukturen bezeichnet hatten.

01:05:55.790 --> 01:05:59.610
Wir wissen, manche Datenstrukturen fordern linearen Aufwand, um darauf

01:05:59.610 --> 01:06:00.270
zuzugreifen.

01:06:00.730 --> 01:06:03.150
Dann ist es nicht allein die Pfadlänge, sondern müssen wir eben auch

01:06:03.150 --> 01:06:04.770
mal diesen Aufwand mit da drin berücksichtigen.

01:06:06.030 --> 01:06:09.910
Ich werde im Weiteren davon ausgehen, dass wir meistens entweder

01:06:09.910 --> 01:06:12.630
wahlfreien Zugriff haben oder einen Baum verwenden.

01:06:13.590 --> 01:06:18.810
Und wenn wir dann noch verteilte Algorithmen oder parallele

01:06:18.810 --> 01:06:21.970
Algorithmen anschauen, und bei parallelen Algorithmen schauen wir uns

01:06:21.970 --> 01:06:25.250
eben an die Anzahl der Schritte und dann auch noch Parallelitätsgrad

01:06:25.250 --> 01:06:29.110
und Effizienz und so weiter und der Zeitgewinn.

01:06:29.430 --> 01:06:31.970
Bei verteilten Algorithmen würde man nur die Anzahl der Nachrichten

01:06:31.970 --> 01:06:32.950
zählen, wie vorher auch.

01:06:34.030 --> 01:06:39.210
Also das ist nicht groß anders als bei den algebraischen Problemen.

01:06:39.870 --> 01:06:42.450
So, und jetzt gehen wir als erstes zu den Sortierverfahren, die Sie

01:06:42.450 --> 01:06:43.210
alle schon kennen.

01:06:43.690 --> 01:06:46.310
Das dauert gar nicht lange, die anzugucken.

01:06:47.250 --> 01:06:51.230
Zunächst einmal muss man überlegen, was weiß ich über eine Folge, die

01:06:51.230 --> 01:06:52.250
sortiert werden soll.

01:06:53.910 --> 01:06:57.250
Meine Folge, die reinkommt, ist mir vorher nicht bekannt.

01:06:57.850 --> 01:06:59.070
Ich weiß gar nichts darüber.

01:06:59.070 --> 01:07:03.590
Ich weiß auch nichts über die konkreten Elemente, die sortiert werden

01:07:03.590 --> 01:07:03.910
sollen.

01:07:04.290 --> 01:07:07.870
Wenn ich weiß, alle meine zu sortierenden Zahlen liegen in der Menge

01:07:07.870 --> 01:07:10.750
0, 1, 2, 3, 4.

01:07:11.510 --> 01:07:18.090
Und ich habe hier irgendeine Folge von solchen Zahlen, dann weiß ich,

01:07:18.230 --> 01:07:21.250
da tauchen nur Werte aus dieser Menge auf.

01:07:21.890 --> 01:07:27.050
Wenn ich so etwas habe, dann kann ich die Information ausnutzen.

01:07:27.050 --> 01:07:29.450
Es tauchen nur diese fünf verschiedenen Werte auf.

01:07:30.190 --> 01:07:31.930
Das kann ich ausnutzen, um zu sortieren.

01:07:32.370 --> 01:07:33.570
Das werden wir später sehen, wie das geht.

01:07:35.070 --> 01:07:38.510
Bei dem allgemeinen Sortierverfahren weiß ich nichts über die Elemente

01:07:38.510 --> 01:07:38.870
von oben.

01:07:39.270 --> 01:07:41.830
Das ist vergleichbar mit dem, was Sie bei den algebraischen Problemen

01:07:41.830 --> 01:07:42.890
gemacht haben, hatte ich gesagt.

01:07:43.270 --> 01:07:45.830
Das sind so transzendente Körpererweiterungen.

01:07:47.170 --> 01:07:49.410
Hier passiert sowas ähnliches, aber bezogen auf die

01:07:49.410 --> 01:07:50.310
Vergleichsoperation.

01:07:51.810 --> 01:07:54.470
Wir haben also hier bis nichts.

01:07:55.130 --> 01:07:58.430
Wir müssen also den Algorithmus so formulieren, dass wir nur ausnutzen

01:07:58.430 --> 01:08:01.750
können, Ergebnisse der Vergleiche von Elementen.

01:08:02.910 --> 01:08:06.190
Dadurch, dass wir zwei Elemente vergleichen, wissen wir, in welcher

01:08:06.190 --> 01:08:07.210
Relation die stehen.

01:08:08.570 --> 01:08:11.130
Und damit können wir dann weitermachen, können dann anfangen zu

01:08:11.130 --> 01:08:11.510
sortieren.

01:08:12.250 --> 01:08:15.230
Und wir nehmen an, dass wir wahlfreien Zugriff haben auf die Elemente.

01:08:15.230 --> 01:08:20.010
Wir nehmen an, wir haben eine Realisierung als Vektor oder als Feld

01:08:20.010 --> 01:08:22.070
und können wahlfrei zugreifen.

01:08:22.710 --> 01:08:26.610
Wir ignorieren also den Aufwand für den Zugriff auf die einzelnen

01:08:26.610 --> 01:08:27.210
Elemente.

01:08:27.670 --> 01:08:28.930
Wir sagen, der ist konstant.

01:08:29.990 --> 01:08:33.650
Und, jetzt machen wir das noch einfacher und sagen, wenn wir n

01:08:33.650 --> 01:08:36.310
Elemente haben, dann sind das gerade die Zahlen 1 bis n.

01:08:37.650 --> 01:08:41.230
Also unsere Grundmenge hat n Elemente.

01:08:43.070 --> 01:08:45.650
Also alle Elemente der Liste sind verschieden.

01:08:45.690 --> 01:08:47.410
Wenn sie alle verschieden sind, kann ich sie im Prinzip

01:08:47.410 --> 01:08:49.050
durchnummerieren von 1 bis n.

01:08:49.750 --> 01:08:52.570
Und dann ist das einfach die Menge der Zahlen von 1 bis n.

01:08:53.690 --> 01:08:58.170
Jetzt könnte es sein, dass ich eine Liste habe, die sieht so aus.

01:08:58.270 --> 01:09:03.610
0, 1, 1, 2, 1, 0.

01:09:05.030 --> 01:09:06.350
Da sind nicht alle verschieden.

01:09:07.470 --> 01:09:09.710
Aber ich könnte sie trotzdem durchnummerieren.

01:09:09.790 --> 01:09:13.130
1, 2, 3, 4, 5, 6.

01:09:14.850 --> 01:09:19.350
Jetzt habe ich dieser 1 hier von der 1 unterschieden durch das

01:09:19.350 --> 01:09:22.010
Auftreten in dieser Liste, die eingegeben wurde.

01:09:23.030 --> 01:09:26.570
Das heißt, jetzt könnte ich sagen, ich betrachte sie einfach so, als

01:09:26.570 --> 01:09:27.530
wären sie verschieden.

01:09:27.910 --> 01:09:32.270
Und ich möchte einfach, wenn ich die sortiere, gewährleisten, dass das

01:09:32.270 --> 01:09:36.490
Element, das zuerst auftauchte, auch in der sortierten Reihenfolge als

01:09:36.490 --> 01:09:37.410
erstes auftaucht.

01:09:37.770 --> 01:09:41.050
Das heißt, ich unterscheide diese drei Einzelnen bezüglich ihres

01:09:41.050 --> 01:09:42.270
Auftretens in der Folge.

01:09:42.790 --> 01:09:44.650
Und dann habe ich wieder nur verschiedene Elemente.

01:09:46.170 --> 01:09:49.510
Das heißt, ich kann ohne Beschränkung der Allgemeinheit sagen, ich

01:09:49.510 --> 01:09:50.590
betrachte nur verschiedene Elemente.

01:09:51.190 --> 01:09:54.410
Wir werden später sehen, wenn das nicht der Fall ist, muss man

01:09:54.410 --> 01:09:57.030
manchmal ein bisschen aufpassen, aber erst mal vereinfachen, dass das

01:09:57.030 --> 01:09:57.870
Leben doch deutet.

01:09:59.570 --> 01:10:03.670
Und jetzt kommen im Schnelldurchgang ein paar Verfahren, die Sie im

01:10:03.670 --> 01:10:06.390
Prinzip kennen, aus Grundlagen der Informatik 1.

01:10:06.730 --> 01:10:09.990
Aber ich will einfach ein paar Effekte darstellen.

01:10:10.710 --> 01:10:13.210
Ich will Ihnen ja auch parallele Algorithmen vorstellen.

01:10:13.490 --> 01:10:18.630
Dann werden wir gleich sehen, was hier für Dinge wichtig sind.

01:10:18.770 --> 01:10:19.890
Sortieren durch Auswahl.

01:10:20.430 --> 01:10:21.510
Algorithmus kennen Sie.

01:10:21.510 --> 01:10:28.910
Ich möchte einfach sukzessive sortieren, indem ich das Minimum der

01:10:28.910 --> 01:10:29.850
Folge berechne.

01:10:31.250 --> 01:10:34.490
Und dann, dass als erstes hinschreibt, möchte aufsteigend sortieren.

01:10:35.350 --> 01:10:37.830
Und wenn ich mir hier ein Beispiel angucke...

01:10:37.830 --> 01:10:42.350
Ups, da ist jetzt die Formatierung leider verrutscht durch das

01:10:42.350 --> 01:10:45.050
Überführen in ein neues Format der Folien.

01:10:45.490 --> 01:10:46.790
Habe ich hier nicht aufgepasst.

01:10:47.950 --> 01:10:49.410
Hier ist unsere Eingangsfolge.

01:10:51.030 --> 01:10:52.450
Das ist die Eingangsfolge.

01:10:52.570 --> 01:10:56.810
Und jetzt werden hier als nächstes die Folgen entstehen daraus.

01:10:57.390 --> 01:11:01.350
Wir haben die 1 gefunden als Minimum, das ist unser erstes Element.

01:11:02.070 --> 01:11:04.630
Suchen dann das Minimum der Restfolge.

01:11:05.210 --> 01:11:07.330
Wir finden die 2, das ist das zweite Element.

01:11:07.550 --> 01:11:09.330
Suchen das Minimum der Restfolge.

01:11:09.790 --> 01:11:12.450
Das ist die 3, das Minimum der Restfolge, die 4.

01:11:12.950 --> 01:11:14.570
Das Minimum der Restfolge, die 5.

01:11:15.070 --> 01:11:15.670
Und das sind wir fertig.

01:11:16.350 --> 01:11:18.030
Das sortieren wir durch Auswahl.

01:11:18.090 --> 01:11:21.310
Wir wählen jeweils das Minimalelement der Folge, die noch zu

01:11:21.310 --> 01:11:22.070
betrachten ist.

01:11:22.550 --> 01:11:24.630
Und können das an die definierte Position schreiben.

01:11:25.690 --> 01:11:26.610
Wie hoch ist der Aufwand?

01:11:27.530 --> 01:11:28.330
Ganz einfach.

01:11:29.090 --> 01:11:31.530
Der Aufwand, um alle diese minimal zu bestimmen.

01:11:33.750 --> 01:11:35.770
Also N mal Aufwand für ein Minimum.

01:11:36.330 --> 01:11:40.210
Wobei die Folge, in der wir das betrachten, jeweils um 1 kleiner wird.

01:11:44.150 --> 01:11:48.370
Und intuitiv, wenn ich ein Minimum betrachten will, muss ich ja jedes

01:11:48.370 --> 01:11:49.210
Element angucken.

01:11:49.310 --> 01:11:51.890
Um zu sehen, ob ein Element, das mir herausgreift, immerhin, ich

01:11:51.890 --> 01:11:53.550
schätze, dass die 2 das Minimum ist.

01:11:54.230 --> 01:11:57.290
Und wenn ich bei der 1 bin, habe ich Pech gehabt, da ist nicht die 2.

01:11:57.430 --> 01:12:00.270
Ich muss natürlich feststellen, da ist ein Element, das kleiner ist.

01:12:01.030 --> 01:12:02.110
Aber Sie wissen, wie man das macht.

01:12:02.190 --> 01:12:04.110
Man läuft einfach von links nach rechts hier durch.

01:12:04.110 --> 01:12:08.030
Und vergleicht die einfach miteinander.

01:12:08.450 --> 01:12:11.770
Und merkt sich immer das kleinste Gesehene.

01:12:12.270 --> 01:12:13.670
Und am Ende hat man das Minimum bestimmt.

01:12:14.290 --> 01:12:15.030
N-Vergleiche.

01:12:15.110 --> 01:12:15.710
Ganz einfach.

01:12:15.790 --> 01:12:19.770
Oder N-1-Vergleiche für das Minimum in der Folge von N Elementen.

01:12:19.910 --> 01:12:20.990
Ganz einfaches Verfahren.

01:12:22.250 --> 01:12:25.270
Die Frage ist, ist das ausreichend?

01:12:25.370 --> 01:12:26.230
Geht das nicht schneller?

01:12:26.570 --> 01:12:28.790
Das war ein naives Verfahren.

01:12:30.250 --> 01:12:31.530
Kann ich das schneller machen?

01:12:33.150 --> 01:12:36.730
Und ein ganz einfaches Lemma sagt, ich brauche mindestens N-1

01:12:36.730 --> 01:12:37.490
-Vergleiche.

01:12:38.030 --> 01:12:39.590
Für die Bestimmung des Minimums.

01:12:39.990 --> 01:12:41.170
Oder des Maximums.

01:12:42.230 --> 01:12:43.130
Es geht nicht schneller.

01:12:45.170 --> 01:12:47.910
Also in einer Folge von N Elementen natürlich.

01:12:48.330 --> 01:12:49.230
Wie kann ich das beweisen?

01:12:50.650 --> 01:12:53.570
Ich muss jetzt eine Aussage machen über beliebige Algorithmen.

01:12:53.670 --> 01:12:56.130
Ich kann nicht sagen, ich kann das mit dem Algorithmus mit N-1

01:12:56.130 --> 01:12:56.590
vergleichen.

01:12:56.670 --> 01:12:57.170
Das reicht nicht.

01:12:58.130 --> 01:12:59.750
Ich muss einen beliebigen Algorithmus mir hin.

01:12:59.750 --> 01:13:03.510
Und ich sage jetzt ganz einfach, das ist ein Wettkampf zwischen N

01:13:03.510 --> 01:13:03.990
Spielern.

01:13:05.550 --> 01:13:08.450
Ich habe N Tennisspieler, die spielen gegeneinander und ich möchte den

01:13:08.450 --> 01:13:09.190
Besten haben.

01:13:10.410 --> 01:13:12.490
Was ist die Eigenschaft des besten Spielers?

01:13:13.210 --> 01:13:14.950
Der Beste, der darf nie verlieren.

01:13:16.670 --> 01:13:21.030
Der Spieler, der nie verloren hat, ist besser als Spieler, die

01:13:21.030 --> 01:13:22.450
mindestens einmal verloren haben.

01:13:22.450 --> 01:13:28.870
Es müssen N-1 Spieler mindestens einmal verlieren.

01:13:29.530 --> 01:13:34.390
Damit ein Spieler der einzige ist, der nie verloren hat.

01:13:37.350 --> 01:13:38.950
Das sind N Spieler insgesamt.

01:13:39.050 --> 01:13:41.290
N-1 Spieler müssen mindestens einmal verloren haben.

01:13:41.790 --> 01:13:43.550
Egal nach welchem Verfahren sie das machen.

01:13:44.930 --> 01:13:46.850
Und wenn sie verlieren, heißt das, sie spielen.

01:13:48.390 --> 01:13:52.810
Also haben wir hier mindestens N-1 Vergleiche.

01:13:53.790 --> 01:13:56.830
Pro Spiel verliert ja genau einer, der andere gewinnt.

01:13:57.850 --> 01:13:59.730
Und deswegen haben sie mindestens N-1 Spiele.

01:14:00.490 --> 01:14:01.430
Und das war's.

01:14:02.490 --> 01:14:04.550
Egal, wie sich die Vergleiche anordnen.

01:14:05.250 --> 01:14:07.090
Sie brauchen immer mindestens N-1.

01:14:12.070 --> 01:14:15.230
Das heißt, Zeitaufwand fürs Minimum ist linear.

01:14:15.730 --> 01:14:19.890
Und damit haben wir sofort den Aufwand für Sortieren durch Auswahl,

01:14:19.970 --> 01:14:21.390
ist dann N².

01:14:23.050 --> 01:14:29.610
Also das ist dann die Einfach-Summe der Zahl von 0 bis N-1.

01:14:31.090 --> 01:14:32.750
Also ganz schlechtes Verfahren.

01:14:34.210 --> 01:14:35.450
Auch im Mittel geht es nicht besser.

01:14:37.250 --> 01:14:39.390
Erwartungswert bleibt auch noch quadratisch.

01:14:40.830 --> 01:14:44.050
Und parallel geht es natürlich...

01:14:44.050 --> 01:14:46.690
Ich muss es ja nicht unbedingt so machen, dass ich durch so eine

01:14:46.690 --> 01:14:49.550
Liste, wenn ich hier meine Elemente habe...

01:14:53.770 --> 01:14:54.130
irgendwie...

01:14:54.130 --> 01:15:00.410
S1, S2, S3, S4, S5, S6, S7, S8.

01:15:00.590 --> 01:15:02.530
Ich muss ja nicht von links nach rechts da durchlaufen.

01:15:03.190 --> 01:15:04.270
Danach wieder von links nach rechts.

01:15:04.350 --> 01:15:06.450
Ich kann es natürlich auch so machen, dass ich das so mache.

01:15:06.750 --> 01:15:10.850
So, so, so, und dann so nochmal, da nochmal, und da.

01:15:10.890 --> 01:15:11.510
Das ist ja viel schneller.

01:15:12.070 --> 01:15:13.910
Anzahl der Vergleiche ist N-1.

01:15:14.890 --> 01:15:17.390
Parallel mache ich diese Vergleiche alle gleichzeitig.

01:15:17.390 --> 01:15:18.750
Die auch gleichzeitig.

01:15:19.210 --> 01:15:22.370
Das heißt, da habe ich nur Lock-In-Schritte zu machen.

01:15:23.770 --> 01:15:24.770
Besser kann es ja nicht gehen.

01:15:24.890 --> 01:15:29.150
Ich muss ja hier diese Vergleiche machen.

01:15:30.210 --> 01:15:33.310
Und es können ja maximal N-Halbe gleichzeitig spielen.

01:15:34.870 --> 01:15:36.570
Wie will ich das besser machen?

01:15:36.750 --> 01:15:37.930
Das hat diesen Fan-In.

01:15:39.210 --> 01:15:42.230
Und jetzt überlegt man sich, ob das wirklich so ist, dass das nicht

01:15:42.230 --> 01:15:42.830
besser geht.

01:15:44.470 --> 01:15:46.310
Im realen Leben geht es nicht besser.

01:15:47.390 --> 01:15:51.630
Da brauchen Sie Lock-In-Runden, um die Spieler alle spielen zu lassen.

01:15:52.030 --> 01:15:53.690
Im Rechner können wir das ein bisschen anders machen.

01:15:54.050 --> 01:15:57.350
Im Rechner haben wir nämlich die Möglichkeit, dass wir uns klonen.

01:15:58.730 --> 01:16:03.270
Wenn wir das bei Tennis machen könnten mit den Spielern, wäre das

01:16:03.270 --> 01:16:04.270
einfacher, dann geht es besser.

01:16:04.450 --> 01:16:05.170
Wir sehen gleich warum.

01:16:06.150 --> 01:16:07.950
Hier kann ich parallel das Minimum bestimmen.

01:16:11.150 --> 01:16:12.810
Also, hier steht es schon.

01:16:13.590 --> 01:16:15.470
Konstant in drei Schritten.

01:16:15.870 --> 01:16:17.090
Was steht hier für ein Verfahren?

01:16:18.750 --> 01:16:21.730
Ich baue mir ein Feld auf.

01:16:22.850 --> 01:16:24.950
Also Speicher i.

01:16:26.430 --> 01:16:34.330
Also ich habe hier i0, i1 und so weiter bis in.

01:16:35.970 --> 01:16:39.050
Und ich schreibe dann überall eine Null rein.

01:16:42.310 --> 01:16:43.190
Das ist der erste Schritt.

01:16:43.850 --> 01:16:45.330
Eine Null im Register e von i.

01:16:47.070 --> 01:16:54.350
Und jetzt vergleiche ich die Elemente si und sj.

01:16:56.530 --> 01:17:00.250
Wenn ich si und sj vergleiche, das mache ich für alle i und j.

01:17:02.090 --> 01:17:05.570
Für alle vergleiche aus von si und sj.

01:17:05.770 --> 01:17:09.770
Jetzt sehen Sie schon, hier brauche ich jetzt die Fähigkeit, dass ein

01:17:09.770 --> 01:17:11.750
Spieler mehrfach vorhanden ist.

01:17:12.110 --> 01:17:15.650
Weil ich jedes Element mit allen anderen vergleiche.

01:17:16.570 --> 01:17:18.050
Das kann ich parallel alles machen.

01:17:18.610 --> 01:17:20.230
Ich nehme an, dass ich parallel zugreifen kann.

01:17:21.050 --> 01:17:22.570
Ich vergleiche also si und sj.

01:17:23.470 --> 01:17:29.990
Und wenn si größer als sj ist, dann schreibe ich da eine 1 rein.

01:17:30.910 --> 01:17:37.650
Also wenn ich hier eine Liste habe, 2, 5, 3, 1 oder sowas.

01:17:39.070 --> 01:17:41.250
Dann würde ich alle Vergleiche durchführen.

01:17:43.230 --> 01:17:47.150
Das ist hier s1, s2, s3, s4.

01:17:48.130 --> 01:17:50.850
Ich würde 2 mit 5 vergleichen, da tue ich nichts.

01:17:51.530 --> 01:17:53.810
2 mit 3 passiert auch nichts.

01:17:53.810 --> 01:17:59.610
S2 mit 1, da muss ich eine 1 in e...

01:18:00.510 --> 01:18:04.510
Also eine 1 in ei, falls si größer als sj.

01:18:05.790 --> 01:18:06.350
In ei.

01:18:09.330 --> 01:18:16.530
si ist 1 und sj ist...

01:18:16.530 --> 01:18:18.810
Das ist größer als...

01:18:18.810 --> 01:18:20.410
Genau, da kommt eine 1 rein.

01:18:20.670 --> 01:18:23.370
Es ist s1 größer als sj.

01:18:23.670 --> 01:18:27.630
Also schreibe ich hier entsprechend bei s1 eine 1 rein.

01:18:29.550 --> 01:18:31.630
Und so mache ich das für alle anderen auch.

01:18:31.990 --> 01:18:34.470
Also hier habe ich dann bei...

01:18:34.470 --> 01:18:38.430
Also 5 wird verglichen mit 2.

01:18:39.730 --> 01:18:42.710
Bei 5 muss ich also auch eine 1 reinschreiben und so weiter.

01:18:43.050 --> 01:18:47.050
5 ist aber größer als 2, als 3, als 1.

01:18:47.050 --> 01:18:53.530
Es schreiben also mehrere, wenn wir uns hier e2 angucken, da schreiben

01:18:53.530 --> 01:18:54.710
mehrere eine 1 rein.

01:18:56.330 --> 01:19:04.670
Alle Prozessoren, die das Element s2 vergleichen mit irgendeinem sj,

01:19:05.350 --> 01:19:09.890
schreiben in s2 eine 1 rein, weil das das größte Element ist.

01:19:11.630 --> 01:19:18.210
Wenn ich aber die Vergleiche mir anschaue, s4 mit irgendeinem sj, dann

01:19:18.210 --> 01:19:23.510
werde ich für alle Vergleiche feststellen, dass s4 nie größer als sj

01:19:23.510 --> 01:19:24.050
ist.

01:19:24.590 --> 01:19:31.770
Also bleibt bei e4 die 0 stehen.

01:19:35.740 --> 01:19:42.360
Das heißt, bei s4 habe ich den Effekt, dass es niemals größer war als

01:19:42.360 --> 01:19:43.120
irgendein anderes.

01:19:44.100 --> 01:19:45.680
Und das heißt, es ist das kleinste Element.

01:19:45.820 --> 01:19:48.200
Es hat in diesem Sinne nie verloren.

01:19:49.160 --> 01:19:50.940
Es war nie größer.

01:19:52.240 --> 01:19:58.080
Und jetzt schreibe ich einfach für alle i aus n, jeder Prozessor guckt

01:19:58.080 --> 01:20:00.960
nach, was steht in dem entsprechenden ei drin.

01:20:00.960 --> 01:20:06.160
Wenn dort eine 0 drin steht, dann schreibt er den Index hier rein.

01:20:06.680 --> 01:20:12.500
Da steht also noch eine 0 drin, dann wird hier reingeschrieben eine 1.

01:20:13.380 --> 01:20:13.880
Nee, Quatsch.

01:20:13.940 --> 01:20:15.180
Er schreibt hier den Index rein.

01:20:15.320 --> 01:20:16.160
4 schreibe ich da rein.

01:20:17.700 --> 01:20:22.440
Und dann weiß ich anschließend, in e0 steht der Index des Elements,

01:20:22.960 --> 01:20:23.880
dass das Minimum ist.

01:20:24.520 --> 01:20:30.580
Das ist das einzige Element, das niemals in der Situation war, dass es

01:20:30.580 --> 01:20:31.720
größer war als ein anderes.

01:20:32.020 --> 01:20:34.680
Das heißt, bei der Bestimmung des Minimums hat es gewonnen.

01:20:36.920 --> 01:20:42.520
Und damit habe ich drei Schritte, nach denen der Index des Minimums in

01:20:42.520 --> 01:20:43.120
e0 steht.

01:20:44.220 --> 01:20:47.520
Das Ganze erfordert natürlich einiges an Fähigkeiten der

01:20:47.520 --> 01:20:48.200
Rechnerstruktur.

01:20:48.200 --> 01:20:50.380
Jetzt habe ich hier das übereinander geschrieben.

01:20:52.220 --> 01:20:55.820
Sie können es trotzdem noch lesen und da es ja aufgezeichnet ist, ist

01:20:55.820 --> 01:20:56.400
es nicht weiter schlimm.

01:20:58.660 --> 01:21:02.020
Es erfordert natürlich Größenordnung N² Vergleiche.

01:21:02.080 --> 01:21:04.900
Ich mache alle Vergleiche si und sj.

01:21:06.140 --> 01:21:06.900
Hoher Aufwand.

01:21:08.260 --> 01:21:10.620
Und ich muss natürlich gleichzeitig lesen können.

01:21:10.740 --> 01:21:14.320
Ich muss jedes Element in N Vergleichen anwenden.

01:21:15.160 --> 01:21:17.080
Und ich muss gleichzeitig schreiben können.

01:21:17.940 --> 01:21:24.020
Aber alle Prozessoren, die schreiben, schreiben das Gleiche, weil

01:21:24.020 --> 01:21:28.280
alle, die in so einer Situation sind, dass si größer als j ist,

01:21:28.420 --> 01:21:32.380
schreiben in das Register ei, den wir in eins schreiben.

01:21:33.140 --> 01:21:35.600
Das heißt, wenn einer sowas schreiben will, schreibt er eine eins.

01:21:36.200 --> 01:21:39.180
Alle das Gleiche, also reicht es, wenn einer schreibt, es ist einfach

01:21:39.180 --> 01:21:40.760
zu lösen, dieser Schreibkonflikt.

01:21:42.520 --> 01:21:46.660
Und bei dem letzten Schritt hier, oder bei diesem Schritt hier, Nummer

01:21:46.660 --> 01:21:52.240
3, da schreibt derjenige, bei dem das ei gleich 0 ist.

01:21:52.940 --> 01:21:57.160
Das kann aber nur einer sein, weil alle anderen mindestens einmal

01:21:57.160 --> 01:21:59.160
verloren haben.

01:21:59.220 --> 01:22:02.160
Und das heißt, also mindestens einmal größer waren als dieses Minimum,

01:22:02.260 --> 01:22:05.240
das heißt, bei allen anderen steht eine eins drin, nur bei einem steht

01:22:05.240 --> 01:22:06.880
eine 0 drin und dieser eine schreibt.

01:22:07.580 --> 01:22:09.000
Das heißt, ich habe hier keinen Konflikt.

01:22:09.000 --> 01:22:15.320
Ich habe also bei einer PRAM mit Concurrent Read, Concurrent Write und

01:22:15.320 --> 01:22:20.680
der Common Schreibregel, habe ich also die Möglichkeit, in drei

01:22:20.680 --> 01:22:25.020
Schritten das Minimum zu bestimmen, egal wie groß meine Folge ist,

01:22:25.120 --> 01:22:30.800
sofern ich genügend parallele Möglichkeiten habe, meine Vergleiche

01:22:30.800 --> 01:22:31.300
auszuführen.

01:22:31.400 --> 01:22:33.980
Ich brauche halt n Quadratvergleiche, die gleichzeitig ausgeführt

01:22:33.980 --> 01:22:36.420
werden müssen, was eine ziemlich hohe Anforderung ist.

01:22:36.420 --> 01:22:40.160
Aber prinzipiell heißt das, ich kann in konstanter Zeit das Minimum

01:22:40.160 --> 01:22:43.120
bestimmen, wenn ich genügend Rechenressourcen zur Verfügung stelle.

01:22:45.120 --> 01:22:51.980
Effizienz ist natürlich nur 1 durch n, weil ich erreiche eine

01:22:51.980 --> 01:23:00.580
Reduktion von n auf 1, von Linearzeit auf konstante Zeit, aber mit n

01:23:00.580 --> 01:23:01.640
Quadratprozessoren.

01:23:01.640 --> 01:23:04.100
Das heißt, die Effizienz ist nur 1 durch n.

01:23:04.960 --> 01:23:06.280
Parallelitätsgrad ist n Quadrat.

01:23:07.540 --> 01:23:09.660
Und damit habe ich eine sehr schlechte Effizienz.

01:23:10.140 --> 01:23:11.960
Aber es geht im Prinzip in konstanter Zeit.

01:23:13.540 --> 01:23:17.300
Gut, das also zu diesem kleinen Ausflug.

01:23:17.480 --> 01:23:19.080
Parallele Bestimmung des Minimums.

01:23:19.420 --> 01:23:22.520
Und wir haben konstante Zeit für das Minimum.

01:23:22.960 --> 01:23:27.020
Müssen das, wenn wir das sortieren, durch Auswahl machen, aber n mal

01:23:27.020 --> 01:23:27.380
machen.

01:23:28.420 --> 01:23:30.380
Und dann haben wir immer noch Linearzeit.

01:23:30.600 --> 01:23:33.600
Also das ist kein guter Ansatz für parallele Sortieren.

01:23:34.420 --> 01:23:35.440
Da kommen wir später noch drauf.

01:23:36.300 --> 01:23:37.500
Sortieren durch Einfügen.

01:23:38.140 --> 01:23:39.120
Auch das kennen Sie.

01:23:40.080 --> 01:23:44.080
Ich habe einfach die Idee, dass ich mir eine Folge hernehme.

01:23:44.200 --> 01:23:46.440
Das ist meine Folge, die sortiert werden soll.

01:23:47.360 --> 01:23:50.720
Und ich füge die einfach der Reihe nach in eine leere Liste ein.

01:23:51.240 --> 01:23:54.440
Fange mit dem ersten Element an, die 2, danach kommt die 5, dann kommt

01:23:54.440 --> 01:23:55.160
die 1.

01:23:55.160 --> 01:23:58.760
Jetzt steht die 1 nicht dahinter, die muss ganz nach vorne geschoben

01:23:58.760 --> 01:23:59.160
werden.

01:23:59.620 --> 01:24:02.760
Dann muss ich die 5 und die 2 jeweils um 1 nach rechts schieben.

01:24:03.220 --> 01:24:06.560
Dann kommt die 3, die passt auch nicht an die Stelle, da muss ich also

01:24:06.560 --> 01:24:08.620
in dem Fall die 5 um 1 nach rechts schieben.

01:24:09.340 --> 01:24:11.260
Dann kommt die 6, die ist schon richtig.

01:24:11.840 --> 01:24:14.600
Und dann kommt die 4 und dann muss ich die 6 und die 5 um 1 nach

01:24:14.600 --> 01:24:15.000
rechts schieben.

01:24:16.100 --> 01:24:19.580
Das geht also offensichtlich ganz schnell.

01:24:20.420 --> 01:24:23.160
Mit relativ wenig Verschiebungen und Vergleichen.

01:24:23.700 --> 01:24:26.660
Ich muss ja nur immer vergleichen mit dem Element, das als letztes

01:24:26.660 --> 01:24:27.220
hier steht.

01:24:28.800 --> 01:24:32.300
Und wenn das Element ein Stück kleiner ist, muss ich das mit dem

01:24:32.300 --> 01:24:32.880
vertauschen.

01:24:34.440 --> 01:24:43.360
Und wenn ich Glück habe, da ist mir etwas verrutscht.

01:24:45.660 --> 01:24:47.660
Also, wo sollte das denn jetzt hin?

01:24:49.260 --> 01:24:50.720
Hier ist mir etwas verrutscht.

01:24:50.720 --> 01:24:54.120
Im schlechtesten Fall suchen wir mal die richtige Position für diese

01:24:54.120 --> 01:24:54.560
Formel.

01:24:55.500 --> 01:24:58.640
Die ist mir beim Einfügen, beim Umformatieren leider verrutscht.

01:24:59.080 --> 01:24:59.740
Habe ich nicht gesehen.

01:25:00.460 --> 01:25:02.720
Also das ist der Aufwand für den schlechtesten Fall.

01:25:03.480 --> 01:25:04.080
Das ist klar.

01:25:05.620 --> 01:25:12.460
N², weil ich eben im schlechtesten Fall gerade jedes Mal I-Vergleiche

01:25:12.460 --> 01:25:12.860
machen muss.

01:25:13.320 --> 01:25:15.140
Das passt also genau dazu.

01:25:16.040 --> 01:25:19.260
Ich habe halt quadratisch viele Vergleiche zu machen.

01:25:19.260 --> 01:25:23.500
Im Mittel muss ich gerade immer so zur Hälfte etwa laufen.

01:25:24.180 --> 01:25:27.980
Das ist genauso quadratisch insgesamt.

01:25:29.280 --> 01:25:32.360
Also, im Mittel haben wir hier auch noch quadratische Zeit.

01:25:34.260 --> 01:25:37.360
Im besten Fall habe ich hier aber einen Vorteil.

01:25:37.420 --> 01:25:41.880
Im besten Fall muss ich nur jeweils mit dem letzten Element

01:25:41.880 --> 01:25:42.440
vergleichen.

01:25:42.520 --> 01:25:44.240
Ich habe bereits die sortierte Reihenfolge.

01:25:44.720 --> 01:25:46.560
Dann geht das in linearer Zeit.

01:25:48.080 --> 01:25:52.080
Bei Sortieren durch Auswahl war auch der beste Fall quadratisch.

01:25:52.400 --> 01:25:54.360
Weil ich immer das Minimum bestimmt habe.

01:25:54.420 --> 01:25:55.680
Ich musste immer ganz durchlaufen.

01:25:56.220 --> 01:25:58.420
Das heißt, ich habe dort in jedem Fall quadratische Zeit.

01:25:59.060 --> 01:26:01.680
Hier habe ich im besten Fall lineare Zeit.

01:26:02.160 --> 01:26:02.720
Interessant.

01:26:03.400 --> 01:26:06.380
Es gibt eine ziemliche Bandbreite.

01:26:07.300 --> 01:26:10.420
Bester Fall linear, schlechtester Fall quadratisch, mittlerer Fall

01:26:10.420 --> 01:26:11.380
quadratisch.

01:26:12.480 --> 01:26:14.360
Dann kommt Bubble Sort.

01:26:14.480 --> 01:26:16.520
Das will ich Ihnen noch kurz darstellen.

01:26:16.620 --> 01:26:19.520
Das kennen Sie auch aus Anfänger-Vorlesungen.

01:26:20.040 --> 01:26:20.800
Bubble Sort.

01:26:21.120 --> 01:26:22.420
Nehmen Sie nur fest an, dass Sie das kennen.

01:26:22.620 --> 01:26:23.680
Auch einfaches Verfahren.

01:26:24.680 --> 01:26:28.380
Sie machen hier sukzessive immer so ein Blasen-Sortieren.

01:26:28.480 --> 01:26:29.900
Blasen steigen im Wasser auf.

01:26:30.400 --> 01:26:33.860
Also die Idee ist, dass die leichten Elemente nach oben steigen.

01:26:34.580 --> 01:26:37.200
Das heißt, Sie vergleichen hier 4 und 6.

01:26:37.340 --> 01:26:39.000
Dann müssen die hier vertauscht werden.

01:26:39.000 --> 01:26:41.680
Dann vergleichen Sie hier weiter.

01:26:44.200 --> 01:26:46.080
Hier muss die 1 nach oben wandern.

01:26:48.980 --> 01:26:51.900
Und dann muss die 1 nochmal nach oben wandern.

01:26:53.000 --> 01:26:55.120
Und dann geht das Ganze von vorne los.

01:26:55.720 --> 01:26:56.860
Wir müssen hier wieder vergleichen.

01:26:56.940 --> 01:26:58.620
Da wandert die 4 nach oben.

01:26:59.180 --> 01:27:02.420
Dann wandert die...

01:27:02.420 --> 01:27:04.000
Na, wo haben wir hier...

01:27:04.880 --> 01:27:06.460
Da muss eigentlich gar nichts mehr passieren.

01:27:06.520 --> 01:27:07.080
Das ist schon alles.

01:27:07.300 --> 01:27:08.280
Und dann sind wir schon fertig.

01:27:08.280 --> 01:27:11.820
Aber wir laufen im Prinzip immer von unten nach oben durch.

01:27:11.940 --> 01:27:14.740
Vergleichen immer nebeneinander liegende Elemente.

01:27:15.320 --> 01:27:18.540
Und schieben praktisch das kleinere Element immer nach oben.

01:27:19.120 --> 01:27:21.000
Das heißt, es wandern die kleinen Elemente nach oben.

01:27:21.100 --> 01:27:22.700
Deswegen nennt man das eben Bubblesort.

01:27:23.480 --> 01:27:26.480
Das Problem ist, wir haben hier eine zweifach geschachtelte Schleife.

01:27:27.480 --> 01:27:29.400
Und da ist kein Abbruch drin.

01:27:29.960 --> 01:27:32.220
Wir laufen praktisch immer von unten nach oben durch.

01:27:32.320 --> 01:27:34.760
Natürlich nicht immer bis ganz oben, weil das kleinste Element nach

01:27:34.760 --> 01:27:36.160
der ersten Runde schon ganz oben ist.

01:27:36.160 --> 01:27:41.180
Wir haben Vertauschungsoperationen zu machen, wenn das also nicht

01:27:41.180 --> 01:27:42.500
stimmt in der Reihenfolge.

01:27:43.600 --> 01:27:45.780
Und wir haben hier also wieder quadratisches Verhalten.

01:27:46.780 --> 01:27:48.260
Jetzt kann man das Ganze...

01:27:48.620 --> 01:27:51.080
Das ist also ganz klar, dass wir hier für quadratisches Verhalten

01:27:51.080 --> 01:27:52.320
haben.

01:27:52.380 --> 01:27:55.420
Man kann das Ganze verbessern, indem man in dem Augenblick, wo nicht

01:27:55.420 --> 01:27:56.680
mehr vertauscht wird, aufhört.

01:27:57.180 --> 01:27:59.420
Wenn ich also feststelle, beim ersten Durchlaufen, ich habe nichts

01:27:59.420 --> 01:28:00.520
vertauscht, bin ich fertig.

01:28:00.700 --> 01:28:01.400
Linearer Aufwand.

01:28:02.000 --> 01:28:03.780
Bester Fall, linearer Aufwand geht also.

01:28:03.780 --> 01:28:09.300
Ich kann abwechselnd praktisch einmal von unten nach oben, dann von

01:28:09.300 --> 01:28:10.720
oben nach unten und so weiter.

01:28:11.460 --> 01:28:15.040
Und habe dann auch eine Verbesserung.

01:28:15.440 --> 01:28:17.820
Manchmal, das ist etwas, was man Shaker Sort nennt.

01:28:18.360 --> 01:28:19.620
Auch ein interessantes Verfahren.

01:28:20.360 --> 01:28:22.800
Aber ich bleibe im schlechtesten Fall bei n².

01:28:23.480 --> 01:28:24.520
Das kriege ich hier nicht raus.

01:28:25.220 --> 01:28:28.360
Und wie man das parallel macht, werde ich Ihnen nächstes Mal

01:28:28.360 --> 01:28:28.920
vorstellen.

01:28:28.920 --> 01:28:32.440
Der Optimum Transposition Sort ist also ein Verfahren, das kann ich

01:28:32.440 --> 01:28:33.600
Ihnen hier schon zeigen.

01:28:34.300 --> 01:28:38.640
Da haben wir ein Verfahren, das Linearzeit braucht.

01:28:39.480 --> 01:28:44.740
Im schlechtesten Fall immer Linearzeit braucht, mit n Prozessoren.

01:28:45.340 --> 01:28:48.800
Das heißt, wir sind von n² runter auf n mit n Prozessoren.

01:28:49.320 --> 01:28:53.640
Ist aber kein optimaler Zeitgewinn, weil das beste sequenzielle

01:28:53.640 --> 01:28:55.320
Verfahren Zeit n log n braucht.

01:28:56.060 --> 01:28:57.760
Wir kommen darauf dann später nochmal zurück.

01:28:57.760 --> 01:29:01.940
Das interessante ist aber, dass dieses Verfahren Optimum Transposition

01:29:01.940 --> 01:29:05.600
Sort, das ich Ihnen nächstes Mal vorstelle, auf der Basis von Bubble

01:29:05.600 --> 01:29:09.600
Sort, auf linearen Feldern optimal ist.

01:29:10.580 --> 01:29:13.600
Das heißt, wir haben für bestimmte Infrastrukturen hier ein optimales

01:29:13.600 --> 01:29:15.000
Verfahren, das sehr einfach ist.

01:29:15.740 --> 01:29:17.160
Das war's für heute, vielen Dank.

01:29:17.940 --> 01:29:21.400
Nächste Woche geht's weiter mit Bubble Sort und weiteren interessanten Sortierverfahren.