2 - algoritmen in het dagelijks leven

Aan de hand van een aantal voorbeelden uit het dagelijks leven zullen we kennis maken met de verschillende concepten die van belang zijn rond algoritmen. We zullen ook zien wat er allemaal mis kan gaan, en hoe we kunnen proberen dat te voorkomen. Het mag duidelijk zijn dat het voor automatisering een vereiste is dat het algoritme altijd het juiste resultaat oplevert.Niet alleen moet een algoritme een juist resultaat opleveren, dat moet ook niet teveel moeite kosten; een algoritme dat op een computer uitgevoerd wordt, moet binnen redelijke tijd met een resultaat komen; bovendien moet de hoeveelheid computergeheugen die daarvoor nodig is, zo mogelijk binnen de perken blijven. Ook bij algoritmen in het dagelijks leven hebben we vaak te maken met dergelijke eisen op het gebied van efficiëntie en schaalbaarheid.

Een probleem dat door middel van een algoritme op te lossen is, heet een algoritmisch probleem. (Er zijn overigens ook veel problemen die we niet door middel van een algoritme kunnen oplossen.) We zullen een aantal aspecten van algoritmische problemen behandelen.

Concepten

Een voorbeeld van een algoritme uit het dagelijks leven is een recept voor het bereiden van een gerecht. Rond een recept kunnen we het volgende onderscheiden:

1. Een recept is een abstract iets – het bestaat eigenlijk alleen in de hoofden van mensen. “Een recept kun je niet eten.” Een recept is statisch, speelt zich niet af in de tijd.
2. Een recept is meestal beschreven in een speciale keukentaal, als variant van een natuurlijke taal zoals Nederlands. (Zo’n concrete beschrijving is meestal nodig om het recept in een ander hoofd te krijgen dan degene die het bedacht heeft.)
3. Een recept kan uitgevoerd worden door een kok.
4. Het uitvoeren van een recept is dynamisch, het is een proces dat zich afspeelt in de tijd.
5. Voor het uitvoeren van een recept zijn allerlei hulpmiddelen (resources) nodig, en energie, en tijd.
6. Voor het uitvoeren van een recept zijn ingrediënten nodig (“invoer”).
7. Als resultaat van het uitvoeren van een recept krijgen we een gerecht (“uitvoer”).

In het algemene geval kunnen we zo bij algoritmen de volgende concepten onderscheiden:

1. Het algoritme, als abstract, statisch, wiskundig concept
   • "algoritme" is een abstract wiskundig begrip, te vergelijken met "cirkel"
   • een algoritme is de statische beschrijving van een dynamisch proces.
     • een algoritme beschrijft de handelingen voor een bepaalde klasse van uitvoerders
2. Het programma, als concrete vorm van het algoritme, uitgedrukt in een specifieke taal met een duidelijk omschreven betekenis
3. Het programma kan uitgevoerd worden door een processor; deze processor moet deze specifieke taal kunnen interpreteren.
   • Een processor kan typisch een grote klasse van algoritmen uitvoeren
     • in het bijzonder vormen computers zeer universele processoren
4. De uitvoering van een programma noemen we een proces; dit is dynamisch, speelt zich af in de tijd
   • We moeten bijhouden hoe ver we met de uitvoering van het programma gevorderd zijn
   • Tijdens elke stap van het proces verkeert de processor, in combinatie met de invoer en de uitvoer, zich in een bepaalde toestand
5. Voor het uitvoeren van een programma zijn allerlei resources nodig
6. Voor het uitvoeren van een programma is er (meestal) invoer of input nodig
7. Als resultaat van het uitvoeren van een programma (met een bepaalde invoer) krijgen we de uitvoer.

Invoer en uitvoer kunnen concreet zijn (meel en brood), of abstract (bijvoorbeeld getallen).

Invoer en uitvoer kunnen statisch zijn, zoals in de zojuist genoemde voorbeelden. Invoer en uitvoer kunnen ook dynamische zijn, dat wil zeggen zich afspelen in de tijd. Een voorbeeld hiervan zijn de invoer en uitvoer van regelalgoritmen.

In de relaties tussen deze concepten zijn onder meer de volgende eigenschappen van belang:

• Eenzelfde algoritme kan in verschillende talen, op verschillende manieren gecodeerd worden - er is dan nog steeds sprake van hetzelfde algoritme. Voorbeeld: een recept, oorspronkelijk beschreven in het Italiaans, vertaald in het Nederlands, blijft hetzelfde recept.
• Een programma kan vele malen uitgevoerd worden, op verschillende processoren, mogelijk met verschillende eigenschappen.
• Elke uitvoering van een programma heeft een specifieke invoer, en resulteert in de daarbij behorende uitvoer.

