WEBVTT

00:00.000 --> 00:07.440
Also, schönen guten Tag! Wir wollen weitermachen mit effizienten Algorithmen.

00:08.800 --> 00:12.220
Ich begrüße auch diejenigen, die die Vorlesung nicht live verfolgen.

00:12.640 --> 00:20.000
Offensichtlich steigt die Zahl derjenigen, die die Vorlesung in der gespeicherten, in der aufgezeichneten Version sich anschauen.

00:20.660 --> 00:27.700
Also, letztes Mal haben wir uns einiges angeschaut, was algebraische Probleme anging.

00:27.700 --> 00:29.280
Wir hatten ja vieles hier schon gemacht.

00:29.820 --> 00:31.520
Ich gehe hier mal ganz schnell durch.

00:32.380 --> 00:33.100
Was haben wir denn?

00:33.580 --> 00:34.080
Ach du Jemine!

00:35.680 --> 00:42.900
Wir hatten uns sehr viel, oder einige Matrix-Multiplikationsverfahren betrachtet.

00:43.100 --> 00:47.560
Wir hatten den systematischen Entwurf von Algorithmen angeschaut.

00:47.760 --> 00:50.680
Wir hatten Polynome ausgewertet.

00:52.620 --> 00:55.000
Wir hatten dann auch hier untere Schranken gesehen.

00:55.080 --> 00:57.080
Wir hatten gesehen, wie schön das Horner-Schema ist.

00:58.780 --> 01:02.060
Dann hatten wir uns die schnelle Fourier-Transformation vorgenommen.

01:02.240 --> 01:07.720
Auch da gesehen, dass man die sehr effizient machen kann.

01:08.520 --> 01:20.480
Dass es eine effiziente Art und Weise ist, wie man Polynome auswerten kann an n Stellen.

01:20.600 --> 01:21.960
Also, Polynome enden gratis.

01:22.400 --> 01:26.800
Nämlich mit Aufwand n log n und nicht n², wie die naive Methode das sagen würde.

01:28.260 --> 01:34.800
Wir haben uns das auf eine schnelle Art und Weise genau angeschaut.

01:34.980 --> 01:40.240
Und gesehen, dass wir hier so ein schönes Netzwerk kriegen, das viele schöne Eigenschaften hat.

01:40.340 --> 01:46.860
Nämlich ein Permutationsnetzwerk, das beliebige Permutationen unterstützt.

01:46.980 --> 01:55.280
Das heißt, von jedem Punkt auf der linken Seite gibt es genau ein Pfad zu jedem Punkt auf der rechten Seite.

01:55.280 --> 02:00.920
Und das war die letzte Folie dieses Kapitels.

02:01.780 --> 02:06.280
Und wir haben dann anschließend uns das Kapitel 4 vorgenommen.

02:07.340 --> 02:09.310
Das war der Einschub über die Lösung von Rekurrenzgleichungen.

02:10.660 --> 02:20.680
Wo ich Ihnen noch einmal die Art von Gleichungen aufgeschrieben habe, die man bekommt, wenn man divide-and-conquer-Probleme bearbeitet.

02:20.680 --> 02:23.920
Beziehungsweise wenn man divide-and-conquer-Verfahren analysiert.

02:24.360 --> 02:27.120
Da hat man halt gerade diese typischen Rekurrenzgleichungen.

02:27.660 --> 02:33.120
K-Teilprobleme der Größe n durch c und irgendeinen Aufwand, um aufzuteilen und wieder zusammenzusetzen.

02:33.600 --> 02:34.880
Also Lösungen zusammenzusetzen.

02:35.560 --> 02:41.480
Und wir hatten dann uns einmal diese Standardlösungsansätze angeschaut.

02:41.620 --> 02:45.640
Und ich hatte Ihnen einen allgemeinen Ansatz vorgestellt.

02:45.640 --> 02:54.460
Das sogenannte Master-Theorem, das uns für allgemeinere Fälle angibt, welche Funktionen dabei herauskommen.

02:55.000 --> 02:56.820
Und wir hatten uns das auch an einem Beispiel angeschaut.

02:56.940 --> 02:59.640
Hier unten drei Beispiele hatten wir betrachtet.

03:00.580 --> 03:05.460
Und dann gesehen, die Anwendung des Master-Theorems lieferte uns sofort das Ergebnis.

03:06.600 --> 03:13.340
Das eine war also dann quadratisch, weil hier halt die 9 gerade Quadrat von 3 ist.

03:13.340 --> 03:22.660
Und deswegen war das der entsprechende Fall A und so weiter.

03:22.800 --> 03:24.120
Wir hatten uns die anderen beiden Fälle auch angeschaut.

03:24.260 --> 03:31.040
Und beim dritten Fall hatten wir festgestellt, dass die Funktion n log n weder Fall B noch Fall C ist.

03:31.120 --> 03:37.240
Weil halt log n langsamer wächst als jede Potenz von n.

03:37.760 --> 03:39.280
Und deswegen passt das da nicht rein.

03:39.280 --> 03:44.920
Da muss man sich dann eine weitere Art der Auflösung überlegen.

03:45.020 --> 03:48.720
Ist nicht weiter schwer, aber das fällt halt nicht unter dieses Master-Theorem.

03:50.160 --> 03:53.860
So, man kann es zwar natürlich nach oben abschätzen, aber das hilft einem dann auch nicht viel.

03:54.240 --> 03:55.980
Es gibt dann eine zu große obere Schranke.

03:57.160 --> 04:04.100
Und das war dann schon das Ende von diesem Abschnitt.

04:04.100 --> 04:07.400
Da habe ich nämlich verwiesen auf weitere Beispiele.

04:07.820 --> 04:10.960
Auf das Buch von Corman Lysogon Rivers.

04:11.280 --> 04:14.220
Beziehungsweise ich könnte auch auf den neuen Übungszettel verweisen.

04:14.620 --> 04:16.940
Auf dem nämlich auch ein paar Aufgaben dazu drin stehen.

04:17.960 --> 04:23.260
Ja, da sollen ein paar solche Rekurrenzgleichungen dann mal genauer bearbeitet werden.

04:23.600 --> 04:28.940
Also gelöst werden unter Verwendung dieser Aussagen, die wir hier kennengelernt haben.

04:28.940 --> 04:38.300
Das war also ein Einschub über etwas, was ja eigentlich aus Informatik 1 schon hätte bekannt sein können.

04:38.740 --> 04:41.820
Zumindest ein Teil ist dort ganz kurz angesprochen worden.

04:42.780 --> 04:44.100
Es steht zumindest ein Skript drin.

04:44.260 --> 04:46.700
Wie weit das wirklich in der Vorteilung angesprochen wurde, weiß ich natürlich nicht.

04:46.780 --> 04:47.520
Aber ich nehme es an.

04:48.360 --> 04:55.420
Und es ist halt, wie gesagt, Standardart von Analysegleichungen, die man kriegt bei die weiteren Conquer-Verfahren.

04:55.420 --> 04:58.760
Und die sind ja sehr zahlreich in der Informatik vertreten.

04:59.400 --> 05:02.500
Und dann gehen wir gleich in den nächsten Bereich rein.

05:02.800 --> 05:03.860
Suchen und Sortieren.

05:04.020 --> 05:07.160
Eines der Lieblingsthemen der Informatiker.

05:08.300 --> 05:09.180
Suchen und Sortieren.

05:09.240 --> 05:11.760
Nicht weil wir so unordentliche Menschen sind und ständig suchen und sortieren.

05:12.320 --> 05:23.380
Sondern weil einfach dieses Problem des Suchen und Sortierens zu den Hauptaufgaben zählt, die in der Praxis auftreten.

05:23.380 --> 05:29.840
Wenn Sie sich anschauen, was Sie irgendwo in einer Bank machen müssen und in irgendeinem Unternehmen,

05:29.920 --> 05:33.620
Sie werden immer wieder das Problem haben, wenn Sie irgendwie auf Daten zugreifen,

05:33.680 --> 05:40.120
in der systematischen Art und Weise, dass Sie die Daten erstmal in irgendeine sortierte Reihenfolge bringen.

05:40.740 --> 05:45.560
Dann ist auch der Zugriff auf diese Daten einfacher.

05:46.700 --> 05:50.600
Und Sie werden häufig eben auch das Problem haben, dass Sie suchen müssen,

05:50.600 --> 05:56.220
nach irgendwelchen Elementen feststellen müssen, ob ein Element in einer Datenmenge oder in einer Folge drin ist oder nicht.

05:57.420 --> 06:03.960
Und dann muss man sehen, welche Datenstruktur wählt man eigentlich, damit das effizient geschehen kann.

06:04.820 --> 06:06.220
Damit wollen wir uns jetzt beschäftigen.

06:06.800 --> 06:15.480
Also es ist nochmal etwas, was uns, wenn wir Informationsverarbeitung machen, ständig begegnet.

06:15.900 --> 06:18.160
Und deswegen macht es Sinn, sich das genauer anzugucken.

06:18.160 --> 06:21.460
Worum es geht, sind also Elemente einer geordneten Menge.

06:22.220 --> 06:27.380
Wenn wir über Suchen reden, muss es nicht unbedingt geordnet sein.

06:27.460 --> 06:29.740
Wenn wir keine Ordnungsrelationen haben, wird das Suchen aber sehr schwer.

06:30.840 --> 06:34.700
Wenn wir keine weiteren Informationen haben, müssten wir wirklich die Elementenliste in Einzelnen durchgehen.

06:35.280 --> 06:38.640
Wir nehmen es deswegen zumindest an, dass wir eine geordnete Menge haben.

06:38.740 --> 06:41.660
Das heißt, wir können hier zwei Elemente auf ihre Größe vergleichen.

06:43.100 --> 06:46.940
Das ist also das, was wir normalerweise voraussetzen.

06:48.360 --> 06:58.760
Wir haben unsere Objekte aus einer geordneten Menge U.

06:58.980 --> 07:02.460
Das ist also unsere Menge U und die Ordnung ist eine kleine Gleichrelation.

07:04.660 --> 07:06.700
Aber es sind alle vergleichbar.

07:08.940 --> 07:15.680
Wir können also für je zwei Elemente feststellen, ob sie in dieser kleinen Gleichrelation sind.

07:15.800 --> 07:18.320
Ob es eine kleine ist, eine kleine gleich oder ob es größer ist.

07:18.920 --> 07:20.460
Was für Mengen sind das normalerweise?

07:20.560 --> 07:23.860
Das kann sein ein Such- oder Sortierschlüssel.

07:24.400 --> 07:29.020
Kennen Sie aus Informatik 2, Dateiorganisation, da haben wir Schlüssel behandelt.

07:29.160 --> 07:31.780
Beim Suchen und Sortieren redet man auch von Schlüsseln.

07:31.780 --> 07:45.180
Wenn Sie einen größeren Datensatz haben, mit vielen Feldern drin, dann ist es eben wichtig, ein Feld zu haben, nachdem Sie suchen.

07:46.020 --> 07:50.640
Nachdem Sie alles anordnen. Das kann irgendeines mit drin sein, kann auch das erste sein, darauf kommt es gar nicht an.

07:50.740 --> 07:57.680
Sie müssen halt irgendein Feld haben, ein Attribut, das Sie für Suchen verwenden bzw. nachdem Sie die Datensätze sortieren.

07:57.680 --> 08:01.880
Und das können sein irgendwelche Namen, das können Zahlen sein.

08:03.140 --> 08:14.220
Es kann aber auch sein, dass wir diese Sätze einfach als Rekord, als größeren Datensatz auffassen und wir müssen halt nur diese Ordnung drauf haben.

08:14.500 --> 08:15.000
Das ist alles.

08:15.920 --> 08:21.440
Und wenn wir Beispiele betrachten, dann betrachten wir natürlich immer Beispiele, bei denen wir einfache Zahlen verwenden.

08:22.600 --> 08:25.780
In der Praxis sind das die seltensten Fälle.

08:27.140 --> 08:33.180
Weil die Objekte, die in der Praxis sortiert werden oder nach denen gesucht wird, das sind irgendwelche größeren Datensätze.

08:34.340 --> 08:40.520
Nur das, was wir konkret uns in den Algorithmen angucken, ist immer irgendein Feld dieses Datensatzes, um die Vergleiche machen zu können.

08:40.620 --> 08:48.140
Deswegen können wir uns jetzt in der Vorlesung darauf beschränken, im Wesentlichen uns solche Folgen aus Zahlen anzuschauen.

08:49.560 --> 08:58.960
Weil das eigentlich das Wesentliche ausmacht. Alles andere können wir wegschieben in die Realität.

09:01.760 --> 09:05.260
Ich will jetzt nicht sagen, dass das Theorie ist. Natürlich ist es auch Theorie.

09:05.460 --> 09:10.320
Aber wir brauchen uns nicht mit diesen anderen Sachen zu belasten, wenn wir nur die Such- und Sortierverfahren anschauen.

09:10.840 --> 09:16.120
Das wäre unnötige Belastung, die uns Arbeit macht, die gar nicht notwendig ist.

09:16.860 --> 09:20.720
So, dann haben wir Records. Das hatte ich schon gesagt.

09:21.620 --> 09:23.420
Problemgröße ist die Länge der Liste.

09:25.120 --> 09:27.440
Das heißt, die Größe der Listen-Elemente wird ignoriert.

09:27.560 --> 09:32.540
Wir gehen davon aus, dass wir nur die Anzahl der Elemente zählen.

09:32.900 --> 09:36.390
Das heißt, 32-Bit-Schlüssel werden betrachtet.

09:37.060 --> 09:42.260
Wir zählen nur die Anzahl der Listen-Elemente.

09:42.860 --> 09:48.980
Wenn es die Listen-Elemente, die in der Realität große Sätze sind, dann müsste man das berücksichtigen.

