Wiskunde en Informatica

1.3. VF-programma: DISCRETE STRUCTUREN 3
VF-code: TUE.WSK.303.90.25
Programmaleiding: prof.dr. A.E. Brouwer, prof.dr. A.M. Cohen, prof.dr.ir. H.C.A. van Tilborg (Wsk/I), prof.dr.ir. J.P.M. Schalkwijk (E)
Wetenschapsgebied ISN: 1204, 1299 Discrete Wiskunde, 3325

Wetenschapsgebied NWO: P110, T 180

Toepassingsgebied NABS: N025

A. Eindige meetkunde

1. (Eindige) meetkunde en designtheorie   Een artikel over bijna veelhoeken en Fischer ruimten werd voltooid i.s.m. J.I. Hall.

  Een karakterisatie van de meetkunde van hyperbolische lijnen in een niet ontaarde polaire ruimte van eindige orde werd gegeven.

  De meetkunde die ontstaat na wegsnijden van een hypervlak uit de Grass­mannruimte van een projectieve ruimte werd als diagrammeetkunde gekarak­teriseerd.

  Universele inbeddingen van partieel lineaire ruimten in projectieve of affiene ruimten zijn onderzocht.

  De dimensies van de universele inbeddingen van een aantal bijna veelhoeken zijn onderzocht i.s.m. S.V. Shpectorov.

  Bewezen werd dat het complement van een hypervlak in een eindige bij­na veelhoek gewoonlijk samenhangend is.

  Een gemeenschappelijke generalizatie van de nucleistelling van Blokhuis en Wilbrink en de blockingset stelling voor het affine vlak van Brouwer, Schrijver en Jamison werd geformuleerd en bewezen.

  Restricties op het aantal punten van een Partial Unital en van Strong Represen­tative Systems werden afgeleid.

  De p rangen van orthogonale ruimten zijn bepaald i.s.m. Eric Moorhouse.

Toepassingen zijn ondere andere non existentie van ovoiden in zekere gevallen en een expliciete basis voor de code opgespannen door de lijnen in het projectieve vlak.

  De doorsnede van projectieve vlakken: Een grens werd bepaald voor het aantal lijnen dat twee verchillende projectieve vlak structuren op een verzameling gemeen kunnen hebben.

  De minimale afmeting van een blocking set in PG(2,27) werd bepaald.

  Er werd een ondergrens afgeleid voor het aantal verzamelingen waarin de punten van de hyperkubus kan worden gepartitioneerd zo dat tussen twee parten altijd een verbin­ding aanwezig is.

  Karakterisaties van Planar Spaces met weinig vlakken (d.w.z. weinig meer dan een driedimensionale projectieve ruimte) werden gegeven.

  Bekeken is een aantal gevallen waarin semimodulaire tralies ingebed kunnen worden in iets grotere semimodulaire tralies, vergelijkbaar met de inbedding van een affiene ruimte in een projectieve.

  Een overzichtsartikel "Polynomials in Finite Geometries and Combinatorics" werd geschreven.

2. Grafentheorie

  M.b.v. gedraaide Chevalley groepen zijn 2 boog transitieve pentagrafen en heptagrafen geconstrueerd, i.s.m. J. Huizinga.

  I.s.m. D.G. Fon der Flaass en S.V. Shpectorov zijn de grafen gevonden die lokaal

co Heawood zijn. Het blijken er drie te zijn.

  Van een aantal sterk reguliere grafen is bepaald of zij gehalveerde afstandsregu­liere grafen zijn.

  De metrische hierarchie, in het bijzonder met betrekking tot afstandsreguliere grafen, werd onderzocht i.s.m. S.V. Shpectorov.

  De volledig reguliere codes in onder andere de Biggs Smith graaf zijn bepaald. Dit leidde tot het weerleggen van het vermoeden van Martin over de parameters van volledig reguliere codes.

  Een generalisatie van de stelling van Egawa werd bewezen.

3. Groepentheorie

  De structuur van Weylmodulen voor de symplectische groep is onderzocht; meer in het bijzonder zijn de compositiefactoren van Weyl modulen met fundamenteel gewicht bepaald.

  I.s.m. J.I. Hall is de classificatie van centrumvrije 3 transpositiegroepen voltooid, en werden de resultaten tot een artikel verwerkt.

  Op een meetkundige wijze werden de groepen bepaald die voortgebracht worden door een conjugatieklasse van k transvectieondergroepen.

  Er werd een grafentheoretische karakterisatie gegeven van de enkelvoudige

groep Co₂. Tevens werd een karakterisatie gegeven van een lijnensysteem in R ²³ gerelateerd aan de groep Co₂₃.

  De groep SL₂ K, met K een Cayley delingsalgebra, werd bestudeerd.

Deze groep werd gekarakteriseerd via de werking op het natuurlijke moduul K ².

B. Coderingstheorie en cryptografie

1. Coderingtheorie

  In verband met het in Veldhoven gehouden ``International symposium on the occasion of the 60 th birthday of Jack van Lint'' is in samenwerking P.J. Cameron een dubbel­nummer van Discrete Mathematics (en een boek) tot stand gekomen onder de naam ``A collection of contributions in honour of Jack van Lint''.

  Een alternatief algoritme is gegeven om Fire codes te decoderen. Een bijkomend voordeel van deze methode is dat het burst correctie vermogen van Fire codes meteen eruit volgt.

  Een studie is gemaakt van de mogelijkheid tot het verbeteren van fouten voorbij de gegarandeerde foutenverbeteringsmogelijkheid van sommige eindige meet­kunde codes.

  Een voortsel is gedaan om (d,k ) beperkte rijen te beschermen tegen een beperkt aan­tal fouten, piekverschuivingen en toevoegingen en verdwijningen van symbolen.

  Er is verder onderzoek verricht naar de constructie en niet existentie van asymmetric en unidirectional error correcting codes.

  Voor asymmetric error correcting codes zijn verscheidene natuurlijke definities van perfectheid gegeven en geanalyseerd.

- In tegenstelling tot wat algemeen aangenomen werd, is nu aangetoond dat de capaciteit van het Gaussische optelkanaal willekeurig dicht benaderd kan worden met een puntenverzameling waarin alle punten dezelfde kans van voorkomen hebben.

  Decodeeralgoritmes met een lagere complexiteit zijn ontwikkeld voor trelliscodes die gebaseerd zijn op latticepartities Z⁴/₂D₄ en Z⁸/E₈. Hierbij is gebruik gemaakt van een soft decision decodeeralgoritme van de Reed Muller code RM(1,3).

  Een multilevel beschrijving van de binaire extended Golay code is gegeven die resulteert in een maximum likelihood decodeermethode van deze code met een complexiteit van 455 bewerkingen (ten opzichte van 650 voorheen). Voor het decodeeralgoritme van de Leech lattice geeft deze aanpak een verbetering van 400 bewerkingen.

  Er is gewerkt aan het broadcast channel met betrouwbare berichten met publieke communicatie.

  Er is onderzoek verricht naar het Wiretap channel WTCII.

  Er is onderzoek verricht naar fouten corrigerende paren voor cyclische codes.

De MDS codes van minimumafstand 5 die een 2 fouten verbeterend paar hebben zijn gekarakteriseerd.

  Een verbetering van de Van Wee grens voor lineaire overdekking werd verkregen.

  Enkele verbanden tussen overdekkingen, lineaire codes en de structuur van de duale code zijn afgeleid, resulterend in een aantal nieuwe ondergrenzen voor lineaire codes met kleine overdekkingsstraal.

  De uniciteit van de binaire [27,7,12] code werd bewezen.

  Een nieuwe versie van T. Verhoeff's tabel met onder  en bovengrenzen voor de grootst mogelijke minimum afstand van binaire codes met gegeven woordlengte en dimensie werd uitgebracht. Dit leidde tot tal van nevenactiviteiten. Een verscherping van Delsarte's lineaire programmerings grens is uitgerekend, en bleek tot talrijke ver­beteringen van bekende bovengrenzen te leiden. De bovengrens van Johnson werd verscherpt. Dit leidde tot het bewijs i.s.m. L. Tolhuizen dat er geen lineaire binaire codes bestaan met de parameters van eenmaal ingekorte Preparata codes.

Een daemon genaamd Asmodeus werd geschapen   deze geeft volautomatisch antwoord op al uw vragen, mits juist geformuleerd.

1A.Algebraisch meetkundige coderingstheorie

  Een expliciet decodeeralgoritme voor AG codes is geconstrueerd dat fouten tot de halve ontwerpminimumafstand verbetert.

  Er is onderzoek gedaan naar:

Een twee variabelen zeta functie voor krommen over een eindig lichaam.

De gemiddelde gewichtsverdeling van AG codes.

Het "partition design" van een divisoren klassegroep.

Klassegetallen van zekere hyperelliptische krommen.

Aurifeulliaanse factorizatie met behulp van Zeta functies.

MDS codes op hyperelliptische krommen.

Karakterizatie van zelfduale AG codes.

Expliciete constructie van Drinfeld modulaire krommen en hun codes.