Merk op dat we in het dagelijks taalgebruik het algoritme, het proces, en het resultaat soms door elkaar gebruiken: met een steek bij het breien kunnen we zowel het voorschrift, de handeling, als het resultaat bedoelen. In de informatica proberen we hierin zorgvuldiger te zijn.

Algoritme versus uitvoering

De uitvoering of executie van een programma heet ook wel een proces. (In andere vakgebieden wordt de term proces ook wel gebruikt voor een beschrijving van de acties, wat we in de informatica het algoritme of programma noemen. In de informatica betreft een proces altijd het dynamische gebeuren.)

Bij een proces moeten we een administratie bijhouden hoe ver we gevorderd zijn; bijvoorbeeld, als we een trui breien, of als we een gerecht bereiden volgens een ingewikkeld recept, moeten we bijhouden wat de volgende stap is. Vaak moeten we ook deelresultaten onthouden, bijvoorbeeld in het geval van een rekenproces. Kortom, we moeten de toestand van het proces bijhouden, als we het bijbehorende programma goed willen uitvoeren.

Een algoritme (programma) beschrijft alle mogelijke uitvoeringen - voor alle mogelijke invoer-combinaties, voor alle mogelijke uitvoerders (processoren). Het aantal verschillende uitvoeringen kan enorm groot zijn; bijvoorbeeld voor het optellen van 2 32-bits getallen is het aantal invoer-mogelijkheden al 2^64 - of de helft, 2^63, als we van de symmetrie gebruik maken. Toch willen we graag universele uitspraken over alle uitvoeringen van een algoritme kunnen doen. Dit is bijvoorbeeld mogelijk door wiskundige eigenschappen van het algoritme te gebruiken.

Een algoritme is een eindige beschrijving - maar de uitvoering van een algoritme kan in principe oneindig lang duren. Doordat een algoritme herhaling kan bevatten, is er geen relatie tussen de lengte van een algoritme, en de duur van de uitvoering van een algoritme.

Automaten voor de uitvoering van algoritmen

Merk op dat we het begrip algoritme ruim gedefinieerd hebben – een processor kan nog van alles zijn, als het maar de betreffende opdrachten in de specifieke taal kan interpreteren.

In het bijzonder kan de processor een mens zijn. Het begrip algoritme bestaat al heel lang, en totdat er mechanische processoren beschikbaar kwamen, was de mens de gebruikelijke processor. In veel voorbeelden uit het dagelijks leven, inclusief rekenen zoals onderwezen op de basisschool, is de processor een mens.In de informatica zijn we in het bijzonder geïnteresseerd in gevallen waarbij de processor een automaat is, meestal een elektronische. Algoritmen moeten dan niet alleen zonder eigen inbreng of fantasie uitgevoerd kunnen worden, maar we moeten er ook zeker van zijn dat er bij de uitvoering van een algoritme niets mis kan gaan – op straffe van allerlei kleine en grote ongelukken, die we soms pas na jaren opmerken. Het voorkomen van dit soort problemen is dan ook een belangrijk thema in de informatica.

Ruim voordat er sprake was van computers, heeft men automaten bedacht om bepaalde algoritmen uit te kunnen voeren. Er zijn bijvoorbeeld automatische weef- en breimachines die werken op basis van programma's die door gaatjespatronen in een strook papier of karton voorgesteld worden. (Zie Jaquard weefgetouw, Wikipedia: http://nl.wikipedia.org/wiki/Joseph-Marie_Jacquard).

Ook voor muziek bestaan er dergelijke automaten, zoals draaiorgels en pianola's; in het museum Van speelklok tot pierement, in Utrecht, zijn veel van dergelijke automaten te bewonderen. (zie ook http://www.museumspeelklok.nl/)

Deze automatische machines zijn in zekere zin voorgangers van de huidige computers, en sommige van de oplossingen uit deze automaten zijn gebruikt in de eerste generaties computers.

Wat kan er mis gaan?

Een goed begrip van deze verschillende concepten kan ons helpen om te begrijpen wat er allemaal fout kan gaan, en hoe we dat kunnen voorkomen. Om enkele voorbeelden te noemen:

