1
Samenvatting CCSA
1: Zoeken en sorteren............................................................................................................................2
2: Gelinkte lijsten....................................................................................................................................8
2.1: Stapels...........................................................................................................................................16
2.2: Wachtrijen.....................................................................................................................................22
3: Hashtabellen.....................................................................................................................................26
4: Bomen..............................................................................................................................................32
5: Grafen...............................................................................................................................................44
6: Zoekalgoritmes.................................................................................................................................61
8: Machinaal leren................................................................................................................................75
9: Complexiteitstheorie........................................................................................................................82
Extra:....................................................................................................................................................85
Notities examen:
Pseudocodes: pas x toe op deze oefening zelf pseudocode schrijven
o Of: wijzig x in pseudocode y zodat …
Bewijzen skip
Python: zoals dodona: nen tekst
, 2
1: Zoeken en sorteren
Waarom sorteren?
Effect van sorteren sneller zoeken
Vb woordenboek: probeer maar is een woord te zoeken als ze niet gesorteerd zijn.
Lineair / sequentieel zoeken: algoritme
= elk element afgaan om te zoeken
Tijdscomplexiteit is lineair, dus tijdscomplexiteit van orde n
o T(n) = O(n)
Pseudocode – python
Binair zoeken
Eerst de array sorteren
Dan een element beschouwen (het middelste bv)
o Indien dit element kleiner is dan de gezochte waarde, zoek dan rechts verder
o Indien dit element groter is dan de gezochte waarde, zoek dan links verder
Kan iteratief / recursief
Tijdscomplexiteit is logaritmisch: telkens halveer je de lijst
o T(n) = O(²log(n))
Tijdscomplexiteit manueel: hoeveel wordt dit uitgevoerd ‘rij[m] < zoekItem’
o Bij n = 1 0 keer
o Bij n = 2 1 keer
o Bij n = 4 2 keer
o …
, 3
Pseudocode iteratief – python
Pseudocode recursief – python
, 4
Tijdscomplexiteit (=analyse v/d uitvoeringstijd)
Karakteriseert het gedrag v/d uitvoeringstijd voor grote waarden, typisch gedrag is:
Lineaire functie: T(n) = n
o Invoer verdubbelt uitvoeringstijd verdubbelt
Kwadratische functie: T(n) = n²
o Invoer verdubbelt uitvoeringstijd x 4
Exponentiële functie: T(n) = 2n
o Invoer + 1 uitvoeringstijd x 2
Logaritmische functie: T(n) = log(n)
o Invoer verdubbelt uitvoeringstijd + constante
Hoe bepalen?
Bij zoekalgoritmen wordt dit bepaalt door het aantal vergelijkingen dat worden uitgevoerd. Zie
bv bij binair zoeken hierboven
Sorteren door selectie
Basisidee:
o zoek het grootste element en plaats het achteraan
o Doe zo voort
Complexiteitsanalyse: hoeveel keer wordt a[j] > max uitgevoerd?
o For i n keer
o For j n – 1 keer
o (n(n-1)) / 2
o T(n) = O(n²)
Algemeen:
o 0 + 1 + 2 + … + n-1 = ! n (n-1) / 2 !
pseudocode – python (kan ook omgekeerd: buitenste for van klein nr groot en dan telkens de min
bijhouden etc) + examen: van groot nr klein, met mengen / tussenvoegen / selection
Groot nr klein is gwn < of > switchen
Samenvatting CCSA
1: Zoeken en sorteren............................................................................................................................2
2: Gelinkte lijsten....................................................................................................................................8
2.1: Stapels...........................................................................................................................................16
2.2: Wachtrijen.....................................................................................................................................22
3: Hashtabellen.....................................................................................................................................26
4: Bomen..............................................................................................................................................32
5: Grafen...............................................................................................................................................44
6: Zoekalgoritmes.................................................................................................................................61
8: Machinaal leren................................................................................................................................75
9: Complexiteitstheorie........................................................................................................................82
Extra:....................................................................................................................................................85
Notities examen:
Pseudocodes: pas x toe op deze oefening zelf pseudocode schrijven
o Of: wijzig x in pseudocode y zodat …
Bewijzen skip
Python: zoals dodona: nen tekst
, 2
1: Zoeken en sorteren
Waarom sorteren?
Effect van sorteren sneller zoeken
Vb woordenboek: probeer maar is een woord te zoeken als ze niet gesorteerd zijn.
Lineair / sequentieel zoeken: algoritme
= elk element afgaan om te zoeken
Tijdscomplexiteit is lineair, dus tijdscomplexiteit van orde n
o T(n) = O(n)
Pseudocode – python
Binair zoeken
Eerst de array sorteren
Dan een element beschouwen (het middelste bv)
o Indien dit element kleiner is dan de gezochte waarde, zoek dan rechts verder
o Indien dit element groter is dan de gezochte waarde, zoek dan links verder
Kan iteratief / recursief
Tijdscomplexiteit is logaritmisch: telkens halveer je de lijst
o T(n) = O(²log(n))
Tijdscomplexiteit manueel: hoeveel wordt dit uitgevoerd ‘rij[m] < zoekItem’
o Bij n = 1 0 keer
o Bij n = 2 1 keer
o Bij n = 4 2 keer
o …
, 3
Pseudocode iteratief – python
Pseudocode recursief – python
, 4
Tijdscomplexiteit (=analyse v/d uitvoeringstijd)
Karakteriseert het gedrag v/d uitvoeringstijd voor grote waarden, typisch gedrag is:
Lineaire functie: T(n) = n
o Invoer verdubbelt uitvoeringstijd verdubbelt
Kwadratische functie: T(n) = n²
o Invoer verdubbelt uitvoeringstijd x 4
Exponentiële functie: T(n) = 2n
o Invoer + 1 uitvoeringstijd x 2
Logaritmische functie: T(n) = log(n)
o Invoer verdubbelt uitvoeringstijd + constante
Hoe bepalen?
Bij zoekalgoritmen wordt dit bepaalt door het aantal vergelijkingen dat worden uitgevoerd. Zie
bv bij binair zoeken hierboven
Sorteren door selectie
Basisidee:
o zoek het grootste element en plaats het achteraan
o Doe zo voort
Complexiteitsanalyse: hoeveel keer wordt a[j] > max uitgevoerd?
o For i n keer
o For j n – 1 keer
o (n(n-1)) / 2
o T(n) = O(n²)
Algemeen:
o 0 + 1 + 2 + … + n-1 = ! n (n-1) / 2 !
pseudocode – python (kan ook omgekeerd: buitenste for van klein nr groot en dan telkens de min
bijhouden etc) + examen: van groot nr klein, met mengen / tussenvoegen / selection
Groot nr klein is gwn < of > switchen
