Video 4-6: Union-Find-Anwendung in Perkolationstheorie

0:02 Lassen Sie mich noch ein paar Takte zu einer Anwendung sagen, die Sie in den Übungen dann auch implementieren sollen, damit so ein bisschen auch klar wird, dass dieses Union Find, abgesehen von all dem der schönen Theorie und der faszinierenden Mathematik, die da dahinter steckt, ähm auch aus einer Anwendungsperspektive geboren wurde.

0:19 Ähm hier ist eine eine lange Liste von Anwendungen, die Union Find an irgendeiner Stelle als Teilbaustein verwenden. Für viele von denen äh müsste man genauer erklären, was da jetzt dahinter steckt. Und das sind auch teilweise Dinge, die ihnen noch begegnen werden im weiteren Studium. Wir werden uns dieses erste hier gleich im Detail anschauen. Da geht's eigentlich um ein physikalisches Phänomen. Wer trinkt gerne Kaffee?

0:45 Einige, schon einige die Informatiker verfallen ja irgendwann in so zwei Camps, entweder Kaffee süchtig oder gar kein Kaffee. Äh, da scheint so ein so ein Grenzprozess zu geben. Ähm, wie kommt's da wie kommt's dazu, dass am Anfang gerade bei Espresso das Kaffeepulver eigentlich undurchlässig ist, aber irgendwann mit genug Druck geht das Wasser durch und nimmt die ganzen guten Aromastoffe mit? Das ist der Effekt, den man hier ähm Perkulation nennt, wenn ein Stoff, der eigentlich undurchlässig ist, plötzlich doch Flüssigkeit durchlässt. Oder vielleicht haben sie auch damit experimentiert, je feiner man das Pulver malt, desto ähm mehr kann ein passieren, dass da kein Wasser mit durchkommt. Und das ist ein relativ krasser Übergang, den werden wir uns gleich ganz kurz anschauen. Äh und auf die anderen Beispiele werde ich es nicht näher eingehen.

1:41 Die Kaffeeanalogie ist das, was Sie im Kopf haben sollten, was wir an physikalischen Phänomen da untersuchen wollen. Die konkrete mathematische Formulierung davon sieht so aus. Wir wir stellen uns vor, das ist so ein so ein Schnitt durch ihren ihren Siebträger. Und das hier sind äh Kaffeekörnchen mit Zwischenräumen, denn die sind ja nicht komplett ähm verdichtet.

2:06 Das heißt, diese weißen Zellen, das sind Zwischenräume, durch die Wasser fließen kann und die schwarzen sind tatsächlich die Körnchen von ihrem Kaffeepulver. Und ähm in diesem linken Beispiel gibt's eben einen Pfad für das Wasser von oben nach unten durch und sie kriegen Kaffee oder Espresso und in dem rechten Bild bleiben wir hier stecken. Die Ränder sind an der Seite sousagen, das hier ist äh Siebträger, ja, da kommt nichts durch. Und Diagonal ist nicht erlaubt. Also Durchfluss gibt's nur über die links, rechts, oben, unten Verbindung und hier ist eben der Fluss blockiert. Also die Frage ist, geben so ein Gitter von Punkten, die jeweils belegt oder frei sein können, gibt es einen Pfad von irgendwo oben zu irgendwo unten? Das ist die diese Frage, die man bei diesem Kalkulationsproblem löst.

2:58 Und ähm die Modellierung, das ist jetzt was, was aus der Physik motiviert ist. Ähm was wir jetzt erstmal so einfach glauben. Ähm ein sinnvolles Modell ist, dass jede Zelle mit Wahrscheinlichkeit P blockiert ist, äh offen ist und mit Wahrscheinlichkeit 1 - P blockiert ist. Das heißt, jede jedes Gitterpünktchen wird unabhängig von allen anderen mit einem Münzwurf entschieden, blockiert oder nicht blockiert. Physikalisch ist das P dann sowas wie die Dichte und je fester sie ihren Siebträger den Kaffee komprimieren, desto ähm desto kleiner wird dieses P eben werden. Und wir abstrahieren von dem physikalischen echten Prozess zu einem Zufallsprozess, der auf der großen Skala von diesen vielen, vielen Einzelteilen das gut approximiert. Äh, das ist natürlich nicht nur für Kaffee anzuwenden, sondern ähnliches gilt für elektrische Leitung von ähm von Leitern oder Isolatoren. Ähm, für Flüssigkeiten, das ist der Kaffee, aber es ist auch für Dinge wie Kommunikation zwischen Menschen oder Ausbreitung von Pathogen gleiches Spiel. Ähm da ist das das Gitter nicht ganz so fest und Leute bewegen sich, aber ähnliche Prozesse äh laufen auch da ab.

4:17 Das Interessante an der Stelle ist, wenn man dieses Gitter groß macht, gibt es einen ganz krassen Übergang von zu kleinem P. die Wahrscheinlichkeit, dass es offen ist, ist zu klein. Dann habe ich fast immer, wenn ich das zufällig ausführe, den Ausgang, dass es nicht durchfließt bis hin zu einem Wert von P, der deutlich größer als dieser Schwellwert ist, wo ich fast immer einen Durchfluss habe. Und es gibt einen engen Raum für diese Wahrscheinlichkeit P, wo ähm es so gerade an der an der Kippe ist. Mal sehe ich, dass es äh einen Durchfluss gibt und mal nicht. Und der spannende Punkt ist, das ist jetzt eine mathematische Frage. Was ist dieser Schwellwert P? Man kann beweisen als Grenzwert für n gegen unendlich, ich glaube, das kommt auch hier genau, wenn ich dieses dieses Quadrat größer und größer mache, dann gibt es einen ganz harten Schwellwert. Wenn mein P unter diesem Schwellwert ist echt kleiner, dann werde ich mit Wahrscheinlichkeit 1 keinen Durchfluss finden und mit Wahrscheinlich, wenn es drüber ist, mit Wahrscheinlichkeit ein Durchfluss haben und genau am Schwellwert passiert irgendwas Wildes.

5:20 Der Punkt ist, niemand kennt diesen Schwellwert. Man kann den mathematisch äh nicht exakt bestimmen. Wir wissen nicht wie. Also wahrschein man kann beweisen, es gibt einen Schwellwert, aber keiner hat eine Formel, die exakt den Schwellwert bestimmt. Ah, ärgerlich. ähm können wir zu den Mathematikerkollegen gehen und sagen, hier macht mal was. Ähm was wir in der Informatik tun können, um zumindest einen ungefähren Wert zu bekommen, ist Simulation.

5:49 Und hier ist so ein bisschen der Ausgang von solchen Simulationen gezeigt. Äh für verschiedene Werte von Pht man dann, wie der Übergang ist von geht fast nie durch zu geht fast immer durch. Dann wissen Sie, wie fest Sie ihren Kaffee tempern müssen. Was wir hier machen, nennt man Monte Carlos Simulation, weil wir Zufallszahlen oder Pseudofallszahlen im Computer verwenden, um äh ein Beispiel von so einem von so einer Realisierung herzustellen und dann einfach zu berechnen, gibt es da ein Durchfluss, ja oder nein? Und Monte Carlo wird es dann, wenn wir einfach das ganz oft wiederholen und Mittelwert nehmen. Also eine Simulation könnte ja irre führend sein. Vielleicht hatte ich unfassbar Glück und der Kaffee geht durch. Aber was wir wollen ist, dass es fast immer durchgeht oder fast nie. Und dafür wiederholen wir einfach den gleichen Vorgang mehrmals mit neuen Zufallszahlen und schauen, wie oft hat's geklappt.

6:46 Das werden Sie in den Übungen machen ähm als Kilonova Abgabe. Äh und das Ziel ist ein bisschen sich diesem Schwellwert empirisch äh zu nähern. Ähm auf den Folien kommt es noch so ein bisschen ein Hinweis, wie man das implementieren könnte.

7:01 Also nahliewe würden diese diese Quadrate zu den Objekten in unserem Union Feind werden. Das sind also die Dinge. Und dann würden wir für ähm offene Verbindung, also diese zwei Zellen, die sind verbunden. Das heißt, da gibt es einen Weg, da würden wir einen Union Aufruf machen. entsprechend hier auch für diese zwei haben ein Union Aufruf und dann kommen sie diese Pfade auf dem rechten Bild und die Frage ist dann, ob es irgendeine Möglichkeit gibt von einem der hier oben zu einem der hier unten zu kommen. Und das ist im Wesentlichen ein Feaufruf. Das ist genau dann so ein Pad durch dieses Gitter hier. Beispiel gibt's keinen, das ist bisschen schade. Äh, aber im Wesentlichen gäbe es genau dann so ein Pfad von irgendeinem Punkt hier oben zu einem anderen Punkt hier unten, wenn es einen Perkulationspad gibt. Also mit Union Find kann man genau dieses Problem lösen und sie müssen noch ein bisschen drüber nachdenken, wie sie das effizient machen.

8:11 Äh insbesondere ist hier praktisch, da wir diesen Schwellwert P nicht so gut eingrenzen können, ist eine clevere Idee zu sagen, wir fangen an mit einer komplett blockierten Welt und wählen dann zufällige Zellen, die wir jetzt öffnen, wo wir quasi das Kaffeekörnchen entfernen, so wie hier. Und dann habe ich plötzlich neue Verbindungen zur Seite. Also diese hier, diese hier, diese hier. die kommt jetzt neu dazu, wenn ich diese Zelle öffne.

8:40 Und dementsprechend habe ich hier eine Handvoll Union Aufrufe, die mir ähm jetzt neue Wege eröffnen und da ist es clever, dass Union Find diese diese Abfrage dynamisch kann. Ich ich öffne eine Zelle und frag dann wieder, gibt's einen Weg von oben nach unten? Wenn ja, dann kann ich aufhören mit der Simulation. Und dann weiß ich ja, es wird auch in Zukunft weiterin diesen Weg geben. Und sie können dann aus einer Simulation viel mehr Informationen generieren, als äh quasi alle Zellen zu füllen mit einer festen Wahrscheinlichkeit P und dann den Weg zu suchen und wenn es nicht geklappt hat, verwerfen und alles von vorne, sondern stattdessen erhöhen wir sozusagen stückweise, wie viele Zellen offen sind, bis es dann durchgeht. Das ist viel viel effizienter, um diesen Schwerwert ab einzugrenzen, als jedes Mal eine Simulation von null aufzustarten.

9:40 Und hier so die Bottomline ist ist noch mal ähm, dass man äh also sie kriegen gesagt, was zu schwerwert ist. Sie können auch Wikipedia nachlesen, da gibt's ganz viele offene Fragen zu diesem Proculation Theory. Hab sie gesehen. Ähm, komm gleich auf Sie zurück. Äh, ein schönes Beispiel, wie eben ein bisschen Code, relativ wenig Code, wie Sie sehen werden, äh solche offenen äh Fragen in Mathematik und Physik ähm lösen kann. Äh, ich will noch einmal ganz kurz Revue passieren lassen, was wir jetzt gesehen haben. Wir haben ein Problem modelliert als abstrakten Algorithmus. Wenn Sie wollen, können Sie vom Perkulationsproblem loslaufen und sagen: "Ha, ich würde gerne wissen, wann mein Kaffee durchläuft. Wie modelliere ich das denn?" Na ja, da gibt's dieses Gittermodell und dann gibt's irgendwie Pfade von oben nach unten. Wie kann ich das jetzt effizient simulieren? Und von da würde man normalerweise loslaufen und sagen, aha, da gibt's diese Kernkomponente, das Dynamic Connectivity Problem, die ich mit diesem Union und Find beschreiben kann. Das ist das kernalgorithmische Problem, dass ich lösen muss, um dieses diese Simulation effizient zu machen. Und von da haben wir mehrere Algorithmen gesehen, die zuerst nicht so gut funktioniert haben und ähm am Ende dann effizient wurden.

10:53 Das Beispiel ist ein bisschen unfair, weil natürlich mit dem Wissen um, was da so passiert ist über die Jahrzehnte, man das so präsentieren kann, als wäre es immer ganz einfach und ganz smooth von einer Verbesserung zur nächsten zu kommen. Äh, in Wirklichkeit ist die der Pfad da ein bisschen weniger gradlinig. Das nur so als als Warnung, wenn sie da selbst aktiv werden. Aber es ist auch einfach ein schönes Beispiel, wo das wunderbar funktioniert hat.