09:49.080 --> 09:50.560
Deswegen habe ich das hier erwähnt.

09:50.840 --> 09:55.920
Bevor man daran geht, jetzt in der Praxis eine Aufwandsanalyse zu machen, muss man sich anschauen,

09:56.720 --> 10:00.000
wie sehen eigentlich meine Daten-Elemente der Liste aus.

10:00.120 --> 10:09.760
Sind das kleine Elemente, also konstanter Größe, oder sind das irgendwelche großen Listen-Elemente, die man auch noch berücksichtigen muss.

10:10.680 --> 10:13.600
Normalerweise zählen wir nur die Anzahl der Objekte in der Liste.

10:14.560 --> 10:18.830
Die Datenstruktur, die wir verwenden, da gibt es verschiedene Möglichkeiten.

10:19.580 --> 10:21.040
Das werden wir auf verschiedene Arten kennenlernen.

10:21.620 --> 10:28.480
Wenn das ein Array ist, wie hier oben, oder auch ein Vektor, können wir wahlfrei zugreifen.

10:28.600 --> 10:37.850
Das heißt, wir können z.B. auf A von 2 zugreifen und würden dann hier auf das entsprechende Element der Liste zugreifen.

10:37.850 --> 10:40.490
Wenn wir mit 0 anfangen, wäre es das dritte Element.

10:41.790 --> 10:50.570
Oder wir können sagen, wir haben eine linear verkettete Liste, Datenstruktur mit sequenziellem Zugriff.

10:51.290 --> 10:53.830
Auch das ist keineswegs so ungewöhnlich.

10:54.270 --> 11:00.590
Das kann natürlich auch auftauchen, gerade wenn Sie größere Datensätze haben, die in so einer Liste vorkommen.

11:00.590 --> 11:04.930
Dann hätten Sie also hier irgendwo ein Element, und da dran ist ein Zeiger.

11:05.590 --> 11:10.770
Noch ein Element, da ist auch ein Zeiger dran, und dieser Zeiger zeigt halt auf das nächste Element.

11:12.330 --> 11:12.990
Und so weiter.

11:15.050 --> 11:17.170
Das wäre eine linear verkettete Liste.

11:18.530 --> 11:21.890
Und dann könnte es sein, dass Sie vielleicht hier noch ein Feld haben.

11:24.650 --> 11:28.870
Und dieses andere Feld, das zeigt jeweils zurück.

11:30.830 --> 11:32.890
Dann hätten Sie eine doppelt verkettete Liste.

11:33.950 --> 11:42.190
Auch diese Datenstrukturen gibt es, bei denen man halt in der Lage ist, vorwärts und rückwärts durch die Liste durchzulaufen.

11:42.370 --> 11:42.950
Das ist völlig klar.

11:43.830 --> 11:50.790
Wenn Sie einen Algorithmus entwerfen, ist es durchaus entscheidend, ob Sie direkt auf ein Element zugreifen können,

11:50.790 --> 11:57.590
oder ob Sie das über solche verketteten Strukturen machen müssen.

12:00.050 --> 12:01.850
Das dritte, der Baum.

12:01.970 --> 12:05.510
Nun, das ist auch klar, wenn wir die Elemente als Baum anordnen,

12:07.230 --> 12:11.830
dann hätten wir eben zum Beispiel so eine Struktur.

12:13.670 --> 12:19.830
Wir könnten hier jeweils auf linken und rechten Nachfolger verweisen.

12:22.810 --> 12:25.190
Ich sollte mich ein bisschen ordentlicher malen.

12:25.270 --> 12:27.250
Also, das sind jeweils die Nachfolger.

12:28.270 --> 12:32.330
Und es ist offensichtlich, wenn man hier auf ein Element zugreifen will,

12:32.930 --> 12:37.130
dann, wenn man einen solchen vollständigen Baum hat, wie ich ihn hier angedeutet habe,

12:37.130 --> 12:44.130
dann ist natürlich der Pfad zu jedem Element in diesem Baum deutlich kürzer,

12:44.350 --> 12:48.050
als wenn Sie eine linear verkettete Liste haben.

12:48.630 --> 12:53.030
Also für Suchverfahren braucht man solche Bäume, solche Baumstrukturen.

12:53.310 --> 12:56.550
Damit werden wir uns noch, allerdings relativ kurz, beschäftigen.

12:58.630 --> 13:00.950
Das sollten Sie alles aus Informatik 1 kennen.

13:01.750 --> 13:06.030
Sie sind, alle drei, die hier sind, keine Informationswörter?

13:07.010 --> 13:08.310
Nicht, okay.

13:09.850 --> 13:13.150
So, welche Operationen werden wir ausführen auf solchen Listen?

13:14.790 --> 13:17.130
Der Zugriff auf die Komponenten ist klar.

13:18.170 --> 13:20.670
Wir müssen auf eine Komponente zugreifen können.

13:20.890 --> 13:22.810
Wir wollen Komponenten vergleichen.

13:22.870 --> 13:25.550
Ich habe jetzt hier oben gesagt, select li.

13:25.830 --> 13:29.190
Das heißt, es kann natürlich sein, dass so ein Zugriff auf die i-Komponente bedeutet,

13:29.190 --> 13:32.130
wir müssen durch so eine Liste von vorne bis zu der Position durchlaufen.

13:32.490 --> 13:33.990
Kann auch sein, wir können direkt darauf zugreifen.

13:35.010 --> 13:45.250
Vergleich der Komponenten hängt natürlich von der gewählten Datenstruktur ab.

13:45.550 --> 13:48.250
Wenn wir zwei Komponenten vergleichen wollen,

13:48.530 --> 13:52.250
dann ist der Aufwand dafür in der Regel konstant im Array.

13:54.210 --> 13:56.230
Warum logarithmisch im Baum?

13:56.230 --> 13:58.810
Weil wir zugreifen müssen auf die Elemente im Baum.

13:59.010 --> 14:00.590
Das ist jeweils logarithmischer Aufwand.

14:01.550 --> 14:06.690
Und dann ist der Aufwand, um zwei Elemente zu vergleichen,

14:07.370 --> 14:10.470
nicht wegen der Schwierigkeit, den Vergleich durchzuführen,

14:10.530 --> 14:12.750
sondern wegen der Schwierigkeit, auf die Elemente zuzugreifen,

14:13.790 --> 14:16.030
dann in der Größenordnung log n.

14:16.610 --> 14:19.570
Und in einer verketteten Liste kann der Aufwand schon linear sein,

14:19.610 --> 14:21.210
weil wir auf die Elemente zugreifen müssen.

14:21.210 --> 14:29.430
Also insofern ist es beim Zugriff klar, dass wir da die Unterschiede haben,

14:29.570 --> 14:31.670
aber beim Vergleich wirkt es dann halt genauso aus.

14:33.930 --> 14:35.610
Welche Probleme schauen wir uns an?

14:35.730 --> 14:39.230
Ich hatte schon gesagt, Such- und Sortierprobleme sind typische Probleme,

14:40.130 --> 14:42.010
die wir in der Praxis vorliegen haben.

14:42.330 --> 14:44.390
Wir gehen aus von einer Liste der Länge n

14:44.390 --> 14:48.870
und wollen jetzt zum Beispiel das größte Element finden in dieser Liste.

14:48.870 --> 14:51.970
Oder das zweitgrößte, oder drittgrößte, oder viertgrößte.

14:52.430 --> 14:53.870
Oder das mittlere Element.

14:54.630 --> 14:55.770
Den Median zu bestimmen.

14:55.890 --> 15:00.910
Wichtige Aufgabe, wenn Sie z.B. die mittleren Studienzeiten von Studenten feststellen wollen,

15:00.990 --> 15:03.810
da müssen Sie den Median nehmen normalerweise, was häufig nicht gemacht wird.

15:04.190 --> 15:08.150
Nur wir wissen, wie schnell wird etwa die Hälfte der Studierenden fertig.

15:08.370 --> 15:10.230
Deswegen muss man den Median nehmen, das mittlere Element.

15:10.710 --> 15:12.830
Wenn Sie das arithmetische Mittel der Studienzeiten nehmen würden,

15:12.930 --> 15:16.990
hätten Sie eventuell einen ganz anderen Wert.

15:16.990 --> 15:18.730
Also, das k-größte Element.

15:19.350 --> 15:22.110
Also größte, zweitgrößte, drittgrößte und so weiter.

15:23.470 --> 15:25.270
Dann will ich sortieren können.

15:25.690 --> 15:30.690
Also, ich will entweder in nicht fallende oder nicht wachsende Ordnung sortieren.

15:31.230 --> 15:34.410
Also ich habe hier einfach geschrieben, sort kleinergleich oder sort größergleich.

15:35.050 --> 15:37.510
Wobei ich das meistens weglasse, dies kleinergleich oder größergleich.

15:38.850 --> 15:39.890
Sort kleinergleich.

15:40.250 --> 15:42.570
Jetzt habe ich einfach verwendet die Notation, die hier oben steht.

15:42.770 --> 15:43.770
Dieses K von S.

15:44.990 --> 15:47.630
Das k-größte, also das n-größte ist das erste.

15:47.810 --> 15:50.410
Das n-größte bei der Liste von L-Elementen ist das kleinste.

15:51.910 --> 15:52.030
Ja?

15:53.170 --> 15:56.210
Und das n-erstgrößte ist das zweitkleinste.

15:56.490 --> 15:58.530
Und so weiter. Und das 1 von S ist das größte.

15:58.690 --> 16:03.850
Das heißt, hier sind die so aufsteigend angeordnet.

16:04.230 --> 16:08.190
Wenn wir annehmen, dass die Elemente nicht alle verschieden sein müssen,

16:08.610 --> 16:10.250
dafür muss ich sagen, nicht fallend.

16:10.310 --> 16:11.910
Es kann ja sein, dass sie alle gleich sind.

16:13.770 --> 16:16.350
Ja, wenn Sie eine Liste mit nur gleichen Elementen haben,

16:16.490 --> 16:18.850
dann soll es eben nicht fallend sein.

16:18.950 --> 16:20.930
Genauso hier oben, hier unten.

16:21.390 --> 16:23.910
Das soll nicht wachsend sein.

16:25.070 --> 16:29.190
Das heißt, das größte zuerst, zweitgrößte dahinter und so weiter.

16:30.350 --> 16:31.990
Das wären die Sortiermöglichkeiten.

16:32.490 --> 16:34.510
Dann kann es sein, dass ich zwei Listen verschmelzen muss.

16:34.650 --> 16:39.050
Sie haben Hörer von zwei Vorlesungen,

16:40.170 --> 16:44.270
die Klausuren geschrieben haben und Sie wollen eine gemeinsame Liste aussägen.

16:44.330 --> 16:46.630
Oder von zwei Übungsgruppen, die müssen verschmolzen werden.

16:47.050 --> 16:51.890
Dann müssen wir die beiden Folgen zusammenfügen in sortierter Reihenfolge.

16:52.370 --> 17:00.490
Also eine gemeinsame Liste machen zu einer solchen Liste R1 bis Rn plus M.

17:00.990 --> 17:03.270
Wobei ich hier nicht angegeben habe,

17:03.270 --> 17:12.050
dass R1 bis Rn plus M in nicht fallender Ordnung sortiert sein sollen.

17:12.130 --> 17:15.410
Also gleiche Ordnung wie die beiden sortierten Listen S und T.

17:17.710 --> 17:22.890
Dann möchte ich feststellen, ob ein Element A aus U,

17:23.010 --> 17:25.410
also irgendein Element meines Universums,

17:26.750 --> 17:28.210
Element einer Liste ist.

17:28.430 --> 17:32.530
Ist das überhaupt abgespeichert? Studiert ein Student in meiner Vorlesung?

17:33.290 --> 17:36.230
Also, Member-Operation.

17:37.550 --> 17:41.790
Oder ich möchte ein Element holen aus einer Liste.

17:42.770 --> 17:44.910
Das eine ist festzustellen, ist es drin?

17:45.830 --> 17:47.290
Da kommt die Antwort ja oder nein.

17:48.550 --> 17:51.410
Das andere ist, ich möchte das Element tatsächlich haben.

17:51.530 --> 17:53.810
Also diesen Datensatz möchte ich mir rausholen aus der Liste.

17:53.910 --> 17:56.310
Dann habe ich halt diese Search-Operation.

17:56.970 --> 17:58.790
Das Element soll tatsächlich rausgeholt werden.

17:59.610 --> 18:01.130
Da bekomme ich also entweder das Element

18:01.710 --> 18:03.750
oder die Aussage, es ist nicht drin.

18:06.290 --> 18:09.070
Gegenteil, ich möchte, obwohl es nicht ganz das Gegenteil ist.

18:09.310 --> 18:14.030
Search holt mir das Element raus, lässt es aber im Prinzip natürlich in der Folge drin,

18:14.310 --> 18:15.370
löscht es dabei nicht.

18:17.090 --> 18:19.070
Man kann sich genauso gut eine Operation vorschlummern,

18:19.150 --> 18:22.890
der so ein Rausholen heißt, aus der Liste löschen.

18:24.730 --> 18:29.730
Einfügen heißt, ich möchte also ein Element A aus U in die Liste einfügen.

18:30.790 --> 18:32.870
Da kann es sein, dass das schon drin ist.

18:33.470 --> 18:34.950
Muss man sich überlegen, was passiert dann?

18:35.670 --> 18:38.510
Wenn es schon drin ist, wird es dann doppelt drin sein?

18:38.650 --> 18:42.030
Oder ist es dann nur einmal drin?

18:42.250 --> 18:45.550
Wenn Sie sich jetzt überlegen, beim Datensatz, bei Datensätzen,

18:45.630 --> 18:47.410
wenn jedes Element einem Datensatz entspricht

18:49.230 --> 18:52.230
und das, was eingefügt wird, bezieht sich auf den Schlüssel,

