Les 1 - Algoritmen

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

Algoritmen

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.

Voorbeelden

data sorteren

routes vinden

online zoeken

optimale spoorbezetting berekenen

Filmfragment 1

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.

kaarten sorteren

Filmfragment 1

Stappen die werden gevolgd:

1. Verdeel de kaarten eerst 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

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

• 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.

Schematiseren

Filmfragment 3

Bekijk het fragment.

Schrijf uit wat het algoritme is van de verzamelfase.

Maak het bijbehorende schema van de verzamelfase.

Wat is een goed algoritme?

• Het geeft een correct 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 slechste 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.

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.

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?