Forskningens historie – Københavns Universitet

Husker du, da hukommelsen blev lagret på hulkort og hulstrimler. Dette gav jobs til de navnkundige hulledamer, der udfyldte tilværelsen med at klippe huller i kort. Metoden ruges i dag fortsat til amerikanske valg - med større eller mindre succes!

 

Forskningens historie

I instituttets tidlige fase udviklede forskningen sig især inden for tre områder: anvendelser, basisprogrammel og teori. Senere udkrystalliserede forskningen sig indenfor nogle mere specialiserede områder: Semantikbaseret programbehandling, algoritmik, distribuerede systemer, datamatsyn samt informationssystemer.

Datamatiske systemer til medicinske målinger

Fra 1969 forskede man i udviklingen af datamatiske systemer til medicinske målinger, bl.a. måling af hjernens blodgennemstrømning. Denne aktivitet førte til konstruktion af et gammakamera med indbygget minicomputer. Dette kamera muliggjorde målinger, som har givet et bedre kendskab til hjernen funktion i normal og syg tilstand. Fra et datalogisk synspunkt har dette projekt været af værdi, bl.a. som kilde til projekter af tværvidenskabelig art på anden del.

Det gav anledning til udviklingen af et makrosprog, et operativsystem til tidstro multiprogrammeret operation (VACS), modelstudier af fysiologiske systemer og grafisk databehandling. I 1977 påbegyndtes et nyt projekt inden for dette område, en enkelt-fotons emissionstomograf. Instituttet fik sammen med Rigshospitalet og Bispebjerg Hospital midler til udvikling af en enkelt-fotons emissionstomograf. Instituttet har i de seneste år samarbejdet med center for 3D-billedbehandling ved Rigshospitalet, et forskningscenter, der arbejder med rekonstruktion af tredimensionale strukturer baseret på billeddata opsamlet af MR- PET- og SPECT-scannere.

En ny forskergruppe i billedbehandling dannes på DIKU

På instituttet blev senere dannet en forskergruppe, som arbejder med mere teoretiske sider af billedbehandling, bla. visuel inferens (problemet automatisk at uddrage information fra billeder og billedsekvenser eller kunne foretage automatiske beskrivelser af billeder). I forbindelse hermed er arbejdet med skalarum, en billedrepræsentation, der populært sagt opnås ved at "udtvære" eller "sløre" billeder i varierende omfang, således at de finere detaljer udviskes, hvorved billedanalysen forsimples. De matematiske og geometriske egenskaber ved skalarumsrepræsentationen er blevet undersøgt, bl.a. i samarbejde med en forskergruppe i Utrecht.

Praktiske forsøg i billedbehandling

Der er blevet opbygget et billedlaboratorium ved Datalogisk Institut, som har været brugt til flere praktiske undersøgelser. Som et eksempel kan nævnes geometrisk kalibrering af et digitalt kamera udstyret med motoriseret optik således, at graden af zoom, fokus, og blænde kan ændres under programkontrol. Kalibreringen muliggør, at observationer (koordinater) optaget ved forskellig grad af zoom og fokus kan relateres til visuelle synsretninger. Denne kalibrering er en forudsætning for anvendelse af sensoren til visuel udforskning.

Det 3-dimensionale rum

Man har desuden arbejdet på at få bevægelig datastyret maskine til at løse problemer ved direkte input fra omgivelserne via digitale sensorer. Der benyttes rumlige sensorer der som input giver en projektion af det omgivende 3-dimensionale rum. Man må kunne modellere omgivelserne for at kunne håndtere tilbagekobling på maskinens bevægelser og på eventuelle forandringer i omgivelserne. Resultaterne kan deles i to områder. Ved at bevæge en programstyret mekanisk robot fås tidsvarierende data, det vil sige at der optages en digital film.

Den bedste udnyttelse af begrænsede ressourcer

