Faculteit




НазваниеFaculteit
страница5/30
Дата25.09.2012
Размер2.14 Mb.
ТипДокументы
1   2   3   4   5   6   7   8   9   ...   30

1.2 VF-programma: BESLISKUNDE EN STOCHASTIEK 3


VF-code: TUE.WSK.302.90.25

Programmaleiding: prof.dr. J. Wessels

Wetenschapsgebied ISN: 1207, 1208, 1209, 1203, 1206

Wetenschapsgebied NWO: P160

Toepassingsgebied NABS: N083

Beknopte inhoudelijke beschrijving van het programma


Het programma omvat een viertal thema's:

1. Combinatorische optimalisering

2. Stochastische dynamische modellen voor beslissingsondersteuning

3. Structuuranalyse van stochastische processen

4. Statistiek.


Voortgang van het onderzoek

Project 1: Combinatorische optimalisering.

a. Polyhedrale methoden voor combinatorische problemen.

De ontwikkeling van het MINTO-systeem werd voortgezet in samenwerking met het Georgia Institute of Technology; over de algoritmiek van MINTO verschenen enkele rapporten. In het kader van een promotieproject betreffende polyhedrale methoden voor één-machine-volgorde­problemen werd een volledige karakterisering van een bepaalde klasse facetten afgeleid. Een promotieproject betreffende polyhedrale methoden voor routeringsproblemen richtte zich op de bestudering van het handelsreizigersprobleem met tijdvensters.

Een artikel over de polyhedrale beschrijving van het seriegrootteprobleem met opstart­kosten is geaccepteerd voor publicatie in SIAM Journal on Discrete Mathematics.


b. Lokale-zoekmethoden voor combinatorische problemen.

Het werk aan een boek over dit onderwerp werd voortgezet. In het kader van een promotie­project

werd een taxonomie voor lokale-zoekmethoden voltooid; de aandacht werd daarna gericht op de ontwikkeling van 'multi level'-zoekmethoden voor een algemene klasse van machine­volgordeproblemen.


c. Modellen en methoden voor de routering van voertuigen.

In het kader van het door de STW gefinancierde promotieproject op dit gebied werd aandacht besteed aan de verdere ontwikkeling en implementatie van kolomgeneratie­technieken en aan het in kaart brengen van de praktijksituatie waarin deze zullen worden toegepast.


d. Modellen en methoden voor produktieplanning.

In samenwerking met onderzoekers van MIT, Cornell University and Princeton University werden resultaten behaald betreffende de complexiteit van de benaderbaarheid van optimale schedules voor open shops, flow shops en job shops. In samenwer­king met onderzoekers van Carnegie-Mellon University werd gewerkt aan een verscherping van de één-machinegrens voor job shop scheduling. Er werd een artikel geschreven over een nieuwe aanpak van het bin packing probleem van Graham. Het werk aan een boek over machinevolgordeproblemen werd voortgezet.

Een onderzoek is gestart naar de mogelijkheden om (meerdimensionale) bin-packing problemen aan te pakken met combinaties van kolomgeneratie en branch & bound.

Een verbeterd algoritme van het economisch seriegrootteprobleem is gepubliceerd in Operations Research. Toepassingen hiervan en rekenresultaten zijn geaccepteerd door European Journal of Operational Research. Het gecapaciteerd economisch seriegrootte­probleem is nu in onderzoek.

Project 2: Stochastische dynamische modellen voor beslissingsondersteuning.


a. Wachtrijen met meer rijen en onderling afhankelijke instroomprocessen.

In 1992 is het onderzoek naar de gebruiksmogelijkheden van de compensatiemethode voortgezet. Dit heeft onder andere geleid tot een inmiddels geaccepteerd artikel over het gebruik van de compensatiemethode voor de analyse van een 2 x 2-switch. In dit artikel worden de resultaten vergeleken met die van andere methoden, hetgeen de effectiviteit van de compensatiemethode duidelijk maakt. Tevens zijn voorwaarden ontwikkeld voor het gebruik van de compen­satiemethode voor processen met meer dan 2 dimensies. De 2 x n-switch wordt gemodelleerd als een n-dimensionaal Markov proces dat aan de voorwaarden voldoet. Verder zijn er interessante uitbreidingen van de compensatie­methode ontwikkeld voor situaties met Erlang-verdelingen in plaats van negatief-exponentiële verdelingen. Tenslotte is een artikel geschreven over het ontwikkelen van onder- en bovengrenzen voor kortste rij problemen met behulp van de matrix-geome­trische methoden. In 1992 is een groot aantal artikelen geaccepteerd voor publicatie.


b. Seriegroottebepaling.

Het onderzoek naar de praktische toepasbaarheid van neurale netwerken voor produktie­planning (NWO-plaats) is in 1992 nog niet van start gegaan wegens het nog niet beschikbaar zijn van de kandidaat. Wel is voortgebouwd op het eerdere onderzoek naar seriegroottebepaling. Een artikel hierover zal in 1993 gepubliceerd worden.


c. Analyse en ontwerp van logistieke systemen.

In dit project wordt onderzoek verricht naar optimale voorraadstrategieën voor multi-echelon voorraadketens in produktie- en distributiesystemen. Wegens het ontbreken van een geschikte kandidaat is het opstarten van een promotieproject uitgesteld tot 1993.


