Izpitno vprašanje RAČ2PRA 4000

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 08:41, 26 april 2007
193.2.67.50 (Pogovor | prispevki)

← Prejšnja različica
Trenutna različica
METARAM (Pogovor | prispevki)

Vrstica 1: Vrstica 1:
 +{{Student|PeterBedrač|Računalništvo 2 (FMF PRA)}}
==Vprašanje== ==Vprašanje==
-Imamo program, katerega čas izvajanja je O(n<sup>2</sup>), ima pa tudi nezanemarljiv del, ki potrebuje za izvajanje konstanten čas. Ko smo program pognali pri n = 10, je tekel 97 sekund, ko smo ga pognali pri n = 20, je tekel 100 sekund. Kako dolgo bi program delal za n = 1000?+Imamo program, katerega čas izvajanja je O(n<sup>2</sup>), ima pa tudi nezanemarljiv del, ki potrebuje za izvajanje konstanten čas. Ko smo program pognali pri n = 10, je tekel 97 sekund, ko smo ga pognali pri n = 20, je tekel 100 sekund.<br>
-Za problem iz prejnjega dela smo uspeli najti postopek, ki je O(n). Del programa, ki se izvaja konstanten čas, je enak. Program smo pognali pri n = 1000 in je delo opravil v 1096 sekundah. Oba postopka želimo sestaviti tako, da bomo za določene n uporabljali prejšnji (kvadratni) postopek, za druge pa novega (linearnega). Kako?+Kako dolgo bi program delal za n = 1000? <br>
 +Za problem iz prejnjega dela smo uspeli najti postopek, ki je O(n). <br>
 +Del programa, ki se izvaja konstanten čas, je enak. <br>
 +Program smo pognali pri n = 1000 in je delo opravil v 1096 sekundah. <br>
 +Oba postopka želimo sestaviti tako, da bomo za določene n uporabljali prejšnji (kvadratni) postopek, za druge pa novega (linearnega). Kako?
==Odgovor== ==Odgovor==
-Nalogo razdelima na dva dela in jo tako rešujemo: +Nalogo razdelima na dva dela in jo tako rešujemo:<br>
-1. Imamo torej podana dva podatka, s katerima izračunamo splošno funkcijo, ki jo imamo. Matematično se lotimo naloge takole: Določiti je potrebno konstanti a in b, funkcija se glasi f1(n) = a*(n^2) + b, kar vidimo iz teksta naloge, ker program potrebuje O(n^2) in O(n). Poleg tega imamo podana še dva podatka in sicer f1(10) = 97 in f1(20) = 100. Iz teh podatkov določimo konstanti a in b. Torej izračun naj bi se glasil takole: Iz prvega podatka dobimo +1. Imamo torej podana dva podatka, s katerima izračunamo splošno funkcijo, ki jo imamo. Matematično se lotimo naloge takole: Določiti je potrebno konstanti a in b, funkcija se glasi f1(n) = a*(n^2) + b, kar vidimo iz teksta naloge, ker program potrebuje O(n^2) in O(n). Poleg tega imamo podana še dva podatka in sicer f1(10) = 97 in f1(20) = 100. Iz teh podatkov določimo konstanti a in b.
-100a + b = 97 +Torej izračun naj bi se glasil takole: Iz prvega podatka dobimo<br>
-400a + b = 100 +100a + b = 97 <br>
-Rešimo sistem dveh enačb z dvema neznankama, dobimo: +400a + b = 100 <br>
-a = 1/100 in b = 97 - 100/100 = 96. +Rešimo sistem dveh enačb z dvema neznankama, dobimo: <br>
-Naša enačba se zato glasi: f1(n) = 1/100*(n^2) + 96. +a = 1/100 <br>
-Sedaj lahko izračunamo čas pri n = 1000 preprosto z funkcijo f1(1000). +b = 97 - 100/100 = 96. <br>
-Dobimo torej f1(1000) = 1/100*(1000)^2 + 96 = 10.096, kar znaša, če pretvorimo v ure in minute natanko: 2h 48min 16s. +Naša enačba se zato glasi: f1(n) = 1/100*(n^2) + 96. <br>
-2. Imamo torej podano funkcijo f2(n) = a*n + b, kjer je b = 96. Poleg tega imamo podano še f2(1000) = 1096. Izračunamo še konstanto a na sledeč način: +Sedaj lahko izračunamo čas pri n = 1000 preprosto z funkcijo f1(1000). <br>
-f2(n) = a*n + 96 +Dobimo torej f1(1000) = 1/100*(1000)^2 + 96 = 10.096, kar znaša, če pretvorimo v ure in minute natanko: 2h 48min 16s. <br>
-Iz pogoja f2(1000) dobimo: +2. Imamo torej podano funkcijo f2(n) = a*n + b, kjer je b = 96.<br>
-1096 = a*1000 + 96 ===>>>> a = 1 +Poleg tega imamo podano še f2(1000) = 1096. Izračunamo še konstanto a na sledeč način: <br>
-Torej je naša funkcija enaka f2(n) = n + 96. +f2(n) = a*n + 96 <br>
-Sedaj pa samo še izračunamo presečišče teh dveh funkcij, če želimo dobiti kdaj katero uporabiti, torej f1(n) = 1/100*(n^2) + 96 in f2(n) = n + 96. +Iz pogoja f2(1000) dobimo: <br>
-Izenačimo funkciji f1 = f2 +1096 = a*1000 + 96 ===> a = 1 <br>
-1/100*n^2 + 96 = n + 96 +Torej je naša funkcija enaka f2(n) = n + 96. <br>
-1/100*n^2 = n +Sedaj pa samo še izračunamo presečišče teh dveh funkcij, če želimo dobiti kdaj katero uporabiti, torej f1(n) = 1/100*(n^2) + 96 in f2(n) = n + 96. <br>
-n^2 = 100*n +Izenačimo funkciji f1 = f2 <br>
-n(n-100) = 0. +1/100*n^2 + 96 = n + 96 <br>
 +1/100*n^2 = n <br>
 +n^2 = 100*n <br>
 +n(n-100) = 0. <br>