18:53.310 --> 18:55.630
dann ist es durchaus so,

18:55.870 --> 19:00.290
dass Sie mehrere Datensätze mit dem gleichen Schlüssel drin haben können.

19:00.950 --> 19:02.970
Die können durchaus unterschiedlich sein.

19:03.070 --> 19:04.450
Aber das muss man sich genau überlegen.

19:05.070 --> 19:09.210
Was passiert, wenn das Element, das eingefügt werden soll,

19:09.330 --> 19:11.390
schon in der Liste verzeichnet ist?

19:14.250 --> 19:16.970
Dann die Operation, dass wir etwas löschen wollen.

19:18.090 --> 19:21.030
Ein Element A soll aus der Liste gelöscht werden.

19:22.650 --> 19:25.810
Auch für den Fall, dass das Element nicht in der Liste ist,

19:25.970 --> 19:28.490
muss eine sinnvolle Operation ausgeführt werden.

19:30.690 --> 19:37.690
Dann kann es sein, dass ich nicht das Element 17 aus der Liste löschen möchte,

19:37.750 --> 19:39.930
sondern ich möchte das kleinste löschen.

19:42.090 --> 19:44.810
Oder das größte Element löschen.

19:45.070 --> 19:48.790
Typische Operation, wenn Sie sich an Heapsort erinnern,

19:48.790 --> 19:51.010
aus der Vorlesung Informatik 1,

19:51.850 --> 19:58.050
da werden nacheinander die größten Elemente rausgeholt.

19:58.410 --> 20:03.570
Es gibt viele Anwendungen, wo Sie die größten oder kleinsten Elemente haben müssen.

20:04.210 --> 20:06.850
Wenn Sie an Operations Research denken,

20:06.970 --> 20:08.890
da haben Sie Scheduling-Verfahren kennengelernt,

20:08.970 --> 20:15.770
bei denen Prioritäts-gestützte Scheduling-Verfahren oder Heuristiken eingesetzt wurden,

20:15.770 --> 20:18.110
um Abläufe zu planen.

20:18.610 --> 20:22.410
Und da hat man immer eine Menge von möglichen nächsten Aktionen

20:22.410 --> 20:26.490
und Sie brauchen da eben die mit der größten Priorität.

20:27.350 --> 20:28.450
Das ist genau so eine Operation.

20:28.750 --> 20:34.030
Sie müssen da x-max oder x-min von S berechnen und das Element dann auch rauslöschen.

20:36.090 --> 20:40.290
Oder Sie sagen, ich möchte gerne ein Element in meiner Liste haben.

20:41.170 --> 20:44.350
Ich weiß, an welchem Element ich eigentlich interessiert bin,

20:44.350 --> 20:47.330
aber wenn das nicht genau drin ist, dann nehme ich das nächstliegende.

20:48.910 --> 20:53.830
Also ich möchte gerne eine Zahl haben, die möglichst nah an 15 liegt.

20:54.350 --> 20:56.870
Und wenn in der Liste halt 15 nicht drin ist,

20:56.970 --> 21:00.610
dann bin ich mit 16 oder mit 14 auch zufrieden.

21:01.210 --> 21:05.090
Und dazu muss ich natürlich eine Distanzfunktion auf U haben.

21:05.230 --> 21:06.850
Nicht nur vergleichen können,

21:06.930 --> 21:09.910
sondern ich muss auch die Distanz von Elementen bestimmen können,

21:09.990 --> 21:12.330
damit ich diese Nier-Operation angeben kann.

21:13.410 --> 21:16.770
Das sind die Probleme, die in der Praxis auftauchen.

21:16.870 --> 21:19.010
Es gibt sicherlich noch eine Vielzahl weiterer Probleme,

21:20.410 --> 21:24.710
aber das ist so eine Standardliste von Problemen, die man sich anschaut,

21:24.790 --> 21:26.610
wenn man von Such- und Sortierproblemen redet.

21:28.870 --> 21:32.890
Und diese Zahl, circa ein Drittel der Rechenzeit kommerzieller Rechner,

21:34.130 --> 21:36.230
geistert seit langem durch die Literatur.

21:36.670 --> 21:38.170
Ich habe es nicht selber gemessen,

21:38.170 --> 21:42.230
aber das war also schon vor langer Zeit so.

21:43.690 --> 21:46.030
Und das wird auch heute noch so sein,

21:46.130 --> 21:50.610
dass dies mit die Aufgaben sind, die am häufigsten in Rechnern erledigt werden.

21:51.210 --> 21:54.070
Und deswegen ist es elementar wichtig,

21:55.030 --> 21:58.850
diese Aufgaben möglichst kostengünstig erledigen zu können.

21:59.350 --> 22:01.070
Wenn Sie diese Aufgaben im Griff haben,

22:01.610 --> 22:04.410
dann ist schon mal ein wichtiger Teil Ihrer Informationsverarbeitung,

22:04.470 --> 22:07.390
was die Kosten angeht, gut aufgestellt.

22:07.390 --> 22:11.630
Und deswegen macht es Sinn, sich anzuschauen,

22:11.730 --> 22:13.350
was es da für Möglichkeiten gibt.

22:18.330 --> 22:22.650
Dann habe ich hier noch ein paar weitere Operationen.

22:23.850 --> 22:28.490
Also einige dieser Operationen werden auch zusammengefasst

22:28.490 --> 22:32.690
zu einer Klasse von Operationen, Lexikon-Operationen,

22:33.270 --> 22:37.990
sind so diese Einfüge-, Such- und Lösch-Operationen.

22:38.050 --> 22:41.250
Das ist das, was Sie in einem Lexikon normalerweise machen, in einem Verzeichnis.

22:41.830 --> 22:44.530
Sie fügen irgendeinen neuen Eintrag ein

22:44.530 --> 22:47.850
und überschreiben damit eventuell schon vorhandene.

22:48.430 --> 22:51.110
Sie suchen etwas, Sie schlagen nach im Lexikon

22:51.110 --> 22:52.770
oder Sie löschen etwas aus dem Lexikon.

22:53.550 --> 22:55.670
Und dann gibt es eben die Prioritätswarteschlang.

22:56.430 --> 22:58.090
Das hatte ich schon gerade eben erwähnt.

22:58.090 --> 23:02.430
Bei irgendwelchen prioritätsregelbasierten Heuristiken,

23:02.530 --> 23:05.190
da brauchen Sie solche Dinge, dass Sie das X-Min bestimmen können,

23:05.270 --> 23:07.510
dass Sie etwas einfügen oder auch etwas löschen können.

23:10.470 --> 23:14.130
Das Komplexitätsmaß in dem Fall, also was messen wir eigentlich?

23:14.450 --> 23:16.250
Wie bewerten wir die Kosten?

23:16.430 --> 23:18.570
Ich hatte gesagt, wir wollen Elemente vergleichen.

23:19.590 --> 23:23.130
Da ist es völlig irrelevant, ob wir addieren, subtrahieren,

23:23.230 --> 23:26.090
multiplizieren oder dividieren können, zumindest normalerweise.

23:27.290 --> 23:30.690
Da wir nur davon ausgehen, dass wir eine Menge haben

23:30.690 --> 23:35.490
mit einer kleinen Gleichoperation, ist es völlig klar,

23:35.570 --> 23:36.850
das Einzige, was wir machen können, ist,

23:36.990 --> 23:41.030
dass wir die Anzahl der Vergleiche zählen.

23:41.610 --> 23:45.430
Und ich hatte Ihnen schon ganz zu Beginn bei Berechnungsmodellen gesagt,

23:45.530 --> 23:47.510
ein Modell wären eben die Entscheidungsbäume.

23:48.530 --> 23:52.530
Und das heißt, wenn wir uns hier irgendeinen Baum betrachten,

23:52.530 --> 24:00.570
dann ist die Länge des Pfades in diesem Entscheidungsbaum

24:00.570 --> 24:05.210
das Maß, das uns interessiert als Kosten für die Ausführung einer Operation.

24:06.270 --> 24:08.570
Wie viele Vergleiche müssen nacheinander ausgeführt werden,

24:09.090 --> 24:10.830
damit das Problem gelöst ist?

24:12.770 --> 24:16.730
Auch hier müssen wir natürlich den Aufwand für die Zugriffe berücksichtigen.

24:17.610 --> 24:18.810
Das werden wir entsprechend machen.

24:20.250 --> 24:25.090
Wenn man sich jetzt nochmal anschaut, die anderen Berechnungsmodelle,

24:25.190 --> 24:28.050
nämlich parallele Algorithmen, verteilte Algorithmen,

24:29.370 --> 24:39.870
da wird natürlich nach wie vor als Zeitmaß die Anzahl der Schritte genommen

24:43.070 --> 24:46.550
und bei verteilten Algorithmen die Anzahl der Nachrichten.

24:46.550 --> 24:50.030
Das ist natürlich unabhängig von dem, was wir gerade eben berücksichtigt haben.

24:50.250 --> 24:52.610
Wenn wir sequenzielle Algorithmen anschauen, ist klar,

24:52.690 --> 24:55.530
wir gucken nur die Art der Operationen, die ausgeführt werden.

24:56.130 --> 24:59.570
Diese Operationen tauchen natürlich genauso bei den parallel verteilten Algorithmen auf.

24:59.750 --> 25:03.750
Aber was uns da eben vor allen Dingen interessiert bei den parallelen Algorithmen ist,

25:03.850 --> 25:05.870
wie können wir die Anzahl der Schritte reduzieren

25:05.870 --> 25:09.830
im Vergleich zur sequenziellen Variante eines Algorithmus.

25:11.950 --> 25:13.870
So, und ich fange an mit Sortierverfahren.

25:14.710 --> 25:16.710
Vieles kennen Sie hiervon.

25:16.990 --> 25:18.830
Da gehe ich relativ schnell durch.

25:18.990 --> 25:21.510
Sie haben alle Informatik 1 gemacht oder Informatik A.

25:22.050 --> 25:23.950
Das sind in Sortierverfahren vorgestellt worden,

25:24.510 --> 25:29.790
als Beispiel für Algorithmen, für einfache Algorithmen,

25:29.950 --> 25:32.070
als Beispiele, wie man diese analysieren kann.

25:32.970 --> 25:36.630
Und ich muss hier nochmal ganz kurz durchgehen, damit wir den richtigen Einstieg finden.

25:37.150 --> 25:40.050
Zunächst mal, was ist eigentlich die Basis?

25:41.690 --> 25:46.010
Wir nehmen an, dass wir nichts über die Listen wissen,

25:46.170 --> 25:48.450
als eben, dass sie vergleichbar sind.

25:49.070 --> 25:52.050
Deswegen nennen wir dies auch allgemeine Sortierverfahren.

25:53.150 --> 25:57.080
Das heißt, uns ist nichts bekannt, außer wir können die Elemente vergleichen.

25:58.090 --> 26:01.690
Dann nehmen wir an, dass wir die Liste als Array realisiert haben.

26:01.770 --> 26:02.970
Wir machen uns das Leben leicht.

26:03.990 --> 26:06.170
Direkter Zugriff. Wahlfreier Zugriff.

26:08.210 --> 26:11.570
Und wir nehmen an, das macht uns auch das Leben leicht,

26:11.750 --> 26:13.170
alle Elemente sind verschieden.

26:13.970 --> 26:19.290
Eine Liste der Länge N hat genau die Elemente 1 bis N drin,

26:19.610 --> 26:20.670
in irgendeiner Permutation.

26:22.970 --> 26:24.950
Was machen wir denn, wenn wir eine Liste hätten,

26:25.310 --> 26:32.970
wo hier meinetwegen A, A, C, D, C drin steht?

26:33.350 --> 26:34.050
So eine Liste.

26:39.650 --> 26:42.810
Wenn solche Elemente zweimal auftreten,

26:43.950 --> 26:47.270
kann man daraus natürlich auf ganz einfache Art und Weise

26:47.270 --> 26:50.470
eine Liste machen, in der alle Elemente verschieden sind,

26:50.550 --> 26:53.390
indem man einfach da einen Index anfügt.

26:55.590 --> 26:57.990
Also das Auftreten von links nach rechts,

26:58.610 --> 27:00.610
also die Position in der Liste,

27:00.990 --> 27:03.430
wird einfach als weiteres Unterscheidungsmerkmal hinzugenommen

27:03.430 --> 27:07.430
und schon haben wir auch so eine Folge vollständig angeordnet.

27:08.450 --> 27:11.150
Also nicht vollständig angeordnet,

27:11.210 --> 27:12.930
wir haben sie dann, was ich sagen wollte,

27:13.070 --> 27:14.950
dass dann alle Elemente der Liste,

27:15.270 --> 27:17.330
die wir betrachten für das Sortierverfahren,

27:17.870 --> 27:19.370
als verschieden gelten können.

27:21.250 --> 27:24.570
Und insofern ist das hier auch ohne Beschränkung der Allgemeinheit

27:24.570 --> 27:26.030
so zu machen.

27:27.210 --> 27:31.410
Eines der einfachsten Verfahren, Sortieren durch Auswahl,

27:31.410 --> 27:35.030
kennen Sie alle, bestimme das Minimum,

27:36.410 --> 27:37.050
Smin,

27:38.630 --> 27:42.850
dieser Folge, ja, der Folge Sk bis Sn,

27:44.110 --> 27:47.910
also wir machen das ganz einfach,

27:48.050 --> 27:50.730
hier ist die Liste angegeben,

27:51.930 --> 27:54.530
das war ein bisschen zu schnell, also nochmal, so,

27:55.770 --> 28:00.230
das ist die Folge, die wir durch Auswahl sortieren wollen

28:01.790 --> 28:09.050
und wie Sie hier sehen, der Reihe nach suchen wir das Minimum, das ist zunächst mal die 1,

