# Domein B — Grondslagen ## B1.1 Algoritmen Van probleem naar **eenduidige stappen** --- ## Lesdoelen Na deze les kun je: - eenvoudige **algoritmen** voor sorteren en zoeken herkennen; - een schematisch weergegeven algoritme lezen en interpreteren; - de efficiëntie vergelijken met **bestcase**, **worstcase** en **averagecase**. > Kernbegrippen: **algoritme · efficiëntie · bestcase · worstcase · averagecase** --- ## Lesplanning 1. **Periode 2 introdutie:** wat gaan we doen? (5 min) 2. **Introductie:** wat is een algoritme? (2 min) 2. **Praktijkopdracht:** UNO-kaarten sorteren (5-10 min) 3. **Bespreken:** Lesstof lesdoelen (10 min) 6. **Aan de slag:** Fundament B1.1 (ong. 20-30 min) 7. **Afsluiting:** check jezelf en de lesdoelen (5 min) --- ## Eerst even kijken <iframe width="800" height="450" src="https://www.youtube.com/embed/ynJDhXnfmy4" title="Video" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen></iframe> --- ## Wat is een algoritme? | | | |---|---| | Een **algoritme** is een verzameling instructies om een probleem op te lossen of een taak uit te voeren.<br><br>Voorbeelden:<br>- data sorteren<br>- een route vinden<br>- online zoeken |  | > Elke stap moet **precies en eenduidig** zijn. --- ## Opdracht: kaarten sorteren Leg de **UNO-kaarten op de kop** op tafel. - Je mag per stap maximaal **2 kaarten omdraaien**. - Daarna leg je de kaarten weer op de kop. - Je mag **niet onthouden** welke waarde andere kaarten hadden. - Bedenk een vaste werkwijze waarmee je de kaarten toch kunt sorteren. > Welke stappen moet je steeds herhalen?  <!-- .element: style="width: 30%;" --> --- ## Wanneer is het géén goed algoritme? Bijvoorbeeld: 1. Verdeel de kaarten over vier stapels, één per kleur. 2. Sorteer daarna iedere stapel. Het probleem zit in stap 2: **hoe** moet er worden gesorteerd? > Een computer kan geen ontbrekende stappen zelf invullen. --- ## Van woorden naar vaste stappen **Fase 1 — verdeel** - Pak de eerste kaart: dit wordt de eerste stapel. - Vergelijk elke volgende kaart met de **topkaart** van de stapels. - Leg de kaart op de stapel met de kleinste topkaart die even groot of groter is. - Is de kaart groter dan alle topkaarten? Maak rechts een nieuwe stapel. --- ## Daarna: verzamelen **Fase 2 — verzamel** - Kies steeds de kleinste **topkaart**. - Neem die kaart van de stapel. - Herhaal totdat alle kaarten verzameld zijn. > Zo wordt “sorteer de kaarten” een reeks uitvoerbare stappen. --- ## Een algoritme als schema Een schema maakt de volgorde en beslissingen zichtbaar.  <!-- .element: style="width: 72%;" --> > Kun je aanwijzen waar het algoritme een **keuze** maakt? --- ## Wanneer is een algoritme goed? Een algoritme moet: - een **correcte oplossing** geven; - zo **efficiënt** mogelijk werken. Efficiëntie kun je onder andere bekijken via: - het **aantal stappen**; - de hoeveelheid benodigd **geheugen**. --- ## Drie scenario’s | | | |---|---| | **Bestcase**<br>de gunstigste situatie<br><br>**Worstcase**<br>de ongunstigste situatie<br><br>**Averagecase**<br>een gemiddelde situatie |  <!-- .element: style="width: 52%;" --> | > Hetzelfde algoritme kan per situatie een ander aantal stappen nodig hebben. --- ## Raad het getal Iemand kiest een getal van **1 t/m 100**. Je hoort na iedere gok alleen: - **groter**; - **kleiner**; - **goed geraden**. !!!vraag open Welke strategie gebruik jij om het getal met zo weinig mogelijk pogingen te raden? !!! --- ## Strategie 1 — vanaf 1 tellen Je gokt: **1, 2, 3, 4, ...** - **Bestcase:** 1 poging - **Worstcase:** 100 pogingen - **Averagecase:** ongeveer 50 pogingen > Correct? **Ja.** Efficiënt? **Niet erg.** --- ## Strategie 2 — steeds halveren Begin in het midden: **50**. - Groter? Zoek verder tussen 50 en 100. - Kleiner? Zoek verder tussen 1 en 50. - Kies daarna opnieuw het midden. Zo valt na iedere stap ongeveer **de helft** van de mogelijkheden af. --- ## Hoeveel stappen scheelt dat? Bij steeds halveren: **100 → 50 → 25 → 13 → 7 → 4 → 2 → 1** - **Bestcase:** 1 poging - **Worstcase:** maximaal 7 pogingen - **Averagecase:** lastiger exact te bepalen > Een ander algoritme kan hetzelfde probleem veel efficiënter oplossen. --- ## Efficiëntie is meer dan snelheid Het aantal stappen is belangrijk, maar niet het enige. Ook het benodigde **geheugen** telt mee.  <!-- .element: style="width: 45%;" --> --- ## Check jezelf !!!vraag mc Welk antwoord beschrijft een goed algoritme het best? - Het werkt alleen in het bestcasescenario. - De stappen zijn precies en eenduidig en leveren een correcte oplossing. - Het is een stappenplan die heel efficient is. - Het bestaat altijd uit zo weinig mogelijk regels tekst. !!! --- ## Afsluiting Kun je nu uitleggen: 1. wat een **algoritme** is? 2. waarom stappen **eenduidig** moeten zijn? 3. wat **bestcase**, **worstcase** en **averagecase** betekenen? 4. waarom twee correcte algoritmen toch verschillend **efficiënt** kunnen zijn?