100% tevredenheidsgarantie Direct beschikbaar na betaling Zowel online als in PDF Je zit nergens aan vast
logo-home
Samenvatting Algoritmiek €3,49   In winkelwagen

Samenvatting

Samenvatting Algoritmiek

1 beoordeling
 66 keer bekeken  0 keer verkocht

Samenvatting over het onderdeel Algoritmiek van de cursus Analytical Skills gegeven op de HU. Bevat complexiteiten van algoritmes, lineair en binair zoeken en sorteer mechanismen.

Voorbeeld 1 van de 2  pagina's

  • 10 maart 2020
  • 2
  • 2019/2020
  • Samenvatting
Alle documenten voor dit vak (6)

1  beoordeling

review-writer-avatar

Door: mohammedelouali • 3 jaar geleden

avatar-seller
jetwardenier
Inleiding
algoritme: eindige reeks instructies die vanuit een gegeven begintoestand naar een beoogd doel
leidt.

Complexiteit van algoritmes
- tijdscomplexiteit: hoe lang duurt het om het probleem op te lossen
- ruimtecomplexiteit: hoeveel geheugen is er nodig om het probleem op te lossen
- hoe hard groeit de tijdsduur naarmate het probleem groter wordt
Algoritmes zijn in te delen in verschillende klassen van complexiteit

voorwaarden van een algoritme:
* volgordelijkheid
* ondubbelzinnig
* uit te rekenen
* eindig

Linear en binair zoeken
lineair zoeken: begint bij het eerste element in een lijst en bekijkt elk
volgend element totdat het gezochte element gevonden is.

binair zoeken: zoeken door het continu halveren van een bepaalde lijst

Lineair zoeken zal veel langer duren dan binair zoeken. Hoe meer
elementen er zijn waartussen je kunt kiezen, hoe groter het verschil tussen
lineair en binair zoeken wordt.

Binair zoeken halveert bij elke keer dat je raadt het aantal uitkomsten. Bij
een lijst van 8 elementen zul je maar hoogstens 4 keer hoeven te raden om
tot het goede antwoord te komen, bij een lijst van 16 element zul je
hoogstens 5 keer moeten raden. Elke keer dat het aantal elementen
verdubbeld, heb je één extra keer raden nodig.

Bij een lijst van lengte n heb je m keer nodig om te raden. Bij een lijst van
lengte 2n heb je m + 1 keer nodig.

Voor deze berekening is er een wiskundige functie: log2n
Dit maakt het makkelijk om het aantal “guesses” bij binair zoeken te
berekenen, als n 128 is, heb je (log2 128 + 1) = 8 guesses nodig.

Als n geen macht van 2 is, kijk je naar de laagste macht van 2 die het
dichtstbij het getal zit.

E.g.
Bij het getal 2,539,913 is de laagste macht van 2 die het dichtbij het getal
is 2^21 ( dat is 2,097,152) dus we hebben hoogstens 22 guesses.




pseudocode: een compromis tussen natuurlijk taal en programmeertaal




Jet Wardenier

Voordelen van het kopen van samenvattingen bij Stuvia op een rij:

Verzekerd van kwaliteit door reviews

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

Snel en makkelijk kopen

Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.

Focus op de essentie

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

Zit ik meteen vast aan een abonnement?

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

Is Stuvia te vertrouwen?

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

Afgelopen 30 dagen zijn er 62555 samenvattingen verkocht

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

Start met verkopen
€3,49
  • (1)
  Kopen