Årsberetning 1992

STAB

Akademisk personale

43 årsværk

Professorer: P. Johansen, N.D. Jones, J. Krarup, P. Naur, S. Skelboe
Lektorer: J.D. Andersen, N. Andersen, J. Arnspang, J. Bansler, H. Clausen, J. Clausen, E. Frøkjær, K. Grue, K. Hansen, E. Jul, G. Koch, L.B. Kovács, S.I. Olsen. J. Sand, M. Tofte, P. Winter, T.U. Zahle
Adjunkter: B. Andersen, F. Henglein, K. Henriksen, P. Kjellberg, T. Mogensen, M. Rosendahl
Adjunkt-/lektorvikarer: L. Bannon, N.C. Juul, J. Katajainen, H.E. Thomsen
Kandidatstipendiater: R.N. Andersen, C.K. Gomard, K. Havelund, M. Hertzum, C.K. Holst, T.P. Jensen, K.J. Jørgensen, M.F. Larsen, N.E. Larsen, K. Malmkjær, J. Nørbjerg, D. Pisinger, K.H. Rose, J. Träff
Kandidatstipendier (ekst. financ.): L.O. Andersen, P.S. Laursen, M. Nielsen
Eksterne lektorer: P. Høgh
Fondsansatte: P.H. Andersen, L. Birkedal, A. Bondorf, M. Fang, J. Hannan, L.K. Lassen, K.L. Petersen, D. Sands, T. Sparrevohn, R. Stahr, B. Steensgaard, D. Wang

Teknisk og administrativt personale

Antal årsværk 24

TAP: A.Axen, I. Borch, C. Engdahl, 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, S. Lindén, J.B. Lundager, R. Løvgreen, L. Mathiesen, B. Mubarak, E.M. Nielsen, H. Offersen, L. Olsen, K. Outzen, C.-L. Pedersen, R. Schlüter, R. Seindal, B. Søemosegaard, F. Sørensen, L. Wiese

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, f. eks. til analyse, implementering, transformation, syntese og tidsvurdering samt typebegrebets teori og anvendelse. Emnet er relevant for bl.a. konstruktion af oversættere og fortolkere samt programafprøvning og optimering.

Arbejdet ligger på grænsen mellem teori og praksis: 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.

Forskningen er blevet støttet af Statens Naturvidenskabelige Forskningsråd (DART-projektet, fælles med Århus og Aalborg), og af Fæ llesmarkedets ESPRIT program: Semantique II, fælles med Imperial College (London), Glasgow University, Göteborgs Universitet samt École Normale Supérieure (Paris).

Gruppen har ph.d. studerende ved DIKU, Glasgow University, Göteborgs Universitet, Imperial College (London) og Kansas State University. Der holdes et ugentligt uformelt gruppemøde åbent for alle inklusive de studerende (Neil D. Jones, Nils Andersen, Mads Tofte, Fritz Henglein, Torben Mogensen, Mads Rosendahl, C. Kehler Holst, C. Krogh Gomard, Karoline Malmkjær, Thomas P. Jensen, Knud J. Jørgensen, Kristoffer Høgsbro Rose, Lars Ole Andersen, Anders Bondorf og David Sands).

Forskning i automatisk programanalyse og -transformation (abstrakt fortolkning og partiel evaluering), typer i programmeringssprog og kompleksitetsteori. Medlem af Computer Science Logic Council, inviteret foredragsholder ved CSLs 1992 konference, medredaktør ved J. Functional Programming og Monographs af Euro. Assoc. Theor. Comp. Sci. Medlem Int. Fed. Info. Proc. Soc. Working Group 2.8. Extern evaluator for ESPRIT projektet ALCOM samt medlem af flere andre bedømmelsesudvalg (Neil D. Jones).

Programmer i et dovent funktionsprogrammeringssprog af højere orden kan noteres som et system af definerende ligninger, og denne form er velegnet til programtransformation. Wadlers og Chins arbejder vedrørende transformationer, der kan eliminere midlertidige strukturer (såkaldt "deforestation" og "fusion") søges systematiseret og generaliseret (Nils Andersen).

Teorien om højereordens funktorer er blevet videreudviklet, og ideerne er blevet implementeret i samarbejde med AT&T Bell Labs. Desuden er udviklingen af en ny teori, kaldet regionsinferens, hvis formål det er at gøre det muligt at implementere typede funktionsprogrammeringssprog uden brug af en hob, påbegyndt i samarbejde med École des Mines i Paris (Mads Tofte).

Meta-niveau programmering i ren klassisk lambda-kalkule undersøges. Det omfatter effektiv representation af lambda-udtryks syntaks som funktioner i lambda-kalkule, selv-fortolkning og reduktion af lambda-kalkule, partiel evaluering af lambda-kalkule samt realisering af den anden rekursionssætning, altsammen implementeret i ren lambda-kalkule. I øjeblikket arbejdes der med at indlejre lambda-K-kalkulen i lambda-I-kalkulen.

