COVID-beregning førte til løsning på gammelt datalogisk problem

Corona gjorde mange af os til hobby-matematikere. Hvor hurtigt ville antallet af indlagte på hospitalerne stige, og hvornår ville der indtræde flok-immunitet? Også de professionelle matematikere blev udfordret. Endda så meget, at det har inspireret en forsker ved Københavns Universitet til at løse et 30 år gammelt datalogisk problem. Gennembruddet er netop publiceret i det prestigefyldte tidsskrift Journal of the ACM (Association for Computing Machinery).

”Egentlig ville jeg bare regne på COVID-epidemien lige som så mange andre. Jeg ville eksperimentere med nogle ideer fra teoretisk datalogi, men her viste det sig, at det gamle problem var en stopklods,” siger Joachim Kock, lektor ved Matematisk Institut, Københavns Universitet.

Løsningen på problemet kan få anvendelse inden for epidemiologien og datalogien, men potentielt også en lang række andre fagområder. Fælles for disse områder er, at der optræder systemer med mange forskellige komponenter, som indbyrdes har indflydelse på hinanden. For eksempel kan mødet mellem en rask person og en COVID-smittet føre til, at der nu er to COVID-smittede.

Tysk teenager opfandt smart metode

For at forstå gennembruddet må man vide, at denne type komplekse systemer kan beskrives matematisk med såkaldte Petri-net. Metoden blev opfundet i 1939 af tyske Carl Adam Petri (i øvrigt i en alder af blot 13 år) til brug for kemi. Lige som mødet mellem en rask og en COVID-smittet kan føre til en forandring, kan det samme ske, når to kemiske stoffer mødes og reagerer.

I et Petri-net tegnes de indgående komponenter som cirkler, mens begivenheder tegnes som firkanter. Cirkler og firkanter forbindes derefter med pile, der viser de indbyrdes sammenhænge.

Dataloger anså problemet for uløseligt

I kemi anvendes Petri-net til at beskrive, hvordan koncentrationerne af forskellige kemiske stoffer udvikler sig i en blanding. Den tankegang har præget brugen af Petri-net i epidemiologi: man forestiller sig, at der i udgangspunktet er en høj ”koncentration” af raske, hvorefter ”koncentrationen” af smittede begynder at stige.  I datalogi bruges Petri-net på en lidt anden måde: her drejer det sig om individer snarere end koncentrationer, og udviklingen er snarere trinvis end kontinuerlig.

Joachim Kocks idé var at anvende de mere individ-baserede datalogiske Petri-net også til COVID-beregninger. Her løb han imidlertid ind i det gamle datalogiske problem:

”Grundlæggende er der to forskellige tilgange til at beskrive processerne i et Petri-net. I den første tilgang betragtes en proces som en lang serie af begivenheder. I den anden tilgang betragter man nettet som en grafisk fremstilling af sammenhængene mellem de forskellige komponenter og begivenheder,” forklarer Joachim Kock og uddyber:

”Den serielle tilgang er velegnet til udregninger. Men ulempen er, at den ikke beskriver årsagssammenhænge lige så godt som den grafiske tilgang. Den serielle tilgang har også svært ved at beskrive begivenheder, der finder sted samtidig.”

”Problemet består i, at ingen har kunnet forene de to synspunkter. Datalogerne havde vel egentlig givet op, og betragtede nærmest problemet som uløseligt. Det skyldes, at ingen tænkte på, at man var nødt til at gå helt tilbage og revidere selve definitionen af Petri-net,” siger Joachim Kock.

Lille justering med stor effekt

Den danske matematikers opdagelse var, at en lille ændring i definitionen af Petri-net faktisk muliggør en løsning af problemet:

”Ved at tillade parallelle pile i stedet for bare at tælle dem og skrive et tal, er der pludselig en smule mere information tilgængelig. Tingene går op, og de to tilgange til at beskrive processerne kan forenes.” 

Den matematiske begrundelse for, at den ekstra information er vigtig, er indviklet, men kan anskueliggøres ved en analogi:

”Gennem menneskehedens historie har vi haft stor gavn af at sætte tal på fysiske størrelser. For eksempel er det jo praktisk, at jeg på forhånd kan finde det rigtige antal stole frem, når jeg venter gæster til middag, i stedet for, at jeg skal prøve mig frem, når de har indfundet sig. Men antallet af stole og gæster siger ikke noget om, hvem som skal sidde hvor. Information går tabt, når vi betragter tal i stedet for objekter.”

På samme måde går der information tabt, når de individuelle pile i Petri-nettet kun angives ved deres antal.

”Tingene bliver en anelse mere besværlige, når man skal holde styr på de individuelle pile. Til gengæld kan de to tilgange nu forenes, og deres fordele kan opnås samtidigt.

Ringen til COVID er sluttet

Løsningen af problemet gør det muligt at beskrive komplekse systemer med mange indbyrdes sammenhænge mere præcist. Joachim Kock forventer dog ikke, at opdagelsen vil få stor praktisk betydning for dataloger, som anvender Petri-net:

”Det skyldes, at det er muligt at foretage den nødvendige tilpasning uden at revidere hele teorien om Petri-net. Lidt overraskende er der nu nogle epidemiologer, som er begyndt at anvende de reviderede Petri-net. Så man kan sige, at ringen er sluttet,” siger han.

Samtidig er der en morale i historien om den nye opdagelse, mener Joachim Kock:

”Mit ærinde var jo slet ikke at løse et gammelt datalogisk problem, men at regne på COVID. Det svarer lidt til, at man leder efter sin kuglepen, men indser, at man nok skal starte med at finde sine briller. På den måde vil jeg gerne slå et slag for vigtigheden af forskning, hvor man ikke har defineret på forhånd, hvad man skal finde ud af. Det er nogle gange forskning, som er drevet af nysgerrighed, der giver banebrydende resultater.”

Den videnskabelige artikel ”Whole-grain Petri nets and processes” er publicereret i Journal of the ACM (Association for Computing Machinery).