Årsberetning 1994

Forskningsvirksomhed

Ud over en række mindre forskningsområder har instituttet fem hovedindsatsområder: Semantikbaseret programbehandling, algoritmik, 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 1994 er nye teoretiske resultater blevet bevist og stærkere systemer til program optimering er blevet udviklet. Flere af resultaterne formindsker afstanden mellem teori og praksis. Desuden er en artikelsamling, hovedsageligt om typeteori, blevet redigeret og publiceret af Springer LNCS. Typer er blevet studeret dels som værktøj til at formindske lagerforbruget i funktionssproget Standard ML og dels for samtidigt at opnå fleksibiliteten af utypede sprog og effektiviteten og sikkerheden af typede sprog. Teoretiske undersøgelser og praktiske eksperimenter med anvendelse af partiel evaluering på praktiske problemer er blevet foretaget (Neil D. Jones, Nils Andersen, Mads Tofte, Klaus Grue, Torben Mogensen, Mads Rosendahl, Fritz Henglein, Knud J. Jørgensen, Kristoffer Høgsbro Rose, Lars Ole Andersen, Morten Welinder, Christian Mossin, John Hatcliff og David Sands).

Partiel evaluering: En abstrakt formulering af ideerne underliggende Turchins's `driving' er foretaget (Neil D. Jones).; Der er arbejdet med partiel evaluering, bl.a. selvanvendelig on-line partiel evaluering af ren lambda kalkyle. Dette er blevet til en artikel, som er sendt til PEPM'95 (Torben Mogensen).
Typeteori: Regionsinferens, en metode til implementation af `call-by-value' programmeringssprog, er blevet udvidet til at tillade sidevirkninger, undtagelser og rekursive datatyper. En regionsbaseret oversætter fra Core ML til programmeringssproget C er blevet udviklet. Denne eksperimentelle oversætter har i flere tilfælde vist sig at producere objektprogrammer, der er væsentligt mindre pladskrævende end de, der produceres af verdens førende Standard ML-oversætter (Mads Tofte).; Indenfor logik-baseret programanalyse er opnået to konkrete resultater: en formulering af type-baseret programanalyse, som giver invariante svar under udfoldning af (funktions)definitioner, selv for rekursive definitioner (ESOP '94, Edinburgh, med Christian Mossin), og en effektiv algoritmisk reduktion af type-baseret programanalyse til løsning of fixpunktligninger, som har givet nyt indblik i strukturen af type-derivationer og resulteret i en stærkt forbedret typeinferensalgoritme for type-baseret strikthedsanalyse (SAS '94, Namur) (Fritz Henglein).; En typeinferens-baseret analyse og algoritme til begrænsning af `boxing' i funktionsprogrammeringssprog er udvidet til F2, hvilket har ført til en ny og meget effektiv algoritme, som er implementeret. Metoder til automatisk generering af optimerende programspecialisatorer er udviklet og en prototype er implementeret. Der arbejdes på nu på metoder til automatisk generering af programgeneratorer, d.v.s. udvikling af et program, der genererer programmer, der genererer programmer (Knud J. Jørgensen).
Stakautomater: Arbejdet med den metode til transformation af stakprogrammer, som er en ny formulering af S. A. Cooks resultat for to-vejs stakautomater, er fortsat. Desuden har en række algoritmer til konstruktion af en tegnfølges såkaldte suffix-træ været undersøgt. Suffix-træer giver hurtig adgang til hver del af den givne følge, men endnu kendes ingen konstruktionsmetode, der i takt med, at den givne følges tegn bliver kendt, danner et træ, som kan angive delfølgers seneste forekomst (Nils Andersen).; Der arbejdes videre med specialisering af datastrukturer. Endvidere er en artikel om en variant af Cook's konstruktion til lineærtidssimulation af stakautomater optaget i Information Processing Letters (Torben Mogensen).
Kompleksitetsteori: Inviterede konferenceforedrag: International Logic Programming Symposium (Cornell University), SOFSh4 1994 (Tjekkiet) samt IFIP 1994 (Hamburg) hvor NDJ organiserede en `miniworkshop' om Program Speedups in Theory and Practice. Desuden er holdt Foredrag i Singapore, Vancouver i Canada, Courant Institute i New York og Portland i Oregon (Neil D. Jones).
Map Theory: Det lykkedes at simplificere map theory betragteligt, og version 2 af en lærebog, der nyttiggør dette, er under udarbejdelse. Der er endvidere blevet arbejdet med at realisere hardware, assembler, operativsystem og højniveausprog til at understøtte brug af map theory til programmering. Specielt er 1.0 micron ECPD10 processen og sproget VHDL blevet undersøgt med henblik på realisering af en højparallel grafreduktionsmaskine. Endvidere er der i Ph.D. arbejder blevet arbejdet med semantik for Concurrent ML (Afhandling: The Fork Calculus, Januar 1994) og implementation af numeriske algoritmer på højparallele grafreduktionsmaskiner, herunder bl.a. tidsmålinger på implementerede algoritmer (Klaus Grue, Klaus Havelund, Martin Funk Larsen).
Øvrige aktiviteter: Der er arbejdet med metoder til implementation af abstrakt fortolkning. Strikthedsanalyse af højereordens funktioner har længe været betragtet som for kostbart til praktisk anvendelse, men det er nu lykkedes at konstruere en effektiv algoritme for dette. Metoden kan bruges til at løse fikspunktligninger i højereordens domæner (Mads Rosendahl).; Der er arbejdet med det essentielle uløste problem at finde reduktionssystemer, der kan tjene som beregningsmodeller for funktionsprogrammeringssprog med deling. Desuden er tre måneder tilbragt ved Macquarie Universitetet i Sydney på et ARC forskningsprojekt om repræsentation af grafer og diagrammer i praksis. (Kristoffer Høgsbro Rose).; PhD-afhandlingen `Program Analysis and Specialization for the C Programming Language' er blevet skrevet og forsvaret. Afhandlingen beskæftiger sig med analyse og specialisering af C programmer med henblik på optimering. Udgivet som DIKU rapport 94/19 (Lars Ole Andersen).; Med held er benyttet teknikker fra partiel evaluering i tilknytning til formel bevisførelse. Dele af resultaterne blev præsenteret ved HOLTPA94. Arbejdet med partiel evaluering af Standard ML har ført til bidrag til PEPM-94 og PLILP-94 (med Lars Birkedal). Der arbejdes i øjeblikket med et optimalitetsbegreb for stærkt typet partiel evaluering samt med metoder, der sigter til at opnå sådanne optimale evaluatorer (Morten Welinder).; Arbejde med den teorien bag polymorf bindingstidsanalyse er afsluttet og blev præsenteret på ESOP'94, Edinburgh. Desuden arbejdes med linære typesystemer og deres anvendelighed til forudsigelse af lagerforbrug. Dette har ført til længere ophold i Glasgow, hvor samarbejde med Phil Wadler og David N. Turner har mundet ud i et use-type system, der kan forøge hastighed og formindske lagerforbrug for dovne sprog (Christian Mossin).; Arbejdet har været koncentreret om udviklingen af en generel ramme til beskrivelse af transformationer af funktionsprogrammer, kaldet continuation-passing style transformations. Disse transformationer spiller en vigtig rolle i både teori og praksis for funktionsprogrammering: de bruges ofte i formelle definitioner af programmeringssprog og anvendelsen af denne type transformation på et program gør det nemmere at implementerer det. Et resumé af arbedet blev præsenteret på dette års ACM Symposium on Principles of Programming Languages (John Hatcliff).; 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 Métayer og Banâtre. Sprogets semantiske grundlag, dets programlogik og statisk programanalyse studeres. Desuden arbejdes der med betingelser for total korrekthed af foldningsbaserede transformationer i højereordens funktionelle sprog (David Sands).