28:09.650 --> 28:15.210
dann brauchen wir natürlich, dass das Minimum, wie wir hier sehen, vertauscht wird mit der

28:15.210 --> 28:22.290
aktuellen Position K, kommt also zunächst das Minimum an die erste Position, dann brauchen

28:22.290 --> 28:27.430
wir nur noch im Rest zu suchen nach den Zweitgrößten, das ist dort wieder das Minimum und so kriegen

28:27.430 --> 28:34.630
wir sukzessive hier die Elemente unserer Folge alle in sortierter Reihenfolge. Wir

28:34.630 --> 28:42.030
bestimmen also n mal das Minimum und der Aufwand ist natürlich ganz einfach. Wir

28:42.030 --> 28:50.450
müssen n mal das Minimum bestimmen und ich nehme an, dass Sie alle wissen, wie

28:50.450 --> 28:54.910
man das Minimum einer Folge bestimmt. Das ist ja nicht weiter schwer, Aufwand für

28:54.910 --> 28:59.950
das Minimum. Noch mal genau geguckt, wie ist unser Berechnungsmodell. Wir arbeiten

28:59.950 --> 29:08.910
nur mit Vergleichen und die Aussage, die man sich so überlegt ist, wenn wir das

29:08.910 --> 29:15.310
Minimum bestimmen wollen, n Elemente, n-1 Vergleiche brauchen wir sicherlich.

29:15.930 --> 29:23.110
Also das sagt das Lämmer aus. Der Beweis ist ganz einfach. Sie stellen sich vor, Sie haben einen

29:23.110 --> 29:29.470
Wettkampf zwischen n Spielern, irgendein Tennismatch, also Tenniswettkampf und es ist

29:29.470 --> 29:32.150
klar, der Beste, der darf natürlich nie verloren haben.

29:33.210 --> 29:41.850
Der muss immer gewonnen haben und das heißt, dass n-1 Spieler, nämlich die

29:41.850 --> 29:49.430
n-1 anderen Spieler, die müssen jeder mindestens einmal verloren haben und der

29:49.430 --> 30:03.450
Beste, der darf nie verlieren. Also muss es mindestens n-1 Vergleiche geben.

30:04.530 --> 30:10.970
Sonst können n-1 Spieler nicht verlieren und da also pro Spiel genau

30:10.970 --> 30:14.710
ein Spiel verliert, ist es klar, dass wir mindestens n-1 Spiele brauchen.

30:15.810 --> 30:21.770
Wie wir die anordnen, ist uns ja völlig egal, wie die Vergleiche angeordnet werden,

30:21.850 --> 30:25.690
aber mindestens n-1. Das ist schon alles, was wir wissen wollten.

30:25.910 --> 30:33.930
Auch mindestens n-1 Vergleiche und wenn Sie sich noch mal überlegen, Sie laufen einfach hier durch

30:35.190 --> 30:39.490
die Liste so, wie machen wir das normalerweise, wir laufen so von links nach rechts durch,

30:39.490 --> 30:46.650
nehmen das erste Element und vergleichen dieses Element mit dem nächsten, wenn es,

30:46.850 --> 30:53.070
wir wollen ja hier das Minimum haben, wenn es größer ist als das nächste,

30:53.290 --> 30:57.090
müssen wir halt austauschen in der Hilfsvariablen, nehmen also immer das,

30:57.510 --> 31:02.370
wir bewahren das kleinere von Elementen immer auf, laufen hier einmal von links nach rechts durch und

31:02.370 --> 31:08.230
haben, wenn wir am Ende angekommen sind, in unserer Hilfsvariablen das minimale Element abgespeichert,

31:08.230 --> 31:12.590
mit N-1 vergleichen. Also wir brauchen mindestens N-1, können es aber auch ganz

31:12.590 --> 31:17.670
einfach realisieren. Danach also nur das Minimum bestimmen. Für die Anordnung der

31:17.670 --> 31:26.330
anderen wissen wir überhaupt nichts. Und damit wissen wir natürlich, dass die Zeit

31:26.330 --> 31:33.870
für das Minimum N-1 ist und damit ist die Zeit insgesamt in, ist die Zeit

31:33.870 --> 31:42.650
insgesamt quadratisch, weil wir halt die Summe I-1, I gleich 1 bis N-1 hier als

31:43.410 --> 31:48.890
Anzahl der Vergleiche haben. Quadratische Zahl von Vergleichen. Und das geht auch

31:48.890 --> 31:53.290
im Mittel, also auch im Mittel für, also jetzt wenn wir uns das anschauen,

31:55.130 --> 31:58.510
dieser Algorithmus war von den konkreten Daten völlig unabhängig.

31:58.510 --> 32:04.330
Das heißt, egal welche Liste vorliegt, wir werden immer die gleiche Zahl von

32:04.330 --> 32:12.590
Vergleichen haben. Und parallel? Naja, wenn wir das parallel anordnen, dann ist doch

32:12.590 --> 32:18.610
eines klar, wir brauchen N-1 Vergleiche. Das kann man, man kann das irgendwie als

32:18.610 --> 32:27.990
Baum anordnen und lässt also immer hier so zwei gegeneinander antreten und

32:27.990 --> 32:34.970
die Sieger, die spielen wieder gegeneinander und naja, dann hat man doch

32:35.930 --> 32:40.870
die Vergleiche. Also eine Baumstruktur gibt einem sicherlich Log N und weniger,

32:42.190 --> 32:46.970
mit weniger Vergleichen auszukommen als Log N vergleichen, das wird ja eigentlich

32:47.650 --> 32:51.290
so kaum möglich sein. Jetzt habe ich daneben schon stehen, dieses tatsächlich,

32:52.270 --> 32:54.790
wahrscheinlich haben Sie, ich weiß nicht, ob Sie das schon ausgedruckt haben,

32:55.290 --> 33:00.330
die Folien, Sie kennen die noch nicht, waren die schon im Netz, sind schon im

33:00.330 --> 33:14.010
Netz, okay. Also, bitte? Okay, ja. Also, die stehen wie üblich auf FlixCampus,

33:14.090 --> 33:21.110
die Folien. Ich habe jetzt hier halt so intuitiv, denke ich, ist es klar, dass

33:21.110 --> 33:25.270
man denkt, Log N ist die Minimalzahl von Vergleichen, die man, oder von Schritten,

33:25.270 --> 33:31.490
die man braucht, wenn man es parallel macht. Wenn man aber jetzt sich anschaut,

33:33.870 --> 33:37.370
welche Möglichkeiten man hat, hat bei einer parallelen Ausführung von

33:37.370 --> 33:42.530
Vergleichen, dann stellt man fest, man muss sich halt nur das Modell geeignet

33:42.530 --> 33:49.970
zurechtbauen und was ich einfach mache ist, ich nehme mir eine Reihe von

33:49.970 --> 33:57.150
Registern hier und schreibe dort zu Anfang überall eine Null rein.

33:58.770 --> 34:09.610
Ich nenne das eine Reihe von Registern oder Variablen, die ich mit Null

34:09.610 --> 34:15.630
initialisiere, E für Ergebnis oder Entscheidungsvariablen, was immer.

34:15.630 --> 34:26.630
Das kann ich parallel machen. Ich kann ja in N plus eins Register etwas

34:27.330 --> 34:34.810
reinschreiben. Das ist ein paralleler Schritt. Zwei, das ist der entscheidende

34:34.810 --> 34:45.180
Punkt. Für alle IJ aus N, also für alle Zahlen zwischen 1 und N, also,

34:50.040 --> 34:58.000
schreibe ich, natürlich jetzt, hier habe ich jetzt etwas ungünstiges hingeschrieben,

34:58.140 --> 35:02.540
also hier steht jetzt falls I größer J. Ich weiß natürlich, wenn ich nur die Zahlen

35:02.540 --> 35:06.880
1 bis N habe, dass 1 das Minimum ist. Darum geht es eigentlich nicht, sondern es geht

35:06.880 --> 35:12.260
darum, wenn, nehmen wir mal an, wir haben eine, unsere Liste S, falls also nicht I

35:12.260 --> 35:22.480
größer J, sondern falls S I größer SJ. Das sind ja unsere Listenelemente. Das

35:22.480 --> 35:28.480
meinte ich damit. Ja, wir wollen ja das minimale Listenelement bestimmen. Jetzt

35:28.480 --> 35:40.160
vergleiche ich jedes Paar IJ von Listenelementen. Das sind Größenordnung N

35:40.160 --> 35:49.360
Quadrat, genauer ein halb N Quadrat, äh, ein halb N mal N plus 1, ähm, vergleiche

35:49.360 --> 35:57.200
und wann immer S I größer als SJ ist, schreibe ich entsprechend eine 1 rein. Also

35:57.200 --> 36:05.680
wenn hier irgend so ein Element war, jetzt kommt da eine 1 rein, ups, in das Element,

36:05.880 --> 36:16.820
das wäre jetzt also hier Position I. So, und, äh, das heißt nach diesem Schritt,

36:17.600 --> 36:22.960
das ist ein paralleler Schritt, N Quadrat vergleiche, Größenordnung, steht in

36:22.960 --> 36:36.480
dieser, äh, diesem Ergebnisregister in fast allen eine 1 und es wird für ein Element,

36:37.960 --> 36:42.140
jetzt habe ich hier I stehen, machen wir hier raus ein J, da steht jetzt also eine 1 und

36:42.140 --> 36:47.900
haben wir hier irgendwo I stehen, da steht vielleicht eine 0, wenn dort noch eine 0

36:47.900 --> 36:57.920
steht, bei I, dann heißt das, dieses Element war niemals größer als irgendein anderes.

36:58.440 --> 37:01.800
Wenn es aber nicht größer als irgendein anderes ist, nur dann wird dort eine 1

37:01.800 --> 37:08.720
reingeschrieben worden, dann war es immer kleiner gleich und ist deswegen nie in

37:08.720 --> 37:15.420
dem Sinne besiegt worden. Das heißt, dieses Element I ist dann das

37:15.420 --> 37:19.100
kleinste Element und wir können einfach diesen Wert da reinschreiben. Da steht

37:19.100 --> 37:29.600
hier ein I drin. Und wenn wir also hier die 0 durch ein I ersetzen, dann wissen wir,

37:29.920 --> 37:36.340
wenn wir uns anschließend diese Variable E0 anschauen, dann steht dort

37:36.340 --> 37:41.940
der Index des kleinsten Elements drin. Das sind drei parallele Schritte. Einmal

37:41.940 --> 37:46.860
mit 0 initialisieren, einmal n²-Vergleiche durchführen und drittens

37:46.860 --> 37:54.920
einmal reinschreiben in das Element E0, welcher Index zum kleinsten Element

37:54.920 --> 38:04.460
gehört. Dann habe ich das Element. Also, es geht parallel durchaus auch mit drei

38:04.460 --> 38:09.940
Schritten. Wir müssen nur entsprechend Aufwand reinstecken in die Anzahl der

38:09.940 --> 38:15.780
Vergleiche, die wir durchführen. Also wir haben hier Größenordnung n²-Vergleiche.

38:16.680 --> 38:21.260
Auch bei dem sequenziellen Verfahren hatten wir Größenordnung n²-Vergleiche.

38:21.300 --> 38:24.740
Also die Anzahl der Vergleiche, die ausgeführt werden, ist bei dem

38:24.740 --> 38:31.780
sequenziellen Verfahren und bei diesem Verfahren hier identisch. Da wurden auch

38:31.780 --> 38:44.400
genau alle miteinander verglichen. Und das heißt, wir führen eben hier nur

38:44.400 --> 38:48.360
diese Vergleiche alle gleichzeitig durch. Wir müssen selbstverständlich in der Lage

38:48.360 --> 38:58.120
sein, gleichzeitig zu lesen. Ja, wir müssen also für die n-Vergleiche, also jedes

38:58.120 --> 39:02.840
Element wird mit n-1 anderen verglichen, oder entsprechend mit wenigen.

39:03.040 --> 39:06.580
Das reicht ja diese, wir müssen diese Vergleichsmatrix nicht vollständig

39:06.580 --> 39:13.960
machen. Es reicht sie symmetrisch zu machen. Quatsch, da sie symmetrisch ist, reicht es sie,

39:17.980 --> 39:22.500
also nur eine Dionalmatrix, Quatsch, eine Dreiecksmatrix zu berechnen.

39:22.840 --> 39:26.280
Trotzdem brauchen wir gleichzeitiges Lesen und gleichzeitiges Schreiben.

39:26.280 --> 39:30.820
Das ist natürlich das, was schwieriger ist, gleichzeitiges Schreiben. Das wäre

39:30.820 --> 39:35.660
schwierig, wenn wir unterschiedliche Sachen schreiben würden. Da ich aber hier oben sage,

39:35.740 --> 39:42.720
für alle ij schreibe 1 da rein, falls si größer als sj ist, ist der einzige Wert,

39:42.720 --> 39:51.020
der geschrieben wird, eine 1. Wenn also mehrere Vergleiche ergeben, dass si größer als sj ist,

39:52.520 --> 40:02.280
also i größer als sj, i größer als sk, dann würde zweimal bei si reingeschrieben werden,

40:02.340 --> 40:07.840
eine 1, aber das ist ja kein Problem, es wird der gleiche Wert geschrieben. Das Einzige ist,

40:08.120 --> 40:17.060
im dritten Schritt schreiben wir den Index rein, falls das Element das kleinste ist. Und da ist

40:17.060 --> 40:23.020
es wichtig, dass wir nur ein Maximum bzw. Minimum, je nachdem, was wir hier, da habe

40:23.020 --> 40:33.640
ich mich verschrieben, da muss Minimum stehen, falls das Minimum eindeutig bestimmt ist. Also,

40:34.740 --> 40:40.780
wenn wir, wenn die Elemente der Liste alle verschieden sind, ist das kein Problem. Wenn