Operationsanalyse er læren om anvendelse af matematiske modeller som led i beslutninger der søger den bedste udnyttelse af begrænsede ressourcer. Ved Datalogisk Institut valgte man tidligt at koncentrere såvel undervisning som forskning om et af operationsanalysens vigtigste hjælpemidler: de matematisk optimeringsmetoder. Ud af dette emneområde voksede naturligt fagområdet algoritmik.

Begrundelsen herfor er følgende: Datamaskiner anvendes som værktøj til problemløsning på et stadigt voksende spektrum af områder, og centralt heri er effektiviteten af de anvendte algoritmer. En algoritme er en præcis beskrivelseaf den række operationer, der med udgangspunkt i et problems data fører frem til problemets løsning i form af et resultat. Problemerne kan handle om tal, tekster, billeder, naturlige sprog, egenskaber ved programmer, praktisk planlægning og beslutning etc. Den øgede regnekraft i nutidens datamater har snarere end at dække behovet for problemløsning øget mængde og størrelse af de problemer, der ønskes løst. Effektive algoritmer spiller hermed en central rolle i at kunne udnytte det eksisterende hardware bedst muligt.

Algoritmiske studiefelter

Studiet af algoritmer omfatter traditionelt også felterne datastrukturer og kompleksitet. Da alle data skal repræsenteres i datamaskinen for at kunne bearbejdes, er datastrukturering et centralt studiefelt i forbindelse med algoritmer. Vurdering af algoritmernes ressourceforbrug i form af tid og plads, samt vurdering af et forelagt problems kompleksitet målt i ressourcebehov ved dets løsning er det andet traditionelle studiefelt. En taksonomi for algoritmer kan baseres på i hvert fald 4 kriterier: det løste problem, den anvendte metode i algoritmen, algoritmens egenskaber mht. effektivitet, og den underliggende maskinmodel.

Forskellige problemområder til og løsningsmetoder med algoritmik

Der forskes i algoritmer for vidt forskellige problemer (optimering, numerisk linear algebra, algoritmisk geometri, etc.), der arbejdes med mange forskellige grundlæggende løsningsmetoder (algebraiske, kombinatoriske, geometriske, kontinuerte), både metodernes teoretiske effektivitet og den praktiske effektivitet i form af at eksperimenter med implementerede algoritmer studeres, og der ses både på sekventielle algoritmer, parallelle algoritmer for konkrete arkitekturer, og parallelle algoritmer for maskinmodeller.

Prioritetskøer, VLSI-design og Steinertræet

Som grundlag for algoritmekonstruktion optræder ofte en matematisk model. I forbindelse hermed undersøgesprincipper for matematisk modellering i forbindelse med beslutningsstøtte ved planlægning i praksis. Indenfor algoritmik er der også arbejdet på rekonstruktion af evolutionsforløb fra genetiske afstande samt med dynamiske grafalgoritmer. Desuden er der arbejdet med prioritetskøer og på at lave registerallokering for strukturerede programmer. I 1996 har forskere fra instituttet undersøgt generering og forening af fulde Steinertræer, et problem, der har en række anvendelser i VLSI-design og netværkssyntese. På grundlag af nye geometriske og kombinatoriske tests lykkedes det at løse eksempler med op til 150 punkter.

Maskinnært programmel

Et andet forskningsområde i instituttets tidlige fase var maskinnært programmel. Her udvikledes tegneprogrammel, en makrooversætter og terminalsoftware, der var ret avanceret for den tid. Senere udvikledes MIK, et korutineorienteret styresystem til en mikrocomputer. Systemet kunne afvikle prioriterede reentrante korutiner og omfattede mekanismer til indbyrdes synkronisering og kommunikation, synkronisering med sand tid og retningslinier for behandling af ydre enheder.

Nye begreber: Beskyttelse og nedlæggelse

Ligeledes arbejdede man med afklaring af begreberne beskyttelse og nedlæggelse. Arbejdsmetoden bestod i at definere en "kerne" (d.v.s et sæt grundoperationer til at opbygge operativsystemer). Dernæst anvendtes kernen til at konstruere de vanskelige dele af et operativsystem. Resultaterne vurderedes, begrebsapparatet blev revideret og "kernen" forbedret tilsvarende. Senere blev kernekonstruktion en del af undervisningen på førstedelskurset i materiel.

