WEBVTT 00:03.120 --> 00:04.120 So, schönen guten Tag. 00:04.200 --> 00:07.240 Ich begrüße Sie zur Fortsetzung der Vorlesung effizienter Algorithmen. 00:08.080 --> 00:15.240 Wir haben uns letztes Mal beschäftigt mit, zunächst mal, auch mit den 00:15.240 --> 00:18.220 rot -schwarzen Bäumen, wir haben uns zunächst mal die 00:18.220 --> 00:23.680 Selektionsverfahren angeguckt, das Verfahren für die Bestimmung des 00:23.680 --> 00:24.740 Medians zum Beispiel. 00:24.780 --> 00:27.100 Ich hatte Ihnen Quick Select vorgestellt, ich hatte Ihnen die 00:27.100 --> 00:29.500 Selektion in linearer Zeit vorgestellt, also insbesondere 00:29.500 --> 00:33.060 Medianbestimmung in linearer Zeit. 00:33.220 --> 00:37.180 Etwas, was eigentlich so aussieht, wenn man das Problem sieht, dass es 00:37.180 --> 00:41.120 deutlich wesentlich einfacher ist als sortieren und es zeigt sich eben 00:41.120 --> 00:42.260 auch, dass es tatsächlich geht. 00:42.360 --> 00:45.960 Quick Select hat es schon im mittleren Fall linear und mit diesem 00:45.960 --> 00:48.980 Verfahren, wo man eben dafür sorgt, dass man im Prinzip Quick Select 00:48.980 --> 00:53.160 macht, aber das Pivot-Element effizient so bestimmt, dass man bei 00:53.160 --> 00:58.580 jedem rekursiven Schritt eine ausreichend große Folge abschneiden 00:58.580 --> 00:58.880 kann. 00:59.400 --> 01:02.780 Das hat dann halt lineare Laufzeit insgesamt. 01:02.960 --> 01:05.260 Wir hatten uns das angeschaut, gesehen, dass man das auch sehr gut 01:05.260 --> 01:09.180 parallelisieren kann, zumindest erwähnt, dass man das machen kann und 01:09.180 --> 01:11.220 wir sind dann zu den Suchverfahren gekommen. 01:11.500 --> 01:16.660 Ich habe Ihnen vorgestellt, die verschiedenen Baumarten, mit denen man 01:16.660 --> 01:17.440 so etwas macht. 01:17.560 --> 01:19.620 Wir hatten gesehen, was ein binärer Suchbaum ist. 01:19.680 --> 01:23.840 Ich hatte Ihnen erzählt, dass es dazu die höhenbalancierten Bäume 01:23.840 --> 01:25.280 gibt, die AVL-Bäume. 01:26.140 --> 01:28.860 Es gibt eine Vielfalt von anderen Bäumen. 01:28.980 --> 01:31.720 Wenn Sie sich anschauen, Literatur zu Suchverfahren, Datenstrukturen 01:31.720 --> 01:35.300 für Suchen, gibt es sehr, sehr viele verschiedene Strukturen. 01:35.480 --> 01:38.120 Ich habe Ihnen hier nur einen ganz kleinen Ausschnitt dargestellt, 01:38.600 --> 01:42.680 aber die 2-3-4-Bäume sind eben, insbesondere mit der Variante der Rot 01:42.680 --> 01:47.140 -Schwarz -Bäume, dann eine Datenstruktur, die sich als sehr effizient 01:47.140 --> 01:48.020 herausgestellt hat. 01:48.320 --> 01:51.780 Je nachdem, was für Anwendungsszenarien man hat, welche Arten von 01:51.780 --> 01:55.680 Suchen man hat, wie die Dateien strukturiert sind, gibt es aber noch 01:55.680 --> 02:00.380 eine Vielfalt anderer Datenstrukturen, die man dort sinnvoll einsetzen 02:00.380 --> 02:00.740 kann. 02:01.300 --> 02:05.880 Splash -Trees und so, also wirklich eine Vielfalt von Bäumen, die ich 02:05.880 --> 02:07.020 Ihnen hier alle nicht vorstellen kann. 02:07.120 --> 02:11.780 Ich wollte einfach nur diese klassischen Verfahren Ihnen darstellen. 02:12.360 --> 02:14.920 Und wir hatten gesehen, bei den 2-3-4-Bäumen haben wir halt eine 02:14.920 --> 02:22.580 Struktur, die dazu führt, dass wir tatsächlich einen einigermaßen 02:22.580 --> 02:26.380 ausgeglichenen Baum bekommen, wobei eben die Ungleichgewichte in den 02:26.380 --> 02:30.300 Knoten sind, dadurch, dass wir dort 1-3 Schlüssel haben, aber die 02:30.300 --> 02:32.180 Pfadlängen sind alle die gleichen. 02:33.180 --> 02:38.340 Und im Prinzip ist das eine Variante der B-Bäume, eben hier mit einer 02:38.340 --> 02:43.220 sehr kleinen Anzahl von Schlüsseln, die maximal in dem Knoten drin 02:43.220 --> 02:48.800 sein können, während das beim B-Baum bis zu Blockgröße im 02:48.800 --> 02:53.240 Speicherbereich sind, können das hier eben nur maximal 3 Schlüssel 02:53.240 --> 02:54.300 sein pro Knoten. 02:54.820 --> 02:58.520 Und ich hatte Ihnen dann verschiedene Operationen dargestellt, wir 02:58.520 --> 03:00.940 hatten gesehen, was für Probleme da auftreten können, und dann haben 03:00.940 --> 03:04.460 wir uns die Rot-Schwarz-Bäume angeschaut, hatten gesehen, wie man die 03:04.460 --> 03:10.680 realisieren kann und hatten dann diskutiert, inwieweit das jetzt 03:10.680 --> 03:11.900 wirklich ein Vorteil ist. 03:14.380 --> 03:17.720 Und natürlich gibt es da auch Operationen, die man sich anschauen 03:17.720 --> 03:22.700 muss, es ist nicht sehr trivial, wie man dort die Operation macht, das 03:22.700 --> 03:28.580 Umbauen von einem Knoten, also wenn man das aufteilt, dass man eben 03:28.580 --> 03:31.060 weiß, welche Knoten darunter sind und so weiter, dass man feststellt, 03:31.120 --> 03:33.020 ob ein Knoten tatsächlich ein Vierknoten ist. 03:33.400 --> 03:35.440 Hier in dem Fall, wo man da hinkommt, muss man erstmal feststellen, 03:35.540 --> 03:37.040 welche beiden Nachfolger sind, das haben wir das letzte Mal 03:37.040 --> 03:37.560 diskutiert. 03:37.560 --> 03:41.000 Aber es gibt insgesamt schon eine effiziente Art, das zu 03:41.000 --> 03:44.940 implementieren, und damit hat man eine Suchbaumstruktur, die man sehr 03:44.940 --> 03:49.000 gut verwenden kann, die einem eben eine Durchführung der Operationen 03:49.000 --> 03:51.760 in logarithmischer Zeit ermöglicht, das, was man gerne erreichen 03:51.760 --> 03:52.100 möchte. 03:52.520 --> 03:55.220 Damit sind wir durch dieses klassische Gebiet Suchen und Sortieren 03:55.220 --> 04:01.420 durch, und ich komme zum nächsten Problem, zum nächsten Problemklasse, 04:01.420 --> 04:08.680 die Sie wahrscheinlich auch kennen aus anderen, eventuell aus 04:08.680 --> 04:10.840 oberrechtlichen Schülern, das müssten Sie eigentlich Grafen auch 04:10.840 --> 04:11.720 kennengelernt haben. 04:12.820 --> 04:17.660 Ich werde hier jetzt die Algorithmen für solche Grafen nochmal genauer 04:17.660 --> 04:19.420 bei mir angucken, und insbesondere werden wir uns auch ein paar 04:19.420 --> 04:21.040 parallele Varianten anschauen. 04:22.000 --> 04:25.900 Es geht also hier um typische Probleme in Grafen. 04:26.000 --> 04:28.420 Was sind typische Probleme in Grafen? 04:28.520 --> 04:29.820 Zunächst mal, was ist ein Graf? 04:29.820 --> 04:32.980 Wir können ihn gerichtet betrachten, da haben wir irgendwelche Knoten, 04:33.800 --> 04:39.500 und diese Knoten sind verbunden durch irgendwelche Kanten, und die 04:39.500 --> 04:44.160 Knotenmenge ist eine Menge V für Vertices, und die Kantenmenge ist E 04:44.160 --> 04:49.420 für Edges, und damit haben wir als Kantenmenge hier bei einem 04:49.420 --> 04:54.280 gerichteten Grafen jeweils ein paar von Knoten, also in dem Fall hier 04:54.280 --> 04:59.140 wäre das hier die Kante 1,4. 04:59.860 --> 05:05.260 Das ist also ein typisches Beispiel für solche Grafen, und wir wissen, 05:05.380 --> 05:09.820 dass man damit zig verschiedene Dinge in der Welt modellieren kann, 05:09.980 --> 05:15.460 dass viele Probleme, die man bearbeitet, als Probleme auf Grafen 05:15.460 --> 05:16.640 modelliert werden können. 05:17.220 --> 05:19.440 Hier sind alle möglichen Dinge aufgeführt, Leitungsnetz, 05:19.520 --> 05:23.420 Flussdiagramm, Kontrollfluss, Schaltnetz, Projektstrukturen, 05:23.420 --> 05:27.480 Relationen im Internet, die ganzen Verbindungen, die wir dort haben, 05:28.840 --> 05:34.020 Fahrpläne und Ähnliches, also wenn Sie Fahrplansuchen machen, was Sie 05:34.020 --> 05:37.120 bei der Bahn herausfinden können, kürzere Verbindungen zwischen zwei 05:37.120 --> 05:41.420 Wegen, Navigationsprobleme, Sie wollen von A nach B und suchen dafür 05:41.420 --> 05:43.300 den bestmöglichen Weg. 05:44.040 --> 05:47.060 Das sind alles typische Probleme, die man hier bearbeiten muss, oder 05:47.060 --> 05:50.500 Sie wollen in einem Grafen feststellen, was passiert, wenn ein Knoten 05:50.500 --> 05:53.380 wegfällt, oder eine Kante wegfällt, ist ja immer noch vollständig 05:53.380 --> 05:53.840 verbunden. 05:53.840 --> 05:57.200 Das sind zig Probleme, die sehr hohe praktische Relevanz haben. 05:58.320 --> 06:05.760 Und solche Grafen sind halt dargestellt, wie gesagt, durch Knoten und 06:05.760 --> 06:06.140 Kanten. 06:06.560 --> 06:08.620 Wie ist die Problemgröße hierbei? 06:08.800 --> 06:13.840 Da guckt man sich an, die Anzahl der Knoten und die Anzahl der Kanten 06:13.840 --> 06:15.960 spielt natürlich auch eine Rolle, die Anzahl der Kanten kann 06:15.960 --> 06:19.240 quadratisch sein in der Anzahl der Knoten. 06:19.240 --> 06:22.460 Wenn Sie einen vollständig verbundenen Grafen haben, haben Sie n² 06:22.460 --> 06:29.000 halbe Kanten, und das heißt, man muss genau aufpassen, wie aufwendig 06:29.000 --> 06:30.900 dann die Algorithmen werden, die darauf laufen. 06:31.080 --> 06:34.040 Also zur vollständigen Beschreibung eines Grafen brauchen Sie im 06:34.040 --> 06:42.300 Prinzip n² Platz, wenn Sie n Knoten haben, oder Sie brauchen halt 06:42.300 --> 06:48.660 genau Platz m, wenn m die Anzahl der Kanten ist. 06:48.660 --> 06:51.420 Damit haben Sie eigentlich den Vollständigen beschrieben, 06:51.520 --> 06:53.380 beziehungsweise Maximum von n und m. 06:53.500 --> 06:57.840 Wenn Sie keine Kanten hätten, hätten Sie halt trotzdem die Anzahl der 06:57.840 --> 06:58.820 Knoten, sich hinzuschreiben. 06:59.320 --> 07:01.860 Also, das ist die Problemgröße. 07:01.980 --> 07:06.240 Wie stellt man das Ganze dar, einen solchen Grafen? 07:06.780 --> 07:10.340 Sie können das machen über eine Adjacenzmatrix, also wenn Sie hier 07:10.340 --> 07:14.580 einen Knoten i und einen Knoten j haben, schreiben Sie hier rein, ob 07:14.580 --> 07:15.640 der verbunden ist. 07:19.560 --> 07:23.100 Das heißt, wenn die Kante drin ist, haben Sie dort eine 1 stehen. 07:23.200 --> 07:25.740 Sie können das noch anders machen, Sie können da auch noch irgendeine 07:25.740 --> 07:28.980 Zahl hinschreiben, dann haben Sie da nicht nur die Information, da ist 07:28.980 --> 07:31.920 eine Verbindung da, sondern hätten Sie noch ein Gewicht an der Kante 07:31.920 --> 07:33.640 oder eine Entfernung oder ähnliches. 07:34.400 --> 07:38.980 Das heißt, diese Matrix kann noch interessantere Inhalte haben, als 07:38.980 --> 07:42.240 nur einfach eine Bool'sche Matrix zu sein, oder wäre das eine Matrix 07:42.240 --> 07:43.140 über ganzen Zahlen. 07:43.140 --> 07:46.140 Also, da gibt es verschiedenste Varianten. 07:46.260 --> 07:48.240 Platzbedarf dafür ist selbstverständlich quadratisch. 07:49.580 --> 07:55.800 Und Sie hätten also hier in dieser Zeile von i alle Kanten, die die 07:55.800 --> 08:01.880 Quelle i haben, und in der Spalte des Knotens j alle Kanten mit Ziel 08:01.880 --> 08:02.440 j. 08:03.520 --> 08:06.980 Das ist also eine sehr einfache Darstellung, kann aber eine deutlich 08:06.980 --> 08:12.740 zu große Darstellung sein, insbesondere wenn Sie Planarengrafen haben, 08:12.820 --> 08:18.080 also einen, bei dem Sie alle Kanten ohne Überschneidungen hinmalen 08:18.080 --> 08:21.400 können in der Ebene, dann haben Sie immer nur eine lineare Anzahl von 08:21.400 --> 08:25.360 Kanten in der Anzahl der Knoten, das heißt, dann bräuchten Sie nicht 08:25.360 --> 08:28.000 n², sondern nur Aufwand n, um das zu machen. 08:29.100 --> 08:32.780 Für solche Zwecke wäre es sinnvoller, nicht eine Adjacenzmatrix 08:32.780 --> 08:36.600 -Darstellung zu nehmen, sondern Adjacenzlisten, das heißt, Sie würden 08:36.600 --> 08:40.840 jeweils zu jedem Knoten hinschreiben, mit welchen anderen Kanten der 08:40.840 --> 08:44.840 verbunden ist, ähnlich wie das, was wir vorher gemacht hatten bei den 08:44.840 --> 08:49.840 Matrizen, dass wir dünn besetzte Matrizen betrachtet haben, im Prinzip 08:49.840 --> 08:54.360 kann es sein, dass interessante Grafen dünn besetzt sind, dann würde 08:54.360 --> 09:02.240 man eben solche Listen der Knoten nehmen, die von einem Knoten i aus 09:02.240 --> 09:06.820 über eine Kante erreicht werden und dann wäre der Aufwand eben gerade 09:06.820 --> 09:12.000 Anzahl der Knoten plus Anzahl der Kanten und insbesondere bei 09:12.000 --> 09:18.240 Planarengrafen wäre dann also der Aufwand für die Datenstruktur 09:18.240 --> 09:18.760 linear. 09:18.760 --> 09:22.360 Da muss man genau gucken, was man braucht, was für die Praxis wichtig 09:22.360 --> 09:25.740 ist und auch, welche Art von Operation man darauf macht, wie effizient 09:25.740 --> 09:29.160 man die dann auf diesen Datenstrukturen ausführen kann. 09:29.760 --> 09:32.720 Ich will auf die Datenstrukturen gar nicht so lange drauf eingehen, 09:32.800 --> 09:33.820 das ist eigentlich alles Standard. 09:34.460 --> 09:36.200 Welche wichtigen Begriffe brauchen wir hier? 09:36.300 --> 09:41.100 Wir betrachten Wege über irgendwelche Kanten, also hier von einem 09:41.100 --> 09:47.340 Knoten, wenn das hier u1 ist und das hier un, hätten wir also hier 09:47.340 --> 09:59.880 einen Weg von u1 nach vn, genau, immer Knoten uv, und das wäre also 09:59.880 --> 10:02.260 über eine Folge von Kanten dann dargestellt. 10:03.220 --> 10:09.200 u1 wäre hier die Quelle des Weges, vn wäre das Ziel des Weges und wir 10:09.200 --> 10:13.500 haben die Länge, das ist die Anzahl der Kanten und wenn wir also hier 10:13.500 --> 10:18.900 e1 bis en als Kanten haben, haben wir halt so eine Länge n, dann gibt 10:18.900 --> 10:23.240 es einfache Wege, bei denen wir nur unterschiedliche Knoten haben oder 10:23.240 --> 10:26.340 auch Wege mit Knotenwiederholungen, dann wären das irgendwelche 10:26.340 --> 10:31.480 Zyklen, das wäre also hier ein typischer Kreis, den wir dort drin 10:31.480 --> 10:38.380 hätten, und dann betrachten wir auch a-zyklische Graphen, Graphen, die 10:38.380 --> 10:44.000 keine Kreise enthalten, also das sind alles typische Begriffe, die Sie 10:44.000 --> 10:44.660 alle kennen. 10:46.300 --> 10:50.700 Und dann betrachten wir nicht nur gerichtete Graphen, sondern wir 10:50.700 --> 10:52.380 betrachten auch ungerichtete Graphen. 10:53.400 --> 10:58.640 Ungerichtet heißt, ich habe eine Kante zwischen zwei Knoten, wie hier 10:58.640 --> 11:02.500 angedeutet, aber diese Verbindung gilt in beide Richtungen, ich kann 11:02.500 --> 11:07.400 über diese Kante von i nach j oder auch von j nach i kommen und um das 11:07.400 --> 11:13.340 anzudeuten, schreibt man in der Regel solche Kanten als Menge i, j und 11:13.340 --> 11:17.140 damit habe ich also ausgedrückt, dass die Reihenfolge keine Rolle 11:17.140 --> 11:20.960 spielt, während bei der Tupelschreibweise natürlich die Reihenfolge 11:20.960 --> 11:21.660 eine Rolle spielt. 11:21.780 --> 11:24.680 Tupel sind immer gerichtet, Mengen halt nicht. 11:25.500 --> 11:31.760 Jetzt nennen wir einen ungerichteten Graphen zusammenhängend, wenn wir 11:31.760 --> 11:34.840 von jedem Knoten zu jedem anderen Knoten kommen können. 11:35.340 --> 11:38.440 Man kann ja auch bei gerichteten Graphen von zusammenhängenden Graphen 11:38.440 --> 11:43.700 reden, dann müssen wir unterscheiden, zusammenhängend und streng 11:43.700 --> 11:45.340 zusammen oder stark zusammenhängend. 11:45.340 --> 11:48.960 Beim gerichteten Graphen, wenn wir da die Bedingung haben, dass ich 11:48.960 --> 11:51.960 für alle Knoten einen Weg von i nach j haben muss, dann müssen das 11:51.960 --> 11:55.220 gerichtete Wege sein und dann wird das der starke Zusammenhang. 11:55.300 --> 11:58.480 Hier betrachten wir nur den ungerichteten Graphen, der ist 11:58.480 --> 12:02.760 zusammenhängend, wenn es also für je zwei Knoten einen Weg von i nach 12:02.760 --> 12:03.340 j gibt. 12:04.240 --> 12:08.900 Das heißt, dieser Graph zerfällt nicht in zwei Teile oder mehrere 12:08.900 --> 12:15.860 Teile und bei einem Baum, da gehen wir also davon aus, Baum ist halt 12:15.860 --> 12:19.840 so definiert, dass das ein zusammenhängender und a-zyklischer Graph 12:19.840 --> 12:25.160 ist, also zusammenhängend, ich habe also hier irgendwelche Knoten und 12:25.160 --> 12:30.000 Sie wissen alle, was ein Baum ist, das ist ein typischer Baum und 12:30.000 --> 12:34.080 sobald wir hier irgendeine Kante hätten, die zwei Knoten weiter unten 12:34.080 --> 12:37.040 verbindet, hätten wir im ungerichteten Graphen damit sofort einen 12:37.040 --> 12:37.540 Kreis. 12:37.540 --> 12:44.160 Das wäre dann also zyklisch oder ein Zyklus, das darf nicht sein, so 12:44.160 --> 12:44.820 ist es ein Baum. 12:45.320 --> 12:48.800 Sobald wir eine Kante dazwischen hätten, auf Knoten, die auf 12:48.800 --> 12:53.060 verschiedenen Pfaden liegen, hätten wir halt einen Kreis dort drin. 12:56.600 --> 13:00.320 Also dieses, natürlich muss man dabei noch berücksichtigen, dass das 13:00.320 --> 13:04.240 ij, also diese eine Kante hier, wenn ich mir das hier anschaue, könnte 13:04.240 --> 13:06.020 ich sagen, da habe ich einen Kreis. 13:06.020 --> 13:09.120 Im gerichteten Graphen könnte ich sagen, ich habe hier einen trivialen 13:09.120 --> 13:13.220 Kreis, der zwei Knoten miteinander verbindet, aber das betrachten wir 13:13.220 --> 13:16.800 halt nicht als einen echten Kreis, sondern beim echten Kreis bräuchten 13:16.800 --> 13:21.120 wir halt mehr als zwei Knoten in dem Fall. 13:22.100 --> 13:26.920 So, das zu diesen typischen Begriffen, die Sie eigentlich aus den 13:26.920 --> 13:28.160 anderen Vorlesungen kennen. 13:28.600 --> 13:30.320 Wenn ich zu schnell mache, müssen Sie mich stoppen. 13:31.340 --> 13:33.560 Ich gehe hier ein bisschen schnell durch, durch diese Teile. 13:33.560 --> 13:38.020 Wir wollen dann jetzt bestimmte typische Probleme anschauen. 13:38.640 --> 13:42.320 Und da gibt es zunächst mal den Begriff der Erreichbarkeit. 13:42.440 --> 13:45.480 Also ich will feststellen, welche Knoten kann ich eigentlich von einem 13:45.480 --> 13:46.620 anderen aus erreichen. 13:47.660 --> 13:52.140 Sie erinnern sich bei, wenn Sie alle Grundlagen der Informatik 2 13:52.140 --> 13:57.860 gehört, da haben wir die Automaten minimiert und haben dort die 13:57.860 --> 14:00.760 erstmal vereinfacht, indem wir alle nicht erreichbaren Zustände 14:00.760 --> 14:01.720 rausgeschmissen haben. 14:01.720 --> 14:04.500 Alle, die nicht vom Anfangszustand aus erreichbar waren. 14:05.460 --> 14:07.480 Und das heißt, da ist man an sowas interessiert. 14:08.900 --> 14:10.620 Erreichbarkeit ist etwas ganz Wichtiges. 14:11.700 --> 14:16.560 Und das heißt, wenn ich hier irgendwelche zwei Knoten habe, möchte ich 14:16.560 --> 14:22.880 wissen, gibt es irgendeinen Pfad, der mir diese Knoten hier, diese 14:22.880 --> 14:25.540 Source und Target miteinander verbindet. 14:27.980 --> 14:31.940 Das habe ich natürlich zunächst mal in der Adjacenzmatrix so nicht 14:31.940 --> 14:35.240 drin stehen, da stehen nur die einzelnen Kanten drin, um daraus die 14:35.240 --> 14:36.620 Erreichbarkeitsmatrix zu machen. 14:36.780 --> 14:41.860 Möchte ich eine Matrix haben, die hier mit Tg bezeichnet ist, das 14:41.860 --> 14:47.140 heißt, das Tij soll 1 sein, wenn es einen Weg gibt von I nach J. 14:47.440 --> 14:48.900 Also irgendeine Folge von Kanten. 14:49.760 --> 14:54.720 Und das T, oder man nennt die, T hat ja mit Erreichbarkeit nichts zu 14:54.720 --> 14:54.960 tun. 14:55.420 --> 14:58.260 Aber T hat was mit transitiver Hülle zu tun. 14:58.900 --> 15:03.020 Und Transitivität einer Relation kennen Sie alle, wenn ich zwei 15:03.020 --> 15:10.300 Elemente habe, I und K, die in Relation stehen, und außerdem K und J. 15:10.840 --> 15:16.520 Wenn daraus folgt, dass I und J auch in Relation stehen, dann ist das 15:16.520 --> 15:17.720 eine transitive Relation. 15:17.720 --> 15:22.140 Und bei einer Erreichbarkeit, wenn ich also eine Matrix aufschreibe, 15:22.180 --> 15:25.860 die eine Erreichbarkeitsmatrix ist, dann habe ich eben genau diese 15:25.860 --> 15:31.140 Eigenschaft, dass ich sage, also alle Knoten, die irgendwie 15:31.140 --> 15:34.180 miteinander über eine Folge von Kanten verbunden sind, sind dann auch 15:34.180 --> 15:39.740 bei der transitiven Hülle direkt über einen solchen Eintrag hier 15:39.740 --> 15:40.460 miteinander verbunden. 15:40.600 --> 15:42.980 Also das ist praktisch nur die Erreichbarkeit. 15:42.980 --> 15:48.560 Wenn K von I erreichbar ist und J von K, ist natürlich J auch von I 15:48.560 --> 15:49.040 erreichbar. 15:50.080 --> 15:53.760 So, man kann das jetzt definieren, dass man sukzessive sagt, ich 15:53.760 --> 16:02.480 betrachte diese auf dem Weg bis zu dem Tg, ich betrachte hier eine 16:02.480 --> 16:09.620 Menge Tg hoch R, so, dass das Tg hoch R gerade gleich 1 ist, genau 16:09.620 --> 16:16.480 dann, wenn es einen Weg der Länge maximal R gibt von I nach J, das Tg 16:16.480 --> 16:22.480 hoch 1 wäre dann gerade die Adjacenzmatrix, und das ist also das, was 16:22.480 --> 16:28.760 hier steht, das ist das Aij, Tij hoch 1 wäre gerade das Aij, und das 16:28.760 --> 16:36.420 Tij2 wäre dann Aij, also das heißt, IJ sind über einen Weg der Länge 2 16:36.420 --> 16:41.560 verbunden, entweder wenn I und J direkt oder maximal, kleiner gleich R 16:41.560 --> 16:46.580 steht hier, wenn I und J direkt verbunden sind oder es gibt einen 16:46.580 --> 16:52.180 Knoten, so dass I mit K verbunden ist und K mit J verbunden ist. 16:52.460 --> 16:53.920 Das wäre ein Weg der Länge 2. 16:54.860 --> 16:58.180 Das andere wäre ein Weg der Länge 1 oder Weg der Länge 2, das wäre 16:58.180 --> 16:58.940 Tij2. 17:00.060 --> 17:05.680 Tijn würde entsprechend bedeuten, entweder sind I und J direkt 17:05.680 --> 17:15.180 verbunden oder es gibt einen Knoten, so dass der Knoten I direkt mit K 17:15.180 --> 17:22.580 verbunden ist und der Knoten K über einen Weg der Länge N maximal mit 17:22.580 --> 17:23.260 dem Knoten J. 17:23.260 --> 17:29.500 Das heißt, wenn ich hier meinen Knoten I betrachte und den Knoten J, I 17:29.500 --> 17:34.880 und J, dann sage ich, entweder sind die direkt verbunden, das ist das 17:34.880 --> 17:43.380 Aij, oder es gibt einen Knoten K, mit dem das I direkt verbunden ist 17:44.960 --> 17:51.660 und danach gibt es einen Pfad der Länge maximal N-1, so dass das K mit 17:51.660 --> 17:52.760 dem J verbunden ist. 17:52.760 --> 17:59.280 Dann ist der Knoten I über einen Pfad maximal der Länge N mit J 17:59.280 --> 17:59.780 verbunden. 18:00.420 --> 18:01.360 Das kennen Sie alles. 18:02.240 --> 18:06.720 Wenn Sie eine solche Formel sehen, dann müsste Sie das an etwas 18:06.720 --> 18:07.380 erinnern. 18:09.140 --> 18:13.140 Wir hatten ähnliche Gleichungen schon mal gehabt, nämlich bei der 18:13.140 --> 18:14.320 Matrixmultiplikation. 18:15.240 --> 18:16.840 Die sahen ganz ähnlich aus. 18:16.840 --> 18:17.420 Ja? 18:20.480 --> 18:21.340 So ist es. 18:21.980 --> 18:23.180 Ja, genau. 18:24.440 --> 18:25.840 Das ist einfach eine Boole'sche Matrixmultiplikation. 18:26.620 --> 18:27.180 Wer ist das nicht? 18:27.400 --> 18:28.840 Also ganz einfacher Algorithmus. 18:29.380 --> 18:30.520 Steht ja auch direkt unten drunter. 18:30.960 --> 18:32.060 Haben Sie auch alle vorliegen gehabt. 18:32.240 --> 18:34.500 Das ist eine einfache Operation. 18:36.100 --> 18:37.020 Und Aufwand? 18:37.200 --> 18:39.860 Naja, ich mache einfach Boole'sche Matrixmultiplikation. 18:39.960 --> 18:41.640 Boole'sche Matrixmultiplikation. 18:41.740 --> 18:42.860 Wissen wir, wie der Aufwand ist. 18:42.860 --> 18:43.900 Naives Verfahren. 18:44.240 --> 18:45.140 N hoch 3. 18:46.020 --> 18:48.040 Das wäre aber ein ziemlicher Aufwand. 18:48.500 --> 18:50.060 Dann hätten wir Aufwand N hoch 4. 18:50.940 --> 18:52.440 Nur das sukzessive Machen. 18:54.020 --> 18:58.240 Wenn man es ein bisschen effizienter macht, könnte man auf N hoch 3 18:58.240 --> 18:59.060 log N kommen. 18:59.600 --> 19:04.660 Indem man sagt, naja, ich möchte ja gerne, eigentlich muss ich ja nur 19:04.660 --> 19:06.400 das Tg hoch N berechnen. 19:07.780 --> 19:11.820 Und wenn ich etwas hoch N berechnen möchte, brauche ich ja nur, das 19:11.820 --> 19:17.740 ist ja das übliche Problem, irgendein X hoch N, Endpotenz einer Zahl. 19:17.820 --> 19:20.640 Wissen wir, geht in logarithmischer Zeit durch sukzessives Quadrieren. 19:21.160 --> 19:22.320 Das ist ja eigentlich kein Problem. 19:23.040 --> 19:25.140 Also das wäre sofort N hoch 3 log N. 19:25.820 --> 19:29.260 Aber auch das ist noch nicht wirklich effizient. 19:30.220 --> 19:34.020 Und effizient wird es, wenn wir zum Beispiel den Warschall-Algorithmus 19:34.020 --> 19:34.340 nehmen. 19:34.340 --> 19:37.360 Kennt jemand den Begriff Warschall-Algorithmus unter dem Namen? 19:38.260 --> 19:38.740 Nicht? 19:39.060 --> 19:45.380 Sie kennen vielleicht den Begriff Trippel-Algorithmus. 19:46.340 --> 19:47.480 Kennen Sie auch nicht? 19:48.740 --> 19:49.660 Sie kennen den. 19:50.020 --> 19:53.840 Also das ist im Prinzip der Trippel-Algorithmus, heißt aber nach dem 19:53.840 --> 19:55.540 Autor Warschall-Algorithmus. 19:56.220 --> 19:57.740 Was habe ich jetzt Ihnen hier hingeschrieben? 19:57.820 --> 19:59.000 Das ist doch das Übliche, was wir kennen. 19:59.100 --> 20:00.600 Das ist doch die Marktesmultiplikation. 20:01.040 --> 20:01.720 Sieht man doch sofort. 20:01.720 --> 20:03.100 Dreifach geschachtelte Schleife. 20:03.540 --> 20:08.000 Hier haben wir in der Mitte oder im Kern haben wir hier unten diesen 20:08.000 --> 20:08.500 Rumpf. 20:08.560 --> 20:09.800 Das ist genau die Marktesmultiplikation. 20:09.900 --> 20:10.720 Was ist daran besonders? 20:11.200 --> 20:13.820 Wenn man genau hinguckt, ist es eben nicht die Marktesmultiplikation, 20:14.700 --> 20:19.320 sondern hier haben Sie etwas, das ist anders aufgebaut. 20:20.520 --> 20:24.460 Bei der Marktesmultiplikation hatten wir eine Marktesmultiplikation. 20:24.860 --> 20:28.960 Da ging die Schleife über I und J und innen drin hatten wir K. 20:29.900 --> 20:38.040 Und hier steht jetzt, für K gleich 1 bis N, iteriere ich über alle I 20:38.040 --> 20:47.200 und J und habe dann innen drin diesen Term hier auszuwerten. 20:48.320 --> 20:51.760 Und die Behauptung ist, mit diesem Algorithmus bin ich schon fertig, 20:51.960 --> 20:53.120 wenn ich ihn einmal ausführe. 20:54.340 --> 20:56.080 Zunächst mal sieht das so aus wie eine Marktesmultiplikation. 20:56.080 --> 21:01.080 Wir sagten gerade, wir müssen aber A hoch N berechnen. 21:02.820 --> 21:04.880 Wieso reicht da ein solches Verfahren aus? 21:04.980 --> 21:09.140 Es ist zunächst mal nicht klar, dass das tatsächlich reicht. 21:09.560 --> 21:11.500 Und das liegt eben hier an diesem K. 21:11.940 --> 21:12.920 Was macht man hier? 21:13.340 --> 21:14.440 Nochmal aufgemalt. 21:14.880 --> 21:16.920 Ich weiß nicht, habe ich hier nicht aufgemalt. 21:18.100 --> 21:20.440 Also, das ist genau das, was hier unten steht. 21:21.400 --> 21:23.460 Ich glaube, ich habe es nicht aufgemalt. 21:24.260 --> 21:25.380 Dann male ich das hier nochmal auf. 21:25.380 --> 21:28.460 Also, ich habe hier meinen... 21:28.460 --> 21:29.680 Wo kommt da noch irgendwas? 21:30.280 --> 21:31.400 Da ist noch irgendein Bild. 21:31.800 --> 21:32.700 Das ist die Verbesserung. 21:33.420 --> 21:35.700 Also, ich habe Platz, um das aufzumalen, habe ich hier unten. 21:36.800 --> 21:39.860 Wir haben unseren Knoten I, wir haben den Knoten J. 21:41.540 --> 21:45.760 Und die beiden werden angeguckt. 21:46.000 --> 21:51.100 Es ist also entweder hier bereits, wenn ich mir diese Anweisung 21:51.100 --> 21:57.280 anschaue, entweder ist dieses hier bereits bekannt, dass I und J 21:57.280 --> 21:58.380 verbunden sind. 21:59.400 --> 22:04.180 Und zwar kann das nur bekannt sein dadurch, dass ich etwas gemacht 22:04.180 --> 22:11.940 habe für Werte kleiner als K, für 1 bis K-1 in diesem Fall. 22:12.380 --> 22:13.700 Jetzt gucke ich mir den Fall K an. 22:14.640 --> 22:20.660 Das heißt, was hier bei diesen Betrachten von dem I und J an Ks 22:20.660 --> 22:25.680 aufgetreten sein kann, ist irgendetwas, das können also Knoten sein 22:25.680 --> 22:31.000 hier, aus der Menge K-1. 22:31.320 --> 22:33.840 1 bis K-1 können aufgetreten sein. 22:34.800 --> 22:38.160 Der Knoten K kann dort unten auf diesem Weg nicht aufgetaucht sein, 22:38.400 --> 22:44.080 weil ich in den vorherigen Iterationen immer nur Werte kleiner als K 22:44.080 --> 22:45.040 betrachtet habe. 22:45.700 --> 22:46.220 So. 22:47.040 --> 22:52.700 Es ist also I und J verbunden über einen Weg der Länge K-1. 22:53.060 --> 22:54.560 Das ist also das, was hier steht. 22:55.940 --> 22:59.180 Hier steht es über eine Kante verbunden, aber gemeint ist ja 22:59.180 --> 23:04.680 eigentlich, dass die aufgrund der Information, die ich aktuell habe in 23:04.680 --> 23:08.760 dieser Iteration, und diese Information bezieht sich darauf, dass ich 23:08.760 --> 23:13.460 schon die ganzen vorherigen Iterationen durchgeführt habe, also 23:13.460 --> 23:19.520 verbunden über den Weg der Kante, in dem Knoten 1 bis K-1 auftauchen. 23:20.160 --> 23:28.600 Oder I ist verbunden mit einem Knoten K, mit dem Knoten K, über einen 23:28.600 --> 23:35.400 Pfad, auf dem auch wieder nur Kanten auftauchen aus der Menge 1 bis K 23:35.400 --> 23:35.960 -1. 23:35.960 --> 23:44.380 Und K ist mit J verbunden, auch wieder nur mit einem Pfad, in dem nur 23:44.380 --> 23:47.100 Knoten auftauchen von 1 bis K-1. 23:48.640 --> 23:49.360 So. 23:51.300 --> 23:56.540 Wenn Sie sich dieses Bild anschauen, dann ist schon klar, dass dieser 23:56.540 --> 24:02.280 Algorithmus eigentlich korrekt sein muss, weil wir nämlich, wenn wir 24:02.280 --> 24:03.780 hier durchlaufen bis N, 24:07.400 --> 24:14.740 dann haben wir für K gleich N, haben wir dann überprüft, ob I und J 24:14.740 --> 24:18.700 verbunden sind über einen Weg, bei dem irgendwelche anderen Knoten 24:18.700 --> 24:25.000 vorkommen aus der Menge 1 bis N, oder ich muss über den Knoten N 24:25.000 --> 24:30.060 laufen und die Wege dahin zu dem Knoten N dürfen irgendwelche anderen 24:30.060 --> 24:33.000 Knoten aus der Menge 1 bis N-1 enthalten. 24:33.760 --> 24:37.420 Das heißt, es muss dann der Knoten N dort auch mit auftauchen. 24:38.980 --> 24:40.620 Das ist das, was man sich hier anschaut. 24:41.880 --> 24:46.060 Und wenn ich die letzte Iteration gemacht habe, habe ich 24:46.060 --> 24:51.520 offensichtlich alle Möglichkeiten betrachtet, weil ich dann für je 24:51.520 --> 24:58.340 zwei Knoten genau das untersucht habe, ob es einen Pfad gibt von I 24:58.340 --> 25:03.880 nach J, der über irgendwelche anderen Knoten in dem Graphen läuft. 25:04.720 --> 25:07.860 Irgendwelche anderen heißt Knoten aus der Menge 1 bis N. 25:09.780 --> 25:13.260 Man sieht sofort, wie man das über Induktion beweisen kann, dass 25:13.260 --> 25:15.640 dieser Algorithmus tatsächlich korrekt ist. 25:17.720 --> 25:21.820 Und er läuft halt, wie man hier sieht, dreifach geschaltete Schleife 25:21.820 --> 25:24.540 läuft trivialerweise in Zeit N hoch 3. 25:26.720 --> 25:33.380 Und damit haben wir also hier eine Alternative zu dem, was ich vorher 25:33.380 --> 25:38.600 sagte, N hoch 3 log N ist auch nicht schlecht, aber das hier ist ja 25:38.600 --> 25:39.580 selbstverständlich besser. 25:40.540 --> 25:42.800 Und jetzt kann ich das noch ein bisschen verbessern. 25:43.510 --> 25:52.880 Ich kann also hier zum Beispiel sagen, naja, wenn I mit... 25:55.570 --> 26:02.580 Also ich kann erst mal gucken, ob I mit K verbunden ist, ob ich das 26:02.580 --> 26:03.440 bereits drin habe. 26:03.960 --> 26:09.600 Nur dann macht es Sinn, überhaupt die weiteren Schritte zu betrachten. 26:10.560 --> 26:18.000 Wenn das I gar nicht mit K verbunden ist, über einen Weg, bei dem 26:18.000 --> 26:22.080 Knoten aus der Menge 1 bis K auftauchen, dann brauche ich das hier gar 26:22.080 --> 26:22.980 nicht weiter zu betrachten. 26:24.160 --> 26:30.580 Und dann schaue ich mir an, für alle möglichen Zielknoten, nur wenn 26:30.580 --> 26:37.620 also I nicht mit J verbunden ist, dann wäre ich ja schon fertig, dann 26:37.620 --> 26:42.900 wäre das ja schon verbunden, dann schaue ich mir an, ob K mit J 26:42.900 --> 26:50.020 verbunden ist und dann setze ich natürlich A, I, J auf. 26:51.620 --> 26:59.080 Also wenn A, I, J nicht gilt, dann muss ich nur überprüfen, ob 26:59.080 --> 27:03.540 eventuell eine Verbindung von I nach J über diesen Knoten K existiert 27:03.540 --> 27:06.500 und das ist dann der Wert, auf den ich das A, I, J setze. 27:08.140 --> 27:12.300 Also eigentlich könnte ich das sogar noch mehr vereinfachen, da ich 27:12.300 --> 27:18.120 hier oben ja bereits getestet habe, ob das A, I, K gilt, könnte ich 27:18.120 --> 27:23.620 hier auch hinschreiben, A, I, J gleich A, K, J. 27:25.060 --> 27:30.420 Ich brauche hier gar nicht hinzuschreiben A, I, K und A, K, J, sondern 27:30.420 --> 27:35.460 es reicht hinzuschreiben A, I, J gleich A, K, J, weil ich ja das hier 27:35.460 --> 27:36.800 oben bereits abgetestet habe. 27:38.600 --> 27:45.240 Also das ist eine sehr einfache, eine kleine Variation, die ändert an 27:45.240 --> 27:51.120 der Laufzeit insgesamt nichts, also nichts asymptotisch, aber für den 27:51.120 --> 27:53.380 praktischen Fall ist das ein bisschen eine Verbesserung. 27:54.820 --> 28:01.620 Das ist der klassische Algorithmus, um Erreichbarkeit in Graphen 28:01.620 --> 28:03.800 festzulegen, um die transitive Hülle zu bestimmen. 28:05.660 --> 28:09.100 Und Sie sehen, was es ausmacht, wenn man einfach hier die Reihenfolge 28:09.100 --> 28:11.920 dieser Iterationen verändert. 28:12.700 --> 28:15.680 Das hat drastische Auswirkungen für dieses Verfahren, wenn Sie hier 28:15.680 --> 28:20.980 eben nur für I und J laufen würden und in der Mitte und unten dieses K 28:20.980 --> 28:24.700 überprüfen müssten, dann müssten Sie eben das immer wieder machen, 28:24.780 --> 28:28.840 weil Sie immer nur prüfen würden, würden Sie nur für alle I und J 28:28.840 --> 28:32.080 prüfen, ob es einen Pfad gibt, der über den Knoten 1 geht usw. 28:32.760 --> 28:35.500 Das würde Ihnen insgesamt, da hätten Sie gerade nur die Wege der Länge 28:35.500 --> 28:38.400 1, dann die Wege der Länge 2, Länge 3 usw. 28:38.960 --> 28:41.780 Hier haben Sie beliebige Längen automatisch mit drin. 28:43.000 --> 28:50.500 Das ist ein genialer Algorithmus, ist, wie gesagt, bekannt, wird im 28:50.500 --> 28:53.720 Operations Research manchmal Triple Algorithmus genannt, nach dem 28:53.720 --> 28:56.220 Autor heißt er aber Warshall's Algorithmus. 28:57.340 --> 29:00.220 Im Mittel haben Sie bei dieser Verbesserung den Aufwand reduziert, im 29:00.220 --> 29:04.440 schlechtesten Fall, wie gesagt, immer noch N hoch 3, aber ist auf 29:04.440 --> 29:06.460 jeden Fall ein schönes Verfahren. 29:07.460 --> 29:10.980 Und das, was mich jetzt interessiert, ist Ihnen zu zeigen, wie man das 29:10.980 --> 29:12.260 Ganze parallelisieren kann. 29:14.000 --> 29:17.400 Wir wissen, wie wir parallel Matrixmultiplikationen machen können. 29:18.140 --> 29:20.260 Aber hier haben wir jetzt keine Matrixmultiplikation. 29:21.840 --> 29:25.700 Und jetzt schauen wir uns mal an, wenn ich den Warshall-Algorithmus 29:25.700 --> 29:30.360 auf einem zweidimensionalen Gitter ausführen möchte. 29:30.400 --> 29:33.780 Und ich habe in dem zweidimensionalen Gitter meine 29:33.780 --> 29:37.940 Erreichbarkeitswerte drin, die aij. 29:38.840 --> 29:43.800 Also ein n mal n Gitter und in jedem Element steht gerade so ein aij 29:43.800 --> 29:44.140 drin. 29:44.980 --> 29:49.040 Und jetzt möchte ich gerne diese Operation ausführen. 29:50.940 --> 29:53.580 Ich möchte gerne diese Operation ausführen. 29:54.060 --> 29:58.880 Das ist der Rumpf, den ich dort im Prinzip durchführen muss. 30:00.420 --> 30:03.400 Und Sie erinnern sich, wir hatten das bei der Matrixmultiplikation 30:03.400 --> 30:04.200 ganz einfach. 30:04.300 --> 30:07.480 Da haben wir einfach so die Werte so durchlaufen lassen von oben und 30:07.480 --> 30:12.960 unten oder von links und von oben und hatten die dann direkt 30:12.960 --> 30:13.760 miteinander verbunden. 30:13.760 --> 30:16.080 Es trafen sich immer die richtigen Elemente. 30:17.140 --> 30:18.440 Jetzt schauen wir uns das mal an. 30:19.020 --> 30:23.940 Für k gleich 1 bis n müssen wir dafür sorgen, wir wollen also zum 30:23.940 --> 30:27.860 Beispiel diesen Wert hier ausrechnen, a33. 30:29.240 --> 30:46.340 Dann müssen wir berechnen a33 oder a31 und a13. 30:46.800 --> 30:54.280 a31 ist der Wert aus diesem, der Wert aus dem Prozessor. 30:55.300 --> 31:03.480 Dann brauchen wir als nächstes, für k gleich 2 brauchen wir den Wert 31:03.480 --> 31:04.620 und den Wert. 31:05.900 --> 31:10.140 Dann brauchen wir, natürlich das ist trivial, das ist irrelevant, und 31:10.140 --> 31:11.600 dann brauchen wir diese beiden. 31:13.540 --> 31:18.580 Das heißt, wir müssen hier Elemente zusammenführen, die relativ weit 31:18.580 --> 31:19.600 auseinander sind. 31:21.160 --> 31:24.500 Die Distanzen der Elemente, die wir hier in einem Knoten miteinander 31:24.500 --> 31:26.480 verbinden müssen, die sind alle unterschiedlich. 31:28.620 --> 31:32.900 Und das ist nicht sofort ersichtlich, wie man das eigentlich gut 31:32.900 --> 31:33.820 hinbekommen kann. 31:33.920 --> 31:37.740 Das funktioniert nicht so, wie wir das vorher gemacht haben, mit dem 31:37.740 --> 31:43.040 einfach Durchschieben der Matrizen, sodass die sich jeweils treffen. 31:44.080 --> 31:45.980 Das läuft hier nicht auf diese Art und Weise. 31:47.400 --> 31:49.640 Also, wie kann man das hinbekommen? 31:50.080 --> 31:57.440 Und die Idee ist folgende, im ersten Schritt bewegen wir einfach die 31:57.440 --> 32:00.180 erste Zeile von oben nach unten. 32:01.040 --> 32:05.140 Also diese Zeile hier schieben wir hier einmal ganz durch. 32:05.540 --> 32:12.700 Und bei diesem Durchschieben, das ist ein zyklisches Ringschieben, das 32:12.700 --> 32:17.380 heißt anschließend ist die Zeile, also erst haben wir hier, also diese 32:17.380 --> 32:20.460 geht praktisch nach oben, die geht jeweils eins nach oben. 32:22.380 --> 32:28.340 Und diese erste Zeile hier, die wandert ganz nach unten. 32:29.260 --> 32:31.940 Also die wandert da ganz nach unten. 32:32.240 --> 32:38.120 Aber eben nicht direkt, sondern sie wandert sukzessive durch diese 32:38.120 --> 32:41.320 einzelnen Zeilen hindurch. 32:41.320 --> 32:47.060 Und bei diesem Durchwandern lasse ich jeweils das Element dort stehen. 32:47.200 --> 32:51.020 Also im Prinzip mache ich das so, dass ich das A11 bis A14 nach unten 32:51.020 --> 32:56.920 schiebe, in jedem Knoten dieser Spalte das Element aufbewahre und 32:56.920 --> 33:00.400 anschließend noch alles eins nach oben schiebe. 33:00.400 --> 33:04.240 Das heißt anschließend habe ich hier drin, wenn ich mir das hier 33:04.240 --> 33:12.500 aufmale, hätte ich hier drin stehen, da oben A21 und A11, wenn ich mir 33:12.500 --> 33:22.320 die erste Zeile anschaue, da unten drunter hätte ich dann das A31 und 33:22.320 --> 33:32.840 A11, ich hätte das A41 und A11 und unten hätte ich A11 und A11. 33:34.200 --> 33:37.040 Und entsprechend in den anderen Zeilen, also hier hätte ich dann 33:37.040 --> 33:45.840 entsprechend A23 und A13. 34:10.480 --> 34:14.200 Ja, ja, und A13. 34:16.720 --> 34:19.000 Ich überlege gerade, was habe ich jetzt hier gemacht? 34:27.420 --> 34:28.540 Okay, das muss nun stimmen. 34:28.740 --> 34:41.010 Dann hätte ich hier A33 und A13, 34:44.710 --> 34:47.110 die muss ich doch gar nicht verbinden. 34:47.110 --> 34:48.390 Was habe ich denn jetzt hier an? 34:50.230 --> 34:53.450 Das stimmt jetzt nicht, ist egal, ich werde das schon herausfinden, 34:53.550 --> 34:54.530 was ich hier gemacht habe. 34:55.370 --> 35:05.450 A43 und A13 und hier hätte ich A13 und A13. 35:06.390 --> 35:16.610 So, die lasse ich alle so rüberlaufen, durch Ring schieben und im 35:16.610 --> 35:21.990 zweiten Schritt bewege ich die erste Spalte von links nach rechts und 35:21.990 --> 35:26.030 speichere dabei die Werte in den durchlaufenden Prozessoren. 35:26.630 --> 35:34.290 Das heißt, diese erste Spalte, das wären diese A21, A31 bis A41, die 35:34.290 --> 35:45.150 schiebe ich jetzt nach rechts und speichere entsprechend die Werte in 35:45.150 --> 35:46.430 den durchlaufenden Prozessoren. 35:47.050 --> 35:54.110 Das heißt, dann hätte ich anschließend in dem Prozessor, wo vorher 35:54.110 --> 36:01.690 schon A23 und A13 abgelegt waren, hätte ich dann noch A21 drin stehen. 36:01.690 --> 36:09.650 Also da würde anschließend hier in diesem auch noch drinstehen das A21 36:09.650 --> 36:18.010 und hier würde noch das A31 drinstehen und da würde noch das A41 36:18.010 --> 36:20.830 drinstehen und da das A11. 36:21.630 --> 36:26.870 Jetzt hätte ich also die Elemente A21, A23 und A13 dort drinstehen. 36:26.870 --> 36:33.070 Mit diesen drei Elementen kann ich jetzt die Berechnung machen, A23 36:33.070 --> 36:40.250 ist gleich, A23 oder A21 und A13. 36:41.150 --> 36:43.110 Ich habe diese drei Elemente dort drinstehen. 36:45.430 --> 36:48.450 Ich habe also in jedem Prozessor, habe ich jetzt genau, ich habe also 36:48.450 --> 36:52.670 in diesem zum Beispiel, in dem Prozessor, der jetzt hier eins nach 36:52.670 --> 37:02.730 links geschoben ist, habe ich die Elemente A43, ich habe A41 und A13 37:02.730 --> 37:03.030 drin. 37:03.070 --> 37:06.870 Das heißt, ich kann in jedem Prozessor genau die Operation machen, die 37:06.870 --> 37:08.550 ich brauche für K gleich 1. 37:09.710 --> 37:14.750 Nach diesem Ringschieben der Zeile und der Spalte, habe ich jetzt in 37:14.750 --> 37:20.550 jedem Prozessor, in jeder Zelle genau die drei Elemente, die ich 37:20.550 --> 37:23.430 brauche, um diese Operation auszuführen. 37:24.550 --> 37:28.570 Und zwar habe ich die jetzt nicht, also vorher war dieses Element an 37:28.570 --> 37:35.010 der Stelle und das ist jetzt um eins nach oben verschoben worden und 37:35.010 --> 37:36.450 um eins nach links. 37:39.370 --> 37:43.170 So, das ist dieses Durchschieben der Zeile und durchschieben der 37:43.170 --> 37:43.630 Spalte. 37:44.450 --> 37:51.610 Und dann kann ich diese Operation ausführen und anschließend mache ich 37:51.610 --> 37:52.790 im Prinzip das Gleiche nochmal. 37:54.550 --> 37:59.290 Ich schiebe die oberste Zeile nach unten und schiebe die linkeste 37:59.290 --> 38:00.710 Spalte nach rechts. 38:03.590 --> 38:07.210 So, die oberste Spalte nach unten heißt, jetzt schiebe ich hier oben, 38:08.170 --> 38:16.850 ich habe jetzt zwar hier drin stehen, also dieses A21, jetzt wird 38:16.850 --> 38:21.190 dieses nach unten geschoben und dann habe ich im Prinzip überall die 38:21.190 --> 38:23.890 Möglichkeit, die Operation für K gleich 2 zu machen. 38:24.850 --> 38:31.510 Weil ja die zweite Zeile oben steht und die zweite Spalte links, wenn 38:31.510 --> 38:34.850 ich die nach unten und nach rechts schiebe, habe ich anschließend die 38:34.850 --> 38:37.590 Möglichkeit, in allen Prozessoren die Operation zu machen für K gleich 38:37.590 --> 38:37.910 2. 38:38.850 --> 38:43.450 Und anschließend mache ich das Ganze nochmal und habe dann die 38:43.450 --> 38:47.530 Möglichkeit, das Ganze auszuführen für K gleich 3 und so weiter. 38:48.690 --> 38:54.310 Das ist auf der nächsten, also hier ist es jetzt dargestellt, ich 38:54.310 --> 39:01.210 wische das einfach weg, in der Aufzeichnung ist es ja zu sehen und 39:01.210 --> 39:05.390 damit haben wir hier nochmal das Allgemein dargestellt. 39:06.830 --> 39:09.770 Nach, das ist genau das, was ich hier aufgeschrieben habe, hatte ich 39:09.770 --> 39:15.450 vor dort hingemalt, nach diesem Teile nach unten schieben und Spalte 39:15.450 --> 39:20.770 nach rechts schieben, habe ich in Prozessor I minus 1, J minus 1, das 39:20.770 --> 39:23.770 A, I, J stehen, das A, I, 1 und das A, 1, J. 39:24.750 --> 39:27.250 Und die kann ich jetzt verbinden, das war das für K gleich 1. 39:28.010 --> 39:31.730 Und wenn ich das jetzt für das Normal mache, habe ich das für K gleich 39:31.730 --> 39:33.630 2, für K gleich 3 und so weiter. 39:34.370 --> 39:36.330 Ich kann dort jeweils diese Operation machen. 39:38.190 --> 39:39.670 Ich muss das N mal durchführen. 39:40.870 --> 39:44.630 Und damit hätte ich genau den Wortschallalgorithmus simuliert. 39:44.630 --> 39:48.270 Ich kann genau die Operation des Wortschallalgorithmus, die hier 39:48.270 --> 39:52.290 dargestellt sind, das war die Operation, das mache ich jetzt für K 39:52.290 --> 39:56.670 gleich 1 bis N, in allen Prozessoren I, J diese Operation. 39:57.370 --> 39:58.890 Der Aufwand ist natürlich groß. 39:59.690 --> 40:02.870 Ich muss die Zeile durchschieben, das ist Aufwand, das ist lineare 40:02.870 --> 40:04.490 Aufwand, parallel. 40:05.190 --> 40:07.770 Ich muss die Spalte rüberschieben, nochmal lineare Aufwand. 40:08.390 --> 40:11.210 Dann muss ich einmal die Operation machen, das ist konstanter Aufwand. 40:11.210 --> 40:15.410 Und das Ganze muss ich N mal machen, dann hätte ich also quadratischen 40:15.410 --> 40:15.890 Aufwand. 40:17.150 --> 40:18.450 Und das stört mich. 40:19.650 --> 40:25.730 Hier ist das nochmal dargestellt, wie man das, was ich gerade auf der 40:25.730 --> 40:28.630 vorigen Folie dargestellt hatte, sieht man hier nochmal, wie die 40:28.630 --> 40:31.170 Elemente dort zusammengewürfelt sind. 40:31.690 --> 40:35.770 Also das, was ich vorher sagte, das ist jetzt der Prozessor, der halt 40:35.770 --> 40:37.310 das Element A22 enthält. 40:37.430 --> 40:40.150 Also der Prozessor I1 enthält das Element A22. 40:40.150 --> 40:46.710 Der Prozessor I2 enthält das Element 23 und so weiter. 40:47.230 --> 40:49.910 Und das Element 13, das ist halt hier unten hingewandert. 40:50.790 --> 40:56.190 Und in schwarz ist jeweils das Matrix-Element angegeben, das mich 40:56.190 --> 40:56.810 interessiert. 40:57.150 --> 41:01.990 Und in rot und in blau sind angegeben die Elemente, die ich durch das 41:01.990 --> 41:05.030 Zeilenverschieben und Spaltenverschieben hier reinbekommen habe. 41:06.310 --> 41:08.150 Das ist also die ganze Idee. 41:10.110 --> 41:12.990 Und der Aufwand ist halt relativ hoch. 41:13.410 --> 41:19.770 Das ist hier genau nochmal das dargestellt, hier visualisiert, was für 41:19.770 --> 41:23.410 Elemente dort in die einzelnen Zellen reinkommen. 41:25.050 --> 41:28.690 Und jetzt habe ich also quadratische Zeit. 41:30.170 --> 41:31.430 Und jetzt mache ich das Ganze anders. 41:32.770 --> 41:41.550 Wenn ich das erste Element hier nach unten schiebe und das dann noch 41:41.550 --> 41:47.450 weiter schiebe und noch weiter, dann könnte ich ja eigentlich 41:47.450 --> 41:54.830 gleichzeitig das Element darüber schieben. 41:54.830 --> 41:58.690 Also diese Operation, ich habe jetzt hier nach unten geschoben. 41:58.830 --> 42:02.130 Ich hole natürlich auch ein Element von unten nach oben, das Element 42:02.130 --> 42:03.190 aus der zweiten Zeile. 42:03.870 --> 42:09.290 Aber diese Operation, das war eine Operation auf diesen, im Prinzip 42:09.290 --> 42:11.470 muss ich mir diese drei Elemente angucken. 42:12.070 --> 42:21.130 Hier drin möchte ich gerne ein Element von dort haben und ein Element 42:21.130 --> 42:21.610 von dort. 42:25.550 --> 42:29.550 Und das kann ich lokal erledigen. 42:29.630 --> 42:33.370 Das ist im Prinzip eine Operation, die bezieht sich nur hier oben auf 42:33.370 --> 42:34.490 einen bestimmten Bereich. 42:34.650 --> 42:37.210 Ihr habt gesehen, das kommt nach oben und nach links. 42:38.270 --> 42:40.330 Also eigentlich muss ich dieses Element hier. 42:40.870 --> 42:45.090 Dieses Element muss nach oben geschoben werden und dahin geschoben 42:45.090 --> 42:45.410 werden. 42:45.410 --> 42:54.530 Das kann ich aber durch einige Operationen machen. 42:54.690 --> 42:57.870 Ich kann das im Prinzip so in Diagonalen laufen lassen. 43:00.030 --> 43:04.010 Und wenn ich die hier verschoben habe, dann bin ich eigentlich mit 43:04.010 --> 43:04.870 diesem Element fertig. 43:04.970 --> 43:12.690 Dann habe ich dort meine drei Elemente A2-2, A2-1 und A1-2 drin 43:12.690 --> 43:12.990 stehen. 43:13.870 --> 43:16.630 Und entsprechend kann ich das noch weiter durchlaufen lassen. 43:17.790 --> 43:20.890 Und sobald ich damit fertig bin, kann ich eigentlich hier drin die 43:20.890 --> 43:24.950 Operation ausführen, das Warschallalgorithmus, und kann anschließend 43:24.950 --> 43:27.530 anfangen, die nächste Iteration zu machen. 43:28.010 --> 43:31.630 Das heißt, ich brauche hier eine bestimmte Anzahl von Operationen, 43:31.730 --> 43:37.630 also hier die Breite dieser Berechnungswellen, das ist eine Anzahl von 43:37.630 --> 43:42.950 Operationen C, die ich brauche, um die Elemente aus den benachbarten 43:42.950 --> 43:48.610 Zellen zu verschieben und die Warschall-Operationen zu machen. 43:51.010 --> 43:55.230 Wenn ich diese C-Operation gemacht habe, dann kann ich die nächsten C 43:55.230 --> 44:00.510 -Operationen anfangen, von der zweiten Iteration für K gleich 2, dann 44:00.510 --> 44:02.670 für K gleich 3, für K gleich 4 und so weiter. 44:03.510 --> 44:06.950 Das heißt, ich habe nur eine konstante Anzahl von Operationen zu 44:06.950 --> 44:12.330 machen, in so einem diagonalen Band, und das läuft so sukzessive hier 44:12.330 --> 44:12.750 durch. 44:13.890 --> 44:20.450 Das heißt, ich brauche nur C mal N, nicht ganz, das N muss ja auch 44:20.450 --> 44:21.310 ganz durchlaufen. 44:22.770 --> 44:26.130 Also C mal N, um das hier oben hinlaufen zu lassen, und dann nochmal 44:26.130 --> 44:37.810 das Ganze durch, also C mal N plus entsprechend hier ganz durchlaufen. 44:42.220 --> 44:46.700 Und damit habe ich aber insgesamt linearen Aufwand. 44:47.820 --> 44:50.120 Ich habe nicht quadratischen Aufwand. 44:54.880 --> 44:57.920 Und jede Berechnungswelle besteht aus einer konstanten Zahl von 44:57.920 --> 44:59.160 Diagonalen insgesamt. 44:59.720 --> 45:03.380 Um hier ganz durchzulaufen von diesem Schritt bis zu dem Schritt, wo 45:03.380 --> 45:10.180 ich am Ende dann hier unten die Ende-Operation mache, habe ich 45:10.180 --> 45:12.060 insgesamt einen Aufwand, der linear ist. 45:13.760 --> 45:18.380 Und damit kann ich das Ganze auch noch mit Single Instruction Multiple 45:18.380 --> 45:19.060 Data machen. 45:20.920 --> 45:22.340 Also könnte ich so machen. 45:23.120 --> 45:24.660 Ich kann es auch noch anders machen. 45:24.780 --> 45:28.680 Ich kann das machen mit einem, das habe ich jetzt hier, genau, hier 45:28.680 --> 45:29.840 habe ich es nochmal dargestellt. 45:30.360 --> 45:33.100 Ich kann das, was ich mit Single Instruction Multiple Data machen 45:33.100 --> 45:37.680 möchte, wo ich in jedem Knoten die gleiche Operation mache, kann das 45:37.680 --> 45:41.340 noch verbessern um konstanten Faktor, indem ich sogenannte Wavefront 45:41.340 --> 45:42.140 Arrays betrachte. 45:42.280 --> 45:45.860 Im Prinzip sind das hier Wavefront Arrays, wo ich eine Operation oder 45:45.860 --> 45:51.240 eine komplexere Operation in so einer Wellenart sukzessive durch eine, 45:51.320 --> 45:55.280 also ich habe hier meine einzelnen Wellen und die schiebe ich durch so 45:55.280 --> 45:56.880 ein zweidimensionales Feld durch. 45:58.460 --> 46:02.920 Das ist eben ein Programmierprinzip, das ich Wavefront Array nenne. 46:03.780 --> 46:07.440 Es gibt eine andere Variante, die nennt sich Befehlsystolische Felder 46:07.440 --> 46:09.000 oder Instructional Systolic Arrays. 46:10.660 --> 46:14.100 Diese Wavefront Arrays, die sind von, 46:19.080 --> 46:21.140 es gibt ein schönes Buch von S.Y. 46:21.960 --> 46:29.660 Kung dazu und dieses hier Instructional Systolic Arrays, das sind im 46:29.660 --> 46:33.880 Wesentlichen Arbeiten von Lang und noch ein paar anderen Leuten, wo 46:33.880 --> 46:35.140 mein Name auch mit auftaucht. 46:35.140 --> 46:39.080 Also Instructional Systolic Arrays, die haben wir früher mal in Kiel 46:39.080 --> 46:39.540 entwickelt. 46:41.320 --> 46:43.340 Das ist also Instructional Systolic Arrays. 46:44.160 --> 46:45.400 Was sind Systolische Felder? 46:45.500 --> 46:49.200 Systolic Arrays, haben Sie schon mal gehört den Namen bei den Matrix 46:49.200 --> 46:50.200 -Multiplikationen? 46:50.520 --> 46:52.460 Da wurden Daten durch ein Feld geschoben. 46:53.240 --> 46:56.640 Bei den Instructional Systolic Arrays, da schieben wir im Prinzip 46:56.640 --> 47:03.900 Programme, das ist also hier ein Programm, durch ein Feld durch und 47:03.900 --> 47:09.880 wir schieben hier so eine Art Selektoren durch ein Feld durch. 47:10.000 --> 47:15.740 Also Informationen, die dann jeweils in einer Zelle kombiniert werden, 47:15.840 --> 47:18.840 da kommt dann ein Befehl und ein Selektor rein und ein Befehl wird 47:18.840 --> 47:20.960 ausgeführt, wenn der Selektor einen bestimmten Wert hat. 47:21.800 --> 47:25.880 Das ist in dem Sinne ein Befehlsystolisches Feld, weil wir dort 47:25.880 --> 47:27.280 Befehle durch ein Feld durchschieben. 47:27.280 --> 47:30.540 Das geht über den Umfang dieser Vorlesung hinaus, wenn ich Ihnen dazu 47:30.540 --> 47:34.480 noch zu viel erzähle, aber das ist auch ein interessantes Konzept 47:34.480 --> 47:37.540 gewesen für die Programmierung von zweidimensionalen Feldern. 47:39.280 --> 47:44.520 Also, das zu den parallelen Varianten, wenn ich die erste Idee 47:44.520 --> 47:51.700 verwende, muss ich in einer naiven Parallelisierung quadratische Zeit 47:51.700 --> 47:56.520 spendieren, immerhin ein Vorteil gegenüber Zeit n hoch 3, aber ich 47:56.520 --> 48:00.180 kann es eben verbessern, indem ich diese Wavefront-Array-Ideen 48:00.180 --> 48:06.080 verwende, bei denen ich sukzessive die Operationen in einer diagonalen 48:06.080 --> 48:10.160 Art und Weise mache und dadurch dann dafür sorge, dass diese 48:10.160 --> 48:14.200 Berechnungsregeln nacheinander parallel ausgeführt werden können und 48:14.200 --> 48:16.060 dann habe ich insgesamt einen linearen Aufwand. 48:16.060 --> 48:21.700 Dann habe ich mit n Quadratprozessoren einen linearen Aufwand, bin 48:21.700 --> 48:26.160 also von n hoch 3 runtergekommen auf lineare Zeit, das heißt, das ist 48:26.160 --> 48:29.340 eine bestmögliche Parallelisierung des Warschall-Algorithmus. 48:31.910 --> 48:36.110 Und damit sind wir durch diesen Warschall-Algorithmus schon durch. 48:37.490 --> 48:42.590 Und jetzt ist das Interessante, wenn man sich viele Probleme anguckt 48:42.590 --> 48:47.990 im Bereich der Graphen, dann stellt man fest, dass Sie sehr viele 48:47.990 --> 48:53.430 dieser Probleme lösen können durch algorithmische Ansätze, die 48:53.430 --> 48:58.730 entweder sind vom Typ Matrixmultiplikation, das heißt eine Iteration, 48:59.230 --> 49:05.490 bei der Sie i, j, k in dieser Reihenfolge geschachtelt haben, oder von 49:05.490 --> 49:11.550 Typ Warschall, k, i, j, die drei Iterationen, mit gewissen Varianten 49:11.550 --> 49:15.550 in dem, was in dem Rumpf steht, aber im Prinzip taucht diese Struktur 49:15.550 --> 49:16.330 immer wieder auf. 49:17.110 --> 49:19.450 Und das heißt, wenn man eine parallele Variante hat für diesen 49:19.450 --> 49:24.390 Warschall -Algorithmus, stellt sich gleich heraus, kriegt man sofort 49:24.390 --> 49:28.550 parallele Varianten, effiziente parallele Varianten für eine große 49:28.550 --> 49:32.050 Klasse von anderen Graph-Problemen. 49:32.930 --> 49:35.610 Und das ist das Interessante bei dem Warschall-Algorithmus und der 49:35.610 --> 49:38.810 parallelen Variante, dass das so ein Muster ist, das ich immer wieder 49:38.810 --> 49:43.950 verwenden kann, wobei ich nur das, was in dem Rumpf drinsteht, also 49:43.950 --> 49:47.890 dieses a, i, j oder a, i, k und a, k, j, das sieht dann ein bisschen 49:47.890 --> 49:48.570 anders aus. 49:48.850 --> 49:49.810 Sie sehen das gleich hier. 49:52.090 --> 49:52.890 Dijkstra's Algorithmus. 49:55.510 --> 49:58.270 Dijkstra's Algorithmus kennen Sie auch, denke ich, den haben Sie schon 49:58.270 --> 50:00.090 mal gehört, im Bereich der Berechnungs-Research. 50:01.210 --> 50:04.930 Einfacher Algorithmus, wir haben gewichteten Graph, jede Kante hat 50:04.930 --> 50:05.850 also noch ein Gewicht. 50:05.850 --> 50:08.610 Wir möchten nicht nur feststellen, sind die verbunden, sondern was ist 50:08.610 --> 50:09.510 der kürzeste Weg. 50:10.910 --> 50:14.770 Und ich habe also hier noch so eine Funktion c dabei. 50:15.410 --> 50:21.050 Für jede Kante wird ein Wert dort angegeben, irgendeine ganze Zahl, 50:22.330 --> 50:25.450 eine nicht negative ganze Zahl. 50:26.290 --> 50:31.530 Und wenn die Kanten nicht verbunden sind, dann ist das c, i, j gleich 50:31.530 --> 50:32.130 unendlich. 50:34.010 --> 50:39.970 So, und jetzt möchte ich für irgendeinen Ausgangsknoten in so einem 50:39.970 --> 50:42.650 Graphen die kürzesten Wege bestimmen. 50:44.230 --> 50:53.090 Das heißt die Wege mit kürzester Gewichtssumme zu allen anderen Knoten 50:53.090 --> 50:53.310 v. 50:53.310 --> 50:57.150 So, was mache ich? 50:57.230 --> 51:01.910 Ich beginne, der Dijkstra-Algorithmus läuft so, dass ich mit einer 51:01.910 --> 51:07.090 Menge s beginne, oder ich fliege, ich arbeite mit einer Menge s, 51:08.530 --> 51:13.050 zunächst mal in der Knoten u, zudem kenne ich den kürzesten Weg, das 51:13.050 --> 51:13.930 ist nachdem ich die Länge 0. 51:14.930 --> 51:30.190 Und jetzt setze ich für alle anderen Knoten v, betrachte ich als dv 51:30.190 --> 51:37.690 die Kosten der Kante von u nach v, oder des Weges von u nach v. 51:38.110 --> 51:39.570 Zu Anfang ist das nur die Kante. 51:39.570 --> 51:44.190 Da wird also, wenn die nicht verbunden sind, wenn ich also hier 51:44.190 --> 51:49.690 irgendeinen Knoten v habe, sind die direkt verbunden, wenn ich hier 51:49.690 --> 51:52.350 oben einen Knoten v habe, die vielleicht nicht verbunden sind, wird 51:52.350 --> 51:54.190 das unendlich sein. 51:55.190 --> 52:05.330 Jetzt habe ich also dieses dv, ich habe eine Menge von Distanzen, und 52:05.330 --> 52:15.690 jetzt wähle ich einen Knoten aus, der nicht in s liegt, sodass die 52:15.690 --> 52:20.330 Distanz dv minimal ist. 52:21.470 --> 52:31.010 Also ich wähle einen Knoten v, von dem ich weiß, die Distanz, also das 52:31.010 --> 52:39.990 wird iteriert, die Distanz dv ist minimal. 52:42.330 --> 52:47.670 So, das ist also der Knoten, der nach aktueller Kenntnis den kürzesten 52:47.670 --> 52:53.670 Weg hat von u nach v mit der Distanz dv. 52:55.110 --> 52:59.170 Und dann füge ich das w zu der Menge s mit hinzu. 53:02.650 --> 53:07.430 Und das w war eben vorher noch nicht in s mit drin, das heißt, bei den 53:07.430 --> 53:11.530 vorherigen Iterationen war das w weiter entfernt als andere Knoten. 53:11.890 --> 53:15.750 Jetzt hat es unter denen, die noch nicht in s sind, den kürzesten 53:15.750 --> 53:16.290 Abstand. 53:17.140 --> 53:23.670 Und jetzt berechne ich für alle Knoten v, also für irgendeinen, ich 53:23.670 --> 53:28.350 kann jetzt hier also irgendeinen Knoten v noch hinmalen, für alle 53:28.350 --> 53:38.650 Knoten v berechne ich das dv neu, das ist das Minimum der alten 53:38.650 --> 53:46.090 Entfernung von u nach v, oder, das Minimum der alte Entfernung von u 53:46.090 --> 53:53.450 nach v ist dv, das ist hier diese Distanz, dv plus cwv. 53:56.070 --> 54:03.030 Das heißt, das w ist mit v direkt verbunden, das ist das cwv. 54:03.030 --> 54:06.810 Ich gucke mir also an, alle Knoten, die mit w direkt verbunden sind, 54:08.170 --> 54:14.470 und schaue also nach, welcher Wert ist kürzer, entweder der, den ich 54:14.470 --> 54:22.030 bisher betrachtet habe, von u nach v, oder gibt es einen Weg von u 54:22.030 --> 54:26.530 nach v, der über diesen Knoten w führt, den ich gerade dazu genommen 54:26.530 --> 54:32.350 habe zu meiner Menge s, und mit einer Kante direkt mit v verbunden 54:32.350 --> 54:32.750 ist. 54:33.510 --> 54:38.490 Wenn der w kürzer ist als das, was ich bisher betrachtet hätte, was 54:38.490 --> 54:42.630 dort hinführt, dann habe ich hier einen neuen Wert einzutragen. 54:43.990 --> 54:49.370 Es kann eben sein, dass vorher bei dieser Operation, da hatte ich auch 54:49.370 --> 54:52.030 einen Wert drinstehen, aber der war halt größer, und wenn er jetzt 54:52.030 --> 54:56.070 über diese Kante von w nach v kleiner wird, habe ich hier eine 54:56.070 --> 54:57.290 Veränderung einzutragen. 54:58.670 --> 55:01.510 Also das wäre hier im Prinzip das dv gewesen. 55:02.670 --> 55:08.830 Und diese Schritte wiederhole ich, bis ich alle Knoten dort drin habe, 55:09.610 --> 55:23.510 bis also s gleich n-1 ist, dann ist nur ein Knoten übrig, und damit 55:23.510 --> 55:30.770 ist es klar, welches die kürzesten Wege sind zu all diesen Knoten. 55:31.510 --> 55:33.370 Der Aufwand dafür ist wie groß. 55:35.970 --> 55:40.610 Ich muss zunächst mal hier dieses dv setzen für alle Knoten, das ist 55:40.610 --> 55:41.750 natürlich ein linearer Aufwand. 55:42.410 --> 55:46.570 Dann muss ich hier ein Minimum bestimmen, das ist auch ein linearer 55:46.570 --> 55:47.010 Aufwand. 55:47.330 --> 55:51.810 Diese Menge der Knoten wird zwar jedes Mal um eins kleiner, aber 55:51.810 --> 55:57.670 trotzdem ist es jedes Mal ein Aufwand in der Größe der Menge v-s. 55:58.830 --> 56:03.070 Und dann muss ich noch für alle Knoten das dv wieder neu berechnen, 56:03.270 --> 56:05.710 für alle Knoten, die in der Menge v-s drin sind. 56:06.650 --> 56:10.750 Und da ich das entsprechend oft wiederholen muss, habe ich insgesamt 56:10.750 --> 56:12.270 einen Aufwand, der quadratisch ist. 56:12.610 --> 56:18.830 Also das ist hier quadratischer Aufwand, um alle kürzesten Wege zu 56:18.830 --> 56:22.830 bestimmen, von einem Knoten zu allen anderen. 56:25.110 --> 56:27.430 Klassischer Algorithmus, kennen Sie. 56:28.650 --> 56:32.010 Hier ist nochmal etwas zur Korrektheit, das nochmal dargestellt. 56:32.630 --> 56:37.410 Ich wähle immer den Knoten, der den kürzesten Abstand von u hat, wobei 56:37.410 --> 56:40.790 nur Wege über zuvor gewählte Knoten betrachtet werden. 56:41.070 --> 56:45.830 s steht also für Menge der Selected Nodes, deswegen s. 56:48.650 --> 56:56.330 Und ich mache im Prinzip, habe ich hier einen greedy Algorithmus, der 56:56.330 --> 56:59.550 jeweils das nächstbeste hier betrachtet. 57:00.690 --> 57:04.830 Und ich habe also immer, dieses w hier ist jeweils das lokale Optimum. 57:05.930 --> 57:14.790 Um die Korrektheit zu zeigen, muss ich zeigen, dass die Entfernung dw 57:14.790 --> 57:17.870 tatsächlich die Länge des kürzesten Weges von u nach w ist. 57:19.070 --> 57:24.470 Um das zu zeigen, nehme ich einfach an, dass es irgendeinen kürzeren 57:24.470 --> 57:28.510 Weg von u nach w geben könnte, über einen Knoten außerhalb von s. 57:28.510 --> 57:35.890 Also, ich habe jetzt diesen, wie ist denn das, wenn ich von u nach w 57:35.890 --> 57:43.550 laufe, dann, und ich behaupte, es gibt also irgendeinen kürzeren Weg, 57:43.790 --> 57:48.990 als den, den ich jetzt hier betrachte, direkt von u nach w, das wäre 57:48.990 --> 57:49.470 das dw. 57:49.470 --> 57:54.850 Ich behaupte, es gibt einen kürzeren, also hier würde ich ja direkt 57:54.850 --> 57:58.370 von einem Knoten aus s nach w laufen. 57:59.670 --> 58:05.230 Wenn es einen kürzeren Weg gibt, über einen Knoten außerhalb von s, 58:06.990 --> 58:13.930 dann wäre das dx kleiner als das dw. 58:14.890 --> 58:19.010 Dann wäre aber das x vorher schon gewählt worden. 58:19.590 --> 58:23.510 Also das dx muss dann, die Entfernung von u nach x, diese Entfernung 58:23.510 --> 58:28.690 dx muss dann ja kleiner sein als das dw. 58:31.750 --> 58:36.930 Weil ansonsten der Weg von u nach w über x nicht kürzer sein kann als 58:36.930 --> 58:39.990 der Weg von u nach w, wo ich das x nicht mit drin hatte. 58:40.790 --> 58:45.910 Also das ist ein einfacher Widerspruch, dass das x, dass also ein 58:45.910 --> 58:49.050 Knoten geben könnte, der nicht in dem s drin ist, der also noch nicht 58:49.050 --> 58:54.550 gewählt wurde, sodass ich trotzdem direkt zu dem, also einen kürzeren 58:54.550 --> 58:55.750 Weg zu dem w gefunden hätte. 58:56.270 --> 58:59.450 Es reicht sich immer, die Knoten zu nehmen, die in der Menge s drin 58:59.450 --> 59:04.710 sind, um die Wege tatsächlich, um die Weglänge anzupassen. 59:04.710 --> 59:11.050 Und also der Beweis für den Dijkstra-Algorithmus ist sehr naheliegend. 59:11.170 --> 59:15.210 Im Prinzip habe ich Ihnen das hier schon erläutert, dass das so 59:15.210 --> 59:18.610 korrekt läuft mit diesem Algorithmus. 59:21.770 --> 59:25.530 Dass hier tatsächlich die Länge der kürzesten Wege bestimmt wird über 59:25.530 --> 59:34.710 Knoten aus s, ist auch, da muss ich auch was zumalen, also hier wird 59:34.710 --> 59:40.350 die Länge der kürzesten Wege von u nach v über Knoten aus s bestimmt, 59:40.470 --> 59:40.770 genau. 59:41.410 --> 59:55.450 Ich gehe ja zu dem w, also der Weg von u über w und x nach v. 59:56.990 --> 59:58.110 Oder der Weg von, 01:00:02.080 --> 01:00:07.540 also wenn ich betrachte, was ich hier mache in dem Schritt 5 des 01:00:07.540 --> 01:00:11.920 Algorithmus, das war auf Folie 11. 01:00:11.920 --> 01:00:19.880 Ich berechne für alle Knoten, ob die bisherige Distanz, die ich 01:00:19.880 --> 01:00:26.640 betrachtet habe, aktualisiert werden muss, weil es einen Pfad oder 01:00:26.640 --> 01:00:28.980 eine Kante gibt von w direkt nach v. 01:00:29.520 --> 01:00:35.240 Also es gibt einen Pfad von u nach w und jetzt, das ist ja das, was 01:00:35.240 --> 01:00:39.720 ich hier gemacht habe, da habe ich mir nur angeguckt, die Entfernungen 01:00:39.720 --> 01:00:41.520 zu meinen, 01:00:45.860 --> 01:00:53.060 also ich habe ja immer nur betrachtet oder aktualisiert, hier wird 01:00:53.060 --> 01:00:56.960 aktualisiert die Entfernung zu dem Knoten v, dadurch, dass ich einen 01:00:56.960 --> 01:01:00.720 neu hinzugenommenen Knoten w betrachte, der jetzt in der Menge s mit 01:01:00.720 --> 01:01:01.260 drin ist. 01:01:01.440 --> 01:01:04.500 Und ich gucke mir an, ob ich dadurch mit einer direkten Kante zu dem v 01:01:04.500 --> 01:01:05.780 schneller hinkommen kann. 01:01:05.880 --> 01:01:14.020 Wenn ich jetzt das hier betrachte, ich schaue mir also an diese Kante 01:01:14.900 --> 01:01:18.920 und die Frage ist, gäbe es noch einen anderen Weg, der vielleicht 01:01:18.920 --> 01:01:22.900 kürzer wäre, der über eine andere Kante aus dem x gelaufen wäre. 01:01:23.480 --> 01:01:27.580 Also dieser Weg von u über w und noch irgendeine andere Kante in x. 01:01:28.600 --> 01:01:31.980 Das heißt, es könnte es sein, dass ich das v über eine andere Kante 01:01:31.980 --> 01:01:36.400 von einem anderen Knoten aus hätte kürzer erreichen können. 01:01:37.760 --> 01:01:41.780 Und das kann nicht passieren, weil alle Gewichte größer gleich 0 sind. 01:01:41.780 --> 01:01:52.180 Und das heißt, dieser Pfad hier, der kann nicht kürzer sein als das u 01:01:52.180 --> 01:01:57.340 nach w zu dem v über w. 01:01:57.700 --> 01:02:02.940 Wenn das ein kürzerer Weg wäre über x nach dem v, dann wäre das v 01:02:02.940 --> 01:02:06.040 gewählt worden und nicht das w in dem Schritt 3. 01:02:09.560 --> 01:02:13.280 Und auf die Art und Weise kann man sich also auch für diesen Schritt 5 01:02:13.280 --> 01:02:16.600 überlegen, dass dort auf richtige Art und Weise die Distanzen 01:02:16.600 --> 01:02:17.960 aktualisiert werden. 01:02:18.480 --> 01:02:22.680 Und damit ist also die Korrektheit von dem Dijkstra-Algorithmus im 01:02:22.680 --> 01:02:23.180 Prinzip nachgewiesen. 01:02:23.680 --> 01:02:26.300 Ich habe das etwas intuitiv hier argumentiert. 01:02:27.000 --> 01:02:29.620 Man kann das alles auch formal hinschreiben, das wollte ich Ihnen aber 01:02:29.620 --> 01:02:30.160 ersparen. 01:02:30.740 --> 01:02:33.180 Ich wollte aber noch eine Bemerkung machen zum Dijkstra-Algorithmus. 01:02:33.180 --> 01:02:36.820 Das ist ein klassischer Algorithmus, braucht wie gesagt quadratische 01:02:36.820 --> 01:02:43.500 Zeit und wird auch in ganz vielen Anwendungen eingesetzt. 01:02:44.640 --> 01:02:48.440 Wenn ich also kürzten Weg haben will von einem Knoten zu irgendeinem 01:02:48.440 --> 01:02:53.940 anderen, zum Beispiel bei Routingverfahren im Internet, wird genau der 01:02:53.940 --> 01:02:56.600 Dijkstra -Algorithmus eingesetzt, um die kürzesten Verbindungen zu 01:02:56.600 --> 01:02:56.900 finden. 01:02:56.900 --> 01:03:04.300 Wenn Sie aber Routingverfahren machen, im Verkehr zum Beispiel, und 01:03:04.300 --> 01:03:10.940 Sie haben hier ein großes Straßennetz, viele verschiedene Straßen, ein 01:03:10.940 --> 01:03:16.800 riesiges Straßennetz mit riesengroß verbundenen Graphen, und jetzt 01:03:16.800 --> 01:03:20.240 wollen Sie eine kürzeste Verbindung haben zwischen irgendwelchen 01:03:20.240 --> 01:03:23.280 Knoten, Sie wollen Ihre Fahrtroute bestimmen. 01:03:24.140 --> 01:03:28.220 Sie wollen von hier meinetwegen nach dort oben kommen. 01:03:31.560 --> 01:03:35.600 Wenn Sie jetzt den Dijkstra-Algorithmus anwenden, dann werden alle 01:03:35.600 --> 01:03:36.580 Knoten betrachtet. 01:03:37.820 --> 01:03:43.040 Sie laufen im Prinzip so sukzessive von dem hier so rum in solchen 01:03:43.040 --> 01:03:50.040 Fronten durch den ganzen Graphen durch, immer erst die Abstand 1 und 01:03:50.040 --> 01:03:54.540 so weiter, wählen einen nächsten Knoten, wählen dessen direkte 01:03:54.540 --> 01:04:00.100 Nachbarn, wählen dort wieder den kürzesten Weg, wählen wieder dessen 01:04:00.100 --> 01:04:03.560 direkte Nachbarn, wählen immer den Knoten aus, der den kürzesten 01:04:03.560 --> 01:04:05.760 Abstand hat und von dem aus wieder direkten Nachbarn. 01:04:07.140 --> 01:04:08.300 Und das dauert sehr, sehr lange. 01:04:09.180 --> 01:04:13.120 Aber das, was in diesem Bereich hier unten ist, wäre eigentlich gar 01:04:13.120 --> 01:04:13.680 nicht relevant. 01:04:15.580 --> 01:04:22.740 Eigentlich wollen Sie ja nur das betrachten, was eigentlich in einer 01:04:22.740 --> 01:04:26.660 gewissen Nachbarschaft Ihres optimalen Pfades läuft. 01:04:28.800 --> 01:04:34.940 Wenn Sie das machen könnten, dass Sie im Prinzip eine Art haben, wie 01:04:34.940 --> 01:04:40.860 Sie identifizieren können, die relevanten Kanten in dem Graphen, die 01:04:40.860 --> 01:04:45.660 Sie betrachten müssen, um den kürzesten Weg zu finden von A nach B, 01:04:48.280 --> 01:04:51.340 dann hätten Sie hier linearen Aufwand, wenn Sie also diesen Korridor 01:04:51.340 --> 01:04:52.400 schmal machen können. 01:04:52.620 --> 01:04:55.800 Hätten Sie also nur alle Kanten in dem Korridor zu betrachten, Sie 01:04:55.800 --> 01:05:00.200 hätten auf einmal linearen Aufwand in der Länge des Pfades. 01:05:01.280 --> 01:05:03.740 Und man kann das tatsächlich machen. 01:05:04.620 --> 01:05:07.160 Man kann also den kürzesten Weg finden. 01:05:08.020 --> 01:05:12.700 Durch gewisse Vorbearbeitungen des Graphen kann man erreichen, dass 01:05:12.700 --> 01:05:16.540 man deutlich schneller wird als der Dijkstra-Algorithmus. 01:05:16.680 --> 01:05:24.080 Das sind Sachen, das haben hier die Kollegen Wagner und Sanders 01:05:24.080 --> 01:05:27.620 herausgefunden, wie man das macht. 01:05:27.620 --> 01:05:31.820 Die haben also für solche Anwendungen in großen Graphen den Aufwand um 01:05:31.820 --> 01:05:33.740 sehr große Faktoren reduziert. 01:05:34.580 --> 01:05:36.840 Und mittlerweile sind das also die Verfahren, die tatsächlich auch in 01:05:36.840 --> 01:05:38.100 der Praxis eingesetzt werden. 01:05:39.320 --> 01:05:42.620 Also Dijkstra ist ein guter Algorithmus, aber ich muss mir mal 01:05:42.620 --> 01:05:44.080 anschauen, wo setze ich ihn ein. 01:05:44.160 --> 01:05:46.660 Wenn ich in der Lage bin, das ein bisschen zu reduzieren, ist es noch 01:05:46.660 --> 01:05:46.920 besser. 01:05:47.440 --> 01:05:50.660 Also wenn ich eben den Bereich reduzieren oder einschränken kann. 01:05:50.660 --> 01:05:52.300 Natürlich geht das nicht immer. 01:05:53.660 --> 01:05:56.240 Wenn ich einen beliebigen Graphen habe, kann es natürlich sein, dass 01:05:56.240 --> 01:05:59.060 der kürzeste Weg aus irgendeinem Grund gerade hier hinten drüber 01:05:59.060 --> 01:05:59.420 läuft. 01:06:00.500 --> 01:06:03.660 Das muss man dann entsprechend vorher ausgeschlossen haben, dass das 01:06:03.660 --> 01:06:04.160 der Fall ist. 01:06:04.160 --> 01:06:06.240 Man muss dann schon die richtigen wirklich betrachten. 01:06:06.360 --> 01:06:10.200 Aber das kann man in solchen praktischen Straßennetzen, da kann man 01:06:10.200 --> 01:06:11.780 solche Einschränkungen machen. 01:06:11.780 --> 01:06:16.820 Und wenn Sie sich, also nur noch mal so zu den Problemen der kürzesten 01:06:16.820 --> 01:06:22.200 Wege, wenn Sie sich anschauen, die typischen Navigationsverfahren, und 01:06:22.200 --> 01:06:25.480 Sie sind hier meinetwegen auf dem kürzesten Pfad an irgendeinem Knoten 01:06:25.480 --> 01:06:29.680 angekommen, dann stellt sich heraus, Sie haben hier ein Problem, da 01:06:29.680 --> 01:06:31.000 ist eine Abweichung. 01:06:32.640 --> 01:06:34.500 Was machen die Verfahren dann? 01:06:35.740 --> 01:06:40.700 Dann nehmen Sie irgendeinen anderen Knoten, Sie fahren irgendwie ab 01:06:40.700 --> 01:06:46.660 und dann versucht das Verfahren, sucht da den kürzesten Weg zurück zu 01:06:46.660 --> 01:06:48.100 Ihrem alten optimalen Weg. 01:06:50.620 --> 01:06:54.000 Das heißt, da wird nicht der Pfad ganz neu berechnet, sondern man geht 01:06:54.000 --> 01:06:56.620 im Prinzip den kürzesten Weg zurück zu der alten Route. 01:06:58.540 --> 01:07:00.200 Was natürlich schlecht sein kann. 01:07:00.200 --> 01:07:03.920 Es kann sein, dass dadurch, dass Sie hier einen Umweg genommen haben 01:07:03.920 --> 01:07:06.340 hierhin, dass vielleicht das hier besser gewesen wäre. 01:07:08.160 --> 01:07:10.420 Das wird aber bei den üblichen Verfahren nicht gemacht. 01:07:10.540 --> 01:07:17.120 Die meisten Anwendungen, die Sie in Ihren Navigationsgeräten haben, 01:07:17.800 --> 01:07:22.780 die machen so eine einfache Umwegart, dass Sie, wenn Sie abgewichen 01:07:22.780 --> 01:07:26.720 sind von der Route, dann werden Sie zurückgeführt zu Ihrer alten 01:07:26.720 --> 01:07:26.980 Route. 01:07:26.980 --> 01:07:30.020 Deswegen gibt es, wenn man sich nur noch auf den Navi verlässt, und 01:07:30.020 --> 01:07:34.140 man hat irgendeinen Bereich, der gesperrt ist, Sie werden immer wieder 01:07:34.140 --> 01:07:36.080 dahin geführt, wo es gesperrt war. 01:07:37.080 --> 01:07:38.980 Ist also manchmal ein bisschen problematisch. 01:07:39.740 --> 01:07:43.380 Diese Thematik ist eine interessante Thematik, kürzeste Wege zu 01:07:43.380 --> 01:07:47.560 berechnen, in solchen Umgebungen, wo sich Dinge verändern können, dass 01:07:47.560 --> 01:07:50.520 Sie mal auf einmal eine Kante nicht mehr da haben, das wird ein 01:07:50.520 --> 01:07:51.780 Fehlerfall auftreten und so weiter. 01:07:51.880 --> 01:07:53.160 Das ist eine interessante Thematik. 01:07:53.160 --> 01:07:57.520 Also das wären so dynamische Probleme. 01:07:59.360 --> 01:08:05.760 Und noch interessanter ist es, wenn Sie zeitlich unterschiedliche 01:08:05.760 --> 01:08:06.540 Gewichte haben. 01:08:07.740 --> 01:08:09.340 Sie haben Stauvorhersagen. 01:08:09.840 --> 01:08:13.500 Sie wissen, zu bestimmten Zeiten während des Tages sind die Fahrzeiten 01:08:13.500 --> 01:08:16.980 zwischen zwei Punkten anders, die verändern sich. 01:08:16.980 --> 01:08:22.760 Und Sie wollen also einen Weg so planen, dass Sie unter 01:08:22.760 --> 01:08:27.800 Berücksichtigung der zu erwartenden Staus dort gut ans Ziel kommen. 01:08:28.580 --> 01:08:34.440 Dann müssen Sie zeitlich variable Gewichte auf den Kanten haben und je 01:08:34.440 --> 01:08:37.580 nachdem, wann Sie losfahren, würden Sie zu anderen Zeitpunkten dorthin 01:08:37.580 --> 01:08:40.300 kommen müssen, dann entsprechend andere Algorithmen anwenden. 01:08:40.400 --> 01:08:44.220 Das sind Dinge, woran aktuell gearbeitet wird, wie man das dann auch 01:08:44.220 --> 01:08:46.780 noch bestmöglich hinbekommt, wobei man sich eben über eines im Klaren 01:08:46.780 --> 01:08:52.860 sein muss, wenn jetzt alle Leute dynamisch bestmögliche Pfade finden 01:08:52.860 --> 01:08:57.360 würden, würden natürlich die Prognosen für die Staus, die man macht, 01:08:57.620 --> 01:09:00.720 so nicht mehr zutreffen, weil sie ja diese Staus vermeiden. 01:09:02.860 --> 01:09:05.600 Und dann muss man wieder dafür sorgen, dass durch diese Stauvermeidung 01:09:05.600 --> 01:09:07.280 nicht woanders Staus auftauchen. 01:09:08.280 --> 01:09:10.300 Das ist ein sehr dynamisches Problem, ein sehr interessantes 01:09:10.300 --> 01:09:14.020 Optimierungsproblem, mit dem kann man sehr viele interessante 01:09:14.020 --> 01:09:15.240 Forschungsarbeiten drauf machen. 01:09:17.400 --> 01:09:22.660 Und jetzt möchte ich manchmal nicht nur die Verbindungen von einem 01:09:22.660 --> 01:09:27.840 Knoten zu allen anderen haben, sondern ich möchte gerne alle kürzesten 01:09:27.840 --> 01:09:28.520 Wege haben. 01:09:30.080 --> 01:09:32.920 Von je zwei Punkten den kürzesten Weg. 01:09:34.180 --> 01:09:37.920 Und ich kann das also so machen, dass ich für jeden Knoten einfach 01:09:37.920 --> 01:09:42.540 Dijkstra's Algorithmus anwende, dann hätte ich kubischen Aufwand, n 01:09:42.540 --> 01:09:43.040 hoch 3. 01:09:45.700 --> 01:09:53.880 Ich kann aber auch den Floyd'schen Algorithmus anwenden. 01:09:55.800 --> 01:09:59.400 Und bei dem Floyd'schen Algorithmus, wie sieht der aus? 01:10:00.360 --> 01:10:03.860 Der läuft im Prinzip ähnlich, aber der hat hier eine einfache 01:10:03.860 --> 01:10:04.500 Formulierung. 01:10:04.500 --> 01:10:07.920 Sie haben also für je zwei Knoten, haben Sie zunächst mal das 01:10:07.920 --> 01:10:11.140 Kantengewicht draufstehen, das kann also unendlich sein, wenn Sie dort 01:10:11.140 --> 01:10:12.140 keine Verbindung haben. 01:10:13.260 --> 01:10:18.040 Und dann haben Sie hier eine Schleifenformulierung für K gleich 1 bis 01:10:18.040 --> 01:10:20.780 N, für IJ gleich 1 bis N. 01:10:22.280 --> 01:10:28.220 Ist DIJ gleich dem Minimum von DIJ und dem DIK plus DKJ. 01:10:29.040 --> 01:10:34.060 Und jetzt sehen Sie sofort eine Analogie zu dem Worschel-Algorithmus. 01:10:35.480 --> 01:10:39.300 Kürzeste Verbindung zwischen je zwei Knoten. 01:10:40.400 --> 01:10:42.880 Sie haben genau wieder diese Operation. 01:10:43.160 --> 01:10:45.820 Wir hatten bei dem Worschel-Algorithmus hier nicht stehen, das Minimum 01:10:45.820 --> 01:10:54.020 von DIJ und DIK plus DKJ, sondern wir hatten AIJ stehen oder AIK und 01:10:54.020 --> 01:11:06.460 da stand also, das war AIJ gleich AIJ oder AIK und AKJ. 01:11:06.740 --> 01:11:09.200 Die Indexpaare hier sind identisch. 01:11:10.800 --> 01:11:14.640 Sie haben aber nicht oder und und, sondern Sie haben das Minimum von 01:11:14.640 --> 01:11:20.080 zwei Werten und es ist offensichtlich, dass man genau diese Operation 01:11:20.080 --> 01:11:27.700 hier natürlich dann ausführen kann in der Struktur, die wir Worschel 01:11:27.700 --> 01:11:28.820 -Algorithmus genannt haben. 01:11:29.160 --> 01:11:32.040 Das heißt, der Floyd'sche Algorithmus ist eigentlich der Worschel 01:11:32.040 --> 01:11:32.620 -Algorithmus. 01:11:32.980 --> 01:11:33.680 Das ist nichts anderes. 01:11:35.660 --> 01:11:41.840 Das ist also nur hier unten die Operation leicht ersetzt und dadurch 01:11:41.840 --> 01:11:44.400 haben Sie dann nicht nur die Erreichbarkeit, sondern Sie haben den 01:11:44.400 --> 01:11:45.700 kürzesten Weg. 01:11:46.980 --> 01:11:51.540 Die Frage ist, Sie haben hier zunächst mal nur die Längen der 01:11:51.540 --> 01:11:52.400 kürzesten Wege. 01:11:55.020 --> 01:11:59.920 Wenn ich jetzt weiß, das ist der kürzeste Pfad zwischen irgendwelchen 01:11:59.920 --> 01:12:08.700 zwei Knoten, woher weiß ich, wenn ich hier irgendwo bin, über welchen 01:12:08.700 --> 01:12:10.460 nächsten Knoten ich laufen muss? 01:12:14.220 --> 01:12:17.740 Und die Frage ist, wie erreiche ich hier für jedes Paar den 01:12:17.740 --> 01:12:20.380 vollständigen, kürzesten Weg? 01:12:21.560 --> 01:12:24.960 Also erstmal ist das Entwurfsmuster Warschall, das ist klar. 01:12:27.340 --> 01:12:33.520 Wenn ich wissen möchte, wie ich laufen muss, muss ich also von jedem 01:12:33.520 --> 01:12:37.020 Knoten wissen, was ist mein nächster Knoten, über den ich laufen muss. 01:12:39.850 --> 01:12:45.650 Also muss ich doch einfach nur wissen, wenn ich zwei Knoten habe, ich 01:12:45.650 --> 01:12:48.770 muss wissen, welches ist der nächste Knoten, über den ich laufen muss, 01:12:48.890 --> 01:12:50.950 um von A nach B zu kommen. 01:12:51.690 --> 01:12:53.570 Das ist also mein Zwischenknoten K. 01:12:56.230 --> 01:13:00.210 Das heißt, ich betrachte jetzt eine kleine Variante von dem 01:13:00.210 --> 01:13:04.050 Floyd'schen Algorithmus, das ist ja alles so wie vorher. 01:13:06.130 --> 01:13:10.290 Ich betrachte jetzt aber nicht nur die Abstände, sondern ich betrachte 01:13:10.290 --> 01:13:17.050 auch noch jeweils eine Variable WIJ. 01:13:19.730 --> 01:13:23.390 Und das WIJ setzt sich zu Anfang auf I. 01:13:24.590 --> 01:13:30.850 Wenn das CIJ kleiner und endlich ist, wenn ich also einen Weg habe, 01:13:31.590 --> 01:13:35.670 dann ist der Knoten, das ja zu Anfang heißt, ich habe eine Kante von I 01:13:35.670 --> 01:13:43.210 nach J, das heißt, das WIJ gibt mir an, den Knoten, von dem aus ich 01:13:43.210 --> 01:13:48.550 direkt das J erreichen kann, den Knoten J erreichen kann, was ist der 01:13:48.550 --> 01:13:50.230 letzte Knoten auf dem Weg dorthin. 01:13:53.950 --> 01:13:55.830 Und entsprechend mache ich das weiter. 01:13:57.130 --> 01:14:01.690 Hier wird zunächst mal eine kleine Vereinfachung gemacht, das Ganze 01:14:01.690 --> 01:14:06.150 macht ja nur Sinn, wenn ich durch die Summe, also wenn ich den Weg 01:14:06.150 --> 01:14:08.170 über K tatsächlich eine Verbesserung habe. 01:14:08.730 --> 01:14:11.170 Wenn das größer wäre, bräuchte ich hier gar nicht weiterzumachen. 01:14:11.690 --> 01:14:16.590 Nur wenn das eine Verbesserung ist, dann setze ich das DIJ auf diesen 01:14:16.590 --> 01:14:20.090 neuen Wert, DIK plus DKJ. 01:14:22.090 --> 01:14:28.050 Und da ich jetzt weiß, ich habe, wenn wir uns das anschauen, nochmal I 01:14:28.050 --> 01:14:36.110 und J und ich weiß, ich muss jetzt hier über den Knoten K laufen, das 01:14:36.110 --> 01:14:41.150 sind jeweils hier Pfade, keine einzelnen Wege, und mein WIJ, sagte 01:14:41.150 --> 01:14:46.350 ich, war der Knoten, über den ich das J als letztes erreichen kann. 01:14:48.030 --> 01:14:55.390 Das heißt, ich habe hier ein WIJ, hier habe ich ein WIK und da habe 01:14:55.390 --> 01:14:57.350 ich ein WKJ. 01:14:58.010 --> 01:15:03.710 Und wenn jetzt der Weg über K, wenn dieser Weg hier kürzer ist, als 01:15:03.710 --> 01:15:08.830 der Weg, den ich vorher hatte, dann erreiche ich doch den Knoten J 01:15:10.170 --> 01:15:13.970 über den letzten Knoten auf dem Weg von K nach J. 01:15:13.970 --> 01:15:19.410 Das heißt, ich setze einfach das WIJ auf den letzten Knoten, den ich 01:15:19.410 --> 01:15:22.110 auf dem Weg von K nach J besucht hatte. 01:15:24.170 --> 01:15:25.750 Ansonsten brauche ich nichts zu verändern. 01:15:27.450 --> 01:15:33.150 Und damit habe ich immer in dem WIJ gespeichert den letzten Knoten auf 01:15:33.150 --> 01:15:38.070 dem Weg, über den ich auf diesem kürzesten Weg das J erreicht hatte 01:15:38.070 --> 01:15:40.370 und habe damit genau diese Pfadeinformation. 01:15:40.370 --> 01:15:42.930 Und so kann ich sukzessive da durchlaufen. 01:15:43.410 --> 01:15:48.330 Ich habe an jeder Position, für jede Position J oder für jedes, für 01:15:48.330 --> 01:15:53.250 jede, ich habe also dort jeweils gespeichert genau diesen kürzesten 01:15:53.250 --> 01:15:53.550 Pfad. 01:15:54.350 --> 01:15:58.610 Ich weiß also, wenn ich dann zurückgelaufen bin, bei dem Knoten WIJ 01:15:58.610 --> 01:16:03.730 bin, dann kann ich von dem aus betrachten, den kürzesten Pfad von I zu 01:16:03.730 --> 01:16:10.010 diesem Knoten WIJ und habe dann wieder den Knoten, den ich dort als 01:16:10.010 --> 01:16:11.790 letztes besucht habe usw. 01:16:12.870 --> 01:16:17.210 Auf die Art und Weise bekomme ich also einfach mit dieser einfachen 01:16:17.210 --> 01:16:19.510 Variable die Wege auch noch geliefert. 01:16:19.610 --> 01:16:23.530 Ich muss nicht für jeden Pfad, für jeden einzelnen, also wenn ich den 01:16:23.530 --> 01:16:27.450 kürzesten Weg vollständig abspeichern wollte, hätte ich einen hohen 01:16:27.450 --> 01:16:28.330 Speicheraufwand. 01:16:29.350 --> 01:16:32.910 Auch einen hohen Aufwand, um das immer zu aktualisieren. 01:16:32.910 --> 01:16:35.350 Das kann ich mir hier mit sparen. 01:16:36.510 --> 01:16:40.190 Man kann das also alles in einer Matrix abspeichern mit quadratischem 01:16:40.190 --> 01:16:40.590 Aufwand. 01:16:43.190 --> 01:16:48.970 Und jetzt sind wir im Prinzip schon mit diesem Algorithmen in Graphen 01:16:48.970 --> 01:16:49.410 durch. 01:16:51.030 --> 01:16:56.270 Es gibt eine ganze Reihe weiterer Probleme, die man sich anschauen 01:16:56.270 --> 01:16:57.690 kann, die alle sehr interessant sind. 01:16:57.690 --> 01:17:02.790 Ich möchte von einem Graphen die Zusammenhangskomponenten bestimmen. 01:17:03.570 --> 01:17:07.070 Also das sind die verschiedenen Komponenten, wenn ein Graph in so 01:17:07.070 --> 01:17:08.390 verschiedene Teile zerfällt. 01:17:09.210 --> 01:17:10.090 Welche sind das? 01:17:12.590 --> 01:17:16.250 Wie sieht das aus mit dem Grad des Zusammenhangs? 01:17:18.030 --> 01:17:18.730 Was heißt das? 01:17:19.170 --> 01:17:21.910 Ein Graph ist k-Knoten zusammenhängend. 01:17:21.910 --> 01:17:34.650 Das heißt, ich kann irgendeinen beliebigen Knoten rausnehmen, oder ich 01:17:34.650 --> 01:17:39.130 kann bis zu k-Knoten rausnehmen und er ist immer noch zusammenhängend. 01:17:41.390 --> 01:17:45.230 Ich darf also bis zu k-Knoten rausnehmen, einfach zusammenhängend, 01:17:45.290 --> 01:17:47.010 zweifach zusammenhängend usw. 01:17:47.830 --> 01:17:55.110 Das gibt mir praktisch an, wie redundant die Verbindungsstruktur ist. 01:17:55.790 --> 01:17:58.090 Und solche Informationen sind natürlich wichtig. 01:17:58.590 --> 01:18:03.290 Sie wissen zum Beispiel, in Stromnetzen ist es so, dass wir eine N-1 01:18:03.290 --> 01:18:06.330 Sicherheit haben. 01:18:06.430 --> 01:18:12.010 Das heißt, wenn eine Komponente ausfällt, haben Sie immer noch die 01:18:12.010 --> 01:18:14.830 volle Leistungsfähigkeit des Netzes garantiert. 01:18:15.830 --> 01:18:22.230 Sie können also den Ausfall eines beliebigen Knotens tolerieren oder 01:18:22.230 --> 01:18:23.750 auch den Ausfall einer beliebigen Kante. 01:18:24.650 --> 01:18:32.470 Das macht natürlich Unterschiede, wenn hier ein Knoten wäre, der die 01:18:32.470 --> 01:18:35.690 alle verbindet, und der Knoten würde ausfallen, wären die alle uns 01:18:35.690 --> 01:18:36.510 zusammenhängend. 01:18:37.550 --> 01:18:42.890 Wenn eine Kante ausfallen würde, dann wären die immer noch verbunden. 01:18:42.890 --> 01:18:47.330 Also Knotenzusammenhang, Kantenzusammenhang sind leicht 01:18:47.330 --> 01:18:48.050 unterschiedlich. 01:18:48.430 --> 01:18:51.570 Was dann interessiert ist, wo sind die kritischen Bereiche eines 01:18:51.570 --> 01:18:54.150 Graphen, wo sind also die Brücken. 01:18:55.030 --> 01:19:03.150 Brücken wären so etwas oder so etwas oder so etwas und Zentren wäre so 01:19:03.150 --> 01:19:03.970 ein Knoten. 01:19:05.370 --> 01:19:14.130 Das heißt, Brücken wären Kanten, bei deren Ausfall ein Graph 01:19:14.130 --> 01:19:21.070 unzusammenhängend wird oder ein Zentrum ist ein Knoten, bei dessen 01:19:21.070 --> 01:19:24.550 Ausfall der Graph nicht mehr zusammenhängend ist. 01:19:25.130 --> 01:19:27.790 Das sind also die kritischen Punkte eines Graphen. 01:19:28.750 --> 01:19:32.310 Oder ich möchte vollständig verbundene Teilgrafen finden. 01:19:32.590 --> 01:19:39.730 Vollständig verbundene Teilgrafen, das heißt, wenn ich mir die 01:19:39.730 --> 01:19:43.290 transitive Hülle anschaue, dann wäre das in der transitiven Hülle, 01:19:43.350 --> 01:19:44.990 wäre jeder mit jedem verbunden. 01:19:45.950 --> 01:19:49.270 Das wäre ein Klicken in der transitiven Hülle des Graphen. 01:19:50.270 --> 01:19:52.150 Kann von jedem zu jedem anderen kommen. 01:19:53.150 --> 01:19:57.050 Oder ich möchte einen Graphen färben, keine gleich gefärbten Nachbarn. 01:19:58.010 --> 01:20:04.590 Wie viele Farben brauche ich, um einen Graphen so zu färben, dass je 01:20:04.590 --> 01:20:06.570 zwei Nachbarn unterschiedliche Farben haben? 01:20:07.730 --> 01:20:13.850 Typisches Problem, wenn Sie Landkarten färben, Sie wollen Länder mit 01:20:13.850 --> 01:20:16.190 unterschiedlichen Farben kennzeichnen, sodass Sie die direkt 01:20:16.190 --> 01:20:17.010 unterscheiden können. 01:20:17.010 --> 01:20:21.010 Keine zwei Länder, die aneinander grenzen, dürfen der gleichen Farbe 01:20:21.010 --> 01:20:21.730 gefärbt sein. 01:20:23.150 --> 01:20:25.150 Das kann man mit vier Farben erreichen. 01:20:28.830 --> 01:20:32.570 Was ist der Durchmesser eines Graphen? 01:20:33.450 --> 01:20:41.650 Der Durchmesser ist der maximale kürzeste Weg zwischen zwei Knoten 01:20:41.650 --> 01:20:42.490 eines Graphen. 01:20:43.250 --> 01:20:47.930 Sie haben also hier irgendwelche Knoten, Sie gucken sich an, alle 01:20:47.930 --> 01:20:52.910 kürzesten Wege, der maximale kürzeste Weg zwischen irgendwelchen zwei 01:20:52.910 --> 01:20:54.490 Knoten ist der Durchmesser. 01:20:56.530 --> 01:20:58.870 Dann gibt es die Weite eines Graphen. 01:20:58.930 --> 01:21:00.690 Noch ein Problem, das interessant ist. 01:21:01.590 --> 01:21:04.010 Sie schauen sich irgendeinen Graphen an, 01:21:07.150 --> 01:21:10.450 oder auch hier in diesem Graphen. 01:21:11.230 --> 01:21:17.770 Sie schauen sich an, Sie schneiden den Graphen in zwei Teile, und zwar 01:21:17.770 --> 01:21:22.410 so, dass etwa gleich viele Elemente links und rechts liegen. 01:21:24.450 --> 01:21:30.210 Es ist die Frage, wie viele Kanten müssen Sie durchschneiden, um einen 01:21:30.210 --> 01:21:31.970 Graphen in zwei Teile zu teilen. 01:21:33.210 --> 01:21:39.770 Wenn ich Ihnen einen Baum aufmale, einen vollständig balancierten 01:21:39.770 --> 01:21:42.930 Baum, dann bräuchten Sie nur eine Kante zu zerschneiden, und Sie 01:21:42.930 --> 01:21:44.670 hätten eine vollständige Aufteilung. 01:21:46.070 --> 01:21:50.150 Das Problem ist aber, wenn diese eine Kante wegfällt, oder wenn Sie 01:21:50.150 --> 01:21:54.550 Informationen austauschen wollen zwischen diesem Bereich A und dem 01:21:54.550 --> 01:21:57.430 Bereich B, dann hätten Sie hier einen Engpass. 01:21:59.430 --> 01:22:05.030 Also die Anzahl der Kanten, die zwischen so zwei etwa gleich großen 01:22:05.030 --> 01:22:11.710 Teilen eines Graphen liegen, sagen Ihnen etwas darüber, wie lange es 01:22:11.710 --> 01:22:15.790 dauert, um Informationen zwischen diesen beiden Bereichen 01:22:15.790 --> 01:22:16.570 auszutauschen. 01:22:17.250 --> 01:22:22.130 Wenn die miteinander reden müssen, und Sie können das nur über diese 01:22:22.130 --> 01:22:24.950 eine Kante hier oder diesen schmalen Weg da oben, dann dauert das sehr 01:22:24.950 --> 01:22:25.250 lange. 01:22:27.290 --> 01:22:30.090 Also möchten Sie gerne, dass Sie eine, also für 01:22:30.090 --> 01:22:34.310 Kommunikationskomplexität zum Beispiel, wollen Sie gerne erreichen, 01:22:35.050 --> 01:22:41.750 dass Sie eine einigermaßen große Weite eines Graphen haben, egal wie 01:22:41.750 --> 01:22:47.310 Sie den aufteilen in zwei Teile, so dass Operationen auf einem solchen 01:22:47.310 --> 01:22:51.430 Graphen relativ schnell bearbeitet werden können. 01:22:51.530 --> 01:22:54.650 Ansonsten bekommen Sie einen Engpass dadurch, dass Sie über eine 01:22:54.650 --> 01:23:01.870 solche, wie hier bei dem Baum, über einen solchen Engpass halt lange 01:23:01.870 --> 01:23:03.430 brauchen, um Informationen auszutauschen. 01:23:04.610 --> 01:23:09.170 Also Informationen über die Weite eines Graphen sind wichtig, um 01:23:09.170 --> 01:23:13.150 untere Schranken anzugeben für die Ausführungszeit von bestimmten 01:23:13.150 --> 01:23:16.710 Funktionen auf parallelen Rechnerstrukturen. 01:23:17.550 --> 01:23:18.830 Andere Probleme. 01:23:19.070 --> 01:23:20.650 Kürzester Hamilton'scher Kreis. 01:23:20.730 --> 01:23:22.410 Das Problem kennen Sie unter einem anderen Namen. 01:23:22.670 --> 01:23:27.430 Der Hamilton'scher Kreis ist ein Pfad, der alle Knoten eines Graphen 01:23:27.430 --> 01:23:29.270 verbindet, ohne Knotenwiederholungen. 01:23:29.870 --> 01:23:34.210 Kürzester ist praktisch das Travelling Salesperson Problem. 01:23:36.330 --> 01:23:40.330 Anderes Problem ist, Sie wollen ein Layout eines Graphen zeichnen. 01:23:42.230 --> 01:23:44.990 Wie zeichne ich das Layout eines Graphen? 01:23:45.370 --> 01:23:50.530 Ich könnte einen Baum so aufmalen. 01:23:58.040 --> 01:23:59.040 Das wäre ein Baum. 01:23:59.920 --> 01:24:02.140 Ich kann den Baum auch so aufmalen. 01:24:08.460 --> 01:24:10.640 Oder ich kann ihn auch noch anders aufmalen. 01:24:10.740 --> 01:24:12.140 Ich kann ihn so aufmalen. 01:24:14.020 --> 01:24:17.580 Wie male ich einen Baum bestmöglich auf? 01:24:18.180 --> 01:24:21.020 Wie male ich einen beliebigen Graphen bestmöglich auf? 01:24:22.280 --> 01:24:30.000 Also, wenn ich vier Knoten habe, ich habe die miteinander verbunden, 01:24:30.140 --> 01:24:38.960 die und die, und ich habe die noch verbunden, und die verbunden, male 01:24:38.960 --> 01:24:41.400 ich jetzt die Kante zwischen den beiden so hin? 01:24:41.800 --> 01:24:43.700 Oder male ich sie hier direkt durch? 01:24:45.080 --> 01:24:47.360 Möchte ich Kantenkreuzungen erlauben oder nicht? 01:24:47.660 --> 01:24:50.480 Natürlich ein planarer Graph, ich kann das so hinmalen. 01:24:51.460 --> 01:24:53.420 Ist das eine sinnvolle Art, den aufzumalen? 01:24:55.180 --> 01:24:59.300 Also es gibt viele Überlegungen, wie man Graphen zeichnen kann. 01:25:00.160 --> 01:25:06.240 Nehmen Sie sich ein, wenn der Graph der Streckennetz eines 01:25:06.240 --> 01:25:08.180 öffentlichen Nahverkehrs ist. 01:25:09.280 --> 01:25:14.720 Da wollen Sie, dass die geografischen Zuordnungen, dass das 01:25:14.720 --> 01:25:15.900 einigermaßen passt. 01:25:16.800 --> 01:25:18.620 Sie wollen aber auch eine schnelle Übersicht haben. 01:25:20.020 --> 01:25:21.740 Der muss leicht überschaubar sein. 01:25:23.200 --> 01:25:27.060 Also, Graphen zu zeichnen, ist ein sehr interessantes Problem. 01:25:28.120 --> 01:25:32.440 Und da kann man also viele verschiedene Kriterien aufführen. 01:25:33.020 --> 01:25:36.060 Kann sein, dass ich eine gleichmäßige Knotenkantenverteilung haben 01:25:36.060 --> 01:25:36.360 möchte. 01:25:36.500 --> 01:25:39.240 Das will ich bei einem Streckennetz einer U-Bahn nicht haben. 01:25:39.800 --> 01:25:43.360 Nicht gleichmäßige Knotenkantenverteilung, sondern das soll der 01:25:43.360 --> 01:25:47.080 Geografie der Stadt entsprechen. 01:25:47.940 --> 01:25:51.280 Minimale Anzahl Kreuzungen, das sind andere, habe ich hier angedeutet. 01:25:53.600 --> 01:25:54.960 Symmetrieeigenschaften können eine Rolle spielen. 01:25:54.960 --> 01:25:58.360 Da gibt es viele verschiedene Probleme, die man betrachten kann. 01:25:59.040 --> 01:26:02.980 Und das, was interessant ist, hatte ich schon gesagt vorhin, dass also 01:26:02.980 --> 01:26:06.440 gerade die Probleme, die hier oben sind, im Prinzip alle entweder vom 01:26:06.440 --> 01:26:09.180 Typ Matrixmultiplikation oder vom Typ Warschall sind. 01:26:09.700 --> 01:26:12.080 Und man kann sie alle mit diesen beiden Mustern, die ich Ihnen 01:26:12.080 --> 01:26:14.160 vorgestellt habe, im Prinzip bearbeiten. 01:26:15.120 --> 01:26:16.500 Das sei für heute genug. 01:26:16.500 --> 01:26:22.800 Ah ja, das ist noch was anderes. 01:26:25.780 --> 01:26:31.680 Zum Mapping-Ansatz, ich kann natürlich den Warschall-Algorithmus auch 01:26:31.680 --> 01:26:32.760 abbilden. 01:26:33.020 --> 01:26:37.180 Wir haben diese Parallelisierung betrachtet, bei denen wir über den 01:26:37.180 --> 01:26:41.520 Mapping -Ansatz das Ganze betrachtet haben. 01:26:41.800 --> 01:26:45.800 Wenn Sie das hier machen, als Rekurrenzgleichung aufmalen, dann 01:26:45.800 --> 01:26:53.060 stellen Sie fest, dass die Datenabhängigkeiten in diesen 01:26:53.060 --> 01:26:55.640 Rekurrenzgleichungen alle unterschiedlich sind. 01:26:55.900 --> 01:26:57.840 Das sind keine uniformen Rekurrenzgleichungen. 01:26:58.600 --> 01:27:03.080 Und deswegen, wenn Sie den Warschall-Algorithmus modellieren im Sinne 01:27:03.080 --> 01:27:07.520 dieses Mapping-Ansatzes, sehen Sie, dass Sie mit dem üblichen Ansatz 01:27:07.520 --> 01:27:09.260 hier nicht zum Ziel kommen. 01:27:09.260 --> 01:27:13.160 Da musste man eben diese andere Überlegung machen, die wir gemacht 01:27:13.160 --> 01:27:18.380 haben mit der Wavefront, also mit dem wellenförmigen Abarbeiten von 01:27:18.380 --> 01:27:18.960 Diagonalen. 01:27:19.360 --> 01:27:22.060 Okay, das ist aber wirklich jetzt alles, was ich in dem Kapitel Ihnen 01:27:22.060 --> 01:27:22.740 zeigen wollte. 01:27:23.240 --> 01:27:25.540 Damit haben wir heute ein ganzes weiteres Kapitel geschafft. 01:27:26.440 --> 01:27:30.140 Und nächste Woche bin ich nicht da, da wird Herr Schuklam mich 01:27:30.140 --> 01:27:30.680 vertreten. 01:27:31.220 --> 01:27:36.800 Nächste Woche haben wir Abschluss unseres Projektes EIZEUS und haben 01:27:36.800 --> 01:27:38.060 dann eine Veranstaltung in Stuttgart. 01:27:38.060 --> 01:27:42.040 Nächste Woche wird also Herr Schukla Ihnen etwas erzählen über ein 01:27:42.040 --> 01:27:44.260 paar Probleme im Bereich algorithmische Geometrie. 01:27:44.740 --> 01:27:45.940 Vielen Dank für die Aufmerksamkeit.