1B.Informatie  en communicatietheorie

  Er is een overzichtsartikel over tweewegkanalen verschenen in het tijdschrift "Discrete Mathematics". In het project AXE wordt een programma ontwikkeld waarmee coderings­strategiën voor tweewegkanalen geconstrueerd kunnen worden.

Het project is zodanig gevorderd dat een diskette met het programma uitgegeven kan worden. Begonnen is met de verspreiding onder studenten van de colleges Infor­matietheorie I en II en geïnteresseerde personen, waaronder enkele hoogleraren Telecommunicatie.

Er zijn reeds coderingsstrategiën met transmissiesnelheid groter dan Shannon's onder­grens van 0,61695 bit per transmissie per richting gevonden.

  Een nieuw promotieonderzoek naar feedback strategiën voor niet deterministische eenwegkanalen is gestart. Er zijn nieuwe adaptieve feedbackmethoden gevonden die geschikt zijn voor kanalen met grote foutenkansen. De transmissiesnelheden van deze strategiën liggen boven de zogenaamde Berlekamp grens.

  Een bespreking van het nieuwe standaardwerk over informatietheorie van T. Cover en J. Thomas werd geschreven.

2. Cryptografie

  Voor het ``Handboek Telematica'' bij Samson Bedrijfsinformatie is het hoofdstuk ``Een inleiding in de cryptologie'' geschreven.

  Voor Van Lanschot is een voorstel gedaan voor de beveiliging van hun Lansnet.

  In samenwerking met PTT Research Lab is een methode ontwikkeld, geimple­menteerd en geanalyseerd om Boolean functies te benaderen door woorden uit een bepaalde orde Reed Muller codes.

  Eveneens in samenwerking met PTT Research Lab is de veiligheid van het McEliece

public key cryptosysteem getoetst met betrekking tot information set decoding. Hierbij is een uitvoerige vergelijking van mogelijke decodeertechnieken van lineaire codes zonder verdere structuur gemaakt.   Een beschrijving en cryptologische analyse van een geautomatiseerd tolheffingssysteem en van een electronisch geldsysteem is in samen­werking met INTERCAI uitgevoerd.

  Een bijdrage ``Cryptology'' is verschenen in de Encyclopedia of Telecommuni­cations (Marcel Dekker Inc.).

B "Samenwerkingen"

Samenwerking op het gebied van de eindige meetkunde en grafentheorie bestaat met S. Bezrukov (Moskou), R. Calderbank (Bell Labs), P.J. Cameron (London), D. Fon der ­Flaass (Novosibirsk), C.D. Godsil (Waterloo), W.H. Haemers (KUB), J.I. Hall (Michi­gan), R. Hill (Salford), P. Johnson (Manitoba), F. Mazzocca (Napels), Th. Meixner (Giessen), K. Metsch (Giessen), E. Moorhouse (Laramie), A. Pasini (Napels), S.V. Shpectorov (Moskou), N.J.A. Sloane (Bell Labs), T. Szönyi (Buda­pest), J.A. Thas (Gent) en met tal van andere wiskundigen op meer incidentele basis.

1.4. VF-programma: PROGRAMMEREN
VF-code: TUE.INF.301.90.26
Programmaleiding: dr.ir. C. Hemerik, prof.dr. R.C. Backhouse, dr. A. Kaldewaij, dr. R.R. Hoogerwoord
Wetenschapsgebied ISN: 1101, 1203, 3304

Wetenschapsgebied: P110

Toepassingsgebied: N076, N070, N10
Beknopte inhoudelijke beschrijving van het programma
Het VF-programma Programmeren houdt zich bezig met diverse aspecten van het programmeren: ontwerpen van algoritmen en datastructuren, programmeertalen en implimentatieaspecten. Het programma is verdeeld in drie projecten:
Project 1

In het project ALPHA wordt onderzoek verricht op het gebied van lambda calculi, type­theorie en programmeertalen.

Er wordt een algemene en unificerende theorie van getypeerde lambda calculi opgesteld. Op basis van die theorie worden programmeertalen en programmalogica's ontworpen en bij­behorende programmeermethoden ontwikkeld.

Tevens wordt een systeem geimplementeerd voor de geintegreerde ontwikkeling van program­ma's en bewijzen.

Project 2
Dit project heeft tot doel het opstellen van taxonomieen van algoritmen en methoden op het gebied van compilerconstructie en implementatie. Het gaat daarbij om onderwerpen als scanning, parsing, attribuutevaluatie en codegeneratie. De classificatiemethode is ontworpen door Jonkers en eerder met succes toegepast op het onderwerp garbage collection.

Project 3

Programmeermethodologie.

Dit project behelst onderzoek van de fundamentele aspecten van programme­ren. Hieronder vallen programmeertechnieken bij diverse stijlen (functioneel, sequen­tieel, parallel), het ontwikkelen van

geschikte notaties voor specificaties en pro­gramma's en het opstellen van heuristieken voor het ontwerpen van correcte efficiënte programma's. Ook het redeneren over en het afleiden van ingewikkel­der datastructuren is onderwerp van onderzoek.

Een programmeercalculus gebaseerd op de relationele calculus, toegespitst op berekening met datatypen wordt ontwikkeld.

Voortgang van het onderzoek

Project 1: ALFA (typentheorie, lambda-culculi en programmeertalen).

Het onderzoek op het gebied van getypeerde lambda calculi heeft zich het afgelopen jaar geconcentreerd op het gebruik van zgn. Pure Type Systems (PTS).

Door Poll is een PTS ontworpen waarin programma's, specificaties, stellingen en bewijzen op uniforme wijze als lambda termen kunnen worden voorgesteld. Dit PTS maakt het mogelijk programma's en hun bewijzen hand in hand te ontwikkelen.

Als eerste stappen in de richting van een implementatie zijn door Poll, Hemerik en Van Dommelen (student) algoritmen ontworpen voor synthese van termen en typen in PTS'en en is door Poll de volledigheid daarvan bewezen voor de belangrijke subklasse van bijectieve PTS'en, waarmee een moeilijk open probleem een heel stuk dichter bij een oplossing is gekomen. Eveneens ten behoeve van implementatiedoeleinden wordt thans onderzocht hoe PTS'en kunnen worden uitgebreid met een definitiemechanisme.

Hemerik werkt al geruime tijd aan de implementatie van het systeem "Lolita", waarmee voor een grote klasse van PTS'en goedgetypeerde termen geconstrueerd kunnen worden. Dit werk is een voorstudie voor het later te ontwikkelen systeem "Lola" voor het geintegreerd ontwikkelen van programma's en bewijzen.

Nederpelt heeft zijn fundamentele werk over de fijnstructuur van de lambda calculus afgerond in een rapport, waarin ook expliciete substitutie, canonieke typering en segment­afkortingen worden behandeld. Nederpelt en mevr. Kamareddine, gast van de faculteit, hebben deze onderwerpen, met toelichting en voorbeelden, in een aantal artikelen samengevat. Mevr. Severi is haar werk als aio bij de faculteit begonnen met een studie van de getypeerde lambda calculus.

Project 2: Handboek van implementatiemethoden

Het werk op het gebied van implementatiemethoden heeft geresulteerd in een fraaie taxonomie van patroonherkenningsalgoritmen in strings. Deze taxonomie heeft de vorm van een boom, waarin de knopen overeenkomen met algoritmen en de takken met voor deze algoritmen relevante "details" van het probleem of de implementatie. Onder de bladeren van de boom treffen we een aantal bekende en zeer efficiente algoritmen aan - zoals Aho Corasick, Knuth ­Morris Pratt, Commentz Walter en Boyer Moore - alsmede een aantal nieuwe algoritmen. De correctheid van al deze algoritmen volgt uit de (triviale) correctheid van het algoritme in de wortel en het feit dat met elke tak in de boom een algoritme­transformatie correspondeert die correctheidbehoudend is.

Belangrijke voordelen van deze taxonomie zijn dat alle algoritmen beschreven worden in een uniform kader en dat in een oogopslag duidelijk is welke details voor een algoritme relevant zijn. Dit maakt een eenvoudige en exacte vergelijking van algoritmen mogelijk, in tegenstelling tot eerder gepubliceerde overzichten.

Een belangrijk nevenresultaat van het hierboven beschreven werk is, dat betrouwbare en volledige afleidingen verkregen zijn van de zgn. "pre computations" die voor bepaalde algorit­men noodzakelijk zijn. Voor het Boyer Moore algoritme zijn vele foute oplos­singen gepubli­ceerd, gecorrigeerd en weer gepubliceerd. Voor het moeilijker Commentz­ Walter algoritme was tot nu toe geen enkele volledige pre computation gepubliceerd.

