Årsberetning 1993

Forskningsvirksomhed

Ud over en række mindre forskningsområder har instituttet fem hovedindsatsområder: Semantikbaseret programbehandling, optimering, parallel programmering og distribuerede systemer, datamatsyn samt systemarbejde.

Semantikbaseret programbehandling

Området drejer sig om programmeringssprog, herunder behandling af programmer som dataobjekter til analyse, implementering, transformation, syntese og tidsvurdering samt typebegrebets teori og anvendelse. Emnet er relevant for konstruktion af oversættere og fortolkere samt programafprø vning og optimering. Arbejdet ligger på teori-praksis grænsen: teorier afprø ves på datamaskinen; og praktiske eksperimenter fører ofte til nye teoretiske undersøgelser. Der lægges vægt på, at de udviklede teknikker er automatiske, og at de er velfunderede i semantikken for et programmeringssprog.

I 1993 er nye teoretiske resultater blevet bevist, nye og stærkere systemer til programoptimering er blevet udviklet, og eksperimenter med anvendelse af partiel evaluering til praktiske problemer er blevet foretaget. Flere af resultaterne formindsker afstanden mellem teori og praksis. Desuden er en bog om partiel evaluering blevet færdiglavet og publiceret.

I 1993 var DIKU vært for ACM konferencerne Functional Programming and Computer Architecture og Partial Evaluation and Semantics-Based Program Manipulation med proceedings, en workshop i State in Programming Languages og et møde af IFIP Working Group 2.8 (Neil D. Jones, Nils Andersen, Mads Tofte, Torben Mogensen, Mads Rosendahl, Fritz Henglein, Anders Bondorf, Christian Mossin, Knud J. Jørgensen, Kristoffer Høgsbro Rose, Lars Ole Andersen, David Sands og Morten Welinder).

En bog om partiel evaluering er blevet færdiglavet og publiceret. Flere tidligere metoder til automatisk programforbedring er blevet forenet: partiel evaluering, "deforestation" og "supercompilering". Ved ACM Symposium on Theory of Computing er for første gang fremlagt bevis for, at problemløsningsevnen strengt forøges, når man ganger beregningstiden med en konstantfaktor. Dette resultatet indsnævrer en kløft mellem teori og praksis. Inviterede foredrag om disse emner blev holdt ved flere udenlandske konferencer og universiteter (Neil D. Jones).

Undersøgelserne af transformationsmetoder til forbedring af programmer har ført til en ny beskrivelse af Stephen A. Cooks simulering af to-vejs stak-automater i lineær tid. Den nye beskrivelse viser samtidigt, hvordan metoden kan generaliseres til vilkårlige programmer, der bruger stak, og hvordan visse programforbedringer, herunder transformationerne til lineære beregningsmetoder ud fra de rekursive definitioner af Fibonaccital eller af binomialkoefficienter, kan ses som specialtilfælde (Nils Andersen).

Hovedvægten har været lagt på videreudvikling af det arbejde om regions-baseret implementation af Standard ML, som blev på begyndt i 1992. Regionsinferenssystemet er blevet generaliseret til at tillade regionspolymorfi i rekursive funktioner og denne udvidelse er blevet bevist korrekt. Med støtte fra DART projektet er et større prototypesystem blevet bygget og grundigt afprøvet. De opnåede måleresultater indikerer, at regionsbaseret oversættelse vil kunne føre til en Standard ML implementation med aggressiv lagerpladsgenbrug (Mads Tofte).

Der er arbejdet med generalisering af et arbejde fra slutningen af 1992 om specialisering af datastrukturer. I den forbindelse er indledt samarbejde med Dirk Dussart, en ph.d- studerende fra Belgien, som står for implementering af en prototype baseret på en metode udarbejdet i fællesskab. Derudover er arbejdet på programtransformation og implementering af funktionsprogrammeringssprog samt konstrueret et brugbart syntaksanalyseværktøj i et dovent funktionsprogrammeringssprog. Dette værktøj er blevet hentet ad elektronisk vej af over hundrede personer (Torben Mogensen).

Der er arbejdet med metoder til implementation af abstrakt fortolkning. Herunder er der specielt studeret metoder til at finde fikspunkter af højereordens funktioner over endelige gitre. Desuden er sammenhængen mellem fikspunktalgoritmer og top-ned programanalyser undersøgt (Mads Rosendahl).

En mere generel undersøgelse af typesystemer som specialiserede programlogikker for programmeringssprog er i gang under Fritz Henglein og har ledt til udformningen af en coercionkalkuleteori. Denne ligger til bunds for nye teoretiske resultater i repræsentationsoptimering for polymorfe programmeringssprog (med Jesper Jørgensen) og en robust typeteoretisk formulering af polyvariant bindingstidsanalyse (med Christian Mossin). En SML-implementering og integration i ML-Kittet af dynamisk typeanalyse for programmeringssproget Scheme er undervejs (med Jakob Rehof). Som led i dette projekt er en fortolker færdiggjort (Fritz Henglein).

En helt ny udgave af systemet Similix er udviklet; systemet behandler nu partielt statiske strukturer og baseres på nye effektive programanalyser, der kører i lineær tid. Semantiske "action"-specifikationer er blevet implementeret ved hjælp af systemet. Der arbejdes på "continuation"-baseret partiel evaluering og på et eksperimentelt system til effektiv multipel "currying" af programmer; i begge tilfælde skrives "cogen" i hånden for at undgå selvanvendelse (Anders Bondorf).

