Les 1 en 2 - Introductie algoritmen en tijdsefficiëntie

• New lesson editor
• Informatica
• Middelbare school
• havo, vwo
• Leerjaar 4-6

Algoritmes

Een introductie

Leerdoel

Aan het eind van deze les weet je wat een algoritme is en kan je dit uitleggen aan de hand van het model met kaarten tellen (de processor en het geheugen). Ook kan je een algoritme visualiseren in een stroomdiagram en bepalen of een algoritme voldoet aan de eisen van eenduidigheid, correctheid en efficiëntie.

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

A

Bij het volgen van instructies duidelijkheid van belang is

B

Bij het volgen van instructies zorgvuldigheid van belang is

C

Bij het volgen van instructies de volgorde van belang is

D

Het opvolgen van instructies moeilijker is dan het lijkt

Eenduidigheid

De strategie van de kinderen 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.

Wanneer het kind instrueert: "doe de pindakaas op het brood", zet de vader de gesloten pot op het brood. Waarom is deze instructie geen eenduidig algoritme?

A

Het kind geeft de instructies in de verkeerde volgorde.

B

Er is niet exact omschreven wat en hoe je de tussenstappen moet uitvoeren.

C

De instructie is in spreektaal geformuleerd in plaats van in een programmeertaal.

D

Er ontbreekt een voorwaarde (beslissing) om te controleren of het brood al gesmeerd is.

Tellen met kaarten

We gaan een aantal standaard algoritmen bekijken om deze eenduidigheid te demonstreren.

Eenduidigheid

De werkvorm met de kaarten laat voorbeelden zien van een eenduidig algoritme. Bij elke stap weet je precies wat je moet doen. Daardoor kan een computer (bijvoorbeeld een robot) dit algoritme ook uitvoeren.

Wat is een goed algoritme?

• Het geeft een correcte oplossing

• Het is efficiënt

Leerdoel gehaald?

Aan het eind van deze les weet je wat een algoritme is en kan je dit uitleggen aan de hand van het model met kaarten tellen (de processor en het geheugen). Ook kan je een algoritme visualiseren in een stroomdiagram en bepalen of een algoritme voldoet aan de eisen van eenduidigheid, correctheid en efficiëntie.

Doornemen en maken

Informatica Baas -> Grondslagen -> Algoritmen 

2.1 Introductie

2.2 Wat is een algoritme - t/m 2.2.2

Algoritmes

Verdeel en Heers
Over tijdsefficiëntie

Leerdoel

Aan het eind van deze les begrijp je het verschil tussen lineair zoeken O(n) en binair zoeken O(log n) aan de hand van het getallenraadspel. Je kunt uitleggen hoe de verdeel-en-heers-strategie werkt, waarom een lijst gesorteerd moet zijn, en hoe een gedistribueerd algoritme (zoals Slim tellen) groepen razendsnel kan verwerken door slim te halveren.

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?

A

1

B

7

C

50

D

100

Stel dat je gewoon alle getallen op gaat noemen: 1, 2, 3, enz. Hoeveel stappen heb je nodig voor het worstcasescenario?

A

1

B

7

C

50

D

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

Efficiëntie (Lineaire complexiteit)

We moeten bij deze strategie elk getal één voor één afgaan. Zoals eerder gezien noemen we dit een lineaire complexiteit O(​n): als we van het raadspel 200 getallen maken, heeft de computer in het ergste geval ook twee keer zoveel stappen nodig. Kun je nagaan wat er gebeurt bij een raadspel van 1000 getallen.

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 het middelste getal kiest (als in het voorbeeld)

Hoeveel stappen heb je nodig voor het bestcasescenario?

A

1

B

7

C

50

D

100

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

Hoeveel stappen heb je nodig voor het worstcasescenario?

A

1

B

7

C

50

D

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. Schat eens hoe vaak moet je maximaal moet raden voor een getal tussen de 1 en 1.000 wanneer je het snelle algoritme gebruikt?

A

10

B

100

C

500

D

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)

Efficiëntie (Logaritmische complexiteit)

Bij deze nieuwere strategie wordt het aantal getallen elke ronde gehalveerd. Hierdoor groeit het aantal stappen niet lineair, maar logaritmisch (met grondtal 2). Elke keer dat we de groep verdubbelen, kost dat het algoritme slechts 1 extra stap! Dit noemen we een logaritmische (of binaire) tijdscomplexiteit: O(log n).

Hoe vaak moet je maximaal raden voor een getal tussen de 1 en 1.000.000 wanneer je het snelle algoritme gebruikt?

A

10

B

20

C

30

D

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

Slim tellen

Laten we nog een werkvorm doen om het belang van tijdsefficiëntie te demonstreren.

Leerdoel gehaald?

Aan het eind van deze les begrijp je het verschil tussen lineair zoeken O(n) en binair zoeken O(log n) aan de hand van het getallenraadspel. Je kunt uitleggen hoe de verdeel-en-heers-strategie werkt, waarom een lijst gesorteerd moet zijn, en hoe een gedistribueerd algoritme (zoals Slim tellen) groepen razendsnel kan verwerken door slim te halveren.

Doornemen en maken

Informatica Baas -> Grondslagen -> Algoritmen 

2.2 Wanneer is een algoritme efficiënt (en waarom maakt dit uit)?