Terug naar de site van Algoritmen Alom.

Kortste pad
In 1959 publiceerde Edsger W. Dijkstra zijn kortste-padalgoritme, een efficiënt rekenrecept waarmee de kortste route van A naar B op een kaart kan worden berekend. Nu, vijftig jaar later, zijn algoritmen niet meer weg te denken uit ons leven. We hebben ze nodig om veilig te pinnen, om de trein op tijd te laten rijden en om DNA van muis en mens met elkaar te vergelijken. Het Nederlandse wiskundecluster DIAMANT organiseert een publieksmiddag over zulke algoritmen, op 18 april in het Spoorwegmuseum te Utrecht. Iedereen is welkom!

Evolutie reconstrueren
Op Algoritmen Alom wordt aandacht besteed aan algoritmen uit drie verschillende toepassingsgebieden. In de eerste plaats algoritmen in de biologie. In zijn 150 jaar geleden gepubliceerde Origin of species betoogt Darwin dat verschillende soorten organismen zijn ontstaan uit verre gemeenschappelijke voorouders in een evolutionair proces dat met een boom kan worden weergegeven. Tegenwoordig kan men zo'n boom reconstrueren aan de hand van het DNA van die verschillende soorten. De Duitse wiskundige Niko Beerenwinkel spreekt over de algoritmen die hierbij een rol spelen.

Cryptologie

De tweede voordracht, van de Amerikaanse wiskundige Edward Schaefer, gaat over een algoritme uit de cryptologie. Met cryptologie hebben we dagelijks te maken: bij elke betaling met een pinpas worden je bankgegevens, om fraude te voorkomen, versleuteld verzonden en geverifieerd. De laatste tijd is de OV-chipkaart vaak in het nieuws geweest omdat de cryptologie die daarin gebruikt wordt nog niet veilig genoeg was.

Spoorboekje
In de derde en laatste voordracht spreekt de Nederlandse wiskundige Alexander Schrijver over de wiskunde achter het huidige Spoorboekje van de Nederlandse Spoorwegen. Schrijver et al. wonnen daarvoor in 2008 de prestigieuze Edelman Award.

Grootste gemene deler

Een algoritme is een rekenrecept waarmee ingevoerde gegevens tot een gewenste uitvoer leiden. Een van de oudste algoritmen is van Euclides. De invoer daarvan bestaat uit twee positieve gehele getallen, en de uitvoer is hun grootste gemeenschappelijke deler (ggd). Het algoritme werkt als volgt. Als het tweede getal niet nul is, maak dan twee nieuwe getallen; het eerste is gelijk aan het tweede oude getal en het tweede gelijk aan de rest bij (staart)deling van het eerste oude getal door het tweede oude getal. Ga hiermee door tot het tweede getal nul is. Het eerste getal is dan de ggd. Zo wordt de invoer (26,18) volgens (26,18)->(18,8)->(8,2)->(2,0) gereduceerd tot (2,0) en de ggd is dus 2. Dijkstra's algoritme om de kortste route van A naar B te bepalen is van vergelijkbare elegantie. Een variant ervan zit in het navigatiesysteem van uw auto.

Algoritmen die niet bestaan
Bij klassen van problemen zoals het vinden van de GGD's en het vinden van kortste routes vragen wiskundigen zich in de eerste plaats af of wer wel  een algoritme bestaat waarmee elk probleem uit die klasse kan worden opgelost. Er zijn klassen problemen bekend waarvoor je kunt bewijzen dat zo'n algoritme niet bestaat. Zo vroeg de wiskundige Hilbert begin vorige eeuw om een algoritme dat bepaalt of een vergelijking opgebouwd uit meerdere variabelen en de operaties maal, plus en min een geheeltallige oplossing heeft. In het bewijs dat zo'n algoritme niet bestaat speelde de wiskundige Julia Robinson een sleutelrol, onderwerp van de onlangs verschenen film Julia Robinson and Hilbert's Tenth Problem.

Efficiënte algoritmen
Als je eenmaal weet dat een klasse problemen in principe algoritmisch oplosbaar is, dient zich de vraag aan of er een efficiënt algoritme bestaat, dat wil zeggen een algoritme dat draaiend op een redelijke computer zijn uitvoer binnen redelijke tijd teruggeeft. Aan een algoritme dat vele millennia nodig heeft heb je niets. Er zijn heel veel probleemklassen waarvoor geen efficiënt algoritme bekend is. In het beroemde handelsreizigersprobleem, bijvoorbeeld, moet een handelsreiziger een zo kort mogelijke rondrit langs al zijn klanten maken. Hoewel dit probleem lijkt op het vinden van een kortste route van A naar B, is het veel ingewikkelder. Wiskundigen en informatici twijfelen eraan dat er een efficiënt algoritme bestaat, maar kunnen vooralsnog niet bewijzen dat dat niet het geval is.

Ook als voor een klasse problemen geen efficiënte algoritmen bekend zijn, kunnen kleine problemen uit die klasse nog wel opgelost worden met een inefficiënt algoritme, liefst op een snelle computer. Daarom wordt, om te bepalen of een algoritme efficiënt genoemd mag worden, gekeken hoe snel de rekentijd groeit als de invoer groter wordt. Die invoer wordt in een computer opgeslagen in bits, die de waarden 0 of 1 kunnen aannemen. Als de rekentijd evenredig is met het aantal bits dat de invoer beslaat, dan heet het algoritme lineair. Als de rekentijd evenredig met het kwadraat van het aantal bits en dus als een parabool stijgt, dan heet het algoritme kwadratisch. Algoritmen die lineair zijn, of kwadratisch, of waarvan de rekentijd niet harder dan een bepaalde macht van het aantal invoerbits stijgt, heten polynomiaal, en worden als efficiënt beschouwd. Voor het definitieve antwoord op de vraag of er voor het handelsreizigersprobleem een polynomiaal algoritme bestaat---in vakjargon de vraag of P=NP---heeft het Clay Mathematics Institute in de VS een miljoen euro uitgeloofd.


Terug naar de site van Algoritmen Alom.


Mathematics cluster DIAMANT

Upcoming events

News - more news

Full professor position in Discrete Mathematics in Delft
1-11-2018

Delft Institute of Applied mathematics, Delft University of Technology, seeks a full Professor in the field of Discrete Mathematics. A description of the position can be found here. The deadline for applications is January 15, 2019.



ERC Starting grant for Daniel Dadush
26-9-2018

Daniel Dadush (CWI) has been awarded an ERC Starting Grant of 1.5 ME for his proposal ‘Towards a Quantitative Theory of Integer Programming’. With this grant, Dadush aims to revolutionize the understanding of integer programming (IP), the most popular method used today for finding optimal solutions to real-world optimization problems.

Read more.



VICI grant for Nikhil Bansal
26-9-2018

Nikhil Bansal has been awarded a Vici grant of 1.5 ME. He is one of the 35 academics to receive this grant from NWO in 2018. Bansal aims to use his grant to develop new algorithmic methods to make discrete decisions in a continuous way. He expects this to lead to applications in the fields of logistics, bio-informatics, chip design and machine learning.

Read more.



3 DIAMANT PhD positions awarded
19-12-2017

NWO, following a shortlist provided by the DIAMANT board, has decided to award 3 PhD positions to young DIAMANT members: Dion Gijswijt (TU Delft), Jan Steffen Müller (RUG) and Arno Kret (UvA).
Read more.