1. Het algoritme kan fout zijn – dat wil zeggen, niet geschikt als oplossing voor het bedoelde algoritmisch probleem.
2. Het programma kan fouten bevatten; dit kan bijvoorbeeld een resultaat zijn van een fout bij het opschrijven of vertalen van het algoritme in de specifieke taal.
3. De processor kan fouten bevatten,
   1. bijvoorbeeld ontwerpfouten,
   2. maar mogelijk ook fouten in de mechanica of elektronica, veroorzaakt door slijtage;
   3. het kan ook zijn dat de processor de specifieke taal niet kan interpreteren; het programma is bedoeld voor een ander soort processor
4. Als er iets fout gaat, resulteert dat in een mislukking tijdens het proces; een van de resultaten kan zijn dat het proces op een onverwachte manier afgebroken wordt, of dat het proces niet eindigt. In extreme gevallen kan de processor kapot gaan, of iets in de omgeving. Maar, soms merken we niet dat er iets mis gaat, en krijgen we een resultaat dat ogenschijnlijk goed is.
5. De invoer kan fout zijn – dat wil zeggen, niet passen bij het algoritmisch probleem.
   • “Garbage in, garbage out”
6. Als we een resultaat krijgen, is niet gezegd dat dit het resultaat is dat we verwachten. Het is niet altijd eenvoudig te controleren of het resultaat juist is.
   • Als je een programma hebt om de dikte van een pijler voor een brug uit te rekenen, komt daar vast een getal uit – hoe weet je of dit juist is?

Opgave. Probeer zelf na te gaan wat de overeenkomstige problemen kunnen zijn in het geval van het receptenvoorbeeld.

Algoritme als resultaat

Het resultaat van een algoritme kan ook weer een algoritme zijn. Een voorbeeld hiervan uit het dagelijks leven is de routeplanner: het resultaat is een routebeschrijving, wat ook weer een algoritme is, met een bestuurder als uitvoerder. In de informatica vind je dit bijvoorbeeld in de vorm van een compiler (vertaler) of een programma-generator: het resultaat daarvan is een programma, meestal in een andere taal dan de invoer.

Elementen van een algoritme

Waaruit bestaat een algoritme? Laten we het voorbeeld van het recept weer eens onder de loep nemen:

1. Het recept bevat basisopdrachten die door de kok direct begrepen worden; bijvoorbeeld: doe het meel in de kom
2. Het recept bevat manieren om deze basisopdrachten samen te stellen tot (delen van) een recept; enkele voorbeelden:
   1. Opeenvolging: doe eerst het meel in de kom, en voeg vervolgens de melk toe;
   2. Groepering
   3. Keuze, of voorwaardelijke uitvoering: als de boter te koud is, verwarm deze dan enige seconden in de magnetron;
   4. Herhaling, vaak in twee vormen:
      1. Bepaalde herhaling, waarbij het aantal van de voren vaststaat: voeg driemaal een schep suiker toe;
      2. Onbepaalde herhaling: roer het meel en de melk totdat je een stevig beslag hebt;
   5. Concurrency - meerdere opdrachten die tegelijkertijd uitgevoerd worden: bereid de saus, terwijl het vlees in de oven gaart;
   6. In het bijzonder bevat een recept deelrecepten die een naam gekregen hebben; veel van deze deelrecepten zijn standaard, maar bij een ingewikkeld recept zouden die ook ter plekke uitgelegd kunnen worden.

In het algemene geval van algoritmen komen we deze ook tegen, afhankelijk van de taal waarin we onze algoritmen of programma’s beschrijven.

1. Basisopdrachten
2. Samenstellingen:
   1. Opeenvolging - eerst A, dan B
   2. Groepering
   3. Keuze of voorwaardelijke opdracht - voer A alleen uit als aan voorwaarde X voldaan is
   4. Herhaling, te onderscheiden in
      1. bepaalde herhaling - herhaal A B-maal
      2. onbepaalde herhaling - herhaal A totdat aan voorwaarde X voldaan is
   5. Concurrency - meerdere opdrachten die deels overlappend in de tijd uitgevoerd worden
3. Benoemde deelalgoritmen (procedures of functies)

Enkele voorbeelden ontleend aan de programmeertaal Python:

Concurrency

In sommige gevallen is er sprake van gelijktijdigheid van meerdere acties. Een voorbeeld is het bereiden van een ingewikkeld recept: daarbij is het vaak nodig om verschillende onderdelen tegelijkertijd op het vuur te hebben. "bereid de saus terwijl het vlees in de oven gaart"

Een ander voorbeeld is meerstemmige muziek: de verschillende stemmen verlopen gelijktijdig.

