Izpitno vprašanje RAČ2PRA 4000

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 20:39, 22 april 2007
METARAM (Pogovor | prispevki)
Izpitno vprašanje RAČ2PRA 4000 prestavljeno v Izpitno vprašanje RAČ2PRA 4200
← Prejšnja različica
Različica od 08:41, 26 april 2007
193.2.67.50 (Pogovor | prispevki)

Naslednja različica →
Vrstica 1: Vrstica 1:
-#redirect [[Izpitno vprašanje RAČ2PRA 4200]]+==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?
 +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 in 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.
 + 
 +[[Kategorija:Izpitno vprašanje]]
 +[[Kategorija:Računalništvo 2 (UL-FMF Praktična matematika)]]

Različica od 08:41, 26 april 2007

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 in 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