Derudover arbejdes med partiel evaluering, især specialisering af datastrukturer. Dette har afstedkommet en artikel, som er sendt til PEPM'93 (Torben Mogensen).

Der er arbejdet med anvendelser af abstrakt fortolkning til analyse af realistiske sprog. Herunder er der konstrueret en analyse af udregningsrækkefølgen i attributgrammatikker og en analyse af hægtede datastrukturer i imperative sprog. Desuden er egenskaber ved semantiske beskrivelser baseret på minimale funktionsgrafer undersøgt (Mads Rosendahl).

Et typesystem, som integrerer både statisk og dynamisk typede programmeringssprog med fuld støtte af automatisk typeinferens, er undersøgt. Ved European Symposium on Programming i februar blev selve typesystemet præsenteret, og nogle af dets fundamentale teoretiske egenskaber vist, og ved ACM Conference on LISP and Functional Programming i juni blev det vist, hvordan et dynamisk sprog som Scheme kan optimeres ved hjælp af statisk typeinferens i dette typesystem. Desuden udførtes censur på en Ph.D. afhandling i constraint logic programming samt arbejde med adskillige problemer i programanalyse (Fritz Henglein).

Bogen "Partial Evaluation and Automatic Program Generation" er blevet gjort næsten færdig (sammen med N. Jones og P. Sestoft) og vil udkomme på Prentice-Hall i foråret 93. Bogen er en sammenhængende lærebog, der indeholder såvel introducerende og formidlende kapitler baseret på de sidste 10 års forskning som kapitler baseret på helt nye forskningsresultater (C. Krogh Gomard).

Effektive programanalyser for en stor delmængde af Scheme (bl.a. flow- og bindingstidsanalyse) er udviklet, implementeret og integreret i den partielle evaluator Similix. Analyserne, der kører i lineær tid, behandler såvel højereordensfunktioner som partielt statiske datastrukturer. Der arbejdes på en ny "release" af systemet Similix. Endvidere arbejdes der med anvendelse af partiel evaluering til implementering af semantiske specifikationer (Anders Bondorf).

Analyse, der forudbestemmer egenskaber ved programmer, genereret ved partiel evaluering, er udvidet til at håndtere højereordens funktioner. For visse klasser af programmer kan en simplere partiel evalueringsalgoritme anvendes. Analyser til at bestemme, om et program tilhører en sådan klasse, er udviklet. Partiel evaluering er anvendt til forenkling af beregninger med monader (med O. Danvy og J. Koslowski fra Kansas State University) (Karoline Malmkjær).

Et typesystem til analyse af uniforme egenskaber af datastrukturer (egenskaber der alene afhænger af indholdet af en struktur) er blevet udviklet. En tilsvarende abstrakt fortolkning baseret på Plotkins "powerdomain" er blevet konstrueret. Arbejdet med modeller for sand parallellitet baseret på automater af højere dimensioner er blevet fortsat. Brugen af teknikker fra algebraisk topologi til beskrivelsen af disse automaters struktur er blevet undersøgt (Thomas P. Jensen).

Effektive analyser til "off-line" partial evaluering er udviklet. Analyserne er implementeret og integeret i den partielle evaluator Similix. Analyserne kører i lineær tid og kan behandle både højereordensfunktioner og partielt statiske datastrukturer. Der arbejdes på at udvikle effektive typeinference baserede analyser/algoritmer til bl. a. begrænsning af "boxing" i funktionsprogrameringssprog og til typeinferens med undertyper (Knud J. Jørgensen).

Projektet "Grafbaseret specifikation af deling i programmeringssprog" omhandler en systematisk undersøgelse af, hvorledes grafbaserede formalismer og algoritmer kan hjælpe til at opnå bedre forståelse og bedre udnyttelse af de former for eksplicit deling af data og beregninger, som udtrykkes i programmer. Undersøgelsen falder først og fremmest indenfor området semantik for programmeringssprog, indtil videre især dovne funktionssprog, tilsvarende er kun termgrafomskrivningssystemer brugt som basis, men det er tanken at udvide til også at relatere til grafalgoritmer (Kristoffer Høgsbro Rose).

Der er blevet udviklet en automatisk partiel evaluator, herunder pointer- og bindingtidsanalyse, for en større delmængde af sproget C. En prototype version af systemet er blevet implementeret. Dette sker i forbindelse med PhD. projekt omhandlende effektive programanalyser og automatiske transformationer (Lars Ole Andersen).