Torej se funkciji zamenjata pri n = 0 in n = 100, kar iz našega primera sledi, da se splača uporabljati f2 torej funkcijo z časovno zahtevnostjo O(n) za n od 0 do 100 in drugače f1 za n večji od 100. Torej se funkciji zamenjata pri n = 0 in n = 100, kar iz našega primera sledi, da se splača uporabljati f2 torej funkcijo z časovno zahtevnostjo O(n) za n od 0 do 100 in drugače f1 za n večji od 100.
[[Kategorija:Izpitno vprašanje]] [[Kategorija:Izpitno vprašanje]]
[[Kategorija:Računalništvo 2 (UL-FMF Praktična matematika)]] [[Kategorija:Računalništvo 2 (UL-FMF Praktična matematika)]]

Trenutna različica

GFDL Avtor tega članka je študent/ka PeterBedrač.

Pripravil/a ga je pri predmetu Računalništvo 2 (FMF PRA).


Kljub temu ste vsi vabljeni k urejanju in popravkom, saj je bistvo wikija ravno v sodelovalnem delu.

Vprašanje

Imamo program, katerega čas izvajanja je O(n2), ima pa tudi nezanemarljiv del, ki potrebuje za izvajanje konstanten čas. Ko smo program pognali pri n = 10, je tekel 97 sekund, ko smo ga pognali pri n = 20, je tekel 100 sekund.
Kako dolgo bi program delal za n = 1000?
Za problem iz prejnjega dela smo uspeli najti postopek, ki je O(n).
Del programa, ki se izvaja konstanten čas, je enak.
Program smo pognali pri n = 1000 in je delo opravil v 1096 sekundah.
Oba postopka želimo sestaviti tako, da bomo za določene n uporabljali prejšnji (kvadratni) postopek, za druge pa novega (linearnega). Kako?

Odgovor

Nalogo razdelima na dva dela in jo tako rešujemo:
1. Imamo torej podana dva podatka, s katerima izračunamo splošno funkcijo, ki jo imamo. Matematično se lotimo naloge takole: Določiti je potrebno konstanti a in b, funkcija se glasi f1(n) = a*(n^2) + b, kar vidimo iz teksta naloge, ker program potrebuje O(n^2) in O(n). Poleg tega imamo podana še dva podatka in sicer f1(10) = 97 in f1(20) = 100. Iz teh podatkov določimo konstanti a in b. Torej izračun naj bi se glasil takole: Iz prvega podatka dobimo
100a + b = 97
400a + b = 100
Rešimo sistem dveh enačb z dvema neznankama, dobimo:
a = 1/100
b = 97 - 100/100 = 96.
Naša enačba se zato glasi: f1(n) = 1/100*(n^2) + 96.
Sedaj lahko izračunamo čas pri n = 1000 preprosto z funkcijo f1(1000).
Dobimo torej f1(1000) = 1/100*(1000)^2 + 96 = 10.096, kar znaša, če pretvorimo v ure in minute natanko: 2h 48min 16s.
2. Imamo torej podano funkcijo f2(n) = a*n + b, kjer je b = 96.
Poleg tega imamo podano še f2(1000) = 1096. Izračunamo še konstanto a na sledeč način:
f2(n) = a*n + 96
Iz pogoja f2(1000) dobimo:
1096 = a*1000 + 96 ===> a = 1
Torej je naša funkcija enaka f2(n) = n + 96.
Sedaj pa samo še izračunamo presečišče teh dveh funkcij, če želimo dobiti kdaj katero uporabiti, torej f1(n) = 1/100*(n^2) + 96 in f2(n) = n + 96.
Izenačimo funkciji f1 = f2
1/100*n^2 + 96 = n + 96
1/100*n^2 = n
n^2 = 100*n
n(n-100) = 0.
Torej se funkciji zamenjata pri n = 0 in n = 100, kar iz našega primera sledi, da se splača uporabljati f2 torej funkcijo z časovno zahtevnostjo O(n) za n od 0 do 100 in drugače f1 za n večji od 100.

Osebna orodja