Video 4-2: Dynamische Äquivalenzklassen

0:01 Ich hatte letztes Mal schon ganz grob gesagt, was dieses Dynamic Connectivity Problem ist, aber noch nicht die mathematischen Feinheiten besprochen. Äh, das wollen wir jetzt noch nachholen. Diese Verbindung, die wir hier als solche Striche zwischen zwei äh Objekten gemalt haben und wo ich dann sagte, es gibt einen Pfad, äh können wir mathematisch als eine Äquivalenzrelation auffassen, also Äquivalenzrelation auf Deutsch.

0:37 sprich sowas, was im Wesentlichen den Eigenschaften genügt, die wir an einen ist gleichstellen wollen, aber es ist ein bisschen weniger streng. Äh, es ist eine Relation, also eine ähm äh ja, eine bullische Funktion, also eine äh etwas, was ein was einem ja oder nein sagt, wenn ich hier zwei Objekte reingebe, kriege ich ja oder nein zurück und welche sind erlaubt, welche Funktionen solche, die für Eingabe PP, also das klein mal zweimal das identische Objekt immer ja zurückgeben. Also ist gleich sollte immer ich bin ich selbst. P ist = P. Es sollte symmetrisch sein. Die Reihenfolge, in der ich die beiden Parameter angebe, ändert den Rückgabewert nicht. Entweder P und Q sind gleich oder eben nicht. Auch wenn ich dann Q = Prage. Und das etwas weniger intuitive vielleicht ist diese Transitivität. Wenn P = Q ist und Q = R ist, dann mussen müssen auch P und R gleich sein. Das ist das, was wir mit Pfad anschaulich gemalt hatten. Also P = Q hatten wir gemalt als es gibt eine Verbindung von P zu Q und wir hatten die zweite Verbindung von Q zu R.

1:51 Das bedeutet nicht, dass es einen direkten Weg von P zu direkte Verbindung von P zu R gab in den Beispielen vorhin. Es gibt aber diesen Pfad über Q und das ist gut genug. Für diese Relation heißt es dann schon, dass auch P und R gleich anzusehen sind. Benutzt man, wenn man Gleichung löst intuitiv die ganze Zeit. Äh, der Punkt hier ist einfach das allgemeiner zu fassen. Äh, Äquivalenzrelation kann auch Dinge für gleich ansehen, die wir nicht die nicht identisch sind. Also klassisches Beispiel, was Sie im mathematischen Kontext dann hätten, wäre das gleich Modulo einer ähm so Restklassenmodulo.

2:42 Zwei Zahlen können gleich sein bezüglich dem Rest, wenn ich durch fünf teile. Das heißt nicht, dass es die gleiche Zahl ist. Also 1 wäre äquivalent zu sech in diesem in dieser Relation, weil beide haben Rest 1, wenn ich durch fünf dividiere. Natürlich sind trotzdem die Zahlen nicht identisch, aber ich kann auf diese Relation diese drei äh Eigenschaften prüfen und die erfüllt das. Darum geht es. Wir haben also Äquivalenzrelationen, aber anders als in der Mathematik sind die in unserem Fall dynamisch. die ändern sich, weil wir neue Verbindungen einziehen zur Laufzeit. Auch da wieder ganz am Ende werden Sie ein Beispiel sehen, wo das auf natürliche Weise äh hilft, dass man das tun kann. Ähm in Graf, wenn wir noch mal drauf zurückkommen, sind das dann Zusammenhangskomponenten, also Teile ähm Teilmengen von Knoten, zwischen denen ich einen Pfad finden kann. Und wir werden das hier teilweise auch so schreiben, dass ich die Menge, die Grundmenge partitioniere in die Äquivalenzklassen.

3:47 Also, Das kann man auch allgemein machen, diese Quotientenbildung, dass man eine Menge hat mit ein Äquivalenzrelation und dann betrachte ich eine andere Menge da der Menge, die Menge der Äquivalenzklassen. Alle Objekte sind in einer Menge, die gleich sind nach der Äquivalenzrelation. Okay, an irgendeiner Stelle müssen wir das mal äh in Code umsetzen und K die konkreten ähm Methoden, die Sie als Benutzer dieser dieser Datenstruktur aufrufen, die sind so gewählt. sind drei hier, wobei die mittlere ist so ein bisschen weniger wichtig, die können wir durch die anderen zwei lösen. Daher auch der Name Case Study Union Find nennt sich. Es gibt Find, das liefert mir für jedes Element, für jedes Objekt in der Menge einen Identifier für die Äquivalenzklasse, in der es ist. Das könnte erstmal irgendwas sein, aber die Idee ist, dass ich connected lösen kann, indem ich zweimal Feind aufrufe, nämlich Feind von P und Feind von Q. Und dann sollen die beiden gleich sein. Genau dann, wenn dieser Rückgabewert von Feind gleich ist. Werden wir auch gleich noch mal kommt noch mal extra auf den Folien auch. Und Union ist diese Operation, die die Relation verändert. Da behandle ich nachher P und Q gleich. Vielleicht waren sie auch vorher schon äquivalent, vielleicht auch nicht.