Gammamodellen er et minimalt programmeringssprog baseret på lokal multimængdeomskrivning (med en elegant kemisk reaktionsmetafor). Via en passende formalisering er en kalkule for Gamma programmer blevet udviklet og brugt til at studere forholdet mellem parallel og sekventiel programsammensætning og tilsvarende programtransformationer. (Sammen med C. Hankin og D. le Metayer fra Imperial College). Nuværende arbejde overvejer, hvordan 'strictness' egenskaber i dovne funktionsprogrammeringssprog kan beskrives operationelt, og dermed give nye indblik i forholdet mellem abstrakte egenskaber og beregningsmekanismer og mellem projektions/PER-baserede egenskaber og parametriseret bisimulering i ccs-lignende sprog (David Sands).

Optimering

Optimering handler om formulering og løsning af beslutningsproblemer, hyppigt i forbindelse med bedst mulig udnyttelse af knappe ressourcer. Anvendelsesområderne omfatter mangeartede 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: Forskning i grænseområder mellem kombinatorisk optimering og diskret matematik. Artikler om hhv. todelt parring og eksistens af såkaldt endelige geometrier er under udarbejdelse. Andre aktiviteter er: 1) deltagelse i internationale programkomitéer, redaktionskomitéer og bedømmelsesudvalg, 2) TEMPUS-projekt: Udvikling af nye uddannelseselementer til MBA-uddannelsen i Polen, 3) Formidling af internationalt samarbejde inden for operationsanalyse som medlem af eksekutivkomitéen for EURO, Assoc. of Europ. OR Societies og vicepræsident for IFORS. Intern. Fed. of OR Societies (J. Krarup).
Netværkssyntese: Netværkssyntese beskæftiger sig med konstruktion af netværk (for eksempel i forbindelse med energiforsyning og datakommunikation), der opfylder visse formål og som tillige i en eller anden veldefineret forstand er optimale eller efficiente. I 1992 var forskningen koncentreret omkring anvendelsen af Algoritmisk Geometri (eng. computational geometry) til løsning af nogle grundlæggende netværkssyntese problemer (Pawel Winter).
Optimeringsproblemer: I forbindelse med et Ph.D.studium indenfor området Kombinatorisk Optimering afprøves enumerationsalgoritmer til løsning af NP-hårde optimeringsproblemer. Den indledende fase omfattede primært litteratursøgning, samt afprøvning af eksisterende algoritmer, hvorpå selvstændige eksperimenter kan foretages. Dette arbejde har resulteret i en artikel omhandlende en ny og bedre algoritme til løsning af Knapsack Problemet. Endvidere er en anden artikel, der omhandler løsning af svære heltalsprogrammeringsproblemer, under forberedelse (David Pisinger).

Parallel programmering og distribuerede systemer

Paralleldatamater med mange processorer og netværk af selvstændige 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 programmeringssprogene Emerald og Ellie. Begge er baseret på objekt-begrebet, som muliggør indkapsling af data, så de kun kan manipuleres med veldefinerede operationer. Ellie er et højniveau sprog for finkornede parallelle datamater. Det startede som et Ph.D. projekt i 1988 og er nu blevet videreført. Det overordnede formål er at finde metoder til at programmere fremtidens fin-kornet parallelle datamater.

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.

Forskningen i generelle principper for konstruktion og analyse af algoritmer omfatter: parallelle algoritmer, datalogisk geometri, datastrukturer og datakompression samt metoder til simulering 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.

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 Träff, Ming Fang, Martin Funk Larsen og Niels Elgaard Larsen).

