Hvordan finder man den bedste øl på den videnskabelige måde?
Forskere vinder pris for metoder, som fokuserer på at minimere slid på data under dataanalyse.
I denne regnvåde juletid kan man godt have brug for at skylle de store vandmængder ned med et godt glas af de gyldne dråber – men, hvordan sammenligner man egentlig øl uden at ”slide” sin favorit-øl op i processen?
Rolf Fagerberg, professor i datalogi på Institut for Matematik og Datalogi, demonstrerer i filmen her problemet omkring slid af data ved hjælp af en simpel øl-smagning.
Sammenligninger er en central del af mange algoritmer
Professor Rolf Fagerberg og en international gruppe af kollegaer har vundet en pris for bedste videnskabelige artikel ved konferencen European Symposium on Algorithms. I artiklen stiller de nye spørgsmål om måder for at sammenligne data.
– Man har, siden datalogi opstod som videnskab tilbage i 1960’erne, fundet det vigtigt at vide, hvor lang tid en algoritme bruger, inden man implementere den i et program. Derfor har meget forskning fokuseret på at analysere algoritmers køretid, og på at finde nye og endnu bedre algoritmer, hvor køretiden er kortere, forklarer Rolf Fagerberg.
En algoritme er en matematisk problemløsningsmetode. Det kan f.eks. være den bedste måde at sortere en samling data på. Algoritmer udgør rygraden i effektivt software og er dermed helt centrale for udviklingen af vores IT-baserede samfund.
– For mange algoritmer består den grundlæggende handling i at sammenligne to dataelementer, og for sådanne algoritmer finder man køretiden ved at se på den samlede mængde sammenligninger, der laves. At tælle hvor mange sammenligninger man har brugt, er derfor en klassisk problemstilling, når man taler om algoritmer, siger Rolf Fagerberg.
Et nyt perspektiv på at tælle sammenligninger
Rolf Fagerberg og hans kollegaer har foreslået, at man i stedet for at kigge på det samlede antal sammenligninger, kigger på algoritmerne set fra det enkelte elements synspunkt:
– Den klassiske måde at spørge på, er som sagt at se på, hvor mange sammenligninger der skal der bruges i alt til at sortere. Her er man ligeglade med, ”hvem” det går ud over, dvs. om der er et element, der deltager i rigtig mange af sammenligningerne, eller om sammenligningerne er mere jævnt spredt ud på elementerne. I vores artikel ser vi stedet på, hvad er det største antal sammenligninger et enkelt element i en algoritme kan risikere at være med i. Dvs. hvad det ”koster” for det enkelte element at være med i algoritmen. Dette spørgsmål er relevant i situationer, hvor hver sammenligning udgør en belastning for dataelementerne. Som i eksemplet med øl-smagningen, hvor man ved den traditionelle metode, som vises først, kan risikere pludselig ikke længere at have nok af sin favorit-øl. Et andet eksempel kunne være sport, hvor deltagere kan blive skadet, når de sammenlignes via en match, siger han.
Rolf Fagerberg pointerer, at det er overraskende, at der ikke tidligere er nogen, der har fundet netop denne problematik interessant
– Det er egentlig et ret simpelt spørgsmål vi stiller. Og netop derfor er det også forbavsende, at der ikke er nogen, der tidligere har forholdt sig på denne måde til en problematik, der sådan set har eksisteret siden 1960’erne.
Ud over selve den nye synsvinkel, udvikler Rolf Fagerberg og hans kollegaer i artiklen også en række algoritmer, som netop kan bruges til at minimere antallet af sammenligninger for de enkelte elementer og dermed bane vej for yderligere udvikling inden for IT-området.
Mød forskeren
Rolf Fagerberg er professor i datalogi på Institut for Matematik og Datalogi. Hans speciale er algoritmer og datastrukturer. Ud over forskning og undervisning er Rolf Fagerberg også optaget af at udvikle SDU's datalogiuddannelse og at tiltrække endnu flere studerende til den.