Les 1 - Introductie algoritmen

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

Algoritmen

Een introductie

Leerdoel

Aan het eind van deze les weet je wat een algoritme is en kan je dit uitleggen aan de hand van een voorbeeld met het sorteren van kaarten, kan je uitleggen waarom je een algoritme het beste in een schema kan uitwerken en kan je bepalen of een algoritme goed of slecht is.

Wat is een algoritme?

Een algoritme is een verzameling instructies om een probleem op te lossen of een taak uit te voeren.

• data sorteren
• routes vinden
• online zoeken
• optimale spoorbezetting berekenen

Filmfragment Exact Instructions

Bekijk het filmfragment. Wat heeft deze video met een algoritme te maken?

Ehm... Wat is ook alweer een algoritme?

Een algoritme is een verzameling instructies om een probleem op te lossen of een taak uit te voeren.

Wat heeft deze video met algoritmes te maken?
Uit de video blijkt dat...

1. Bij het volgen van instructies duidelijkheid van belang is
2. Bij het volgen van instructies zorgvuldigheid van belang is
3. Bij het volgen van instructies de volgorde van belang is
4. Het opvolgen van instructies moeilijker is dan het lijkt

Filmfragment 1: kaarten sorteren

Bekijk het filmfragment. Bedenk waarom dit geen goed voorbeeld is van een algoritme.

Wat is ook alweer een algoritme?

Een algoritme is een verzameling instructies om een probleem op te lossen of een taak uit te voeren.

Sorteeralgoritme

Kaarten sorteren

Filmfragment 1: kaarten sorteren

Stappen die werden gevolgd:

1. Verdeel de kaarten over vier stapels. Voor elke kleur een aparte stapel.

2. Sorteer daarna per stapel de kaarten met de hand.

Zijn allebei de stappen duidelijk?

Zijn beide stappen duidelijk?

1. Stap 1 wel, stap 2 niet
2. Stap 2 wel, stap 1 niet
3. Stap 1 en 2 zijn beide duidelijk
4. Stap 1 en 2 zijn beide niet duidelijk

Filmfragment 1: kaarten sorteren

Stappen die werden gevolgd:

1. Verdeel de kaarten over vier stapels. Voor elke kleur een aparte stapel.

2. Sorteer daarna per stapel de kaarten met de hand.

Stap 1 is duidelijk

Stap 2 is niet duidelijk

Hoe ga je in stap 2 dan sorteren?

Eenduidigheid

Deze strategie uit het filmfragment is nog geen eenduidig algoritme. Dat is het pas als er in elke stap duidelijk is wat je moet doen en hoe je dat moet doen. Algoritmen die door een computer worden uitgevoerd, moeten altijd eenduidig zijn.

Filmfragment 2: verdeelfase

Het volgende filmfragment zal 2 keer worden afgespeeld. 

Probeer de eerste keer gewoon goed op te letten wat er gedaan wordt.

Probeer bij de tweede keer op te schrijven welke instructie(s) worden gevolgd.

sorteeralgoritme

verdeelfase

Filmfragment 2: verdeelfase

• Pak de eerste kaart en leg die zichtbaar op tafel. Dit wordt de eerste stapel.
• Pak de volgende kaart. Kijk of de kaart een grotere waarde heeft dan de kaart op de eerste stapel.
        - Zo ja, dan leg je de kaart rechts naast de eerste stapel. Dit wordt een nieuwe stapel.
        - Zo nee, dan leg je de kaart bovenop de eerste stapel.
• Doe voor alle volgende kaarten het volgende:
        - Zoek alle stapels waarvan de topkaart even groot is of groter dan de kaart
           die je vasthoudt.
        - Zijn die stapels er? Leg je kaart dan op de stapel met de kleinste topkaart.
        - Is je kaart groter dan alle topkaarten? Begin dan een nieuwe stapel aan
          de rechterkant.

A) Alleen rechts van de bestaande stapels kunnen nieuwe stapels gevormd worden
B) Het aantal stapels staat vanaf het begin vast

1. A is waar, B is niet waar
2. B is waar, A is niet waar
3. A en B zijn waar
4. A en B zijn niet waar

Schematiseren: duidelijk en overzichtelijk

Filmfragment 3: verzamelfase

Bekijk het fragment.

Schrijf uit wat het algoritme is van de verzamelfase.

Maak het bijbehorende schema van de verzamelfase.

Sorteeralgoritme

verzamelfase

Filmfragment 3: verzamelfase

Oplossing

Eenduidigheid

De video's laten een voorbeeld zien van een eenduidig algoritme. Bij elke stap weet je precies wat je moet doen. Daardoor zou een computer (bijvoorbeeld een robot) dit algoritme ook kunnen uitvoeren.

Je bent klaar met de verdeelfase (fase 2). Waar ligt nu de kaart met de laagste waarde?

1. Deze kaart kan overal liggen.
2. Deze kaart zal nu op de meest linker stapel liggen.
3. Deze kaart kan op alle stapels links van het midden liggen.
4. Deze kaart zal op de middelste stapel liggen.

Waarom ligt de kaart met de laagste waarde op de meest linker stapel?  

Omdat alle stapels gesorteerd zijn, zal de kleinste kaart bovenop één van de stapels liggen. Omdat de topkaarten gesorteerd zijn, zal de laagste kaart helemaal links liggen. De laagste kaart ligt dus bovenop de eerste stapel.

Wat is een goed algoritme?

• Het geeft een correcte oplossing
  
  
  
• Het is efficiënt

Efficiënt algoritme

•  Efficiëntie wordt bepaald door het aantal stappen
  
  
• De efficiëntie is afhankelijk van de situatie

Efficiëntie bepalen

Aan de hand van drie scenario's:

1. Bestcasescenario
   De beste situatie
2. Worstcasescenario
   De slechtste situatie
3. Averagecasescenario
   Een gemiddelde situatie

Voorbeeld

Stel, je moet een getal tussen de 1 en de 100 raden. 

Je krijgt alleen te horen of het getal groter, kleiner dan wel geraden is.

Hoe goed is een algoritme?

Hoger/ lager spelen

De drie scenario's

Stel dat je gewoon alle getallen op gaat noemen: 1, 2, 3, enz.

Bestcasescenario
1 is het bestcasescenario
Worstcasescenario
100 is het worstcasescenario
Averagecasescenario
Gemiddeld 50 keer raden

De drie scenario's

Stel dat je steeds middelste getal kiest

Bestcasescenario
het getal 50, die raad je in één keer

Worstcasescenario

50 - 25 - 13 - 7 - 4 - 2 - 1 (dus 7 keer raden)
Averagecasescenario
Moeilijk 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?  

Je halveert in elke stap het aantal getallen dat over is:
1000 – 500 – 250 – 125 – 63 – 32 – 16 – 8 – 4 – 2 – 1

dat is in 10 stappen. (Of: log2(1000) ≈ 9,97, dus 10 stappen)

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

Hoe vaak moet je maximaal raden voor een getal tussen de 1 en 1.000.000?  

Bedenk van te voren of je tijdens het halveren kiest voor afronden naar boven of naar beneden. (Bijvoorbeeld 15.625 ÷ 2 = 7.813 of 15.625 ÷ 2 = 7.812). Als je dit correct toepast dan kun je in maximaal 20 stappen (log2(1.000.000) ≈ 19,93) ieder getal tussen de 1 en de 1.000.000 raden.

Hieronder staat de rij uitgewerkt met afronden naar beneden:

1.000.000 – 500.000 – 250.000 – 125.000 – 62.500 – 31.250 – 15.625 – 7.812 – 3.906 – 1.953 – 976 – 488 – 244 – 122 – 61 – 30 – 15 – 7 – 3 – 1

Leerdoel gehaald?

Aan het eind van deze les weet je wat een algoritme is en kan je dit uitleggen aan de hand van een voorbeeld met het sorteren van kaarten, kan je uitleggen waarom je een algoritme het beste in een schema kan uitwerken en kan je bepalen of een algoritme goed of slecht is.

Wat is een algoritme?

Wat is het voordeel van het in een schema weergeven van een algoritme?

Wat maakt een algoritme een goed algoritme?

Hoe bepaal je de efficiëntie van een algoritme?