Video 4-1: Dynamic Connectivity

0:03 Wo sind wir jetzt in der Vorlesung? Wir haben so ein bisschen Grundlagen gelegt und ganz ganz wenig Algorithmik gemacht. Es gibt noch so ein zwei äh Blöcke mit mit Methodiken, die die nachkommen, aber ich hatte das Gefühl, wenn ich jetzt noch weiter auf diesem Vorbereitungslevel bleibe, dann äh dauert das zu lange, bis wir mal was echtes algorithmisches machen. Deswegen ein kurzer Exkurs zu einem konkreten Beispiel, auch einer konkreten Anwendung, die Sie dann in den Übungen bauen dürfen, wo man mal ein bisschen sieht, wo die Reise hingehen soll. Und äh danach werden wir noch mal ein bisschen zurückgehen mit ein zwei kurzen Kapiteln zur Algorithmenanalyse.

0:46 Aber wie gesagt, als Auflockerung zwischen rein jetzt mal was ganz konkretes und handfestes, was man auch äh programmieren kann. Äh, wir werden uns eine bestimmte Datenstruktur anschauen, Union Find und eine Anwendung, wo die vorkommt. Äh, wir werden verschiedene Implementierungen davon sehen, definitiv nicht mehr heute. Ich werde äh kurz das Problem erklären können, so ein bisschen Ausblick geben und dann machen wir am Mittwoch weiter.

1:17 Wie schon gesagt, Ziel ist es äh mal konkret zu werden, bevor wir uns verlieren in Vorbereitung. Ähm, aber ein bisschen strukturierter noch äh sozusagen vorab schon mal achten Sie so ein bisschen drauf in dem, was dann folgt und am Mittwoch folgt, äh ob Sie diese Schritte da wieder erkennen können. Wie löst man algorithmische Probleme, wenn man ähm in der Anwendung irgendwie das Gefühl hat, da passiert was, was ähm eine spannende algorithmische Frage enthält. Äh wie nähre ich mich der so, dass ich eine gute Lösung finden kann? und äh nicht irgendwie kleine Änderung überall nur mache und nicht wirklich vom vom Fleck komme. Ähm der erste Schritt ist das Problem so zu modellieren, dass wirklich klar ist, was wir eigentlich lösen wollen. Das klingt vielleicht ganz einfach, aber manchmal äh gar nicht so klar, was das dann wann man damit fertig ist oder wann wann man eine gute Modellierung gefunden hat. Dann sollte der nächste Schritt immer sein, erstmal eine eine plumpe einfache Lösung zu versuchen und zu schauen, ob die gut genug ist.

2:20 Äh manchmal ist sie das dann eben noch nicht und es könnte sein, dass sie nicht schnell genug ist. Es kann aber auch sein, dass sie nicht in den Speicher passt. Beides kann ein KO Kriterium sein. Wenn dem eben noch nicht so ist, wenn sie noch nicht gut genug ist, dann müssen wir irgendwie versuchen, sie zu verbessern. Und Ziel wäre auch Teil des ganzen Moduls, dass sie ein bisschen ein geschultes Auge dafür bekommen, wie man solche Engpässe findet, an denen es hängt. Äh dazu natürlich auch und dann natürlich die Engpässe ausräumen. Dazu natürlich der Disclaimer, dass das beliebig schwierig werden kann. Ich werde an Fahrstellen auch erwähnen, dass es ähm zu ganz elementaren Fragen immer noch keine Lösung gibt, weil einfach niemand weiß, wie man die perfekt löst. Da werden wir es natürlich auch von ihnen nicht erwarten. Also auch da muss man manchmal dann bisschen ein Auge für entwickeln. O versuche ich hier was, an dem sich seit Jahrzehnten Leute die Zähne ausbeißen. Vielleicht ist es dann nicht eine gute Idee, das zu versprechen, dass ich das nächsten Monat gebaut habe. Äh in der Regel macht man diesen Prozess aber so ein bisschen iterativ, wie oft bei Ingenieurs äh Ansätzen.

3:27 Okay, natürlich möchte ich Ihnen auch ein paar hübsche Sachen zeigen und das ist ein erstes Werkzeug für Ihren Werkzeugkasten. Äh wann immer Sie mit ähnlichen Problemen zu tun haben, vielleicht erkennen Sie dann das Modell, das gleich kommt wieder. Dann brauchen sie nicht neue Sachen erfinden.

3:47 Wie schon kurz angangs erwähnt, die Folien im folgenden sind im Wesentlichen aus äh dem Onlinekurs zu dem äh roten Algorithmenbuch, dass wir dass ich auch schon am Anfang als eine der Quellen äh angegeben hatte. Der Teil ist einfach besonders schön illustriert und ähm sie haben, glaube ich, mehr davon, wie ich Ihnen die Bilder zeige und auf Deutsch den den Text gebe, als wenn wir die Folien übersetzen. Äh das sozusagen als als Zitat nicht wundern und ich mir ähm sie finden auch die die Folien, die da verwendet sind online.

4:28 Für den ersten Abschnitt möchte ich das Problem definieren und an der Stelle äh ganz ganz kurz andeuten, wo das herkommt. Aber so ein bisschen der erste Schritt dieser Modellierung ist ein bisschen schon vorweggenommen. Sie haben da nicht eine faire Chance, den nachzuvollziehen.