Design, konstruktion og analyse af algoritmer

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 beskrivelse af 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 algoritmerne spiller hermed en central rolle i at kunne udnytte det eksisterende hardware bedst muligt.

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 stu- diefelt 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. DIKU udspænder forskningsmassigt alle fire dimensioner på internationalt plan. 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 algortimer for konkrete arkitekturer, og parallelle algoritmer for maskinmodeller (PRAM etc.).

Som grundlag for algoritmekonstruktion optræder ofte en matematisk model. I forbindelse hermed undersøges principper for matematisk modellering i forbindelse med beslutningsstøtte ved planlægning i praksis (J. Krarup, J. Clausen, J. Katajainen, S. Skelboe, M. Thorup, P. Winter, D. Pisinger, J. Träff og P.S. Laursen).

NP-hårde optimeringsproblemer: Der er udviklet og implementeret parallele søgningsbaserede algoritmer for 3 af de `hårdeste' (NP-fuldstændige) kombinatoriske optimeringsproblemer: Placering af afdelinger mhp. minimering af total transportomkostning, skedulering af jobs mhp. minimering af total afviklingstid og oprettelse af depoter til forsyning af givne kunder mhp. minimering af den totale omkostning ved forsyningen. Løsningstider for benchmark-problemer er en faktor 10 bedre end hidtil bedste rapporteret internationalt (Jens Clausen og Michael Perregård).; Forskellige nye varianter af Knapsack-Problemet er blevet studeret. Dette har udmøntet sig i en række algoritmer med næsten ideel opførsel for nemme datasæt, mens svære datasæt stadig kræver en komplet gennemsøgning af udfaldsrummet. Disse arbejder er dokumenteret i form af såvel teoretiske grænseværdier som praktiske implementeringer. Den forventede sværhed af de såkaldte `core problemer' er blevet klarlagt, hvilket dels kan beskrive opførslen af nuværende algoritmer, dels kan føre til udviklingen af mere effektive løsningsmetoder. I løbet af foråret afsluttes en Ph.D. afhandling omhandlende algoritmer til optimal løsning af Knapsack Problemer (David Pisinger).; I forbindelse med et Ph.D.-projekt er der i årets første halvdel arbejdet med en ny strategi for parallelisering af to heuristikker for kombinatorisk optimering (Simuleret Udglødning og Tabu Søgning). Den eksperimentelle evaluering faldt positivt ud, idet den nye strategi medførte en signifikant forbedring af algoritmernes effektivitet. Anden halvdel af året er brugt på udarbejdelsen af en Ph.D. afhandling (Per S. Laursen).
Optimeringsproblemer i P: Eksistens af endelige projektive planer er undersøgt ved hjælp af den grådige algoritme. Endvidere er der givet eksempler på synliggørelse af dualitet. Matrixalgoritmer for korteste veje er under revurdering med henblik på post-optimale analyser. Projekter i forbindelse med et lokaliseringsproblem med `balanceret' fordeling af brugere samt et netværkssyntese-problem er igangsat (J. Krarup).; Arbejdet med eksperimentel afprøvning af parallelle algoritmer for korteste-vej og maksimum-strømsproblemet er afsluttet og vil indgå i PhD-afhandlingen `Distributed and Parallel Graph Algorithms'. Sammen med Jyrki Katajainen er designet parallelle (PRAM) algoritmer for bla. verificering af og sensitivitetsanalyse for mindste udspændende trær. Tildels udsprunget af dette arbejde er sammen med Mikkel Thorup og Jyrki Katajainen defineret det såkaldte `tree slicing' problem og angivet en arbejdsoptimal parallel algoritme til løsning heraf (Jesper Träff).
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 fokuseret på det rektilineære Steiner-træ problem, som har anvendelser bl.a. i VLSI-design (Pawel Winter).
Øvrige aktiviteter: Forskningen i in-place og parallele algoritmer er fortsat. På begge disse områder er den beregningsmæssige kompleksitet af nogle grundlæggende datalogiske problemer som sortering, manipulation af træer og grafer blevet undersøgt. Der er blevet skrevet forskningsrapporter herom sammen med flere udenlandske forskere (Jyrki Katajainen).; Sammen med Farach på Rutgers University og Przytycka (Odense) er der arbejdet på sammenligning af evolutionære træer; sammen med førstnævnte er udviklet den første ikke-trivielle algoritme til at finde mønstre i Ziv-Lempel-komprimerede tekster. Sammen med M. Tofte er der arbejdet på effektivisering af regionsinferens og i samarbejde med J. Träff og J. Katajainen på DIKU er der arbejdet med parallelberegning på træer. Artikler om resultaterne er indsendt til de relevante konferencer og tidsskrifter (Mikkel Thorup).