5:40 ist da nicht ähm nicht angegeben. Hier ist das Beispiel, ja, wenn ich diese Kante einziehe, woher gab es die drei Zusammenhangskomponenten eben diese hier, diese und die dritte. Und wenn ich diese Kante hier zwischen 2 und 5 einziehe, dann werden zwei davon verschmolzen. Deswegen heißt das Ding Union, weil es die Mengenvereinigung auf diesen Äquivalenzklassen darstellt.

6:05 Also Union ist nichts anders als Vereinigung. und Feind eben finden. Der Name ist vielleicht gar nicht so glücklich gewählt. Er hat sich etabliert. Eigentlich wäre Repräsentant vielleicht schöner in Codes. Ähm drücken wir das so aus. Man könnte jetzt an der Stelle ein richtiges Java Interface draus machen. In dem Setwagen Waynbuch machen sie das in aller Regeln nicht, sondern beschränken sich einfach drauf zu beschreiben, wie eine Klasse aussehen soll, die diesen Datentyp, diese äh API, dieses Application Programming Interface, dafür steht API, äh die das implementiert, ohne dass sie das streng in Java abbilden als Interface. Der Grund ist hauptsächlich, weil Interfaes dann doch nicht alles abbilden können und dann lassen sie es gleich ganz. Ähm ist eine Designentscheidung, kann man so und so lösen. Wir haben eine Anzahl von Objekten, mit der wir arbeiten und die Anzahl, die ist festgelegt im Konstruktor. Die kann man also nicht hinterher ändern. Die muss man vorher schon wissen. Dann kann ich Aufrufe an Union und Find machen und die Objekte sind einfach durch Ins dargestellt.

7:30 Also die hatten wir auch schon mal kurz auf der Folie vorher angesprochen. Die Objekte sind einfach die ersten n inte Integer und wir fangen bei null an. Dann kann ich die bei mit ähm einem Aufruf von Union in die gleiche Äquivalenzklasse zwingen und mit Find bekomme ich einen äh eine ID für die Zusammenhangskomponente.

7:52 Okay. Und hier ist, was ich schon gesagt hatte, die Frage, ob zwei äquivalent sind. Die eigentliche Frage, die uns für diese Relation vielleicht interessiert, die löse ich, indem ich zweimal Feind aufrufe und prüfe, ob das Ergebnis das gleiche ist. Soweit so gut.

8:17 Wenn ich so eine Implementierung schon hätte, wir tun mal so, als gäbe es die schon. Und der Hauptteil von der Vorlesung heute wird's dann darum drehen, diese ähm Implementierung zu füllen, dann kann ich damit z.B. dieses einfache Problem lösen. Äh das ist so ein quasi ein kleiner Test, damit wir auch uns nur Datenstrukturen auf gerekt überprüfen können. Wir kriegen Eingaben dieser Form, die lesen wir von Standard in so wie sie es auf Kilonova machen würden. Die erste Zeile ist die Anzahlobjekte, das groß n und dann folgt eine Reihe von Zeilen, in der wir immer zwei Zahlen bekommen und auf denen sollen wir Union aufrufen. Das ist die Idee äh von diesem dieser Ausgabe. Und tatsächlich ist das, was hier in Text geschrieben ist, ist das gleiche Beispiel, das auch hier auf den Folien war. Wenn Sie wollen wollen, können Sie die Aufzeichnung vom Montag anschauen und da haben wir es im Detail durchgeführt. Nur die Feind Aufrufe fehlen hier. Das sind nur die Union Aufrufe und sie sehen an paar Stellen sind da redundante Aufrufe drin für Objekte, die schon transitiv äquivalent sind, aber mit denen muss die Datenstruktur auch zurechtken.

9:28 Hier ist Code, der das umsetzt. Also wir lesen das N ein, wir bauen unsere Union Fight Datenstruktur, solange wir noch weitere Zeilen haben, als diese hier, lesen wir P und Q aus diesen zwei aus den zwei Zahlen. Und dann prüfe ich, ob die schon verbunden sind und falls nicht, rufe ich Union auf und gebe gebe auf der Kommandozeile aus, was da rauskam. Wen wir gleich auch noch äh in in Live sehen, wie das aussieht. Ähm, die Ausgabe ist nicht besonders spannend. Das sind einfach eine Reihe von diesen Zeilen. Ich habe dann noch ergänzt, dass wir die Anzahl Zusammenhangskomponenten am Ende bekommen. Ähm mehr passiert da erstmal nicht.

10:16 Also das ist das ist die Aufgabe. Jetzt würden wir gerne dieses Union Find implementieren und alles, was sie sozusagen zur Verfügung bekommen, ist die Spezifikation, was es tun soll. Und jetzt müssen wir uns überlegen, wie wir das denn im Code machen.