Kaartschudprofessor ontvangt wiskundeprijs

6 februari 2006

De Amerikaanse onderzoekers prof.dr. Nancy A. Lynch en prof.dr. Persi Diaconis ontvangen de Van Wijngaarden Award 2006. Deze prijs wordt voor de eerste keer uitgereikt ter markering van het 60-jarig bestaan van het Centrum voor Wiskunde en Informatica (CWI) te Amsterdam en is bestemd voor wetenschappers die een bijzondere betekenis hebben voor de wiskunde en informatica. De laureaten ontvangen de prijs op donderdagavond 9 februari 2006 uit handen van prof.dr. P. Adriaans, voorzitter van het bestuur van de Stichting Centrum voor Wiskunde en Informatica.

De wiskundige Persi Diaconis (Stanford University) heeft vooral naam gemaakt doordat zijn fundamentele onderzoek toepasbaar is voor praktische problemen. Zo kwam zijn onderzoek op het gebied van Markov-ketens van pas voor een probleem dat in casino’s speelt: hoe vaak moet je een spel kaarten schudden, willen de spelers werkelijk willekeurige kaarten krijgen. Ook de manier waarop hij – ex-beroepsgoochelaar – zijn onderzoek over het voetlicht brengt, maakte hem immens populair. Persi Diaconis (New York, 1945) is als Mary V. Sunseri Professor of Statistics and Mathematics aan Stanford University verbonden.

Binnen de informatica heeft Nancy A. Lynch (MIT) zich gespecialiseerd in zogeheten gespreide systemen (distributed systems); zij is een van de pioniers en een van de toonaangevende onderzoekers op dit gebied. Voorbeelden van gespreide systemen zijn telefooncentrales, met knooppunten op straat-, lokaal, regionaal en landelijk niveau. Binnen dergelijke systemen moeten de verschillende onderdelen met elkaar communiceren om te controleren of er niets fout is gegaan en om alles precies op elkaar af te stemmen. Zij heeft onder andere aangetoond dat, als sommige onderdelen falen, de overige onderdelen niet altijd tot een uniforme beslissing kunnen komen. Nancy Lynch is NEC professor of Software Science and Engineering en Professor of Electrical Engineering and Computer Science aan het Massachusetts Institute of Technology (MIT), waar zij ook de Theory of Distributed Systems onderzoeksgroep leidt in het Computer Science and Artificial Intelligence Laboratory.

De prijs is vernoemd naar Adriaan van Wijngaarden (1916 - 1987), een van de grondleggers van de informatica in Nederland. Ongeveer een jaar na de oprichting van het Mathematisch Centrum (op 11 februari 1946) kwam Van Wijngaarden er in dienst als hoofd van de vermaarde rekenafdeling. Later was hij van 1961 tot 1980 directeur van het Mathematisch Centrum, dat sinds 1983 Centrum voor Wiskunde en Informatica heet.

Tijdens de feestelijke uitreiking van de prijzen speelt het Mondriaan Kwartet het in 1968 door een computer gecomponeerde strijkkwartet no 1 in C groot.

Plaats: Oude Lutherse kerk, Singel 411, Amsterdam
Tijd: donderdag 9 februari 2006, 19.30 – 21.30 uur
Zaal open: vanaf 18.45 uur; muzikaal intro door het Mondriaan Kwartet vanaf 19.00 uur

Programma:
19.30 Opening - prof.dr. J.K. Lenstra, algemeen directeur Centrum voor Wiskunde en Informatica.
Laudatio - prof.dr. F. W. Vaandrager
19.45 Impossibility of consensus in distributed systems … and other tales - prof.dr. N.A. Lynch
20.25 Computerstrijkkwartet no 1 in C Groot van Lambert Meertens - Mondriaan Kwartet
Laudatio - prof.dr.R.W. van der Hofstad
20.45 The search for randomness - prof.dr. P. Diaconis
21.25 Uitreiking Van Wijngaarden Award - prof.dr.P.W. Adriaans
Receptie

Toeval bestaat. Of niet?
Persi Diaconis zal in zijn voordracht ingaan op enkele zeer simpele toevalligheden, zoals kruis of munt gooien, het schudden van speelkaarten en het patroon van regendruppels. Bij nader inzien – en met behulp van wis- en natuurkunde – blijken veel dingen helemaal niet zo toevallig te zijn. Voor wiskundigen is het schudden van kaarten – door ze, met in elke hand een stapel, ongeveer om en om in elkaar te schuiven – een ‘snel mengende Markov-keten’. De kansverdeling na elke keer schudden hangt alleen af van de volgorde in de stapel direct daarvoor. Persi Diaconis toonde in 2002 samen met David Bayer en met zijn vrouw, de statisticus Susan Holmes, aan, dat na zeven keer op deze manier schudden niemand de volgorde van de kaarten kan voorspellen. Bij minder vaak schudden is de volgorde nog wel voorspelbaar, waar ervaren spelers van kunnen profiteren, maar vaker schudden is zinloos, omdat er toch nauwelijks nog verbetering optreedt. Het bewijs van deze stelling is fundamenteel en abstract en maakt gebruik van representatietheorie van groepen en niet-commutatieve Fourieranalyse. Diaconis deed dit onderzoek in opdracht van een Amerikaanse casinoketen. Hij leverde ook belangrijke bijdragen op het gebied van zogeheten contingency-tabellen, random matrices en permutaties.

Nieuwe uitdagingen
In de voordracht van Nancy Lynch klinkt haar fascinatie door voor gespreide systemen en voor het onderzoek, zoals dit zich in de afgelopen 25 jaar heeft ontwikkeld. Zij heeft veel bijgedragen aan de ontwikkeling van de theoretische basis, mathematische modellen, algoritmen en bewijstechnieken. Haar grote verdienste is, dat zij heeft aangetoond, dat het in sommige gespreide systemen niet mogelijk is om consensus te bereiken, zeker niet in die systemen, die gevoelig zijn voor fouten en afwijkingen. Dat heeft serieuze consequenties voor de verwachtingen en garanties die je voor dergelijke systemen kunt geven. Een voorbeeld is een metrosysteem, waarbij zowel de treinstellen met automatisch open- en dicht gaande deuren een gespreid systeem is, als wat er langs de lijn gebeurt en ook delen van de centrale. Hoe fout het kan gaan bleek onlangs bij een proef met chauffeurloze bussen, die op elkaar botsten. Wat dat betreft ziet Nancy Lynch veel nieuwe uitdagingen om zich heen. Ook bijvoorbeeld op het gebied van mobiele telefoonnetwerken. In haar onderzoek maakt zij daarbij gebruik van de computertaal Python, die in 1989/90 door CWI-medewerkers werd ontwikkeld.

..........................

Voor de redactie:

• Behandeld door Godelief Nieuwendijk
• tel. 020 – 592 4181
• g.m.t.nieuwendijk@cwi.nl
• Centrum voor Wiskunde en Informatica (CWI)
• Kruislaan 413
• 1098 SJ Amsterdam
• www.cwi.nl

Het Centrum voor Wiskunde en Informatica (CWI) is het nationale onderzoeksinstituut voor wiskunde en informatica. Het is gelieerd aan de Nationale Organisatie voor Wetenschappelijk Onderzoek (NWO).

bron: Centrum voor Wiskunde en Informatica (CWI)