COVID inspiriert dazu, ein 30 Jahre altes Problem in der Informatik zu lösen

Startseite » COVID inspiriert dazu, ein 30 Jahre altes Problem in der Informatik zu lösen
COVID inspiriert dazu, ein 30 Jahre altes Problem in der Informatik zu lösen

Während der Corona-Epidemie wurden viele von uns zu Laienmathematikern. Wie schnell würde die Zahl der Krankenhauspatienten steigen und wann wäre die Herdenimmunität erreicht? Auch professionelle Mathematiker wurden herausgefordert, und ein Forscher der Universität Kopenhagen wurde inspiriert, ein 30 Jahre altes Problem in der Informatik zu lösen. Der Durchbruch wurde gerade von der renommierten veröffentlicht Zeitschrift der ACM (Association for Computing Machinery).

Wie viele andere wollte ich ausrechnen, wie sich die Epidemie entwickeln würde. Ich wollte in diesem Zusammenhang bestimmte Ideen aus der Theoretischen Informatik untersuchen. Ich erkannte jedoch, dass das Fehlen einer Lösung für das alte Problem ein Showstopper war.“

Joachim Kock, außerordentlicher Professor am Institut für Mathematik der Universität Kopenhagen

Seine Lösung des Problems kann in der Epidemiologie und Informatik und möglicherweise auch in anderen Bereichen von Nutzen sein. Gemeinsames Merkmal dieser Bereiche ist das Vorhandensein von Systemen, bei denen sich die verschiedenen Komponenten gegenseitig beeinflussen. Wenn beispielsweise eine gesunde Person auf eine mit COVID infizierte Person trifft, kann das Ergebnis sein, dass zwei Personen infiziert sind.

Clevere Methode, erfunden von deutschen Teenagern

Um den Durchbruch zu verstehen, muss man wissen, dass solche komplexen Systeme mathematisch durch sogenannte Petri-Netze beschrieben werden können. Die Methode wurde 1939 vom Deutschen Carl Adam Petri (übrigens im Alter von nur 13 Jahren) für chemische Anwendungen erfunden. So wie eine gesunde Person, die eine mit COVID infizierte Person trifft, eine Veränderung auslösen kann, kann dasselbe passieren, wenn sich zwei chemische Substanzen mischen und reagieren.

In einem Petrinetz werden die verschiedenen Komponenten als Kreise gezeichnet, während Ereignisse wie eine chemische Reaktion oder eine Infektion als Quadrate gezeichnet werden. Als nächstes werden Kreise und Quadrate durch Pfeile verbunden, die die Abhängigkeiten im System zeigen.

Eine einfache Version eines Petri-Netzes für die COVID-Infektion. Ausgangspunkt ist eine nicht infizierte Person. „S“ bedeutet „anfällig“. Der Kontakt mit einer infizierten Person („Ich“) ist ein Ereignis, das dazu führt, dass sich zwei Personen anstecken. Später wird ein weiteres Ereignis stattfinden, bei dem eine Person aus der Gruppe der Infizierten entfernt wird. Hier bezeichnet „R“ „geheilt“, was in diesem Zusammenhang entweder geheilt oder tot sein könnte. Beide Ergebnisse würden die Person aus der infizierten Gruppe entfernen.

Informatiker hielten das Problem für unlösbar

In der Chemie werden Petri-Netze verwendet, um zu berechnen, wie sich die Konzentrationen verschiedener chemischer Substanzen in einem Gemisch entwickeln werden. Diese Denkweise hat die Verwendung von Petri-Netzen in anderen Bereichen wie der Epidemiologie beeinflusst: Wir beginnen mit einer hohen „Konzentration“ von nicht infizierten Menschen, woraufhin die „Konzentration“ von Infizierten zu steigen beginnt. In der Informatik ist die Verwendung von Petri-Netzen etwas anders: Der Fokus liegt auf Individuen statt auf Konzentrationen, und die Entwicklung erfolgt in Schritten statt kontinuierlich.

Joachim Kock hatte vor, die eher individuenorientierten Petrinetze aus der Informatik für COVID-Berechnungen einzusetzen. Dabei stieß er auf das alte Problem:

„Grundsätzlich können die Prozesse in einem Petri-Netz durch zwei getrennte Ansätze beschrieben werden. Der erste Ansatz betrachtet einen Prozess als eine Reihe von Ereignissen, während der zweite Ansatz das Netz als grafischen Ausdruck der Wechselwirkungen zwischen Komponenten und Ereignissen betrachtet“, sagt er Joachim Kock, ergänzt:

„Der serielle Ansatz ist gut geeignet, um Berechnungen durchzuführen. Allerdings hat er einen Nachteil, da er Kausalitäten weniger genau beschreibt als der grafische Ansatz. Außerdem greift der serielle Ansatz tendenziell zu kurz, wenn es um gleichzeitig stattfindende Ereignisse geht.“

„Das Problem war, dass es niemandem gelungen war, die beiden Ansätze zu vereinen. Die Informatiker hatten mehr oder weniger resigniert und das Problem als unlösbar angesehen Definition eines Petrinetzes“, sagt Joachim Kock.

Kleine Modifikation mit großer Wirkung

Der dänische Mathematiker erkannte, dass eine geringfügige Modifikation der Definition eines Petrinetzes eine Lösung des Problems ermöglichen würde:

„Indem man parallele Pfeile zulässt, anstatt sie nur zu zählen und eine Zahl zu schreiben, zusätzliche Informationen zur Verfügung gestellt. Die Dinge funktionieren und die beiden Ansätze können vereinheitlicht werden.“

Der genaue mathematische Grund, warum diese zusätzlichen Informationen wichtig sind, ist komplex, kann aber durch eine Analogie veranschaulicht werden:

„Die Nummerierung von Gegenständen hat der Menschheit sehr geholfen. So ist es zum Beispiel sehr praktisch, dass ich für eine Dinnerparty die richtige Anzahl von Stühlen im Voraus arrangieren kann, anstatt nach der Ankunft mit verschiedenen Kombinationen von Stühlen und Gästen experimentieren zu müssen. Aber , die Anzahl der Stühle und Gäste verrät nicht, wer wo sitzen wird. Einige Informationen gehen verloren, wenn wir Zahlen anstelle der realen Objekte betrachten.“

Ebenso gehen Informationen verloren, wenn die einzelnen Pfeile des Petrinetzes durch eine Zahl ersetzt werden.

„Es erfordert etwas mehr Aufwand, die parallelen Pfeile einzeln zu behandeln, aber man wird reichlich belohnt, da es möglich wird, die beiden Ansätze zu kombinieren, so dass die Vorteile beider gleichzeitig erreicht werden können.“

Der Kreis zu COVID hat sich geschlossen

Die Lösung hilft unserem mathematischen Verständnis, komplexe Systeme mit vielen Abhängigkeiten zu beschreiben, wird aber laut Joachim Kock keine großen praktischen Auswirkungen auf die tägliche Arbeit von Informatikern mit Petri-Netzen haben:

„Denn die notwendigen Modifikationen sind größtenteils rückkompatibel und können ohne Revision der gesamten Petrinetz-Theorie angewendet werden.“

„Überraschenderweise haben einige Epidemiologen begonnen, die überarbeiteten Petri-Netze zu verwenden. Man könnte also sagen, der Kreis hat sich geschlossen!“

Joachim Kock sieht noch einen weiteren Punkt in der Geschichte:

„Ich war überhaupt nicht darauf aus, eine Lösung für das alte Problem in der Informatik zu finden. Ich wollte nur COVID-Berechnungen durchführen. Das war ein bisschen so, als würde man nach seinem Stift suchen, aber feststellen, dass man zuerst seine Brille finden muss. Also, ich möchte die Gelegenheit nutzen, um für die Bedeutung von Forschung einzutreten, die kein vordefiniertes Ziel hat. Manchmal führt Forschung, die von Neugier getrieben wird, zu Durchbrüchen.“

Quellen:

Zeitschriftenreferenz:

Kock, J. (2022) Vollkorn-Petrinetze und -prozesse. Zeitschrift der ACM. doi.org/10.1145/3559103.