Algoritme, systematische procedure die - in een eindig aantal stappen - het antwoord op een vraag of de oplossing van een probleem oplevert. De naam is afgeleid van de Latijnse vertaling, Algoritmi de numero Indorum, van de 9e-eeuwse rekenkundige al-Khwarizmi's rekenkundige verhandeling 'Al-Khwarizmi betreffende de hindoeïstische kunst van het afrekenen'.
informatica: algoritmen en complexiteit
Een algoritme is een specifieke procedure voor het oplossen van een goed gedefinieerd rekenprobleem. De ontwikkeling en analyse van algoritmen is fundamenteel
Voor vragen of problemen met slechts een eindige reeks gevallen of waarden bestaat altijd een algoritme (althans in principe); het bestaat uit een tabel met waarden van de antwoorden. Over het algemeen is het niet zo'n triviale procedure om vragen of problemen te beantwoorden met een oneindig aantal gevallen of waarden om te overwegen, zoals "Is het natuurlijke getal (1, 2, 3,…) Een priemgetal?" of 'Wat is de grootste gemene deler van de natuurlijke getallen a en b?' De eerste van deze vragen behoort tot een klasse die beslisbaar wordt genoemd; een algoritme dat een ja of nee antwoord geeft, wordt een beslissingsprocedure genoemd. De tweede vraag behoort tot een klasse genaamd berekenbaar; een algoritme dat tot een bepaald aantal antwoord leidt, wordt een berekeningsprocedure genoemd.
Algoritmen bestaan voor veel van zulke oneindige klassen van vragen; Euclid's Elements, gepubliceerd omstreeks 300 voor Christus, bevatte er één voor het vinden van de grootste gemene deler van twee natuurlijke getallen. Elke basisschoolstudent wordt geboord in staartdeling, wat een algoritme is voor de vraag "Wat zijn het quotiënt en de rest bij het delen van een natuurlijk getal a door een ander natuurlijk getal b?" Het gebruik van deze berekeningsprocedure leidt tot het antwoord op de beslissende vraag: 'Deelt b een?' (het antwoord is ja als de rest nul is). Herhaaldelijke toepassing van deze algoritmen levert uiteindelijk het antwoord op de beslissende vraag 'Is een prime?' (het antwoord is nee als a deelbaar is door een kleiner natuurlijk getal dan 1).
Soms kan er geen algoritme bestaan om een oneindige klasse van problemen op te lossen, vooral wanneer er een andere beperking wordt opgelegd aan de geaccepteerde methode. Twee problemen uit de tijd van Euclides die het gebruik van alleen een kompas en een richtliniaal (ongemarkeerde liniaal) vereisten - het doorsnijden van een hoek en het construeren van een vierkant met een oppervlakte gelijk aan een bepaalde cirkel - werden bijvoorbeeld eeuwenlang nagestreefd voordat ze onmogelijk bleken te zijn. Aan het begin van de 20e eeuw stelde de invloedrijke Duitse wiskundige David Hilbert 23 problemen voor die wiskundigen de komende eeuw moesten oplossen. Het tweede probleem op zijn lijst vroeg om een onderzoek naar de consistentie van de axioma's van rekenen. De meeste wiskundigen twijfelden weinig aan de uiteindelijke verwezenlijking van dit doel tot 1931, toen de in Oostenrijk geboren logicus Kurt Gödel het verrassende resultaat demonstreerde dat er rekenkundige stellingen (of vragen) moeten bestaan die niet bewezen of weerlegd kunnen worden. In wezen leidt een dergelijke propositie tot een vaststellingsprocedure die nooit eindigt (een aandoening die bekend staat als het stopprobleem). In een mislukte poging om ten minste vast te stellen welke stellingen onoplosbaar zijn, heeft de Engelse wiskundige en logicus Alan Turing het losjes begrepen concept van een algoritme rigoureus gedefinieerd. Hoewel Turing uiteindelijk bewees dat er onbeslisbare stellingen moesten bestaan, werd zijn beschrijving van de essentiële kenmerken van een algemene algoritmemachine of Turing-machine de basis van de informatica. Tegenwoordig staan de kwesties van beslisbaarheid en berekenbaarheid centraal in het ontwerp van een computerprogramma - een speciaal type algoritme.