Bij concurrency is het nodig om de gelijktijdige opdrachten in de tijd op elkaar af te stemmen: er is op sommige momenten de noodzaak tot synchronisatie. Bij koken kan dit een lastig probleem zijn, om de verschillende onderdelen op het juiste moment klaar te hebben, bijvoorbeeld om ze samen te kunnen voegen. Bij muziek is deze synchronisatie eigenlijk voortdurend; als er meerdere processoren (musici) bij betrokken zijn, is er vaak een aparte processor (dirigent) die deze synchronisatie tracht aan te geven.

Ook in de informatica speelt concurrency een belangrijke rol. Algoritmen voor systemen met concurrency zijn vaak lastig te begrijpen - een van de grote problemen is dat de verschillende onderdelen in willekeurige volgorde afgehandeld kunnen worden.

Efficiëntie van een algoritme

De uitvoering van een algoritme vraagt resources (hulpbronnen) zoals tijd en hulpmiddelen: voor het breien van een trui hebben we tijd nodig, breinaalden, en een bepaalde hoeveelheid wol. De hoeveelheid tijd en de hoeveelheid wol die we nodig hebben voor een trui van een bepaalde maat, kan van patroon tot patroon (algoritme) verschillen.

In plaats van tijd, kunnen we soms ook het aantal stappen (elementaire opdrachten) bepalen dat voor de uitvoering van een algoritme nodig is.

In sommige gevallen is het mogelijk om resources tegen elkaar uit te wisselen: in het geval van algoritmen op het gebied van dataverwerking kunnen we soms rekentijd (rekenstappen) uitwisselen tegen ruimte (geheugen). We kunnen bijvoorbeeld, in plaats van een algoritme om twee getallen met elkaar te vermenigvuldigen, een tabel maken met alle uitkomsten van die vermenigvuldiging. (Dit lukt natuurlijk alleen als die getallen niet al te groot zijn.)

De hoeveelheid resources, bijvoorbeeld tijd, die nodig is om voor de uitvoering van een algoritme kan afhankelijk zijn van de (omvang van) de invoer; soms is dit gerelateerd aan de omvang van de uitvoer.

Voorbeeld: het aantal rekenstappen dat we moeten uitvoeren als we twee getallen moeten optellen, hangt af van de lengte (het aantal cijfers) van de getallen: als we volgens de methode zoals geleerd op de basisschool twee getallen van elk honderd cijfers moeten optellen, hebben we daarvoor tien maal zoveel tijd nodig als wanneer we twee getallen van tien cijfers moeten optellen.

Maar het kan ook voor een bepaald algoritme zo zijn dat we voor een invoer die tien maal zo groot is, (veel) meer dan tien maal zoveel tijd nodig hebben. Zo kan het sorteren van een rij getallen volgens het bubblesort-algoritme, bij het sorteren van een rij getallen die tien maal zo groot is, honderdmaal zoveel tijd nodig zijn. (We zullen in een volgend hoofdstuk hiermee experimenteren.)

Algoritmisch probleem

Een algoritmisch probleem is een probleem dat door middel van een algoritme opgelost kan worden.

Een algoritmisch probleem vormt de specificatie van verzameling algoritmen. Vaak beschrijven we een algoritmisch door vast te stellen aan welke eisen het resultaat moet voldoen, in termen van de invoer. Bijvoorbeeld, in het geval van het algoritmische probleem "opklimmend ordenen van een rij getallen" (sorteren): de uitvoerrij moet een permutatie (verwisseling) van invoerrij zijn zodanig dat elk volgend getal tenminste even groot is als het voorafgaande getal. Merk op dat deze specificatie geen uitspraak doet over de manier waarop het resultaat bereikt moet worden: er zijn verschillende algoritmen mogelijk die een oplossing van dit algoritmisch probleem vormen.

In de informatica proberen we soms af te schatten hoe efficiënt een algoritmisch probleem opgelost kan worden, anders gezegd: wat de efficiëntie is van de meest efficiënte oplossing die mogelijk is. Het is eigenlijk vrij bijzonder dat we zo'n soort analyse kunnen doen: zonder de meest efficiënte oplossing voor een probleem te kennen, kunnen we toch uitspraken over die oplossing doen. We kunnen ook aantonen dat een bepaalde oplossing de meest efficiënte is, en dat er geen betere oplossing bestaat.

Specificatie, volledigheid en overspecificatie

