Sorteren met kaarten

Sorteer de kaarten, hoe pak je dat aan? Leerlingen zeggen al gauw: maar dan zie je toch gelijk, wat de juiste volgorde is? Daarom voegen we wat restricties toe om het perspectief van de computer helder te maken.

Leerlingen werken in groepjes van drie en bedenken een algoritme om een set kaarten te sorteren. Dit algoritme spelen ze na, waarbij ze alleen de mogelijkheid hebben om steeds twee kaarten te vergelijken. Ze ontdekken dat er meerdere manieren zijn om een probleem op te lossen (sorteren in dit geval) en dat deze manieren kunnen verschillen in efficiency. Ze maken kennis met stroomdiagrammen.

  • Voorbereiding: 10 minuten
  • Uitvoer: 25 – 50 minuten (afhankelijk van gebruik van verdieping)
  • Klas: 1 t/m 6

Voorbereiding

Zorg voor voldoende spelkaarten. Elke groep van drie leerlingen heeft een setje speelkaarten van negen kaarten nodig, bijvoorbeeld 2 t/m 10 van schoppen.

Er zijn vier dubbelzijdige werkbladen. Zorg ervoor dat ieder groepje in ieder geval kan beschikken over het eerste werkblad. De overige werkbladen hoeven niet in volgorde te worden gemaakt. Het ene groepje kan dus aan de slag met werkblad II en het andere met werkblad III of IV.

Zet de PowerPoint-presentatie klaar.

In de les

Deze activiteit bestaat uit meerdere fasen.

Introductie: (5 min)

Vraag de leerlingen wanneer computers gegevens sorteren. Mogelijk antwoorden zijn: in Excel kun je gegevens laten sorteren; gegevens op alfabetische volgorde zetten; in een webwinkel producten sorteren op prijs. Een lijst van tien namen sorteren gaat nog wel. Maar daarna is het niet leuk meer. Computers kunnen gelukkig heel goed sorteren. Maar hoe doen ze dat precies?

“Jullie gaan vandaag ontdekken hoe een computer gegevens kan sorteren, en ook: hoe dat op een slimme manier kan. Aan het eind van de les kan iedereen een methode beschrijven waarmee dat kan.”

Geef aan wat het doel is en hoe het sorteren werkt, met behulp van de Powerpoint-presentatie.

Je kunt het voorbeeld van Bogo-sort laten zien, een erg inefficiënte methode.

Oefening I (12 min)

“Jullie hebben nu 12 minuten om zelf een manier te bedenken. Na die 12 minuten gaan we het bespreken. Je mag niet overleggen met andere groepjes. Gebruik het werkblad en zorg dat je de vragen op het werkblad invult. Als je eerder klaar bent krijg je van mij een tweede werkblad. Zijn er nog vragen?”

Als het helder is voor iedereen zeg je: “Veel succes!”

Als een groepje eerder klaar is kun je ze één van de andere werkbladen geven (2, 3, of 4).

Bespreking (7 min)

Bespreek na 12 minuten de resultaten met elkaar. Vraag hoeveel vergelijkingen ieder groepje nodig heeft. Vraag het groepje met de minste vergelijkingen om hun aanpak kort toe te lichten.

Je kunt vervolgens toelichten dat er dus meerdere manieren om een probleem zoals sorteren op te lossen. Zo’n aanpak heet een algoritme. Er zijn dus meerdere algoritmes voor het sorteren van gegevens. Algoritmes kunnen verschillen in efficiency. Ze leiden niet allemaal tot hetzelfde aantal vergelijkingen. Dat is belangrijk, want computers werken vaak niet met tien gegevens, maar het miljoenen gegevens. Dan is het belangrijk om een efficiënt algoritme te hebben.

Verdieping (15 minuten)

Je kunt het hierbij laten, maar je kunt ook verder gaan. De leerlingen gaan dan ieder een aanpak uitproberen aan de hand van de andere werkbladen. Er zijn drie verschillende aanpakken beschreven (werkblad II, III, en IV). Geef iedere groep een ander werkblad, zodat alle werkbladen (II, III, en IV) worden uitgevoerd.

“Lees de aanpak in het werkblad en voer het uit. Beantwoord de vragen. Hiervoor heb je weer 12 minuten.  Je mag niet overleggen met andere groepjes. Zorg dat je de vragen op het werkblad invult. Als je eerder klaar bent krijg je van mij een nieuw werkblad. Na die tien minuten gaan we afsluiten. Veel succes!”

Afsluitende bespreking (10 min)

Vraag naar het aantal vergelijkingen en schrijf die op het bord. Het gaat er niet om per se alle getallen in te vullen, maar vooral om te zien dat er verschillen ontstaan. We maken nog geen onderscheid tussen het gemiddelde scenario en slechtste scenario (worst-case). Hoewel het wel kan zijn dat leerlingen hier opmerkingen over maken.

“Vandaag hebben jullie geleerd hoe je een sorteeralgoritme kunt maken.”

Sluit af met de belangrijkste begrippen.

Varianten

  • Het is ook mogelijk om de groepjes elkaars uitwerkingen te laten testen. Dan blijkt hoe belangrijk het is om de algoritmen heel precies en eenduidig te beschrijven.
  • Laat leerlingen die werkblad II doen hun algoritme (bubble sort) vergelijken met het algoritme van een groepje met werkblad IV (insertion sort) en stel de vraag welke van de twee algoritmen sneller is. Dat hangt namelijk van de situatie af, oftewel: hoe de kaarten aan het begin gerangschikt zijn.

Materialen

Elke groep van drie leerlingen heeft een setje speelkaarten van negen kaarten nodig, bijvoorbeeld 2 t/m 10 van schoppen.

Sorteren met kaarten – werkblad

Powerpoint-presentatie met de instructie en toelichting.

Achtergrond bij deze werkvorm

Het doel van deze activiteit is om leerlingen kennis te laten maken met algoritmen, zonder bezig te zijn met de details van het programmeren. Ze ontdekken dat het belangrijk is om een algoritme zo precies mogelijk te beschrijven.  Belangrijke termen zijn:

  • Algoritme: een stappenplan om een probleem op te lossen
  • Efficiency: in hoeverre werkt een algoritme snel. In dit geval gaat het om de relatie tussen het aantal gegevens (specifiek: het aantal speelkaarten) en het aantal stappen dat wordt uitgevoerd bij het volgen van het algoritme (specifiek: het aantal vergelijkingen).
  • Stroomdiagram: een visuele weergave van een algoritme.

Als het gaat om efficiency, het is nog best lastig om te bepalen hoeveel vergelijkingen gemiddeld nodig zijn. Belangrijkste is dat de leerlingen beseffen dat er verschillen kunnen optreden in algoritmes.

Hierbij enkele heldere instructiefilmpjes die laten zien hoe verschillende sorteeralgoritmen:

Relatie met het nieuwe examenprogramma informatica

  • Subdomein: Subdomein B1: Algoritmen (Grondslagen)

Zie: http://www.slo.nl/organisatie/recentepublicaties/adviesinformatica/

Relatie met Digitale Geletterdheid

  • Computational Thinking – Algoritmes en procedures

Zie: https://www.kennisnet.nl/publicaties/werken-aan-digitale-geletterdheid-van-visie-naar-praktijk/#c1036

Licentie

Creative Commons-Licentie
Dit werk valt onder een Creative Commons Naamsvermelding-GelijkDelen 4.0 Internationaal-licentie.