WEBVTT 00:08.090 --> 00:10.770 Willkommen zur Algorithmenvorlesung. 00:13.130 --> 00:14.890 Erstmal sorry für die kleine Verzögerung. 00:18.350 --> 00:22.290 Als allererstes würde ich mit ein paar organisatorischen Dingen mal 00:22.290 --> 00:22.970 kurz anfangen. 00:23.930 --> 00:28.210 Es gibt jetzt ein Update von der Vorlesungswebsite, wir haben jetzt 00:28.210 --> 00:29.130 ein paar mehr Angebote. 00:29.310 --> 00:32.270 Es gibt jetzt ein Feedback-Kasten, wenn Ihnen was auf dem Herzen 00:32.270 --> 00:32.510 liegt. 00:32.510 --> 00:38.150 Es gibt jetzt ein Forum, wo Sie sich dann beteiligen können oder wenn 00:38.150 --> 00:39.850 Sie Fragen haben, die auch fragen können. 00:40.970 --> 00:46.050 Dann gibt es einen YouTube-Mitschnitt, wenn Sie es nicht schon gemerkt 00:46.050 --> 00:48.590 haben und der wird da auch verlinkt. 00:49.470 --> 00:52.250 Und die Tutorien sollten jetzt auch eingeteilt sein. 00:56.590 --> 01:00.250 Gibt es sonst noch organisatorische Fragen, Unklarheiten? 01:03.490 --> 01:07.210 Ansonsten würde ich dann anschließen an das, was wir letztes Mal 01:07.210 --> 01:09.510 gemacht haben, vorher aber noch mal einen kleinen Überblick geben. 01:09.930 --> 01:12.210 Zunächst mal, wie gesagt, an das, was wir letztes Mal gemacht haben. 01:13.930 --> 01:18.270 Und das war vor allem ein Überblick und ein paar Vereinbarungen über 01:18.270 --> 01:19.790 Konzepte, die wir brauchen werden. 01:21.290 --> 01:25.630 Wir haben uns letztes Mal einige Vereinbarungen zur Algorithmenanalyse 01:25.630 --> 01:25.630 angeguckt. 01:25.690 --> 01:28.510 Das ist das O-Kalkül gewesen aus technischer Seite. 01:29.230 --> 01:31.270 Und intuitiv, was wir eigentlich wollen. 01:31.510 --> 01:34.770 Wir haben uns darauf geeinigt, was wir denn am Ende idealerweise 01:34.770 --> 01:35.670 dastehen haben wollen. 01:37.510 --> 01:40.630 Insbesondere waren das so Dinge wie, wir wollen die Laufzeit von einem 01:40.630 --> 01:43.870 Algorithmus zählen und zwar im Worst Case üblicherweise, aber 01:43.870 --> 01:46.490 vielleicht haben wir auch manchmal Situationen, wo das nicht so gut 01:46.490 --> 01:46.690 ist. 01:47.390 --> 01:51.310 Dann haben wir uns auf ein Maschinenmodell geeinigt und das war das 01:51.310 --> 01:55.710 RAM -Modell, also das Random Access Machine Modell. 01:56.310 --> 01:59.450 Und das Wichtige dabei ist, wir haben also freien Zugriff auf den 01:59.450 --> 02:00.230 Hauptspeicher. 02:01.150 --> 02:05.130 Und vielleicht eine Sache, die nicht so ganz kanonisch ist, ist, dass 02:05.130 --> 02:10.430 wir Register haben und Speicherkomponenten, die jeweils logarithmisch 02:10.430 --> 02:13.350 breit sind in der Anzahl der benutzten Speicherzellen. 02:13.350 --> 02:17.110 Und was genau benutzt dann bedeutet, maximal oder wie auch immer, das 02:17.110 --> 02:19.950 hängt dann tatsächlich von dem Algorithmus ab, den wir uns angucken. 02:21.450 --> 02:24.830 Okay, das haben wir dann als Vereinbarung getroffen und letztlich ist 02:24.830 --> 02:27.830 die Idee, dass alle Algorithmen, die wir uns angucken in Pseudocode, 02:27.990 --> 02:34.190 also zu Pseudocode gleich mehr, die werden wir dann übersetzt, uns 02:34.190 --> 02:35.810 denken, in dieses Maschinenmodell. 02:36.350 --> 02:39.850 Und was Pseudocode angeht zum Beispiel, haben wir dann auch noch ein 02:39.850 --> 02:43.430 paar Vereinbarungen getroffen und in gewisser Weise so ein paar 02:43.430 --> 02:45.130 Abstraktionen auch legitimiert. 02:45.390 --> 02:47.770 Also viele Dinge kann man vielleicht nicht auf dem Taktzyklus genau 02:47.770 --> 02:50.730 festlegen, insbesondere nicht unabhängig von der Maschine. 02:51.710 --> 02:55.830 Und selbst wenn wir so eine RAM-Maschine festlegen, da werden 02:55.830 --> 03:00.110 vielleicht immer noch zur Realität noch so ein paar Ungenauigkeiten 03:00.110 --> 03:00.430 sein. 03:01.010 --> 03:05.450 Und deshalb werden wir insbesondere bei dieser Übersetzung auch nicht 03:05.450 --> 03:06.790 auf Konstanten achten. 03:07.430 --> 03:09.930 Bei Konstanten in der Ausführungszeit insbesondere. 03:10.590 --> 03:13.190 Ja, wir haben uns wie gesagt beim Pseudocode so ein paar Beispiele 03:13.190 --> 03:18.270 angeguckt und eine wichtige Sache dabei war, dass wir uns Invarianten 03:18.270 --> 03:20.210 und Bedingungen angeguckt haben. 03:20.870 --> 03:24.530 Das sind Dinge, die im Pseudocode stehen und für uns insofern wichtig 03:24.530 --> 03:30.210 sind, als dass sie sagen, was wir erwarten zum Aufruf vom Algorithmus, 03:30.270 --> 03:33.510 was wir garantieren am Ende in der Nachbedingung und was irgendwann 03:33.510 --> 03:36.230 während einer Schleife oder womöglich in der Datenstruktur, da sehen 03:36.230 --> 03:38.570 wir heute auch noch was, was gelten soll. 03:38.730 --> 03:39.310 Bestimmte Dinge. 03:40.770 --> 03:43.450 Also insbesondere haben wir uns dann mal den Algorithmus angeguckt und 03:43.450 --> 03:48.790 erst mit Invarianten versehen, naja, ließ der sich dann so 03:48.790 --> 03:52.170 einigermaßen handhaben oder wir haben gesehen, warum der funktioniert. 03:53.330 --> 03:55.730 Also wir haben hier so eine Schleifeninvariante, die wird immer dann 03:55.730 --> 04:00.050 erfüllt, wenn wir an dieser Stelle im Ablauf kommen und diese 04:00.050 --> 04:05.170 Assertions, also diese Bedingungen vor und nach dem Funktionsaufruf, 04:06.090 --> 04:09.250 die legen halt fest, was wir erwarten und was am Ende rauskommt. 04:10.670 --> 04:12.490 Okay, haben wir uns auch ein paar Beispiele angeguckt. 04:13.550 --> 04:17.710 Und das letzte, was wir uns angeguckt haben, ist das Mastertheorem. 04:18.150 --> 04:19.250 Und das haben wir dann auch bewiesen. 04:19.770 --> 04:24.890 Das Mastertheorem, das gibt uns eine Aussage darüber, wie wir solche 04:24.890 --> 04:29.330 Rekurrenzen, die oft auftreten, wenn wir rekursive Algorithmen 04:29.330 --> 04:31.270 analysieren, wie wir die auflösen. 04:31.770 --> 04:35.010 Also wir haben zwei Beispiele letztes Mal schon gesehen von 04:35.010 --> 04:39.370 Algorithmen, die halt ein großes Teilproblem in kleinere Teilprobleme 04:39.370 --> 04:39.710 aufteilen. 04:40.230 --> 04:45.470 Und zwar, das waren diese rekursiven Multiplikationsalgorithmen, 04:45.590 --> 04:46.590 insbesondere Carazuba. 04:47.690 --> 04:52.450 Und da haben wir jeweils ein Problem der Größe n, also dass wir zwei n 04:52.450 --> 04:53.890 -Bit -Zahlen miteinander multiplizieren. 04:53.890 --> 04:58.950 Wir haben in dem Fall bei Carazuba in drei Teilprobleme der Größe n 04:58.950 --> 05:03.370 -Halbe aufgeteilt und das dann rekursiv abgearbeitet. 05:04.010 --> 05:10.210 Und je nachdem, wie da genau diese Balance ist zwischen zum einen der 05:10.210 --> 05:13.170 Zeit, die wir fürs Aufteilen brauchen, c mal n, das ist nur der 05:13.170 --> 05:17.630 Aufteilungsschritt selber, und dann die Anzahl der Teile d und die 05:17.630 --> 05:21.330 jeweilige Teilgröße, die gegeben wird durch b oder als der Anteil 05:21.330 --> 05:25.030 quasi, der Bruchteil von der Ursprungsgröße. 05:26.250 --> 05:30.790 Alles das fließt dann in so eine Fallunterscheidung ein, also genauer 05:30.790 --> 05:31.450 gesagt d und b. 05:32.250 --> 05:35.870 Und in dieser Fallunterscheidung können wir dann sehen, wie groß die 05:35.870 --> 05:36.970 Laufzeit insgesamt ist. 05:37.130 --> 05:42.550 Also für uns war das dann bei Carazuba Theta von n hoch ungefähr 1,58, 05:42.850 --> 05:47.310 also genauer gesagt Theta von n hoch der Logarithmus von 3 zu Basis 2, 05:47.310 --> 05:51.150 weil wir da halt hier drei Teilstücke haben und die waren jeweils halb 05:51.150 --> 05:51.590 so groß. 05:52.310 --> 05:56.190 Und dieses allgemeine Theorem haben wir letztes Mal bewiesen. 05:56.550 --> 05:58.670 Also zum Beweis brauche ich jetzt auch gar nicht mehr viel zu sagen. 05:59.590 --> 06:03.950 Die Idee war, dass wir uns halt angucken, wie viel Zeit für das 06:03.950 --> 06:07.310 Aufteilen verbraten wird, jeweils auf den verschiedenen Ebenen. 06:08.750 --> 06:14.630 Und je nachdem, ob dann die Anzahl der Teilstücke größer war als der 06:14.630 --> 06:21.150 Bruchteil, oder hier in dem Fall kleiner als der Bruchteil, der Größe 06:21.150 --> 06:21.790 der Teilstücke. 06:21.990 --> 06:25.510 Also in dem Fall hier wäre es zwei Teilstücke, jeweils ein Viertel so 06:25.510 --> 06:28.810 groß, die zusammengerechnet sind, dann kleiner als das, was wir 06:28.810 --> 06:29.770 ursprünglich hatten. 06:30.630 --> 06:34.090 Dann kommt man zu dem Fall, wo alles am Ende ziemlich schnell geht und 06:34.090 --> 06:35.250 wir haben einen linearen Aufwand. 06:36.010 --> 06:40.270 Dann gab es diesen n log n Aufwand, wenn das, was wir da aufgeteilt 06:40.270 --> 06:43.090 haben, zusammengerechnet, wieder genau so groß ist, wie das, womit wir 06:43.090 --> 06:43.770 angefangen haben. 06:44.830 --> 06:47.290 Und dann haben wir den Teil, der für uns, für die 06:47.290 --> 06:52.170 Multiplikationsalgorithmen, interessanter war, da wo die Zeit, bzw. 06:52.330 --> 06:57.070 die Gesamtgröße der Probleme nach dem Aufteilen größer war als die 06:57.070 --> 06:59.050 Ursprungsproblemgröße. 06:59.590 --> 07:02.270 Und dann kriegen wir so ein exponentielles Wachstum und das äußert 07:02.270 --> 07:07.370 sich halt in so einem n hoch irgendwas Term bei der Gesamtlaufzeit. 07:07.510 --> 07:09.790 Also das haben wir letztes Mal gemacht, bis dahin waren wir gekommen. 07:11.010 --> 07:15.650 Was ich noch tun würde, dazu abschließend, ist, das vielleicht noch 07:15.650 --> 07:19.250 ein bisschen mehr zu motivieren mit Beispielen, weil man das immer mal 07:19.250 --> 07:20.870 wieder braucht, dieses Theorem. 07:21.470 --> 07:24.870 Also man kann halt beim rekursiven Algorithmus dann sehen, wie groß 07:24.870 --> 07:28.110 sind die Teilprobleme, die ich aufteile, wie viele Stücke habe ich, 07:28.310 --> 07:30.610 wie groß sind die einzelnen Teilprobleme, wie groß ist es, wenn ich 07:30.610 --> 07:31.350 das zusammenrechne. 07:31.370 --> 07:33.690 Und dann ist man sofort in einem von diesen drei Fällen. 07:33.790 --> 07:35.010 Und das kommt halt auch öfter mal vor. 07:35.810 --> 07:38.910 Also ein Fall ist zum Beispiel Sortieralgorithmen. 07:38.910 --> 07:41.730 Das ist für uns ein interessanter Fall, denn da haben wir dann eine 07:41.730 --> 07:43.350 Laufzeit, die ist n log n. 07:43.630 --> 07:47.490 Und viele interessante Sortieralgorithmen, die haben halt genau diese 07:47.490 --> 07:50.570 Laufzeit n log n, wenn ich eine Eingabe der Größe n bekomme. 07:51.370 --> 07:55.570 Für Quicksort stimmt das eigentlich nicht ganz, sondern eigentlich 07:55.570 --> 07:58.370 müssen wir dann eine Variante von Quicksort betrachten, damit das 07:58.370 --> 07:58.910 wirklich stimmt. 07:59.050 --> 08:00.910 Aber dazu kommen wir dann bei den Sortieralgorithmen noch. 08:01.410 --> 08:04.870 Die Schulmultiplikation und die Karatsuba-Aufmann-Multiplikation, also 08:04.870 --> 08:08.970 insbesondere die rekursive Schulmultiplikation, die haben wir schon 08:08.970 --> 08:09.910 hier identifiziert. 08:10.690 --> 08:16.050 Und es gibt auch Fälle, wo man tatsächlich Dinge aufteilt und hat am 08:16.050 --> 08:18.070 Ende sozusagen weniger Probleme als vorher. 08:19.090 --> 08:21.770 Und dann ist man im günstigen Fall, wo alles linear ist. 08:25.600 --> 08:31.880 Wir sind immer noch in diesem Vereinbarungskapitel und die letzten 08:31.880 --> 08:35.500 Dinge, die wir uns angucken, sind also nicht wirklich randomisierte 08:35.500 --> 08:37.840 Algorithmen, sondern dazu später mehr. 08:37.840 --> 08:41.620 Insbesondere auch bei der Analyse wird es dann manchmal hilfreich 08:41.620 --> 08:45.480 sein, wenn man vielleicht irgendwo eine Zufallseingabe noch hat. 08:46.060 --> 08:48.640 Das gucken wir uns wie gesagt später an, sondern was wir uns noch ein 08:48.640 --> 08:50.120 bisschen genauer angucken, sind Graphen. 08:51.380 --> 08:53.880 Also jetzt geht es vor allem darum, das haben Sie sicherlich schon mal 08:53.880 --> 08:56.240 gesehen, Sie wissen sicherlich, was ein Graph ist, dass wir einfach 08:56.240 --> 08:59.760 ein paar Vereinbarungen treffen, wie wir Dinge nennen wollen und was 08:59.760 --> 09:01.900 erlaubt ist und was nicht erlaubt ist, was wir unter einem Graph 09:01.900 --> 09:02.600 verstehen wollen. 09:03.680 --> 09:08.000 Also zunächst mal, ein Graph ist formal nicht so ein Bild, sondern 09:08.000 --> 09:10.720 formal ist es eigentlich erstmal eine Relation. 09:10.900 --> 09:15.140 Also wir können einen Graphen auffassen als eine Relation auf eine 09:15.140 --> 09:20.680 Menge der Knoten und eine binäre Relation und zwei Knoten stehen in 09:20.680 --> 09:25.600 Relation oder wir haben eine Relation von hier, wie wäre das zum 09:25.600 --> 09:27.440 Beispiel, von Y nach Z. 09:28.380 --> 09:32.600 Intuitiv dann, wenn es in dem Graphen, wenn wir aussagen wollen, dass 09:32.600 --> 09:34.380 es eine Kante von Y nach Z gibt. 09:34.380 --> 09:37.980 Also so können wir einen Graphen in Relationen übersetzen und 09:37.980 --> 09:38.700 umgekehrt auch. 09:41.680 --> 09:45.380 Also das sind Knoten und Kanten und gemalt haben Sie das sicherlich 09:45.380 --> 09:49.480 schon mal gesehen, die können dann beliebige Dinge repräsentieren. 09:49.780 --> 09:55.600 Also das hier könnte vielleicht so eine Art Routennetzwerk sein, was 09:55.600 --> 09:59.380 ein bisschen komisch ist, weil man hier auch Längen dran hat. 09:59.500 --> 10:01.060 Also dazu vielleicht gleich nochmal später mehr. 10:01.060 --> 10:04.360 Manchmal könnte es vielleicht sogar günstig sein, irgendwo 10:04.360 --> 10:08.600 langzufahren, weil man dadurch vielleicht noch beim Transport von 10:08.600 --> 10:10.960 irgendwelchen Dingen was Günstiges macht, was einem letzten Endes 10:10.960 --> 10:11.760 Ressourcen spart. 10:12.440 --> 10:16.000 Okay, aber das sind so grob Knoten und Kanten, haben Sie sicherlich 10:16.000 --> 10:18.740 schon gehört in Grundbegriffe. 10:20.120 --> 10:24.000 Dann gibt es als wichtige Unterscheidung bei Graphen gerichtete und 10:24.000 --> 10:25.120 ungerichtete Graphen. 10:25.120 --> 10:29.860 Also ungerichtete Graphen, das sind zum Beispiel die hier. 10:31.480 --> 10:34.620 Und das sind Graphen, wo die Kanten keine Richtung haben. 10:34.780 --> 10:40.040 Also die zugehörige Relation wäre dann entweder symmetrisch oder wir 10:40.040 --> 10:42.580 gucken halt gar nicht drauf, in welcher Reihenfolge das passiert. 10:44.160 --> 10:47.420 Das heißt also hier haben die Kanten keine Richtung. 10:48.780 --> 10:53.100 Und das Gegenstück dazu, das sind gerichtete Graphen. 10:53.100 --> 10:55.580 Naja, da haben die Kanten natürlich, die gehen halt jeweils von einem 10:55.580 --> 10:57.340 Knoten zum anderen mit einer Richtung. 10:58.060 --> 11:02.660 Man kann natürlich jeden ungerichteten Graphen auch als gerichteten 11:02.660 --> 11:05.760 Graphen auffassen, zum Beispiel indem man einfach die Kanten in beide 11:05.760 --> 11:08.200 Richtungen dann zählen lässt. 11:08.840 --> 11:11.420 Und so ähnlich ist dann auch die Interpretation, wenn wir über Wege 11:11.420 --> 11:12.120 oder sowas reden. 11:13.140 --> 11:14.700 Das sind dann beide Richtungen erlaubt. 11:15.980 --> 11:20.520 Und man kann auch jeden gerichteten Graphen wieder als ungerichteten 11:20.520 --> 11:22.540 Graphen betrachten, indem wir einfach die Richtung vergessen. 11:23.040 --> 11:25.040 Und wenn wir zwei solche Kanten haben, ist das egal. 11:27.540 --> 11:30.460 Im ungerichteten Graphen ist dann nur eine Kante da. 11:33.560 --> 11:39.440 Wie schon hier vielleicht mal angedeutet, manchmal haben Knoten und 11:39.440 --> 11:41.820 Kanten so eine Art Vielfachheit. 11:42.000 --> 11:45.780 Also bei den Kanten wären das Gewichte, die an den Kanten dran sind. 11:46.280 --> 11:48.740 Und das bedeutet einfach, zu jeder dieser Relationen haben wir noch 11:48.740 --> 11:50.320 eine Zahl. 11:50.320 --> 11:54.220 Die muss nicht positiv sein, also die kann auch mal minus zwei sein. 11:55.120 --> 12:01.240 Aber die gibt uns vielleicht intuitiv manchmal sowas an wie die 12:01.240 --> 12:02.820 Weglänge zwischen W und X. 12:02.940 --> 12:06.480 Wenn ich von W nach X fahre, kostet mich das eine Einheit. 12:07.940 --> 12:09.820 Und wie gesagt, es gibt vielleicht auch Anwendungen, vielleicht auch 12:09.820 --> 12:12.040 viele, wo das unsinnig ist. 12:12.120 --> 12:14.760 Aber in manchen Anwendungen hat man dann vielleicht sogar negative 12:14.760 --> 12:15.680 Kosten. 12:16.100 --> 12:17.900 Und in dem Fall ein negatives Kantengewicht. 12:17.900 --> 12:21.580 Also jedenfalls wollen wir es uns mal nicht verbieten, a priori. 12:23.060 --> 12:32.520 Und so ein Begriff der Vielfachheit bei Knoten wäre dann der Grad. 12:33.080 --> 12:36.600 Also der Eingangsgrad und der Ausgangsgrad. 12:36.760 --> 12:40.840 Das sind bei gerichteten Graphen jeweils die Anzahl der Kanten, die in 12:40.840 --> 12:42.080 diesen Knoten reingehen. 12:42.080 --> 12:44.720 Das wäre der Eingangsgrad und der Ausgangsgrad ist halt die Zahl der 12:44.720 --> 12:49.200 Kanten, die daraus gehen, aus diesem Knoten. 12:49.620 --> 12:53.900 Und bei einem ungerichteten Graphen machen wir da keinen Unterschied. 12:54.020 --> 12:55.100 Da gibt es halt einfach nur einen Grad. 12:57.980 --> 12:59.160 Okay, was gibt es sonst noch? 12:59.200 --> 13:01.440 Es gibt noch Teilgraphen. 13:02.260 --> 13:04.000 Und das können dann zum Beispiel diese sein. 13:04.020 --> 13:06.500 Das wird manchmal ganz nützlich sein, indem wir halt nur die 13:06.500 --> 13:10.580 Teilgraphen betrachten, die bestimmte Knoten enthalten. 13:10.580 --> 13:13.180 Und die Kanten, die dann ins Nichts führen oder aus dem Nichts kommen, 13:13.340 --> 13:14.400 die werfen wir dann halt weg. 13:16.200 --> 13:21.380 Okay, also wichtiges Konzept für uns sind Pfade. 13:21.980 --> 13:24.400 Und das sind einfach Wege durch diesen Graphen. 13:25.100 --> 13:28.600 Also wenn ich den Pfeilen halt folge, dann habe ich einen Pfad. 13:29.740 --> 13:31.320 Und dann gibt es einfache Pfade. 13:31.540 --> 13:35.280 Einfache Pfade, das sind die, wo die Knoten nicht zweimal vorkommen. 13:35.280 --> 13:39.720 Also das heißt, ich könnte von V nach X gehen und das wäre ein 13:39.720 --> 13:40.400 einfacher Pfad. 13:40.880 --> 13:42.500 Und dann gibt es hamiltonische Pfade. 13:44.020 --> 13:49.260 Und das sind die, wo halt jeder Knoten einmal besucht wird in dem 13:49.260 --> 13:49.820 Graphen. 13:50.240 --> 13:52.700 Und es gibt auch noch hamiltonische Kreise. 13:53.540 --> 13:56.320 Achso, Kreise habe ich auch noch nicht erklärt. 13:56.500 --> 14:01.920 Kreise, das sind halt solche Pfade, wo ich dann halt am Ende wieder da 14:01.920 --> 14:03.800 ankomme, wo ich losgegangen bin. 14:04.860 --> 14:06.600 Und dann gibt es hamiltonische Kreise. 14:07.020 --> 14:10.540 Das sind halt genau solche Kreise, wo ich keinen Knoten zweimal 14:10.540 --> 14:12.080 besuche. 14:12.740 --> 14:16.940 Und vor allem geht es halt, wie gesagt, nur darum, eine Sprechweise zu 14:16.940 --> 14:17.280 haben. 14:17.980 --> 14:21.920 Und vielleicht eine Sonderregelung oder nicht unbedingt 14:21.920 --> 14:23.460 Sonderregelung, aber eine Vereinbarung. 14:23.840 --> 14:27.720 Manche Leute gucken sich Graphen mit Schlingen an oder mit Selfloops. 14:27.720 --> 14:33.440 Das sind halt solche, wo ich eine Kante von einem Knoten zu sich 14:33.440 --> 14:34.060 selber habe. 14:34.300 --> 14:38.140 Also für uns wird es günstig sein, einfach um ein paar 14:38.140 --> 14:40.740 Sonderbehandlungen zu vermeiden, dass wir das verbieten. 14:41.100 --> 14:44.440 Also unsere Graphen haben niemals solche Schlingen. 14:48.140 --> 14:51.540 Okay, wichtiges Konzept für später, gucken wir uns auf der 14:51.540 --> 14:54.380 übernächsten Folie, glaube ich, nochmal genauer an. 14:54.380 --> 14:58.160 Das sind DAGs, also die haben so einen kurzen Namen, weil man die 14:58.160 --> 14:59.080 einfach so oft braucht. 14:59.220 --> 15:02.000 Das ist halt eine sehr nützliche Struktur. 15:02.820 --> 15:07.920 Und was das bedeutet, das sind Directed Acyclic Graphs und Directed, 15:07.960 --> 15:10.380 naja halt gerichtet, also gerichtete Graphen. 15:11.920 --> 15:16.340 Und acyclic ist das Wichtige, die sind nämlich kreisfrei, also die 15:16.340 --> 15:17.920 haben keine Kreise. 15:17.980 --> 15:23.260 Wenn ich da die Pfeile entlang gehe, dann kann ich nicht im Kreis 15:23.260 --> 15:23.480 gehen. 15:23.480 --> 15:27.060 Und das bedeutet insbesondere, dass ich nicht unendlich lange in 15:27.060 --> 15:29.120 irgendeinem Algorithmus hänge, wenn ich immer den Pfeilen entlang 15:29.120 --> 15:29.300 gehe. 15:32.040 --> 15:37.900 Andere wichtige Struktur, die wir schon vor den eigentlichen Graphen 15:37.900 --> 15:40.560 -Kapiteln, wo wir allgemeinere Resultate haben, nochmal genauer 15:40.560 --> 15:41.860 angucken, sind Bäume. 15:42.660 --> 15:46.380 Also schon vorher, gerade bei sortierten Listen zum Beispiel, gucken 15:46.380 --> 15:47.240 wir uns Bäume an. 15:48.240 --> 15:51.080 Und zunächst mal, also es gibt gerichtete und ungerichtete Bäume. 15:53.340 --> 15:58.640 Und ungerichtete Bäume, das sind solche Graphen, die natürlich 15:58.640 --> 16:02.920 ungerichtet sind und zusammenhängend sind und keinen Kreis haben. 16:03.040 --> 16:05.020 Also die dürfen keinen Kreis haben. 16:06.280 --> 16:12.300 Und zusammenhängend bedeutet, dass ich von jedem Knoten zu jedem 16:12.300 --> 16:13.500 anderen Knoten kommen kann. 16:16.500 --> 16:18.520 Und manchmal haben die auch eine Wurzel. 16:19.520 --> 16:23.800 Und eine Wurzel ergibt vor allem Sinn bei gerichteten Graphen, bei 16:23.800 --> 16:24.400 ungerichteten. 16:26.200 --> 16:30.760 Dann gibt es halt einen Knoten, von dem ich zu allen anderen komme. 16:31.020 --> 16:33.340 Aber wenn es zusammenhängt, ist das ja schon klar. 16:33.900 --> 16:35.900 Ich kann dann vor allem einen als Wurzel bestimmen. 16:36.460 --> 16:40.460 Und das ist dann vor allem eine Auszeichnungssache. 16:41.580 --> 16:43.860 Dann gibt es gerichtete Bäume. 16:44.980 --> 16:48.440 Und das sind halt im Prinzip die selben Bedingungen erstmal. 16:48.600 --> 16:52.820 Die müssen zykelfrei sein und außerdem zusammenhängend. 16:54.080 --> 16:58.780 Und dann gibt es bei gerichteten Graphen nochmal Unterscheidungen. 16:58.840 --> 17:00.780 Stark zusammenhängend oder schwach zusammenhängend. 17:00.860 --> 17:03.000 Schwach zusammenhängend bedeutet einfach, wenn der zugehörige 17:03.000 --> 17:05.520 ungerichtete Graph zusammenhängt ist. 17:05.720 --> 17:08.160 Und stark zusammenhängend bedeutet, es gibt irgendwo eine Wurzel. 17:08.160 --> 17:13.860 Und von dieser Wurzel aus kann ich an alle anderen Knoten rankommen. 17:14.980 --> 17:15.880 Also mit einem Pfad. 17:17.160 --> 17:19.340 Manchmal ist es auch günstig, das halt umgekehrt zu schreiben. 17:19.440 --> 17:21.220 Dass ich halt zu der Wurzel hinkomme. 17:22.180 --> 17:26.960 Und das ist jetzt vielleicht noch so ein bisschen ein schräges 17:26.960 --> 17:27.900 Beispiel für einen Baum. 17:28.500 --> 17:29.700 Das ist so ein Berechnungsbaum. 17:31.140 --> 17:35.400 Und der hat eine etwas besondere Eigenschaft. 17:36.260 --> 17:41.320 Und zwar, wenn der jetzt so einen algebraischen Term in der 17:41.320 --> 17:47.180 naheliegenden Weise veranschaulichen soll, dann gibt es da eine 17:47.180 --> 17:51.680 Besonderheit, die durch unsere Modellierung von Graphen als Relationen 17:51.680 --> 17:53.080 eigentlich nicht so richtig abgefangen wird. 17:54.560 --> 17:55.060 Sieht es jemand? 18:06.470 --> 18:08.110 Okay, also wenn man mal hinguckt. 18:08.430 --> 18:11.230 Also angenommen, ich möchte wirklich so einen algebraischen Term 18:11.230 --> 18:11.670 berechnen. 18:11.670 --> 18:15.510 Der wäre dann halt a plus und dann in Klammern, oder naja, das ist ja 18:15.510 --> 18:18.430 Punkt -vor-Strich-Richtung, da brauchen wir das nicht, zwei geteilt 18:18.430 --> 18:18.870 durch b. 18:19.610 --> 18:24.430 Dann würde sich jetzt was ändern, wenn wir hier b geteilt durch zwei 18:24.430 --> 18:24.930 stehen haben. 18:25.010 --> 18:28.150 Das heißt, wenn sich hier die Reihenfolge verändert, dann verändert 18:28.150 --> 18:30.210 sich auch das, was wir üblicherweise damit machen. 18:31.090 --> 18:34.630 Also in dem Fall wäre das halt einfach ein anderer algebraischer 18:34.630 --> 18:35.090 Ausdruck. 18:36.630 --> 18:40.650 Und dann muss man sich halt überlegen, wenn man diesen Graphen 18:40.650 --> 18:45.410 darstellt im Programm irgendwie, dann muss man sicherstellen, dass 18:45.410 --> 18:48.770 halt hier in dem Fall die Knoten eine bestimmte Reihenfolge haben. 18:48.990 --> 18:50.810 Also man kann es auf verschiedene Weisen lösen. 18:51.450 --> 18:56.970 Man kann halt die Vorgänger oder Nachfolger von einem Knoten in einer 18:56.970 --> 19:01.310 bestimmten Reihenfolge speichern oder sich sonst irgendwas überlegen. 19:01.310 --> 19:05.030 Aber man sollte halt darauf achten, also man sollte sich dessen vor 19:05.030 --> 19:07.570 allem bewusst sein, dass hier irgendwas Komisches passieren kann. 19:15.920 --> 19:21.560 Zur Illustration von Graphen gucken wir uns jetzt als erstes mal einen 19:21.560 --> 19:24.820 Algorithmus an, also um auch insbesondere nochmal ein bisschen die 19:24.820 --> 19:28.320 Konzepte Pseudocode und Invariante zu üben sozusagen. 19:29.460 --> 19:31.600 Nicht erschrecken, das sieht erstmal vielleicht ein bisschen komisch 19:31.600 --> 19:31.960 aus. 19:31.960 --> 19:35.660 Was die Motivation von dem Algorithmus ist, was wollen wir überhaupt 19:35.660 --> 19:36.000 machen? 19:36.280 --> 19:37.400 Vielleicht fangen wir damit mal an. 19:39.000 --> 19:42.720 Der Algorithmus sagt mir, wenn ich einen Graph gegeben habe, der jetzt 19:42.720 --> 19:46.580 gegeben ist durch seine Knoten- und Kantenmenge, also V für Vertices 19:46.580 --> 19:52.660 für Knoten und E für Edges für die Kanten, dann sagt er mir, ob das, 19:52.860 --> 19:58.240 was ich da habe, überhaupt ein DAG ist, also ein gerichteter a 19:58.240 --> 19:59.120 -zyklischer Graph. 20:00.400 --> 20:04.300 Und das wird so als Test sehr nützlich sein für einen Augenblick. 20:05.560 --> 20:11.280 In gewisser Weise vereinfachen wir uns das Ganze jetzt nochmal, indem 20:11.280 --> 20:15.200 wir sagen, wie das repräsentiert ist, diese Knoten- und Kantenmenge 20:15.200 --> 20:15.880 und diese Operation. 20:16.400 --> 20:17.800 Das ist jetzt für einen Augenblick mal nicht wichtig. 20:18.020 --> 20:20.820 Also was der Algorithmus tut, sollte klar sein. 20:22.100 --> 20:24.340 Zumindest syntaktisch sollte es erstmal klar sein. 20:24.340 --> 20:28.240 Also wie gesagt, die Frage ist, ist das, was ich hier habe, ist das 20:28.240 --> 20:31.480 ein Directed acyclic Graph? 20:31.640 --> 20:34.500 Und im Prinzip das Problem ist eigentlich nur noch herauszufinden, ob 20:34.500 --> 20:35.440 der Zyklen hat. 20:35.840 --> 20:37.840 Denn dass er gerichtet ist, das sollte eigentlich schon an der 20:37.840 --> 20:38.880 Datenstruktur klar sein. 20:41.240 --> 20:45.980 Und das Ganze, was hier passiert, ist zunächst mal etwas sehr 20:45.980 --> 20:46.480 Einfaches. 20:46.540 --> 20:52.140 Ich gucke, in diesem Graphen gibt es einen Knoten, also einen Vertex 20:52.140 --> 20:58.700 in V, das einen Ausgangsgrad von 0 hat, also wo keine Kanten von 20:58.700 --> 20:59.180 rausgehen. 21:00.380 --> 21:05.540 Und wenn ja, dann die Invariante ignorieren wir mal kurz, dann 21:05.540 --> 21:06.620 streiche ich den raus. 21:07.120 --> 21:12.020 Und was das bedeutet ist, ich werde die Knotenmenge als erstes mal um 21:12.020 --> 21:17.140 diesen Knoten hier erleichtern und anschließend alle die Kanten 21:17.140 --> 21:19.540 rausstreichen, die eine Verbindung zu diesem Knoten hatten. 21:19.540 --> 21:24.080 Also das sind natürlich nur noch die Kanten, die in diesen Knoten 21:24.080 --> 21:27.500 reingehen, denn ausgehende Kanten hat er ja nicht gehabt, das war ja 21:27.500 --> 21:29.040 gerade hier die Aussage. 21:30.460 --> 21:33.440 Und am Ende, naja, wenn ich dann so lange weggestrichen habe, bis 21:33.440 --> 21:37.980 nichts mehr übrig ist, dann sage ich, okay, fertig und dann gebe ich 21:37.980 --> 21:40.180 halt eine 1 aus oder ein Ja oder ein True. 21:41.360 --> 21:44.540 Also das, was hier steht, das ist keine Zuweisung, sondern das ist 21:44.540 --> 21:48.180 halt ein Prädikat, das sagt halt einfach, entweder das ist so oder 21:48.180 --> 21:49.420 nicht, das ist ein Ja oder Nein. 21:51.060 --> 21:57.840 Und wenn es keinen Knoten mehr gibt, der diesen Ausgangsgrad Null hat 21:57.840 --> 22:01.860 und der Graph ist noch da, da sind noch Dinge übrig geblieben, dann 22:01.860 --> 22:04.280 sage ich, okay, hier gibt es einen Kreis. 22:06.180 --> 22:11.580 Und wie kann man sich jetzt überhaupt an diesen Algorithmus ranwagen? 22:11.740 --> 22:14.900 Also eine Möglichkeit ist, indem wir hier eine Invariante angeben und 22:14.900 --> 22:19.920 die Invariante ist, dass der Algorithmus durch unsere Aktion, so einen 22:19.920 --> 22:23.720 Knoten wegzustreichen, die Eigenschaft, ob ein Deck ist oder nicht, 22:24.180 --> 22:25.740 nicht verliert oder nicht gewinnt. 22:25.880 --> 22:27.060 Also wir ändern dadurch nichts. 22:29.540 --> 22:32.180 Und, naja, wie könnte man das einsehen? 22:32.720 --> 22:38.560 Also, wenn ich einen Graphen habe, der einen Kreis hatte und ich 22:38.560 --> 22:43.160 streiche dann Knoten mit Ausgangsgrad Null weg, dann wird das, was da 22:43.160 --> 22:45.780 rauskommt, immer noch ein Graph sein, der einen Kreis hat. 22:46.280 --> 22:50.820 Also die Argumentation ist so, für den Kreis sind ja nur die Knoten 22:50.820 --> 22:52.880 wichtig, die auch Teil dieses Kreises sind. 22:53.140 --> 22:56.540 Also die während einem Pfad, der halt einmal im Kreis geht, vorkommen. 22:57.340 --> 23:00.480 Und auf so einem Pfad kann aber der Knoten, den ich rausstreiche, 23:00.520 --> 23:01.000 nicht liegen. 23:02.260 --> 23:05.960 Denn jeder Knoten in einem Kreis, der muss mindestens mal einen 23:05.960 --> 23:09.040 Ausgangsgrad und natürlich auch einen Eingangsgrad von mindestens mal 23:09.040 --> 23:09.580 eins haben. 23:10.700 --> 23:11.260 Okay? 23:14.310 --> 23:18.150 Und natürlich ein Knoten, der vorher keinen Kreis hatte, der wird auch 23:18.150 --> 23:20.450 keinen Kreis dadurch kriegen, dass ich da Knoten wegstreiche. 23:21.250 --> 23:23.750 Also die Invariante ist erfüllt. 23:24.590 --> 23:27.430 Und vielleicht Übung. 23:28.450 --> 23:32.790 Die Frage ist jetzt, wenn ich am Ende also einen leeren Graphen habe, 23:33.490 --> 23:37.670 wie kann ich denn daraus dann auch schließen, also wenn der Graph leer 23:37.670 --> 23:40.810 ist, bedeutet das natürlich insbesondere, dass der ursprüngliche Graph 23:40.810 --> 23:41.630 keinen Kreis hatte. 23:42.850 --> 23:47.210 Aber was ist denn, wenn der ursprüngliche Graph einen Kreis hatte, 23:47.630 --> 23:50.670 warum komme ich denn dann nie bei der... 23:50.670 --> 23:51.950 Oder war das jetzt richtig? 23:52.290 --> 23:52.810 Mal überlegen. 23:54.010 --> 23:55.710 Also es müssen natürlich zwei Dinge erfüllt sein. 23:55.790 --> 23:58.590 Wenn der ursprüngliche Graph einen Kreis hatte, dann darf ich hier 23:58.590 --> 23:59.750 nicht bei der leeren Menge ankommen. 24:00.790 --> 24:02.450 Und das ist eigentlich der einfache Fall. 24:02.670 --> 24:10.250 Denn dann gibt es ja in diesem Kreis offenbar Knoten, welche diesen 24:10.250 --> 24:12.310 Kreis nicht wegstreichen können hierdurch, da ich den Kreis nie 24:12.310 --> 24:12.810 antaste. 24:15.070 --> 24:19.330 Und der interessante Fall ist, wenn der Graph keinen Kreis hatte, 24:19.410 --> 24:21.910 warum komme ich dann wirklich bei der leeren Menge an? 24:22.130 --> 24:23.930 Also das ist dann der interessantere Teil. 24:24.190 --> 24:25.810 Also das ist wie gesagt dann eine kleine Übung. 24:27.210 --> 24:29.810 Zur Analyse, wie lange dauert es? 24:30.610 --> 24:36.090 Die erste Idee, wie man das implementieren könnte, vielleicht mit 24:36.090 --> 24:40.530 Adjacenzmatrizen oder so, also eine naive Implementierung, die käme 24:40.530 --> 24:43.450 auf mindestens mal einen Aufwand, der quadratisch ist von diesem 24:43.450 --> 24:46.770 gesamten Algorithmus in der Größe der Knoten und der Kanten. 24:47.150 --> 24:49.890 Aber wenn man da ein bisschen aufpasst, und das werden wir uns nochmal 24:49.890 --> 24:55.090 ein bisschen genauer angucken, später bei dem Graphenkapitel, da kann 24:55.090 --> 24:57.350 man ein bisschen optimieren und da kommt man tatsächlich auf eine 24:57.350 --> 24:58.150 lineare Laufzeit. 24:58.150 --> 25:03.290 Das heißt, man kann in lineare Laufzeit feststellen, ob ein Graph 25:03.290 --> 25:04.710 einen Kreis hat oder nicht. 25:06.510 --> 25:11.150 Okay, so abstrakt erstmal Fragen. 25:11.950 --> 25:14.430 Also es gibt jetzt direkt anschließend noch ein Beispiel zu dem 25:14.430 --> 25:14.970 Algorithmus. 25:15.230 --> 25:16.710 Aber gibt es vielleicht noch Fragen? 25:21.980 --> 25:24.760 Okay, also hier ist ein Beispiel. 25:26.380 --> 25:29.240 Das hier wäre ein Beispielgraph. 25:31.220 --> 25:33.720 Und jetzt gucken wir halt, das oben ist der Algorithmus, das ist nur 25:33.720 --> 25:35.000 kopiert, ohne die Invariante. 25:35.880 --> 25:37.180 Und jetzt gucken wir halt mal, was der macht. 25:37.540 --> 25:41.060 Und naja, jetzt hat man am Anfang im Prinzip erstmal die Frage, gibt 25:41.060 --> 25:45.160 es hier einen Knoten, der hat einen Ausgangsgrad 0. 25:45.540 --> 25:47.380 Und da gibt es jetzt im Prinzip mehrere Kandidaten. 25:47.540 --> 25:49.960 Also der hier wäre gerade ein schlechter Kandidat, der hat sogar einen 25:49.960 --> 25:50.840 Ausgangsgrad 2. 25:52.160 --> 25:53.920 Aber zum Beispiel der hier wäre ein Kandidat. 25:54.340 --> 25:56.100 Oder der da. 25:56.640 --> 25:58.280 Also ich glaube, wir fangen oben an. 25:58.280 --> 25:59.900 Ne, wir fangen in der Mitte an. 26:01.600 --> 26:05.600 Also der erste Schritt könnte dann dieser hier sein, je nachdem, ist 26:05.600 --> 26:06.440 eigentlich egal welcher. 26:08.020 --> 26:11.280 Der zweite könnte dann diesen Knoten hier entfernen. 26:12.760 --> 26:14.780 Und so arbeitet man sich dann weiter vor. 26:14.880 --> 26:17.980 Und das Wichtige ist, oder die Beobachtung ist eigentlich, dadurch, 26:18.140 --> 26:21.140 dass ich zum Beispiel diesen Knoten hier entferne, habe ich auf einmal 26:21.140 --> 26:24.620 neue Knoten generiert, die vorher noch einen Ausgangsgrad haben. 26:24.680 --> 26:27.480 Der war größer als 0, aber die haben jetzt einen Ausgangsgrad, der ist 26:27.480 --> 26:27.680 0. 26:27.680 --> 26:30.400 Einfach weil dieser Pfeil hier zum Beispiel wegfällt. 26:31.900 --> 26:33.680 Und deshalb kann ich die, die jetzt noch übrig bleiben, alle 26:33.680 --> 26:34.780 schrittweise entfernen. 26:37.060 --> 26:39.900 Und so geht es immer weiter, bis ich irgendwann nur noch einen Knoten 26:39.900 --> 26:40.080 habe. 26:40.200 --> 26:43.980 Der hat dann natürlich auch keine ausgehende Kante mehr. 26:45.260 --> 26:48.620 Und dann bin ich beim leeren Graph und dann gibt es natürlich keinen 26:48.620 --> 26:50.850 Knoten mehr mit Ausgangsgrad 0. 26:51.380 --> 26:52.540 Es gibt überhaupt keinen Knoten mehr. 26:52.660 --> 26:55.980 Und deshalb kann ich diese While-Schleife verlassen und bin fertig. 26:55.980 --> 26:59.460 Und gebe dann natürlich True zurück. 27:00.960 --> 27:03.400 Also das als Beispiel. 27:07.920 --> 27:13.600 Eine Folie ganz kurz zu Komplexitätstheorie oder Dingen, die an 27:13.600 --> 27:15.020 Komplexitätstheorie angrenzen. 27:15.840 --> 27:19.700 P und NP haben Sie auch schon kennengelernt, aber wird sich nochmal 27:19.700 --> 27:25.020 sehr viel genauer angeguckt im nächsten Semester in den theoretischen 27:25.020 --> 27:25.660 Grundlagen. 27:29.800 --> 27:35.200 Und was für uns jetzt vielleicht wichtig ist, ist P und NP, das sind 27:35.200 --> 27:37.500 erstmal so abstrakte Begriffe, die kann man mit Turing-Maschinen 27:37.500 --> 27:38.000 definieren. 27:38.440 --> 27:44.460 Aber für uns, was wir wichtig daraus ziehen ist, dass wir polynomielle 27:44.460 --> 27:49.200 Laufzeit oder Algorithmen mit polynomieller Laufzeit mit effizienten 27:49.200 --> 27:50.540 Algorithmen identifizieren. 27:50.640 --> 27:53.260 Zumindest mal auf so einer abstrakten Ebene. 27:53.260 --> 27:55.840 Also da kann man jetzt natürlich auch sagen, das ist Unsinn. 27:57.260 --> 28:00.320 Je nachdem, was polynomiell bedeutet, polynomiell in der Eingabelänge, 28:00.360 --> 28:03.120 also natürlich meine ich polynomiell in der Eingabelänge, aber je 28:03.120 --> 28:07.240 nachdem, was für ein Polynom das genau ist, das kann natürlich eine 28:07.240 --> 28:11.300 unglaubliche Laufzeit haben, wenn da eine multiplikative oder auch nur 28:11.300 --> 28:14.380 additive Konstante mit 2 hoch 1000 ist, will das niemand 28:14.380 --> 28:15.140 implementieren. 28:15.840 --> 28:20.360 Aber es gibt tatsächlich theoretische und praktische Gründe, das 28:20.360 --> 28:22.420 trotzdem irgendwie zu identifizieren. 28:22.420 --> 28:27.060 Ein theoretischer Grund ist, naja, das verhält sich gut, das ist eine 28:27.060 --> 28:28.960 gute Klasse für uns, die ist handlich. 28:29.320 --> 28:31.360 Aber das ist vielleicht noch nicht so motivierend. 28:32.240 --> 28:35.020 Und ein anderer Grund ist, es hat sich herausgestellt, dass die 28:35.020 --> 28:39.420 Algorithmen, die tatsächlich eine polynomielle Laufzeit haben, in den 28:39.420 --> 28:43.060 allermeisten Fällen auch effizient im intuitiven Sinne sind. 28:43.280 --> 28:47.180 Also die Implementierung, die man da anguckt, die sind auch wirklich 28:47.180 --> 28:49.080 so, dass man den dann laufen lassen kann. 28:49.080 --> 28:51.940 Es gibt vielleicht ein paar Ausnahmen. 28:52.060 --> 28:55.300 Eine Ausnahme ist ein deterministischer Prim-Test. 28:55.500 --> 28:58.640 Also es gibt probabilistische Prim-Test-Algorithmen, aber es gibt 28:58.640 --> 29:07.160 insbesondere seit 12 oder 13 Jahren einen deterministischen Test, der 29:07.160 --> 29:11.100 gegeben eine Zahl in Binärdarstellung sagt, ob das eine Primzahl ist 29:11.100 --> 29:11.480 oder nicht. 29:12.120 --> 29:18.300 Und der hat tatsächlich immer noch eine Laufzeit von N hoch 4,5 oder 4 29:18.300 --> 29:19.320 ,55, sowas. 29:20.520 --> 29:22.920 Am Anfang war das N hoch 13 und dann wurde das halt schrittweise 29:22.920 --> 29:24.000 besser gemacht. 29:26.540 --> 29:29.320 Und der ist tatsächlich so, dass man den auch nicht verwenden würde, 29:29.440 --> 29:31.840 sondern stattdessen gibt es viel schnellere probabilistische Prim 29:31.840 --> 29:32.220 -Tests. 29:33.160 --> 29:37.640 Aber in den allermeisten Fällen wird es so sein, dass das Polynomielle 29:37.640 --> 29:41.800 auch tatsächlich für uns effizient bedeutet. 29:43.380 --> 29:49.220 Es gibt viele Probleme, von denen wir glauben, dass sie in NP liegen, 29:49.320 --> 29:51.880 aber nicht in P. Also eigentlich glauben wir schon, dass P ungleich NP 29:51.880 --> 29:53.120 ist, aber wir können es nicht zeigen. 29:54.020 --> 29:57.020 Und im gewissen Sinne kann man das noch so quantifizieren, dass man 29:57.020 --> 30:02.040 sagt, dass es sehr überraschend wäre, wenn diese Probleme in P liegen 30:02.040 --> 30:02.360 würden. 30:03.120 --> 30:05.600 Also das wäre deshalb überraschend, weil wenn man die lösen könnte 30:05.600 --> 30:08.120 effizient, dann könnte man auch noch eine viel größere Klasse von 30:08.120 --> 30:09.060 Problemen lösen. 30:09.060 --> 30:13.000 Dann würden bestimmte Komplexitätsklassen, ganze Hierarchien von 30:13.000 --> 30:15.020 Komplexitätsklassen kollabieren. 30:15.760 --> 30:18.580 Und das wäre einfach zu überraschend im Augenblick. 30:18.840 --> 30:19.840 Aber man kann es nicht beweisen. 30:20.800 --> 30:25.520 Aber wie gesagt, für uns im Augenblick nicht sehr wichtig, sondern nur 30:25.520 --> 30:29.000 mal um es angesprochen zu haben und vor allem dieses Polynomielle und 30:29.000 --> 30:29.820 Effizient zu klären. 30:29.940 --> 30:32.860 Also wenn man Polynomielle sagt, dann für uns bedeutet es auch dann 30:32.860 --> 30:33.800 Effizient. 30:35.020 --> 30:38.400 Okay, das waren die Vereinbarungen. 30:38.400 --> 30:41.920 Jetzt kommen wir zu den Datenstrukturen. 30:42.880 --> 30:44.620 Also jetzt gucken wir uns erstmal so ein paar elementare 30:44.620 --> 30:48.740 Datenstrukturen an, die wir immer wieder brauchen werden, um 30:48.740 --> 30:51.880 komplexere Datenstrukturen zu bauen oder auch in den Algorithmen 30:51.880 --> 30:53.020 geeignet zu gebrauchen. 30:54.740 --> 31:00.220 Und dazu gibt es vielleicht ein ganz nettes Bild oder zwei Bilder 31:00.220 --> 31:02.500 eigentlich und eine Geschichte. 31:04.120 --> 31:09.480 Und zwar ist es so, das sind Beispiele für eine der ältesten oder 31:09.480 --> 31:13.220 vielleicht sogar die ältesten Datenstrukturen, von denen man so weiß. 31:14.180 --> 31:16.960 Und das linke, das ist eine Keilschrift, die ist ca. 31:17.020 --> 31:22.760 5000 Jahre alt und die hat man in sumerischen oder vorsumerischen 31:22.760 --> 31:23.530 Tempeln ausgegraben. 31:25.200 --> 31:32.040 Und was da gemacht wurde ist, also man vermutet, dass das so eine Art 31:32.040 --> 31:35.520 Steuerkonten sind für die damalige Zeit. 31:36.300 --> 31:40.300 Also schon damals gab es Steuern und manche Leute haben vielleicht ein 31:40.300 --> 31:42.900 bisschen mehr bezahlt, manche ein bisschen weniger und das war auch 31:42.900 --> 31:44.200 vieles in Naturalien natürlich. 31:45.200 --> 31:48.540 Und dann wurde hier festgehalten, wer was bezahlt hat. 31:50.020 --> 31:53.840 Und das war im Prinzip dann, so konnte man schnell gucken, der Fred 31:53.840 --> 31:57.340 hat dieses Jahr oder letztes Jahr vielleicht weniger bezahlt, er 31:57.340 --> 31:59.360 bezahlt dieses Jahr vielleicht ein bisschen mehr und so konnte man 31:59.360 --> 32:01.180 dann so ein bisschen Buch führen und Haus halten. 32:02.480 --> 32:05.240 Also das Instrument für Steuereintreiber. 32:06.620 --> 32:12.560 Aber das war vielleicht nicht das handlichste Instrument für 32:12.560 --> 32:16.020 Steuereintreiber, denn wenn man da von Dorf zu Dorf geht, dann will 32:16.020 --> 32:18.420 man ja vielleicht nicht diese ganzen Platten damit sich rumschleppen. 32:19.360 --> 32:22.000 Obwohl die vielleicht ziemlich übersichtlich sind, wenn man sie einmal 32:22.000 --> 32:22.580 vor sich hat. 32:23.420 --> 32:28.440 Also hat man das gefunden, das hängt natürlich damit nicht zusammen, 32:28.720 --> 32:33.280 aber man hat damals noch ein anderes Instrument benutzt, um ähnliche 32:33.280 --> 32:35.600 Dinge, naja, Buch zu halten. 32:36.300 --> 32:43.060 Und das ist so eine Art Kordel, wo dann so Seile von abgehen wieder. 32:45.220 --> 32:48.000 Und der Grundgedanke ist ganz ähnlich. 32:48.100 --> 32:49.100 Man kann da Dinge zählen. 32:49.260 --> 32:53.460 Also man kann zum einen mal diese Unterstränge da zählen und am Iden 32:53.460 --> 32:57.160 -Unterstrang kann man dann nochmal Knoten reinmachen und vielleicht 32:57.160 --> 32:59.780 auch Knoten von verschiedener Form, die verschiedene Zahlen ausdrücken 32:59.780 --> 33:01.900 und so in gewisser Weise auch Buch führen. 33:02.980 --> 33:05.400 Die sind aber jetzt nicht ganz so übersichtlich hier. 33:09.340 --> 33:12.740 Diese Kordeldatenstruktur ist nicht so übersichtlich und sie erlaubt 33:12.740 --> 33:14.420 vielleicht auch nicht dieselben Operationen. 33:14.560 --> 33:17.140 Naja gut, wenn links der Lehm einmal trocken ist, dann wird es 33:17.140 --> 33:18.020 vielleicht auch schwieriger. 33:19.420 --> 33:21.720 Aber rechts die Operationen sind vielleicht andere. 33:21.820 --> 33:26.240 Da kann ich vielleicht noch anfügen, aber das dann wieder aufzuknoten 33:26.240 --> 33:26.940 wird auch schwierig. 33:28.800 --> 33:32.700 Okay, also im Prinzip haben wir hier so eine mobile und eine nicht so 33:32.700 --> 33:36.560 mobile Datenstruktur, die in beiden Fällen genutzt wurden, um 33:36.560 --> 33:38.180 irgendwelche Informationen abzulegen. 33:38.720 --> 33:40.300 Und eigentlich wird es bei uns auch nicht anders sein. 33:40.300 --> 33:43.500 Also wir werden uns jetzt als nächstes zwei verschiedene 33:43.500 --> 33:48.300 Datenstrukturen angucken, die im Wesentlichen dieselben Informationen 33:48.300 --> 33:52.420 oder dieselben Arten von Informationen abspeichern, aber die halt 33:52.420 --> 33:53.780 unterschiedliche Eigenschaften haben. 33:54.440 --> 33:58.580 Also insbesondere was den Zugriff angeht und die Handhabung. 34:00.340 --> 34:04.560 Okay, was wollen wir darstellen? 34:05.180 --> 34:07.740 Im allgemeinsten Fall sind das bei uns einfach mal Folgen. 34:07.740 --> 34:12.440 Also mathematisch sind damit Zahlenfolgen gemeint, so wie Sie sie auch 34:12.440 --> 34:15.580 kennen aus der höheren Mathematik oder der Analysis. 34:17.780 --> 34:23.840 Und es gibt aber je nachdem, was wir damit machen können und wie wir 34:23.840 --> 34:28.860 sie denn abspeichern, gibt es unterschiedliche Darstellungen von 34:28.860 --> 34:29.220 Folgen. 34:29.720 --> 34:33.020 Also im Prinzip das, was hier steht, das sind alles verschiedene 34:33.020 --> 34:40.020 Mittel oder verschiedene Arten, wie man eine Folge darstellen kann. 34:40.160 --> 34:43.040 Also ein Array, das werden wir uns noch später angucken, oder ein 34:43.040 --> 34:43.340 Feld. 34:44.860 --> 34:48.160 Also das kennen Sie sicherlich auch schon, eine Schlange, eine 34:48.160 --> 34:49.880 Warteschlange oder eine Liste. 34:50.120 --> 34:52.420 Und das gucken wir uns jetzt als direkt nächstes an. 34:53.060 --> 34:56.160 Oder wir können auch eine geordnete Folge von Zahlen, also nicht nur 34:56.160 --> 34:58.360 eine Menge, sondern da ist auch eine Ordnung drauf. 34:58.980 --> 35:03.180 Können wir auch als letztlich Stapel oder womöglich nur als Datei 35:03.180 --> 35:03.680 darstellen. 35:03.680 --> 35:07.620 Und von diesen Dingen gucken wir uns ein paar noch genauer an, also 35:07.620 --> 35:09.840 insbesondere Liste, Feld, Stapel und Schlange. 35:11.200 --> 35:14.240 Aber man sollte im Hinterkopf haben, dass man unterscheidet, im 35:14.240 --> 35:16.940 Prinzip sind das ähnliche Daten, die man damit speichert, aber man 35:16.940 --> 35:19.760 unterscheidet diese Dinge noch bezüglich der Dinge, die ich damit 35:19.760 --> 35:21.900 machen kann und wie ich sie abspeichere. 35:24.710 --> 35:26.790 Okay, soweit Fragen? 35:27.730 --> 35:32.250 Denn wenn nicht, würden wir dann direkt schon zum ersten Datentyp 35:32.250 --> 35:32.490 kommen. 35:36.980 --> 35:39.740 Achso, ja, wofür braucht man Folgen? 35:40.200 --> 35:46.700 Das ist so universell, dass man da gar nichts genaueres sagen müsste. 35:47.380 --> 35:50.460 Aber eine wichtige Sache ist, man hat entweder die direkte Anwendung 35:50.460 --> 35:56.040 oder man hat solche Datenstrukturen wie Folgen oder die Darstellung 35:56.040 --> 36:00.520 von Folgen, wenn man andere Datenstrukturen, die komplexer sind, zum 36:00.520 --> 36:04.480 Beispiel Graphen oder Mengen, wenn man die darstellen möchte. 36:04.480 --> 36:07.740 Also dann wird das ein guter Baustein sein und vor allem deshalb 36:07.740 --> 36:08.680 unterhalten wir uns auch. 36:13.380 --> 36:17.940 Wir haben also diese vier genaueren Datenstrukturen, die wir uns 36:17.940 --> 36:18.280 angucken. 36:18.380 --> 36:19.740 Das sind zwei Varianten von Listen. 36:20.360 --> 36:23.760 Das ist, genauer gesagt, eine doppelt verzeigerte Liste oder eine 36:23.760 --> 36:25.400 einfach verzeigerte Liste. 36:26.020 --> 36:28.220 Und dann haben wir noch zwei verschiedene Darstellungen von einem 36:28.220 --> 36:28.720 Array. 36:28.960 --> 36:31.020 Eins, das wachsen kann oder eins, das zyklisch ist. 36:31.880 --> 36:34.460 Und dann hat man verschiedene Operationen. 36:34.460 --> 36:38.120 Und im Augenblick geht es gar nicht darum, das Diagramm genauer zu 36:38.120 --> 36:42.040 verstehen, sondern das wird hoffentlich noch später klar werden, wenn 36:42.040 --> 36:43.060 wir uns das genauer angucken. 36:43.180 --> 36:47.380 Das sind die Kosten jeweils für verschiedene Operationen hier in der 36:47.380 --> 36:50.240 Spalte mit einer doppelt verzeigerten Liste. 36:51.440 --> 36:56.900 Und was würde ich vom grundsätzlichen Vorgehen, was würde ich denn 36:56.900 --> 36:58.300 haben wollen, können? 36:59.000 --> 37:01.200 Also natürlich Zugriff, das hier bedeutet Zugriff. 37:01.200 --> 37:06.560 Ich möchte die Größe von dieser Liste oder von der Folge herausfinden. 37:07.040 --> 37:08.960 Zugriff auf das erste, auf das letzte Element. 37:09.100 --> 37:12.200 Ich möchte Dinge einfügen können, wieder rausnehmen können. 37:13.380 --> 37:17.700 Am Ende einfügen, am Anfang einfügen, am Ende rausnehmen, am Anfang 37:17.700 --> 37:18.220 rausnehmen. 37:18.760 --> 37:21.480 Und vielleicht möchte ich noch zwei, drei andere Dinge machen können. 37:22.880 --> 37:27.160 Und das einzig Wichtige an der Folie ist eigentlich, dass Sie sehen, 37:27.740 --> 37:31.800 je nachdem, was Sie für Operationen später haben, ist es vielleicht 37:31.800 --> 37:34.900 günstiger, den einen oder den anderen Datentyp zu haben. 37:35.100 --> 37:37.940 Also es gibt hier keinen klaren Gewinner, wenn Sie so wollen, sondern 37:37.940 --> 37:41.440 das sind alles so Abstriche, die man machen muss an gewissen Stellen. 37:42.040 --> 37:49.920 Und das Wichtige ist, es gibt hier keine Patentlösung, sondern von der 37:49.920 --> 37:54.200 Anwendung, wie Sie es später gebrauchen, hängt davon ab, was für 37:54.200 --> 37:55.280 Operationen Sie haben wollen. 37:55.700 --> 37:58.680 Also davon hängt ab, welche Datenstruktur für Sie vielleicht am 37:58.680 --> 37:59.440 günstigsten ist. 38:01.200 --> 38:08.220 Okay, also jetzt geht es dann los mit den doppelt verketteten Listen. 38:09.900 --> 38:13.200 Und das drückt schon so ein bisschen aus, dass wir einzelne 38:13.200 --> 38:18.580 Listenglieder oder Listenelemente haben und die sind dann irgendwie 38:18.580 --> 38:19.420 zusammengefügt. 38:19.420 --> 38:22.100 Und was das konkret bedeutet ist, wir können uns das vorstellen als 38:22.100 --> 38:22.600 eine Klasse. 38:23.620 --> 38:32.300 Das wäre die Klasse zunächst mal von einem einzelnen Listenglied und 38:32.300 --> 38:37.960 auf dieses Listenglied haben wir dann auch einen Zeiger. 38:38.120 --> 38:39.860 Also Handle ist nichts anderes als ein Zeiger. 38:40.900 --> 38:44.600 Und den Zeiger werden wir deshalb brauchen, weil wir halt bei doppelt 38:44.600 --> 38:47.340 verketteten oder doppelt verzeigerten Listen, da brauchen wir 38:47.340 --> 38:50.860 natürlich auch irgendeine Möglichkeit, diese Zeiger auszudrücken. 38:51.480 --> 38:55.780 Okay, also die Idee ist, diese Klasse hat erstmal die eigentliche 38:55.780 --> 38:59.260 Information, E ist das Element, also das sind die eigentlichen Daten, 38:59.520 --> 39:01.000 die wir repräsentieren wollen. 39:01.560 --> 39:05.600 Das könnte dann eine Zahl sein, wie viel derjenige oder diejenige 39:05.600 --> 39:12.460 bezahlt hat oder mit Daten, also mit Namen und alles drum und dran. 39:12.940 --> 39:15.400 Und dann gibt es hier, das ist vielleicht das Interessante, es gibt 39:15.400 --> 39:19.380 hier zwei Zeiger und zwar einen Zeiger next auf das nächste Element, 39:19.760 --> 39:22.740 auf den 39:25.930 --> 39:29.910 nächsten Listen-Eintrag und einen auf den vorherigen Listen-Eintrag. 39:30.650 --> 39:32.750 Also hier ist es vielleicht so ein bisschen grafisch dargestellt, da 39:32.750 --> 39:36.910 gibt es einmal die eigentliche Information, den Inhalt und dann halt 39:36.910 --> 39:43.030 diese beiden Zeiger in die Richtung nach vorne und nach hinten. 39:43.030 --> 39:46.270 Und die Elemente, die ja vor und danach kommen, die sollen dann 39:46.270 --> 39:47.850 natürlich auch entsprechend verzeigert sein. 39:48.370 --> 39:52.210 Also ich habe schon mal direkt so eine Kette hergestellt. 39:53.510 --> 39:56.210 Hier gibt es jetzt vielleicht das erste Mal, dass wir das sehen, eine 39:56.210 --> 39:59.630 Datenstruktur -Invariante und die soll sagen, solange das hier, was 39:59.630 --> 40:03.570 hier steht, erfüllt ist, das ist eine implizite Annahme erstmal, die 40:03.570 --> 40:07.250 ich mache, und solange ist die Datenstruktur für uns in Ordnung. 40:07.510 --> 40:10.750 Und wie drücken wir aus, dass diese Datenstruktur für uns in Ordnung 40:10.750 --> 40:10.970 ist? 40:11.650 --> 40:17.490 Naja, indem diese Verzeigerung konsistent ist. 40:17.970 --> 40:20.950 Also wenn ich ein Element nach vorne gehe und dann wieder eins zurück, 40:21.050 --> 40:23.970 dann lande ich wieder da, wo ich angefangen habe und umgekehrt. 40:26.810 --> 40:30.590 Okay, das ist auch, was man annehmen würde. 40:31.070 --> 40:32.430 Ein kleines Problem gibt es jetzt. 40:33.850 --> 40:38.930 Die Listen sind ja alle endlich und die Frage ist jetzt, was mache ich 40:38.930 --> 40:41.830 denn, wenn ich beispielsweise beim ersten Listen-Element angekommen 40:41.830 --> 40:42.650 bin oder beim letzten? 40:43.230 --> 40:47.410 Wenn ich dann noch weiter nach vorne gehe, also vor das erste Versuche 40:47.410 --> 40:50.770 zu gehen oder hinter das letzte, dann habe ich ja eigentlich, ja wo 40:50.770 --> 40:51.330 lande ich dann? 40:51.590 --> 40:55.330 Was müsste dann dieses Handle sein, was müsste dann dieser Zeiger 40:55.330 --> 40:55.610 sein? 40:56.410 --> 40:59.970 Eine Möglichkeit ist, man sagt, das ist halt sowas wie der Nullzeiger 40:59.970 --> 41:02.990 und dann schreibe ich halt hier sowas wie eine Null rein. 41:02.990 --> 41:07.370 Aber das ist für uns vielleicht ein bisschen unelegant. 41:07.810 --> 41:12.090 Also insofern unelegant, dann habe ich halt in diesen ganzen Methoden, 41:12.190 --> 41:16.310 die noch auf Listen arbeiten und das, was ich mit denen machen will, 41:16.350 --> 41:17.590 dann habe ich immer so eine Sonderbehandlung. 41:17.690 --> 41:23.210 Ich muss eigentlich erst gucken, ist beispielsweise Next oder Prev ist 41:23.210 --> 41:27.330 es Null und wenn ja, dann muss ich irgendeine Sonderbehandlung machen 41:27.330 --> 41:29.510 und wenn nein, dann mache ich halt das, was ich eigentlich machen 41:29.510 --> 41:29.770 wollte. 41:31.630 --> 41:35.590 Das ist eigentlich ganz günstig, wenn wir versuchen, das zu vermeiden. 41:36.170 --> 41:40.630 Und deshalb gibt es einen kleinen Trick und der ist, dass wir 41:40.630 --> 41:45.010 sozusagen ein extra Listen-Element haben, das wir Dummy-Header oder 41:45.010 --> 41:45.770 einfach Header nennen. 41:46.790 --> 41:51.970 Und dieses Header-Element, das ist ein Element, das hat halt ein, 41:52.270 --> 41:54.830 naja, kann man nennen, wie man will, eigentlich einen leeren 41:54.830 --> 41:55.770 Dateninhalt. 41:55.770 --> 42:04.030 Das trägt keine Daten, aber es kettet sozusagen das Ende und den 42:04.030 --> 42:05.330 Anfang von der Liste zusammen. 42:05.990 --> 42:10.310 Das heißt, das ist ein Element, was vor dem ersten eigentlichen Listen 42:10.310 --> 42:14.150 -Element steht und Next von diesem Header-Element zeigt auf das erste 42:14.150 --> 42:19.610 Listen -Element und umgekehrt wird das Ende der Liste, also diese 42:19.610 --> 42:25.410 Grafik ist zyklisch zu sehen, das Ende von der Liste, das wird mit 42:25.410 --> 42:28.250 diesem Header auf der anderen Seite verklebt. 42:30.090 --> 42:33.250 Okay, also für uns hat es ein paar Vorteile. 42:33.490 --> 42:35.990 Also insbesondere diese Invariante ist erfüllt, wir können einfach 42:35.990 --> 42:41.890 ausdrücken, wann wir eine Liste als okay sozusagen erachten, weil wir 42:41.890 --> 42:47.730 dieses Next da von der Zeiger-Pref, dass das wieder dasselbe sein 42:47.730 --> 42:51.970 soll, das ergibt dann jetzt vor allem mal Sinn. 42:52.270 --> 42:54.930 Also wenn wir die halt so verketten, dann ist die Liste tatsächlich 42:54.930 --> 42:56.230 zyklisch. 42:56.790 --> 43:00.710 Und vor allem, und das ist für uns jetzt auch im Folgenden noch ganz 43:00.710 --> 43:03.670 nützlich, wir vermeiden dann halt einfach solche Sonderfälle, dass wir 43:03.670 --> 43:08.090 testen müssen, ob wir jetzt beim letzten Listen-Element sind und das 43:08.090 --> 43:10.410 wird dann diese Fälle einfach wegfallen lassen. 43:10.610 --> 43:12.290 Das ist dann dadurch abgedeckt. 43:15.070 --> 43:18.010 Ein bisschen blöd ist, dass wir jetzt natürlich ein extra Listen 43:18.010 --> 43:23.270 -Element haben und das kann schon einen Unterschied machen, wenn wir 43:23.270 --> 43:27.230 sehr viele ansonsten kurze Listen haben von vielleicht einem Element 43:27.230 --> 43:30.170 und da haben wir ganz viele von und auf einmal blähe ich die dann 43:30.170 --> 43:32.210 jetzt mit einem extra Element, das wir nur für unsere 43:32.210 --> 43:34.490 Buchhaltungszwecke brauchen, blähe ich die auf. 43:35.310 --> 43:38.170 Kann blöd sein, im dümmsten Fall haben wir es dann verdoppelt, den 43:38.170 --> 43:40.510 Speicherverbrauch, oder womöglich, wenn wir ganz viele leere Listen 43:40.510 --> 43:41.270 haben, noch viel mehr. 43:43.750 --> 43:47.290 Aber für größere Listen fällt das natürlich immer weniger ins Gewicht. 43:49.030 --> 43:51.250 Okay, also muss man da natürlich auch abwägen, ob man das haben will 43:51.250 --> 43:53.270 und wenn nicht, muss man sich ein paar Sonderbehandlungen einfallen 43:53.270 --> 43:57.430 lassen, aber wir werden es aus mehreren Gründen einfach jetzt mit so 43:57.430 --> 43:58.370 einem Dummy-Element machen. 43:59.030 --> 44:01.490 Also das ist jetzt nicht der einzige Fall, wo so etwas auftritt, nicht 44:01.490 --> 44:03.930 nur bei Listen, sondern auch in anderen Fällen, wird man vielleicht 44:03.930 --> 44:09.870 dann mal so eine elegante Möglichkeit haben, etwas zu lösen und 44:09.870 --> 44:11.450 manchmal wird das vielleicht nur ein Hack sein. 44:11.690 --> 44:13.910 Also ob das jetzt ein Hack ist oder eine elegante Möglichkeit, etwas 44:13.910 --> 44:16.830 zu lösen, hängt auch immer von den Randbedingungen so ein bisschen ab. 44:18.410 --> 44:20.370 Okay, also Header-Element klar. 44:23.470 --> 44:27.110 Denn dann können wir eigentlich daran gehen, uns jetzt mal anzugucken, 44:27.210 --> 44:28.770 was man mit diesen Listen machen kann. 44:30.890 --> 44:33.710 Achso, hier ist noch ein Beispiel zu dem Dummy-Element. 44:33.710 --> 44:36.910 Jetzt wäre hier eine Liste, in der eigentlich die Elemente A, B, C 44:36.910 --> 44:41.250 stehen und dann haben wir halt diese Liste in der Reihenfolge A, dann 44:41.250 --> 44:45.750 B, dann C und dieses Header-Element steht halt auch noch da drin. 44:47.230 --> 44:49.790 Okay, also das Wichtige ist halt, diese Pfeile sind natürlich 44:49.790 --> 44:51.870 konsistent. 44:52.910 --> 44:54.950 Also wenn ich hier hingehe und dann wieder zurück, lande ich wieder 44:54.950 --> 44:56.090 beim Header-Element. 44:59.560 --> 45:04.960 Okay, das wäre dann unsere Klasse, die besteht für eine Liste. 45:04.960 --> 45:07.700 Also wir haben uns jetzt schon die Elemente von der Liste angeguckt, 45:07.780 --> 45:10.540 jetzt gucken wir uns die gesamte Liste an. 45:12.120 --> 45:15.560 Und das Wichtige ist, die hat dann so ein Element H, das ist dieses 45:15.560 --> 45:16.220 Header -Element. 45:18.260 --> 45:24.240 Das ist ein Element, das zeigt am Anfang zunächst mal auf sich selber. 45:24.420 --> 45:27.400 Also das hier wäre initialisiert erstmal eine leere Liste und dann 45:27.400 --> 45:29.260 müssen wir zusehen, dass wir da irgendwie Daten reinbringen. 45:30.320 --> 45:34.520 Und dieses Head ist einfach nur eine Funktion in dem Fall, die liefert 45:34.520 --> 45:36.660 zurück einen Zeiger auf das Header-Element. 45:36.920 --> 45:42.200 Also am Anfang haben wir eine Liste, in der formal erstmal dieses 45:42.200 --> 45:44.560 Header -Element drin ist, aber eigentlich ist sie leer. 45:45.020 --> 45:46.440 Also dieses Header-Element zählt halt nicht. 45:48.340 --> 45:51.620 Und so ein paar erste Funktionen können wir uns angucken. 45:52.360 --> 45:53.740 Wann ist die Liste leer? 45:54.180 --> 45:58.560 Genau dann, wenn das Nachfolge-Element zu dem Header der Header selber 45:58.560 --> 45:58.800 ist. 45:58.800 --> 46:03.040 Also sobald wir da Dinge einfügen in die Liste, wird der Nachfolger 46:03.040 --> 46:05.620 von dem Header-Element halt ein echtes Element sein, das erste 46:05.620 --> 46:06.000 Element. 46:06.680 --> 46:07.960 Das können wir dann auch zurückgeben. 46:08.100 --> 46:12.060 Also hier haben wir so eine kleine Annahme, dass wir sagen, dass die 46:12.060 --> 46:14.780 Liste nicht leer sein soll, damit das überhaupt Sinn ergibt, dieses 46:14.780 --> 46:15.100 First. 46:15.740 --> 46:19.740 Und dann können wir das erste Element zurückgeben, genauer gesagt 46:19.740 --> 46:24.020 einen Pointer auf das erste Element und das wäre halt einfach der 46:24.020 --> 46:24.900 Nachfolger vom Header. 46:24.900 --> 46:28.980 Und genau so ist das letzte Element der Vorgänger vom Header. 46:29.680 --> 46:32.420 Also auf diese Weise klebt der Header die gesamte Liste zusammen. 46:34.320 --> 46:37.940 Okay, das ist jetzt vielleicht noch nicht so spannend, aber was wir 46:37.940 --> 46:40.860 eigentlich machen wollen, das sind ja echte Operationen mit Listen. 46:42.160 --> 46:47.900 Und dafür gibt es die Funktion oder die Prozedur Splice. 46:49.620 --> 46:54.400 Für den Augenblick ist es vielleicht eine Funktion, die sieht nicht so 46:54.400 --> 46:57.760 aus, als würde man die oft brauchen, aber für uns wird sie halt extrem 46:57.760 --> 47:01.540 nützlich sein, weil wir viele Dinge als Spezialfall von dieser 47:01.540 --> 47:02.900 Funktion ausdrücken können. 47:03.040 --> 47:06.340 Und die meisten anderen Sachen werden dann später halt einfach 47:06.340 --> 47:07.120 Einzeiler werden. 47:08.400 --> 47:10.440 Also diese Splice-Funktion ist ziemlich wichtig. 47:10.540 --> 47:11.120 Was macht die? 47:12.500 --> 47:14.740 Das ist eine Methode von der Liste. 47:15.900 --> 47:21.820 Und was sie tut ist, sie nimmt eine Liste, die zwischen A und B ist. 47:21.940 --> 47:24.740 Also A und B sind Zeiger auf Elemente. 47:28.140 --> 47:30.780 Und diese Elemente selber sind dann eine Unterliste. 47:31.380 --> 47:35.180 Also das ist auch im Prinzip die Interpretation. 47:35.280 --> 47:38.560 Wir haben hier eine Liste von A nach B und das kann auch eine 47:38.560 --> 47:39.260 Unterliste sein. 47:39.380 --> 47:42.080 Also B muss jetzt nicht das letzte Element sein. 47:42.080 --> 47:44.760 Also B kann jetzt irgendwie auch noch Nachfolger haben und A kann 47:44.760 --> 47:45.420 Vorgänger haben. 47:45.980 --> 47:49.600 Und was wir tun wollen ist, wir nehmen wo immer diese Liste ist, 47:50.760 --> 47:51.760 schneiden sie raus. 47:54.220 --> 47:56.320 Ich sehe gerade, hier sind die Pfeile nicht... 47:56.320 --> 47:59.580 Also das hier sollten eigentlich schräge Pfeile noch sein. 47:59.700 --> 48:03.220 Also hier ist quasi so eine Überbrückung an der Stelle. 48:04.220 --> 48:08.220 Also wir schneiden diese Unterliste zwischen A und B raus und setzen 48:08.220 --> 48:09.720 sie an der anderen Stelle ein. 48:09.860 --> 48:13.440 Und zwar nach einem Target-Element, nach einem Ziel-Element T. 48:14.940 --> 48:15.420 Okay? 48:16.320 --> 48:22.020 Also Fragen zu dem grundsätzlichen Ziel vielleicht? 48:23.300 --> 48:26.720 Also rechts ist es halt auch so ein bisschen versucht, grafisch zu 48:26.720 --> 48:27.120 illustrieren. 48:27.200 --> 48:29.700 Am Anfang haben wir hier so eine Liste, irgendein A', das ist der 48:29.700 --> 48:30.460 Vorgänger von A. 48:30.740 --> 48:33.240 Dann kommt die Liste zwischen A und B und dann kommt B'. 48:33.240 --> 48:39.380 Und was wir tun ist, wir operieren das daraus, diese A-B-Liste, und 48:39.380 --> 48:41.360 setzen die halt nach einem Target-Element ein. 48:42.580 --> 48:43.420 Okay, und wie tun wir das? 48:43.500 --> 48:50.240 Als erstes mal müssen wir diese Liste zwischen A und B daraus kriegen. 48:51.100 --> 48:55.100 Und was das bedeutet ist, bis jetzt denkt ja A' noch, dass er der 48:55.100 --> 48:56.680 Vorgänger von A sei. 48:58.040 --> 49:04.100 Und als erstes mal identifizieren wir dieses A' und wir identifizieren 49:04.100 --> 49:05.860 auch das B', also den Nachfolger von B. 49:06.340 --> 49:09.840 Und denen erzählen wir jetzt erstmal, dass zwischen ihnen nichts mehr 49:09.840 --> 49:10.020 ist. 49:10.140 --> 49:16.280 Also der Nachfolger von A' wird jetzt B' sein und B' hat halt jetzt 49:16.280 --> 49:17.340 einen Vorgänger A'. 49:17.340 --> 49:23.100 Das heißt, von der Struktur der Liste her ist es jetzt so, dass 49:23.100 --> 49:25.260 zwischen A' und B' keine Lücke mehr ist. 49:25.260 --> 49:28.140 Also die Liste von A nach B ist da jetzt schon mal raus. 49:29.880 --> 49:36.020 Aber die fühlt sich jetzt vielleicht ein bisschen einsam, so ganz 49:36.020 --> 49:36.340 alleine. 49:37.440 --> 49:41.720 Und das ist ja das Ziel, die soll nach dem Listen-Element T wieder 49:41.720 --> 49:42.520 eingefügt werden. 49:42.860 --> 49:45.600 Und das ist jetzt der zweite Teil von dieser Funktion. 49:46.260 --> 49:49.340 Also was wir da tun ist, wir identifizieren erstmal den Nachfolger von 49:49.340 --> 49:52.240 T', das ist T'. 49:54.980 --> 50:01.700 Und zwischen T und T' müssen wir jetzt diese Liste von A nach B 50:01.700 --> 50:02.260 einfügen. 50:02.780 --> 50:04.840 Das heißt, wir sagen erstmal der Liste Bescheid. 50:05.140 --> 50:09.280 Das heißt, wir sagen dem Listen-Element B, dein Nachfolger ist T'. 50:10.140 --> 50:12.380 T' weiß zu dem Zeitpunkt noch nichts davon. 50:12.920 --> 50:17.240 Und wir sagen A, dass sein Vorgänger jetzt auf einmal T sein soll. 50:17.580 --> 50:19.920 Also die Liste zwischen A und B weiß jetzt schon Bescheid. 50:19.920 --> 50:24.420 Und an diesem Zeitpunkt hier ist jetzt auch mal für eine kurze Zeit 50:24.420 --> 50:26.880 die Invariante auch nicht mehr erfüllt. 50:27.620 --> 50:30.420 Die Datenstruktur-Invariante, die muss halt danach wieder erfüllt 50:30.420 --> 50:30.640 sein. 50:30.740 --> 50:35.420 Deshalb müssen wir T und T' auch noch Bescheid sagen. 50:35.680 --> 50:39.660 Also jetzt sagen wir T erstmal, dass sein Nachfolger A ist. 50:39.740 --> 50:43.760 Und T', das war der vorige Nachfolger von T, sagen wir auch noch, dass 50:43.760 --> 50:44.840 B jetzt sein Vorgänger ist. 50:45.620 --> 50:47.860 Also wie gesagt, rechts sollte es so ein bisschen veranschaulicht 50:47.860 --> 50:50.520 sein, wenn man sich hier die kleinen schrägen Pfeile noch denkt. 50:51.900 --> 50:56.480 Wir haben da erstmal so eine Überbrückung zwischen T und T'. 50:56.480 --> 51:01.780 Und in diese Lücke, am Anfang sind die noch überbrückt, aber am Ende 51:01.780 --> 51:06.080 werden wir das halt alles so verbinden, dass erst T kommt, dann A und 51:06.080 --> 51:07.820 irgendwann B und danach kommt T'. 51:08.620 --> 51:09.060 Okay? 51:13.280 --> 51:17.900 Okay, ich kann es jetzt nicht so ganz beurteilen, ob das verständlich 51:17.900 --> 51:21.560 oder langweilig oder zu schnell war, aber ich mache einfach so lange 51:21.560 --> 51:22.980 Sie nichts sagen, mache ich einfach so weiter. 51:25.400 --> 51:28.700 Okay, also wie schon gesagt, das ist für uns erstmal vielleicht so 51:28.700 --> 51:33.280 eine technische Hilfsmethode, die aber sehr nützlich sein wird, weil 51:33.280 --> 51:34.400 wir damit viel machen können. 51:36.140 --> 51:38.820 So, vielleicht noch hier ein Beispiel dazu, ich vergesse immer die 51:38.820 --> 51:39.240 Beispiele. 51:40.420 --> 51:44.420 Wir haben hier eine Liste zwischen 5 und 8 und die wollen wir halt 51:44.420 --> 51:47.460 jetzt umverpflanzen in so eine andere Liste nach T. 51:48.020 --> 51:51.020 Also nach diesem Element W. 51:52.120 --> 51:55.980 Und das würde dann so sein, dass am Ende danach weiß diese erste 51:55.980 --> 52:01.040 Folge, die weiß Bescheid, dass nach der Fee jetzt die 9 kommt, das 52:01.040 --> 52:03.860 heißt die Folge zwischen 5 und 8 ist raus, ist aber jetzt an der 52:03.860 --> 52:05.260 Stelle nach dem W eingefügt. 52:06.120 --> 52:08.000 Also konsistent mit unserer Datenstruktur. 52:10.520 --> 52:18.060 Okay, und was wir damit machen können ist zum Beispiel, dass wir eine 52:18.060 --> 52:25.560 bestimmte Teilliste oder Elemente, dass wir die an eine andere Stelle 52:25.560 --> 52:26.280 verschieben können. 52:26.560 --> 52:30.220 Das heißt, wir haben hier ein Element B und das wollen wir an eine 52:30.220 --> 52:31.120 andere Stelle verschieben. 52:31.120 --> 52:33.700 Also das verschieben wir jetzt hinter dieses A'. 52:34.520 --> 52:37.160 Und das können wir einfach so machen, indem wir sagen, nimm die 52:37.160 --> 52:40.480 Teilliste, die aus B und B besteht und füge die nach A'. 52:40.920 --> 52:47.480 Dann wird dann schon sorgsam umgegangen, sodass das A und C, also die 52:47.480 --> 52:52.300 Nachbarn von B, Bescheid kriegen und am Ende A' und C' auch Bescheid 52:52.300 --> 52:52.500 wissen. 52:54.400 --> 52:56.380 Wir können auch ein Element nach vorne ziehen. 52:57.580 --> 53:00.760 Die Besonderheit hier ist, dass wir jetzt auf einmal dieses Head 53:00.760 --> 53:02.160 -Element, diesen Header gebrauchen. 53:02.800 --> 53:06.480 Das heißt, das ist auch wieder ein schöner Seiteneffekt, dass wir 53:06.480 --> 53:11.100 diesen Header haben, dass wir jetzt den explizit benutzen können und 53:11.100 --> 53:13.720 sagen, nach dem Header wird irgendwas eingefügt, aber nach dem Header 53:13.720 --> 53:14.920 ist halt der Anfang der Liste. 53:15.420 --> 53:19.780 Also das heißt, dass irgendetwas an den Anfang geschoben wird und 53:19.780 --> 53:20.720 genauso gut an das Ende. 53:20.720 --> 53:24.940 Das ist halt der Vorgänger von dem Header oder alternativ das, was wir 53:24.940 --> 53:25.800 Last genannt hatten. 53:30.200 --> 53:34.240 Okay, jetzt vielleicht noch eine kleine Besonderheit. 53:35.400 --> 53:39.360 Naja, nicht Besonderheit, sondern eher noch ein Kommentar zur 53:39.360 --> 53:40.120 Implementierung. 53:40.740 --> 53:45.280 Wenn man das jetzt implementieren würde, in Java zum Beispiel, dann 53:45.280 --> 53:47.900 ist die Frage, wo kommen diese Elemente denn eigentlich her? 53:48.060 --> 53:49.580 Wo kommt der Speicher dafür her? 53:49.660 --> 53:54.040 Das sind ja letzten Endes Objekte, die muss man erstmal erzeugen und 53:54.040 --> 53:57.020 vielleicht werden die irgendwann, wenn ich die Liste nicht mehr 53:57.020 --> 53:59.480 brauche und die stehen da so allein rum, sind nicht mehr verzeigert. 54:00.620 --> 54:03.680 Das haben wir uns noch gar nicht angeguckt, was passiert, wie man 54:03.680 --> 54:04.620 Listenelemente löscht. 54:04.680 --> 54:05.920 Im Augenblick haben wir nur rum verschoben. 54:08.260 --> 54:11.580 Aber es ist überhaupt nicht so klar, wo denn die Elemente herkommen 54:11.580 --> 54:12.380 und wo die hingehen. 54:13.860 --> 54:18.480 Und wenn man das jetzt naiv machen würde, dann würde man vielleicht 54:18.480 --> 54:21.640 jedes Mal, wenn man ein neues Listenelement braucht, eins erzeugen. 54:21.640 --> 54:28.520 Und das wäre dann in C vielleicht ein Memory Allocation Aufruf oder in 54:28.520 --> 54:30.920 Java wäre das so ein New Aufruf. 54:31.380 --> 54:34.720 Aber dann wird der Speicherverwaltung Bescheid gesagt, dass wir hier 54:34.720 --> 54:37.000 ein bisschen Speicherplatz brauchen für ein Element. 54:37.580 --> 54:46.060 Und das kann ein bisschen ungünstig oder unekonomisch sein, einfach 54:46.060 --> 54:49.200 weil wir dann vielleicht ganz viele verschiedene 54:49.200 --> 54:52.760 Speicherreservierungsaufrufe hintereinander haben und die liegen dann 54:52.760 --> 54:54.100 irgendwie kreuz und quer im Speicher rum. 54:55.060 --> 54:58.120 Und dann ist auch die Frage, was passiert, wenn die Elemente nicht 54:58.120 --> 54:58.880 mehr gebraucht werden. 54:59.000 --> 55:00.740 Irgendwann in Java passiert dann vielleicht mal so eine Garbage 55:00.740 --> 55:01.120 Collection. 55:01.780 --> 55:04.780 Aber das ist für unseren Spezialfall vielleicht gar nicht so das 55:04.780 --> 55:05.500 Günstigste. 55:09.220 --> 55:12.240 Deshalb ist hier ein anderer Vorschlag, also so wie wir uns das 55:12.240 --> 55:14.240 vorstellen würden. 55:14.240 --> 55:22.900 Und der Vorschlag, der braucht eine einmal existierende Variable, die 55:22.900 --> 55:24.340 wir Freelist nennen. 55:24.500 --> 55:30.380 Und diese Freelist, die enthält Items, also Listenelemente, die noch 55:30.380 --> 55:31.280 nicht genutzt sind. 55:32.020 --> 55:33.320 Also im Augenblick noch nicht genutzt. 55:33.400 --> 55:37.220 Und jedes Mal, wenn wir ein neues Element benutzen, bedeutet das, dass 55:37.220 --> 55:40.420 wir aus der Freelist ein Element oder mehrere Elemente vielleicht 55:40.420 --> 55:41.280 sogar rausnehmen. 55:41.280 --> 55:45.280 Das heißt, wir haben hier einfach eine spezielle Liste von Anfang an, 55:45.420 --> 55:46.860 in der stehen ganz viele Elemente drin. 55:47.220 --> 55:50.020 Und das sind die Elemente, die ich vielleicht später brauchen könnte 55:50.020 --> 55:51.620 oder in die ich Daten reinschreiben könnte. 55:53.640 --> 55:57.540 Okay, also wir haben dann so einen Aufruf Check Freelist. 55:58.800 --> 56:01.840 Und der wird an den Stellen, wo ich ein neues Element brauche, 56:02.120 --> 56:04.720 vielleicht mal aufgerufen, um zu sehen, ob die Liste leer ist. 56:04.720 --> 56:12.260 Wenn sie leer ist, dann werden mehrere Elemente gerade generiert, so 56:12.260 --> 56:14.500 ein ganzer Block von Elementen, und die werden dann in diese Freelist 56:14.500 --> 56:15.280 wieder reingeschrieben. 56:15.780 --> 56:18.900 Umgekehrt kann man auch gucken, dass wenn irgendwann die Freelist so 56:18.900 --> 56:22.100 groß ist, dass man ganz viele ungenutzte Elemente hat, ob man die 56:22.100 --> 56:23.460 vielleicht nicht wieder freigibt. 56:27.140 --> 56:31.860 Und wenn man sich die realen Implementierungen anguckt, was man 56:31.860 --> 56:35.720 feststellt, was tatsächlich gebaut wird, aber da gibt es dann 56:35.720 --> 56:38.180 verschiedene Möglichkeiten. 56:40.100 --> 56:44.020 Viele Implementierungen benutzen dann einfach diese naive 56:44.020 --> 56:47.680 Implementierung, dass jedes Mal, wenn wir ein neues Listenelement 56:47.680 --> 56:51.360 brauchen, dass wir ein neues Objekt generieren oder ein neues 56:51.360 --> 56:52.320 Speicherplatzstück. 56:53.320 --> 56:57.340 Und da muss man dann an anderer Stelle natürlich gucken, dass diese 56:57.340 --> 57:00.740 Anfragen nach Speicherplatz irgendwie intelligent geregelt werden. 57:02.040 --> 57:05.000 Also da verlässt man sich auf die Speicherverwaltung von entweder der 57:05.000 --> 57:06.620 Programmiersprache oder von dem Betriebssystem. 57:07.780 --> 57:11.760 Und dann gibt es halt diese Freelist oder so ähnliche Konzepte. 57:12.300 --> 57:15.340 Und manchmal auch in Varianten, die für eine bestimmte Anwendung zum 57:15.340 --> 57:20.680 Beispiel abschätzen können von vornherein, wie viele Listen-Items man 57:20.680 --> 57:23.660 maximal braucht und dann von vornherein eine bestimmte Größe 57:23.660 --> 57:24.420 reservieren. 57:31.690 --> 57:34.950 Und jetzt können wir eigentlich auch dahin kommen, dass wir sagen, was 57:34.950 --> 57:36.550 passiert, wenn wir Items löschen. 57:40.470 --> 57:43.190 Denn jetzt können wir sagen, wenn wir ein Item löschen, dann können 57:43.190 --> 57:45.150 wir zumindest mal näher fassen, wo das hingehen soll. 57:45.250 --> 57:49.070 Also sagen wir mal, wir wollen dieses Item, was das Handle B hat, 57:49.270 --> 57:49.510 löschen. 57:49.510 --> 57:52.270 Das heißt, wir wollen die Liste, die vorher meinetwegen A, B, C 57:52.270 --> 57:55.590 enthielt, jetzt zu einer Liste umformulieren, die jetzt nur noch A, C 57:55.590 --> 57:56.890 enthielt und was immer drum herum war. 57:58.190 --> 58:03.730 Das bedeutet, dass wir einfach das Element B an den Kopf oder man 58:03.730 --> 58:07.350 könnte es auch an das Ende von der Freelist schieben. 58:08.930 --> 58:11.550 Okay, also jetzt bedeutet ein Element löschen eigentlich nur, das 58:11.550 --> 58:12.510 umzuverschieben. 58:12.510 --> 58:18.090 Nämlich auf unsere Halde sozusagen, auf unsere Liste, die die nicht 58:18.090 --> 58:19.830 gebrauchten Elemente verwaltet. 58:20.530 --> 58:24.890 Und genauso gut können wir dann Hilfsmethoden oder 58:24.890 --> 58:28.730 Bequemlichkeitsmethoden Popfront und Popback definieren, die dann halt 58:28.730 --> 58:32.970 das erste oder das letzte Element von der Liste wegstreichen und in 58:32.970 --> 58:34.230 diese Freelist verschieben. 58:36.950 --> 58:41.330 Genauso können wir Elemente einfügen, also aus einem Element hier. 58:41.630 --> 58:46.790 Also die Klasse für Listenglieder oder Listenelemente ist Item und die 58:46.790 --> 58:50.110 Klasse für die eigentlichen Daten ist in dem Fall Element. 58:50.210 --> 58:51.350 Das kann natürlich irgendwas sein. 58:51.850 --> 58:54.630 Und jetzt angenommen, wir haben so ein Datum hier bekommen und wollen 58:54.630 --> 58:56.550 das in eine Liste einfügen. 58:56.550 --> 59:02.210 Also wir wollen das genauer gesagt hinter diesem Handle A oder hinter 59:02.210 --> 59:05.730 diesem Listenelement, diesem Zeiger auf dem Listenelement A einfügen. 59:06.730 --> 59:10.350 Was wir dann tun können, ist wir gucken erstmal, dass überhaupt noch 59:10.350 --> 59:12.550 Listengliederelemente da sind. 59:12.990 --> 59:15.890 Und wichtig ist halt, hier muss dann was passieren, was gegebenenfalls 59:15.890 --> 59:17.150 diese Freelist auffüllt. 59:18.210 --> 59:23.870 Und dann nehmen wir meinetwegen das erste oder auch das letzte Element 59:23.870 --> 59:24.910 aus der Freelist raus. 59:24.910 --> 59:31.550 In dem Fall das erste und senden das an die Stelle, wo das neue 59:31.550 --> 59:34.430 Element hin soll, nämlich nach A. 59:34.890 --> 59:38.870 Also dieses A-Strich ist das neue Element und wir fügen das ein nach 59:38.870 --> 59:39.190 A. 59:39.890 --> 59:42.210 Und anschließend belegen wir das halt mit dem richtigen Wert. 59:42.330 --> 59:44.570 Also die Daten werden an der Stelle übertragen. 59:45.650 --> 59:47.390 Und das neue Element geben wir dann zurück. 59:48.910 --> 59:54.370 Und so kann man sich auch analog Hilfsmethoden schreiben für Insert, 59:54.490 --> 59:54.790 Before. 59:54.890 --> 59:57.620 Das wird halt vor einem bestimmten Element eingefügt. 59:59.510 --> 01:00:05.730 Und das funktioniert hier, indem wir einfach das Element, wo es davor 01:00:05.730 --> 01:00:06.870 eingefügt wird, nehmen. 01:00:07.030 --> 01:00:10.810 Nehmen den Vorgänger und danach fügen wir halt das neue Element ein. 01:00:11.190 --> 01:00:15.110 Und Push Front und Push Back bedeutet halt am Anfang oder am Ende der 01:00:15.110 --> 01:00:15.910 Liste einfügen. 01:00:15.910 --> 01:00:18.450 Das sind halt alles Hilfsmethoden eigentlich. 01:00:18.570 --> 01:00:22.510 Aber man sieht auch, dieses Header-Element ist hier ziemlich nützlich, 01:00:22.670 --> 01:00:25.390 weil wir überhaupt keine Unterscheidungen haben. 01:00:25.450 --> 01:00:28.490 Wir haben keine Fallunterscheidungen, ob die Liste jetzt leer ist, ob 01:00:28.490 --> 01:00:31.170 ein bestimmter Pointer jetzt null ist oder nicht. 01:00:31.590 --> 01:00:33.830 Und das kann man alles lösen, indem man dieses Header-Element hat. 01:00:37.250 --> 01:00:39.470 Wir können auch Listen zusammenfügen. 01:00:40.370 --> 01:00:44.190 Und das ist eigentlich auch wieder ein Aufruf von diesem Splice. 01:00:44.190 --> 01:00:53.370 Und da bedeutet es einfach, dass wir halt die Teilliste L' Also das 01:00:53.370 --> 01:00:58.250 ist jetzt hier ein Aufruf, eine Methode von der Liste. 01:00:58.430 --> 01:01:00.750 Und da soll man eine Liste anfügen, L'. 01:01:00.750 --> 01:01:06.030 Und wir nehmen einfach diese L'-Liste und implantieren die sozusagen 01:01:06.030 --> 01:01:09.370 an unser letztes Element dran. 01:01:11.870 --> 01:01:15.890 Und wir können die Liste auch einfach löschen, indem wir sagen, die 01:01:15.890 --> 01:01:18.830 soll komplett an die Freelist angefügt werden. 01:01:21.810 --> 01:01:26.970 Also wichtig hier, man kann auch große Datenmengen oder große Folgen 01:01:26.970 --> 01:01:28.510 in konstanter Zeit verschieben. 01:01:28.590 --> 01:01:32.790 Das ist etwas, was man zum Beispiel mit Feldern nicht so ohne weiteres 01:01:32.790 --> 01:01:33.230 machen kann. 01:01:33.310 --> 01:01:36.390 Und das gucken wir uns dann voraussichtlich nächstes Mal an, dass wir 01:01:36.390 --> 01:01:40.190 halt noch ein Beispiel sehen, was man denn für alternative Strukturen 01:01:40.190 --> 01:01:40.690 haben kann. 01:01:46.090 --> 01:01:50.290 Eine Methode noch, wenn wir ein Listen-Element finden möchten wollen, 01:01:51.310 --> 01:01:52.970 ist, dass wir halt ein Element suchen. 01:01:53.310 --> 01:01:56.230 Und an der Stelle sind vielleicht zwei Dinge interessant. 01:01:56.470 --> 01:02:01.170 Zum einen ist interessant, dazu komme ich dann sofort, dass wir so 01:02:01.170 --> 01:02:04.950 einen speziellen Einsatz von unserem Header-Element haben als Stopper 01:02:04.950 --> 01:02:05.590 sozusagen. 01:02:05.670 --> 01:02:06.910 Das ist einfach mehr so eine Art Trick. 01:02:07.290 --> 01:02:09.970 Und man muss sich dann überlegen, ob das ein Hack ist oder ob das 01:02:09.970 --> 01:02:11.130 wirklich etwas Elegantes ist. 01:02:11.590 --> 01:02:15.510 Und die zweite Sache ist, wenn ich so eine Liste habe, dann habe ich 01:02:15.510 --> 01:02:17.250 jetzt nicht so richtig wahlfreien Zugriff. 01:02:17.450 --> 01:02:19.710 Also wenn ich dann ein Element suche, dann bleibt mir eigentlich 01:02:19.710 --> 01:02:23.890 nichts anderes übrig, als durch die Liste halt so von vorne nach 01:02:23.890 --> 01:02:27.890 hinten oder von welcher Stelle ich auch will hier, ab einem bestimmten 01:02:27.890 --> 01:02:32.450 Element, dann halt durchzugehen, zu vergleichen und weiter zu machen, 01:02:32.750 --> 01:02:35.570 bis ich halt am Ende fertig bin und das Element gefunden habe oder 01:02:35.570 --> 01:02:36.130 auch nicht. 01:02:38.110 --> 01:02:44.090 Also es gibt vielleicht Strukturen, wo man Dinge einfacher finden 01:02:44.090 --> 01:02:48.690 könnte, aber jetzt, wie gesagt, noch was zu diesem speziellen Einsatz 01:02:48.690 --> 01:02:49.550 von diesem Header-Element. 01:02:49.550 --> 01:02:55.610 Also das Ziel ist, ich möchte ein Listen-Element X, also vielmehr das 01:02:55.610 --> 01:02:59.490 ist jetzt kein List-Item, das ist ein Daten-Element X, möchte ich 01:02:59.490 --> 01:03:00.270 finden in der Liste. 01:03:00.410 --> 01:03:03.390 Und wenn ja, dann hätte ich gerne einen Pointer auf die Stelle, wo es 01:03:03.390 --> 01:03:05.590 in der Liste vorkommt, damit ich sehe, was drumherum passiert. 01:03:06.410 --> 01:03:09.010 Das heißt also, ich gehe die Liste ab einem bestimmten Punkt, den ich 01:03:09.010 --> 01:03:15.390 übergeben kann, gehe ich die durch und gucke halt in jedem Schritt, 01:03:16.110 --> 01:03:18.790 also hier gehe ich weiter und dann gucke ich in jedem Schritt, ob das, 01:03:19.330 --> 01:03:25.250 was in diesem Listen-Element drinsteht, also from E, das wäre der 01:03:25.250 --> 01:03:29.190 Inhalt, der Dateninhalt von diesem Element, wo ich gerade bin, ob das 01:03:29.190 --> 01:03:30.890 mein Ziel-Element X ist oder nicht. 01:03:31.490 --> 01:03:35.790 Und wenn ja, dann gebe ich das zurück, wo ich gerade bin. 01:03:36.270 --> 01:03:40.190 Und die Frage ist jetzt, was mache ich, wenn das Element gar nicht in 01:03:40.190 --> 01:03:43.070 dieser Liste oder ab diesem Zeitpunkt from nicht in der Liste 01:03:43.070 --> 01:03:43.590 vorkommt. 01:03:45.210 --> 01:03:48.370 Und das ist jetzt eine Möglichkeit, da noch großartige 01:03:48.370 --> 01:03:49.770 Sonderbehandlungen zu vermeiden. 01:03:50.110 --> 01:03:53.450 Eine Möglichkeit wäre natürlich, ich gucke in dieser Weilschleife 01:03:53.450 --> 01:03:55.830 jedes Mal nach, ob ich schon am Ende bin. 01:03:56.530 --> 01:04:00.470 Aber da die Liste womöglich sehr lange ist, könnte das viel Zeit 01:04:00.470 --> 01:04:00.740 verbrauchen. 01:04:01.410 --> 01:04:04.230 Also ich möchte ja das, was hier in dieser Weilschleife vorkommt, 01:04:04.590 --> 01:04:05.610 möglichst optimieren. 01:04:07.730 --> 01:04:13.610 Also schön wäre es, wenn ich eben gerade nicht so eine Extra-Abfrage 01:04:13.610 --> 01:04:16.690 hätte, die eigentlich sowieso nur einmal zuschlägt, nämlich am Ende 01:04:16.690 --> 01:04:20.170 der Liste, also höchstens einmal und zwischendurch eigentlich unnütz 01:04:20.170 --> 01:04:20.390 ist. 01:04:21.670 --> 01:04:22.510 Und jetzt kommt hier der Trick. 01:04:22.790 --> 01:04:27.070 Der Trick ist, dieses Header-Element, das eigentlich diese Liste nur 01:04:27.070 --> 01:04:30.610 zusammenleimt und nicht wirklich da ist, das hat ja auch einen 01:04:30.610 --> 01:04:31.450 Datenanteil. 01:04:31.450 --> 01:04:32.930 Den habe ich bis jetzt noch nie genutzt. 01:04:33.290 --> 01:04:35.070 Also das hat eine Komponente E. 01:04:36.550 --> 01:04:38.590 Und die kann ich aber im Prinzip auch belegen. 01:04:39.630 --> 01:04:42.670 Und vorher war die mal mit so einem Bottom-Element, mit diesem 01:04:42.670 --> 01:04:47.210 komischen Element da belegt, aber hält mich erstmal nichts davon ab, 01:04:47.310 --> 01:04:49.110 die auch mit irgendeinem Element zu belegen. 01:04:49.470 --> 01:04:53.470 Und der Trick ist, wenn ich die jetzt mit meinem Zielelement X belege, 01:04:54.210 --> 01:04:57.950 dann werde ich in der Weilschleife maximal bis zum Ende der Liste 01:04:57.950 --> 01:04:58.210 gehen. 01:04:58.210 --> 01:05:01.050 Wenn ich am Ende der Liste bin, komme ich als nächstes an dieses 01:05:01.050 --> 01:05:02.110 Header -Element dran. 01:05:02.350 --> 01:05:05.330 Also nach dem Ende der eigentlichen Liste, dann komme ich zu diesem 01:05:05.330 --> 01:05:07.590 Header -Element wieder und da habe ich ja schon dieses Zielelement 01:05:07.590 --> 01:05:08.350 eingespeichert. 01:05:08.790 --> 01:05:12.350 Das heißt, die Suche wird in jedem Fall stoppen beim Header-Element. 01:05:12.570 --> 01:05:16.590 Und wenn ich dann am Ende was zurückgebe, wenn das das Header-Element 01:05:16.590 --> 01:05:20.690 ist, das kann man ja dann vergleichen, dann bedeutet das, dass das 01:05:20.690 --> 01:05:22.110 Element nicht in der Liste vorkam. 01:05:26.830 --> 01:05:31.470 Solche Stopper-Elemente oder in dem Fall könnte man auch Wächter 01:05:31.470 --> 01:05:35.650 -Element sagen, nennt man halt auch manchmal Sentinel. 01:05:36.490 --> 01:05:40.130 Also einfach, weil sie quasi darüber wachen, dass irgendeine Suche 01:05:40.130 --> 01:05:42.070 oder irgendwas nicht aus dem Ruder läuft. 01:05:44.010 --> 01:05:47.550 Und da gibt es halt verschiedene Vorkommen oder verschiedene Stellen, 01:05:47.750 --> 01:05:50.670 an denen das mal gebraucht werden könnte. 01:05:50.670 --> 01:05:53.290 Hier könnte man vielleicht jetzt am ehesten noch sagen, das ist 01:05:53.290 --> 01:05:54.030 irgendwie elegant. 01:05:54.430 --> 01:05:57.570 Aber manchmal gibt es halt auch Dinge, wo man eher sagen würde, das 01:05:57.570 --> 01:05:58.410 ist jetzt vielleicht ein Hack. 01:06:01.910 --> 01:06:03.910 Okay, aber für uns ist es jetzt eigentlich ganz nützlich. 01:06:04.130 --> 01:06:07.810 Es ist vor allem in dieser Wildschleife haben wir was optimiert und es 01:06:07.810 --> 01:06:10.030 ist auch so relativ einfach hingeschrieben. 01:06:10.150 --> 01:06:11.310 Und es hat auch eine einfache Semantik. 01:06:11.370 --> 01:06:13.870 Wenn ich das Header-Element zurückgebe, bedeutet das, das Element war 01:06:13.870 --> 01:06:14.450 nicht in der Liste. 01:06:21.130 --> 01:06:22.990 Wenn ich von einem Hack spreche, was meine ich damit? 01:06:23.290 --> 01:06:24.870 Naja, das ist natürlich subjektiv. 01:06:26.130 --> 01:06:28.690 Manchmal gibt es vielleicht besonders elegante Lösungen, die keine 01:06:28.690 --> 01:06:29.430 Nachteile haben. 01:06:29.870 --> 01:06:34.990 Ein Hack wäre sowas, was nicht einfach zugänglich ist und manchmal 01:06:34.990 --> 01:06:37.050 vielleicht negative Nebeneffekte hat. 01:06:37.570 --> 01:06:43.910 Also Beispiel, ich könnte so ein Wächte-Element haben, was in 01:06:43.910 --> 01:06:48.010 irgendeinem Sinne einen Zahlenvergleich abdecken soll. 01:06:48.010 --> 01:06:52.350 Also ich habe vielleicht einen Vergleich von der Zahl und in jedem 01:06:52.350 --> 01:06:54.990 Fall soll immer ein Element da sein, das das größte Element in einer 01:06:54.990 --> 01:06:57.130 bestimmten Liste ist und größer als meine Anfrage. 01:06:57.910 --> 01:07:01.970 Wenn ich da jetzt MaxInt reinschreibe, also die größte Integerzahl, 01:07:02.710 --> 01:07:04.370 dann wird das vielleicht funktionieren. 01:07:04.470 --> 01:07:07.230 Es sei denn, mein Anfrage-Element ist selber schon wieder MaxInt. 01:07:08.210 --> 01:07:10.530 Und das wäre vielleicht so ein hässlicher Nebeneffekt, der eigentlich 01:07:10.530 --> 01:07:13.410 nicht vorkommen sollte, aber irgendwie schon die Funktionalität von 01:07:13.410 --> 01:07:14.770 meinem Programm so subtil verändert. 01:07:14.770 --> 01:07:17.390 Aber ich gebe zu, ich kann es nicht genau definieren, das ist 01:07:17.390 --> 01:07:18.130 subjektiv. 01:07:18.190 --> 01:07:20.430 Das müssen Sie dann natürlich auch entscheiden für die Anwendung. 01:07:21.190 --> 01:07:24.390 Aber okay, ich kann die Frage nicht richtig gut beantworten, nicht 01:07:24.390 --> 01:07:25.710 besser als so mit einem Beispiel. 01:07:26.610 --> 01:07:27.810 Okay, sonst noch Fragen? 01:07:38.490 --> 01:07:44.330 Okay, manchmal möchte man Dinge haben, die mit so einer doppelt 01:07:44.330 --> 01:07:45.990 verzeigerten Liste nicht so gut gehen. 01:07:45.990 --> 01:07:49.070 Also wenn ich jetzt zusätzlich auch noch die Größe von der Liste 01:07:49.070 --> 01:07:54.070 abspeichern möchte, das ist ja eigentlich ein sehr natürlicher Wunsch, 01:07:54.890 --> 01:07:58.230 dann wird das mit so einer doppelt verzeigerten Liste wie gerade nur 01:07:58.230 --> 01:07:59.250 so halb gut gehen. 01:07:59.630 --> 01:08:00.610 Also der Grund ist folgender. 01:08:01.170 --> 01:08:06.850 Wenn ich jetzt eine Größe habe und das jetzt zum Beispiel als Variable 01:08:06.850 --> 01:08:12.450 von meiner Klasse betrachte, also von meinem Objekt, dann wird das 01:08:12.450 --> 01:08:17.110 Problem sein, wenn ich jetzt mit Splice anfange, Listen zu verschieben 01:08:17.110 --> 01:08:20.930 von einer Liste in eine andere Liste, dann weiß ich ja a priori nicht, 01:08:21.130 --> 01:08:23.090 wie groß diese Liste, die ich verschoben habe, ist. 01:08:23.470 --> 01:08:26.730 Das heißt, ich weiß auch nicht, um wie viel ich jetzt diesen 01:08:26.730 --> 01:08:29.250 Größenwert in den Listen anpassen muss. 01:08:30.050 --> 01:08:33.270 Und sich das in jeder einzelnen Liste zu merken, naja, dann müsste ich 01:08:33.270 --> 01:08:36.170 ja bei jedem Element noch irgendwas dabei stehen haben, oder das ist 01:08:36.170 --> 01:08:37.470 auch nicht so klar, wie man das machen würde. 01:08:38.330 --> 01:08:42.630 Wenn ich Splice allerdings nur innerhalb einer Liste verwende, dann 01:08:42.630 --> 01:08:43.130 geht das schon. 01:08:43.190 --> 01:08:48.210 Wenn ich innerhalb einer Liste vom hinteren Teil etwas in den vorderen 01:08:48.210 --> 01:08:52.690 Teil verschiebe von dieser Liste, dann weiß ich ja, die Größe ändert 01:08:52.690 --> 01:08:54.430 sich hier von dieser Liste nicht. 01:08:54.530 --> 01:08:56.510 Deshalb wird dieses Size immer konstant bleiben. 01:08:56.610 --> 01:08:59.110 Und für alle anderen Operationen weiß ich ja, ob ich ein Element 01:08:59.110 --> 01:09:02.050 anhänge, dann wird dieses Size größer werden. 01:09:02.150 --> 01:09:04.570 Oder ob ich ein Element aus der Liste irgendwo raus streiche, dann 01:09:04.570 --> 01:09:05.570 wird es natürlich kleiner werden. 01:09:05.570 --> 01:09:11.370 Das heißt, wenn man das mal Inter-List-Splice nennt, dann wird das 01:09:11.370 --> 01:09:14.470 eine Operation sein, die mit so einer zumindest naheliegenden 01:09:14.470 --> 01:09:18.530 Variablen -Size nicht mehr so kompatibel ist. 01:09:20.450 --> 01:09:23.630 Und man muss sich dann natürlich überlegen, was man für die Anwendung 01:09:23.630 --> 01:09:24.030 braucht. 01:09:24.190 --> 01:09:29.690 Ob das okay ist, wenn man diese Größe nicht verwaltet, oder ob man die 01:09:29.690 --> 01:09:31.690 verwalten muss, und wenn ja, dann muss man irgendeinen Kompromiss 01:09:31.690 --> 01:09:32.130 eingehen. 01:09:35.480 --> 01:09:39.640 Eine Variante von doppelt-verketteten Listen sind einfach-verkettete 01:09:39.640 --> 01:09:40.020 Listen. 01:09:40.300 --> 01:09:43.180 Und die sind in gewisser Weise ein bisschen hässlicher, deshalb werden 01:09:43.180 --> 01:09:45.060 die jetzt auch als zweites behandelt. 01:09:46.300 --> 01:09:48.820 Die sind deshalb hässlicher, weil sie sind vielleicht effizienter, 01:09:48.900 --> 01:09:50.420 aber dafür auch schwerer in der Handhabung. 01:09:50.620 --> 01:09:54.840 Also die Idee ist, wir haben wieder so eine Liste, und jetzt gibt es 01:09:54.840 --> 01:09:57.500 aber einfach diese Zeiger zu dem vorherigen Element, die gibt es nicht 01:09:57.500 --> 01:09:57.720 mehr. 01:09:58.260 --> 01:09:59.840 Die haben wir nicht mehr, die verwalten wir nicht mehr. 01:10:00.980 --> 01:10:03.680 Das bedeutet, es gibt nur wie jeweils den Zeiger auf das nächste 01:10:03.680 --> 01:10:04.700 Listen -Element. 01:10:05.160 --> 01:10:07.940 Und wir haben wieder dieses Dummy-Element, das heißt, wir können uns 01:10:07.940 --> 01:10:10.880 das auch so als Ring vorstellen, aber wir können immer nur in eine 01:10:10.880 --> 01:10:11.460 Richtung gehen. 01:10:13.280 --> 01:10:14.980 Warum würde ich das überhaupt haben wollen? 01:10:16.160 --> 01:10:19.200 Naja, der offensichtliche Grund ist, ich brauche mir diese ganzen 01:10:19.200 --> 01:10:23.320 Rückzeiger nicht mehr zu merken, es braucht natürlich weniger 01:10:23.320 --> 01:10:23.980 Speicherplatz. 01:10:25.060 --> 01:10:27.860 Das kann manchmal entscheidend sein, muss nicht, aber das kann 01:10:27.860 --> 01:10:29.360 manchmal natürlich ein entscheidender Grund sein. 01:10:30.280 --> 01:10:33.240 Aber es ist natürlich auch in der Funktionalität eingeschränkt, weil 01:10:33.240 --> 01:10:36.760 wenn ich jetzt hier ein Element rauslösen wollte, ist gar nicht mehr 01:10:36.760 --> 01:10:40.580 so klar, wie ich dem Element davor Bescheid sage. 01:10:41.100 --> 01:10:44.200 Denn ich kann ja nicht einfach zum Element davor gehen, ich könnte 01:10:44.200 --> 01:10:48.080 natürlich die Liste durchgehen, bis ich bei dem Element davor bin, 01:10:48.240 --> 01:10:51.280 aber das würde ja ziemlich lange dauern, wenn die Liste lang ist. 01:10:51.900 --> 01:10:58.320 Das heißt, da es keine Zeiger zum Vorelement mehr gibt, müsste ich 01:10:58.320 --> 01:11:01.980 jetzt sowas machen wie Remove After, was natürlich ziemlich hässlich 01:11:01.980 --> 01:11:02.220 ist. 01:11:04.200 --> 01:11:07.660 Also ich habe so gewisse Abstriche in der Funktionalität, bestimmte 01:11:07.660 --> 01:11:11.460 Aufrufe gehen nicht mehr oder gehen nur noch eingeschränkt und dafür 01:11:11.460 --> 01:11:13.040 habe ich natürlich ein bisschen Speicherplatz gewonnen. 01:11:13.320 --> 01:11:16.780 Da kann man sich jetzt überlegen, was für die Anwendung dann günstiger 01:11:16.780 --> 01:11:16.980 ist. 01:11:17.140 --> 01:11:19.160 Also im Augenblick geht es auch nur darum, so ein paar Sachen einfach 01:11:19.160 --> 01:11:19.880 mal vorzustellen. 01:11:22.660 --> 01:11:25.860 Eine andere Frage, vielleicht theoretischer ist eher, wann sage ich 01:11:25.860 --> 01:11:29.180 denn, dass die einfach verkettete Liste überhaupt noch in Ordnung ist. 01:11:29.280 --> 01:11:33.120 Also vorher konnte ich das sagen, wenn diese Verzeigerung irgendwie 01:11:33.120 --> 01:11:38.160 kompatibel ist oder konsistent ist, in dem Sinne, dass die Vor- und 01:11:38.160 --> 01:11:41.540 Zurückzeiger auch mit den Elementen abgesprochen sind, die davor und 01:11:41.540 --> 01:11:43.740 dahinter stehen. 01:11:45.020 --> 01:11:47.860 Das geht jetzt hier nicht mehr so leicht, weil ich ja nicht 01:11:47.860 --> 01:11:48.840 zurückgehen kann. 01:11:49.340 --> 01:11:51.300 Aber ich kann es zumindest noch theoretisch fassen. 01:11:51.380 --> 01:11:54.960 Das ist jetzt nichts, was effizient überprüft werden könnte, aber es 01:11:54.960 --> 01:11:57.640 ist noch wohl definiert, ich kann es noch hinschreiben. 01:11:57.800 --> 01:11:59.260 Wie gesagt, nicht mehr so einfach überprüfen. 01:12:00.340 --> 01:12:03.640 Das wäre dann die Aussage, dass wir den Graphen betrachten, 01:12:08.020 --> 01:12:12.360 aller Listenglieder und wir gucken uns die Kanten an, die daraus 01:12:12.360 --> 01:12:16.320 entstehen, wenn wir halt diese Next-Pfeile jeweils verbinden. 01:12:16.320 --> 01:12:21.040 Das heißt, wir haben eine Kante von einem Item 1 zu einem Item 2, wenn 01:12:21.040 --> 01:12:26.260 der Next-Zeiger von dem Item 1 auf Item 2 zeigt. 01:12:28.400 --> 01:12:32.360 Und jetzt kann man sagen, dass die Datenstruktur noch irgendwie in 01:12:32.360 --> 01:12:36.320 Ordnung ist, wenn zum einen jeder Next-Zeiger immer Nachfolge hat, 01:12:36.340 --> 01:12:39.680 also wenn jedes Element eine Nachfolge hat, wenn der Next-Zeiger auf 01:12:39.680 --> 01:12:41.120 ein anderes Element zeigt. 01:12:42.120 --> 01:12:48.120 Und wenn wir uns den Graphen angucken, dass es halt im Prinzip so eine 01:12:48.120 --> 01:12:50.540 Ansammlung von Kreisen ist, von Zyklen. 01:12:50.640 --> 01:12:52.060 Das sind jeweils die einzelnen Listen. 01:12:52.800 --> 01:12:56.400 Und genauer gesagt sollte der Eingangsgrad, also der Ausgangsgrad, das 01:12:56.400 --> 01:12:59.900 oben sagt, der Ausgangsgrad ist 1, das unten sagt, der Eingangsgrad 01:12:59.900 --> 01:13:01.880 ist 1 von jedem Element. 01:13:03.840 --> 01:13:07.200 Wie gesagt, das ist wohl definiert, aber nicht unbedingt leicht zu 01:13:07.200 --> 01:13:07.640 testen. 01:13:08.940 --> 01:13:13.420 Okay, also das ist auch so eine Eigenschaft von einfach verketteten 01:13:13.420 --> 01:13:17.620 Listen, die die vielleicht nicht so handhabbar oder handlich macht. 01:13:18.780 --> 01:13:20.560 Wir können auch Supplies angeben. 01:13:20.960 --> 01:13:23.460 Das fällt tatsächlich jetzt ein bisschen leichter, weil wir weniger 01:13:23.460 --> 01:13:24.240 Arbeit machen müssen. 01:13:24.620 --> 01:13:26.180 Wir müssen weniger Verwaltung machen. 01:13:26.460 --> 01:13:31.820 Also die Idee ist wieder, dass ich eine Liste zwischen A und... 01:13:31.820 --> 01:13:35.200 Also eigentlich das Blöde ist, ich brauche jetzt halt den Vorgänger 01:13:35.200 --> 01:13:36.980 von A. 01:13:36.980 --> 01:13:39.860 Ich brauche jetzt A' als zusätzliche Eingabe. 01:13:39.980 --> 01:13:42.880 Und eigentlich möchte ich aber die Liste, die von A nach B geht, wobei 01:13:42.880 --> 01:13:46.260 A der Nachfolger von A' ist, die möchte ich halt an T ranhängen. 01:13:46.680 --> 01:13:49.360 Also grafisch ist es vielleicht am einfachsten so dargestellt. 01:13:52.140 --> 01:13:53.940 Irgendwie funktionieren die schrägen Pfeile nicht. 01:13:54.420 --> 01:13:56.460 Also hier sollte ein schräger Pfeil sein. 01:13:57.640 --> 01:13:58.800 Das ist der Zustand vorher. 01:13:58.960 --> 01:14:03.240 Von A' geht es nach A, von da irgendwie nach B und dahinter steht B'. 01:14:04.920 --> 01:14:11.160 Das möchte ich jetzt so machen, dass ich dieses Ganze hier abendere, 01:14:11.240 --> 01:14:15.440 indem ich zunächst mal den A'-Nachfolger auf B' setze. 01:14:15.660 --> 01:14:17.700 Zu dem Zeitpunkt ist dann die Liste hier schon rausgelöst. 01:14:18.560 --> 01:14:22.420 Und dann sage ich diesem Element T noch Bescheid und dem letzten 01:14:22.420 --> 01:14:23.260 Element B hier. 01:14:23.980 --> 01:14:27.500 Also hier wird der T-Nachfolger dann auf den Anfang der Liste gesetzt, 01:14:27.640 --> 01:14:28.000 auf A. 01:14:28.000 --> 01:14:35.720 Das ist A' next und B sagt man dann auch, dass sein Nachfolger ab 01:14:35.720 --> 01:14:37.620 jetzt der Nachfolger von T ist. 01:14:38.260 --> 01:14:39.880 Das, was vorher der Nachfolger von T war. 01:14:40.680 --> 01:14:42.580 Also das macht es tatsächlich hier noch ein bisschen einfacher. 01:14:49.500 --> 01:14:57.500 Und dann kann man auch noch bestimmte Operationen sich genauer 01:14:57.500 --> 01:14:57.980 angucken. 01:14:57.980 --> 01:15:00.560 Und eine, die man so nicht hinkriegt, ist erstmal Pushback. 01:15:00.760 --> 01:15:04.720 Also wenn ich an das Ende von der Liste was anfügen soll, dann kann 01:15:04.720 --> 01:15:08.540 ich das erstmal nicht, da ich halt das Ende der Liste nicht kenne. 01:15:08.660 --> 01:15:12.380 Das kann man sich aber als zusätzliche Information in der Listenklasse 01:15:12.380 --> 01:15:16.100 noch merken, dass man halt diesen Anfang der Liste oder genauer gesagt 01:15:16.100 --> 01:15:20.320 diesen Header als Vorgänger des Anfangs, dass man sich den merkt und 01:15:20.320 --> 01:15:23.080 zusätzlich noch dieses Endelement. 01:15:23.280 --> 01:15:25.280 Und wenn ich das kenne, dann kann ich natürlich auch hinter dem 01:15:25.280 --> 01:15:26.600 Endelement noch Dinge einfügen. 01:15:26.600 --> 01:15:30.280 Und das ist halt eine zusätzliche Information, wie gesagt, die man 01:15:30.280 --> 01:15:31.260 einfach verwalten kann. 01:15:33.960 --> 01:15:39.980 Okay, das beendet das, was wir zu Listen machen wollten. 01:15:40.980 --> 01:15:45.240 Und ich werde dann jetzt gleich nochmal kurz zusammenfassen, was die 01:15:45.240 --> 01:15:47.680 wichtigsten Dinge oder vielleicht die wichtigsten Schlussfolgerungen 01:15:47.680 --> 01:15:47.940 sind. 01:15:48.760 --> 01:15:53.280 Und mit den Feldern werden wir dann nächstes Mal anfangen. 01:15:53.280 --> 01:15:57.100 Das ist heute vielleicht dann nicht mehr so gut möglich in den letzten 01:15:57.100 --> 01:15:57.660 zehn Minuten. 01:15:58.260 --> 01:16:01.060 Okay, also was haben wir heute über Listen gesehen? 01:16:02.180 --> 01:16:05.220 Das Wichtigste ist, dass wir halt diese Zeiger haben. 01:16:05.340 --> 01:16:08.100 Und die erlauben uns ziemlich viel Flexibilität, vor allem bei den 01:16:08.100 --> 01:16:09.100 doppeltverketteten Listen. 01:16:09.260 --> 01:16:11.620 Also gerade die doppeltverketteten Listen können wir natürlich 01:16:11.620 --> 01:16:12.800 besonders einfach behandeln. 01:16:12.800 --> 01:16:21.180 Und dieses Dummy-Element bespart uns jede Menge Sonderfälle und 01:16:21.180 --> 01:16:21.900 Sonderbehandlungen. 01:16:23.800 --> 01:16:27.220 Okay, wir haben diese Datenstruktur-Invarianten gesehen. 01:16:27.280 --> 01:16:29.380 Die könnte man vielleicht jetzt noch nicht so richtig würdigen, aber 01:16:29.380 --> 01:16:31.900 die sagen einem zumindest schon mal, ob die Liste noch in Ordnung ist. 01:16:32.240 --> 01:16:34.640 Das kann vielleicht auch nützlich sein, wenn man sich des Speichers 01:16:34.640 --> 01:16:35.500 nicht mehr so sicher ist. 01:16:36.840 --> 01:16:39.660 Und vielleicht das Wichtigste ist zum einen das Dummy-Element und dann 01:16:39.660 --> 01:16:40.260 dieser Wächter. 01:16:41.280 --> 01:16:46.280 Da haben wir gesehen, dass das so ein paar Sonderfälle einspart und 01:16:46.280 --> 01:16:49.340 für uns das Programm vielleicht auch irgendwie eleganter macht. 01:16:49.720 --> 01:16:54.480 Also einfacher auf jeden Fall und lesbarer vielleicht auch und 01:16:54.480 --> 01:16:54.740 schneller. 01:16:56.160 --> 01:16:57.700 Okay, haben Sie noch Fragen? 01:17:03.780 --> 01:17:06.420 Okay, dann würde ich sagen, wir sehen uns am Mittwoch. 01:17:06.460 --> 01:17:07.920 Am Mittwoch ist dann die erste Übung. 01:17:08.100 --> 01:17:11.740 Also die ist nach 45 Minuten und 45 Minuten Vorlesung. 01:17:11.740 --> 01:17:12.680 Danke!