03. juli 2015

Eva Rotenberg vinder Årets Specialepris i Datalogi

Specialeprisen 2015, Eva Rotenberg, Grafalgoritmer og -datastrukturer

Årets Specialepris, som uddeles af Dansk Selskab for Datalogi og DANSK IT, blev dette år vundet af datalogistuderende Eva Rotenberg for hendes speciale inden for emnet dynamiske grafer. Specialet har resulteret i en datastruktur, der tillader at en bruger kan indsætte og slette kanter i en plan graf uden at ændre på denne egenskab.

Torsdag den 18. juni afholdte Dansk Selskab for Datalogi og DANSK IT deres årlige Specialeprisudrækkelse, og vi er på DIKU stolte over årets vinder, Eva Rotenberg. Hun var nomineret for sit speciale Maintaining alterable planar embeddings of dynamic graphs, som omhandler problemet med at tilføje og slette kanter i en plan graf.

Den nye funktion hedder flip

En plan graf er en graf i planet, hvor ingen kanter krydser hinanden, undtagen i deres to endepunkter. En plan graf kan ofte tegnes på flere forskellige måder i planen. Hver af disse kaldes en "indlejring". Den nye datastruktur, Eva har udviklet, understøtter at man sletter og indsætter kanter af grafen, uden at lave om på indlejringen, og så grafen endnu er plan. Dette var understøttet tidligere i en lignende datastruktur fra 1993.

Som noget helt nyt tillader datastrukturen brugeren at lave om på indlejringen, altså måden hvorpå grafen tegnes i planen. For at ændre på indlejringen, udføres et flip, hvor en delgraf vendes på hovedet. For at kunne udføre flippet, må delgrafen kun hænge sammen med resten af grafen i højest to punkter. Hvis en graf kan tegnes på flere forskellige måder i planet, kan man komme fra den ene til den anden ved en række af disse flips.

Højt teknisk niveau

I indstillingen til prisen blev Eva især rost for sit høje tekniske niveau, men også for sin effektive og forståelige præsentation af sit emne.

Det blev fremhævet som imponerende, at den nye funktion, flip, kunne understøttes i samme hurtige køretid, O((log n)^2), samt kantindsættelser og -sletninger, som igen understøttes i samme hurtige køretid, som den tidligere lignende datastruktur fra 1993, samt at hendes resultater var på niveau med absolutte topforskere, Henzinger og Fredman.

Godt niveau over hele linjen

Eva var først og fremmest stolt over, at være nomineret til prisen:

"De andre nominerede specialer lød alle sammen rigtigt spændende og gode," forklarer hun og fortsætter "Der var specialer indenfor vidt forskellige emner fra mange universiteter over hele landet."

Eva har siden hun afsluttede sit speciale i januar 2014 arbejdet videre med emnet i samarbejde med datalogistuderende Jacob Holm, hvilket resulterede i en artikel på konferencen STACS. Hun er på nuværende tidspunkt ansat som Ph.D. studerende hos Mikkel Thorup og Christian Wulff-Nilsen i APL Sektionen på DIKU.

Tidligere års vindere

Det er ikke første gang, DIKU studerende har vundet Dansk Selskab for Datalogis specialepris. I 2008 delte tre studerende førstepladsen, James Avery med specialet The Generalized Sturmian Method: Development, Implementation and Applications in Atomic Physics og René Truelsen og Kristine Slot med specialet Content-aware video editing in the temporal domain, og året før gik den til Mohammad Jowkar for hans speciale om Cell-processorer.

Ligeledes har hendes kollega i APL Sektionen Rasmus Fonseca vundet i 2009 for hans speciale med titlen Ab Initio Protein Structure Prediction using Bezier Curve Representation.

Faktisk var den første vinder nogensinde tilbage i 1994, Klaus Harbo, også fra DIKU, og der har været adskillige andre DIKU studerende blandt vinderne herimellem.