Distribuerede systemer

Distribuerede systemer bestående af selvstændige, samarbejdende datamater spillere en stadigt voksende rolle efterhånden som hurtigere og kraftigere netværk muliggør større udveksling af data og processer. Dette stiller nye store krav til operativsystemers funktionalitet og effektivitet. Samtidigt udvikles der nye former for tæt-koblede paralleldatamater, der stiller ekstreme krav til hurtigt kommunikation mellem de indgående processorer.

I gruppen forskes der med udvikling af nye paradigmer og mekanismer for distribuerede operativsystemer, fx distribueret spildopsamling, data- og processflytninger mellem datamater med forskellige maskinarkitekturer, objektlokalisering, 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 forbundet med varierende former for datatransmissionsudstyr, fx lokal net, telefonnet eller mobiltelefon (AMIGOS projektet).

Med støtte fra det naturvidenskabelige fakultet og statens forskningsråd udføres 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 (CarlOS projektet). Et mindre netværk er opbygget og forventes udbygget med flere maskiner og højhastighedsnetværk.

Der arbejdes med udvikling af grafreduktionsmaskiner og specielt med simulering af disse med henblik på måling af paralleliseringsgraden.

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 (Eric Jul, R. Fowler, Birger Andersen, Povl Koch, Niels Elgaard Larsen og Martin Funk Larsen).