Project 3: Structuuranalyse van stochastische processen.


Het boek over oneindige deelbaarheid, met Van Harn (VUA), vordert gestaag maar langzaam.

Het onderzoek m.b.t. breukdelen van maxima verloopt bevredigend; behalve Wilms en Brands zijn Steutel en Thiemann hierbij betrokken. Twee artikelen zijn geaccepteerd, waarvan één over het aantal maxima in diskrete steekproeven.

Het werk met Van Harn op het gebied van vernieuwingstheorie en vertakkingsproces­sen is afgerond.

Enigszins verwant hiermee is het werk in de wachttijdtheorie van Resing, waar ondermeer theorie van de multi-type vertakkingsprocessen wordt toegepast. Twee artikelen zijn ge­accepteerd, waarvan één met Boxma (CWI).


Project 4: Statistiek


Binnen dit thema zijn twee projecten gedefinieerd, namelijk `Schatten en selecteren bij stochastische modellen' en `Robuuste technieken'.

Het eerste project bestond in 1992 uit drie deelprojecten:

a. Analyse van stochastische beslissingsproblemen.

Er werd gewerkt aan een algemeen concept voor het verwerken van subjectieve gegevens ten behoeve van praktische beslissingsproblemen. Zeven memoranda zijn geschreven en er is aan een aantal artikelen gewerkt.


b. Selecteren van populaties.

Eigenschappen van selectie werden onderzocht voor een aantal specifieke verdelingen. Selectie van een ε-beste populatie werd nader bestudeerd. Het gebruik van verliesfunk­ties werd opgenomen bij het selecteren van de beste of ε-beste populatie. Een drietal artikelen en vijf memoranda werden gepubliceerd. Er werden vier voordrachten over selectie gehouden.


c. Het Behrens-Fisher probleem.

Bij dit probleem en zijn generalisaties is fundamenteel onderzoek verricht. Een lijvig artikel over waarnemingsreductie en -classificatie is geaccepteerd en er zijn een drietal voordrachten gehouden. Er is grote vooruitgang geboekt wat betreft het onderzoek naar de verificatie van statistische methoden.


Bij het tweede project is onderzoek verricht op het gebied van de niet-parametrische en semi-parametrische statistiek, met name extreme-waarden theorie, robuust schaalschatten onder censurering en niet-parametrische regressie. Bij een groot deel van dit onderzoek spelen empirische en verwante processen een belangrijke rol. Een aantal memoranda zijn geschreven of in voorbereiding en er werden zes artikelen gepubliceerd; ook werden een aantal voordrachten gehouden. Het artikel over gegeneraliseerde quantielen ontsluit een nieuwe lijn van onderzoek; hiervoor is een AIO-project ingediend. Tevens werd onderzoek gedaan naar een uitschieter-resistente regressiemethode. Er werd een voordracht gehouden en een rapport en een publikatie geschreven. Verder is onderzoek gedaan aan stapsgewijze regressie en ook aan logistische regressie en loglineaire modellen. Over deze onderwerpen is een rapport geschreven en een artikel gepubliceerd. Tevens zijn een aantal voordrachten gehouden. Tenslotte werden resultaten bereikt op het gebied van D-optimale proefopzet­ten; een artikel hierover is gepubli­ceerd.

Samenwerkingen.


Naast vele incidentele vormen van samenwerking was in het verslag­jaar sprake van meer geïnstitutionaliseerde samenwerking in de volgende vormen:

• Interuniversitaire Werkgroep Beslissingsondersteunende Syste­men en Modellen

• Onderzoeksamenwerking Discrete Optimalisering EUR-CWI-TUE

• Onderzoeksamenwerking TUE - Philips Research

• Onderzoeksamenwerking TUE - Philips CQM

• Onderzoeksamenwerking TUE - DSM Research

• Onderzoeksamenwerking TUE - IPL.

Met groepen van Bedrijfskunde en Informatica wordt gewerkt aan een Onderzoekschool Produktie en Logistiek, waaraan vermoedelijk ook andere instellingen zullen deelnemen.

De groep Combinatorische Optimalisering is betrokken bij de oprichting van een Onderzoek­school Diskrete Wiskunde. Voorts wordt door verschillende groepen deelname aan het Stieltjes Instituut overwogen.

Er wordt deelgenomen aan het initiatief om tot een IOP voor Distributie, Opslag en Transport te komen.

In het verslagjaar werd voorts intensief samengewerkt met het International Institute for Applied Systems Analysis (Laxenburg, Oostenrijk) op het gebied van de beslissingsana­lyse.


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 Co2. Tevens werd een karakterisatie gegeven van een lijnensysteem in R 23 gerelateerd aan de groep Co23.

  De groep SL2 K, met K een Cayley delingsalgebra, werd bestudeerd.

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

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 Z4/2D4 en Z8/E8. 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   2   3   4   5   6   7   8   9   ...   30

Похожие:

Faculteit iconFaculteit

Faculteit iconFaculteit

Faculteit iconFaculteit

Faculteit iconUniversiteit Gent Faculteit Landbouwkundige en Toegepaste Biologische Wetenschappen Vakgroep plantaardige productie

Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница