Resume
Samenvatting Datastructuren deel 2
- Cours
- Établissement
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#.
[Montrer plus]
1 vérifier
Par: olivierbellaart • 1 année de cela
Par: MarlindeD • 1 année de cela
Hi, thanks for your review! Are there things I could improve about the summary?
Vendeur
S'abonner
MarlindeD
Avis reçus
Aperçu du contenu
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
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 €6,49. Vous n'êtes lié à rien après votre achat.
Peut-on faire confiance à Stuvia ?
4.6 étoiles sur Google & Trustpilot (+1000 avis)
71184 résumés ont été vendus ces 30 derniers jours
Fondée en 2010, la référence pour acheter des résumés depuis déjà 14 ans