Ung datalog vinder som første dansker prestigefyldt pris
© Lars Svankjær
Findes der hurtigere algoritmer, eller er vi faktisk nået til et punkt, hvor en given udregning eller handling ikke kan foretages hurtigere? Så banalt og alligevel abstrakt kan Kasper Green Larsens forskning beskrives. Han har netop som den første dansker modtaget den prestigefyldte Presburger Award.
Forestil dig, at du har to tal: 3495 og 7895.
Hvis du blev bedt om at vælge mellem, om du helst ville plusse eller gange de to tal, og du kun måtte bruge et stykke papir og en kuglepen som hjælpemidler, så ville du nok vælge at plusse dem. Det virker nemlig umiddelbart nemmest.
Lidt karikeret er det den samme øvelse, som Kasper Green Larsen, lektor i datalogi ved Aarhus Universitet, sammen med sine kollegaer begiver sig ud på, når han undersøger algoritmers optimeringspotentiale med sine banebrydende metoder.
For selv om en computer langt fra fungerer på samme måde som en menneskelig hjerne, så handler øvelsen helt banalt om at finde ud af, om en given algoritme kan optimeres, så den kan løse et problem endnu hurtigere, end den gør i dag. Og det er det, som han netop som den første dansker har vundet den prestigefyldte Presburger Award for. Prisen gives til unge forskere under 35 år for ”fremragende bidrag inden for teoretisk datalogi”.
”Min forskning handler grundlæggende om at forstå, om det med at gange er et svært problem, eller om vores nuværende algoritme bare er dårlig. Måske kunne der findes en hurtigere måde at gøre det på, men andre gange handler det om at bevise, at der ikke findes en hurtigere udregningsmetode end den nuværende”, siger han.
Kasper Green Larsens forskning kan overføres til andre områder
Den grundforskning har Kasper Green Larsens overført til andre områder af datalogien som fx kryptering, hvor nogle kan have brug for både at gemme og tilgå data i fx en sky (cloud-løsning) hos Amazon, men her opstår der et problem, for når du tilgår den krypterede data, kan Amazon se, hvad for noget data du tilgår og dermed potentielt udlede indholdet af dine data.
Den request, man laver i sine data, kan man imidlertid også kryptere, men her opstår der så problemer, fordi ens program bliver langsommere, når man forsøger at skjule, hvad man laver. Over årene har man lavet hurtigere og hurtigere løsninger på det problem, og nu har Kasper og hans kollegaer testet, hvor stort optimeringspotentialet er på den nuværende løsning.
"Svaret er, at det faktisk ikke kan blive bedre. Det har vi bevist. Så man kan lige så godt stoppe med at forsøge at finde på bedre algoritmer", siger han.
Med andre ord er der en grænse for, hvor meget hurtigere en algoritme kan løse et bestemt problem. Som eksempel forklarer Kasper Green Larsen, at han har ført et lignende bevis for, hvor meget man kan komprimere en database af billeder, hvis man skal kunne bevare lighederne mellem billederne.
Uanset hvad billederne forestiller så er det primære formål med at forsøge at optimere algoritmen, at man kan finde det præcise punkt, hvor de ikke længere kan komprimeres mere, hvis de stadig skal kunne være søgbare. Det er typisk noget, der bliver brugt inde i maven på en søgealgoritme, som gør det nemmere at søge i en database, hvor formålet er at bruge så lidt hukommelse på din computer som muligt på at gemme en database, uden at man mister søgbarheden, forklarer Kasper Green Larsen.
Her har man allerede i 1984 ved hjælp af det såkaldte Johnson-Lindenstrauss lemma fundet en fremragende måde at komprimere billeder og samtidig beholde lige præcis nok pixel til, at man stadig kan bevare lighederne imellem billederne.
"Her har vi endnu en gang bevist, at der ganske enkelt ikke findes en bedre algoritme. Hvis man går længere ned i pixelstørrelse, end man er nået ned på nu, vil man ikke længere kunne adskille billederne fra hinanden, og man vil derfor ikke kunne søge i dem", siger han.
Hvis du blev bedt om at vælge mellem, om du helst ville plusse eller gange de to tal, og du kun måtte bruge et stykke papir og en kuglepen som hjælpemidler, så ville du nok vælge at plusse dem. Det virker nemlig umiddelbart nemmest.
Lidt karikeret er det den samme øvelse, som Kasper Green Larsen, lektor i datalogi ved Aarhus Universitet, sammen med sine kollegaer begiver sig ud på, når han undersøger algoritmers optimeringspotentiale med sine banebrydende metoder.
For selv om en computer langt fra fungerer på samme måde som en menneskelig hjerne, så handler øvelsen helt banalt om at finde ud af, om en given algoritme kan optimeres, så den kan løse et problem endnu hurtigere, end den gør i dag. Og det er det, som han netop som den første dansker har vundet den prestigefyldte Presburger Award for. Prisen gives til unge forskere under 35 år for ”fremragende bidrag inden for teoretisk datalogi”.
”Min forskning handler grundlæggende om at forstå, om det med at gange er et svært problem, eller om vores nuværende algoritme bare er dårlig. Måske kunne der findes en hurtigere måde at gøre det på, men andre gange handler det om at bevise, at der ikke findes en hurtigere udregningsmetode end den nuværende”, siger han.
Kasper Green Larsens forskning kan overføres til andre områder
Den grundforskning har Kasper Green Larsens overført til andre områder af datalogien som fx kryptering, hvor nogle kan have brug for både at gemme og tilgå data i fx en sky (cloud-løsning) hos Amazon, men her opstår der et problem, for når du tilgår den krypterede data, kan Amazon se, hvad for noget data du tilgår og dermed potentielt udlede indholdet af dine data.
Den request, man laver i sine data, kan man imidlertid også kryptere, men her opstår der så problemer, fordi ens program bliver langsommere, når man forsøger at skjule, hvad man laver. Over årene har man lavet hurtigere og hurtigere løsninger på det problem, og nu har Kasper og hans kollegaer testet, hvor stort optimeringspotentialet er på den nuværende løsning.
"Svaret er, at det faktisk ikke kan blive bedre. Det har vi bevist. Så man kan lige så godt stoppe med at forsøge at finde på bedre algoritmer", siger han.
Med andre ord er der en grænse for, hvor meget hurtigere en algoritme kan løse et bestemt problem. Som eksempel forklarer Kasper Green Larsen, at han har ført et lignende bevis for, hvor meget man kan komprimere en database af billeder, hvis man skal kunne bevare lighederne mellem billederne.
Uanset hvad billederne forestiller så er det primære formål med at forsøge at optimere algoritmen, at man kan finde det præcise punkt, hvor de ikke længere kan komprimeres mere, hvis de stadig skal kunne være søgbare. Det er typisk noget, der bliver brugt inde i maven på en søgealgoritme, som gør det nemmere at søge i en database, hvor formålet er at bruge så lidt hukommelse på din computer som muligt på at gemme en database, uden at man mister søgbarheden, forklarer Kasper Green Larsen.
Her har man allerede i 1984 ved hjælp af det såkaldte Johnson-Lindenstrauss lemma fundet en fremragende måde at komprimere billeder og samtidig beholde lige præcis nok pixel til, at man stadig kan bevare lighederne imellem billederne.
"Her har vi endnu en gang bevist, at der ganske enkelt ikke findes en bedre algoritme. Hvis man går længere ned i pixelstørrelse, end man er nået ned på nu, vil man ikke længere kunne adskille billederne fra hinanden, og man vil derfor ikke kunne søge i dem", siger han.
