| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
Ally
Forumaš(ica)
Pridružen/a: 15. 04. 2008. (19:57:23)
Postovi: (7F)16
Spol: 
|
|
| [Vrh] |
|
Atomised
Forumaš(ica)
Pridružen/a: 04. 09. 2007. (15:33:59)
Postovi: (399)16
Lokacija: Exotica
|
|
| [Vrh] |
|
bixodococo
Forumaš(ica)
Pridružen/a: 22. 11. 2007. (20:26:24)
Postovi: (7F)16
Spol: 
|
|
| [Vrh] |
|
Gino
Forumaš(ica)
Pridružen/a: 11. 09. 2008. (10:54:06)
Postovi: (370)16
Lokacija: Pula
|
|
| [Vrh] |
|
bixodococo
Forumaš(ica)
Pridružen/a: 22. 11. 2007. (20:26:24)
Postovi: (7F)16
Spol:
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3560)16
Spol: 
Lokacija: /sbin/init
|
|
| [Vrh] |
|
bixodococo
Forumaš(ica)
Pridružen/a: 22. 11. 2007. (20:26:24)
Postovi: (7F)16
Spol:
|
|
| [Vrh] |
|
Tygy
Forumaš(ica)
Pridružen/a: 22. 11. 2008. (15:27:08)
Postovi: (102)16
|
|
| [Vrh] |
|
Gino
Forumaš(ica)
Pridružen/a: 11. 09. 2008. (10:54:06)
Postovi: (370)16
Lokacija: Pula
|
 Postano: 10:41 sub, 5. 11. 2011 Naslov: |
    |
