British Museum-algoritme

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Een British Museum-algoritme is een algoritme dat een oplossing probeert te vinden door alle mogelijkheden te bekijken, beginnend bij de kleinste. Met deze term wordt vaak een conceptuele maar niet praktische aanpak bedoeld om een oplossing te vinden in situaties waar zeer veel mogelijkheden zijn. De naam verwijst naar het British Museum, een museum in Londen dat een van de grootste collecties ter wereld bezit.

Voorbeelden[bewerken]

In theorie kan men bijvoorbeeld het kleinst mogelijke computerprogramma dat een probleem oplost, vinden door eerst alle programma's met een broncode bestaande uit één teken te genereren. Controleer vervolgens of een van deze programma's het probleem oplost (het stopprobleem maakt deze controle overigens niet mogelijk). Zo niet, genereer alle programma's bestaande uit twee tekens, drie tekens, enzovoort. Deze aanpak vindt, in theorie, het kleinst mogelijke programma dat een bepaald probleem oplost. In de praktijk zou deze aanpak een onacceptabele hoeveelheid tijd vergen: voor veel problemen zal meer tijd dan de leeftijd van het heelal benodigd zijn.

Een ander voorbeeld is het vervullen van een propositie in de logica. Het vervullen van een propositie is het vinden van een toekenning van waar of onwaar aan de atomaire formules zodat de gehele propositie waar wordt. Een algoritme zou, in principe, elke mogelijke toekenning van waar en onwaar kunnen proberen maar in het slechtste geval moeten alle mogelijke toekenningen bekeken worden - zeker bij lange proposities kost dit veel tijd.

Deze redenaties kunnen worden gebruikt om aan te tonen dat bepaalde optimalisaties, het bewijzen van stellingen of spraakherkenning mogelijk of onmogelijk zijn.

Zie ook[bewerken]