Parallelle numeriske algoritmer: Meget store systemer af sædvanlige differentialligninger kan ofte betragtes som en samling løst koblede delsystemer. Nøjagtighed og stabilitetsegenskaber for metoder, der udnytter dette til parallel numerisk løsning af sædvanlige differentialligninger, er analyseret. Forskellige metoder til forbedring af nøjagtigheden er undersøgt, såvel teoretisk som eksperimentelt (Stig Skelboe).; I forbindelse med et Ph. D. studium arbejdes der med iterative metoder til parallel løsning af tyndt befolkede lineære ligningssystemer. De teoretiske egenskaber hos metoderne undersøges, ligesom metoderne programmeres og sammenlignes med parallelle direkte metoder (Ming Fang).; Et projekt vedrørende parallellisering af numeriske algoritmer ved brug parallelle grafreduktionsmaskiner har været koncentreret om følgende hovedområder: 1. Grafreduktion foretaget i parallel, 2. Klassiske numeriske algoritmer implementeret på en parallel grafreduktionsmaskine, 3. Numerisk løsning af strømningsligninger og 4. Wavelets og muligheden for anvendelse af disse i numeriske algoritmer (Martin Funk Larsen).
Parallelle algoritmer til optimeringsproblemer: For mange af de lette kombinatoriske optimeringproblemer er det i praksis vanskeligt at konstruere effektive parallelle algoritmer, selvom der teoretisk set findes massivt parallelle, effektive løsningsalgoritmer. Der er arbejdet med at undersøge årsagen hertil i forbindelse med distribuerede datastrukturer for korteste vej-problemer, samt påbegyndt undersøgelse af en ny klasse af dualitetsbaserede algoritmer, de såkaldte auktionsalgoritmer (Jens Clausen).; Som en del af et Ph.D-studium er der arbejdet med udvikling og implementation af parallelle Branch and Bound algoritmer for tre forskellige optimeringsproblemer. Nye - meget simple - strategier har vist sig at være konkurrencedygtige med traditionelle algoritmer, der normalt er væsentligt mere komplicerede at implementere. I forlængelse heraf er en anden mere traditionel strategi blevet udviklet, dog med væsentligt anderledes kommunikation end normalt. Foreløbige resultater tyder paa meget høj ydeevne for denne algoritme (Per Laursen).; Der er arbejdet med transputer-implementation af distribuerede algoritmer til løsning af enkelt-kilde korteste-vej problemet. En artikel, der sammenligner distribuerede versioner af Dijkstra's og Moore's algoritmer er sendt til en konference. En kort artikel omhandlende en optimal parallel algortime til løsning af problemet, er også færdiggjort. Denne danner basis for endnu en konkret implementation (Jesper Träff).
Objektorienterede distribuerede systemer: Det tidligere udviklede objekt-orienterede programmeringssprog, Emerald, er udvidet med faciliteter til såkaldt broadcast, således at et procedurekald kan sendes samtidigt og pålideligt til en række andre objekter. Et database forespørgselssprog er integeret ind i Emerald. Tillige undersøges, hvorledes en version af Emerald vil virke i et netværk med flere end 10⁵ datamater. Satellitnavigationssystemet GPS åbner nye muligheder for at give en pilot nøjere oplysninger om position og bevægelse af hans fly. Der forskes i udvikling af metoder og programmel hertil (Eric Jul).; En fuldstændig, parallel og robust spildopsamlingsmetode for distribuerede, objekt-baserede systemer er udviklet og implementeret i køretidssystemet for Emerald. Metoden udmærker sig ved at opsamle alt spild, også i et kørende distribueret system. Metoden er endvidere robust overfor fejl hvor dele af det distribuerede system er midlertidig utilgængelige. Systemet er optimeret ved hjælp af målinger af systemets ydeevne under samtidig brug af almindelige programmer (Niels Chr. Juul).; Som speciale-projekt udvikledes et objektorienteret databasesystem baseret på Emerald-systemet. Nu arbejdes specielt med persistens og objektorienterede søgesprog og på en artikel, `Nested Queries implemented in Emerald' (Niels Elgaard Larsen).; Programmeringssprog for fin-kornet parallelle datamater har traditionelt været lav-niveau sprog med tilføjet udvidelser. I forskningsprojektet om dette emne er der skabt og afprøvet et nyt sprog, Ellie, der er født til at beskrive løsninger af opgaver med fin-kornet parallelitet. Sproget er objekt-orienteret og tillader programmering på højt abstraktionsniveau, således at programmer bliver mindre afhængige af datamatens opbygning end tidligere. Projektet vil fortsætte fremover og inddrage datamater med beregningsenheder af forskellige typer (Birger Andersen).
Konstruktion og analyse af algoritmer: Et mål har været at udvikle algoritmer (f.eks. for stabil partitionering og sortering), som bruger minimalt arbejdslager. Et andet mål har været at udvikle randomiserede algoritmer, der er mere effektive end deterministiske algoritmer, som løser samme problem (f.eks. determination af det nærmeste par og konstruktion af Voronoi-diagram for punkter i planen).; Det er også undersøgt, hvordan man manipulerer datastrukturer (f.eks. en ordbog) parallelt. således at processorerne ikke generer hinanden. Arbejdet er sket sammen med andre forskere fra forskellige algoritmegrupper i Europa (Dortmund, Joensuu, Linköping, Lund, Saarbrücken, Tammerfors og Åbo) (Jyrki Katajainen).

Datamatsyn (hovedindsatsområde)

Formålet med forskningen er at konstruere og afprøve metoder og algoritmer til automatisk beskrivelse af omverdenen ud fra billeddata. De efterfølgende projekter benytter alle DIKUs billedlaboratorium, der indeholder udstyr til billedoptagelse og billedanalyse med en særlig billeddatamat (der også kan behandle billedsekvenser) og en to-akset robot, der indeholder en styrbar kameraplatform. Projekterne vedrører visuel udforskning af omverdenen (aktiv vision), overvågning, sensing-strategier samt lukket sløjfe styring, hvor næste kameraposition afgøres ud fra en analyse af de foregående billeder.

Et princip om maksimal datakompression har været anvendt i et forsøg på at løse Overvågningsproblemet. Dette problem går ud på at skrive et program, som skal slå alarm, når noget uventet sker. Programmets data er en løbende række billeder af en scene i bevægelse. Denne scene kan for eksempel være en maskine, som skal udføre ganske bestemte bevægelser. Programmet overvåger maskinen, og slår alarm, hvis den udfører uventede bevægelser som tegn på slitage eller som tegn på at instruktionerne til maskinen er forkerte. Programmet har været afprøvet på sekvenser af billeder, som er optaget i DIKU's billedlaboratorium (Peter Johansen).

Elektronisk nethinde: Ved indledende billedanalyse, som danner grundlag for en senere billedfortolkning, skal billedet segmenteres, dvs. opdeles i geometisk meningsfyldte elementer. Metoder til segmentering og kantdetektion ved hjælp af højparallele elektroniske kredløb (en elektronisk nethinde) er blevet undersøgt og kredsløbet er blevet simuleret på datamaskine. Desuden er nogle metoder til grovsegmentering ved hjælp af primitive formoperationer (morfologiske operationer) blevet afprøvet (Jens Damgaard Andersen).
Time-to-contact: Mange paradigmer indenfor datamatsyn er ikke tilstrækkelige til autonome seende maskiner. De bør reformuleres uden brug af begreber som absolutte afstande, hastigheder og orienteringer. Der arbejdes med et time to contact-begreb, hvor tiden til udpegede features rammer billedplanet beregnes. Dette tillader meget enkle og nok så vigtigt direkte mål for bl. a. scenens dynamik, transparens og deformation. Foreløbige eksperimenter viser gode resultater. Et samarbejde med universiteter i Aalborg, Genoa og Boston er etableret (Jens Arnspang).
Bevægelsesinvarianter: Udfra en billedsekvens optaget med et perspektivisk kamera kan der udledes numerabelt mange bevægelsesinvarianter for en tredimensional ret linie i bevægelse. For en given bevægelse bestemmer invarianterne et lineært ligningssystem til bestemmelse af liniens 3D orientering samt dennes tidsafledede til vilkårlig høj orden. For et perspektivisk kamera med variabel brændvidde kan bevægelsesinvarianterne omskrives til et lineært ligningssystem til bestemmelse af en 3D stationær ret linies orientering. For en ret linie med en regulær textur kan liniens forsvindingspunkt og dermed dens orientering bestemmes udfra ét billede optaget med et perspektivisk kamera (Knud Henriksen).; Forskningen i metoder til estimation af af mængden af støj i billeder er fortsat. Metoden til estimation af epipolarlinieligningen for et stereobilledpar er forbedret. Studiet af aktiv billedanalyse og analyse af informationsstrømme i en seende robot er nye forskningsområder, som bl.a. har omfattet udvikling af en metode til `parametriseret kalibrering' af et kamera monteret på en bevægelig platform (Søren I. Olsen).; I forbindelse med regularisering er brugen af genetiske algoritmer til diskontinuert regularisering og skalarumsudvidelser af diskontinuert regularisering undersøgt. Endvidere er regularisering anvendt til at finde binokulære stereokorrespondancer i en model, hvor der tages højde for diskontinuiteter i dybden og at nogle områder kun er synlige i det ene kamera. Endvidere undersøgelse af time-to-contact for et kamera, der ikke blot translaterer (Mads Nielsen).
Kantdetektorer: Der har været arbejdet med syntetiske billeder som redskab i forbindelse med aftestning og kalibrering af kantdetektorer. Målet er at konstruere et sæt af billeder, der har bestemte kvantitative egenskaber, og derved kan illustrere specifikke egenskaber ved algoritmer til kantdetektering (Klaus Hansen).

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 datamatiske værtø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, Liam Bannon og Randi Andersen).