Afsluttet arbejde med partiel evaluering af generelle parsere. En polymorf bindingstids-analyse er udviklet. Analysen er bevist korrekt m.h.t. sprogets semantik, og bevist partielt komplet - d.v.s. udfoldning af definitioner vil ikke forbedre analysens resultat. Arbejde med effektive algoritmer er påbegyndt. Endvidere arbejdes på en oversættelse fra doven PCF til et tilsvarende sprog med eksplicitte lagerallokerings- og deallokerings-kommandoer (Christian Mossin).

En typeinferens-baseret analyse og algoritme til begrænsning af "boxing" i funktionsprogrammeringssprog er udviklet. Der arbejdes på at udvikle en effektiv algoritme til denne analyse, at klarlægge sammenhængen mellem denne og konventionel "value/data flow analysis" og udvikle nye analyser/algoritmer baseret på de samme metoder til f. eks. "closure"-analyse og undertypeinferens. Der arbejdes også med automatisk generering af optimerende programspecialisatorer ud fra fortolkere (Knud J. Jørgensen).

Der er arbejdet på ph.d.-projektet "Graphical Semantics of Sharing in Programming Languages" hvor materialet er klar til den første tredjedel, som beskriver, hvorledes deling er en naturlig optimering af "naive" programmeringssprog. Elleve måneder er benyttet til ophold hos John Hughes og Thomas Johnsson paa Chalmers Tekniska Högskola i Göteborg paa et NorFA (SNF) rejsestipendium (Kristoffer Høgsbro Rose).

Arbejdet med udviklingen af C-Mix, en automatisk partial evaluator for C, er fortsat. Anvendelse af en ny transformationsmetode har muliggjort behandling af hele ANSI-C. Endvidere udvikles analyser af pointer variabler (Lars Ole Andersen).

Koordinationssprog er en ny klasse af parallelle sprog, hvor kommunikation mellem delprogrammer foregår gennem et delt lagerområde (modsat delte globale variable). Et eksempel på et sådant sprog er Gamma, opfundet af Le Metayer og Banâtre. Sprogets semantiske grundlag, programlogik og statisk programanalyse undersøges. Desuden arbejdes der med total korrekthed af partiel evaluering fra en semantisk model af bindingstider og betingelser for total korrekthed af foldningsbaserede transformationer i højereordens funktionelle sprog (David Sands).

En artikel til konferencen ESOP'94 er skrevet og indleveret. Det undersøges i øjeblikket, om man kan anvende partiel evaluering på programmet Hol (Higher Order Logic - et program for formel bevisførelse) (Morten Welinder).

Optimering

Optimering handler om formulering og løsning af beslutningsproblemer, hyppigt i forbindelse med bedst mulig udnyttelse af knappe ressourcer. Anvendelsesområderne omfatter mange grene af samfundet, i privat såvel som offentlig regi.

Forskningen ved DIKU centrerer sig om udvikling og analyse af algoritmer til nye eller allerede kendte problemstillinger, om løsning af planlægningsproblemer i praksis, om effekten ved brug af paralleldatamater, om udnyttelse af begreber som fx. simuleret nedkøling og neurale netværk, samt om systematisering og formidling af dele af fagområdet. Desuden undersøges problemer med to eller flere kriterier samt problemer indenfor beslægtede områder som grafteori og kombinatorik (J. Krarup, J. Clausen, P. Winter og D. Pisinger).

