Algoritme les 4

• Informatica
• Middelbare school
• havo, vwo
• Leerjaar 4

Aan het eind van deze les

• kan je verschillende  algoritmes benoemen
  
• Begrijp je het verschil tussen verschillende algoritmes
• weet je waar je bepaalde algoritmes voor gebruikt
• heb je zelf verschillende strategieën gebruikt
  

vorige keer

• bubble sort
• selection sort
• merge sort
• insertion sort
• heap sort
• quick sort
  

Je wilt een algoritme dat goed werkt. Maar hoe kun je beoordelen of een algoritme 'goed' is?

Er zijn veel factoren die bepalen of een algoritme goed is.

Eén van de belangrijkste is het aantal stappen dat je moet doorlopen om tot een oplossing te komen

Iemand neemt een getal tussen de 1 en de 100 in gedachten. Jij moet raden welk getal dat is. Je mag zo vaak raden als je wilt. Je tegenspeler mag steeds maar één van drie antwoorden geven:

Het getal is groter,
het getal is kleiner,
je hebt het geraden.

• Maak groepen van 3
• 1 kiest een getal onder de 100
• 1 schrijft op hoe vaak er geraden moet worden
• 1 probeert het getal te raden

Welke aanpak heb je gekozen om snel het getal te raden?

Hoe vaak moest je met jouw aanpak maximaal raden om het getal tussen de 1 en de 100 te vinden?

De efficiëntie van een algoritme bepaal je aan de hand van het aantal stappen dat nodig is om tot een oplossing te komen. Hoe minder stappen nodig zijn, hoe efficiënter een algoritme is. Het heeft de oplossing dan sneller gevonden.

Er zijn drie scenario's om de efficiëntie van een algoritme te bepalen:

• Bestcasescenario (het beste),
• worstcasescenario (het slechtste),
• averagecasescenario (het gemiddelde)

voorbeeld

Stel dat je net bij het raden alle getallen één voor één opnoemt. Je raadt dan eerst 1, dan 2, dan 3, enzovoort.

Bestcasescenario: je moet één keer raden. Dat gebeurt als je tegenspeler het getal 1 in gedachten heeft.
Worstcasescenario: je moet 100 keer raden. Dat gebeurt als je tegenspeler het getal 100 in gedachten heeft.
Averagecasescenario: je moet gemiddeld 50 keer raden.

50 keer raden om een getal tussen 1 en 100 te vinden is erg veel. Er bestaan snellere manieren.

Bijvoorbeeld:

Kies het middelste getal tussen 1 en 100. Dat is 50.

Als je tegenspeler 'het is groter' zegt, kies je het middelste getal tussen 50 en 100. Dat is 75.
Als je tegenspeler 'het is kleiner' zegt, kies je het middelste getal tussen 1 en 50. Dat is 25.
Ga zo door totdat je het juiste getal hebt geraden.

Voor dit algoritme is het bestcasescenario dat je maar één keer hoeft te raden.

Dat gebeurt als je tegenspeler het getal 50 heeft gekozen.

In het worstcasescenario vind je het getal in 7 keer raden.

Dat zit zo. Bij elke stap sluit je de helft van de getallen uit. Na de eerste stap zijn er nog 50 getallen over om te raden. Na de tweede stap zijn er nog 25 getallen over om te raden, enzovoort. Na 7 stappen is er nog maar één getal over om te raden.

Het averagecasescenario is voor dit algoritme lastig te bepalen.

Als het aantal getallen waaruit je mag raden toeneemt, stijgt het aantal keer dat je moet raden niet heel erg.
Hoe vaak moet je maximaal raden voor een getal tussen de 1 en 1.000?

1. 10
2. 100
3. 500
4. 1000

Hoe vaak moet je maximaal raden voor een getal tussen de 1 en 1.000.000? Leg uit waarom.

Iemand neemt een getal tussen de 1 en de 60 in gedachten. Jij moet raden welk getal dat is. Je gebruikt daarbij het hierboven beschreven snellere algoritme.

Welk getal hoort bij het bestcasescenario?

1. 29
2. 30
3. 60
4. 61

In hoeveel stappen raad je het getal in een worstcasescenario?

1. 6
2. 15
3. 30
4. 60

Selecteer alle getallen die horen bij een worstcasescenario.

1. 1
2. 29
3. 60
4. 15

Je bent op zoek naar de betekenis van een woord. Je gebruikt hierbij de dikke Van Dale, die 1000 bladzijdes telt.

Beschrijf een snel algoritme om de juiste bladzijde te vinden waarop het woord staat dat je zoekt.

Je zoekt nogmaals naar de betekenis van een woord. Ook nu gebruik je de dikke Van Dale, die 1000 bladzijdes telt. Dit keer gebruik je als algoritme het zoekalgoritme die we net besproken hebben.

Na het zoeken blijkt dat het woord dat je zocht op de eerste bladzijde stond. Welke bladzijden heb je allemaal bekeken om tot deze conclusie te komen?

oplossing

Begin bij bladzijde 500. Hier vind je het woord 'luchtdicht'. 'Aalmoes' staat eerder.
Je zoekt verder op bladzijde 250. Hier vind je het woord 'feminisme'. 'Aalmoes' staat eerder.
Je zoekt verder op bladzijde 125. Hier vind je het woord 'brak'. 'Aalmoes' staat eerder.

Je zoekt verder op bladzijde 63. Hier vind je het woord 'balsemen'. 'Aalmoes' staat eerder.

Je zoekt verder op bladzijde 32. Hier vind je het woord 'antiglobalist'. 'Aalmoes' staat eerder.
Je zoekt verder op bladzijde 16. Hier vind je het woord 'aardkunde'. 'Aalmoes' staat eerder.
Je zoekt verder op bladzijde 8. Hier vind je het woord 'aanvallen'. 'Aalmoes' staat eerder.
Je zoekt verder op bladzijde 4. Hier vind je het woord 'aanleiding'. 'Aalmoes' staat eerder.
Je zoekt verder op bladzijde 2. Hier vind je het woord 'aanbevelingsbrief'. 'Aalmoes' staat eerder.
Je zoekt verder op bladzijde 1. Hier vind je het woord 'aalmoes'!

In het voorbeeld van het raden van het juiste getal was het gemakkelijk om het aantal stappen te bepalen.

Maar hoe zit dat bij de algoritmen voor het sorteren van kaarten?

En wanneer kun je een algoritme eigenlijk efficiënt noemen?

Alleen het bepalen van het aantal benodigde stappen is daarvoor niet voldoende.

Bij computers is bijvoorbeeld ook het benodigde geheugen belangrijk.

Denk weer aan het algoritme voor het raden van het juiste getal.

Stel dat je ervoor kiest om alle onjuiste getallen op aparte briefjes te schrijven. Dan zou je daar erg veel briefjes voor nodig hebben.

Een computer kan die getallen vrij gemakkelijk in het geheugen opslaan. Maar dat is niet efficiënt.

Het is voldoende om te onthouden tussen welke grenzen het juiste getal zit. Dan hoeft de computer maar twee getallen op te slaan in het geheugen.

Na deze les, 

wil ik...

de uitleg nog 1 keer horen

meer voorbeelden krijgen

meer oefeningen maken

de leerstof thuis nog even bekijken

overgaan naar nieuwe leerstof

nog meer te weten komen over de leerstof

niet meer te weten komen over de leerstof

Hoe vond je 

deze les?

😒🙁😐🙂😃