Edb i offentlig administration: I samarbejde med cand.oecon. Helge Korsbæk arbejdes der med at kortlægge, hvilke virkemidler og politikker, der har præget edb-anvendelsen i det offentlige Danmark gennem årene. Arbejdet foregår delvist inden for rammerne af et fælles-europæisk forskningsprojekt til belysning af karakteristika og erfaringer med udvikling og anvendelse af datasystemer i offentlig administration (Erik Frøkjær).
Strategier for systemudvikling: Der arbejdes videre med at undersøge, hvordan udvikling af edb-systemer foregår i praksis. Studiet fokuserer på udviklingsstrategier samt på kooperations- og kommunikationsformer i arbejdet. 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): Det langsigtede mål er at opbygge en uddannelse for design af edb-systemer. I årets løb er der arbejdet med at udvikle metoder og arbejdsformer, der understøtter et brugerrettet systemdesign. Fortællingen ses som det centrale omdrejningspunkt i et sådant systemdesign, idet det herigennem vil være muligt - allerede i udviklingsarbejdet - at iværksætte en dialog med fremtidige brugere af edb-systemet om kvaliteten af edb-systemet (Hasse Clausen).
Edb-støtte til fagfolks tekstsøgning: Tekstsøgning er den aktivitet, hvor mennesker søger information i skrevne tekster. Som eksempler på fagfolks tekstsøgning ses på juristers, kemikeres og systemudvikleres dokumentationsarbejde. I projektet lægges særlig vægt på at bringe søgesystemet i tæt kontakt med fagfolkenes arbejdssituation og give dem mulighed for på en kontrolleret måde selv at ændre søgesystemet (Morten Hertzum).; Der arbejdes, i samarbejde med en gruppe andendelsstuderende, med opbygningen af et tekstsøgessystem til edb-dokumentation til støtte for programmører med henblik på eksperimentel afprøvning af forskellige brugergrænseflader (Erik Frøkjær og Morten Hertzum).
Computer Supported Cooperative Work (CSCW): Der er arbejdet med at afklare, hvordan det nye forskningsfelt Computer Supported Cooperative Work (CSCW) kan konstitueres som et selvstændigt videnskabeligt område med egne begreber, metoder og teorier. I stedet for simpelthen at definere CSCW som udvikling af "groupware", foreslås det at forskningen fokuserer på edb-støtte til kooperativt arbejde i almenhed.; Der er desuden (som en del af EF-programmet COST CoTech Action) arbejdet med evaluering af eksisterende systemer og med udvikling af nye konstruktionsbegreber for fremtidige CSCW-systemer. Dette arbejde fortsættes i projektet COMIC under det nye EF-program, ESPRIT Basic Research Action (1992-1995) (Liam Bannon).
Arbejdsdeling og kooperation 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 projektet gennemføres empiriske studier af samarbejde i systemudviklingsprocesser på tværs af organisatoriske skel og faggrænser. Disse studier kan fungere som basis for udviking af teknikker og værktøjer, der kan støtte processen (Jacob Nørbjerg).
Om at forstå i systemarbejde: Projektet belyser opbygningen af forståelse i systemarbejde. Det præsenteres, hvordan emnet er behandlet indenfor datalogien, og centrale problemstillinger med dyberegående filosofiske betragtninger forfølges. Antagelserne om betydningen af praksis samt af dialogen for opbygning af forståelse undersøges ved empiriske studier (Randi N. Andersen).

