Modderdorp – Informatica Unplugged

De wereld van de informatica kent tal van problemen die alleen kunnen worden opgelost met slimme algoritmen. Welke oplossing bied jij voor het probleem van de burgemeester van Modderdorp?

De docent legt de leerlingen een probleem voor: hoe kun je met zo min mogelijk wegen alle huizen in Modderdorp met elkaar verbinden? De leerlingen denken na over een strategie om dit probleem op te lossen.

Voorbereiding: 10 minuten
Uitvoer: 20 minuten
Klas: 1 t/m 6

Voorbereiding

Zet de Powerpoint-presentatie klaar en print voor elk tweetal een werkblad uit.

In de les

Laat de leerlingen een afbeelding van Modderdorp zien en schets het probleem.

De burgemeester van Modderdorp wil graag dat alle bewoners elkaar kunnen bereiken zonder vieze voeten te krijgen. Daarvoor moeten sommige wegen worden geasfalteerd. Maar wel zo min mogelijk, want er moet ook geld overblijven voor een zwembad.

Maak tweetallen en zorg dat alle leerlingen een werkblad hebben. “Jullie hebben nu vier minuten om een oplossing voor dit probleem te vinden. Denk na over hoe je dit aanpakt. Ik ben benieuwd wie van jullie de beste oplossing kan vinden. Zorg dat jullie oplossing goed zichtbaar is op het werkblad.”

Als alle leerlingen weten wat ze te doen staat zeg je: “Jullie hebben vier minuten, veel succes!”

Als de vier minuten voorbij zijn bespreek je de resultaten van de leerlingen. Eerst bespreek je de oplossingen die de leerlingen hebben gevonden en hoeveel wegen hebben ze daarbij geasfalteerd. Optimale oplossingen leiden tot 23 blokjes die moeten worden geasfalteerd.

Maar belangrijker nog, welke aanpak hebben de leerlingen gekozen? Vraag leerlingen hierover en probeer dit steeds te herleiden tot een generieke aanpak die ook gebruikt kan worden bij andere modderdorpen, die er dus anders uitzien.

Vervolgens kun je twee bekende algoritmen toelichten. Beide algoritmes leiden altijd tot optimale oplossingen. Dat wil dus zeggen dat er geen goedkopere oplossing mogelijk is. De eerste aanpak is om de dure wegen te elimineren.

De tweede aanpak is om steeds goedkope wegen te asfalteren.

(Dat tweede algoritme staat bekend als Kruskal’s algoritme. Een ander bekend algoritme dat ook uitgaat van het aanleggen van goedkope wegen staat beken als Prim’s algoritme. Dat algoritme wordt hier niet behandeld.)

Aan de hand van de Powerpoint-presentatie kun je laten zien hoe je het modderdorp kunt weergeven als een graaf, bestaande uit knooppunten en lijnen.

Je kunt het hierbij laten. Je kunt de leerlingen ook nog laten oefenen met deze algoritmes. De figuren staan op de achterkant van het werkblad.

Na deze oefening bespreek je het belang hiervan.

Het modderdorp bevat maar een paar knopen en lijnen, maar als het aantal knopen en lijnen toeneemt, hebben sommige algoritmen vrij veel tijd nodig. Het is dus belangrijk slimme algoritmen te vinden en daarbij te letten op de efficiëntie van deze algoritmen.

Materialen

Modderdorp_werkblad

Powerpoint-presentatie met de instructie en toelichting.

Achtergrond bij deze werkvorm

Zie voor meer interessant lesmateriaal hierover:

http://www.csfieldguide.org.nz/en/chapters/complexity-tractability.html

Relatie met het nieuwe examenprogramma informatica