Bij het beschrijven van een algoritmisch probleem moeten we enerzijds volledig zijn: we moeten alle essentiële aspecten van een mogelijke oplossing beschrijven. Anderzijds moeten we niet overspecifiek zijn: we moeten geen eisen stellen die niet essentieel zijn voor een oplossing.

Overspecificatie is meestal een gevolg van het denken in termen van mogelijke oplossingen, in plaats van in termen van het eigenlijke probleem. In plaats van het probleem helder te omschrijven, beschijf je dan een of meer oplossingen die je in gedachten hebt.

Een voorbeeld van mogelijke overspecificatie: als je een wet opstelt die moet voorkomen dat werknemers in hun werk gedwongen worden mee te roken met hun collega's of met klanten, bijvoorbeeld in een cafe, dan moet je deze eis beschrijven, en geen beschrijving geven van de toegestane oplossingen; door dit laatste te doen sluit je de inventiviteit van betrokkenen uit, die de gestelde eis met de lokale omstandigheden moeten combineren.

Neem als voorbeeld het sorteerprobleem. Een eerste aspect waaraan een oplossing moet voldoen is dat het resultaat een geordende rij is. Maar, hiermee is het probleem nog niet volledig gespecificeerd: immers, een oplossing die altijd, ongeacht de invoer, de rij "1, 2, 3, 4, 5" oplevert, voldoet ook aan deze specificatie. We moeten dus nog een tweede aspect toevoegen: het resultaat moet bovendien een rij zijn die een permutatie (verwisseling) is van de invoerrij. Een derde aspect, dat we meestal impliciet veronderstellen en dus meestal niet vermelden is dat het algoritme (de oplossing) moet eindigen, in een toestand waarin het resultaat volledig bepaald is.

Preconditie

Naast eisen aan het resultaat, moeten we ook vaak eisen stellen aan de invoer: het probleem heeft alleen zin voor waarden die aan bepaalde eisen voldoen. Bijvoorbeeld in het geval van het sorteerprobleem, zal de invoer een rij waarden moeten zijn waarvoor een volledige ordening gedefinieerd is, en waarvan de elementen dus paarsgewijs vergeleken kunnen worden. Appels en peren kunnen we onderling niet vergelijken, en daarvoor kunnen we het sorteerprobleem niet definiëren. Dergelijke eisen aan de invoer noemen we ook wel de preconditie.

Algoritmen in de biologie

In de biologie kunnen we het principe van algoritmen op vele plaatsen ontdekken. Een eerste voorbeeld is het DNA; dit bevat onder meer een aantal algoritmen voor de productie van eiwitten. De code op het DNA bestaat uit een sequentie van 3-tupels van de basen die aangeduid worden als A, C, G, en T. Elk 3-tupel of codewoord (codon) heeft daarmee 4x4x4 = 64 mogelijkheden; een eiwit bestaat uit een sequentie van aminozuren; er zijn 20 verschillende aminozuren, waardoor de code voor dit doel ruim bemeten is. Sommige codons fungeren als startsymbool of stopsymbool, om het begin of het eind van het gecodeerde eiwit aan te geven. Daarnaast worden soms verschillende codons gebruikt voor hetzelfde aminozuur. De productie van de eiwitten uit de DNA-code verloopt indirect: eerst wordt een kopie van het overeenkomstige stuk DNA gemaakt in de vorm van RNA (mRNA, ofwel messenger RNA). Dit wordt vervolgens naar de ribosomen getransporteerd, die we als universele programmeerbare eiwitproductie-processoren kunnen beschouwen, met het mRNA als programma. Op basis van eenzelfde stuk mRNA kunnen meerdere exemplaren van hetzelfde eiwit gemaakt worden.

(Zie o.a. Wikipedia: http://nl.wikipedia.org/wiki/Dna, http://nl.wikipedia.org/wiki/Ribosoom; de Engelstalige versie, die je vanuit de Nederlandse versie vindt door English als taal te kiezen, is uitgebreider, en bevat enkele leuke animaties.)

Er zijn ook veel voorbeelden van regelalgoritmen in de biologie; een van de voorbeelden hiervan is de regeling van het bloedglucoseniveau, door middel van de hormonen insuline en glucagon (en adrenaline). Enerzijds moet er voldoende glucose in het bloed zitten, om de cellen in het lichaam van voldoende brandstof te voorzien; anderzijds is een te hoog niveau glucose riskant, zowel op de korte als op de lange termijn.

(Zie o.a. Wikipedia: http://nl.wikipedia.org/wiki/Bloedglucosespiegel)