Begrippen
In de stof kom je verschillende begrippen tegen. Ze zijn altijd oranje en vetgedrukt. In deze
paragraaf vind je een overzicht van alle begrippen uit dit subdomein.
Hoofdstuk 1. Algoritmen
- Algoritme
- Een verzameling instructies om een probleem op te lossen.
- Lijst
- Een verzameling van getallen, woorden, spelkaarten e.d.
- Element
- Eén onderdeel van een lijst.
- Gesorteerde lijst
- Een lijst waarvan de elementen op een afgesproken volgorde liggen.
- Ongesorteerde lijst
- Een lijst waarvan de elementen niet op een afgesproken volgorde liggen.
- Bestcasescenario
- Een situatie waarin een algoritme het beste presteert
- Worstcasescenario
- Een situatie waarin een algoritme het slechts presteert
- Averagecasescenario
- Een situatie waarin een algoritme gemiddeld presteert
- Zoekalgoritme
- Een algoritme om een element in een lijst te vinden.
- Efficiëntie van een algoritme
- De samenhang tussen de benodigde tijd, het aantal stappen en het benodigde geheugen om een probleem op te
lossen.
Hoofdstuk 2. Standaardalgoritmen
- Standaardalgoritme
- Een algoritme voor een vaker voorkomend probleem, zoals het sorteren van elementen in een lijst of het
berekenen van een route tussen twee punten.
- Sorteeralgoritme
- Een algoritme om de elementen in een lijst volgens een afgesproken volgorde te sorteren.
- BubbleSort
- Een eenvoudig sorteeralgoritme. Hierbij doorloop je de lijst, vergelijk je elementen en verwissel je
elementen – indien nodig – van plek.
- MergeSort
- Een efficiënt sorteeralgoritme. De lijst wordt gesplitst in deellijsten die afzonderlijk worden opgelost en
uiteindelijk worden samengevoegd.
- Divide-and-conquermethode
- Het opsplitsen van een probleem in deelproblemen, het oplossen van deze deelproblemen en
het samenvoegen van de resultaten.
- Quicksort
- Een efficiënt sorteeralgoritme. Aan de hand van een willekeurig element uit de lijst wordt de
divide-and-conquermethode toegepast.
- Pivot
- Het willekeurige gekozen element in het algoritme QuickSort.
- Kortepadalgoritme
- Een algoritme om het kortste pad tussen een aantal punten te berekenen.
- Graaf
- Een schema wat gebruikt wordt om het kortstepadalgoritme weer te geven. De punten worden genoteerd als
cirkels. Deze cirkels zijn met elkaar verbonden d.m.v. een lijn als er een route is tussen de punten.
- Gewogen graaf
- Een graaf, waarbij er naast de verbindingen tussen de punten eenheden vermeld staan.
Hoofdstuk 3. Onoplosbare problemen?
- Rugzakprobleem
- Een klassiek probleem, waarbij er spullen met een verschillend gewicht en waarde in een rugzak meegenomen
moeten
worden. Echter passen niet alle spullen in de rugzak. Doel is om de meeste waarde mee te nemen.
- Correctheid (algoritme)
- De meest ideale oplossing van een probleem.
- Efficiëntie (algoritme)
- De meest efficiënte oplossing van een probleem (zie ook ‘efficiëntie van een algoritme’).
- Brute force
- Een algoritme dat alle mogelijkheden langsgaat.
- Oplossing benaderen
- Een afweging tussen een correcte en een efficiënte oplossing van een probleem.
- Handelsreizigersprobleem
- Een klassiek probleem, waarbij een reiziger naar een aantal steden moet reizen. Hij bezoekt elke stad maar
één
keer. Hoe kan hij dit doen, door zo kort mogelijk te hoeven reizen?
- Chinese postbodeprobleem
- Een klassiek probleem, waarbij een postbode in een stad alle straten tenminste één keer moet doorlopen – en
waarbij hij zo weinig mogelijk straten meerdere keren doorloopt.