Algoritmen - broodje hagelslag

• Informatica
• Middelbare school
• vwo
• Leerjaar 5

Introductie

lgg

Algoritmen

• Je kan een gegeven oplossingsrichting voor een probleem weergeven als een algoritme,
  
• Je kan deze weergave structureren met een flowchart of in (pseudo)code

B1 - Leerdoelen

De leerling..

1. maakt kennis met eenvoudige algoritmen om kaarten te sorteren en getallen in een lijst te zoeken.
   
2. kan een algoritme wat schematisch is weergegeven lezen en/of interpreteren.
   
3. weet dat de efficiëntie van een algoritme bepaalt kan worden aan de hand van het best-, worst- en averagecasescenario.
   
4. kent de werking van de standaard sorteeralgoritmen BubbleSort, MergeSort en QuickSort.
   
5. weet in welke situatie één van deze algoritmen het beste toegepast kan worden.
   
6. kent de werking van het kortstepadalgoritme van Dijkstra.
   
7. weet dat niet alle problemen door een computer opgelost kunnen worden.
   
8. kent het spanningsveld tussen correctheid en efficiëntie van een algoritme.
   
9. weet wat brute force is.
   
10. kent de werking van klassieke problemen, zoals het rugzakprobleem, het handelsreizigersprobleem en het Chinese postbodeprobleem.

Komende weken

1. (B 1) t/m 1.8 -  Introductie - hagelslag (stukje herhaling, flowchats hebben we al gedaan)
2. (B 1) Zeeslag - binary search
3. (B 1) t/m 2.3 - Standaard algoritmen: bogo sort, bubble sort (kaarten sorteren), 
4. Sorteren met python
5. (B 1) t/m 2.6 - Standaard algoritmen: quick sort, merge sort, vergelijken sorts
6. (B 1) t/m 3.2 - Onoplosbare problemen: rugzakprobleem: klassikaal
7. (B 1) t/m 3.3 - Onoplosbare problemen: rugzakprobleem: klassikaal

GPW (SE) TOETS!

Algoritme: een definitie

"Een algoritme (van het Perzische woord Gaarazmi : خوارزمي naar de naam van de Perzische wiskundige Al-Chwarizmi محمد بن موسى الخوارزمي) is een eindige reeks instructies die vanuit een gegeven begintoestand naar een beoogd doel leidt"

https://en.wikipedia.org/wiki/Muhammad_ibn_Musa_al-Khwarizmi

Wie heeft er al eens een algoritme gemaakt?

1. Ik
2. Ik niet

Flowcharts: Galgje

Beschrijven: kaarten sorteren

Fase 1: Verdeel

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

Fase 2: Verzamel

1. De kaart met de kleinste waarde ligt nu bovenop de meest linker stapel. Pak die.
   
2. Pak nu steeds de topkaart met de kleinste waarde van de andere stapels.

Broodje hagelslag

Maak in groepjes van twee of drie een algoritme om een broodje hagelslag te smeren.

Aan de slag

Lezen 

Fundament: B1 - Algoritmen t/m 1.8

Maken 

1.3 vraag 1

1.4 vraag 5

1.5 vraag 1 en 2

1.7 vraag 3

Dit heb ik vandaag geleerd