Date: 09 Jan 2004 From: jyrki@diku.dk Subject: PE-lab: Det forgangne år Tak for alle! \Jyrki Følgende personer har været involveret i gruppens arbejde: Christopher Derek Curry (specialestuderende) Andrei Bjarke Moskvitin Josephsen (kandidatstuderende) Claus Jensen (specialestuderende) Jyrki Katajainen (gruppeleder) Jeppe Nejsum Madsen (specialestuderende) Jesper Holm Olsen (specialestuderende) Tomi Armas Pasanen (samarbejdspartner fra Helsinki universitet) Jakob Gregor Pedersen (kandidatstuderande) Frederik Rønn (specialestuderende) Søren Christian Skov (specialestuderende) Christian Ulrik Søttrup (kandidatstuderande) Fabio Vitale (udvekslingsstuderende fra "the University of Insubria"). Forskningen, som er udført i PE-labs regi, breder sig over flere områder, fra forretningsmodellering, værktøjsudvikling og empirisk algoritmik til teoretisk algoritmik. Der er kommet betydningsfulde resultatet fra følgende seks projekter: * Omskabelse af en uddannelsesinstitution Bogmanuskriptet "Reengineering a university department", som blev færdig i november, fokuserer på datalogiundervisningen og hvordan undervisningen kan forbedres ved at tilpasse den til de studerende individuelle indlæringspræferencer. Som udgangspunkt anvendes Myers Briggs Type Indicator (MBTI) til at bestemme en persons præferencer for opfattelse og vurdering. Viden om sammenhængen mellem MBTI og indlæringspræferencer er siden anvendt i udarbejdelsen af en strategi til en helt ny form for datalogiundervisning ved Datalogisk Institut. [Christopher, Jyrki] * Sammenligningsværktøj Første versionen af CPH STL værktøj benchmark blev frigivet på internettet i starten af året. Værktøj blev udviklet for at det skulle være let at måle eksekveringstiden af sine programmer. Det er lykkedes vældig godt; tidligere tog det dagevis at udføre et eksperiment og nu kan det gøres på få timer. I løbet af året er værktøjet blevet udvidet til også at kunne måle antallet af instruktioner, cachekiksere og sidefejl. [Christian, Jakob, Jyrki] * Cache-oblivious algoritmer i praksis Analyse af algoritmer under den ideelle cachemodel, hvor man antager at cachehukommelsen udnytter den optimale blokerstatningsstrategi, begyndte i 1999. Målet med den tidligare teoretiske forskning har været at udvikle algoritmer som opfører sig optimalt på alle hukommelsesniveauer. Vi har testet de nyudviklede metoder til klassiske søgning- og sorteringsogaver. Resultaterne har overvejende været negative: De nye metoder er som oftest meget langsomme. Det er nødvendigt med en betydelig forskningindsats for at forbedre disse metoder inden de kan anvendes i praktiske applikationer. [Andrei, Frederik, Jesper, Søren] * Sandheden om hobe Ifølge vores bedste overbevisning er hobe de eneste datastrukturer som udfylder de strenge effektivitetskrav som C++ standarden stiller til hobeoperationer. De seneste artikler om hobenes praktiske effektivitet giver modstridende resultater. Vi har under vores eksperimenter sammenlignet næsten alle kendte varianter af hobe publiceret efter Williams artikel fra 1964. Det er meget svært at slå Williams' binære hobe. Der har absolut ikke været nogen fremskridt indenfor dette område i de sidste 40 år. [Claus, Fabio, Jyrki] * Interaktiv begrænsningssatisfaktion Mange praktiske problemer kan modelleres som begrænsningssatisfaktion problemer. Problemet er NP-svært og den interaktive variation, hvor man skal løse problemet online efter ændringer af gældende begrænsninger, er beregningsmæssigt meget krævende. Alligevel har det været overraskende hvor store probleminstanser vi kan løse interaktivt. Arbejdet er blevet udført i samarbejde med Array Technology A/S. [Jeppe] * Generering af tilfældige data strukturer Der er blevet udviklet metoder for at generere tilfældige binære søgetræer og hobe, selvom inddata for genereringsalgoritmer er vilkårlige. Motivationen for denne forskning har været at transformere gamle algoritmer, som er effektive hvis deres inddata er tilfældige, til randomiserede algoritmer, hvor randomiseringen sker i selve algoritmerne og effektiviteten er garanteret uden nogle antagelser om inddata. [Jyrki, Tomi]