Naar inhoud
BetaAI Begrippen

AI-begrippen in gewone taal. Zoek een begrip, blader op letter of filter op onderwerp.

Niet-deterministisch algoritme

Engels: Nondeterministic algorithm · Ook wel: nondeterministic algorithm, non-deterministic algorithm

In het kort

Een niet-deterministisch algoritme is een rekenmethode die bij dezelfde invoer verschillend gedrag kan vertonen. Anders dan een deterministisch algoritme, dat steeds hetzelfde pad volgt, kan dit algoritme per uitvoering een andere stap of uitkomst kiezen. Dat kan komen door een toevalsgetal of doordat gelijktijdige stappen in een andere volgorde klaar zijn, zodat dezelfde invoer twee keer een ander resultaat geeft.

Waarom is dit belangrijk?

Met een niet-deterministisch algoritme kunnen onderzoekers moeilijke rekenvragen aanpakken, doordat één geldige oplossingsroute volstaat ook als andere routes mislukken. In de wetenschap gebruiken onderzoekers dit model om te bepalen welke problemen een computer in redelijke tijd kan oplossen. Studenten en werknemers moeten zo'n antwoord extra controleren, omdat een poging soms een fout resultaat oplevert voordat een juiste route is gevonden.

Zo werkt het in de praktijk

In de cryptografie gebruiken ontwerpers een niet-deterministisch algoritme, zodat een aanvaller de uitkomst niet vooraf kan berekenen. Getallen die alleen op toeval lijken, zijn dan niet genoeg. De hashtabel die Hans Peter Luhn bij IBM invoerde, is een vroege datastructuur die met toeval werkt.

Onderzoek naar priemtests bouwt op dit idee. Solovay en Strassen maakten een test die voor grote getallen snel blijft, en Rabin deed hetzelfde met de test van Miller. Een even snelle test zonder toeval ontbrak toen nog.

Twee werkwijzen ordenen deze algoritmen. Een Las Vegas-algoritme geeft altijd een juist antwoord en laat de rekentijd wisselen. Een Monte Carlo-algoritme stopt binnen een vaste tijd en laat een kleine kans op een fout toe.

Bron: en.wikipedia.org

Gecontroleerd op 5 november 2026