informatica/wiskunde vraag

Dit forum is voor het voortgezetonderwijs (of 2de/3de graad ASO), als je in de bovenbouw zit. We gaan er vanuit dat je een Grafische Rekenmachine hebt.
Ellenaoae
Nieuw lid
Nieuw lid
Berichten: 1
Lid geworden op: 27 feb 2013, 20:12

informatica/wiskunde vraag

Bericht door Ellenaoae » 27 feb 2013, 20:25

kan iemand mij helpen met deze informatica/wiskunde vraag? het gaat vooral om vraag (13) A
bedankt!
hier de opgave:


(13) Hoe snel groeien functies? Hoe belangrijk is de snelheid van de computer voor

de uitvoering van een algoritme?

De rekentijd die nodig is voor een bepaald algoritme, als functie van de omvang van

het probleem N, gedraagt zich soms als een lineaire functie (0(N)), als een

logaritmische functie (0(log N)), als een kwadratische functie (0(N”2)), als een

exponentiële functie (0(2”N)): wat maakt dit in de praktijk uit?

Stel, je krijgt de beschikking over een modernere computer, die 1000 (of 1.000.000)

maal zo snel rekent als je vorige computer. Hiermee kun je, in dezelfde tijd, een groter

probleem uitrekenen dat met je oude computer; de vraag is nu: hoeveel groter kan dat

probleem zijn, voor algoritmen met het volgende gedrag van de rekentijd. Anders

geformuleerd: voor welke waarde x geldt dat f(x) = 1000 f(N)?

Voor f(N) = N is dit eenvoudig: x=1000, immers f(1000 * N) = 1000 * F(N)

«N) x waarvoor f(x) = 1000 * «N) x waarvoor f(x)10A6 *

«N)

log N

N 1000*N 1000000*N

N”2

NA3

2AN

a.) Maak de tabel compleet: bepaal genoemde x voor de andere functies; probeer eerst

een grove schatting te maken.

b.) Wat betekent dit voor Dijkstra’s algoritme? Hoeveel punten kun je extra in de graaf

opnemen als je over die snellere computer beschikt?

c.) Idem, voor het Traveling Salesman Problem? Met hoeveel steden kun je dit

uitbreiden?

Plaats reactie