Øvrige forskningsområder

Map Theory: En doktordisputats, Map Theory, der introducerer et alternativ til mængdelære som matematisk fundament, er forsvaret. Map Theory udmærker sig fremfor mængdelære ved at kunne bruges som programmeringssprog (Klaus Grue).
Datanetprogrammel: Der har i det forløbne år været fokuseret på problemstillinger i forbindelse med den praktiske anvendelse af moderne netværksfaciliteter inden for forskningssektoren, herunder specielt elektronisk post efter X.400, i lille og i stor målestok. Der er tale om problemstillinger inden for Network Management, og af organisatorisk art i forbindelse med Naming and Addressing, Routing og Gatewaying. Arbejdet er sket i forbindelse med etableringen af et EF-støttet pilotprojekt i Danmark (Klaus Hansen).; I logikprogrammering er arbejdet videre med Montagues intensionelle logik samt Kamps diskursrepræsentationsteori. Desuden er der arbejdet med Jens Erik Fenstads varianter af situationssemantiske teorier, alt sammen inden for rammerne af det ny og spændende paradigme induktiv logikprogrammering. Ved et induktivt logikprogrammeringsproblem forstås her problemet at konstruere et datamatisk system S som med anvendelse af en vis baggrundsviden B og med konstatering af visse positive kendsgerninger E+ og visse negative kendsgerninger E- automatisk kan inducere en passende hypotese H således at B og H implicerer E+ samtidig med at H, B og E- er opfyldelige. Her er E- tom, B syntaktisk, og E+ vedrører logisk repræsentation (Gregers Koch).
Logikprogrammering og vidensbaserede systemer: Der arbejdes med systemudviklingsmetoder, der omfatter videnstilegnelse, vidensrepræsentation, modellering, generelle og specifike problemløsnings metoder. Logikprogrammeringens ideer og metoder muliggør rapid prototyping, dvs. gradvis systemudvikling, støtte til menneskelig begrebsudvikling og problemløsning. Problembeskrivelser og information - hyppigt baseret på formulering i naturligt sprog - er ofte ufuldstændige. Nuværende anvendelsesområder omfatter planlægning af huse og lejligheder, byplanlægning, konstruktion af stålgitterstrukturer, integritetsbehandling af databaser samt støtte til matematikundervisning (László Béla Kovács).; Har fortsat beskæftiget sig med studier over den menneskelige videns natur, med henblik på en afklaring af datalogisk relevante spørgsmål såvel om den indsigt, der indgår ved programmørers udvikling af programmer, som om den mulige simulering af menneskelig tankevirksomhed. I studierne inddrages synspunkter fra såvel psykologi som filosofi, lingvistik og logik. Der sigtes mod en sammenhængende monografisk præsentation (Peter Naur).; Zhuqing Ma er gæsteforsker på DIKU fra juli 1992 til februar 1993. Der er i dette år arbejdet med humansproglige grænseflader til databaser og videnbaserede systemer med særligt henblik på biblioteksystemer. En stor del af tiden ved opholdet her i København er dog gået med studium af mere fundamentale problemstillinger inden for emner som databaseteknologi, logikprogrammering og humansproglig tekstanalyse med særligt henblik på forespørgsler formuleret i simpelt engelsk (Zhunquin Ma).
Differentiation ud fra funktionsværdier: Til at estimere differentialkvotienter benyttes oftest en polynomiel approksimation af funktionen, hvor polynomiet fås ved mindste kvadraters metode eller ved interpolation i nulpunkterne for et Chebyshev-polynomium af 1. grad. Lokale funktionsværdier vægtes dog betydeligt mere, hvis man benytter en polynomiel approksimation af differenskvotienter af funktionsværdierne, og nulpunkterne i Chebyshev-polynomierne af 2. grad (ikke 1.!) synes at være en optimal placering af interpolationspunkter, når man tager hensyn til såvel metodens støjfølsomhed som dens trunkeringsfejl (Jørgen Sand).
Konsistenscheck i relationsdatabaser ved hjælp af PROLOG: I mange år har der været enighed om det ønskværdige i at kunne checke vilkårlige konsistenskrav i en relationsdatabase, men det skorter i praksis på at finde en håndterlig måde at gøre det på. I det forløbne år er sammen med László Béla Kovács publiceret en artikel, der viser, hvor nemt konsistenskrav kan udtrykkes ved hjælp af logikprogrammeringssproget PROLOG. Det næste skridt bliver at implementere disse check ved at sammenkoble databasesystemet INGRES med PROLOG (Torben Zahle).
Datamodeller og lagringsstrukturer: Arbejdet er fortsat inden for 3 områder med tilknytning til databaser: 1) Opbygning af en ny datamodel for Geografiske Informations Systemer, hvis fundamentale princip er, at de positionelle og rumlige egenskaber ved geografiske elementer lagres uafhængigt af vilkårlige grafiske repræsentationer (kort). 2) Udvikling af en generel datamodel, som integrerer elementer fra objekt-orienterede, deduktive (logik-baserede) og semantiske modeller, hvorved såvel strukturelle som semantiske aspekter af modellen kan beskrives homogent. 3) Udvikling af en metode til lagring af dynamiske hash-filer, hvor overløb lagres uden brug af pegere (Peter Kjellberg).; Klaus Havelund (Ph.D.-studerende) har udarbejdet fork calculus, der kan bruges som grundlag for beskrivelse af parallelle sprog (Klaus Havelund).

Fondsstøtte

Statens Naturvidenskabelige Forskningsråd

DART: Design, Analysis and reasoning abaout Tools (Fælles med Datalogisk Afdeling ved Aarhus Universitet og Institut for Elektroniske Systemer, Aalborg Universitetscenter) (TOPPS-gruppen ved Neil D. Jones; endvidere Klaus Grue) (for 1992 til hele projektet) kr. 2.600.000
Datamatsynsmetoder til billledanalyse (Peter Johansen) kr. 325.000
Simple og effektive parallelle Branch and Bound algoritmer til løsning af NP-komplette kombinatoriske optimeringsproblemer (Per Storgaard Laursen) kr.274.559
Center for anvendelse af paralleldatamater (Stig Skelboe) (i alt 8 institutioner på DTH og KU samt UNI•C) kr. 4.000.000

Statens Teknisk-videnskabelige Forskningsråd

Informationsstrømme i en seende robot (Søren Olsen) kr. 329.705
Effektive programanalyser og automatiske programtransformationer (Lars Ole Andersen) kr. 316.517

Forskerakademiet

Studieophold 9 mdr. i Glasgow (forlængelse) (Carsten Kehler Holst) kr. 50.100
Studieophold 1 år i London (forlængelse) (Thomas Phillip Jensen) kr. 60.000
Studieophold 1 år i Paris (forlængelse) (Klaus Havelund) kr. 58.600
Introduktionsstipendium (Per S. Laursen) kr. 25.200
Gæstestipendiat Djordje Kadijevic 8 mdr. (László B. Kovács) kr. 30.300

EF-kommisionen