4:43 Ähm worum es hier geht, ähm könnte man als äh als ähm dynamische Zusammenhangskomponenten beschreiben. Wir haben Objekte angenommen. Wir wissen schon vorher, wie viele das sind. Das ist äh oft nicht das Problem. Dann können ähm zur Laufzeit zwei Arten von äh Anfragen kommen. Entweder wir wollen zwischen zwei Objekten eine neue Verbindung etablieren oder wir wollen wissen, ob es zwischen zwei Objekten in dieser Menge einen Pfad gibt. Also hier ist so ein Beispiel, das so einen Schnappschuss zeigt. Also wir haben diese Objekte 0 bis 9. Da gibt's ein paar ähm schon vergangene Verbindungen. Also zwischen 4 und 3 ist eine Verbindung eingezeichnet. Hier die schwarzen Kanten 3 bis 8, schwarze Kante 65 und so weiter. Ähm ist durchaus okay, dass es da Kreise gibt, je nachdem welche äh Queries da äh kam. Was uns interessiert ist nur, gibt es ein Pfad von A nach B? Also aus 0 bis 7 kann mich von 0 zu 7 irgendwie ähm am Anfang noch nicht. Äh das ist dann hier der das Endergebnis von der Animation. Da sind diese Connect ähm Befehle schon schon ausgeführt.

6:04 Vielleicht müsste ich das noch mal nachmalen, um es klar zu machen. Und wir können die die Schritte sukzessive nachvollziehen. Also das ist der Ausgangszustand. wichtig in diesem in diesem Problem, ich kann Verbindung nicht mehr entfernen. Das ist das macht das Leben hier unfassbar viel einfacher. Das allgemeine Problem, wo ich auch Verbindungen entfernen kann, ist schon eins von diesen, wo die endgültig beste Lösung unbekannt ist. Wenn ich aber nur Verbindung hinzufügen kann und prüfen kann, ob es einen Pfad gibt, dann ist es sehr viel einfacher. Also, wir fügen dann von 4 zu 3 den Pfad ein. von 3:8, von 6:5, 9:4 und 2:1. Zu diesem Zeitpunkt wird jetzt gefragt, ob 0 und 7 verbunden sind und sind sie natürlich nicht, deswegen ist das hier ein Kreuz. Dann 8 und 9. Aha. Ja, sie haben zwar keine direkte Verbindung, aber ein Pfad gibt's schon, also ist die Antwort ja.

7:10 Dann ähm heben wir uns das auf und machen hier unten weiter. Also verbinden 5 und 0, wir verbinden 7 und 2, wir verbinden 6 und 1, wir verbinden 1 und 0 und fragen dann, ob 7 und 0 verbunden sind. Und in dem Fall dann ist es ein Jahr. Okay, also natürlich ist das ein Graf, der äh Knoten und Kanten hat, wie es ihnen vielleicht auch schon begegnet ist. Wir werden darüber noch länglich und völlig ausführlich und sauber definiert sprechen, aber eher gegen Ende vom Semester. Ähm und man kann das als graftheoretisches Problem formulieren, muss man aber nicht. Das sind dann Zusammenhangskomponenten in ungerichteten Grafen. Aber wenn Ihnen das jetzt nicht hilft, macht nichts. Behalten Sie einfach hier dieses Bild im Kopf und wir können hier wann immer man hier diesen Connectbefehl hat ein so ein Strich einzeichnen. Aber Sie sehen vielleicht auch schon hier dieser letzte ähm diese letzte Verbindung zwischen 1 und 0, die hier eingezeichnet wurde, die brauche ich eigentlich nicht. Wenn ich die nicht eingezeichnet hätte, wären alle Queries, wer einen Pfad hat, die gleichen gewesen. Das Ergebnis ist unabhängig davon, ob ich diesen Strich hier einzeichne.

8:24 Da sieht man also schon, man kann vielleicht cleverer vorgehen, als komplett diesen diesen Graf da zu speichern. Okay. Äh, als eines ein erstes Beispiel, wo man ähm das einsetzen könnte, ist um äh in einem einem einem großen Gitter von Punkten. Also, jeder jedes Objekt, was wir hier 0 bis 9 hatten, ist jetzt hier einer dieser schwarzen Punkte und ich habe schon eine ganze Reihe von Connect Queries ausgeführt und kann jetzt fragen, ob es von hier nach da eine Verbindung gibt. Und in dem Fall ist es ein Jahr, weil es hier diesen langen roten Pfad gibt. Äh, das ist also ein Beispiel, wo man das einsetzen kann, wo auch vielleicht die Antwort nicht ganz so offensichtlich ist wie dem Miniispiel auf der Folie davor.

9:21 Welche Arten von Objekten haben wir da? Das ist jetzt wiederum für das algorithmische Problem ausgeklammert. Irgendwas ist die eigentliche Antwort. Und wo kann man das brauchen? Na ja, könnte alles mögliche sein. Es können Pixel in Bild sein oder es können Rechner in dem Netzwerk sein oder äh Freunde in einem sozialen Netzwerk oder Transistoren in dem Chip oder äh abstraktere Dinge. Ähm ist eine Programmiersprache, also Variablennamen, die vielleicht jetzt auf den die gleiche Speicherzelle zeigen. Tatsächlich ist einer der ursprünglichen ähm Kontexte, in denen das Ding erfunden wurde, Compilerbau.

9:59 Wir werden hier einfach aus Bequemlichkeit und weil es das effizienter macht, aber annehmen, dass diese n Objekte, mit denen wir es zu tun haben, immer die Zahlen 0 bis n -1 sind. Warum ist das bequem? Weil ich sie dann als Array indices verwenden kann und das macht es einfach schneller. Ähm und ich muss nicht schon andere Datenstrukturen, die wir noch gar nicht kennen, bemühen, werden wir noch sehen. Da gibt's allgemeine Lösungen, die das äh diese Anschränkung aufweichen. Ähm haben wir aber noch nicht gemacht. M.