Voorts is onderzocht hoe verschillende programmeermethoden kunnen worden gecom­bineerd bij het construeren van taxonomieen. Dit heeft geleid tot een alternatieve afleiding van de Aho Corasick algoritmen waarbij zoveel mogelijk de Bird Meertens methode gebruikt wordt voor de correctheidbehoudende transformaties, terwijl op geschikte plaatsen een conversie naar een equivalent imperatief programma gegeven wordt. Pas als implementatiedetails onvermijdelijk worden, wordt overgegaan op de methode van stapsgewijze verfijning van imperatieve pro­gramma's. Deze werkwijze heeft geresulteerd in een elegante afleiding die veel inzicht verschaft in de algebraïsche structuur van het patroonherkenningsprobleem.

Project 3: Programmeermethodologie

De eerste resultaten op het gebied van het redeneren over en het afleiden van data­structuren en bijbehorende programma's zijn in het verslagjaar vastgelegd in het proefschrift van Schoen­makers. Dit onderzoek is voortgezet. Het onderzoek richt zich op het verfijnen van algebra's tot datastructuren. Hierbij is een algebra een collectie basisverzamelingen met operaties (relaties) daarop en verfijningen zijn relaties tussen algebra's die de operaties respecteren. Een datastruc­tuur is een algebra die in een programmanotatie is beschreven. Voor een aantal klassieke datastructuren (zoals AVL bomen, leaf search trees, (a,b) bomen) is geprobeerd calculationele afleidingen te geven van programma's voor operaties op deze structuren. Hierbij zijn seg­mentproblemen uit het gebied van geometrische algoritmen bestudeerd en zijn een­voudiger en efficiëntere oplossingen voor een klasse queries gevonden. Ook is in samenwerking met de universiteit Groningen en Washington University St. Louis (USA) een parallelle implementatie van priority queues ontworpen en gepubliceerd.

In het afgelopen jaar is ook vooruitgang geboekt bij het onderzoek naar de invloed die programmeertaalconcepten en semantiek op de programmeermethodologie uitoefenen. Zo werd een vereenvoudigde rekenmethode voor het afleiden van programma's in een procedure geörien­teerde imperatieve taal ontworpen. Nader onderzoek is nodig naar de invloed van parameter­mechanismen en naar andere specificatievormen dan de klassieke predikaatparen. Ook is onderzoek voltooid naar een semantiek voor partieel on­gedefinieerde expressies.

Er is begonnen met onderzoek naar de inbedding van temporele concepten in de wp/wlp seman­tiek, met de bedoeling een alternatief voor temporele logica tot stand te brengen dat zich beter laat invoegen in calculationele programma afleiding. In het geval van discrete lineaire tijd is dit gelukt; voor reële en vertakkende tijd is verder onderzoek nodig.

Voor de komende jaren zal de aandacht vooral zijn gericht op: afleiden van logische pro­gramma's; alternatieven voor de verschillende vormen van temporele logica; vormen van specificatie; vergelijkend onderzoek van programmeerstrategieën.

Op het gebied "Programmeermethodologie voor speciale probleemklassen" is in het verslagjaar gekeken naar het afleiden van algoritmen voor problemen op gerichte grafen, door de bij­behorende specificaties uit te drukken in termen van een dekpuntsoperator. Veel problemen bleken gekarakteriseerd te kunnen worden door dezelfde eigenschap en aldus een algemene oplossing toe te laten. Door problemen verder te formuleren in termen van de abstracte datastructuren "set", "functie" en "partiële functie", en de daarbij ontwikkelde calculus toe te passen kon voor elke klasse van beschouwde problemen een korte, elegante afleiding gevonden worden. Het gebruik van regular algebra bij het afleiden van programma's voor graafproblemen is verder uitgebreid door het toe te passen op een klasse van problemen waaronder vallen depth first en breadth first search alsmede bepaalde kortstepadproblemen.

In verder onderzoek zal getracht worden nog enkele klassen van graafproblemen aan te pakken en bestaande klassen nog verder te generaliseren, met als doel na te gaan of de bekende programmeertechnieken voor kleine programmeerprobleempjes toepasbaar zijn op middelgrote problemen, als de juiste abstracties toegepast worden.

Op het gebied van de theorie van datatypen is onderzoek gedaan in wanneer twee datatypen "commuteren" en de gevolgen daarvan. (Een elementair voorbeeld is lijst en product; er is een functie die een paar van lijsten commuteert in een lijst van paren.) Een grote klasse van datatypen paren die deze eigenschap hebben is gedokumenteerd. Ook is er een verband gelegd met stellingen over powersets die relationele cata­morfismen uitdrukken in termen van functionele catamorfismen.

Onderzoek op het gebied van Galois connecties en clousure operatoren is afgerond. Er wordt nu gekeken hoe deze resultaten gebruikt kunnen worden om eigenschappen van adjuncties en monads (de bijbehorende categorische begrippen) te voorspellen en de gevolgen daarvan voor de constructie van simulaties en isomorfismen tussen datatypen.

De groep heeft bijgedragen aan de in september 1992 gehouden STOP zomerschool.

Samenwerking

In het kader van het SION project "Typed Lambda Calculi" wordt samengewerkt met KUN (Barendregt) en RUU (Van Dalen).

De TUE groep neemt via KUN deel aan een vervolgproject van de "Jumelage on Typed Lambda

Calculi", een samenwerkingsverband tussen een aantal Europese universitaire onderzoeksgroepen op het gebied van getypeerde lambda calculi.

In de Constructieve Algoritmengroep en de Algoritmen en Datastructurengroep wordt samen­gewerkt met Oxford University, Washington University St Louis, Rijksuniversiteit Groningen, Rijksuniversiteit Utrecht.

Samenwerking van de secties IS, TI en TT met KUB (Tilburg) en IPO in het kader van het SOBU samenwerkingsproject Dialoog­voering en Kennisopbouw. (DenK); op dit project is Borghuis aangesteld.

1.5. VF-programma: Parallallisme
VF-code: TUE.INF.302.90.26
Programmaleiding: prof.dr. M. Rem, prof.dr. J.C.M. Baeten
Wetenschapsgebied ISN: 1101, 1203, 3304

Wetenschapsgebied NWO: P110

Toepassingsgebied NABS: N076, N077, N070, N10
Beknopte beschrijving van het programma
Het VF-programma Parallellisme van de vakgroep Informatica bestaat uit twee projecten:

1. Ontwerp en implementatie van parallelle programma's.

2. Specificatie, verificatie en reïficatie van parallelle systemen
Project 1 legt zich toe op het ontwerpen van parallelle programma's die bestaan uit onderling communicerende processen, en op het implementeren van deze programma's op processornet­werken en als VLSI-chips. Project 1 bestaat zodoende weer uit drie deelprojecten:

