Samenvatting Informatica – Fundament – 5 VWO – B1 Algoritmen

Joël Smit | 5V.in1


Informatica – B Grondslagen – B1 Algoritmen
B1.1 Algoritmen
B1.1.1 Inleiding
Algoritmen zijn overal
Algoritme is manier waarop je iets doet  Proberen zo efficiënt mogelijk iets te doen  Algoritmen
kom je overal tegen, vooral in informatica  Vormen basis van alle software


Algoritmen in de informatica
In informatica: Algoritme = Verzameling instructies die computer uitvoert  Daardoor lost computer
probleem op of voert het complexe taak uit  Worden veel gebruikt, bv:
 Korstepadalgoritme  Navigatiesysteem  Bv. Google Maps
 Sorteeralgoritme  Webshops voor producten weergeven van laagste naar hoogste prijs


Complexe algoritmen
Sommige algoritmen zijn best ingewikkeld  Bv. zoekalgoritme dat Google gebruikt om snel iets te
vinden op internet
Er zijn heel eenvoudige problemen die niet of nauwelijks met een algoritme opgelost kunnen worden


B1.1.2 Kaarten sorteren
Veel manieren om kaarten te sorteren zijn best snel  Voor mensen geldt dat snelheid vooral
afhangt van vingervlugheid
Om te vergelijken gaat het vaak niet om wie het snelst qua tijd is  Handelingen tellen  Methode
waarvoor minste handelingen nodig is, is het snelst


B1.1.3 Sorteeralgoritme
Video: kaarten sorteren
Manier om kaarten te sorteren:
1. Verdeel kaarten over 4 stapels  Voor elke kleur aparte stapel
2. Sorteer daarna per stapel de kaarten op waarde
Stap 1 is duidelijk hoe het moet, maar stap 2 is niet helemaal duidelijk  Er zijn verschillende
manieren om stapel kaarten te sorteren  Strategie is dus nog geen eenduidig algoritme
Algoritmen die door computer worden uitgevoerd, moeten altijd eenduidig zijn  In elke stap moet
duidelijk zijn wat je moet doen en hoe je dat moet doen


Algoritme uitschrijven
Fase 1: Verdeelfase
1. Pak eerste kaart en leg deze op tafel
2. Doe voor alle volgende kaarten het volgende: Zoek alle stapels waarvan de topkaart even
groot is of groter dan de kaart die je vasthoudt
a. Zijn die er  Leg de kaart op de stapel met de kleinste topkaart, de topkaart moet
wel even groot of groter zijn dan de kaart die je vasthoudt
b. Is de kaart groter  Begin een nieuwe stapel aan de rechterkant
Fase 2: Verzamelfase
1. Pak steeds de topkaart met de kleinste waarde


1

, Joël Smit | 5V.in1



Bij kaarten met waarden van 0 tot 9 is het maximale aantal stapels 10  Kan alleen als stapel
kaarten al gesorteerd was  Zal in praktijk niet vaak voorkomen, want dan zul je het algoritme niet
meer toepassen om de kaarten te sorteren


B1.1.4 Schematische weergave van een algoritme
Fase 1: Verdeelfase
In tekst staat 1e kaart apart genoemd  In schema niet, omdat:
 Opdracht ‘pak een kaart’ geldt ook voor 1 e kaart
 Het maakt niet uit welke kaart je pakt
 Als je 1e kaart pakt zijn er nog geen stapels  Uit schema is
wel duidelijk dat die kaart 1e stapel wordt
Fase 2: Verzamelfase
 Topkaarten liggen altijd gesorteerd van klein naar groot  Rechter
topkaart is dus altijd de grootste topkaart
 In verdeelfase is elke stapel altijd gesorteerd van klein naar groot 
Nieuwe kaart wordt namelijk alleen boven op topkaart gelegd als
nieuwe kaart kleiner is dan of gelijk is aan topkaart
 Laagste kaart ligt bovenop linker stapel
 In verzamelfase ontstaat er in elke stap op 1 van de stapels nieuwe topkaart
 Topkaarten liggen dan niet altijd meer goed gesorteerd van links naar
rechts


B1.1.5 Hoe goed is een algoritme?
Veel factoren die bepalen of algoritme goed is  Een van de belangrijkste is aantal
stappen dat je moet doorlopen om tot oplossing te komen


B1.1.6 Best-, average- en worstcasescenario
Efficiëntie van algoritme bepaal je aan hand van aantal stappen dat nodig is om tot oplossing te
komen  Hoe minder stappen, hoe efficiënter  3 scenario’s om efficiëntie te bepalen:
 Bestcasescenario  Beste
 Worstcasescenario  Slechtste
 Averagecasescenario  Gemiddelde
Bv. getal raden tussen 1 en 100 en elk getal 1 voor 1 opnoemen:
 Bestcasescenario  1x raden
 Worstcasescenario  100x raden
 Averagecasescenario  50x raden


B1.1.7 Een zoekalgoritme
Snellere manier om getal tussen 1 en 100 te raden:
Middelste getal kiezen (50)  Weer middelste getal kiezen (25 of 75) etc.  Efficiënter omdat:
 Bestcasescenario  1x raden
 Worstcasescenario  7x raden (50, 25, 13, 6, 3, 2, 1)
 Averagecasescenario lastig te bepalen




2