Objektorienterede distribuerede systemer: Det tidligere udviklede objekt-orienterede programmeringssprog, Emerald, er videreudviklet i en udgave, der kan anvendes på mindre maskiner. Denne udgave skal anvendes i AMIGOS projektet, der drejer sig om udnyttelse af små, mobile datamater forbundet med fx lokalnet eller mobiltelefon. Der ses på, hvorledes de grundliggende operativsystemsparadigmer påvirkes af den varierende form for kommunikationsforbindelse. I CarlOS projektet er der eksperimenteret med distribueret lager fordelt over en mindre gruppe af maskiner. Metoder til effektivisering af fordelt lager undersøges. En undersøgelse af brugen af GPS til flynavigation er afsluttet (Eric Jul).; Hovedtemaet i forskningen har været CarlOS (Commodity Architecture Research Laboratory), et distribueret delt-lager operativsystemslag. Formålet hermed er at fremme udviklingen ved at stille en programmeludgave af distribueret delt lager til rådighed. Det vigtigste tekniske bidrag indtil nu har været formularing af meddelelsesdrevet lagerkonsistens og dens implementation i CarlOS (Robert Fowler).; Arbejdet har koncentreret sig om problematikker vedr. distribueret delt lager (DSM) og heterogene systemer med mobile enheder. Studiet af distribueret delt lager (DSM) og nye mere effektive metoder til at opretholde lagerkonsistens er blevet fortsat under opholdet i Kaiserslautern. Bl.a. er der fundet sene opdateringsmekanismer, der potentielt er mere effektive. Desuden har der været arbejdet med centrale problematikker i heterogene systemer med mobile enheder, her især kommunikationsformer og operation i perioder, hvor kommunikation til/fra mobile enheder er umuligt. En ny type transaktioner udvikles for understøttelse heraf (Birger Andersen).; Som licentiatprojekt arbejdes med højtydende distribuerede operativsystemer, specielt med en hybrid programmeringsmodel, der integerer et distribueret delt adresserum (DSM) med almindelig besked-udveksling. Denne model, som hedder "message-driven relaxed consistency", har stor fleksibilitet med hensyn til synkronisering og fordeling af arbejdet i et distribueret miljø. Gennem en prototype, CarlOS, er vist at denne model kan give store ydelses- og programmeringsmssige fordele (Poul Koch).; Der arbejdes med distribuerede, objektorienterede databaser og specielt med distribuerede transaktioner. Emerald systemet er udvidet til at understøtte persistente, distribuerede transaktioner. under et ophold på Basser Dept. of Computer Science, University of Sydney, er arbejdet med persistente operativsystemer i efteråret (Niels Elgaard Larsen).

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.

En robot med to frihedsgrader er anskaffet med henblik på at kunne positionere kameraet bedst muligt ved billedoptagelse. For at kunne beregne den rumlige placering af et objekt ud fra dets projektioner er det nødvendigt at kende kameraets interne parametre, f.eks. dets brændvidde. Desuden skal man kende den geometriske placering af kameraet som fremkommer når en kommando gives til robotten. Forskellige metoder til at finde disse kalibreringsparametre er udviklet. Kalibreringen omfatter også motorer til automatisk indstilling af kameraets linser.

Denne eksperimentelle forskning er en del af visiongruppens arbejde med active vision, d.v.s. opbygning af sceneforståelse ved hjælp af aktivt bevægede kameraer. 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).

Mønstergenkendelse: En model af en robot som modtager input fra sine omgivelser og som igen ændrer omgivelserne baseret på de modtagne input er opstillet. Eksakt overensstemmelse mellem mønstre i tidrækken af input blev valgt som styringsalgoritme. Enkle modeller for omgivelserne har været undersøgt, herunder en et tegns buffer. Ligeledes er det undersøgt hvad der sker når to styringsalgoritmer forbindes med tilbagekobling. Et tilbagekoblingssystem kan tilsyneladende opføre sig på to kvalitativt helt forskellige måder, meget regelmæssigt eller meget uregelmæssigt (Peter Johansen).
Genkendelse af geometriske former: Der arbejdes med en ny metode til detektion af form og objekter i billeder, `reciprokerende Hough Transformation'. Ved denne undgås problemer med den traditionelle Hough-transformations entydighed og beregningsarbejdet kan optimeres. (Jens D. Andersen og Klaus Hansen).
Robot-kamera selvkalibrering: På basis af et speciale udført af Morten Hanehøj og Lars Arne Christensen er udviklet en metode til kalibrering af systemer bestående af robotter og kameraer, der bevæges i forhold til hinanden (Jens D. Andersen, Morten Hanehøj og Lars Arne Christensen).
Spejlkameraer: Eksperimenter med spejlkameraer viser sig at kunne løse klassiske sceneanalyseproblemer med stor robusthed og nøjagtighed (Jens Arnspang).; Forskningen i metoder til bestemmelse af rette liniers 3-dimensionale orientering udfra en billedsekvens har resulteret i implementation af et prototype-system, som kan gøre dette halvautomatisk, idet linierne skal udpeges manuelt. Der arbejdes i øjeblikket på at gøre systemet fuldautomatisk. Desuden er der implementeret et prototype-system til opbygning af en hierarkisk objektorienteret 3-dimensional geometrisk model. Denne model kan vises fra forskellige positioner på en farveskærm (Knud Henriksen).
Aktiv vision: Der er arbejdet med kalibrering af DIKU's optisk- mekaniske robot. Kalibreringen er basal ved anvendelse inden for visuel udforskning og metriske opmålinger. Der forskes i hvorledes en kommercielt tilgængelig optik med styrbar zoom og fokus kan medtages i kalibreringen. Dette er vanskeligt, bl.a. fordi optikken ikke er perfekt. Den udvidede kalibrering vil muliggøre visuelle analyser hvor den skala, hvorunder dele af scenen betragtes, bestemmes adaptivt (Søren I. Olsen).
Kantdetektorer: Til test og evaluering af kantdetektorer er der arbejdet med programmel til kvantitativ evaluering af visse mål for kvaliteten af kantdetektorer, samt med en udvidelse af et tidligere udviklet sæt af syntetiske billeder med nye med Gaussisk støj (Klaus Hansen).
Regularisering: Indenfor datamatsyn er forsket i A) sammenhængen mellem skalarum, regularisering og kantdetektorer. B) Udnyttelsen af Bayes estimation som inferens maskine. C) Stereosyn baseret på aktiomer om strukturen af 3D-rum. D) Fasebaserede metoder til bestemmelse af flow-strukturer. I de første 8 måneder foregik forskningen ved INRIA, Sophia-Antipolis i Frankrig, støttet af Forskerakademiet (Mads Nielsen).
Musikinformatik: Musiklaboratoriets aktiviteter er gået ind i en international fase: dels ved etableringen af en yderst succesfuld verdenskongres med både videnskabelige og musiske sessioner, dels ved oprettelse af en europæisk arbejdsgruppe med temaet performance, kunsten at syntetisere en musisk plausibel opførelse af et stykke via et kunstigt datastyret orkester, evt. dirigeret via optiske ordninger eller helt uden dirigent, men via kunstig intelligens. Der er åbne spørgsmaal i, hvorledes dette bedst kan gribes an, men mange små teatre og orkestre er interesseret i en løsning (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 avisproduktionssystemer. 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, Peter Naur, Jørgen Bansler, Hasse Clausen, Morten Hertzum og Jacob Nørbjerg).

Edb i offentlig administration og fagfolks informationshåndtering: Erfaringer fra et toårigt eksperiment med brug af et edb-system til støtte af det daglige arbejde for politikere og byrådssekretariatet i Ravnsborg Kommune er sammenfattet. Systemet, der er opbygget af Kommunedata, er et eksempel på en ny type edb-værktøjer til datamatstøttet samarbejde, såkaldte CSCW-værktøjer (Computer Supported Cooperative Work). Indtil videre er der kun få rapporteringer om vellykket organisatorisk indførelse og brug af sådanne edb-baserede systemer, også internationalt set. I samarbejde med PhD-studerende Morten Hertzum er redegjort for en omfattende eksperimentel undersøgelse af brugergrænseflader af betydning for forståelsen af brugseffektivitet i mindre, edb-baserede informationssøgesystemer til støtte for fagfolk under opgaveløsning (Erik Frøkjær).
Datalogiens videnskabelige status: Udarbejdelsen af en sammenhængende diskussion i form af en monografi omkring de fire temaer viden, sprog, datalogi, og videnskab er fortsat. Som hovedtitel er valgt: Knowing and the Mystique of Logic and Rules. Herved identificeres monografiens gennemgående tema, at en beskrivelse af bevidsthedslivet og videnaktiviteten, som bygger på logik og regler, findes at være uholdbar. Som årets mest markante bidrag til monografien kan nævnes et afsnit med titlen Computer Modelling of Human Knowing Activity (Peter Naur).
Udviklingsstrategier: Flere og flere virksomheder baserer deres informationssystemer på generisk programmel, dvs. på `standardkomponenter' som de køber på det ekspanderende marked for `software'. I samarbejde med Erling Havn studeres konkrete systemudviklingsprocesser på udvalgte danske virksomheder, hvor brugen af generiske komponenter spiller en central rolle. Studiet fokuserer på hvordan organisationsformer, kvalifikationskrav og betingelserne for brugerdeltagelse forandres i forhold til traditionelle udviklingsprocesser (J.P. Bansler og E. Havn, Institut for Samfundsfag, DTU).
Design af edb-systemer: Det langsigtede mål er at opbygge en uddannelse for design af edb-systemer. Gennem afviklingen af kurser på DIKU er fremkommet en række fortællinger, som kan indgå i en rapport/kursusbog, der behandler temaet `Designerens arbejde med fortællingen som et led i systemudviklingen'. De hidtidige erfaringer er beskrevet i to artikler. Med henblik på at opbygge en egentlig designuddannelse er der etableret kontakt til en forskningsgruppe ved Lunds universitet (Hasse Clausen).
Fagfolks dokumentationsarbejde og edb-støtte: For de fleste fagfolk indgår dokumentationsarbejde som en integreret del af deres primære arbejde og er et vigtigt middel til at sikre kvalitet i det samlede arbejdsresultat. Gennem et ph.d.-studium er den praktiske og organisatoriske kontekst for dokumentationsarbejde undersøgt, og brugseffektiviteten af udvalgte edb-baserede lagrings- og informationssøgeteknikker studeret (Morten Hertzum).
Systemudvikling: kvalifikationer, samarbejde, organisation: Systemudvikling er en kompleks proces med mange deltagere, der har vidt forskellig baggrund og viden: Brugere, designere, programmører, systemprogrammører, operatører o.s.v. Ph.d. afhandlingen "Kvalifikationer og Samarbejdsformer i Systemudvikling" er indleveret og forsvaret. I afhandlingen, der bygger på empiriske studier af systemudvikling, diskuteres organisation, samarbejde, og kvalifikationer i systemudvikling (Jacob Nørbjerg).

Øvrige forskningsområder

Logikprogrammering: Inden for logikprogrammering og sprogbehandling er der i år i forlængelse af tidligere arbejder blevet arbejdet paa udvikling af en (semantisk) analysemetode, som indeholder væsentlige aspekter, der tilsyneladende er ganske nye, heriblandt et visualiseringsaspekt samt et induktivt aspekt vedroerende automatisk syntese af programmer ud fra eksempler paa inddata og ønsket uddata. Det drejer sig om at anvende en uskøn blanding af lingvistiske, logiske og naturligvis ikke mindst datalogiske argumenter og teknikker til at analysere problemer med. Til afprøvning af metoden er nogle helt simple problemstillinger blevet undersøgt, heriblandt Aristoteliske syllogismer (Gregers Koch).
Logikprogrammering og videnbaserede systemer: Der arbejdes med gradvis systemudvikling metoder, der omfatter videnstilegnelse, videnrepræsentation, modellering, generelle og specifikke problem løsning metoder. Logiske- og kognitive modeller er kombineret med kunstig intelligence til at støtte menneskelige kreativitet. Problembeskrivelser og information, der oftest begynder i det naturlige sprog, er sædvanligvis ufuldstændige. Nuværende anvendelse omfatter byplanlægning; indendørs bygningmiljø (luftkvalitet, lokale ubehageligheder) og medicinsk diagnose (László Béla Kovács).
Lineær Stabilitetsanalyse og Resolventbetingelser: Ved numerisk løsning af lineære begyndelsesværdiproblemer har man som oftest en iterativ proces, hvis stabilitetsegenskaber afhænger af, hvor stor normen af den n'te potens af en vis matrix kan blive. At kræve at matricens spektralradius er mindre end 1, udelukker ikke, at normen kan blive uacceptabel stor, og de seneste 4-5 år har man i stedet interesseret sig meget for resolventen. F.eks. ved man nu, at hvis en såkaldt Hille-Yosida betingelse er opfyldt, er fejlvæksten mindre end lineær i n. Det er vist, at visse af disse estimater er skarpe, og at for 1-step metoder kan man nøjes med en betingelse i stabilitetsområdet. (Jørgen Sand).
Sekventielle databaser: For en række anvendelser er sekvensen af en række informationer en så integreret del af problemstillingen, at det er uhensigtsmæssigt at udtrykke sig i de gængse forespørgselssprog for relationsdatabaser, som opererer med mængder. Derfor arbejdes der på at udvikle et sprog, hvor sekvensangivelser er en integreret del af databasen, og hvor man derfor kan udtrykke sig væsentligt kortere og naturligere. Arbejdet er stærkt inspireret af de såkaldte temporale databaser (T. U. 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. Det er erkendt, at den relationelle model har sine begrænsninger i forbindelse med en række mere avancerede database-anvendelser. Et væsentligt forskningsfelt indenfor database-området er derfor udviklingen af kraftigere datamodeller. Der arbejdes fortsat på en integration af to hovedlinier inden for denne forskning: 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).

Stab

VIP

Antal årsværk: 47.

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, K. Henriksen, E. Jul, J. Katajainen, G. Koch, L.B. Kovács, T. Mogensen, S.I. Olsen. J. Sand, M. Tofte, P. Winter, T.U. Zahle.
Adjunkter: B. Andersen (orlov), F. Henglein, P. Kjellberg, J. Nørbjerg, M. Rosendahl, M. Thorup.
Adjunkt-/lektorvikarer: R. Fowler, N.C. Juul, K. Keller, M.F. Larsen, D. Pisinger, J.L. Träff.
Kandidatstipendiater: M. Hertzum, K.J. Jørgensen, M.F. Larsen, J. Träff, D. Pisinger.
Kandidatstipendiater (eksternt financierede): L.O. Andersen, P.S. Laursen, M. Nielsen.
Eksterne lektorer: P. Høgh.
Fondsansatte VIP: D. Sands, J. Hatclif.
Ph.D. Studerende: P. Koch. N.E. Larsen,C. Mossin, K.H. Rose, M.H. Sørensen, M. Welinder.
Besøgende gæsteforskere: R. Glück, S. Horwitz, R. Nakashige, R. Paige, T. Reps, S. Sagiv.

TAP

Antal årsværk: 32.

TAP: A.Axen, I. Borch, C. Engdahl, J. Errebo, C.F.Hansen, I.U. Haq, T. Holst, B. Hougaard, K. Høglund, L. Jacobsen, L.G. Jakobsen, C.D. Jensen, S.O. Jensen, A. Jepsen, M. Jespersen, V.T. Jørgensen, 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.
Fondsansatte TAP: P.H. Andersen, L. Birkedal, M.V. Christiansen, M. Elsman, L. Fu, M. Haahr, K. Nielsen, L.K. Lassen, M. Perregaard, J. Rehof, J. Sporring, L. Zong.

Ph.d.-afhandlinger

Lars Ole Andersen: Program Analysis and Specialization for the C Programming Language	DIKU rapport 94/19
Klaus Havelund: The Fork Calculus: Towards a Logic for Concurrent ML
Morten Hertzum: Computer Support for Documentation Work	DIKU rapport 94/20
Ming Fang: Krylov Subspace Methods: Convergence and Parallel Aspects
Per S. Laursen: Parallel Optimization Algorithms - Efficiency vs. Simplicity	DIKU rapport 94/31
Jacob Nørbjerg: Kvalifikationer og Samarbejdsformer i Systemudvikling	DIKU rapport 94/28

Afhandlingerne findes på Datalogisk Institut.

Specialer

Andersen, Rene Villy: Maskinoversættelse - teori og praksis

Andreassen, Flemming Stig: A distributed wide area name service for an object oriented programming system

Bagger, Jesper: Traffic Advisor - Et logikprogrammeringsprojekt

Bjerring, Ulf: Global Positioning system (GPS)

Broch, Ken: Distribution af C++ objekter

Burman, Mikael: Edb-virus og ormeprogrammer

Gammeltoft, Peter Byrjalsen: Edb-støtte til projektgruppearbejde

Hansen, Helen: Implementation af attributgrammatikker

Hansen, Peter Wad: Parallel Jobshop Scheduling

Hansson, Hasse: Digital Signatures

Harbo, Klaus: Dokumenthåndtering og SGML transformation

Hessellund, Mogens: Brugerdeltagelse ved standardsystemindførelse - undersøgelse af Castrols og Electromatics indførelse af BP-systemet

Hjæresen, Peter Frits: Strikthedsanalyse af Haskell

Illum, Bent: Implementation under MS-DOS af oberon-2 med spildopsamling

Jensen, Flemming: Heuristic Amplification in Medical Intensive Care

Jensen, Kristian Damm: Strikthedsanalyse af Haskell

Jørding, Nick: A distributed wide area name service for an object oriented programming system

Jørgensen, Morten Due: Spektralanalyse af signaler

Kølander, Jan: Implementation af OSI-protokoller i det distribuerede system Emerald ved hjælp af ISODE

Laforce, Stine Maria: Systemarbejde - vurdering og afprøvning af metoden multiview

Larsen, Anne Oddershede: The Hough-Transformation: A Study of Ellipses in a 2-D Projection of a 3-D World

Laustsen, Kaj: Den individuelle brugervenlighed

Lehrmann, Morten Jes: Load Distribution in Emerald - An Experiment

Madsen, Ole: Heuristic Amplification in Medical Intensive Care

Petterson, Bjarne: Skemalægning ved hjælp af kromatisk optimering

Rasmussen, Morten Bune: Undervisningsprogram til "Assignment Problem"

Singh, Arvinder: Metoder for bevægelsesstyring i 3D-animation

Sørensen, Morten Heine: Turchin's Supercompiler Revisited

Thorup, Lars: En komparativ analyse af begreber i objektorienteret programmering

Thuneby, Tom: Effektiv implementation af tabeller i funktionssprog

Titan, Georg: Møblering af et rum som eksempel til interaktiv D, hjulpet af 3D grafik

Vejlstrup, Magnus: Multiplicity Inference

Vind, Christian: A Comparison of Neural Networks and Statistical Methods for Classification

Wagner, Morten: Computerstøttet harmonisering

(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) DIKU andel 1.200.000 kr.
Problemer i forbindelse med numerisk løsning af sædvanlige differentialligninger (Jørgen Sand) 56.670 kr.
Center for Anvendelse af Paralleldatamater (Jens Clausen) 130.000 kr.
Simple og effektive 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) 52.067 kr.
Rejse- og ekstraudgifter ved ophold på RUTR og DIMA, Rutgers Univ., og på University of Waterloo (Pawel Winter) 78.620 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) 230.000 kr.
Typeinferens og programanalyse (Christian Mossin) 285.000 kr.

Forskerakademiet

Ph.D. sommerskole i kompleksitetsteori (Peter Johansen) 146.200 kr.
Studieophold 8 måneder i Sophia-Antipolis (Mads Nielsen) 19.330 kr.
DANVIS: postdoktoral gæsteforsker John Hatcliff (Neil D. Jones) 100.000 Ecu.

EU-kommisionen

SCOOP: Solving Combinatorial Problems in Parallel (Jens Clausen) 17.000 Ecu.
(EU Capital and Mobility Programme) Cabernet: 18 mdr. Research Fellowship (Birger Andersen) 38.748 Ecu.
(EU Value II Programme) X.500 pilotprojekt (Klaus Hansen) 10.000 Ecu.
(ESPRIT) Semantics Based Program Manipulation (Neil D. Jones) DIKU andel 60.000 kr.
(ESPRIT) Amerikansk-Europæisk forskningssamarbejde om Sematiques emner (Neil D. Jones) DIKU andel 65.000 kr.
(ESPRIT) Semantik for `concurrent' programmeringssprog Neil D. Jones) DIKU andel 460.000 kr.

