We beschrijven hier enkele voorbeelden van algoritmen zoals we die in de informatica tegen komen. Als processor maken we gebruik van een spreadsheetprogramma. Dit heeft als voordeel dat de formulering van de algoritmen vaak eenvoudig is; een nadeel is dat we geen gebruik kunnen maken van herhaling - waardoor we de acties volledig moeten uitschrijven.
Toelichting bij de notatie. In de spreadsheets die wij gebruiken wordt eenzelfde formule herhaaldelijk uitgerekend; dit bereiken we door deze formule te kopiëren in de gehele kolom (meestal alleen de eerste 50 posities, om het rekenwerk binnen de perken te houden). Vaak is er iets bijzonders aan de hand met de eerste rij. We beschrijven in de schema's de eerste rij, de tweede rij, en de (n+1)e rij. In de praktijk betekent dit dat we de eerste rij invullen, en de tweede rij, en vervolgens de inhoud van de tweede rij in een bepaalde kolom kopiëren naar de rest van die kolom (bijvoorbeeld tot rij 50). In de meeste gevallen is er sprake van relatieve verwijzingen - bij het kopiëren worden deze automatisch aangepast. Alleen als er sprake is van een absolute verwijzing moeten we dit expliciet aangeven, bijvoorbeeld als "B$1" in plaats van "B1".
De velden gemerkt als (input) zijn bedoeld voor de invoer-waarden van het algoritme.
Een spreadsheet met deze voorbeelden is te vinden als bijlage.
Een bekend algoritme is het algoritme van Euclides voor het bepalen van de grootste gemene deler van twee strikt positieve gehele getallen, zeg A en B.
De informele beschrijving van dit algoritme is als volgt:
Zolang A en B niet gelijk zijn:
Trek van het grootste van de twee het andere af.
Zodra ze gelijk zijn, is de grootste gemene deler A (of B).
In het spreadsheetmodel gebruiken we de kolommen A en B voor de twee getallen zoals die zich ontwikkelen; we trekken steeds het kleinste getal van van het grootste, hierdoor verandert de volgende waarde in een van beide kolommen. Als de waarden in beide kolommen gelijk zijn, hebben we het antwoord gevonden. (In het spreadsheet-algoritme is daar geen rekening mee gehouden: de berekening wordt een vast aantal malen herhaald.)
In de programmeertaal Python wordt dit:
def ggd (a, b): if a < b: return ggd (a, b-a) elif a > b: return ggd (a-b, b) else: return aEen bekend voorbeeld uit de numerieke wiskunde is het algoritme van Newton-Raphson voor het bepalen van het nulpunt van een functie. Dit gebruiken we hier voor het uitrekenen van de vierkantswortel van een getal.
Het algoritme wordt onder andere beschreven, met een fraaie animatie, op Wikipedia: http://nl.wikipedia.org/wiki/Newton-Raphson.
Dit algoritme benadert het nulpunt x van een functie f door herhaald toepassen van:
x(n+1) = x(n) - f(x(n)) / f'(x(n))
We kunnen dit algoritme gebruiken voor het bepalen van de vierkantswortel van het getal B, door het nulpunt te bepalen van de functie f(x)=x^2-B
De afgeleide f'(x) is dan 2*x. We krijgen zo het volgende spreadsheet-schema:
Merk op dat dit algoritme zeer snel convergeert naar het gezochte nulpunt (als het convergeert): je hebt maar weinig stappen nodig om een precies antwoord te krijgen.
We kunnen de binaire representatie van een getal bepalen door steeds het laatste (minst-significante) cijfer ("bit") te bepalen, en het getal vervolgens te halveren. We krijgen zo als spreadsheet-schema:
Kolom A bevat het oorspronkelijke getal, en de herhaald gehalveerde versies daarvan; kolom B bevat de rest na deling door 2: het achterste bit. De waarde hiervan wordt in kolom 3 in een letterteken omgezet; deze lettertekens worden in de laatste kolom gecombineerd tot de uiteindelijke binaire representatie.