40:40.780 --> 40:45.480
wir eventuell mehrere kleinste Elemente haben, dann haben wir ein Problem, dann würden nämlich

40:45.480 --> 40:56.440
verschiedene Indizes in das Element E0 reingeschrieben werden und dann hätten wir einen

40:56.440 --> 41:00.520
Konflikt. Wenn wir aber davon ausgehen, die Elemente sind alle verschieden, haben wir den

41:00.520 --> 41:05.260
Konflikt nicht. Und dann hätten wir hier also eine PRAM, Parallel Random Access Machine,

41:06.000 --> 41:14.060
mit Concurrent Read, Concurrent Write verwendet und zur Auflösung von Schreibkonflikten hier die

41:14.060 --> 41:20.360
Common Schreibregel, die aussagt, dass alle Werte, die geschrieben werden, identisch sein

41:20.360 --> 41:25.920
müssen. Sonst ist ein gleichzeitiges Schreiben unzulässig. Das ist hier also durchaus erfüllt

41:27.040 --> 41:37.000
und damit sehen wir, man kann also hier durch Parallelität erreichen, dass der Aufwand

41:37.000 --> 41:47.400
tatsächlich runtergeht bis auf konstante Zahl von Vergleichen. Die Effizienz für die Bestimmung

41:47.400 --> 41:54.840
des Minimums ist natürlich ganz schrecklich. Übrigens habe ich mich gerade eben an einer

41:54.840 --> 42:00.420
Stelle versprochen, hat keiner von Ihnen protestiert. Ich habe gesagt, der Aufwand,

42:00.820 --> 42:04.300
die Anzahl der Vergleiche, aber ja auch im sequentiellen Fall O von n Quadraten,

42:04.300 --> 42:11.840
hat er im Kopf sortierend durch Auswahl. Der Aufwand für die Bestimmung des Minimums ist

42:11.840 --> 42:18.540
natürlich nur linear. n-1 Vergleiche haben wir gerade vorgesehen auf der Folie davor. Das heißt,

42:18.840 --> 42:25.780
der Aufwand für das parallele Verfahren ist schrecklich viel größer als für das sequentielle

42:25.780 --> 42:30.460
Verfahren, weil wir im sequentiellen Verfahren ja nur n Vergleiche oder n-1 Vergleiche machen

42:30.460 --> 42:35.760
und hier machen wir Größenordnung n Quadratvergleiche. Das heißt, wir haben eine

42:35.760 --> 42:46.980
schreckliche Effizienz in 1 durch n. Wir machen viel mehr Arbeit, als eigentlich erforderlich

42:46.980 --> 42:55.040
ist, können aber dadurch die Laufzeit runterdrücken auf konstante Laufzeit. Das geht nur,

42:55.040 --> 43:01.140
weil wir eben diese Concurrent Read, Concurrent Write Schreibregel haben. Sobald wir da runter

43:01.140 --> 43:06.020
gehen, nicht mehr Concurrent Read, Concurrent Write, sondern Exclusive Read, Exclusive Write,

43:06.540 --> 43:15.780
dann wird es schwierig. Dann bekommen wir als Unterschranke tatsächlich dann Login. Dann geht

43:15.780 --> 43:23.280
es nicht besser. Gut, das nur als kurzer Ausflug, dass man auch bei der Bestimmung des Minimums sich

43:23.280 --> 43:33.700
bei parallelen Algorithmen interessante Sachen einfallen lassen kann. Zweiter Algorithmus Sortieren

43:33.700 --> 43:40.380
durch Einfügen. Oh, was habe ich denn da gemacht? Das ist nicht gut animiert. Also, Sortieren durch

43:40.380 --> 43:46.560
Einfügen kennen Sie auch. Wir fügen einfach der Reihe nach die Elemente der Liste ein. Das ist

43:46.560 --> 43:55.360
unsere Einfügereihenfolge und das geht hier im ersten Schritt ganz einfach. Dann wird die 1

43:55.360 --> 44:01.060
eingefügt, die muss halt vorne rein und so weiter. Wir fügen immer das nächste Element an die richtige

44:01.060 --> 44:07.720
Position ein und das kann eben dazu führen, dass wir, wenn wir wie in diesem Fall von da nach da

44:07.720 --> 44:15.520
halt hier die 1 einfügen müssen, dann müssen halt die 2 und 5 im Array verschoben werden. Und wenn

44:15.520 --> 44:19.800
wir die 3 einfügen als nächstes, dann wird halt hier die 5 verschoben. Das heißt, es werden immer

44:19.800 --> 44:24.920
Teile der Liste verschoben. Die Teile rechts der Einfügeposition müssen verschoben werden. Das

44:24.920 --> 44:30.800
ist ein ziemlicher Aufwand. Wenn wir Glück haben, ist das Element, das wir einfügen, immer gerade

44:32.040 --> 44:39.840
an der hintersten Position. Sofern die Liste in der sortierten Reihenfolge eingelesen wird, dann

44:39.840 --> 44:51.500
haben wir Glück. Der beste Fall ist hier gerade nicht angegeben. Im besten Fall, das sollte ich

44:51.500 --> 45:05.960
hier noch kurz hinschreiben, haben wir gerade Aufwand O von N. Also linearen Aufwand. Wir müssen

45:05.960 --> 45:09.120
die nur an die richtige Position halt immer einfach reinschreiben. Wenn da kein Verschieben

45:09.120 --> 45:20.800
erforderlich ist, haben wir lineare Zeit. Also im besten Fall deutlich besser. Im Mittel immer

45:20.800 --> 45:27.040
noch quadratisch bringt nicht viel. Bubble Sort kennen Sie auch, nehme ich an. Wer kennt Bubble Sort

45:27.040 --> 45:38.370
nicht? Kennen Sie alle. So, Bubble Sort, warum stelle ich Ihnen das vor? So ein Verfahren, das

45:39.530 --> 45:48.010
man als Informatiker niemals einsetzt, wenn man ein Programm schreiben muss, das auf einem

45:48.010 --> 45:55.850
normalen Rechner ausgeführt wird. Da ist Bubble Sort einfach zu schlecht. Warum? Bubble Sort hat

45:55.850 --> 46:05.090
eine datenunabhängige, also listenunabhängige Vorgehensweise, starre Anzahl von Vergleichen

46:05.690 --> 46:15.050
für K gleich 2 bis N, für I gleich N bis K runter. Also hier in einer Allgolf Modula oder

46:15.050 --> 46:22.090
ähnlichen Notationen formuliert. Was passiert hier? Ich habe die Liste mal hier von oben nach

46:22.090 --> 46:30.990
unten aufgeschrieben. Wenn wir hier vergleichen, das steht für K gleich 2 bis N, für I gleich N

46:30.990 --> 46:38.090
down to K, also was passiert folgendes. Wir fangen hier an, vergleichen 4 und 6 und stellen fest,

46:38.350 --> 46:48.590
die beiden müssen vertauscht werden. Wir gehen weiter, vergleichen 4 mit 3, da passiert nichts.

46:50.770 --> 46:58.790
Vergleichen 3 mit 1, da passiert nichts. Vergleichen 1 mit 5 und stellen fest, wir müssen vertauschen.

46:59.830 --> 47:08.550
Das heißt, wir haben hier die beiden vertauscht. Und wir vergleichen 1 mit 2 und stellen fest, auch hier müssen wir vertauschen.

47:08.950 --> 47:16.010
Das ist also ein Durchlauf für K gleich 2. Sind wir hier einmal durchgelaufen. Und jetzt geht es weiter.

47:17.450 --> 47:28.110
Jetzt brauchen wir nicht mehr ganz so hoch zu laufen. Warum nicht? Weil wir hier oben jetzt

47:28.930 --> 47:33.790
garantiert das minimale Element stehen haben. Deswegen brauchen wir nicht mehr ganz bis dort

47:33.790 --> 47:40.570
oben hin zu laufen. Bei diesen Vergleichsoperationen ist garantiert das minimale Element nach oben

47:40.570 --> 47:50.170
gewandert. Denn es wird ja beim Laufen vom Ende nach oben durchgeschoben, wie wir hier sehen an

47:50.170 --> 47:58.510
diesen beiden Vergleichen. Und dann fangen wir wieder hier unten an. Stellen fest, 6 und 4 sind

47:58.510 --> 48:03.310
der richtigen Reihenfolge. 4 und 5 sind in der falschen Reihenfolge. Die müssen vertauscht

48:03.310 --> 48:09.410
werden. Dann haben wir 4 und 3 in der richtigen Reihenfolge. 2 und 1 auch. Und wir laufen noch

48:09.410 --> 48:15.590
mal hier von unten durch. Stellen fest, jetzt ist alles in der richtigen Reihenfolge. Wir können

48:15.590 --> 48:22.330
aber noch nicht aufhören. Nach dem Verfahren läuft das sogar noch ein bisschen weiter. Ich habe

48:22.330 --> 48:33.490
hier nur angegeben die Position an denen etwas vertauscht wird. Hier werden eigentlich nur 4

48:33.490 --> 48:40.310
Vertauschungen durchgeführt. Aber um die zu entdecken mussten wir Größenordnung N² Vergleiche

48:40.310 --> 48:49.310
ausführen. Der Name Bubblesort hat damit zu tun, dass man bei dieser Anordnung die leichten

48:49.310 --> 48:54.470
Elemente nach oben wandern lässt und die schweren die sinken nach unten. Also die 6 ist nach unten

48:54.470 --> 48:59.490
gewandert, die 5 wandert nach unten und so weiter. Das heißt, die schweren Elemente sinken nach

48:59.490 --> 49:06.010
unten, die leichten gehen nach oben. Deswegen dieser Name Bubblesort. So kann man sich das

49:06.010 --> 49:14.090
vorstellen. So bewegen sich die Elemente und es ist klar, dass wir immer N-1½ Vergleiche machen

49:14.090 --> 49:19.670
und deswegen ist die Zeit quadratisch ein schlechtes Verfahren, wenn wir uns das so

49:19.670 --> 49:27.930
sequenziell anschauen. Man kann es verbessern, indem man in dem Augenblick, wo bei einem Durchlauf

49:27.930 --> 49:33.550
keine Vertauschung mehr vorgenommen wurde, das Verfahren abbricht. Denn wenn keine Vertauschung

49:33.550 --> 49:40.370
mehr durchgeführt wird für einen solchen Durchlauf, hier für I gleich N down to K, wenn kein

49:40.370 --> 49:44.910
Vergleich durchgeführt werden musste, kann man aufhören, dann ist die Folge sortiert. Das wäre

49:44.910 --> 49:50.210
eine Verbesserung. Die andere wäre, dass man nicht immer von unten nach oben das macht, sondern

49:50.210 --> 49:56.110
ein Abwechseln von unten nach oben und oben nach unten oder links rechts rechts links, je nachdem

49:56.110 --> 50:01.610
wie man sich die Folge anschaut. Und das ist ein Verfahren, das nennt sich Shaker Sort. Das bringt

50:01.610 --> 50:11.930
also eine Verbesserung. Wenn man Glück hat, hat man jetzt im besten Fall ein lineares Verhalten.

50:12.050 --> 50:17.570
Wir müssen einmal nur durchlaufen und sind fertig. Das wäre schon durch diese erste

50:17.570 --> 50:23.990
Verbesserung. Eine sortierte Folge, da wird nur einmal durchgelaufen, wir sind fertig. Und auch

50:23.990 --> 50:30.750
diese Shaker Sort bringt also noch weitere Verbesserungen. Aber auch hier im Mittel bleibt

50:30.750 --> 50:42.690
es immer noch quadratisch, nur im besten Fall haben wir dann hier ein, sollte besser schreiben,

50:44.010 --> 50:56.510
im besten Fall Groß O von N. So, auch hier eine parallele Variante. Die ist nämlich ganz interessant,

50:56.510 --> 51:02.730
die parallele Variante. Eine parallele Variante von Bubble Sort würde doch so laufen, dass wir

51:02.730 --> 51:09.290
genau das, was wir jetzt gemacht haben, mit diesem sequenziellen Durchlaufen durch die Liste

51:09.290 --> 51:19.910
parallel machen. Und das heißt, wir haben ja hier unsere N-Elemente. Also schreibt ihr mal hier

51:19.910 --> 51:30.110
einfach 1, 2, 3, 4, 5, 6 meinetwegen auf. Und wenn wir sagen, wir wollen jetzt das, was Bubble Sort macht,

51:30.550 --> 51:38.990
parallel machen. Das Bubble Sort hat diese Elemente hier verglichen. Das Maximum soll nach rechts,

51:39.150 --> 51:46.150
das Minimum nach links. Das soll dieser Pfeil andeuten. Jetzt kann ich natürlich parallel, ich will

51:46.150 --> 51:51.070
jetzt also Exclusive Read, Exclusive Write machen. Ich könnte natürlich gleichzeitig diese Elemente

51:51.070 --> 51:56.710
hier 2 und 3 vergleichen. Das will ich jetzt aber nicht, weil ich hier ein Konflikt habe. Ich möchte

51:56.710 --> 52:02.590
jetzt Exclusive Read, Exclusive Write Modell mir anschauen. Dann könnte ich gleichzeitig nur diese

52:02.590 --> 52:11.330
beiden vergleichen und diese beiden. Und das ist ein sogenannter ungerader Schritt. Dieser Schritt heißt

52:11.330 --> 52:19.890
ungerade oder odd, weil der Index des unteren Elementes hier bei diesem Paar von Elementen, die verglichen

52:19.890 --> 52:33.790
werden, ungerade ist. Und danach machen wir halt einen geraden Vergleich. Da sind die Indizes der

52:33.790 --> 52:44.210
Paare, des kleineren Elements der Paare jeweils gerade. Deswegen gerade, ungeraden, odd, even.

