糖果派对

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 鈥漵lide鈥� 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鈥檈rne, 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, 鈥漢vem鈥� 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 鈥漦oster鈥� 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鈥檈rne.

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.