Complexiteitsprijs INFORMATICA

De jaarlijkse Turingprijs voor informatica is toegekend aan de grondleggers van de complexiteitstheorie.

Juris Hartmanis, van de Cornell universiteit en Richard Stearns van de universiteit van de staat New York krijgen er samen vijfenveertigduizend gulden voor. Dat is veel minder dan de Nobelprijs, maar voor de informatica wordt de prijs, genoemd naar de Engelse wiskundige Alan Turing, toch als de tegenhanger daarvan beschouwd.

Stearns en Hartmanis bedachten de complexiteitstheorie in de jaren zestig, toen ze samen bij General Electric werkten. Bij het gebruiken van de toen piepjonge computer bleek het vaak nodig om van tevoren te weten hoeveel tijd het draaien van een programma zou kosten. Volgens de organisatie die de Turingprijs uitlooft, de Association for Computing Machinery, is er geen gebied binnen de informatica dat niet door de theorie is beinvloed.

De complexiteit van een algoritme bepaalt of een computer het in een redelijke tijd aankan. Een bekend voorbeeld is het probleem van de handelsreiziger die een aantal steden precies een keer moet aandoen. Bij een niet eens zo groot aantal steden doet zelfs een supercomputer er eeuwen over om de kortste route te vinden. Met behulp van technieken uit de complexiteitstheorie kon van een aantal andere problemen worden aangetoond dat ze precies zo moeilijk zijn als dit handelsreizigersprobleem.

Meer over

Wilt u iets delen met Trouw?

Tip hier onze journalisten

Op alle verhalen van Trouw rust uiteraard copyright. Linken kan altijd, eventueel met de intro van het stuk erboven.
Wil je tekst overnemen of een video(fragment), foto of illustratie gebruiken, mail dan naar copyright@trouw.nl.
© 2020 DPG Media B.V. - alle rechten voorbehouden