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
Les avantages d'acheter des résumés chez Stuvia:
Qualité garantie par les avis des clients
Les clients de Stuvia ont évalués plus de 700 000 résumés. C'est comme ça que vous savez que vous achetez les meilleurs documents.
L’achat facile et rapide
Vous pouvez payer rapidement avec iDeal, carte de crédit ou Stuvia-crédit pour les résumés. Il n'y a pas d'adhésion nécessaire.
Focus sur l’essentiel
Vos camarades écrivent eux-mêmes les notes d’étude, c’est pourquoi les documents sont toujours fiables et à jour. Cela garantit que vous arrivez rapidement au coeur du matériel.
Foire aux questions
Qu'est-ce que j'obtiens en achetant ce document ?
Vous obtenez un PDF, disponible immédiatement après votre achat. Le document acheté est accessible à tout moment, n'importe où et indéfiniment via votre profil.
Garantie de remboursement : comment ça marche ?
Notre garantie de satisfaction garantit que vous trouverez toujours un document d'étude qui vous convient. Vous remplissez un formulaire et notre équipe du service client s'occupe du reste.
Auprès de qui est-ce que j'achète ce résumé ?
Stuvia est une place de marché. Alors, vous n'achetez donc pas ce document chez nous, mais auprès du vendeur MarlindeD. Stuvia facilite les paiements au vendeur.
Est-ce que j'aurai un abonnement?
Non, vous n'achetez ce résumé que pour €5,49. Vous n'êtes lié à rien après votre achat.
