Puzzels oplossen voor een betere dienstregeling

Prof.dr. Mark de Berg - Algoritmiek

Onderzoek doen met slechts pen en papier – waar zie je dat nog? De core business van informaticus Mark de Berg gebeurt in zijn hoofd, op papier of op een whiteboard. Simpel gezegd lost hij zeer ingewikkelde puzzels op. Abstracte, wiskundige problemen, die voor menigeen als abracadabra zullen klinken, maar die ten grondslag liggen aan maatschappelijke uitdagingen als een betere dienstregeling voor treinen of voldoende opslagcapaciteit voor energienetwerken.

Bij binnenkomst op de kamer van Mark de Berg valt direct het overvolle whiteboard op: een kluwen van letters, pijltjes, symbolen en krabbels. Dit is het ‘kladpapier’ waarmee de hoogleraar Algoritmiek zijn onderzoek doet aan de faculteit Wiskunde & Informatica. Zijn hoofddoel is in één zin uit te drukken: het bedenken van algoritmes. Een algoritme is een set instructies voor een computer om tot een beoogd resultaat te komen, zoals een recept dat is voor een kok.

Het ‘resultaat’ waar De Berg naar zoekt is in zijn algemeenheid bewijzen dat iets ‘klopt’. De Berg: “Je definieert eerst een probleem op een wiskundige manier en zorgt dat de vraagstelling nauwkeurig genoeg is. Vervolgens gebruik je een algoritme om tot het juiste antwoord te komen.” De Berg richt zich op algoritmes met ruimtelijke data, dus data met meerdere dimensies. Denk aan geografische gegevens (2D) of de ruimtelijke modellering van gebouwen (3D).

De problemen waar De Berg aan werkt komen voort uit bijvoorbeeld een nieuwe technologie of toepasgebied waar fundamentele, interessante vragen achter zitten, maar kunnen ook puur uit nieuwsgierigheid ontstaan. Bijvoorbeeld: hoe beweegt een robot van punt A naar punt B? Ook al is er vaak een link met de praktische toepassingen, de problemen waar De Berg zich op richt zijn een abstractieniveau hoger. Zo los je het niet voor één specifiek geval op, maar voor alle vergelijkbare situaties.

Rondjes en kruisjes

Gevraagd om een voorbeeld te geven van het soort problemen waar hij aan werkt, veegt hij een stukje van het whiteboard schoon. Hij begint te tekenen. “Stel, je hebt een aantal meetpunten met twee types: rondjes en kruisjes. De vraag is bijvoorbeeld: bestaat er een lijn zodanig dat alle kruisjes aan één kant liggen en rondjes aan de andere kant, en hoe snel kun je die vinden?”

Nog voordat de vraag goed en wel doorgedrongen is, gaat De Berg verder. “Als je hier even over nadenkt zie je dat je alleen maar naar lijnen hoeft te kijken waar twee punten op liggen. Stel dat je n punten hebt, dan moet je dus n-kwadraat verschillende lijnen bekijken.” De Berg doet een paar denkstappen die voor de luisteraar te snel gaan en beredeneert dat het algoritme uit n tot de derde macht stappen bestaat. “Maar kan dat niet veel sneller, moet ik echt elke lijn bekijken?”, vervolgt De Berg. Zonder de volledige uitleg verklapt hij dat dit niet nodig is: er is een slim algoritme dat het antwoord in een lineair aantal stappen vindt.

In feite is De Berg dus bezig met het oplossen van complexe, wiskundige puzzels, grote danwel kleine. Geen hypermodern lab voor hem, of mensgrote microscopen; meer dan pen en papier heeft hij in principe niet nodig. “Ik heb regelmatig promovendi die de computer alleen gebruikt hebben om hun proefschrift vorm te geven”, lacht De Berg.

Logisch nadenken is in zijn discipline van het grootste belang, om een vraag te kunnen vertalen naar de essentie van het probleem. De Berg: “Het leuke aan dit vak is dat je aan de ene kant creatief moet zijn en logisch moet nadenken, en dat je aan de andere kant uitzoeken welke beschikbare trucs en technieken je kunt toepassen.” 

Puzzels oplossen

Het oplossen van een puzzel komt vaak neer op het vinden van dat ene inzicht, dat ‘eureka-moment’ waarmee alles op zijn plaats valt. Dat maakt zijn werk – en dat van zijn vakgroep – vrij onvoorspelbaar. “Het verschilt heel erg hoe lang je over een probleem doet”, zegt De Berg. “Dat ene idee dat je nodig hebt kan in een dag komen, na een paar maanden of soms helemaal niet. Op de fiets of onder de douche wil wel eens een ingeving komen, maar vaak blijkt dan toch dat het niet klopt”, lacht hij.

Druk om continu met resultaten op de proppen te komen ervaart hij niet. “Alleen voor afstudeerders of promovendi is dat lastiger, want die hebben een beperkte tijd om een opdracht af te ronden. Het is natuurlijk jammer, als iets na afloop nog steeds niet is opgelost, maar dat hoort erbij. Een probleem dat je in 30 minuten oplost vindt niemand interessant.”

Al geeft De Berg toe dat je als hoogleraar tegenwoordig minder rust hebt om zelf lange tijd aan dingen te werken. “De cultuur aan de universiteit is in de afgelopen twintig jaar veranderd. Het binnenhalen van geld is belangrijker geworden. Je bent daarom vaak met meerdere dingen tegelijk bezig en legt soms iets ‘op de plank’  om het na lange tijd met een nieuw inzicht weer eens op te pakken. Het werk van andere mensen kan soms ook aanleiding te geven met iets anders verder te gaan.” 

Netwerken

Tot welke concrete toepassingen de ‘puzzels’ van De Berg kunnen leiden werd duidelijk met de toekenning van een Zwaartekrachtsubsidie van NWO eind vorig jaar aan een groot samenwerkingsproject, genaamd Networks, van TU/e, UvA, CWI en Universiteit Leiden. De TU/e is hierin de grootste partner, met zeven van de elf hoofdaanvragers waarvan De Berg er een is.

Het project draait om complexe netwerken, voor bijvoorbeeld infrastructuur, energie en communicatie. Het gaat hier om netwerken die van grote invloed zijn in ons dagelijks leven: dienstregeling van treinen, opslagcapaciteit voor energienetwerken of sociale netwerken als Facebook. De wiskundigen en informatici bundelen binnen Networks hun krachten om zulke netwerken bestand te maken tegen verstoringen of onvoorspelbare fluctuaties.

“In principe werkt bijvoorbeeld de dienstregeling van treinen goed, maar bij een verstoring verspreiden de problemen zich als een olievlek over het land”, zegt De Berg.  “Net zo is het met energie. De opbrengst kun je van tevoren niet voorspellen, dus bij een zonnige dag kan het energieaanbod groter zijn dan de vraag. Maar hoeveel en hoe vaak dit gebeurt is niet van tevoren te zeggen”, legt De Berg uit. De vraag is hoe je de netwerken zo kan inrichten dat het op een goede manier met dit soort willekeurige fluctuaties om kan gaan,

Ook al zijn het in de praktijk zeer verschillende netwerken, de wiskundige modellen erachter zijn vergelijkbaar. Het project is dan ook vooral op fundamentele aspecten van zulke complexe netwerken gericht. De Berg: “Het leuke aan deze subsidie is dat het echt bedoeld is voor nieuwsgierigheidsgedreven zaken waarvan we hopen dat het echt dingen gaat verbeteren.” 

Terug naar het overzicht