TEMPUS EF-JEP-0955-92/3 (tredie år) (Klaus Hansen) (I alt 489.200 ecu over 3 år) (Hovedkontrakt: Københavns Universitet, deltagere: Spanien, Tjekkoslovakiet, Ungarn, Bulgarien, Holland og Storbrittanien, i alt 8 universiteter) 190.900 ecu.
EF Value II Projekt 5801 (ISI-DK)(Klaus Hansen) Totalt 380.000 ecu, DIKU's andel 54.000 ecu.
ESPRIT Basic Research Action 3124 (Semantique) indtil 1. maj 1992 (Fælles med Imperial College, England, École Polytechnique, Frankrig og Glasgow University, Skotland. (Neil D. Jones, Anders Bondorf, Fritz Henglein, Torben Mogensen, Mads Tofte, Lars Ole Andersen, Jesper Jørgensen, Christian Mossin og Mads Rosendahl). DIKU's andel i 1992 kr. 280.000
ESPRIT Basic Research Action 6809 (Semantique) fra 24 juli 1992 (Fælles med Imperial College, England, École Normale Supeieure, Frankrig, Glasgow University, Skotland og Göteborgs Universitet, Sverige) (Neil D. Jones, Anders Bondorf, Fritz Henglein, Torben Mogensen, Mads Tofte, Lars Ole Andersen, Jesper Jørgensen, Christian Mossin og Mads Rosendahl). DIKU's andel i 1992 kr. 40.000

Team Danmark

Konkurrencemæssig udnyttelse af GPS-systemet (Eric Jul) kr. 18.500

Indberettede publikationer til PUF 92

Kan ses i Årbogen 1992 hos Randi Løvgreen (S202).

Ph.D.-afhandlinger

Andersen, Birger: A General, Grain-Size Adaptable, Object-Oriented Programming Language for Distributed Computers

Jensen, Thomas: Abstract Interpretation in Logical Form (ved Imperial College, University of London)

Afhandlingerne findes på Datalogisk Institut.

Specialer

Andersen, Lars Ole: C Program Specialization

Bassan, Yigal og Christian Bastlund: Edb-anvenderens oplevelse- en metode til forståelse

Bjerregaard, Peter Iben: Implementering af en cps-compiler

Christensen, Dan: Euklidiske Steiner-problemer med forhindringer

Christensen, Morten Schantz: Bayesnet - analyseret og videreudviklet

Christensen, Ole Kjær: Computer Chess - Experiments in Search Algorithms

Christoffersen, Kim: Automatisering af spillet af kortene i bridge

Dalby, Joakim: Database-Håndbogen fra design til brug

Dalby Per, Svend Enevoldsen og Grith Riise: Kommunikationsfunktioner for et netværk af transputere

Göttsche, Paul: Et hjælpesystem til Nimbus

Gabe, Christian og Peter Berggreen: Automatisk persongenkendelse ud fra portrætbilleder

Garde, Michael og Niels Quistgaard Hansen: Multiprogrammering i C++

Hendeles, Allan: Kvantisering af billeder

Jørgensen, Jesper: Compiler Generation by Partial Evaluation

Jørgensen, Jes Sixtus: Ray-tracing metoder

Jørgensen, Carsten: A Study of Algebraic Specifications and their Semantics

Jacobsen, Henrik Friborg: Specialisering af C programmer

Jensen, Line: Brugerindsigt i det moderne edb-brugermiljø

Jensen, John Bach og Thomas B.E. Andersen: Anvendelse af compilertime analyse

Kjeldsen, Jon og Sju Thorup: Økonomisk og organisatorisk belysning af edb-investeringerne

Koch, Poul Thorsgaard: Efficient two-level Scheduling in a Distributed Shared Memory Environment

Larsen, Morten: Automatisk fremskrivning af vejrradar-billeder

Larsen, Niels Elgaard: An Object-Oriented Datbase in Emerald

Larsen, Uffe Birkerod: Sammenligning af Anisotrop Diffusion og Retinasimuleringer

Larsen, Ulf Rangholm og Lilja Thorsbro: Kvalitative aspekter ved et edb-system

Ludwig, Jan: Distribuerede databaser - med fokus på tilgængelighed

Marquard, Jacob: Porting Emerald to a Sparc

Navaretta, Constanza og Keld Knudsen: Editor for labanotation med tilhørende prototype til animation af en tredimensional menneskelignende figur

Nielsen, Dan Allan: Kvalitative aspekter i den grafiske branches edb-værktøjer

Nielsen, Ole: Et interaktivt dokumentationsværktøj med datamodel som brugergrænseflade

Oliveira, Marc de og Dominik Krøll: Advanced Development Tools for Pascal

Olsen, Barbara og Morten Bune Rasmussen: Effektiv produktionsplanlægning - om flowshop schedulering

Pagh-Rasmussen, Jens: Økonomisk og organisatorisk belysning af edb-investeringerne

Pedersen, Kurt Fog: Neuronen- Byggestenen i Neurale Netværk.

Rømer, Bo: Existence of Finete Projective Planes

Rose, Kristoffer Høgsbro: GOS - Graph Operational Semantics

Skjoldbirk, Marlene: En optimizer til relationsdatabaser

Spliid, Mikael: Krav til kravspecifikationer

Stensgaard, Bjarne og Morten Marquard: Partial Evaluation of an Object-oriented Imperative Language

Thorsen, Peter: Distribueret raytracing

Thrysøe, Christian Jørgen: Indførelse af persistente objekter i C++

Vieira, Lucy Martins: Konsistens i det Distribuerede Directory-System

Whitt, Michella: Brugerdeltagelse i systemudviklingsprojekter

(Specialerne findes på Datalogisk Institut)