52:44.790 --> 52:52.190
Transposition heißt halt Vertauschung oder Umordnung. Das heißt, wir gucken uns abwechselnd

52:52.190 --> 53:02.010
die Paare an den geraden und ungeraden Positionen an und ordnen sie jeweils um entsprechend unserer

53:03.070 --> 53:09.370
kleiner Gleichrelation. Also das ist hier dieses Compare Exchange. Heißt, ich vergleiche und

53:09.370 --> 53:18.510
vertausche, falls erforderlich. Und dann steht hier noch diese Annahme Sn plus 1 gleich unendlich

53:18.510 --> 53:23.310
wird angenommen. Eigentlich hätten wir nach dem Verfahren hier noch einen Vergleich mit

53:23.310 --> 53:27.670
irgendeinem Element. Da nehme ich halt an, dass hier unendlich steht. Wenn man das in der Realität

53:27.670 --> 53:32.450
ausführen würde, würde man auf den Vergleich halt verzichten. Das macht nur das Schreiben des

53:32.450 --> 53:36.970
Programms ein bisschen umständlicher. Deswegen habe ich es hier weggelassen. So, das soll also alles

53:36.970 --> 53:44.070
jetzt parallel gemacht werden. Wie viele haben wir hier parallel? Gerade für n Elemente, n halbe

53:44.070 --> 53:55.250
vergleiche parallel. Hier n halbe minus 1. Das ist das, was hier steht als Analyse. Wir haben

53:55.250 --> 54:02.010
insgesamt n Schritte. Wir machen ja j gleich 1 bis n wird das Ganze gemacht. n Schritte. Wir brauchen

54:02.010 --> 54:11.010
in den ungeraden Schritten haben wir jeweils n halbe Vergleiche von Elementen. Also n halbe

54:11.010 --> 54:21.450
Operationen werden gleichzeitig ausgeführt. Der Zeitgewinn in diesem Fall. Ja, Zeitgewinn im

54:21.450 --> 54:28.830
Vergleich zu, müsste ich eigentlich jetzt sagen, zum besten sequenziellen Verfahren. Das beste

54:28.830 --> 54:33.830
sequenzielle Verfahren, wissen Sie noch aus Informatik 1, hat auch im schlechtesten Fall n

54:33.830 --> 54:39.970
Log n Vergleiche. Hier haben wir, also dazu kommen wir noch, mit n Log n Vergleichen. Hier haben wir

54:39.970 --> 54:48.330
n Vergleich, also n Schritte. Also ist die Effizienz oder ist der Zeitgewinn Log n und die Effizienz

54:48.330 --> 54:59.370
ist Log n durch n halbe. Also Größenordnung Log n durch n. Effizienz ist immer noch nicht so

54:59.370 --> 55:05.790
doll. Also der Zeitgewinn ist nicht groß, mit n Prozessoren beziehungsweise n halbe Vergleichen

55:05.790 --> 55:11.770
gleichzeitig. Aber man muss sich anschauen, was wir hier eigentlich machen. Wir nehmen ja hier,

55:11.770 --> 55:21.270
wir nehmen hier im Prinzip an, dass wir ein lineares Feld haben von Prozessoren. Und also

55:21.270 --> 55:27.350
ein lineares Feld von Prozessoren ist etwas, was durchaus nicht so ungewöhnlich ist. Und es ist

55:27.350 --> 55:31.310
auch nicht so ungewöhnlich, dass Sie auf so einer Folge von Prozessoren Elemente haben,

55:31.350 --> 55:35.370
die verglichen werden sollen. Vielleicht sind das nicht nur einzelne Elemente, vielleicht sind das

55:35.370 --> 55:41.410
einzelne Dateien, die in eine richtige Anordnung gebracht werden sollen. Da haben wir also komplexe

55:41.410 --> 55:49.830
Operationen auszuführen. Also Vergleich oder Verschmelzen von zwei Dateien. Und es ist völlig

55:49.830 --> 55:58.230
klar, wenn zum Beispiel das kleinste Element hier in dem linkesten Prozessor liegt, das muss ja am

55:58.230 --> 56:02.670
Ende, wenn das das Größte ist, hier in dem linkesten Prozessor, das soll am Ende ganz nach

56:02.670 --> 56:10.790
rechts wandern. Das geht nur über n-1 Vertauschungsoperationen. Das heißt, der Aufwand

56:10.790 --> 56:17.890
ist auf jeden Fall linear. Mindestens linear, wenn wir solch eine Rechnungsstruktur haben.

56:18.990 --> 56:25.850
Und deswegen ist es klar, dass wir auf einem linearen Feld gar nicht schneller als mit linearer

56:25.850 --> 56:33.370
Zeit das machen können. Wie gesagt, weil eben die Prozessoren links und rechts eventuell ihre Daten

56:33.370 --> 56:42.430
vertauschen müssen. Und deswegen ist OETS, also Optical Transposition Sort, ein optimales

56:42.430 --> 56:49.630
Verfahren für lineare Felder. Es geht nicht besser. Man kann Kleinigkeiten eventuell noch

56:49.630 --> 56:58.970
ausstreichen, aber es ist im Prinzip, hat es genau die Laufzeit, die wir brauchen, wir mindestens

56:58.970 --> 57:03.910
brauchen, also ist es ein optimales Verfahren. Wir sehen also hier, dass ein Verfahren, das man,

57:04.330 --> 57:10.210
wenn man sich nur die sequenzielle Welt anschaut, sofort in den Papierkorb wirft, weil das viel zu

57:10.210 --> 57:18.550
langsam ist, auf einmal interessant wird, wenn ich ein paralleles Verfahren oder eine parallele

57:18.550 --> 57:23.490
Rechnungsstruktur habe, in diesem Fall noch mit einer speziellen Verbindungsstruktur, nämlich

57:23.490 --> 57:30.090
ein lineares Feld. Dann ist OETS bzw. OETS auf einmal wieder ein sehr interessantes

57:30.090 --> 57:37.510
Verfahren. Und das ist das, was ich Ihnen hier eigentlich vermitteln wollte. Ganz kurz, ich habe

57:37.510 --> 57:42.370
gesagt, das wird durch diese Verfahren sortiert in Endschritten. Ich habe gar nicht gesagt, dass es

57:42.370 --> 57:48.890
tatsächlich so ausreicht, dass es das tatsächlich tut. Man muss natürlich beweisen, dass diese

57:48.890 --> 58:00.670
Endschritte ausreichen, dass dann nicht nur das Maximalelement am richtigen Platz ist. Ich habe

58:00.670 --> 58:08.810
gesagt, mindestens Endschritte, damit im schlechtesten Fall das Größte von links nach rechts oder das

58:08.810 --> 58:14.730
Kleinste von rechts nach links wandern kann. Das geht sicherlich mit Endvergleichen oder mit

58:14.730 --> 58:19.230
solchen Schritten. Aber es müssen alle anderen auch am richtigen Platz sein. Und dann kann man

58:19.230 --> 58:23.890
sich zunächst mal überlegen, dass man natürlich für die einfachen Schritte N gleich 1 oder N

58:23.890 --> 58:33.670
gleich 2. Sie haben hier Elemente A und B. Es kommt ein OTT-Schritt. Naja, das ist ein OTT-Schritt.

58:34.610 --> 58:41.890
Und es kommt ein EVEN-Schritt. Da passiert nichts. Das wäre ja eigentlich dieser Vergleich. Also 2

58:44.170 --> 58:50.010
für N gleich 1 haben wir nur einen Schritt. Für N gleich 2, da brauchen wir gar nichts weiter zu

58:50.010 --> 58:53.910
machen, weil wir nur ein Element haben. Für N gleich 2 müssen wir eventuell vertauschen. Das

58:53.910 --> 58:58.470
wird hierbei gemacht. Und auch in der anderen Reihenfolge, wenn wir mit EVEN anfangen würden

58:58.470 --> 59:08.570
und OTT hinterher machen, reichen zwei Schritte natürlich aus. Und jetzt schauen wir uns an,

59:08.570 --> 59:18.310
was passiert, wenn wir jetzt das Ganze für einen beliebigen Fall betrachten. Wir nehmen an,

59:18.370 --> 59:25.050
wir haben das für folgende Längen N schon bewiesen und schauen uns jetzt den Fall an für N plus 1.

59:26.990 --> 59:33.270
Und nehmen wir auf diesem Bild hier an, dass wir, also 8 Elemente, N plus 1 in diesem Fall,

59:33.270 --> 59:42.490
also 8 ist. Und das, was wir hier anschauen, ist den Weg des maximalen Elementes durch das lineare

59:42.490 --> 59:49.550
Feld der Länge N plus 1. Das maximale Element steht im schlechtesten Fall ganz links und soll

59:49.550 --> 59:58.630
ganz nach rechts. Dann geht es genau diesen Weg, der hier so grau markiert ist. Über diese Vergleiche

01:00:00.630 --> 01:00:08.810
wandert es rüber an die Position S8. Wenn das maximale Element an einer anderen Position war,

01:00:09.330 --> 01:00:15.070
dann würde es entsprechend über weniger Vergleiche laufen. Das wäre also der schlechteste Fall für

01:00:15.070 --> 01:00:23.330
das maximale Element. Das ist offensichtlich. Im ersten Schritt wird es garantiert hier vertauscht

01:00:23.330 --> 01:00:32.650
und so weiter. Und jetzt eliminieren wir einfach den Weg des maximalen Elementes aus diesem

01:00:32.650 --> 01:00:38.090
Vergleichernetz. Wir streichen einfach die Vergleiche raus und damit auch dieses maximale

01:00:38.090 --> 01:00:46.210
Element. Und schauen uns nur noch den Rest an. Die restlichen Elemente sind Elemente in irgendeiner

01:00:46.210 --> 01:00:53.710
Anordnung 1 bis 7. Und diese Elemente müssen natürlich auch verglichen werden. Und die tauchen

01:00:53.710 --> 01:00:59.570
in allen anderen Vergleichen auf. Wenn Sie sich jetzt anschauen den Bereich hier oben, diese

01:00:59.570 --> 01:01:12.020
Vergleiche und diese Vergleiche hier unten, dann stellen Sie fest, dass Sie die einfach zusammenschieben

01:01:12.020 --> 01:01:23.160
können. Und Sie bekommen daraus ein solches Vergleichernetz, also eine Anordnung von Vergleichen,

01:01:23.520 --> 01:01:31.500
für n Elemente. Und zwar bleiben hier n solche Zeilen übrig, weil wir genau eine rausgestrichen

01:01:31.500 --> 01:01:36.120
haben, eine solche Digitale rausgestrichen haben. Und die Elemente, die verglichen werden, das sind

01:01:36.120 --> 01:01:41.100
genau die übrigen Elemente. Das maximale Element wurde ja rausgestrichen. Das heißt, die Vergleiche,

01:01:41.100 --> 01:01:47.440
die jetzt übrig bleiben in dem Verfahren, sind genau die Vergleiche, die man ausführt, wenn man mit dem

01:01:47.440 --> 01:01:54.900
Verfahren OITS eine Folge der Länge n sortiert. Und dafür reichen ja gerade n Schritte aus, nach

01:01:54.900 --> 01:02:04.900
Induktionsannahme. Also, das ist das, was hier steht. Das heißt, dass wir mit den übrigen Vergleichen

01:02:04.900 --> 01:02:09.400
alle anderen Elemente an die richtigen Positionen bringen. Und damit haben wir alle Elemente an die

01:02:09.400 --> 01:02:17.500
richtigen Positionen gebracht. Und das Ganze ist also ein korrektes Verfahren. Das, was ich Ihnen hier

01:02:17.500 --> 01:02:28.440
so grafisch dargestellt habe, ist aufwendig, formal zu beschreiben. Aber wenn Sie das formal

01:02:28.440 --> 01:02:38.620
aufschreiben, diese anschaulich klare Aussage, dass in diesen beiden hier so angedeuteten

01:02:38.620 --> 01:02:44.720
Restbereichen, diesen dreigängigen Bereichen, dass dort gerade alle übrigen Elemente der Folge

01:02:44.720 --> 01:02:50.480
verglichen werden und dass das Ganze wieder ein OITS-Netz ist, das kann man sich formal auch

01:02:50.480 --> 01:02:55.640
überlegen, ist aber dann relativ aufwendig, formal hinzuschreiben. Aber so, ich denke,

01:02:56.180 --> 01:03:03.040
anschaulich ist es klar, dass der Vergleich so, dass dieser Beweis so in Ordnung ist.

01:03:04.760 --> 01:03:13.380
Also ist die Folge insgesamt sortiert und das Ganze ist korrekt. So, das ist also jetzt,

01:03:13.840 --> 01:03:19.400
das haben wir zwei Sachen gelernt. Das eine war bei der Minimumsbestimmung. Man kann, wenn man es

01:03:19.400 --> 01:03:27.880
parallel macht, in konstanter Zeit Minimum bestimmen, mit relativ viel Aufwand. Beim Sortieren, also bei

01:03:27.880 --> 01:03:34.620
diesem Bubble Sort, im sequentiellen Fall schlechtes Verfahren, ist im parallelen Fall bei

01:03:34.620 --> 01:03:40.580
einem, zumindest beim linearen Feld, sehr gut geeignet. Jetzt schauen wir uns nochmal an, was

01:03:40.580 --> 01:03:45.860
wir hier machen können beim Sortieren, wenn wir Divide & Conquer einsetzen. Da gibt es verschiedene

01:03:45.860 --> 01:03:53.700
Möglichkeiten. Eine Möglichkeit ist, Quicksort einzusetzen. Quicksort ist Ihnen, nehme ich an,

01:03:53.700 --> 01:04:04.580
allen bekannt. Und das Wesentliche ist ja, dass wir aus der Folge S ein Element rauswählen. Und

