Activiteit 6
Waar gaat activiteit 6 over?
Computers slaan een hoop informatie op, maar ze moeten hier ook weer snel doorheen kunnen om het juiste te vinden. Een van de grootste zoekproblemen in de wereld wordt aan internetzoekmachines gevraagd, zij moeten miljarden webpagina’s doorzoeken in een fractie van een seconde. De data die aan de computer zijn gevraagd om te gaan zoeken, zoals een woord, een barcode of de naam van een auteur, heet een “zoeksleutel”.
Computers kunnen heel snel door informatie heen en je zou misschien denken dat ze gewoon aan het begin van de harde schijf of het internet beginnen en dan blijven zoeken tot ze het juiste gevonden hebben. Dit is wat je doet in het lineaire zoekspel. Maar deze methode is heel traag, zelfs voor computers. Neem bijvoorbeeld een supe
rmarkt die 10.000 verschillende producten in de schappen heeft staan. Wanneer er een barcode wordt gescand bij de kassa moet de computer door 10.000 nummers om het product en de bijbehorende prijs te vinden. Zelfs als het maar een duizendste van een seconde duurt om iedere code te checken, kost het toch tien seconden om door de hele lijst te gaan. Hoe lang zou je dan met een kar vol bij de kassa staan?
Een betere strategie voor het oplossen van het probleem is de binaire zoekmethode. In deze methode worden de getallen op volgorde gezet en door naar het middelste getal te kijken, weet je meteen in welke helft je verder moet zoeken. Dit proces wordt herhaald tot het product gevonden is. Terug naar de supermarkt, de 10.000 producten kunnen nu doorzocht worden met 14 pogingen, wat misschien tweehonderdste van een seconde duurt, daar merk je ook met een volle kar niks van.
De derde strategie om data te vinden heet “groeperen” of “hashing”. De informatie wordt gegroepeerd opgeslagen volgens van tevoren bepaalde methode. Bij het zoeken wordt de zoeksleutel aangepast om de groep (dus de locatie) te vinden. Bijvoorbeeld, als de zoeksleutel een telefoonnummer is, kan je alle cijfers van het nummer optellen de uitkomst vervolgens door elf delen en dan neem je het restgetal; de computer hoeft nu nog alleen maar te zoeken op de locatie van dit laatste getal om daar de juiste gegevens te vinden.
Op dit punt is de groepeersleutel een beetje als de controlegetallen uit activiteit 4 – de magische kaartentruc – een klein stukje informatie wordt toegevoegd (een groepsnummer) die bepaalt waar de data opgeslagen worden. Gewoonlijk vindt de computer dan vrijwel direct de informatie waar hij naar zoekt. Er is maar een hele kleine kans dat verschillende sleutels de computer naar dezelfde plek leiden en de computer dan alsnog door een hele hoop informatie heen moet om de juiste informatie te vinden.
Computerdeskundigen gebruiken vaak een of andere variant van de groeperingsstrategie bij het zoeken; alleen als het heel belangrijk is dat de data op volgorde blijven is deze methode niet handig. Het is ook niet slim om deze methode te gebruiken als een zeldzaam langzame reactie van de computer (in het geval dat er zich heleboel items in de groep bevinden) uit den boze is. Dit kan bij deze methode af en toe gebeuren.
Geschikt voor leeftijd: 9 jaar en ouder
Hele pdf van deze activiteit (staat ook in het boek): activiteit06.pdf
De losse werkbladen:
werkblad_slagschepen_extra.pdf