100% tevredenheidsgarantie Direct beschikbaar na je betaling Lees online óf als PDF Geen vaste maandelijkse kosten
logo-home
Volledige Samenvatting Classic Computer Science Algortihms €4,99
In winkelwagen

Samenvatting

Volledige Samenvatting Classic Computer Science Algortihms

 2 keer verkocht

Volledige Samenvatting Classic Computer Science Algortihms

Voorbeeld 4 van de 85  pagina's

  • 21 oktober 2022
  • 85
  • 2021/2022
  • Samenvatting
Alle documenten voor dit vak (5)
avatar-seller
easyIT
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

Dit zijn jouw voordelen als je samenvattingen koopt bij Stuvia:

Bewezen kwaliteit door reviews

Bewezen kwaliteit door reviews

Studenten hebben al meer dan 850.000 samenvattingen beoordeeld. Zo weet jij zeker dat je de beste keuze maakt!

In een paar klikken geregeld

In een paar klikken geregeld

Geen gedoe — betaal gewoon eenmalig met iDeal, Bancontact of creditcard en je bent klaar. Geen abonnement nodig.

Focus op de essentie

Focus op de essentie

Studenten maken samenvattingen voor studenten. Dat betekent: actuele inhoud waar jij écht wat aan hebt. Geen overbodige details!

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 easyIT. Stuvia faciliteert de betaling aan de verkoper.

Zit ik meteen vast aan een abonnement?

Nee, je koopt alleen deze samenvatting voor €4,99. Je zit daarna nergens aan vast.

Is Stuvia te vertrouwen?

4,6 sterren op Google & Trustpilot (+1000 reviews)

Afgelopen 30 dagen zijn er 65539 samenvattingen verkocht

Opgericht in 2010, al 15 jaar dé plek om samenvattingen te kopen

Start met verkopen
€4,99  2x  verkocht
  • (0)
In winkelwagen
Toegevoegd