01:04:04.580 --> 01:04:09.520
da nimmt man eben immer, ohne Beschränkung der Allgemeinheit, das erste Element raus. Und dann

01:04:09.520 --> 01:04:16.760
zerteilt man die Liste halt so, dass wir hier zwei Folgen haben, der kleineren und der größeren.

01:04:17.920 --> 01:04:24.440
Und anschließend wird auf diesen beiden Folgen der Algorithmus weiter ausgeführt. Das ist Quicksort.

01:04:25.920 --> 01:04:30.640
Also man muss immer, wenn man sich einen Algorithmus merken will, sollte man immer möglichst ein Bild

01:04:30.640 --> 01:04:39.540
haben. Bei OOTS zum Beispiel, bei OOTS braucht man dieses Vergleichernetz, diese Mauer-ähnliche

01:04:40.580 --> 01:04:45.380
Anordnung von Vergleichen, dieses versetzte. Das ist ein Bild, da haben Sie den Algorithmus im

01:04:45.380 --> 01:04:56.600
Kopf. Bei Quicksort brauchen Sie dieses Bild. Das ist Quicksort. Und dass Sie eben ein Element sich

01:04:56.600 --> 01:05:09.320
hernehmen und das an die richtige Position bewegen, durch einen Aufteilungsschritt. Und gut, die

01:05:09.320 --> 01:05:14.100
Analyse, Schritt zwei, also Schritt eins, das Element auszuwählen, ist natürlich ganz einfach.

01:05:14.200 --> 01:05:26.020
Schritt zwei, Aufteilung dieser Folge. Das ist natürlich Überlegung wert, wie macht man das?

01:05:27.060 --> 01:05:33.540
Und Sie kennen alle dieses Verfahren, bei dem man dann halt zwei Zeiger verwendet, die man so nach

01:05:33.540 --> 01:05:39.340
links, den einen nach rechts, den anderen nach links verschiebt, von den beiden Enden. Und wann immer die

01:05:39.340 --> 01:05:46.100
Elemente an diesen beiden Positionen in der falschen Anordnung stehen, werden sie halt einfach vertauscht.

01:05:48.380 --> 01:05:56.960
Und da man die dann sukzessive nach rechts und nach links bewegt, hat man hier problemlos diese

01:05:56.960 --> 01:06:03.200
Anordnung, dass links nur Elemente kleiner gleich c stehen, rechts nur Elemente größer gleich c.

01:06:04.840 --> 01:06:12.300
Und es ist ja klar, dass dadurch, dass man sobald ein Element bei dem linken Zeiger größer ist als

01:06:12.300 --> 01:06:15.940
Element bei dem rechten Zeiger, müssen die halt vertauscht werden, damit das Ganze richtig ist.

01:06:16.340 --> 01:06:23.840
Deswegen haben wir hier linearen Aufwand. Das ist also ganz einfach. Die wesentliche Idee ist

01:06:23.840 --> 01:06:33.160
dieser Aufteilungsschritt. Das muss man im Kopf haben. Gut, was haben wir hier für eine Zeitkomplexität?

01:06:34.760 --> 01:06:41.660
Für Schritt 3, wir machen das Ganze rekursiv. Da wird also jetzt die Zeit für Quicksort mit N

01:06:41.660 --> 01:06:50.200
Elementen ist also gleich der Zeit von Quicksort, ja, auf einer Folge der Länge, also auf der Folge

01:06:50.200 --> 01:06:57.080
S-Strich und Quicksort auf einer Folge S2-Strich. Da wissen wir gar nicht, wie lange die sind.

01:07:00.620 --> 01:07:07.640
Und anschließend, nicht anschließend, außerdem Zeitaufwand O von N. Aufwand O von N brauchen wir

01:07:07.640 --> 01:07:15.140
für diese Aufteilung. Wir haben also hier nur Arbeit für die Aufteilung und für die rekursive

01:07:15.140 --> 01:07:20.100
Anwendung des Verfahrens. Wir brauchen die Lösungen, die rauskommen, nicht mehr zusammenzusetzen,

01:07:20.100 --> 01:07:28.080
weil die beim Aufteilen bereits diese Pivot-Elemente immer an die richtige Position gesetzt wurden.

01:07:29.720 --> 01:07:35.420
Deswegen haben wir am Ende keinen Kombinationsaufwand mehr, wie wir das ansonsten beim allgemeinen

01:07:35.420 --> 01:07:41.460
Divide-and-Conquer-Verfahren ausgeguckt haben. Also lineare Aufwand. Das Dumme ist, im schlechtesten

01:07:41.460 --> 01:07:49.420
Fall steht das C nach wie vor an der linken Position. Alle Elemente sind größer als dieses

01:07:49.420 --> 01:07:56.420
C. Und das kann sich so der Reihe nach fortsetzen. Und dann haben wir halt gerade nur immer Folgen,

01:07:56.500 --> 01:08:04.020
die gerade um 1 kleiner sind. Und wir haben eine Gesamtzeit von Größenordnung N². Wissen Sie,

01:08:04.120 --> 01:08:12.690
alle schlechteste Fall von Quicksort braucht N²-Vergleiche. Im besten Fall haben wir eine

01:08:12.690 --> 01:08:22.090
Formel. T von N ist 2 mal T von N½. Etwas weniger als N½, weil wir ein Element rausgenommen haben.

01:08:22.570 --> 01:08:28.050
Das heißt, das C liegt genau in der Mitte. Und das Ganze läuft auch weiter immer so. Der beste

01:08:28.050 --> 01:08:35.790
Fall wäre, dass wir jeweils genau hälftig aufteilen können. Dann hätten wir also hier 2 mal T von N½

01:08:35.790 --> 01:08:43.990
plus O von N. Und dann sehen Sie sofort, das ist Aufwand N log N. Deswegen nennt man es halt

01:08:43.990 --> 01:08:51.510
Quicksort. Aber der beste Fall ist natürlich nicht ausreichend. Dazu muss man noch mehr wissen. Dazu

01:08:51.510 --> 01:08:58.590
muss man sich das Verhalten im Mittel anschauen. Denn das Verhalten im schlechtesten Fall war ja

01:08:58.590 --> 01:09:07.930
nicht besser als bei den anderen Verfahren. Es war sogar so, dass das Verhalten im besten Fall,

01:09:08.350 --> 01:09:13.850
also Sortieren durch Einfügen, besser ist. Es ist im schlechtesten Fall nicht schlechter,

01:09:14.570 --> 01:09:19.170
im besten Fall besser. Also würde man zunächst mal sagen, dann nehme ich doch Sortieren durch

01:09:19.170 --> 01:09:24.790
Einfügen. Das ist viel einfacher strukturiert als Quicksort. Und für einige Fälle nimmt man

01:09:24.790 --> 01:09:31.190
auch Sortieren durch Einfügen, weil man da durchaus, wenn man also vorsortierte Folgen hat,

01:09:31.270 --> 01:09:39.850
da kann man durchaus Vorteile haben gegenüber Verfahren wie Quicksort. Schauen wir uns das

01:09:39.850 --> 01:09:47.010
mittlere Verhalten an. Da habe ich jetzt einfach hier dieses V von J angegeben als Anzahl der,

01:09:47.990 --> 01:09:53.410
also mittlere Anzahl der Vergleiche bei Aufruf von Quicksort auf einer Teilliste der Länge J.

01:09:53.790 --> 01:10:01.070
Wir haben ja unsere Folge zu betrachten, die, ups, ist doch ein Fehler, wenn man den Bildschirm nicht

01:10:01.070 --> 01:10:06.650
richtig auflegt, dann schreibt man nicht mehr gerade. Wir müssen also jetzt irgendeinen Abschnitt aus

01:10:06.650 --> 01:10:14.210
dieser Folge uns ja hernehmen und wir schauen uns an, wie ist der Aufwand, wenn wir eine Folge der

01:10:14.210 --> 01:10:22.730
Länge J haben als Teilliste. Das ist V von J. So, wir nehmen an, dass alle Listenlängen beziehungsweise

01:10:22.730 --> 01:10:29.670
alle Positionen des Pivot-Elements in der Folge gleich wahrscheinlich sind. Und da muss man sich

01:10:29.670 --> 01:10:38.310
einfach überlegen, was man rauskriegt als Anzahl der Vergleiche. Wenn die Liste die Länge 1 hat

01:10:38.310 --> 01:10:47.130
oder die Länge 0 hat, dann brauchen wir gar nichts zu machen. Das ist ja klar. Und für den

01:10:47.130 --> 01:10:56.820
Fall, für den allgemeinen Fall, wir haben also eine Länge N. Ja, welche, ich sagte, alle Listen sind

01:10:56.820 --> 01:11:01.100
gleich wahrscheinlich, alle Möglichkeiten sind gleich wahrscheinlich. Alle Positionen gleich

01:11:01.100 --> 01:11:06.740
wahrscheinlich heißt, wir haben N verschiedene Positionen für C. Und für jede dieser N-Positionen

01:11:06.740 --> 01:11:15.740
bekommen wir zwei Teillisten, in denen Quicksort aufgerufen werden muss. Und das ist einmal, wenn

01:11:15.740 --> 01:11:24.680
das Element an Position I liegt, dann muss gerade eine, die Folge links davon, die hat ja I-1-Elemente,

01:11:25.100 --> 01:11:31.040
da müssen wir Quicksort drauf anwenden und auf die Folge rechts von dem C, das sind gerade N-I-Elemente.

01:11:33.720 --> 01:11:40.880
Und außerdem haben wir noch einen Aufwand N plus 1, das ist der Aufwand für das Aufteilen der Liste.

01:11:43.340 --> 01:11:51.520
Da werden N plus 1 Vergleiche ausgeführt. Wenn man sich das genauer anschaut, stellt man fest,

01:11:51.840 --> 01:11:59.060
hier steht ja VI-1, VN-I. Wenn wir uns diese Summe anschauen, die bisschen umordnen, N plus 1 steht

01:11:59.060 --> 01:12:10.700
jedes Mal da drin. Da wird durch N geteilt, also da steht vorne N plus 1 plus, ja, jede Folge

01:12:11.480 --> 01:12:18.320
von I gleich 0, also jeder Wert von I gleich 0 bis N minus 1, taucht hier genau zweimal auf.

01:12:19.680 --> 01:12:28.900
Es taucht V von 0 auf, hier gleich 1 und hier taucht für I gleich N, haben wir hier nochmal V von 0 drin stehen

01:12:28.900 --> 01:12:34.560
und so weiter. Jede Listenlinie taucht hier in dieser Summe genau zweimal auf, deswegen haben wir

01:12:34.560 --> 01:12:45.740
also hier N plus 1 plus 2 durch N mal die mittlere Anzahl der Vergleiche für die Listenlängen 0 bis N minus 1.

01:12:48.920 --> 01:13:00.000
Und jetzt machen wir eine kleine Zwischenüberlegung. Wir schauen uns an, diesen Term N plus 1 mal VN plus 1

01:13:01.620 --> 01:13:12.180
und ziehen davon ab, N mal V von N. Was kommt dabei raus? Wir haben ja hier gerade diese Formel

01:13:12.180 --> 01:13:20.740
aufgeschrieben, hier oben die Formel, das heißt wir haben N plus 1 mal VN plus 1, das ist N plus 1 mal

01:13:22.760 --> 01:13:31.700
N plus 2 plus 2 mal I gleich 0 bis N V von I, das ist also dieser Term hier für V von N plus 1 aufgeschrieben.

01:13:32.900 --> 01:13:45.560
Da steht ja gerade N plus 1 plus 1 plus I gleich 0 bis N plus 1 minus 1. Minus N mal, da N mal V von N,

01:13:46.800 --> 01:13:56.540
N mal V von N ist aber gerade N mal N plus 1 minus zweimal, das N hier geht ja weg, zweimal diese Summe.

01:13:57.960 --> 01:14:09.260
Und wenn wir das hier uns anschauen, dann steht hier N plus 1 mal N plus 2 minus N mal N plus 1,

01:14:09.260 --> 01:14:20.180
da bleibt also genau zweimal N plus 1 übrig. Und hier steht diese Summe bis N, hier steht die gleiche Summe nochmal bis N minus 1,

01:14:20.660 --> 01:14:29.660
also bleibt hier zweimal V von N übrig. Das ist also das, was übrig bleibt, 2N plus 1 plus 2V von N.

01:14:30.600 --> 01:14:44.480
Und jetzt ordnen wir das einfach um, da kommt dann raus, V von N plus 1 ist gleich, da habe ich also jetzt das N mal V von N hier noch nach rechts rüber gebracht,

01:14:44.620 --> 01:14:53.940
das sind dann hier gerade N plus 2 mal V von N, das Ganze durch N plus 1 dividiert, gibt also jetzt N plus 2 durch N plus 1 mal V von N.

01:14:53.940 --> 01:15:10.340
Bisschen Rumrechnerei. Und jetzt behaupte ich einfach, dass man hier raus schließen kann, dass V von N gleich 2 mal N plus 1 mal Summe I gleich 3 bis N plus 1, 1 durch I ist.

01:15:11.600 --> 01:15:22.480
Dieses kann man beweisen durch Induktion, also diesen Teil hier, also diese erste Gleichheit kann man leicht durch Induktion beweisen.

01:15:23.660 --> 01:15:34.220
Ganz einfach, will ich gar nicht machen. Und der zweite Teil, dass das Ganze aus N durch N mal log N ist, ist eine kleine Überlegung, die so aussieht.

01:15:35.500 --> 01:15:45.500
Wenn wir wissen, dass das V von N so ein 2 N plus 1 mal Summe I gleich 3 bis N plus 1, 1 durch I ist, das ist also das, was uns interessiert, ist diese Summe hier.

