Samenvatting
Samenvatting Datastructuren deel 2
- Vak
- Instelling
Een samenvatting van alle stof die je moet weten voor de final van datastructuren (college 7 t/m 16), inclusief (pseudo)code voor veel van de genoemde algoritmen in C#.
[Meer zien]Voorbeeld 4 van de 38 pagina's
Voorbeeld 4 van de 38 pagina's
In winkelwagen
In winkelwagen
1 beoordeling
Door: olivierbellaart • 1 jaar geleden
Door: MarlindeD • 1 jaar geleden
Hoi, bedankt voor je review! Zijn er dingen die ik zou kunnen verbeteren aan de samenvatting?
Verkoper
Volgen
MarlindeD
Ontvangen beoordelingen
Voorbeeld van de inhoud
Datastructuren: Samenvatting deel 2Recursie en Master theorem
Recursieve methode: een methode die zichzelf aanroept
→ Handig voor het opsplitsen van een probleem, waarvan je niet weet hoe je die moet oplossen, in
kleinere problemen die je wel kan oplossen
Voorbeeld: Optellen
Je hebt een array van integers, waarvan je de som wil berekenen, maar je weet niet hoe je dit moet
aanpakken. Je weet echter wel dat de totaalsom gelijk is aan de som van de linker en rechter helft van de
array. Je gaat het probleem dus met recursie aanpakken:
static int Som(int[] A, int p, int q)
{
//Base-cases
if(q <= p) //Segment van lengte nul...
return 0; //... heeft als return waarde ook nul
if(q == p+1) //Segment met lente een...
return A[p]; //... heeft als return waarde dat element
//Recursie
int r = (p + q)/2;
int L = Som(A, p, r);
int R = Som(A, r, q);
return R+L;
}
Hier splitsen we de array steeds op in twee gelijke delen met grenzen p en q. Dan checken we eerst de
base-cases; is het een segment van lengte 0 of 1? Is dit niet het geval, dan gaan we verder de recursie in,
totdat we wel bij de base-case komen. Wanneer je helemaal onderaan bij de base-case bent, ga je stap
voor stap weer omhoog en tel je elke stap L op bij R. Zo krijg je uiteindelijk de som van de array.
Base-case: het kleinst mogelijke ‘probleem’ dat niet verder opgesplitst kan worden
We hebben hier twee base-cases, want met alleen de eerste base-case zouden we in een oneindige
recursie terecht komen. Want een segment van 1 element kan altijd opgesplitst worden in een segment
van 0 en 1. Het segment van 0 geeft correct 0 terug, maar het segment van 1 gaat oneindig vaak terug de
recursie in, wat een overflow veroorzaakt (wat natuurlijk resulteert in een crash). Door de tweede base-
case toe te voegen, zijn we er zeker van dat alleen segmenten van lengte 2 of meer de recursie in gaan.
Je wil de som over de gehele array, dus deze methode roep je aan met als ondergrens nul en als
bovengrens de lengte van je array: Som(0, n)
De toren van Hanoi
Van een recursief algoritme kan je de kosten niet rechtstreeks uitrekenen, want je hebt te maken met
stappen waarvan je de kosten nog niet kent. Het uitrekenen gaat altijd met een tussenstap; de recurrente
betrekking.
Recurrente betrekking: definieert de waarde van een functie in termen van de waarden voor kleinere
parameters
→ De oplossing van de recurrente betrekking geeft de waarde rechtstreeks
Datastructuren: Samenvatting deel 2 1
, Neem als voorbeeld het oplossen van de toren van Hanoi, dit kan gedaan worden met behulp van
recursie, en de pseudocode ziet er als volgt uit:
Hanoi(A, B, n)
{ if(n==1)
Zet(A, B);
else
{
Hanoi(A, C, n-1);
Zet(A, B);
Hanoi(B, C, n-1);
}
}
De recurrente betrekking die hierbij hoort is:
Z(n) = {
1 als n = 1
Z(n − 1) + 1 + Z(n − 1) als n > 1
Je ziet dat dit een functie is die zichzelf bevat, dit is dus lastig op te lossen. Soms kan je de oplossing
vinden door ‘raden-en-checken’; je maakt een tabel met n en Z(n) en kijkt of je een verband kan vinden.
Je stelt een hypothese op en gaat die bewijzen met inductie. Dit kan omdat we het hier over het aantal
stappen n hebben die nodig zijn om het probleem op te lossen. Wanneer we het over de tijd van een
bepaald algoritme hebben is het lastiger.
MergeSort
Het idee van MergeSort is als volgt; je hebt een array die je wil
sorteren, je splitst met behulp van recursie de array in in de kleinst
mogelijke elementen (in het geval hiernaast losse getallen), daarna ga
je stap voor stap weer die elementen bij elkaar plakken, waarbij je bij
elke plak actie checkt op de juiste volgorde van de elementen.
Het idee van MergeSort is hiernaast weergeven voor een array met
vier getallen. Het ‘ritsen’ van n keys kost lineaire tijd, omdat je
constante tijd per item gebruikt.
Datastructuren: Samenvatting deel 2 2
, De implementatie van MergeSort in C# ziet er als volgt uit:
static void MergeSort(int[] A, int p, int q)
{
if (q - p <= 1)
return;
int m = (p + q) / 2;
//Recursie
MergeSort(A, p, m);
MergeSort(A, m, q);
//Mergen van de sub-arrays
int i = p; int j = m; int k = 0;
int[] B = new int[q - p];
while (i < m || j < q)
{
if (j >= q || (i < m && A[i] <= A[j]))
{
B[k] = A[i]; i++;
}
else
{
B[k] = A[j]; j++;
}
k++;
}
for (k = 0; k < q - p; k++)
{
A[p + k] = B[k];
}
}
De recurrente betrekking die bij MergeSort hoort is als volgt:
M(n) = {
0 als n ≤ 1
2 ⋅ M(n/2) + Θ(n) als n > 1
Deze functie kan je alleen asymptotisch oplossen, niet exact. Dit vinden we niet erg, want wanneer we het
over tijd hebben, redeneren we toch al in ordegroottes, niet met exacte waardes.
Asymptotisch oplossen
Wanneer we globaal kijken naar een probleem, mogen we een paar dingen verwaarlozen:
De randvoorwaarde is onbelangrijk (hoe veel kost de base-case?)
Afronden bij delen is onbelangrijk → We splitsen altijd in tweeën, maar het maakt dus niet uit als
links iets groter of kleiner is dan rechts
De exacte waarde van extra termen (dwangtermen) is onbelangrijk
Wat wel belangrijk is, is hoe vaak je de recursie in gaat
Datastructuren: Samenvatting deel 2 3
, Substitutie methode
De substitutie methode is vergelijkbaar met de ‘raden-en-bewijzen’ methode die eerder besproken is. Je
gokt dat een recurrente betrekking een bepaalde ordegrootte als oplossing heeft, en gaat dat dan aan de
hand van inductie bewijzen. Hierbij zijn drie dingen waar je op miet letten:
Het bewijzen mag zonder basis-stap, want de randconditie is niet van belang
In je inductie stap mag je niet met O of Θ uitrekenen, je moet constanten expliciteren
In je inductie stap vind je een restrictie op de constante c (uit de definitie van O)
De substitutie bewijzen moet je kunnen volgen, maar je hoeft ze niet zelf te kunnen opstellen.
Master Theorem
De algemene vorm van een recurrente betrekking waarbij je a keer de recursie in gaat met steeds een
fractie 1/b van de originele input is:
T (n) = a ⋅ T (n/b) + f(n) (1)
Hierbij is f(n) de dwangterm. We willen voor deze vergelijking de algemene oplossing vinden. Hiervoor
willen we de volgende grootheid uitrekenen, en vergelijken met de dwangterm:
b
log(a)
n (2)
Wanneer we deze term met de dwangterm vergelijken, zijn er drie mogelijke uitkomsten:
b
log(a) b
log(a)
1. n > f(n) → T(n) is van ordegrootte Θ(n )
b b
log(a) log(a)
2. n = f(n) → T(n) is van ordegrootte Θ(n ⋅ lg(n))
b
log(a)
3. n < f(n) → T(n) is van ordegrootte Θ(f(n))
Wanneer f(n) een exponentiële term is, zal deze altijd domineren, want exponentieel wint van alles. Let op:
in geval 1 en 3 gaat het om polynomiaal groter of kleiner zijn, als de twee termen een fractie lg(n) van
elkaar verschillen ga je uit van punt twee, waarbij je nu de dwangterm vermenigvuldigd met lg(n).
Voorbeeld van oplossen met de Master Theorem
Neem de volgende recurrente betrekking:
V (n) = 4V (n/2) + O(n)
Hierbij wordt a gegeven door 2 en b door 4. Hiermee rekenen we met vergelijking 2 uit dat de macht van n
wordt gegeven door 2. De eerste term is dus kwadratisch en domineert dus over de dwangterm die lineair
is. V(n) is dus van ordegrootte O(n2 ).
Datastructuren: Samenvatting deel 2 4
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
√ Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, Bancontact of creditcard voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper MarlindeD. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €6,49. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 81989 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen