Summary
Samenvatting Informatica – Fundament – 5 VWO – B1 Algoritmen
- Course
- Level
Samenvatting: Informatica – Fundament – 5 VWO – B1 Algoritmen
[Show more]
Seller
Follow
SmitJoël
Reviews received
Content preview
Joël Smit | 5V.in1Informatica – 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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller SmitJoël. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $5.16. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
78291 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now