algoritmen-concepten

Algoritmisch probleem: een probleem dat (in principe) door middel van een algoritme opgelost kan worden. Een algoritmisch probleem kan meerdere oplossingen hebben; deze kunnen aanzienlijk verschillen in hun eigenschappen. Soms kunnen we van een bepaald probleem aantonen dat dit geen (deterministische) oplossing heeft, of dat de best denkbare oplossing niet efficiënter kan zijn dan een bepaalde ondergrens. We weten dan ook zeker dat we niet hoeven te zoeken naar een oplossing die nog efficiënter is (of dat een concurrent met een betere oplossing kan komen). Voor sommige lastige problemen, waarbij we zeker weten dat er geen efficiënt algoritme mogelijk is voor de optimale oplossing, zijn er wel efficiënte algoritmen die de optimale oplossing benaderen, vaak op een manier die in de praktijk acceptabel is.

We kunnen een algoritmisch probleem beschrijven zonder een beroep te doen op een oplossing. De beschrijving van een algoritmisch probleem heet ook wel de specificatie.

De specificatie van een (algoritmisch) probleem moet enerzijds volledig zijn: alle essentiële aspecten van het probleem moeten beschreven zijn. Anderzijds mag de specificatie niet over-specifiek zijn: door bijvoorbeeld teveel elementen van een bepaalde oplossing die we voor ogen hebben, in de specificatie op te nemen, maken we het onmogelijk om andere oplossingen te vinden voor het probleem.

Voorbeeld - specificatie van het sorteerprobleem: het sorteren van een rij getallen. Een eerste aspect is dat het resultaat een geordende rij getallen moet zijn. Maar, daarmee is de specificatie nog niet volledig: immers, een algoritme dat de rij 0, 1, 2, ... produceert, ongeacht de invoer, zou dan ook voldoen. Een tweede aspect is dan ook dat het resultaat een permutatie (verwisseling) van de invoer moet zijn.

Uitvoering van een algoritme (als onderdeel van een programma), soms ook wel "executie" genoemd (wat in het Nederlands meestal iets anders betekent), of proces: het algoritme wordt stap voor stap uitgevoerd op een processor, met een bepaalde invoer, en als resultaat de bijbehorende uitvoer. Deze uitvoering kan allerlei eigenschappen hebben: deze vraagt een bepaalde hoeveelheid rekentijd, computergeheugen, communicatie-bandbreedte, enz. (de "resources" of hulpbronnen); de uitvoering kan succes hebben, of falen. Deze eigenschappen kunnen we terugvoeren naar eigenschappen van het oorspronkelijke algoritme, maar soms ook naar de implementatie. Zo kan er bijvoorbeeld in de implementatie een eenvoudige tikfout gemaakt zijn, of kan de implementatie van de gebruikte programmeertaal een fout bevatten (wat overigens zeldzaam is, maar niet onmogelijk). De uitvoering van een algoritme kan op verschillende manieren falen: de uitvoering kan een onjuist resultaat opleveren, wat overigens niet altijd eenvoudig op te merken is; de uitvoering kan op een foutieve bewerking stuiten, zoals deling door 0; of de uitvoering kan in een toestand komen waarbij er geen voortgang meer geboekt wordt, waardoor de uitvoering niet eindigt.

Als de uitvoering van een algoritme faalt, is het algoritme incorrect. Echter, het omgekeerde is niet het geval: een algoritme kan incorrect zijn, maar dat hoeft niet bij elke executie aan het licht te komen; dat is wat het testen van algoritmen of programma's zo hachelijk maakt. (In de woorden van Edsger Dijkstra: Program testing can be used to show the presence of bugs, but never to show their absence!.)

De relatie tussen de verschillende begrippen hier is kort samengevat in bijgaande figuur.

Een voorbeeld: