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 was 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 of dit een goed voorbeeld is van een algoritme.

Wat was 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

Is dit een goed voorbeeld van een algoritme?

Laten we het per stap bekijken, de stappen die werden gevolgd zijn:

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

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

Zijn allebei de stappen duidelijk (eenduidig)?

Zijn allebei de stappen duidelijk (eenduidig)?

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 4 stapels. Voor elke kleur een aparte stapel.

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

Stap 1 is duidelijk, maar stap 2 is niet duidelijk (eenduidig).

Hoe ga je in stap 2 dan sorteren?

Eenduidigheid

Deze strategie uit het filmfragment is 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, anders kan de computer ze niet uitvoeren.

Filmfragment 2: verdeelfase

Bekijk het fragment. 

Probeer 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, leg dan 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.

Schematiseren: duidelijk en overzichtelijk

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

Filmfragment 3: verzamelfase

Bekijk het fragment.

Schrijf uit wat het algoritme is van de verzamelfase en maak daarna het bijbehorende schema.

Sorteeralgoritme

verzamelfase

Filmfragment 3: verzamelfase

Oplossing

Eenduidigheid

De video's 2 en 3 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.

Stel je bent klaar met de verdeelfase. 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

Wanneer is een algoritme efficiënt?

•  Efficiëntie wordt bepaald door het aantal stappen (minder is beter)
  
• De efficiëntie is afhankelijk van de situatie (niet elk probleem is even efficiënt op te lossen)

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 pak je dit aan?

Een strategie is om alle getallen op te gaan noemen: 1, 2, 3, enz. 

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

Hoeveel stappen heb je nodig voor het bestcasescenario?

1. 1
2. 7
3. 50
4. 100

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

Hoeveel stappen heb je nodig voor het worstcasescenario?

1. 1
2. 7
3. 50
4. 100

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

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.

Wat zou een betere betere (efficiëntere) strategie zijn?

Hoe goed is een algoritme?

Hoger/ lager spelen

Stel dat je steeds middelste getal kiest (als in het voorbeeld)

Hoeveel stappen heb je nodig voor het bestcasescenario?

1. 1
2. 7
3. 50
4. 100

Stel dat je steeds middelste getal kiest (als in het voorbeeld)

Hoeveel stappen heb je nodig voor het worstcasescenario?

1. 1
2. 7
3. 50
4. 100

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 wanneer je het snelle algoritme gebruikt?

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 wanneer je het snelle algoritme gebruikt?

1. 10
2. 20
3. 30
4. 1.000.000

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 naar boven of naar beneden afrondt. (Bijvoorbeeld 61 ÷ 2 = 31 of 61 ÷ 2 = 30). Als je dit correct (consequent) 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.

Doornemen

LessonUp

Les 1 - Introductie algoritmen

Fundament 

B: Grondslagen -> Algoritmen (B1) -> 1. Algoritmen (helemaal)

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?