Et nyt forskningsområde opstår: Distribuerede systemer

Man kan se udviklingstendensen indenfor maskinnært programmel som førende til forskningen indenfor distribuerede systemer, som består af selvstændige, samarbejdende datamater og de spiller en stadigt voksende rolle efterhånden som hurtigere og kraftigere netværk muliggør større udveksling af data og processer.

Og et nyt programmeringssprog fødes: Emerald

Der blev udviklet et objekt-orienteret programmeringssprog, Emerald, i samarbejde med University of Washington. Der er blevet forsket i udvikling af nye paradigmer og mekanismer for distribuerede operativsystemer, fx data- og processflytninger mellem datamater med forskellige maskinarkitekturer, objektlokalisering, integration af database forespørgselssprog med objekt-orientering, og på højhastinghednetværk. Desuden har man undersøgt problemerne omkring små, distribuerede mobile datamater, der er forbundet med varierende former for datatransmissionsudstyr, fx lokalnet, telefonnet eller mobiltelefon.

Støttet af statens forskningsråd er udført forskning vedrørende højhastighedsnetværk og dets brug til fordelt fælles virtuelt lager, dvs. at flere datamater er fælles om et stort addresserum, men at selve lageret er fordelt på de enkelte maskiner. Et højhastighedsnetværk baseret på ATM teknologi er blevet opbygget omkring otte meget hurtige RISC processorer og der er der blevet indrettet et laboratorium til både ATM udstyret og til det mobile udstyr.

Pascal til UNIVAC 1100

Instituttet udviklede i den tidlige fase en oversætter til programmeringssproget Pascal for maskinen UNIVAC 1100. Herved blev skabt et godt udgangspunkt for praktisk afprøvning af nye sprogfaciliteter. Denne oversætter blev uddelt til en række udenlandske universiteter.

Semantikbaseret programmeringssprog

Senere blev programmeringssprog og problemerne forbundet hermed et større forskningsområde på instituttet, i form af semantikbaseret programbehandling. Semantikbaseret programbehandling omhandler programmeringssprog, herunder behandling af programmer som dataobjekter med henblik på analyse, implementering, transformering, syntese og tidsvurdering samt typebegrebets teori og anvendelse.

Emnet er relevant for konstruktion af oversættere og fortolkere samt programafprøvning og programoptimering Der er blevet lagt vægt på, at de udviklede teknikker er automatiske og at de er velfunderede i semantikken for et programmeringssprog.

Mellem Teori og Praktik

Forskningen på instituttet ligger på grænsen mellem teori og praksis: teorier afprøves på datamaskiner og praktiske eksperimenter fører ofte til nye teoretiske undersøgelser. Typer er blevet studeret, dels som værktøj til at formindske lagerforbruget, bl.a. i funktionssproget Standard ML, dels for samtidigt at opnå fleksibiliteten ved utypede sprog og effektiviteten og sikkerheden ved typede sprog, og dels ved effektivitetsproblemer i partiel evaluering af typede programmeringssprog.

Teoretiske undersøgelser og praktiske eksperimenter er blevet foretaget med anvendelse af partiel evaluering på praktiske problemer. Der er udført forskning vedrørende termineringsproblemer i partiel evaluering samt stærkere programtransformationer. Kompleksitetsproblemer er blevet studeret for programmeringssprog.

Samarbejde med DTU

Der arbejdes med realisering af en højparallel grafreduktionsmaskine i samarbejde med Mikroelektronikcenteret på DTU. Indenfor området er der blevet publiceret flere bøger. Den sidste, en lærebog om kompleksitet og beregnelighed, "Computability and Complexity From a Programming Perspective", er udgivet på MIT Press forlaget i U.S.A.

Map Theory

En teori, der forener datalogi og klassisk matematik, "Map Theory", er blevet udviklet på instituttet.