Een samenvatting van alle stof die je moet weten voor de midterm van datastructuren (college 1 t/m 6), inclusief uitgewerkte code voor veel van de genoemde algoritmen in C#.
Datastructuren: Samenvatting deel 1
Binary search
Wat is zoeken?
Een datastructuur slaat data op. De simpelste vorm van een datastructuur is een List (in C#), die
elementen van verschillende datasoorten kan opslaan (integers, strings, tupels, enz.).
Databases: je bemoeit je niet met de details van de opslag, maar je stopt vragen die je “aan de data wilt
stellen” in de SQL-query.
Datastructuren: je zoekt naar de beste organisatie van je data, rekening houdend met de vragen die je
wil stellen
Zoeken door een ongesorteerde lijst
Je wil een element x zoeken in een ongesorteerde rij. Dit is niet moeilijk om te implementeren, maar het
zoeken zelf kan erg tijdrovend zijn, want je moet door de hele lijst heen totdat je het element x vindt.
Toevoegen aan de lijst is echter wel heel makkelijk, je plakt het element gewoon op de eerste open plek.
Lineaire tijd O(n): de zoektijd is evenredig met het aantal elementen
Ongesorteerd → toevoegen is goedkoop, zoeken is duur
Zoeken door een gesorteerde lijst
Je wil een element x zoeken in een gesorteerde rij, waarin de elementen van groot naar klein staan.
Toevoegen is nu duur geworden, want we moeten zoeken waar het element dat we willen toevoegen past
(weer lineaire tijd).
Het zoeken gaat nu echter een stuk sneller; we bekijken het element in het midden van de lijst, en als dat
element groter is, dan x moeten we links van dat element verder zoeken en als het kleiner is, zoeken we
verder rechts. Door één element te bekijken, kunnen we de helft van de lijst uitsluiten. Door dit meerdere
keren te herhalen komen we snel uit bij element x.
Gesorteerd → toevoegen is duur, zoeken is goedkoop
Binary search
Het idee van binary search is als volgt:
Houd twee variabelen bij: de onder- en bovengrens van je zoekgebied (i en j)
Bekijk het middelste element en bepaal of je links of rechts van dat element verder gaat zoeken (m =
(i+j)/2)
Pas op basis daarvan je boven- of ondergrens aan
Kleiner dan m → links zoeken + pas je bovengrens aan (j = m)
Groter dan m → rechts zoeken + pas je ondergrens aan (i = m)
Stop als je gebied klein genoeg is (wanneer je je waarde gevonden hebt)
Datastructuren: Samenvatting deel 1 1
, De invariant
Het maken van een loop is ingewikkeld omdat de vier factoren die de loop omschrijven elkaar allemaal
beïnvloeden. De vier elementen zijn:
Initialisatie I: welke variabelen gebruik je en hoe krijgen ze hun initiële waarde
Conditie C: wanneer stop je de loop
Body B: wat ga je in de loop doen
Terminatie T: hoe ga je verder als de loop klaar is
Om dingen aan te passen zonder dat andere elementen ook aangepast worden gebruik je de invariant.
Deze zorgt ervoor dat je met minder dingen tegelijk rekening hoeft te houden.
Invariant: een predikaat over je variabelen en je data, waarvoor je zorgt dat die waar is voor en na elke
ronde van de loop
Bij het kiezen van de invariant formule P moet je rekening houden met de volgende punten:
De initialisatie moet zorgen dat na de initialisatie de formule P geldt (waar is), om dit aan te tonen mag
je de gegevens gebruiken
De body moet zo geschreven zijn zodat P zowel voor als na de body geldt (waar is)
De conditie kun je zo kiezen dat je uit ¬C ∧ P een logische conclusie kan trekken over dat wat je wil
weten
P omdat die na elke ronde van de loop moet gelden
¬C omdat C de terminatie conditie is
Gebruik ¬C ∧ P om je uitkomst te bepalen
Partieel correct: variant
Een programma dat niet termineert (vanwege een lege of incomplete body) voldoet niet aan de premisse
en dan is dus aan partiële correctheid voldaan (je voldoet aan de variant, maar je krijgt nooit een output).
Om te zorgen dat er wel een terminatie is, moet je ook zorgen dat er een bepaalde grootheid is die in elke
ronde van de loop daalt. Deze grootheid is de variant.
Voorbeeld: de kleinste doos
Gegeven: een oplopende rij A met n getallen en een element x
Gevraagd: de locatie van element x in A → A[i] = x (als x meerdere keren voorkomt, willen we het eerste
voorkomen van x)
De invariant die we in deze situatie gebruiken is: A[i] < x ∧ A[j] ≥ x
→ j is net als i een positie van een element in de lijst
→ Hiermee zeggen we dus; x ligt in een bepaald gebied, waarbij het groter is dan element i en kleiner
of gelijk aan element j en we gaan dus alleen in dat gebied zoeken, anders geldt de invariant niet
We zoeken dus een j zodat geldt: A[j] ≥ x en A[j-1] < x → je pakje past in doos j, en doos j-1 is net te
klein
Datastructuren: Samenvatting deel 1 2
, Het programma dat dit probleem oplost ziet er als volgt uit:
static int Zoek(x)
{
//Initialisatie:
int i = -1; int j = A.Count();
//Loop:
while(i < j-1)
{
int m = (i + j)/2; //het element in het midden van het zoekgebied
if(A[m] < x) //ga links zoeken van m...
i = m; //... en pas dus de bovengrens aan
else //ga rechts zoeken van m...
j = m; //... en pas dus de ondergrens aan
}
return j
}
De variant in dit programma is de grootte van de zoekruimte, gegeven door j-i. Elke ronde wordt de
waarde van i groter of de waarde van j kleiner, waardoor dus de grootte van de zoekruimte afneemt.
Binair zoeken werk heel snel!
Het aantal rondes in een loop die werkt met binary search is ongeveer lg(n). Dit wordt ook wel de
logaritmische tijd genoemd, oftewel O(lg n).
→ lg(x) is gelijk aan 2_log(x)
Early stopping: NIET DOEN!
Early stopping: als je op plek m precies vind wat je zoekt, kan je ervoor kiezen om te stoppen met
zoeken
Dit is niet aan te raden, early stopping zijn moeilijker om te implementeren en werkt over het algemeen
niet sneller dan binary search. Je bekijkt bovendien elke waarde twee keer; een keer om te kijken of het
de waarde is die je zoekt en dan nog een keer om je zoekgebied te verkleinen.
Datastructuren: Samenvatting deel 1 3
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 MarlindeD. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $5.97. You're not tied to anything after your purchase.
