Vlaamse Vereniging WiskundeLeraars vzw

49 jaar! -

Welkom op website.

Abelprijs toegekend voor studie van algoritmische complexiteit.

De Abelprijs 2021 is toegekend aan Avi Wigderson uit Israël en László Lovász uit Hongarije. Ze kregen deze ‘Nobelprijs voor de wiskunde’  voor hun onderzoek in het grensgebied tussen theoretische informatica en discrete wiskunde. De naam van Lovász is verbonden aan het fameuze LLL-algoritme, dat hij samen met de Nederlandse wiskundigen Arjen en Hendrik Lenstra ontwierp.

Het is niet moeilijk om een rekenklus te bedenken, waar onze snelste computers nog niet eens mee klaar zullen zijn wanneer over ongeveer vijf miljard jaar de zon de aarde opslokt.

Een voorbeeld is het in twee ongeveer even grote priemfactoren ontbinden van een getal van duizend cijfers (voorbeeldje met een getal van maar vier cijfers: 2021  = 43 x 47. De factoren 43 en 47 zijn door geen enkel ander getal deelbaar, dus zijn het priemfactoren).

De complexiteit van dit type klus is exponentieel: als een computer een uur rekentijd nodig heeft om een getal van 100 cijfers te ontbinden, dan heeft hij al twee uur nodig om een getal van 101 cijfers te ontbinden, vier uur voor een getal van 102 cijfers, acht uur voor een getal van 103 cijfers, enzovoort (dit slechts om een idee te geven; het feitelijke groeitempo is enigszins anders).

Het omgekeerde, twee getallen met elkaar vermenigvuldigen, heeft een polynomiale complexiteit: als de computer twee getallen van 100 cijfers in 1 seconde kan vermenigvuldigen, dan kan hij getallen van 200 cijfers in slechts een paar seconden vermenigvuldigen. Dan groeit de rekentijd dus veel minder snel.

Het is voor computerprogrammeurs natuurlijk belangrijk om van te voren te weten of de complexiteit van een rekenklus exponentieel is of polynomiaal. Dat beperkt zich niet tot rekensommen; het gaat ook om zaken als de kortste route vinden tussen een aantal steden, of een lange lijst woorden op alfabetische volgorde zetten, of uit een groot aantal genetische tests afleiden of een zeker gen verantwoordelijk is voor een bepaalde ziekte.

De theoretische informatica deelt al die problemen in categorieën in, en bestudeert de complexiteit ervan. De wiskunde die daar bij gebruikt wordt is de zogeheten discrete wiskunde: wiskunde die in essentie alleen gehele getallen gebruikt. Dat is voldoende, omdat een computerprogramma alleen maar bewerkingen uitvoert op nullen en enen die ook weer nullen en enen opleveren.

Maar het bouwen en programmeren van computers bleef vrij lang een zeer praktische bezigheid, zonder echte theoretische onderbouwing. Volgens de motivatie van het Abelprijs comité, brachten deze prijswinnaars daar verandering in:  ‘Dankzij het leiderschap van Lovász en Wigderson zijn discrete wiskunde en het relatief jonge vakgebied van de theoretische computerwetenschap nu erkend als centrale delen van de moderne wiskunde.’

Overzicht van het werk van de Abelprijs winnaars in filmpje op You Tube 

Uiteraard bepaalt ook de efficiëntie van het algoritme dat een computer voor een klus gebruikt, hoeveel rekentijd dit vergt. Een taak die een exponentiële complexiteit leek te hebben, kan door een slim algoritme toch polynomiale complexiteit blijken te hebben.

Een voorbeeld is het LLL-algoritme dat Lovász met Arjen en Hendrik Lenstra ontwierp in 1982. Het LLL-algoritme kan in polynomiale tijd een klasse van problemen in de discrete wiskunde oplossen waarvan men tot dan toe altijd had gedacht dat ze exponentieel complex waren.

Met het LLL-algoritme zijn diverse geavanceerde geheimschriften gekraakt, en het speelt een rol in allerlei meer fundamentele wiskundige problemen.

Een gedetailleerde beschrijving van de wordingsgeschiedenis van het LLL-algoritme vind je hier .

De Abelprijs wordt ieder jaar toegekend aan één of meer wiskundigen. De prijs is genoemd naar de Noorse wiskundige Niels Abel. Er hoort een geldprijs van 7,5 miljoen Noorse kronen bij, ongeveer zevenhonderdvijftigduizend euro.