AU


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


Corona gjorde mange af os til hobby-matematikere. 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.


Af Michel Skov Jensen, Københavns Universitet


Corona gjorde mange af os til hobby-matematikere. 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.

Gennembruddet er gjort indenfor det matematiske område, der kaldes Petri-net, som bruges til at beskrive komplekse matematiske systemer. 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.

Anså problemet for uløseligt

Petri-nettet blev opfundet i 1939 af tyske Carl Adam Petri (i øvrigt i en alder af blot 13 år) til brug for kemi. 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.« ♦