Samenvatting

Samenvatting Algoritmiek

Name: Algoritmiek
SKU: doc_667073
Rating: 5.00 (1 reviews)
Author: jetwardenier

1 beoordeling

0 keer verkocht

Vak
Analytical Skills (ASK)

Instelling
Hogeschool Utrecht (HU)

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.

[Meer zien]

Voorbeeld 1 van de 2 pagina's

Bekijk voorbeeld

Geupload op 10 maart 2020
Aantal pagina's 2
Geschreven in 2019/2020
Type Samenvatting

1 beoordeling

Door: mohammedelouali • 4 jaar geleden

Volgen

jetwardenier Lid sinds 5 jaar 26 documenten verkocht

€3,49

Ook beschikbaar in voordeelbundel v.a. €14,49

In winkelwagen

Opslaan

100% tevredenheidsgarantie
Direct beschikbaar na je betaling
Lees online óf als PDF
Geen vaste maandelijkse kosten

Ook beschikbaar in voordeelbundel (1)

Complete Bundel Analytical Skills HBO-ICT

€ 20,94 € 14,49

2x verkocht

6 items

1. Samenvatting - Algoritmiek
2. Samenvatting - Verzamelingenleer
3. Samenvatting - Logisch gevolg
4. Samenvatting - Logica en waarheidstabellen
5. Samenvatting - Statistiek, data-analyse en datavisualisatie
6. Samenvatting - Kunstbeschouwing en schatten
Meer zien

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

Dit zijn jouw voordelen als je samenvattingen koopt bij Stuvia:

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

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

Direct to-the-point

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.