01:15:48.700 --> 01:15:58.640
Und hier steht nicht diese Summe, sondern da steht eine Abschätzung. Diese Abschätzung kann man sich visualisieren, so wie es hier angegeben ist.

01:15:59.640 --> 01:16:10.500
Hier ist angegeben die Funktion 1 durch X an den Positionen I minus 1, I und I plus 1.

01:16:12.720 --> 01:16:36.920
Und diese Werte, 1 durch I, stehen jetzt zu dem Flächeninhalt, jeweils zu dem Integral von I bis I plus 1, das ist also dieser Bereich hier, unterhalb der Kurve.

01:16:38.920 --> 01:16:48.540
Und das ist 1 durch I mal 1, das ist gerade 1 durch I.

01:16:51.140 --> 01:16:58.680
Dieses Rechteck ist größer gleich dem Wert des Integrals, denn der Wert des Integrals ist ein bisschen kleiner, da ist die obere Ecke ja nicht drin.

01:16:58.680 --> 01:17:10.460
Und der ist kleiner gleich, das ist dieses untere Rechteck, als hier entsprechend der Wert des Integrals von I minus 1 bis I.

01:17:11.320 --> 01:17:26.980
Wenn ich diese Abschätzung habe, dann habe ich sofort eine Abschätzung für die Summe 1 durch I, das ist nämlich gerade das Integral von 1 bis N.

01:17:26.980 --> 01:17:36.440
Wenn wir die Summe I gleich 2 bis N, 1 durch I nehmen, ist das kleiner gleich dem Integral, also der Summe der Integrale, das gibt aber das zusammengesetzte Integral.

01:17:37.820 --> 01:17:46.100
Und Sie kennen alle aus der Integralrechnung, wissen Sie, das Integral von 1 durch X ist lnN, plus 1 in dem Fall.

01:17:47.780 --> 01:17:55.200
Und das ist aus Größenordnung, also log N, ist egal auf welche Basis man da nimmt, das ist ein konstanter Faktor.

01:17:55.200 --> 01:18:11.520
Und da haben wir genau diese Summe, die ist also in der Größenordnung lnN, und damit haben wir hier für unser Quicksort nachgewiesen, dass das im Mittelaufwand nln hat.

01:18:13.300 --> 01:18:18.140
Ich nehme an, dass Ihnen das nicht vorgeführt wurde in Informatik 1, deswegen habe ich es hier so ausführlich gemacht.

01:18:18.880 --> 01:18:36.180
Und es zeigt auch, dass man, um abzuschätzen, welchen Aufwand ein Verfahren im Mittel hat, dass man dafür doch ein bisschen mehr Überlegungen machen muss, als wenn man nur den schlechtesten Fall abschätzt.

01:18:37.300 --> 01:18:41.560
Hier geht das relativ leicht, häufig ist es deutlich schwieriger als das, was wir hier gemacht haben.

01:18:44.180 --> 01:18:49.000
Quicksort ist also ein ganz schönes Verfahren, weil es im Mittel schneller ist als die anderen, die wir bisher betrachtet haben.

01:18:49.260 --> 01:18:53.920
Das Problem ist nur diese Abhängigkeit von der Wahl des Pivot-Elementes.

01:18:53.980 --> 01:19:02.540
Man könnte das verbessern, indem man sagt, meinetwegen, ich wähle immer das mittlere von drei Elementen, also ich habe hier meine Folge,

01:19:03.280 --> 01:19:10.920
und ich betrachte einfach das linke, das rechte und das mittlere Element und nehme von diesen dreien das mittlere Element.

01:19:10.920 --> 01:19:18.040
Das ist ein bisschen Aufwand, noch vorher extra zu machen, und dann kann ich vielleicht besser aufteilen.

01:19:18.760 --> 01:19:23.480
Sie können sich sofort den schlechtesten Fall überlegen, bei dem Sie auch hier den Aufwand in Quadrat kriegen.

01:19:25.140 --> 01:19:28.940
Bringt also insofern nichts für den schlechtesten Fall.

01:19:32.980 --> 01:19:37.980
Und natürlich, der beste Fall geht auch nicht besser als nlog n, das wissen wir auch.

01:19:39.040 --> 01:19:44.380
Eine andere Idee ist, ich wähle ein zufälliges Element aus.

01:19:45.320 --> 01:19:50.460
Also ich schmeiße mal Zufallszahlengenerator an, wähle mir auch zufällig eine Position zwischen 1 und n,

01:19:51.580 --> 01:19:56.320
und wähle das Element, mache danach jetzt die Aufteilung.

01:19:58.360 --> 01:20:02.160
Und dann bekomme ich ein sogenanntes randomisiertes Quicksort,

01:20:03.400 --> 01:20:08.180
und habe kein deterministisches Verfahren mehr, sondern ein zufälliges, randomisiertes Verfahren.

01:20:09.080 --> 01:20:16.000
Und da kann ich jetzt einen Erwartungswert für die Laufzeit ausrechnen, und dieser Erwartungswert für die Laufzeit ist nlog n.

01:20:18.320 --> 01:20:27.080
Und zwar, wenn Sie mir hundertmal oder beliebig oft eine Liste geben, die eigentlich ein schlechtester Fall ist,

01:20:27.080 --> 01:20:30.300
also eine völlig vorsortierte Liste, schlechtester Fall für Quicksort,

01:20:31.740 --> 01:20:39.060
wenn Sie ein randomisiertes Verfahren nehmen, dann bekommen Sie hier Erwartungswert,

01:20:39.120 --> 01:20:45.900
weil Sie ja immer zufällige Elemente rauswählen, bekommen Sie hier als Erwartungswert für die Zeit nlog n raus.

01:20:47.660 --> 01:20:54.760
Und das heißt, hier haben Sie ein Verfahren, das für die Praxis eigentlich besser anwendbar ist als die anderen Verfahren,

01:20:56.060 --> 01:21:05.940
weil Sie halt hier im Schnitt Aufwand nlog n haben und nicht im Schnitt n²,

01:21:06.200 --> 01:21:11.300
unabhängig davon, welche Verteilung Ihre zu sortierenden Folgen haben.

01:21:13.380 --> 01:21:17.240
Insofern ist das hier ein großer Vorteil, das Problem ist nur,

01:21:17.820 --> 01:21:21.120
Sie müssen dann natürlich in der Lage sein, auf den Zufallszahlengenerator zuzugreifen,

01:21:21.120 --> 01:21:26.340
und auch der Aufwand kann natürlich so sein, dass Sie sagen, dadurch wird das Verhalten wieder verschlechtert,

01:21:27.840 --> 01:21:31.260
und dann schaue ich mich doch nach einer Alternative um.

01:21:33.060 --> 01:21:38.480
Alternative dazu wäre, das wissen Sie alle noch, Heapsort,

01:21:39.120 --> 01:21:42.680
das ist auch im schlechtesten Fall und im Mittel besser als Quicksort,

01:21:43.540 --> 01:21:45.520
allerdings nur leicht, nur für große Folgen.

01:21:46.720 --> 01:21:51.180
Man kann sich aber auch zunächst mal ein anderes Verfahren anschauen,

01:21:51.240 --> 01:21:59.000
bei dem man diese Schwachstelle, dass man nicht weiß, wo das Pivot-Element hinkommt, von vornherein ausschließt.

01:21:59.120 --> 01:22:02.220
Und das wäre eine strenge Anwendung von divide & conquer.

01:22:03.940 --> 01:22:08.020
Ich erzwinge einfach eine gleichmäßige Aufteilung,

01:22:08.960 --> 01:22:14.420
indem ich die beiden, also meine Folge einfach aufteile in zwei Listen.

01:22:14.420 --> 01:22:20.300
Also ich habe hier meine große Folge, teile ich auf in zwei Listen halber Länge,

01:22:20.640 --> 01:22:22.900
und sage, jetzt sortiere doch bitte diese beiden Folgen.

01:22:27.380 --> 01:22:30.620
Und das ist mir immer noch zu schwer, ich teile die wiederum auf,

01:22:30.680 --> 01:22:36.220
jetzt habe ich vier Folgen der Größe 2, die sind mir immer noch zu schwierig,

01:22:36.340 --> 01:22:42.560
jetzt habe ich in dem Fall acht Folgen der Länge 1, das fällt mir leicht, die zu sortieren.

01:22:42.560 --> 01:22:45.620
Jetzt weiß ich, wie das geht, ich brauche mich gar nichts zu machen,

01:22:46.260 --> 01:22:48.460
und jetzt kommt der eigentliche Aufwand in diesem Verfahren,

01:22:49.260 --> 01:22:53.680
jetzt werden die zusammengebracht, die werden verschmolzen.

01:22:54.280 --> 01:23:02.760
Das heißt, jetzt muss ich vier, oder ich muss acht Folgen, jeweils also zwei, zusammenfügen zu einer Folge, die sortiert ist.

01:23:03.580 --> 01:23:05.880
Dabei werden also auch einige Elemente hier vertauscht,

01:23:06.120 --> 01:23:11.020
da in diesem Fall habe ich also hier die Elemente tatsächlich an andere Positionen gebracht,

01:23:11.020 --> 01:23:14.320
und da genauso, da passiert wirklich was.

01:23:15.580 --> 01:23:18.960
Und jetzt kommt der nächste Aufwand, ich muss diese vier Folgen der Länge 2

01:23:22.440 --> 01:23:28.220
zusammenmischen zu zwei Folgen der Länge 4, die jeweils sortiert sind,

01:23:28.880 --> 01:23:36.180
und jetzt kann ich die beiden Folgen zusammenschmelzen, vermischen zu einer Gesamtfolge, die sortiert ist.

01:23:36.180 --> 01:23:44.660
Das heißt, wenn wir bei Quicksort den Aufwand reingesteckt haben in das Aufteilen der Folgen, bis sie ganz klein waren,

01:23:45.500 --> 01:23:49.780
und durch diese Arbeit beim Aufteilen waren schon immer die Elemente nachher am richtigen Platz,

01:23:50.640 --> 01:23:54.440
haben wir hier keinen Aufwand reingesteckt in das Aufteilen,

01:23:55.220 --> 01:23:57.820
sondern stecken den Aufwand in das Zusammensetzen der Lösungen,

01:23:58.400 --> 01:24:03.340
da müssen wir jeweils sortierte Teilfolgen verschmelzen zu einer neuen sortierten Folge.

01:24:03.340 --> 01:24:06.540
Und das ist hier der Aufwand, der jeweils getrieben werden muss.

01:24:08.300 --> 01:24:12.400
Also vollständig gleichmäßige Aufteile in der Liste, wir haben genau Log N Merge-Stufen,

01:24:12.940 --> 01:24:23.100
das gibt uns eine sehr schöne Formel für den Aufwand, nämlich 2 mal T Merge Sort in halbe plus T Merge von N.

01:24:25.080 --> 01:24:33.140
Und der Aufwand zum Zusammenschmelzen zweier Folgen, der ist in N Log N, wenn das Verschmelzen in N ist.

01:24:33.980 --> 01:24:40.980
Das ist aber, also wie man zwei Folgen zusammensetzt, zusammen verschmilzt, das ist ja gar nicht weiter schwer.

01:24:41.280 --> 01:24:44.780
Also zwei Folgen zusammensetzen, das ist relativ einfach.

01:24:44.940 --> 01:24:50.400
Da muss ich doch nur, wenn ich hier zum Beispiel diese beiden Folgen zusammensetzen will,

01:24:50.400 --> 01:24:54.540
ich vergleiche 1 ist kleiner gleich 4, kommt die 1 dahin.

01:24:54.620 --> 01:24:57.980
Gehe hier weiter, die 2 ist kleiner gleich 4, kommt dorthin.

01:24:58.540 --> 01:25:00.480
Die 3 ist kleiner gleich 4, kommt dorthin.

01:25:01.100 --> 01:25:04.180
Die 5 ist größer als 4, dann muss ich die 4 dahin schreiben.

01:25:04.820 --> 01:25:09.440
Die 6 ist größer als 5, dann muss ich die 5 dahin schreiben.

01:25:09.780 --> 01:25:12.400
Muss da weitermachen, dann bin ich fertig, dann kommt der Rest der Liste rein.

01:25:12.840 --> 01:25:17.320
Ich muss also nur linear durch die beiden Folgen durchlaufen, linearer Aufwand.

01:25:17.320 --> 01:25:20.900
Das heißt, ich habe hier Aufwand N Log N insgesamt, gar kein Problem.

01:25:21.820 --> 01:25:26.280
Und ich habe hier also sofort ein Verfahren, das im schlechtesten Fall Aufwand N Log N hat.

01:25:27.040 --> 01:25:39.400
Und da ich hier datenunabhängig das Ganze mache, habe ich auch im besten Fall für diese Log N Stufen meinen Aufwand N Log N.

01:25:39.600 --> 01:25:40.480
Geht also nicht besser.

01:25:41.900 --> 01:25:42.500
Parallel.

01:25:43.880 --> 01:25:46.060
Wieder eine parallele Variante.

01:25:46.500 --> 01:25:47.580
Paralleles Merge Sort.

01:25:48.200 --> 01:25:51.700
Würde also das entsprechende paralleles Merge verwenden.

01:25:52.340 --> 01:25:57.740
Und da ist die Frage, wie kann ich denn das parallele Mischen parallel machen?

01:25:59.000 --> 01:26:02.060
Also das Mischen parallel machen, wie geht das, wie viele Schritte brauche ich dafür?

01:26:03.160 --> 01:26:05.240
Und das ist ein bisschen schwieriger.

01:26:05.240 --> 01:26:11.400
Da muss man misstrauisch sein, wenn man das mit dem parallelen Minimumsbestimmen sich überlegt hat.

01:26:11.920 --> 01:26:19.840
Wenn das in konstanter Zeit ginge, das parallele Mischen, dann hätte ich hier eine Formel, bei der ich Aufwand Log N hätte.