Optimering og operationsanalyse: Artikler om hhv. todelt parring of analytiske løsninger af et ikke-lineært `rygsækproblem' er afsluttet. En klasse såkaldte projektive planer er fundet ved den grådige algoritme. Med udgangspunkt i bl.a. Torricellis arbejder fra 1644 søges givet en oversigt over problemer, der synliggør begrebet dualitet. En oversigt over matrixalgoritmer til bestemmelse af korteste veje er ligeledes under udarbejdelse (J. Krarup).
Algoritmisk geometri: Der har været arbejdet med at undersøge, hvordan algoritmisk geometri (eng. computational geometry) kan anvendes til løsning af nogle grundlæggende netværkssyntese-problemer. Arbejdet har været specielt fokuseret på brugbarheden af multidimensionale søgetræer og Steiner visibilitetsgrafer i forbindelse med hhv. den omrejsende sælgers problem og Steinerproblemet (Pawel Winter).
Optimeringsproblemer: Forskningen vedrørende løsning af svære Knapsack-problemer er fuldført i foråret med en artikel om egnede løsningsmetoder. Herefter er undersøgt problemet at identificere den mindste delmængde elementer, der skal til for at løse Knapsack problemet optimalt (resultater blev fremlagt på NOAS'93 konferencen), som senere er generaliseret til Multiple-Choice Knapsack problemer. Arbejdet har resulteret i en artikel om emnet. P.t. arbejdes med yderligere generaliseringer indenfor familien af Knapsack problemer (David Pisinger).

Parallel programmering og distribuerede systemer

Paralleldatamater med mange processorer og netværk af selvstændige, samarbejdende datamater spillere en stadigt voksende rolle ved løsning af store og vigtige problemer. Udviklingen af styresystemer, programmeringssprog og algoritmer til effektiv udnyttelse af paralleldatamater og distribuerede systemer er derfor essentiel.

Der er arbejdet med udvikling og implementation af programmeringssproget Emerald, der er baseret på objekt-begrebet, som muliggør indkapsling af data, så de kun kan manipuleres med veldefinerede operationer. Emerald er beregnet til programmering af distribuerede systemer. Det anvendes i forbindelse med forskningen i distribuerede objekt-orienterede systemer med fokus specielt på emnerne distribueret spildopsamling, objekt lokalisering, integration af database-forespørgselssprog med objekt-orientering (herunder persistens af objekter), og på objekter i netværk med flere end 10⁶ datamater. Desuden ses på problemerne omkring små, distribuerede mobile datamater.

Der er påbegyndt forskning omkring 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.

Forskningen i generelle principper for konstruktion og analyse af algoritmer omfatter: parallelle algoritmer, datalogisk geometri, datastrukturer og datakompression samt metoder til simulering af paralleldatamater.

Forskningen i konstruktion og analyse af algoritmer til løsning af kombinatoriske optimeringsproblemer har fokuseret dels på distribuerede algoritmer til løsning af beregningsmæssigt mindre krævende problemer (P-problemer), dels på undersøgelse af den generelle anvendelighed af en simpel parallel variant af branch-and-bound algoritmen til løsning af beregningsmæssigt krævende problemer (NP-komplette problemer).

Der arbejdes på flere fronter med grafreduktionsmaskiner: parallel- og seriel-simulatorer for grafreduktionsmaskiner er under udvikling, der arbejdes med parallellisme, funktionsprogrammering og wavelets i forbindelse med numeriske beregninger og der arbejdes paa at udvikle et matematik-agtigt funktionsprogrammeringssprog baseret paa tidligere forskning. Der er endvidere blevet defineret grænseflader, der skal muliggøre integration af resultaterne.

Arbejdet med programmering af fin-kornet parallelle datamater er foreløbig sat i bero, idet hovedpersonen bag projektet har opnået et 18 måneders EU Research Fellowship til arbejde med distribuerede systemer og distribueret virtuelt lager på universitetet i Kaiserslautern, Tyskland.

Der er udviklet parallelle integrationsmetoder til numerisk løsning af systemer af sædvanlige differentialligninger med struktur. Endvidere arbejdes der med parallelle metoder til løsning af systemer af lineære ligninger, bl. a. med henblik på at kunne parallellisere traditionelle integrationsmetoder effektivt. (Stig Skelboe, Eric Jul, Birger Andersen, Jens Clausen, Klaus Grue, Jyrki Katajainen, Niels Chr. Juul, Per Laursen, Jesper Larsson Träff, Martin Funk Larsen, Povl Koch og Niels Elgaard Larsen).

Parallelle integrationsalgoritmer: Meget store systemer af sædvanlige differentialligninger kan ofte betragtes som en samling løst koblede delsystemer. Ved parallel numerisk integration kan de enkelte delsystemer løses separat indenfor ét tidsskridt. Mellem hvert tidsskridt udveksles information for at sammenkoble delsystemerne. Der er arbejdet med forskellige teknikker til samtidig at forbedre den opnåede nøjagtighed (Stig Skelboe).; Der er arbejdet med med parallelisering af numeriske algoritmer ved brug parallelle grafreduktionsmaskiner. Der er implementeret og foretaget målinger (specielt måling af paralleliseringsgraden) af følgende algoritmer: 1) klassiske numeriske algoritmer, 2) numeriske algoritmer, som har vist sig at køre godt på de almindelige parallelle computere (som f.eks. hyperkuben) og 3) algoritmer til løsning af strømningsligninger (Martin Funk Larsen).; Placering af afdelinger med indbyrdes kommunikation, så den samlede kommunikationsomkostning minimeres er et klassisk "hårdt" problem. I forlængelse af tidligere arbejde udvikles en parallel, søgningsbaseret algoritme herfor til DIKU's MEIKO-paralleldatamat. Denne baseres dels på nyudviklede grænseberegningsstrategier, dels på udnyttelse af afledt information i hver knude i søgetræet. (Jens Clausen, Søren Holm, Handelshøjskolen i Århus).; Arbejdet med parallelle Branch and Bound algoritmer er fortsat, og i hovedtræk afsluttet. Resultaterne antyder, at disse nye - meget enkle - algoritmer er stort set lige så effektive som traditionelle - mere komplicerede - algoritmer. Ydermere er det blevet forsøgt at genanvende dele af det algoritmiske "skelet" til en parallel Simuleret Udglødning algoritme. Foreløbige resultater tyder ogsaa her på, at gode resultater kan opnås selv med ret enkle strategier for parallelisering (Per Laursen).; Der har været arbejdet med sekventielle kombinatoriske algoritmer. Dels er der fundet påviseligt effektive algoritmer for følgende problemer: "maximum agreement sub-tree problem for evolutionary trees" og "construction of the immediate subsumption tree for simple binary pattern forests". Det første problem har betydning indenfor datalogisk biologi, og det andet problem var en flaskehals for en række programmeringssprogssystemer. Derudover er der introduceret de første algoritmer for automatisk eliminering af tvetydighed i kontekstfrie grammatikker. Artikler om disse resultater er sendt til de relevante konferencer (Mikkel Thorup).; Der er arbejdet videre med implementation af korteste-vej algoritmer og afprøvet forskellige typer distribuerede algoritmer, synkrone og asynkrone, på DIKU's transputersystem. Asynkrone algoritmer synes at være mest velegnede til implementation på distribuerede systemer uden delt lager. Desuden er der arbejdet med parallelle og distribuerede "maximum flow" algoritmer. Der er opnået lovende resultater med en algoritme fra litteraturen kombineret med en ny heuristik. Disse arbejder vil udgøre en væsentlig del af en ph.d.-afhandling. (Jesper Träff).
Objektorienterede distribuerede systemer: Det objekt-orienterede programmeringssprog, Emerald, der oprindeligt var udviklet til lokalnet, er udvidet således, at det kan køre på globale net -- processer og data kan frit flyttes jorden rundt. Desuden er der arbejdet med at kunne flytte processer fra maskiner af en arkitektur over til en anden arkitektur -- imens processer kører (I samarbejde med B. Steensgaard-Madsen, Microsoft Research). Et nyt projekt undersøger muligheder for distribueret lager baseret på nye hurtige net og 64-bit processorer. Sammen med forskere på AUC undersøges udvikling af real-time process kontrol programmel (med støtte af STVF). I samarbejde med Team Danmark undersøges nye metoder og programmel til "Computer Aided Flight" ifm. satellitnavigationssystemet GPS (Eric Jul).; Licentiatafhandlingen Comprehensive, concurrent and robust garbage collection in the distributed object-based system Emerald er afsluttet og forsvaret. Den implementerede prototype udmærker sig ved at opsamle alt spild i et kørende distribueret system uden at hele systemet behøver at være tilgængeligt samtidigt (robusthed) (Niels Chr. Juul); Som ph.d.-projekt arbejdes med højtydende distribuerede operativsystemer, specielt for nye microprocessorer stort adresserum ( 2⁶⁴ ), der gør det muligt afskaffe den traditionelle proces-abstraktionen og identificere alle data ved en entydig virtuel lageradresse (et uniformt adresserum). Derved opstår nye problemer, f.eks. lageradministration og beskyttelse af delte data. Under udarbejdelse er designet af et nyt højtydende distributeret operativsystem, Carlsberg, baseret på et objekt-baseret uniformt adressrum, fin-kornet parallelisme, og en netværksgrænseflade med minimale administrationsomkostninger (Povl Koch).; Som ph.d.-projekt arbejdes med objektorienterede, distribuerede databaser. Der udvikles en prototype af et databasesystem i Emerald. Der arbejdes dels med søgesprog, dels med parallitet og transaktioner. Søgesproget udmærker sig ved at være fuldt objekt-orienteret og integreret med Emeralds typesystem (Niels Elgaard Larsen).; Der er udført forskning omkring samspillet mellem mellem fysisk distribuerede systemarkitekturer og det programmel, som styrer dem. En række cache coherency protokoller er simuleret og evalueret. Der er udviklet et multiprocessor C++ bibliotek, som giver mulighed for dataflow scheduling mekanismer, der anvendes til undersøgelse af object-affinity scheduling og hurtig function shipping (Robert Fowler).; I et EU-financieret arbejde på universitet i Kaiserslautern, Tyskland, søges udviklet en generel programmeringsmodel for løst koblede distribuerede systemer. Den centrale problematik er lagerkonsistens, som vil blive vanskeligere at opretholde i fremtiden, hvor kommunikationsforsinkelser bliver større og chancen stiger for at (evt. mobile) dele af et stort distribueret system er uden forbindelse til resten af systemet. I et sådant miljø må lagerkonsistens opgives og en radikal ny programmeringsmodel er nødvendig. (Birger Andersen).
Konstruktion og analyse af algoritmer: Forskningen i algoritmik (konstruktion og analyse af sekventielle og parallelle algoritmer) er fortsat. Aktive forskningsområder er in-place algoritmer til sortering, geometriske algoritmer (relativ naboskabs-grafer) og parallel algoritmer til sortering og bestemmelse af konvekse hylstre (Jyrki Katajainen).

Datamatsyn

Et af målene med forskningen i datamatsyn er udvikling af metoder til automatisk genkendelse af 3D-objekter og 2D-figurer ud fra deres form. Løsningen af dette problem er af stor teoretisk betydning, men har også praktisk interesse. Som et praktisk eksempel kan nævnes udvikling af metoder til automatisk genkendelse af bogstaver i en tekst, således at man kan indlæse teksten i en datamaskine ved at pege på den med et TV-kamera. Som bekendt findes i dag OCR-maskiner og OCR-programmer til scannere til indlæsning af tekst, men de kræver høj opløsning i indscanningen og i reglen også at det benyttede skriftsnit (typefont) er kendt. Hvis figurernes udstrækning er lille sammenlignet med billedopløsningen kan metoden ikke anvendes. Det er f.eks. umuligt at segmentere tegn indlæst ved lav opløsning som gråtonebillede ved hjælp af gængse kantdetektorer.

Der arbejdes bl.a. med metoder til genkendelse af figurer og objekter ved hjælp af evidensvægtning (modelbaseret objektgenkendelse). Det vil sige at finde metoder til at vægte de målinger eller parametre, man kan uddrage fra billeder, således at man opnår den størst mulige klassifikationssikkerhed.

Den her omtalte forskning er en del af visiongruppens forskning i active vision, d.v.s. opbygning af sceneforståelse ved hjælp af aktivt bevægede kameraer med reduceret synsfelt (fovea). Et hovedmål her er at kunne opfatte de væsentlige sceneelementer med mindst mulig beregning (Peter Johansen, Søren Olsen, Jens D. Andersen, Jens Arnspang, Knud Henriksen, Klaus Hansen og Mads Nielsen).

Bestemmelse af bevægelse: I bestræbelsen på at reformulere centrale paradigmer indenfor datamatsyn er direkte metoder til etablering af time to contact blevet studeret. Teknikkerne udmærker sig ved at benytte et minimum af kamerakalibrering, at basere sig på enkle mål i billedsekvenser og ved eliminering af skaleringsproblemer indenfor datamatsyn. Eksperimenter viser, at de udviklede estimater er overordentlige robuste (Jens Arnspang).; Forskningen i metoder til bestemmelse af en ret linies 3-dimensionale orientering udfra bevægelsesinvarianter er fortsat. Prototyper af systemer til automatisk bestemmelse af en linies tidsvarierende orientering udfra en sekvens af billeder optaget med et CCD-kamera er under udvikling, og de foreløbige resultater ser lovende ud. I forbindelse med repræsentation af en 3 dimensional scenes geometri er en hierarkisk objektorienteret datastruktur under udvikling. (Knud Henriksen).
Mønstergenkendelse: Metoder til automatisk genkendelse af objekter undersøges og sammenlignes. Via et robotstyret TV-kamera modtager en datamaskine billeder, f.eks. af en trykt tekst, som maskinen skal læse. Et program prøver at finde den optimale fortolkning og beder evt. om flere billeder. En klasse af metoder tager sigte på hurtig genkendelse af de enkelte billedkomponenter baseret på analyse af et lille centralt billedudsnit (en fovea) (Jens Damgaard Andersen).; Et alternativ er baseret på at beregne den minimale beskrivelse af maskinens inddata. I sin fulde generalitet er den minimale beskrivelse ikke mulig at beregne. Hvis man imidlertid begrænser den notation i hvilken den minimale beskrivelse kan udtrykkes kan man opnå at den kan beregnes effektivt mod at maskinen til gengæld kun kan genkende enkle mønstre (Peter Johansen).
Aktiv vision: En række metoder til kalibrering af en optisk-mekanisk robot er udviklet og sammenlignet. Kalibreringen er fundamental hvis robotten skal anvendes til visuel udforskning eller andre metriske opmålinger. Emneområdet robust estimation er studeret med henblik på anvendelse i billedanalyse, hvor grove fejl i de indledende faser ofte får efterfølgende analyser til at fejle (Søren I. Olsen).
Kantdetektorer: Til test og evaluering af kantdetektorer er der blevet udviklet et sæt syntetiske billeder med veldefinerede egenskaber, med tilhørende sæt af billeder med referencekanter. Der er i denne sammenhæng arbejdet med programmel til kvantitativ evaluering af visse mål for kvaliteten af kantdetektorer. Sættet af billeder giver herudover mulighed for en subjektiv kvalitativ vurdering. Målet er at udvide sættet med støjfyldte billeder, og at udvikle metoder til kalibrering af kantdetektorer (Klaus Hansen).
Regularisering: Forskning indenfor området regularisering i datamatsyn er blevet udført. Specielt er brugen af forhåndsviden blevet analyseret, således at statistiske modeller af en scene kan benyttes til at finde den mest sandsynlige rekonstruktion udfra et stereobilledpar. Metoder til at uddrage denne viden og metoder til at benytte denne viden i form af algoritmer er blevet udviklet. (Mads Nielsen).
Musikinformatik: Musikinformatik er læren om datastrukturer og processer, som kan modellere og evt. understøtte musikudfoldelse. Humaniora har igennem århundreder beskrevet musik skematisk, historisk og verbalt. Eftersom næsten alle er enige om sådanne beskrivelser med alle de benyttede tillægsord, må disse kunne måles i de foreliggende datastrukturer, det være sig analoge mikrofonsignaler eller symbolsekvenser fra moderne instrumenter. Vi har udviklet algoritmer og neuralnet til eksperimenter med automatisk harmonisering samt klassificering af monofoniske melodistrofer og af akustiske instrumenter (Jens Arnspang).

Systemarbejde

Fagområdet systemarbejde omhandler studiet af udvikling, brug og vedligeholdelse af edb-baserede systemer. Programmer ses som en integreret del af en større helhed, der - ud over den edb-tekniske del- også omfatter andre typer af maskiner og værktøjer, arbejdsprocesser, og, ikke mindst, mennesker. Eksempler på edb-baserede systemer kan være økonomisystemer og avisproduktionsystemer. Fagområdet er i stadig udvikling, idet nye muligheder og problemer hele tiden trænger sig på til udforskning, bl.a. som følge af en fortsat hastig udvikling af mere raffinerede og billigere dataværktøjer. Studier af samspillet mellem mennesker og edb-systemer indtager en central position i de mangeartede aktiviteter, der tages op. I øjeblikket koncentreres forskningen på DIKU om at øge forståelsen af systemudviklingsarbejdet, bl.a. gennem empiriske studier af menneskers arbejde med at udvikle, bruge og omlægge edb-systemer. Der lægges vægt på at kombinere forståelsen med viden og erfaring opbygget også inden for andre fag end datalogi, specielt filosofi, sociologi og psykologi (Erik Frøkjær, Hasse Clausen, Jørgen Bansler, Jacob Nørbjerg og Morten Hertzum).

Edb i offentlig administration og fagfolks informationshåndtering: Der er gennemført undersøgelser af edb-anvendelser i den danske centraladministration, specielt til opgaverne journalisering og sagsstyring. Objektorienteret programudviklingsteknologi undersøges med henblik på opbygning af informationssystemer som standard-rammesystemer. Et eksperimentelt tekstsøgesystem, kaldet TeSS, indeholdende manualtekster til brug for programmører, har dannet grundlag for en større empirisk undersøgelse af forskellige typer af brugergrænseflader til informationssøgning (Erik Frøkjær).
Udviklingsstrategier: I samarbejde med sociolog Erling Havn arbejdes der med at undersøge, hvordan udvikling af edb-baserede informationssystemer foregår i praksis. Af særlig interesse er den stadig mere udbredte brug af generiske system-komponenter i udviklingsprocessen. Studiet fokuserer på udviklingsstrategier og organisationsformer. Det bygger på moderne arbejdssociologisk teori og omfatter undersøgelser af udviklingsstrategier på udvalgte danske virksomheder (J.P. Bansler og E. Havn, Institut for Samfundsfag, DTH).
LIDA-projektet (Design af edb-systemer): Målet er at opbygge en uddannelse for design af edb-systemer. I årets løb er der arbejdet med fortællingen som udtryksform. Gennem afviklingen af kurser på DIKU er det søgt afdækket, hvorledes designeren kan arbejde med og anvende fortællingen som et redskab i kommunikationen med andre designere. De gjorte erfaringer er beskrevet i en artikel og et konferencebidrag, ligesom ideerne er blevet præsenteret på et kollokvium på DIKU (Hasse Clausen).
Edb-støtte til fagfolks tekstsøgning: Efter godt 30 års indsats er edb-støtte til fagfolks dokumentationsarbejde stadig et område med få succes-historier. På empirisk grundlag arbejdes med at indkredse centrale årsager til dette, bl.a. ved at sammenholde eksisterende systemer med begrundelserne for at indføre dem. Desuden eksperimenteres med brugergrænsefladens betydning ved brug af sådanne systemer (Morten Hertzum).
Kvalifikationer og samarbejde i systemudvikling: Udviklingen af edb-baserede systemer er en kompleks proces, der involverer mange personer med vidt forskellig baggrund og viden: Brugere, designere, programmører, systemprogrammører, operatører o.s.v. I et ph.d.-studie er gennemført empiriske studier af organisation, samarbejde og kvalifikationer i systemudvikling. De indsamlede data er blevet analyseret og er ved at blive sammenfattet i en licentiatafhandling (Jacob Nørbjerg).

Øvrige forskningsområder

Datalogiens videnskabelige status: I fortsættelse af tidligere studier over datalogiens videnskabelige status udarbejdes en sammenhængende diskussion i form af en monografi omkring de fire temaer viden, sprog, datalogi og videnskab. Årets indsats har især sigtet på at udarbejde argumentationen for, at kernen i enhver videnskabelig aktivitet kan siges at være at udforme beskrivelser af aspekter af verden som er sammenhængende, koherente, med andre beskrivelser (Peter Naur).
Map Theory: I samarbejde med Paris Universitet VII er der blevet udviklet et simplificeret konsistensbevis for Map Theory. Endvidere er der blevet udviklet to simplificerede axiomsystemer for Map Theory. En lærebog for førsteårsstuderende er blevet påbegyndt. Map Theory danner baggrund for lærebogen, men lærebogen handler primært om klassiske matematiske emner, der har relevans for datalogistuderende (Klaus Grue).
Datanet: I forbindelse med to EU-støttede pilotprojekter (X.400 og X.500) er der udarbejdet tekniske specifikationer specielt beregnede for danske forhold vedrørende "Quality of Service" (X.400) og et schema for en dansk distribueret database (X.500), med særlig hensyntagen til dansk lovgivning (Klaus Hansen).
Logikprogrammering: Et velkendt forslag af Johnson og Kay til hvordan de samme regler kan konstruere logiske formler eller Kampske diskursrepræsentationer er blevet studeret. Ideen er, at semantiske repræsentationer specificeres indirekte ved brug af semantiske konstruktionsoperatorer, hvilket nødvendiggør en barriere mellem grammatikken og selve de semantiske repræsentationer. Forskellige operationer kan knyttes til disse semantiske operatorer. Sammenligning er foretaget med eget induktivt system, som kan ses som et meta-system, der automatisk producerer logiske formlismer (i form af anvendelsesspecifike definitte klausul-grammatikker), der kan udføre oversættelser ligesom Johnson og Kays program (Gregers Koch).
Logikprogrammering og vidensbaserede systemer: Der arbejdes med gradvise systemudviklingsmetoder, der omfatter videnstilegnelse, vidensrepresentation, modellering samt problem løsningsmetoder. Logikprogrammeringsideer og -metoder er anvendt indenfor rammerne af kunstig intelligens til støtte for menneskellig kreativitet. Anvendelser omfatter bl.a. byplanlægning, indendørs bygningmiljø, integritetskontrol i databaser og støtte til undervisning i matematik og datalogi (László Béla Kovács).
Towers of Hanoi: Der er udviklet en løsning til det klassiske problem 'Towers of Hanoi' generaliseret til mere end 3 pinde. Løsningen er baseret på en rekursiv algoritme udnyttende en optimal opsplitning af Hanoi-tårnet. Løsningen, som er relateret til Pascal's trekant, vil søges publiceret (Jørgen Sand).
Databaser med sekvens og dubletter: De gængse relationsdatabaser opfatter en database som en mængde af poster, altså en betragtningsmåde inden for hvilken både dubletter og en rækkefølgeangivelse er meningsløs. Ud fra antagelsen, at i praksis er både sekvensangivelse og muligheden for at lagre identiske poster meningsfuld og nyttig, arbejdes der på at udvikle et databasesprog, der er lige så kompakt og letlæseligt som de gængse relationsdatabasesprog (Torben Zahle).
Datamodeller: Ved opbygning af databaser er det af afgørende betydning for udnyttelsen af de lagrede data, at strukturen i databasen er beskrevet ved en logisk model, der i så høj grad som muligt afspejler brugerens begrebsverden. Der arbejdes på integration af to hovedlinier inden for database-forskningen: objekt-orienterede og logik-baserede (deduktive) modeller. Anvendeligheden af en sådan integreret model undersøges såvel generelt som på et særligt område: geografiske databaser (Peter Kjellberg).
Fork Calculus: Der arbejdes på ph.d.-afhandlingen The Fork Calculus: Towards a Logic for Concurrent ML (Klaus Havelund).

STAB

VIP

Antal årsværk: 43.

Professorer: P. Johansen, N.D. Jones, J. Krarup, P. Naur, S. Skelboe (orlov)
Lektorer: J.D. Andersen, N. Andersen, J. Arnspang, J. Bansler, H. Clausen, J. Clausen, E. Frøkjær, K. Grue, K. Hansen, E. Jul, J. Katajainen, G. Koch, L.B. Kovács, S.I. Olsen. J. Sand, M. Tofte, P. Winter, T.U. Zahle
Adjunkter: B. Andersen (orlov), F. Henglein, K. Henriksen, P. Kjellberg, T. Mogensen, M. Rosendahl
Adjunkt-/lektorvikarer: R.N. Andersen, V. Antimirov, A. Bondorf, P. Dickman, R. Fowler, K. Havelund, T.P. Jensen, N.C. Juul, J. Nørbjerg, M. Thorup
Kandidatstipendiater: M. Hertzum, K.J. Jørgensen, P. Koch, M.F. Larsen, N.E. Larsen, D. Pisinger, K.H. Rose, J. Träff, M. Welinder
Kandidatstipendier (eksternt financierede): L.O. Andersen, P.S. Laursen, C. Mossin, M. Nielsen
Eksterne lektorer: P. Høgh, K. Keller
Fondsansatte: P.H. Andersen, L. Birkedal, L. Fu, M. Haahr, K. Nielsen, L.K. Lassen, K.L. Petersen, V. Rehof, D. Sands, J. Sporring, L. Zong
Besøgende gæsteforskere: R. Glück, S. Horwitz, R. Nakashige, R. Paige, T. Reps, S. Sagiv

TAP

Antal årsværk: 26.

TAP: A.Axen, I. Borch, C. Engdahl, J. Errebo, C.F.Hansen, I.U. Haq, K. Høglund, B. Hougaard, L. Jacobsen, L.G. Jakobsen, C.D. Jensen, S.O. Jensen, A. Jepsen, N. Khanam, J. Kværndrup, J.B. Lundager, R. Løvgreen, L. Mathiesen, B. Mubarak, E.M. Nielsen, K. Nyboe, H. Offersen, L. Olsen, K. Outzen, C.-L. Pedersen, L. Pedersen, R. Schlüter, T. Sparrevohn, B. Søemosegaard, F. Sørensen, L. Wiese

Ph.d.-afhandlinger

Thomas Jensen: Abstract Interpretation in Logical Form

Karoline Malmkjær: Abstract Interpretation of Partial-Evaluation Algorithms

Niels Chr. Juul: Comprehensive, Concurrent, and Robust Garbage Collection in the Distributed Object-Based System Emerald

Afhandlingerne findes på Datalogisk Institut.

Specialer

Birkedal, Lars: Partial Evaluation of Standard ML

Bruüel, Alette: ISDN og datakommunikation

Christensen, Henrik Stender: Dansk sætningsanalyse - feltgrammatik, syntaks og semantik

Christensen, Lars Arne: Calibration of Eye-Hand Systems

Christensen, Niels Christian Smed: Automatic Modeling of Chemical and Biological Reaction Systems

Christfort, Jacob: IT-anvendelse - en multirationel problemstilling

de la Cour, Niels Dornonville: Applikative sproganvendelser og implementering

Donslund, Uffe: Objektorienteret systemudvikling i teori og praksis

Engdahl, Claus: Implementation af et tidsforsinket neuralt netværk

Folmer-Petersen, Kenneth: Porting the lan-based distributed system emerald to a wan

Hanehøj, Morten: Calibration of Eye-Hand Systems

Hegelund, Henrik: Scankonvertering og antialiasering af rette linier

Held-Hansen: Teoretiske idealer for edb-systemers funktion

Jacobsen, Brian: Selvjusterende kunstige neurale netværk

Jensen, Niels Carstens: C-eksperimentarium

Karlsmose, Jens: Edb-aftalen som arbejdsredskab

Larsen, Niels Ib: Prediction of Promotor and Transcription

Markussen, Jens: The Multicommodity Maximum Flow Problem

Mossin, Christian: Polymorphic Binding Time Analysis

Nielsen, Holger: Undersøgelse af E-R diagrammer vs. listebaserede brugergrænseflader som støtte til join i relationsdatabaser

Olsen, Keld Jersild: Simulation of a Cellular Neural Network

Panton, Lars B.: Kompressionsmetoder til datatransmission

Papadopoulos, Dimokritos Michael: Porting the lan-based distributed system emerald to a wan

Perstrup, Ketil: Præstrømalgoritmer til maksimastrømproblemer, er det praktisk ?

Petersen, Glenn: Objektorienteret systemudvikling i teori og praksis

Petersen, Kjeld Lau: Udvikling af en featurebaseret stereo-algoritme

Poulsen, Eigil Rosager: Representation for Efficient Implementation of Polymorphism

Rahlff, Charlotte: Udvikling af en featurebaseret stereo-algoritme

Ring, Mikkel Neigaard: Sætningsskemaet - syntaks og semantik

Schütt, Christian: Sequential and Distributed Algorithms for the Assignment Problem

Skadhauge, Peter Rossen: Semantisk Induktion

Skytte, Bo: Undersøgelse af E-R diagrammer vs. listebaserede brugergrænseflader som støtte til join i relationsdatabaser

Ståhlbrand, Eva: Konstrukton af en ny generel metode til omordning og faktorisering af store tyndt befolkede asymmetriske matricer

Veng, Christian Claus: Genkendelse af mønstre i tidssignaler

Welinder, Morten: Partial Evaluation of Standard ML

Whitt, Claus Fjelding: Indførelse af case - set fra et ledelsesperspektiv

(Specialerne findes på Datalogisk Institut)

Fondsstøtte

Statens Naturvidenskabelige Forskningsråd

Computer Vision: Active Vision and Exploration (Peter Johansen) 250.000 kr.
Design, analysis and Reasoning about Tools (Neil D. Jones) 850.000 kr.
Simple og effektive parallelle Branch and Bound algoritmer til løsning af NP-komplette kombinatoriske optimeringsproblemer (Per Storgaard Laursen) 418.878 kr.
Rejse- og ekstraudgifter ved ophold på Universität Kaiserslautern (Birger Andersen) 78.100 kr.

Statens Teknisk-videnskabelige Forskningsråd

Effektive programanalyser og automatiske programtransformationer (Lars Ole Andersen) 357.084 kr.
Informationsstrømme i en seende robot (Søren Olsen) 329.705 kr.
Typeinferens og programanalyse (Christian Mossin) 285.000 kr.

Forskerakademiet

Studieophold 1 år i Le Chesnay (Povl. T. Koch) 54.800 kr.
Studieophold 11 måneder i Göteborg (Kristoffer Høgsbro Rose) 58.650 kr.
Gæstestipendiat Djordje Kadijevic 1 md. (László Béla Kovács) 6.500 kr.
Studieophold 7 måneder i Paris (forlængelse) (Klaus Havelund) 29.270 kr.
Studieophold 4 måneder i Sophia-Antipolis (Mads Nielsen) 19.330 kr.

EU-kommisionen

TEMPUS EF-JEP-0955-92/3 (Klaus Hansen) 308.389 kr.
Value II Programmet (X.400 pilot) (Klaus Hansen) 104.000 ecu
Value II Programmet (X.500 pilot) (Klaus Hansen) 10.000 ecu
Esprit (Semantics Based Program Manipulation) (Neil D. Jones) 60.000 kr.
Esprit (Atlantique) (Neil D. Jones) 65.000 kr.
(EU Capital and Mobility Programme) Cabernet: 18 mdr. Research Fellowship (Birger Andersen) 58.122 ecu

Team Danmark

Computer Aided Flight 18.000 kr.

Nordisk Forskerutdanningsakademi

Konferencen 16th Informations Systems Research Seminar in Scandinavia (Jørgen P. Bansler) 98.000 NOK

J.P. Bansler

Informationsvirksomhed

Jens Clausen har holdt foredrag i Ungdommens Naturvidenskabelige Forening om Optimering. Derudover er han som formand for Dansk Selskab for Datalogi arrangør af en række faglige foredrag afholdt på Datalogisk Institut. Endelig har han skrevet til Dansk Dataforenings blad om uddannelsesplanlægning i de længerevarende edb-uddannelser.

Mere lokalt har han medvirket ved Åbent hus arrangementet for gymnasieelever, og har arrangeret en seminarrække for 1.delsstuderende og andre interesserede om udvalgte datalogiske emner.

Som en del af to EU-støttede pilotprojekter er der etableret en fast gruppe med deltagelse af industrivirksomheder med henblik på formidling af teknologi fra forskning til industri. Denne gruppe har holdt fire møder i 1993.

Som sekretær i DORS - Dansk selskab for Operationsanalyse, har David Pisinger bidraget til udgivelse af medlemsbladet DORS-nyt, samt til afholdelse af diverse tema-arrangementer, studentermøder, og foredragsaftener.

I forbindelse med et projekt om satelit-baseret flynavigation har Eric Jul afholdt et foredrag ved den årlige svæveflyvekonference, Ry, januar 1993. Der er desuden udgivet en artikel om projektets foreløbige resultater i tidskriftet FLYV og en mere uddybende DIKU rapport.