J.P. Bansler

Informationsvirksomhed

Jens Clausen har holdt foredrag for GL's Datalærerforening om nyere udviklinger indenfor algoritmeområdet. Derudover er han som formand for Dansk Selskab for Datalogi arrangør af en række faglige foredrag afholdt på Datalogisk Institut. David Pisinger har som redaktør for DORS - Dansk Selskab for Operationsanalyse - bidraget med orienterende artikler, afholdelse af tema-arrangementer samt studentermøder og foredragsaftener. Jens Clausen og Søren Olsen har bidraget med indlæg til Den Store Danske Encyklopædi. Endvidere har Klaus Hansen og László Béla Kovács bidraget med indlæg til den nye udgave af det danske EDB-leksikon. Peter Naur har præsenteret foredraget `Bridging the gap between pure and applied computing' (invited lecture to FOCUS '94, June 8-10, 1994 i København). Erik Frøkjær har holdt foredrag om kreativitet i samspillet mellem styregruppe og projektgruppe ved Dansk Dataforenings konference `Kreativ udnyttelse af projektets styregruppe' i København 18 maj, og uddrag er trykt i foreningens medlemsblad DATAposten. Erik Frøkjær var ordstyrer og paneldeltager på en edb-sikkerhedskonference for offentlige ledere og edb-systemansvarlige arrangeret af firmaet DDE 13 december.

Semantikbaseret programbehandling (TOPPS):: Neil D. Jones, Nils Andersen, Mads Tofte, Klaus Grue, Torben Mogensen, Mads Rosendal, Fritz Henglein, Knud J. Jørgensen, Kristoffer Høgsbro Rose, Lars Ole Andersen, Morten Welinder, Christian Mossin, John Hatcliff David Sands.
Algoritmik:: Jakob Krarup, Jens Clausen, Jyrki Katajainen, Stig Skelboe, Mikkel Thorup, Pawel Winter, David Pisinger, Jesper Träff og Per Storgaard Laursen.
Distribuerede systemer:: Eric Jul, Robert Fowler, Birger Andersen, Poul Koch, Niels Elgaard Larsen og Martin Funk Larsen.
Datamatsyn:: Peter Johansen, Jens Damgaard Andersen, Jens Arnspang, Klaus Hansen, Knud Henriksen, Søren Olsen og Mads Nielsen.
Systemarbejde:: Erik Frøkjær, Peter Naur, Jørgen Bansler, Hasse Clausen, Morten Hertzum og Jacob Nørbjerg.
Øvrige:: Gregers Koch, Lazlo Kovacs, Jørgen Sand, Torben Zahle, Peter Kjellberg.