Inleiding
Algoritmiek
Rush Hour Traffic Jam Game
Je krijgt volgend spelbord voorgeschoteld.
Alles begint met een probleem.
… en een duidelijke probleembeschrijving:
Wat is de beginsituatie? Wat is het gewenste eindresultaat?
Verschuif beurtelings voertuigen horizontaal en vertikaal op de 'sporen' zodat uiteindelijk de rode auto kan buitenrijden.
Daarvoor bedenken we een oplossingsmethode.
Wat moet erin? / Beginsituatie (A)
Wat komt eruit? / Eindresultaat (B)
Hoe geraken we van A naar B?
En dan zoek je een oplossing
Je zoekt een oplossingsmethode … en als je die gevonden hebt, wil je die oplossing noteren zodat anderen ze ook kunnen uitvoeren.
Bij Rush Hour ziet dat er zo uit …
Terminologie
Probleem
Beginsituatie Gewenst eindresultaat
Oplossingsstrategie? Algoritme: de opsomming - in een eindig aantal stappen - van alle handelingen die men moet uitvoeren om van een gegeven beginsituatie tot een gewenst eindresultaat te komen.
Processor: uitvoerder van het algoritme.
Algoritme
‘Het algoritme’ of ‘de algoritme’ Meervoud: ‘algoritmes’ of ‘algoritmen’
Algoritmes in het dagelijk leven
Algoritmes in het dagelijk leven
Algoritmes in het dagelijk leven
Rugpand: 1. Zet 73 st. op met nld. 2½ needles. Brei 4 cm boordsteek 2. Brei verder met nld. 3 in tricotsteek tot een lengte van 14,4 cm (52 nld.) excl. boord. 3. Armsgat: Kant 2 st. af aan het begin van de volgende 2 nld. Brei tot een armsgathoogte van 11,7 cm (42 nld), tot er 69 st over zijn. Brei verder tot een totale armsgathoogte van 11,7 cm. 4. Hals: Brei beide kanten tegelijkertijd. Brei 20 st., zet de volgende 29 st. op een hulpnaald. Brei de resterende 20 st. met een tweede bol garen. Minder aan de halskant elke naald 2 x 1 st. tot er 18 steken over zijn. 5. Tegelijkertijd, als de armsgathoogte 12,2 cm is (44 nld), met de schouder beginnen. 6. Schoudervorming: Kant 3 x 6 st. af aan de kant van het armsgat.
Algoritmes in het dagelijk leven
Deelalgoritmen CPR
Een algoritme is meestal ingedeeld in verschillende stappen. Iedere stap kan opnieuw gezien worden als een proces om van een bepaalde beginsituatie een bepaald eindresultaat te bereiken. Iedere stap kan bovendien weer als een volledig apart algoritme uitgeschreven worden. ???
• Controleer of de ogen van de patiënt open zijn. • Spreek de patiënt aan en controleer of hij/zij reageert. • …
Iedere afzonderlijke stap binnen een algoritme noemen we daarom een deelalgoritme.
Concrete en abstracte deelalgoritmen
Bepaalde stappen binnen in een algoritme lijken vanzelfsprekend, vb. "Roep hulp".
Dat deelalgoritme kunnen wij zonder verdere uitleg uitvoeren. We spreken dan van een concreet (deel)algoritme of een concrete opdracht. Andere deelalgoritmen kan de processor niet direct uitvoeren. Er zijn bijkomende instructies nodig vooraleer de processor de handeling kan volbrengen. Dat zijn abstracte (deel)algoritmen of abstracte opdrachten. vb.
"Open de luchtweg."
Probleemanalyse: top-downmethode
Deel eerst je probleem op in een aantal grote stappen, een aantal deelproblemen. Dit heet de grofstructuur of het hoofdalgoritme.
Verfijning Stappen die voor de processor abstract zijn, moeten verder uitgewerkt worden.
Top-down
De hierboven beschreven methode om een proces te analyseren, noemt men de top-down ontwerpmethode.
Nog een voorbeeld
1 kopje koffie algoritme (1) (2) (3) (4)
Kook water Doe koffie in kopje Schenk water in kopje Roer
Grofstructuur
Proces is in stappen verdeeld Elke stap kan - indien nodig voor processor beschreven worden door een kleiner en eenvoudiger algoritme
Stapsgewijze verfijning (1)
Kook water (1) (2) (3) (4)
(2)
Doe poeder-koffie in kopje (1) (2) (3) (4)
(3)
Vul de ketel Zet ketel op fornuis Wacht tot het water kookt Haal de ketel van het fornuis
…
Open de koffie-bus Neem er een schepje poeder-koffie uit Doe de koffie in een kopje Sluit de koffie-bus
Verfijning
Stapsgewijze verfijning
De oplossing van een probleem wordt eerst beschreven in grote lijnen (grofstructuur). Doorgaan tot verfijning voldoende gedetailleerd en nauwkeurig is om uitvoering door de betreffende processor mogelijk te maken. Interpretatief vermogen van de processor wordt bekend verondersteld. Stoppen met verfijnen wanneer elke stap van het algoritme in de taal van de processor concreet is geformuleerd.
Programmeren = Ontwerpen van een algoritme waarbij de processor een computer is. Programma: de vertaling van een algoritme in een notatie (taal) die door een processor kan geïnterpreteerd en uitgevoerd worden.
Stappen in de ontwikkeling van een algoritme
Probleemdefinitie
Probleemanalyse
Ontwerp van de interface: het uiterlijk van het formulier/scherm Omzetten van algoritme in computeropdrachten aan de hand van een programmeertaal
Testen
Welke verwerking nodig? Resultaat algoritme
Programmeren
Benodigde invoer Gewenste uitvoer
Grammaticale fouten Denkfouten (logische fouten)
Documentatie Implementatie (in werking stellen) Onderhouden
Controlestructuren in een (computer)algoritme
Bepalen de volgorde waarin opdrachten worden uitgevoerd. Elk algoritme kan worden geschreven gebruik makend van 3 controlestructuren: sequentie = opeenvolging (van opdrachten) selectie = keuze (tussen opdrachten) iteratie = herhaling (van opdrachten)
Een sequentie is een controlestructuur opgebouwd uit één of meer opdrachten die elkaar opvolgen. De volorde is belangrijk. Je mag geen deelalgoritmen van plaats verwisselen.
Een selectie is een basisstructuur die een keuze aangeeft tussen twee mogelijke sequenties, gekoppeld aan een voorwaarde.
Een iteratie is een controlestructuur die ervoor zorgt dat een bepaalde opdracht of een reeks opdrachten een aantal keer herhaald wordt.