1.1 Ontwerpmethoden (afleiden van parallelle programma's uit formele specificaties)

1.2 Netwerk-implementaties (implementeren van parallelle programma's op processor­net­werken)

1.3 VSLI-implementatie (implementeren van parallelle programma's als vertragings ongevoelige schakelingen)

Project 2 houdt zich bezig met de concurrency theorie, met name de specificatie, verificatie en reïficatie van parallelle of gedistribueerde systemen m.b.v. formele methoden. Het project bestaat uit twee deelprojecten:

2.1 Assertionele methoden.

2.2 Algebraïsche methoden.

In beide deelprojecten staat de theorie van concurrente en tijdkritische systemen centraal. In deelproject 2.1 wordt ook aandacht besteed aan betrouwbaarheid en foutbestendigheid van systemen.

Voortgang van het onderzoek

Project 1: Ontwerp en implementatie van parallelle programma's

Deelproject 1.1: Ontwerpmethoden

In het verslagjaar is een nieuwe methode ontwikkeld voor het ontwerpen van parallelle programma's; deze is kort samengevat in Hoofdstuk 2 van het dit jaar verschenen proefschrift van P. Struik. Doordat de nieuwe methode iteratief in plaats van recursief is, geeft hij de mogelijkheid om een veel wijder scala van oplossingen te onderzoeken; tevens maakt hij de ontwerpbeslissingen meer expliciet dan tot nu toe het geval was.

Het onderzoek naar het ontwerpen van grof korrelige programma's, die van belang zijn voor het uitvoeren op processornetwerken, is in dit jaar succesvol afgesloten. De ontwikkelde methode is vastgelegd in het bovengenoemde proefschrift.

Het door NWO gesteunde onderzoek naar het ontwerpen van onregelmatige pro­gramma's, zoals we die bijvoorbeeld in besturingssoftware tegenkomen, is vrijwel afgerond. De resultaten worden thans vastgelegd in de vorm van een proefschrift.

Deelproject 1.2: Netwerk implementaties

In het verslagjaar heeft zich een grote activiteit ontwikkeld rond het transputersysteem, waarbij het gebruik van het systeem zich heeft verplaatst van de programmeertaal OCCAM naar de, aan de RU Groningen ontwikkelde, taal Transputer Pascal. Het dit jaar gestarte transputer practicum heeft er met zijn meer dan 60 deelnemers voor gezorgd dat er thans een grote groep van gebruikers is. Er is een samenwerkingsproject begonnen met A.P.J. Jansen van de vakgroep Anorganische Chemie en Katalyse (Fac. Schei­kundige Technologie) op het gebied van de moleculaire dynamica. Een moleculair botsingsprobleem is succesvol geïmplementeerd op het transputersysteem.

Binnen de samenwerking met Shell Research (KSLA, Amsterdam) is dit jaar het onderzoek naar het op transputers implementeren van programma's uit de lineaire algebra afgerond met de verschijning van het proefschrift van L.D.J.C. Loyens. De samenwerking wordt voortgezet.

Deelproject 1.3: VLSI implementaties

De grote gebeurtenis binnen dit deelproject is de start geweest van het drie jaar lopende ESPRIT OMI project EXACT, waarin wordt samengewerkt met Philips (Nat. Lab.), IMEC (te Leuven) en de universiteiten van Manchester en Oxford. Doel van het project is de (industriële) toepasbaar­heid te onderzoeken van vertragings ongevoelige scha­kelingen. In dit kader is o.a. gewerkt aan de specificatie van een I²C interface. Tevens is de ontwikkelomgeving voor Tangram opera­tioneel gemaakt op de machines van de vakgroep. Binnen de samenwerking met Philips is dit jaar het proefschrift verschenen van C.H. van Berkel, dat het vertalen van Tangram programma's in vertragings­ongevoelige schakelingen behandelt. In hetzelfde kader is een door Philips betaalde AIO aangesteld, die onderzoek zal doen naar het testen van vertragingsongevoelige schake­lingen.

In het verslagjaar is ook het proefschrift van H.M.J.L. Schols verschenen. Dit behandelt het communicatiemodel dat ten grondslag ligt aan asynchrone schakelingen.

Het werk aan de silicon compiler VOICE, dat voornamelijk wordt uitgevoerd binnen de ontwerpersopleiding Technische Informatica, vordert goed. Thans wordt overwogen om naast de Silicon Graphics tools ook een back end te maken naar field programmable logic arrays.
Project 2: Specificatie, verificatie en reïficatie van parallelle systemen
Deelproject 2.1: Assertionele methoden.

Gerth hield zich, samen met Kuiper, bezig met interface refinement. Een eerst con­sistente en toepasbare theorie is geformuleerd en o.a. op CONCUR'92 gepresenteerd.

Een tweede, simpelere, versie van de theorie is in ontwikkeling. Daarnaast werkte hij zich in op het gebied van automatische verificatie methoden en schreef hiervoor een overzicht. Dit bevatte o.a. een efficiëntere automaat constructie voor de verificatie van (lineaire) temporele logica dan de gangbare. Tenslotte bestede hij tijd aan correctheids bewijzen voor cache consistency protocollen.

Kuiper heeft, samen met Penczek (Warsaw) en Golz (Karlsruhe), gewerkt aan het in kaart brengen van partiëele orde temporele logica's en equivalenties. Dit werd op CONCUR'92 gepresenteerd.

Hooman heeft samen met Schepers zijn verificatie formalisme uitgebreid voor de verificatie fouten tolerante systemen; hierin wordt de fout hypothese gespecificeerd als toegestane afwij­kingen t.o.v. het `correcte gedrag'.

E.e.a. is toegepast op een 'triple modular redundancy' protocol. Hij heeft samen met de Gast en Zhou een verificatie gedaan van een fouten tolerant, gedistribueerd membership protocol.

Huizing heeft gewerkt aan de analyse van het tijdsbegrip in specificatie talen voor reactieve systemen.

Dams heeft, samen met Grümberg (AT\&T) en Gerth, gewerkt aan de constructie van minimale modellen voor de automatische verificatie van programma's m.b.t. fragmenten van CTL.

Deelproject 2.2: Algebraïsche methoden.

Baeten heeft zich beziggehouden met procesalgebra's met tijd. In 1992 is een volledige integratie bereikt van real time en discrete time procesalgebra, met zowel relatieve als absolute tijd.

Daarnaast hield hij zich bezig met probabilistische procesalgebra, en schreef een overzicht over interleaving vs. partial order semantiek.

Mauw rondde het boek "Algebraic specification of communication protocols" af (editor samen met G. Veltink), dat zal verschijnen in 1993. Daarnaast hield hij zich in samenwerking met Philips Research bezig met interworkings en leader election protocollen. Hij is rapporteur aan de CCITT werkgroep Message Sequence Charts over de formele semantiek. Veel energie wordt besteed aan de verdere uitbouw van de PSF toolkit, een serie software tools ter ondersteuning van het ontwerp van parallelle of gedistribueerde systemen.

Verhoef schrijft in het kader van het CONCUR2 project een survey artikel over procesalgebra t.b.v. het Handbook of Logic in Computer Science van Oxford University Press. Dit leidde tot nieuwe resultaten over formaten van Structured Operational Semantics.

Blanco schreef een eerste artikel met definieerbaarheidsresultaten voor procesalgebra met toestandsoperator. Hij houdt zich nu bezig met dynamische beschrijvingen en implemen­taties van datatypen in procesalgebra.

De Boer, Coenen en Gerth schreven een artikel over exception handling in proces­algebra.
Samenwerkingen.
• De vakgroep Informatica werkt samen met RUG (vakgroep Informatica), Philips Nat.Lab. en Shell Research (KSLA) in het project OIPP (Ontwerp en implemen­tatie van parallelle program­ma's). Ongeveer 6 keer per jaar houdt het OIPP een dag waarop de deelnemers ervaringen uitwisse­len over hun onderzoek op het gebied van parallelle programma's.

• Met betrekking tot het deel Ontwerpmethoden wordt samengewerkt met de vakgroep Produktietechnologie en  automatisering (J.E. Rooda) van de faculteit Werk­tuigbouw­kunde TUE. Het betreft het ontwerpen van parallelle programma's voor het besturen van industriële systemen.

• Met betrekking tot Netwerk implementaties vindt samenwerking plaats met de compu­tergrafiek­ groep (C.W.A.M. van Overveld) in de sectie TT van de vakgroep Informati­ca van de TU Eindhoven. Het betreft hier het ontwerpen en uitvoeren op het transpu­ternetwerk van parallelle programma's voor het genereren van dis­crete krommen en oppervlakken voor rastergrafische toepassingen.

• Met betrekking tot VLSI implementaties wordt samengewerkt met het Institute for Biomedical Computing (C.E. Molnar) van de Washington University te St. Louis, U.S.A., met het Computer Science Department (J.A. Brzozowski) van de Universi­teit van Waterloo, Canada, met het Computer Science Department (A.J. Martin, J.L.A. van de Snepscheut) van het California Institute of Technology te Pasadena, U.S.A., met Philips (PRLE, groep Van Utteren) en met de RU Groningen (J.T. Udding). Verder is er een landelijk samenwerkingsverband PRORISC, waaraan naast onze groep o.a. de drie faculteiten der Elektrotechniek deelnemen.

• In het kader van het ESPRIT OMI project EXACT no. 6143 wordt samen­gewerkt met Nederlandse Philips bedrijven B.V. Eindhoven, IMEC (Belgium), Manchester University (UK), Oxford University (UK), European Development Center (Belgium).

• In het kader van de ESPRIT Basic Research Working Group (ACiD-WG) no. 7225 wordt samengewerkt met University of Oxford (UK), Manchester Uni­versity (UK), University of Nottingham (UK), Philips Research Laboratories Eindhoven, RUL, Polytechnic University of Catalonia, Barcelona (Spain), Basque Country Universi­ty, San Sebastian (Spain), Technical University of Denmark (Denmark), Universid­ade de Aviero (Portugal), Interuniversity Micro-Electronics Centre, Leuven (Belgium).

• In het kader van het ESPRIT BRA project CONCUR 2 no. 7166 wordt samen­gewerkt met University of Aalborg (Denmark), CWI, University of Edinburg (UK), INRIA Sophia Antipolis (France), University of Oxford (UK), University of Sussex (UK), Swedish institute for Computer Science (Sweden), IMAG Grenoble (France), ECRC (Germany), Sharp Laboratory of Europe Ltd (UK), Chalmers Technical University (Sweden).

• In het kader van het ESPRIT research project REACT no. 6021 wordt samen­gewerkt met University of Liège (Belgium), Foundation of Research and Technology-Hellas (Greece), Swedish Institute of Computer Science (Sweden), University of Oxford (UK), University of

Kiel (Germany), Institut National Polytechnique de Grenoble (France).

• De vakgroep Informatica werkt samen met CWI en RUL in het Landelijk Project Concurrency (SION) en in het NFI-project Research and education in concurrent systems (REX).

• De vakgroep Informatica werkt samen met KUN in het SION/STW p­roject Foutbes­tendig­heid: Paradig­ma's, modellen, logica, constructie.

• De vakgroep Informatica werkt samen met University of Manchester (Manches­ter, UK), Institute of Computer Science - FORTH (Heraklion, Kreta, Grieken­land), Imperial College (London, UK), Swedish Institute of Computer Science (Kista, Zweden), Weizmann Institute (Rehovot, Israël), University of Oxford (Oxford, UK), IMAG Grenoble - INPG (Grenoble, Frankrijk), KUN (Nijmegen, Nederland) en Université de Liège (Liège, België) in het kader van ESPRIT aan het Basic Research-project no. 3096, getiteld Formal methods and tools for the development of dis­tributed and real time systems (SPEC).

• Vanwege het REX project, zijn er institutionele contacten met het Franse C³ project en het Engelse ALVEY project.

• Samenwerking vindt plaats met CWI en RUL in het NFI-projekt REX (Research and education in concurrent systems)

• Samenwerking vindt plaats met UvA en RUL in het NFI-projekt TRANS­FER

• Samenwerking vindt plaats met KUN in het SION/STW projekt Foutbe­stendig­heid: Paradigma's, modellen, logica, constructie

• Op het terrein van procesalgebra wordt nauw samengewerkt met UvA, CWI en UU.
1.6 VF-programma: INFORMATIESYSTEMEN 2
VF-code: TUE.INF.303.90.26
Programmaleiding: prof.dr.ir. J.C. Wortmann (Bdk/BISA); prof.dr. K.M. van Hee (WskI/I), prof.dr.ing. D.K. Hammer (WskI/I); prof.dr. J. Wessels (WskI/B&S)
Wetenschapsgebied ISN: 1203, 1207, 3304

Wetenschapsgebied NWO: P170, P160, S190

Toepassingsgebied NABS: N083, N076, N070, N10
Beknopte inhoudelijke beschrijving van het programma
1. Informatiesystemen vanuit bedrijfskundig perspectief

1.1 Ontwerpmethodologie voor informatiesystemen

1.2 Menskundige en organisatie-aspecten van de automatisering

1.3 Informatiesystemen in produktie en logistiek

1.4 Computer Integrated Manufacturing

2. Informatiesystemen vanuit informatica perspectief

2.1 Formele specificaties

2.2 Robuuste Technische Informatiesystemen

2.3 Database systemen

2.4 Computergraphics en user interface management systemen

2.5 Kennissystemen

3. Informatiesystemen vanuit besliskundig perspectief

3.1 Scheduling

3.2 Prestatie-analyse

3.3 Intelligente systemen
Voortgang van het onderzoek
Algemeen
Project 1: Informatiesystemen vanuit bedrijfskundig perspectief

Zie bijdrage van de faculteit Bedrijfskunde.

Project 2: Informatiesystemen vanuit informatica perspectief
Deelproject 2.1: Formele specificaties.

Dit betreft het onderzoek in het kader van het ExSpect project. ExSpect is een specificatie formalisme gebaseerd op gekleurde petri netten met tijd, een functionele taal en een binair datamodel. Er zijn diverse nieuwe analyse technieken ontwikkeld. Allereerst technieken voor het berekenen van doorlooptijden. Verder is een begin gemaakt met automatische verificatie van database constraints. De derde vorm van analyse die onderzocht is betreft protocollen van

subnetwerken. Veel aandacht is besteed aan de vervolmaking van het sofware gereed­schap.

ExSpect is wederom veelvuldig toegepast op praktijk gevallen in het kader van het TASTE project en het PROOFS project (ESPRIT 2). Hieruit zijn weer veel nieuwe ideeen voor zowel onderzoek als gereedschaps ontwikkeling voortgekomen.

Deelproject 2.2: Robuste Technische Informatiesystemen
Project 2.2.1: DEDOS (Dependable Distributed Operating System)

In het afgelopen jaar zijn een aantal onderwerpen voorlopig afgerond:

• De object-georiënteerde implementatie van het Eindhoven Multiprocessor Systeem EMPS dat als kernel van DEDOS dient. Dit werk wordt binnenkort afgesloten met een promotie. Het resterende werk betreft de overname en het onderhoud van het EMPS systeem door de sectie TT.

• Het object-georiënteerde programmeermodel van DEDOS, de bijbehorende DEDOS Application Language DEAL (C++ based) en een eerste prototype van de bij­behorende ontwikkelomgeving. Dit werk resulteerde in een aantal publikaties. De volgende stap is de verdere uitbouw van de DEAL en de uitbreiding van DEAL met real-time, betrouw­baarheids-, en distributie-eisen. Op lange termijn moet DEAL vervangen worden door een high-level taal.

• De hard- en soft real-time protocollen die nodig zijn om de verschillende EMPS systemen tot een geïntegreerd DEDOS executieplatvorm te verbinden. Ook de onderlinge samenhang van deze protocollen, de DEDOS protocolhiërarchie, is duidelijk geworden. Ook dit werk resulteerde in een aantal publikaties. De volgende stap is aan de ene kant de implementatie en het (functionele en performance) testen van deze protocollen op het EMPS systeem en aan de andere kant het formeel specificeren en verificeren.
De volgende onderwerpen zijn verder uitgewerkt:

• De DEDOS on-line scheduler voor hard real-time, hetgeen in een publikatie resulteerde.

• Het hiërarchische clock-synchronisatie algoritme.

• Het hiërarchische lidmaatschap algoritme.

• De gedistribueerde DEDOS concurrency control algoritmen. Ook op dit gebied is gepubli­ceerd.

De samenwerking met N is verder uitgebouwd, met name m.b.t. de besturing van experimenten en de toepassing van de DEDOS concepten. De interfacultaire werkgroep zal binnenkort opgericht worden.

Samen met de faculteit Bdk (Prof. Wortmann) en het Digital Coorperate Engineering Center in Amsterdam is een STW voorstel ingediend dat de toepassing van de DEDOS concepten voor adaptable en recoverable CIM-omgevingen behelst.

In het kader van het EEG BRITE EURAM project IMAGES 2000 zal in samenwerking met de europese vliegtuigindustrie in het algemeen en met Fokker in het bijzonder binnenkort een onderzoek starten naar de betrouwbaarheids- en beschikbaarheidsaspecten van een modulair controle systeem voor de civiele europese vliegtuigindustrie.

Project 2.2.2. Hard real time scheduling

In het afgelopen jaar is de basisversie van het DEDOS hard real-time scheduling model afgesloten

en aan een uitbreiding voor faultmasking door N-Multiple Redundancy (NMR) begonnen. Dit werk zal als CS-Note gepubliceerd worden. De locale scheduling is nu helemaal afgerond. Verder is er gewerkt aan global scheduling (process allocatie) heuristieken en het verder uitbouwen van het window scheduling algoritme. Over het laatste onderwerp zijn een aantal papers gepubliceerd. Er is een samenwerking ontstaan met Prof. A.D. Stoyenko en Prof. L. Welch van het New Yersey Institute of Tech­nology, Newark.
Project 2.2.3 Foutbestendigheid

In het afgelopen jaar is het onderzoek voortgezet naar een op traces gebaseerd forma­lisme, dat het exceptionele gedrag van een component als een transformatie van het foutvrij component­gedrag modelleert. Met name is gewerkt aan een bewijssysteem. Dit gebeurde in nauwe samenwerking met Dr. J. Hooman. Het bijzondere van dit formalisme is dat het fouten op een abstracte manier modelleert door uit te gaan van het observeer­bare communicatie gedrag van componenten: het beschouwt de mogelijke gevolgen van fouten op het observeerbare gedrag, zonder expliciet op die fouten in te gaan. Dit werk resulteerde in een aantal publikaties en zal voortgezet worden met het geschikt maken van de bewijstheorie om ook over de real-time eigenschappen van systemen te redeneren. Hiertoe wordt het untimed traces model vervangen door een model dat timed traces combineert met een notie van readiness.

Verder is een begin gemaakt met het opzetten van een compositionele bewijstheorie die het mogelijk maakt, op het niveau van een abstracte specificatie, te redeneren over de implementeer­baarheid van een programma onder diverse scheduling strategieën. Dit gebeurde in nauwe samenwerking met Prof. M. Joseph van de University of Warwick.

Daarnaast is in het afgelopen jaar een formalisme ontwikkeld voor het specificeren en verifiëren van gedistribueerde real time systemen. In dit formalisme wordt expliciet gebruik gemaakt van de lokale klokken, in plaats van de gebruikelijke notie van globale tijd. Ook dit werk resulteerde in een publikatie. Het project zal binnenkort afgesloten worden met een promotie.

Deelproject 2.3: Databases systemen

Er is verder gewerkt aan het GOOD model en zijn toepassingen op hypermedia systemen.

Er zijn diverse modellen voor hypertext vergeleken en ontwikkeld.

Op het gebied van EDI is een model ontwikkeld voor communicerende data bases. Voor dit model is een prototype in ExSpect gebouwd.

Er is verder gewerkt aan database schema integratie.
Deelproject 2.4: Computergraphics en user interface management systems.
Project 2.4.1 Grafische algoritmen

Toepassingen van chaincodes in het ontwerpen van krommen en oppervlakken zijn binnen dit project onderzocht en tevens geïmplementeerd in de vorm van een editor voor krommen, genaamd ce (curve editor), en het oppervlaktemodelleringssysteem genaamd pret. Het modelleren van oppervlakken en curven m.b.v. relaxatie methoden is ook aan bod gekomen en zal verder uitgewerkt worden. Andere onderwerpen die aan bod gekomen zijn, zijn: equivalentie klassen algoritme: een uitbreiding van het z buffer algoritme en soft shadows voor het z buffer algoritme. In het kader van het werk aan grafische algoritmen is door van Overveld tijdens de eerste helft van zijn verblijf in het buitenland gewerkt aan oppervlakte modellerings algoritmen. Dit werk vond plaats aan de universiteit van Calgary, Canada, in samenwerking met Prof.B. Wyvill en Prof.P. Prusinkiewicz.

De volgende onderwerpen zijn behandeld:

• polygonalisatie algoritmen voor impliciete oppervlakken

• de ontwikkeling van de zgn. "polygon inflation" techniek om op eenvoudige wijze 3 dimensionale gekromde oppervlakken te specificeren

• een techniek voor het beschrijven van branching structuren (verwant aan L systemen) die gebaseerd is op splines en o.a. ook loops toestaat

• algoritmen voor het verwijderen van straight silhouettes in polygon modellen, geschikt voor gebruik in een renderings pipeline

Over al deze onderwerpen zijn publikaties voorbereid of in voorbereiding.

Daarnaast is service verricht op het gebied van de computer simulatie van planten: gebaseerd op beschikbare renderingshardware is een real time systeem gebouwd om de fotosynthese efficiency van planten als functie van de blad geometrie te onderzoeken. Dit laatste werk is gedaan i.s.m. Dr.G. Rimmington (universiteit van Melbourne, Australie); ook hierover is een artikel ter publikatie aangeboden. Tijdens het tweede gedeelte van het buitenlandse verblijf van Van Overveld aan de Universiteit van Pennsylvania in Phyladelphia is ook het samenwerkingsproject met Wyvill over de polygonalisatie algoritmen nog voortgezet.

E.e.a. heeft geresulteerd in een aanmerkelijke uitbreiding van de Eindhovens geometric­modelling omgeving.

Project 2.4.2 Computeranimatie

De aandacht binnen het computeranimatie project richt zich op het systeem GDP dat mede ook binnen het SOBU project "Dialoogvoering en Kennisopbouw" wordt gebouwd. De object-georiënteerde taal Looks die voor het aansturen van de GDP is ontwikkeld, is in 1992 verbeterd en uitgebreid; Tevens is de interpreter voor Looks voltooid. In Looks zijn een groot aantal elementaire klassen geschreven en er wordt gewerkt aan een klasse voor ondersteuning van een windowing omgeving. De documentatie en handleiding van zowel Looks als de GDP zijn voltooid. Er is tevens ook onderzoek gedaan naar kinematica concepten die binnen de GDP toepasbaar zijn om autonoom bewegende objecten te maken.

Buiten het SOBU project is door Van Overveld onderzoek verricht op het gebied van dynami­sche simulatie, de resultaten hiervan hebben geleid tot nieuwe bewegings­algoritmen in het animatiesysteem WALT. Hierover is een artikel ter publikatie aangeboden aan een conferentie.
Een begin van samenwerking is tot stand gekomen met Prof. D. Metaxas van de universiteit van Pennsylvania in Philadelphia.
Project 2.4.3 UIMS (User Interface)

Er is niet meer gewerkt aan de ontwikkeling van een eigen UIMS systeem, omdat DRUID en GENSUI voldoende functionaliteit bieden. Wel zijn en worden andere systemen geanalyseerd en beoordeeld op hun bruikbaarheid. Afstudeerders zijn bezig met het ontwikkelen van een Reference manual voor UI ontwerp (een beknopte verzameling richtlijnen t.b.v. medewerkers en studenten) en het opstellen van dialoogconcepten voor directe manipulatie interfaces. Als testomgeving voor deze concepten wordt onder andere het hier ontwikkelde geometrische modelleringspakket per gebruikt.

Deelproject 2.5: Kennissystemen
Project 2.5.1: Decision Support Systems.

Dit onderzoek richt zich op twee aspecten: efficiente en robuuste algoritmen voor een zeer ruime klasse van scheduling problemen en grafische user interfaces voor zulke problemen.

Aan de algoritmische zijde is vooral gewerkt aan constraint satisfaction technieken waarmee goede numerieke resultaten zijn geboekt. Als toepassing is gewerkt aan het vervaardigen van dienstregelingen voor de Nederlandse Spoorwegen. Aan de interface zijde is gewerkt aan Petri net representaties van scheduling problemen. Deze represen­taties kunnen ook gebruikt worden voor het berekenen van schedules d.m.v. prioriteits regels. Een andere onderzoekslijn is gestart op het gebied van het toepassen van Markov beslissingstheorie op zoek-problemen.
Project 2.5.2 Gedistribueerde real time expert systemen

Gebruik makend van ervaringen met de STRESS ontwikkelomgeving in de voor­gaande jaren is een begin gemaakt met een ontwerp en implementatie van STRESS-II. Naast de principes die reeds in STRESS-I waren gebruikt, zoals modulariteit en gegarandeerde response-tijden, zijn hierbij een aantal nieuwe uitgangspunten gehan­teerd. De belangrij­kste zijn het samenbrengen van regel-gebaseerde en imperatieve formuleringen in de taal en de mogelijkheid real-time problemen op een generieke manier te modelleren en te specificeren. Er is gekozen voor een aanpak die veel lijkt op de exspect specificatie methode. De taalelementen voor regelgeb­aseerd program­meren ondersteunen nu ook variabelen, predikaten en functies. Door middel van een off-line analyse van de regelbank kan worden bepaald of de applicatie aan de tijdseisen voldoet. Een belangrijke verbetering ten

aanzien van STRESS-I is dat geen gebruik meer behoeft te worden gemaakt van progressieve reasoning om tijdgaranties te kunnen geven. Progressieve reasoning is nu een speciale implementatiemetho­de die naar keuze kan worden toegepast. Enige kleine voorbeelden zijn met behulp van de nieuwe omgeving uitgewerkt.
Project 3: Informatiesystemen vanuit besliskundig perspectief
In het onderstaande wordt de voortgang in de drie deelprojecten kort besproken. In verschillende gevallen is sprake van problemen die in samenwerking met bedrijfskunde en informatica-collega's behandeld worden. Het werk kan in zulke gevallen in beide projecten vermeld zijn.
Deelproject 3.1: Scheduling.
Scheduling van berekeningen binnen geïntegreerde circuits.

Het gaat hierbij om het schedulen van periodieke berekeningen benodigd voor de verwerking van videosignalen. In het verslagjaar werden verscheidene artikelen over dit onderwerp afgerond; een medewerker van Philips Research promoveerde op het onderwerp.

Scheduling van bewerkingen in parallelle computers.

Dit onderzoek werd tot 1 december uitgevoerd op het CWI, met financiële steun van SPIN, en daarna op de TUE. Een proefschrift over het onderwerp werd nagenoeg afgerond. Dit onderzoek omvatte het implementeren en experimenteren met TOSCA, een 'Tunable Off-line SCheduling Algoritme', en het behalen van resultaten betreffende de complexiteit en de benaderbaarheid van schedulingproblemen met communicatiever­tragingen tussen de opdrachten.

Deelproject 3.2: Prestatie-analyse
Prestatie-analyse van computernetwerken.

Dit onderzoek heeft in 1991 wat stil gelegen na het vertrek van de SION/NWO medewerker. Het onderzoek samen met de medewerkers van de faculteit Elektrotechniek aan de TUD naar local area networks heeft in 1991 nog geleid tot een tweetal rapporten die waarschijnlijk gepubliceerd zullen worden. Begin 1992 is een nieuw promotieonder­zoek gestart waarin prestatie-analyse en betrouwbaarheid geïntegreerd worden, en waarin nauw samengewerkt zal worden met Informatica. Verder zal samen met de faculteit Elektrotechniek en PTT Research onderzoek gedaan worden naar de prestaties van ATM netwerken.

Deelproject 3.3: Intelligente systemen.

Een model- en algoritmemanagement systeem voor de routering van voertuigen (MAMS).

De activiteiten bleven beperkt tot een herziening van de rapportage over de tot nu toe behaalde resultaten. Ten gevolge van het uitblijven van financiering door de NFI is het project in de ijskast gezet.

Een planbordgenerator.

In het kader van een promotieproject werd in het verslagjaar gewerkt aan een beschrij­ving van planningsproblemen. Een begin is gemaakt met om met behulp van deze beschrijving een planbordgenerator te bouwen. Verder worden de manipulaties die toegepast kunnen worden op representaties van planningsproblemen geclassificeerd.
Modelspecificatie voor logistieke systemen (TASTE).

In dit onderzoek wordt samengewerkt met Informatica en TNO en via TNO met een aantal medefinancierende bedrijven. Het besliskundige deel bestond vooral uit de verdere ontwikkeling van analysemethoden en het logistieke referentiemodel. Het hierop gebaseerde proefschrift werd voltooid.

In samenwerking met IIASA werd begonnen aan de ontwikkeling van ontwerpprocedu­res op basis van simulatie.

AI-technieken in modelgestuurde beslissingsondersteunende systemen.

Een artikel werd voltooid over integratie van regel-gebaseerde en algoritmische methoden bij het ontwerpen van een geschikt personeelsbeleid.
Neurale netwerken en beslissingsondersteuning.

Er werd vooral gewerkt aan het ontwerpen van neurale netwerken voor combinatori­sche optimaliseringsproblemen. Hierover werden enige artikelen geaccepteerd voor publicatie in 1993. Een proefschrift over dit onderwerp is eveneens gepland voor afronding in 1993.

Samenwerkingen
• Een landelijke werkgroep, getiteld Dutch Decision Support Systems Research Group, waarin samenwerken de faculteit der Economische Wetenschappen en de faculteit der Bedrijfskunde van de EUR, de faculteit der Technische Wiskunde en Informatica van de TUD, de faculteit Bedrijfskunde en de faculteit der Wiskunde en Informatica van de TUE, de faculteit der Wiskunde en Informatica van de RUL en de afdeling Beslis­kunde, Statistiek en Systeemtheorie van het CWI. De groep heeft een samen­werkingsverband met de Universiteit van Passau en is uitgebreid met een groot aantal belangstellen­den.

• Op het gebied van decision support systems wordt samengewerkt met IIASA, Laxenburg, Oostenrijk, in het kader van de International Exercise in DSS Develop­ment.

• Op het gebied van specificatie en simulatie wordt samengewerkt met TNO, in het bijzonder met ITP-TNO/TUE in het kader van het TASTE-project, en op het gebied van databases met de groep van prof.dr. R. Meersman (KUB).

• Een werkgroep ex art. 89 WWO met de vakgroep Grondslagen der weten­schappen van de faculteit der Wijsbegeerte van de KUB en de vakgroep Informatica van de faculteit der Wiskunde en Informatica van de TUE: de werkgroep Logica en Informatiesystemen.

• Samenwerking van de secties IS, TI en TT met KUB (Tilburg) en IPO in het kader van het SOBU samenwerkingsproject Dialoog­voering en Kennisopbouw. (DenK); op dit project is Borghuis aangesteld.

• Op het gebied van Robuuste Technische Informatiesystemen:

VUA (prof.dr. J. Treur) in het kader van het gebruik van DESIRE voor het STRESS project; Océ-Nederland b.v. te Venlo; Werkgroep laboratorium Automatisering van de faculteit Natuurkunde aan de TUE m.b.t. de constructie van een DEDOS kernel; KUN (prof.dr.ir. J. Vytopil) m.b.t. het STW-project over fault-tolerance; Philips BCS m.b.t. distributed operating systems; Univ. of Warwick (prof. M. Joseph) en Univ. van Kiel (prof. W.P. de Roever) m.b.t. het specificeren en verifiëren van fouten tolerante systemen in het kader van het STW project over fault tolerance.

• Op het gebied van Computergraphics en User Interface Management Systemen is samengewerkt met:

NOB (Hilversum), VU Academi­sche Ziekenhuis (Amsterdam), Prof. B. Wyvill en Prof. P. Prusinkiewicz van de universiteit van Calgary, Dr. G. Rimmington van de universiteit van Melbourne.

• De vakgroep Informatica werkt samen met PRISMA Informatica (Perugia, Italië), SLIGOS (Paris La Défense, Frankrijk), Telesystèmes (Paris, Frankrijk), ITI-TNO (Delft, Nederland), IPL-TNO (Eindhoven, Nederland) en ENTEL (Madrid, Spanje) in het kader van ESPRIT aan het project 5342, getiteld Promotion of formal methods in European software industry (PROOFS).

• Op het gebied van de scheduling wordt samengewerkt met Philips Research en, in het kader van het SPIN project PARTOOL met EHT CWI.
2 OVERIGE PROGRAMMA'S EN OF THEMA'S (NIET-VF)
2.1 Project: Computers In Mathematical Education.
Reeds vele jaren wordt aan de TUE bij het service onderwijs in de wiskunde onderzoek gedaan hoe op een verantwoorde wijze computers en software in dit onderwijs geintegreerd kunnen

worden. Dit is een terrein waar nog zeer weinig ervaring mee is, in tegenstelling tot de meer traditionele wiskunde cursussen, die een ontstaansgeschiedenis van vele decennia hebben. Om de ervaringen met het gebruik van computers in het onderwijs te kunnen bundelen is in 1991 het project Computers in Mathematical Education opgezet.

In het jaar 1992 is gewerkt op de gebieden analyse, statistiek en computer algebra; een kort overzicht volgt hierna. Bovendien is actief meegewerkt aan aan aantal landelijke activiteiten op het gebied van computers in het wiskunde onderwijs; ook daarvan volgt een kort verslag. Tenslotte volgt een overzicht van de behaalde resultaten.
Analyse.
In 1992 werd in de cursus Calculus voor W met twee instructiegroepen begonnen met het pakket MATHEMATICA in plaats van de BASIC-program­ma's en DERIVE. Dit past in het kader om bij het onderwijs zoveel mogelijk die software te gaan gebruiken die de ingenieurs ook in hun beroepspraktijk kunnen of zullen gebruiken. De ervaringen zijn redelijk positief. Er waren geen grote problemen. Wel vergde de ontwikkeling van een aantal extra opdrachten in MATHEMATICA ten behoeve van dit onderwijs nogal wat tijd en inspanning. Het oefen­materiaal bij dit experiment was gelijk aan dat van de vorige jaren. Het gebruik van MATHE­MATICA geeft aanleiding tot een bezinning over de aard en de inhoud van het oefenmateriaal bij de cursus. Hieraan zal de komende jaren aandacht besteed gaan worden.
Statistiek.
In vervolg op de experimenten en ervaringen uit 1991 rond het geinte­greerd gebruik van statistische software bij Statistiek cursussen zijn in 1992 bij concreet drie cursussen, namelijk Statistiek 2 voor TM (2S2S190), Statistiek voor W (2S040) en Statistiek 2 voor BDK (2S120) practica opgezet, waarbij de hele studentenpopulatie gedurende een aantal oefenmiddagen statistische problemen op leert lossen met gebruik van het softwarepakket Statgraphics. Hiertoe zijn, per studierichting, een aantal specifieke syllabi ontwikkeld, waarin naast een toelichting op de software ook statistische aspecten van het gebruik en speciaal aangepaste opdrachten opgenomen zijn. Meer in het bijzonder zijn dit TUE-Syllabus 2429: 'Syllabus 2^p-proeven bij Statistiek 2 voor Bedrijfskunde', TUE-Syllabus 2482: 'Syllabus Statgraphics bij Statistiek voor Werk­tuig­bouwkunde' en een tweetal voorlopige uitgaven 'Statgraphics bij Statistiek 2 voor TM' en 'Statgraphics bij Statistiek 2 voor TM'. Voor de komende jaren is gepland om deze syllabi om te werken tot definitieve uitgaven en ook voor andere studierich­tingen mogelijkheden voor aanpas­singen binnen het Statistiek-onderwijs in deze zin te onderzoeken en zo mogelijk concreet uit te voeren. Daarnaast zal ook nader bestudeerd worden in hoeverre verdere inhoudelijke wijzigingen binnen het statistiekonderwijs mogelijk of noodzakelijk worden door de beschikbaar­heid van standaard statistische software.
Computer Algebra.
De cursus Algebra 3 rond het pakket MATHEMATICA werd in iets aangepaste vorm opnieuw gegeven. Aan deze cursus namen ook een aantal studenten en stafleden van andere faculteiten deel. Het afrekenen vormt een merkwaardig probleem. De studenten dienen zelf een onderwerp te vinden waarop zij laten zien hoe MATHEMATICA daar gebruikt kan worden. De goede studenten hebben daar geen moeite mee. Van de overigen laat de afrekening op zich wachten omdat zij geen toepassing zien. Er werden wel suggesties gegeven.

Er is deelgenomen aan een seminarium over Groebner bases in Utrecht (zes middagen).

In de tweede helft van 1992 werd gekeken naar de bruikbaarheid van computer­algebra bij Clifford algebra's. Er werd een pakket ontwikkeld voor het rekenen met quaternionn (een bijzonder geval). In het algemeen lijkt voor Clifford algebra's een nadere beschouwing van AXIOM nodig. Zodra dat kan zal er aan dit onderwerp verder gewerkt gaan worden.
2.2 ONDERZOEKSINSTITUTEN

2.2.1 Instituut Wiskundige Dienstverlening
De omvang van de contractresearch was aanzienlijk groter dan in voorafgaande jaren, niet zozeer omdat het aantal projecten, alswel omdat de gemiddelde projectgrootte toenam. Tevens zijn er enkele (betaalde) voorstudies verricht voor het midden- en kleinbedrijf (MKB). Deze leiden mogelijk tot vervolgprojecten in 1993. Als we een grove indeling naar wiskundige vakgebieden maken van de vragen, vinden we de volgende aantallen: mathematische fysica (6x), optimaliser­ing (3x), statistiek en proefopzetten (2x), differentiaalgeometrie (1x), splines (1x), chaostheorie (1x). Vanwege tijdsdruk is er in 1992 minder dan in voorgaande jaren gelegenheid geweest om projecten zodanig uit te werken dat ze geschikt waren voor publicatie in een officieel tijdschrift.
Op verschillende manieren is geprobeerd de contacten met het bedrijfsleven uit te breiden. Daarbij is vooral aandacht geschonken aan het MKB. De TUE heeft de technologietransfer naar het MKB hoog in het vaandel staan getuige het feit dat de rede getiteld "De ivoren toren?", die de rector magnificus uitsprak bij de opening van het academisch jaar 1992-93, bijna geheel aan dit thema was gewijd. Zakelijk gezien is het MKB niet de meest aantrekkelijke partner voor een universiteit. Uit IWDE-ervaring is echter gebleken dat de in het MKB bruikbare wiskunde van een verrassend hoog niveau kan zijn. De daaruit resulterende spin-off in de vorm van publicaties en voorbeelden bij het onderwijs is een belangrijk doel van het IWDE.
Als we inventariseren hoe de contacten in 1992 tot stand kwamen, verkrijgen we het volgende beeld. De grote bedrijven zoals Shell, Philips, NS, KEMA, weten zelf de weg te vinden, bijvoorbeeld doordat men persoonlijke contacten heeft binnen de faculteit Wiskunde en Informatica. Het MKB komt vooral bij het IWDE terecht via de Innovatiecentra. Er wordt naar gestreefd om in 1993 het IWDE grotere bekendheid te geven bij deze centra. De IWDE-stand bij speciale gelegenheden aan de TUE, zoals symposia, opening academisch jaar, KIVI-dag en publieksdag, hebben één contact opgeleverd. Een interview met prof.dr. J.H. van Lint in een bekend dagblad leidde eveneens tot één project.
2.3 Vakgroepenoverzicht
2.3.1. Vakgroep Discrete Wiskunde (DW)
VF-programma:

• TUE.WSK.303.90.25 Discrete Structuren 3

Thema's en voortgang thema's buiten de VF

• Didaktiek. De training en begeleiding van de Nederlandse deelnemers aan de Interna­tionale olympiade werd verzorgd. Een bijdrage werd geleverd aan de ontwikkeling door het CITO van zogenaamde toetsmatrijzen t.b.v. het centraal schriftelijk eindexamen V.W.O. Wiskunde B.

• O.P.Lossers. In 1992 zijn zeven oplossingen van onze problem solving group met publicatie gehonoreerd. De groep kwam regelmatig bij elkaar met gemiddeld acht deelnemers uit alle vakgroepen en een student uit Nijmegen. Er werden ruim 70 oplossingen verzorgd.
Wetenschapsgebied ISN: 1299 discrete wiskunde, 1204, 3325, 5801

Wetenschapsgebied NWO: P110, T180, S270

Wetenschapsgebied NABS: N025, N10, N081
2.3.2 Vakgroep ANALYSE (A)
VF-Programma's:

• TUE.WSK.301.90.25 Toepassingsgerichte Analyse 3

Thema's buiten de VF

• Veldentheorie en Clifford analyse. Beschrijving van deeltjesvelden, elektromag­ne­ti­sche en andere Yang-Mills velden met behulp van Clifford bundels.

• Mathematische (niet-equidistante) sampling theorie.

• Asymptotisch probleem. Toepassing van de `buizenmethode' op een klasse van integro-differentiaal-vergelijkingen.

• Differentiaalvergelijkingen in de materiaalkunde en de continuumsmechanica.

• Chaostheorie en tijdreeksanalyse

• Aero-akoestiek

• Modellering van polymeerstroming

• SOBU-project Golden Ten: deterministische en stochastische analyse van het Golden Ten spel en soortgelijke kansspelen.
Service

Kortlopend onderzoek naar aanleiding van vragen op het gebied van in de vakgroep vertegen­woordigde disciplines; met name op het gebied van de mechanica, de toegepaste analyse, de numerieke wiskunde en de numerieke programmatuur.

Expliciet kunnen genoemd worden: het werken aan problemen samenhangend met numerieke freeskopbesturing (Philips CFT) en kort onderzoek aan niet-lineaire periodieke differentiaal­vergelijkingen ten behoeve van de faculteit T.

Verder wordt er substantiële steun verleend aan het IWDE, zowel in de vorm van serviceon­derzoek als ook ondersteuning bij implementeren en programmeren.

Samenwerkingen

• Op het gebied van mathematische (niet-equidistante) sampling theorie met Hollandse Signaalapparaten B.V.

• Met de vakgroep Theoretische Natuurkunde TUE, op het gebied van de grondsla­gen voor de quantummechanica i.h.b. de operatoren­theorie. Samenwer­king bestaat o.m. uit medebegeleiding van een promovendus op genoemd gebied.

• Op het gebied van de Wigner-distributie en de Heisenberg-groep wordt samenge­werkt met het Philips Natuurkundig Laboratorium.

• Met DSM-Research, Geleen, in een onderzoek naar het gedrag van stromingen van niet-lineaire (visco-elastische) vloeistoffen (polymeren).

• Met het Nat.Lab. Philips, wisselende projecten in verband met afstudeerders.

• Met de vakgroep Fundamentele Werktuigkunde TUE een promotieprojekt (stroming door aderen).

• Met Fysische Technologie TUE (promotieonderzoek ten aanzien van kleivorm­lin­gen).

• Met de Dienst grondwatervoorziening TNO-Delft.

• Met Philips CFT op het gebied van halfgeleiders en numerieke freeskopbe­sturing.

• Met de vakgroep Econometrie van de KUB (in SOBU-project) i.v.m. promotie­onderzoek Golden Ten.

• Met de vakgroep Wiskunde en Informatica van de RUG, kriteria voor contact tussen een springplank en zijn ondersteuning.

Wetenschapsgebied ISN: 1202, 1206, 2202, 2205, 2212

Wetenschapsgebied NWO: P130 , P140, P170, P190, P200

Toepassingsgebied NABS: N070, N077, N025, N10
2.3.3 Vakgroep BESLISKUNDE EN STOCHASTIEK (B&S)
VF-Programma's:

• TUE.WSK.301.90.25 Toepassingsgerichte Analyse 3

• TUE.WSK.302.90.25 Besliskunde en Stochastiek 3

• TUE.INF.303.90.26 Informatiesystemen 2

Thema's en voortgang thema's buiten de VF

• Probleem-oplossen. Er werden (deels in het kader van `O.P. Lossers') enkele problemen uit wiskundetijdschriften opgelost en ingestuurd; een deel werd gepubli­ceerd.

• Kroonwielvertanding. Ir. M. Peerdeman verricht onder leiding van prof.dr.ir. M.J.W. Schouten promotieonderzoek. Dr. D.A. Overdijk is als copromotor betrokken bij dit onderzoek. De resultaten moeten inzicht verschaffen in de levensduur en de geluids­productie van de kroonwieloverbrenging.

• Er werd een bijdrage geleverd aan het thema "Computergebruik in het wiskunde­onderwijs".

In het kader van het Samenwerkingsorgaan Brabantse Universiteiten liepen er in 1991 2 projekten:

• Aanpassingsprocessen in rantsoeneringseconomieën. Uitvoerder drs. P.J.J. Herings. projectleiders dr. J. van Geldrop en dr. A. Talman.

• Strategisch gedrag en economische theorie. Uitvoerder drs. A.Groot, projektlei­ders, dr. C. Withagen en prof.dr.A. de Zeeuw. Het komend jaar is een promotie in het kader van dit samenwer­kingsprojekt te verwachten.

• Milieu en economische groei. Uitvoerder drs. ing. N.Vellinga. Projektleiders dr.C. Withagen en prof.dr.A. de Zeeuw. Projekt is per 1-1-1992 toegewezen.

Consultatie en service.

Kortlopend onderzoek naar aanleiding van vragen op het gebied van in de vakgroep vertegen­woordigde disciplines.

Statistische consultatie in het kader van het Instituut Wiskundige Dienstverlening Eindhoven.
Samenwerkingen

• Een werkgroep ex art. 89 WWO met de vakgroep Bestuurlijke Informatiesys­te­men en automatisering van de Faculteit der Bedrijfskunde van de TUE (werk­groep System development environments).

• Instituut Wiskundige Dienstverlening Eindhoven.
Wetenschapsgebied ISN: 1207, 1208, 1209

Wetenschapsgebied NWO: P140, P160, P170, P110

Toepassingsgebied NABS: N083, N070, N043, N10
2.3.4 Vakgroep INFORMATICA (I)
VF-programma's:

• TUE.INF.301.90.26 Programmeren

• TUE.INF.302.90.26 Parallellisme

• TUE.INF.303.90.26 Informatiesystemen 2

Overige programma's en/of thema's (niet-VF)

Voor zover onderzoek buiten de VF-programma's wordt gedaan, is dit niet in program­ma's en/of thema's gebundeld en beschreven.

3.3 Kwantitatieve overzichten op faculteitsniveau