|
|
[quote="bixodococo"]I? Gdje se najčešće griješi? :lol:[/quote]
da, to se i ja pitam :D pamcenje me lose sluzi, uglavnom ima par tih zadataka koje je on lijepo namjestio da se fula :lol:
na primjer 1. kol iz 2008. 1(b)
ja sam to pogledao i reko aha to je [tex]\log n[/tex], no, uspostavilo se da sam glup :D
[quote="Tygy"]točnije, zanima me prvi dadatak sa prvih kolokvija(svi su isti)
i kraj rekurzije...bilo koje :)[/quote]
rjesenje bi islo ovako nekako:
indeks [tex]i[/tex] neka poprima vrijednosti [tex]i_1, i_2, \ldots , i_k[/tex] sve dok je [tex]i_k<n[/tex]
vrijedi [tex]i_1=2, i_2=4, i_3=16, \ldots , i_j=2^{2^{j-1}}[/tex]
i sad samo uvjet [tex]2^{2^{k-1}}=i_k<n[/tex] logaritmiras dva puta i vidis da je gornja ocjena [tex]\log \log n[/tex], to je odmah i donja jer mora biti [tex]i_{k+1}\geq n[/tex] (u smisu trazis takav [tex]k[/tex] da imas te dvije ocjene...)
mozda ovo nije posve precizno, ali mislim da je dovoljno dobro :wink:
evo onda odmah i kraj rekurzije (isti kolokvij)
ako sam ja to dobro raspisao, za slucaj kada je [tex]n[/tex] potencija od [tex]3[/tex] vrijedi
[tex]T(n)=(d+3)n^{\log_34}-3n=\mathcal{O}(n^{\log_34})[/tex]
Da bi stvar vrijedila bezuvjetno, mora [tex]f(n)=n^{\log_34}[/tex] biti glatka funkcija i [tex]T(n)=4T(\lfloor n/3 \rfloor)+n[/tex] mora biti asimptotski rastuca (sto znaci da je rastuca od negdje na dalje)
Za prvu stvar treba samo pokazati da je [tex]f(2n)=\mathcal{O}(f(n))[/tex], no to je ocito jer je [tex]f(2n)=(2n)^{\log_34}=2^{\log_34}f(n)=c\cdot f(n)[/tex]
Za drugu stvar cu pokazat da je rastuca od [tex]n\geq3[/tex]. To se radi indukcijom. (Stvar mi se cini da nije definirana za [tex]n=2[/tex] :shock: )
Baza.
[tex]T(3)=4d+3[/tex]
[tex]T(4)=4d+4[/tex]
Pretpostavimo...
Korak. Vrijedi li:
[tex]T(n+1)=4T(\lfloor\frac{n+1}{3}\rfloor)+n+1>4T(\lfloor\frac{n}{3}\rfloor)+n=T(n)[/tex]
pa ja bih rekao da da, dovoljno je da je da vrijedi [tex]T(\lfloor\frac{n+1}{3}\rfloor)\geq T(\lfloor\frac{n}{3}\rfloor)[/tex], a to vrijedi (ili su jednaki ili se pozovemo na pretpostavku)
| bixodococo (napisa): | I? Gdje se najčešće griješi?  |
da, to se i ja pitam  pamcenje me lose sluzi, uglavnom ima par tih zadataka koje je on lijepo namjestio da se fula
na primjer 1. kol iz 2008. 1(b)
ja sam to pogledao i reko aha to je [tex]\log n[/tex], no, uspostavilo se da sam glup
| Tygy (napisa): | točnije, zanima me prvi dadatak sa prvih kolokvija(svi su isti)
i kraj rekurzije...bilo koje  |
rjesenje bi islo ovako nekako:
indeks [tex]i[/tex] neka poprima vrijednosti [tex]i_1, i_2, \ldots , i_k[/tex] sve dok je [tex]i_k<n[/tex]
vrijedi [tex]i_1=2, i_2=4, i_3=16, \ldots , i_j=2^{2^{j-1}}[/tex]
i sad samo uvjet [tex]2^{2^{k-1}}=i_k<n[/tex] logaritmiras dva puta i vidis da je gornja ocjena [tex]\log \log n[/tex], to je odmah i donja jer mora biti [tex]i_{k+1}\geq n[/tex] (u smisu trazis takav [tex]k[/tex] da imas te dvije ocjene...)
mozda ovo nije posve precizno, ali mislim da je dovoljno dobro 
evo onda odmah i kraj rekurzije (isti kolokvij)
ako sam ja to dobro raspisao, za slucaj kada je [tex]n[/tex] potencija od [tex]3[/tex] vrijedi
[tex]T(n)=(d+3)n^{\log_34}-3n=\mathcal{O}(n^{\log_34})[/tex]
Da bi stvar vrijedila bezuvjetno, mora [tex]f(n)=n^{\log_34}[/tex] biti glatka funkcija i [tex]T(n)=4T(\lfloor n/3 \rfloor)+n[/tex] mora biti asimptotski rastuca (sto znaci da je rastuca od negdje na dalje)
Za prvu stvar treba samo pokazati da je [tex]f(2n)=\mathcal{O}(f(n))[/tex], no to je ocito jer je [tex]f(2n)=(2n)^{\log_34}=2^{\log_34}f(n)=c\cdot f(n)[/tex]
Za drugu stvar cu pokazat da je rastuca od [tex]n\geq3[/tex]. To se radi indukcijom. (Stvar mi se cini da nije definirana za [tex]n=2[/tex]  )
Baza.
[tex]T(3)=4d+3[/tex]
[tex]T(4)=4d+4[/tex]
Pretpostavimo...
Korak. Vrijedi li:
[tex]T(n+1)=4T(\lfloor\frac{n+1}{3}\rfloor)+n+1>4T(\lfloor\frac{n}{3}\rfloor)+n=T(n)[/tex]
pa ja bih rekao da da, dovoljno je da je da vrijedi [tex]T(\lfloor\frac{n+1}{3}\rfloor)\geq T(\lfloor\frac{n}{3}\rfloor)[/tex], a to vrijedi (ili su jednaki ili se pozovemo na pretpostavku)
_________________
Mario Berljafa
|
|
| [Vrh] |
|
Tygy
Forumaš(ica)
Pridružen/a: 22. 11. 2008. (15:27:08)
Postovi: (102)16
|
|
| [Vrh] |
|
YMP
Forumaš(ica)
Pridružen/a: 17. 04. 2009. (14:18:45)
Postovi: (1E)16
Lokacija: VINKOVCI
|
|
| [Vrh] |
|
Gino
Forumaš(ica)
Pridružen/a: 11. 09. 2008. (10:54:06)
Postovi: (370)16
Lokacija: Pula
|
| Postano: 1:07 ned, 6. 11. 2011 Naslov: |
|
|
|
MFL je matematicko fizicki list, "krajem" prosle akademske godine su u doticnom objavljeni tekstovi o financijskom smjeru, statistici i primjenjenoj. ako sam dobro shvatio, ovo je samo nastavak toga, dakle o studiju racunarstva, po onom sto sam vidio taj clanak jos nije objavljen (ali moguce da sam ja fulao ili da im stranice nisu jako azurne)
sto se tice tog zadatka, nisam bas vidio detaljno, al cini mi se da je za sve te metode pisala samo neka kao ideja, a naglasak je bio na majority element-u, koji je zapravo jednostavan (kad ga cujes :D) i to mozes lako naci na netu...
sto je to lokalno polje? tog se ne sjecam
a sto se medijana tice, ja sam si to [url=http://www.ics.uci.edu/~eppstein/161/960130.html]tu[/url] pogledao, nije toliko tesko iako mi je trebalo malo vremena da skuzim :D (al tvrdim da je to zbog engleskog! :D) ono sto mi se cinilo korisno je i izracun slozenosti (koji je usput i jednostavan...)
MFL je matematicko fizicki list, "krajem" prosle akademske godine su u doticnom objavljeni tekstovi o financijskom smjeru, statistici i primjenjenoj. ako sam dobro shvatio, ovo je samo nastavak toga, dakle o studiju racunarstva, po onom sto sam vidio taj clanak jos nije objavljen (ali moguce da sam ja fulao ili da im stranice nisu jako azurne)
sto se tice tog zadatka, nisam bas vidio detaljno, al cini mi se da je za sve te metode pisala samo neka kao ideja, a naglasak je bio na majority element-u, koji je zapravo jednostavan (kad ga cujes ) i to mozes lako naci na netu...
sto je to lokalno polje? tog se ne sjecam
a sto se medijana tice, ja sam si to tu pogledao, nije toliko tesko iako mi je trebalo malo vremena da skuzim (al tvrdim da je to zbog engleskog! ) ono sto mi se cinilo korisno je i izracun slozenosti (koji je usput i jednostavan...)
_________________
Mario Berljafa
|
|
| [Vrh] |
|
YMP
Forumaš(ica)
Pridružen/a: 17. 04. 2009. (14:18:45)
Postovi: (1E)16
Lokacija: VINKOVCI
|
|
| [Vrh] |
|
Atomised
Forumaš(ica)
Pridružen/a: 04. 09. 2007. (15:33:59)
Postovi: (399)16
Lokacija: Exotica
|
|
| [Vrh] |
|
(s)Venn
Forumaš(ica)
Pridružen/a: 18. 02. 2009. (17:59:25)
Postovi: (40)16
Lokacija: Velika Gorica
|
| Postano: 15:02 ned, 6. 11. 2011 Naslov: |
|
|
|
Jednostavno, nađeš opći oblik rekurzije za tk (dakle, nakon što provedeš supstituciju, npr n = 3^k).
Zatim, odrediš je li koeficijent uz dominantni član različit od nule - ako jest, onda je rekurzija sigurno tog reda veličine. To radiš tako da ili iskoristiš početni uvjet, ili uvrstiš opće rješenje rekurzije u početni izraz.
Na kraju, provodiš supstituciju vice versa na način da ti je k = logaritam-s-bazom-tri-od-n. Riječ je o jednostavnom uvrštavanju... Česti trik koji se tu koristi jest a^logb = b^loga, prvenstveno u cilju toga da n nemaš u eksponentu. (npr. 3^logn = n^log3). :wink:
Ostatak zadatka se rješava na osnovu teorije sa str 54-62.
Jednostavno, nađeš opći oblik rekurzije za tk (dakle, nakon što provedeš supstituciju, npr n = 3^k).
Zatim, odrediš je li koeficijent uz dominantni član različit od nule - ako jest, onda je rekurzija sigurno tog reda veličine. To radiš tako da ili iskoristiš početni uvjet, ili uvrstiš opće rješenje rekurzije u početni izraz.
Na kraju, provodiš supstituciju vice versa na način da ti je k = logaritam-s-bazom-tri-od-n. Riječ je o jednostavnom uvrštavanju... Česti trik koji se tu koristi jest a^logb = b^loga, prvenstveno u cilju toga da n nemaš u eksponentu. (npr. 3^logn = n^log3).
Ostatak zadatka se rješava na osnovu teorije sa str 54-62.
_________________ ..pišem pjesme, sviram bluz, radost i tugu na stihove lomim.. |
|
| [Vrh] |
|
Atomised
Forumaš(ica)
Pridružen/a: 04. 09. 2007. (15:33:59)
Postovi: (399)16
Lokacija: Exotica
|
|
| [Vrh] |
|
YMP
Forumaš(ica)
Pridružen/a: 17. 04. 2009. (14:18:45)
Postovi: (1E)16
Lokacija: VINKOVCI
|
|
| [Vrh] |
|
(s)Venn
Forumaš(ica)
Pridružen/a: 18. 02. 2009. (17:59:25)
Postovi: (40)16
Lokacija: Velika Gorica
|
| Postano: 21:53 ned, 6. 11. 2011 Naslov: |
|
|
|
Ja mislim da je sve što trebaš napraviti, zaokružiti red veličine na n^2lgn, budući da ionako tražiš približnu vrijednost. Štoviše, mislim da i u integralu možeš koristiti n kao gornju granicu, budući da +-const ionako ne igra ulogu u ocjeni kompleksnosti u ovakvim slučajevima. :)
Ja mislim da je sve što trebaš napraviti, zaokružiti red veličine na n^2lgn, budući da ionako tražiš približnu vrijednost. Štoviše, mislim da i u integralu možeš koristiti n kao gornju granicu, budući da +-const ionako ne igra ulogu u ocjeni kompleksnosti u ovakvim slučajevima.
_________________ ..pišem pjesme, sviram bluz, radost i tugu na stihove lomim.. |
|
| [Vrh] |
|
|
