| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
ivanzub
Forumaš(ica)
Pridružen/a: 08. 02. 2006. (11:16:46)
Postovi: (CC)16
|
|
| [Vrh] |
|
arya
Forumaš(ica)
Pridružen/a: 30. 11. 2006. (20:10:37)
Postovi: (233)16
Spol: 
Lokacija: forum
|
|
| [Vrh] |
|
desire
Forumaš(ica)
Pridružen/a: 06. 09. 2007. (07:46:21)
Postovi: (133)16
Spol: 
|
|
| [Vrh] |
|
arya
Forumaš(ica)
Pridružen/a: 30. 11. 2006. (20:10:37)
Postovi: (233)16
Spol:
Lokacija: forum
|
|
| [Vrh] |
|
j.b.i.n.s.h.
Forumaš(ica)
Pridružen/a: 24. 06. 2007. (10:28:11)
Postovi: (1B)16
|
|
| [Vrh] |
|
arya
Forumaš(ica)
Pridružen/a: 30. 11. 2006. (20:10:37)
Postovi: (233)16
Spol:
Lokacija: forum
|
|
| [Vrh] |
|
Mala_022
Forumaš(ica)
Pridružen/a: 21. 01. 2006. (18:15:12)
Postovi: (73)16
Spol:
Lokacija: ...evo mene među moje...
|
|
| [Vrh] |
|
Feanor
Forumaš(ica)
Pridružen/a: 15. 11. 2005. (18:18:15)
Postovi: (27)16
Spol: 
Lokacija: Zagreb/Bjelovar
|
|
| [Vrh] |
|
arya
Forumaš(ica)
Pridružen/a: 30. 11. 2006. (20:10:37)
Postovi: (233)16
Spol:
Lokacija: forum
|
|
| [Vrh] |
|
Feanor
Forumaš(ica)
Pridružen/a: 15. 11. 2005. (18:18:15)
Postovi: (27)16
Spol:
Lokacija: Zagreb/Bjelovar
|
|
| [Vrh] |
|
arya
Forumaš(ica)
Pridružen/a: 30. 11. 2006. (20:10:37)
Postovi: (233)16
Spol:
Lokacija: forum
|
|
| [Vrh] |
|
Feanor
Forumaš(ica)
Pridružen/a: 15. 11. 2005. (18:18:15)
Postovi: (27)16
Spol:
Lokacija: Zagreb/Bjelovar
|
|
| [Vrh] |
|
arya
Forumaš(ica)
Pridružen/a: 30. 11. 2006. (20:10:37)
Postovi: (233)16
Spol:
Lokacija: forum
|
|
| [Vrh] |
|
Feanor
Forumaš(ica)
Pridružen/a: 15. 11. 2005. (18:18:15)
Postovi: (27)16
Spol:
Lokacija: Zagreb/Bjelovar
|
|
| [Vrh] |
|
arya
Forumaš(ica)
Pridružen/a: 30. 11. 2006. (20:10:37)
Postovi: (233)16
Spol:
Lokacija: forum
|
|
| [Vrh] |
|
Iv
Forumaš(ica)
Pridružen/a: 16. 02. 2007. (00:16:42)
Postovi: (1E)16
Spol:
|
|
| [Vrh] |
|
j.b.i.n.s.h.
Forumaš(ica)
Pridružen/a: 24. 06. 2007. (10:28:11)
Postovi: (1B)16
|
|
| [Vrh] |
|
anekalo
Forumaš(ica)
Pridružen/a: 05. 03. 2007. (16:48:54)
Postovi: (55)16
|
|
| [Vrh] |
|
bose
Forumaš(ica)
Pridružen/a: 20. 02. 2008. (19:03:41)
Postovi: (2)16
|
|
| [Vrh] |
|
ß
Forumaš(ica)
Pridružen/a: 29. 07. 2006. (15:29:06)
Postovi: (115)16
Spol:
Lokacija: Graveyard Mountain Home
|
 Postano: 23:51 sri, 27. 2. 2008 Naslov: |
    |
|
|
Evo ovako, da vidim koliko znam za sutra :)
[quote="anekalo"]Sto bih napisati za prednosti imane hash tablica?[/quote]
Prednost je da, ako sve radi kako treba, vrijeme za izvrsit pojedine operacije je minimalno (kod zatvorenog hasha i dobro "razbacane" tablice uglavnom O(1), kod otvorenog O(N/B)). Mane su što dosta toga može poć u krivom smjeru :)
Recimo, kod svakog hashiranja je problem ako hash funkcija nije takva da ravnomjerno rasporedjuje elemente. Dakle, treba pronaći dobru hash funkciju, a i opet ne možeš biti siguran da će unešeni elementi stvarno biti takvi da se najoptimalnije rasporede u tablicu.
Također, zatvoreno hashiranje ima manu da je maksimalna veličina polja koje ga sadrži unaprijed određena, pa ako dođe do prepunjenja... bude svašta :D
[quote="anekalo"]
-Kada dinamicko programiranje ne daje optimalno rjesenje?
[/quote]
Hm, ne znam. Kad ne definiraš dobro problem? :P
Generalno, dinamičko programiranje dobro je primjenjivati u slučajevima kad problem možeš razbiti u više jednostavnijih, istovrsnih početnom (hint:rekurzija). Ono što čini dinamičko programiranje primjenjivijim nego recimo metodu "podijeli pa vladaj" (koja ima iste početne pretpostavke na prirodu problema), je u tome što vrlo često treba više puta računati iste vrijednosti za određenu funkciju. Rješenje je u pospremanju podataka u tablicu, pa ti onda treba manje koraka, i sve ostale lijepe stvari u vezi s tim. Uglavnom, dinamičko programiranje, ako je početna rekurzivna formula dobro definirana, i sve korektno iskodirano, treba dati optimalno rješenje. Problem je jedino ako je tablica jaaako velika i ne stane u memoriju, ali to je već nešto što smo uglavnom ignorirali :)
[quote="anekalo"]
-Kada podijeli pa vladaj ne daje optimalno rjeseje?
[/quote]
Vidi gore. Opet vrijedi da "podijeli pa vladaj" daje, u konačnici, isto rješenje kao algoritam kreiran metodom dinamičkog programiranja (to nisu vrste problema u kojima se traži više ili manje optimalno konačno rješenje, ono je najčešće jedinstveno.) Opet, metoda "podijeli pa vladaj", kao što sam gore napisao (ali vrijedi ponovit) je vrlo slabo primjenjiva ako treba više puta pozivati funkciju s istom vrijednosti (primjer: Fibonaccijevi brojevi, imaš još toga [url=http://web.math.hr/nastava/spa/files/SPA%20--%20vjezbe%20--%2006%20--%20Algoritmi.pdf]ovdje[/url])
[quote="anekalo"]
INSERTION SORT- sto reci vise o njemu
[/quote]
Ajoj. Ovo je naporno. Ima valjda negdje u skripti ili onim vježbama na webu, a u krajnjem slučaju [url=www.justfuckinggoogleit.com]google[/url] is your friend :D
[quote="anekalo"]
-Kako radi algoritam za sazimanje listi pomocu hrpe
[/quote]
Ovako radiš: ubacuješ prvi element svake liste u hrpu - bitno je da, uz [i]vrijednost[/i] samog elementa koju uspoređuješ, čuvaš i podatak [i]iz koje liste[/i] je element došao. Zatim pozivaš DELETE_MIN i izbacuješ najmanji element iz hrpe, a u hrpu dodaješ sljedeći element [b]iz iste liste[/b] (iz koje je bio ovaj izbačeni najmanji). Zatim opet izbacuješ najmanji element iz hrpe i ubacuješ nazad sljedeći iz liste iza tog izbačenog (imaš neke kursore koji pokazuju na kojem si mjestu u svakoj od listi).
Znači, u svakom trenutku je u hrpi onoliko elemenata koliko ima listi, minus one kod kojih je kursor došao do kraja. Kad se isprazni hrpa, voila. Doduše, na ispitu najvjerojatnije (ako i ponove takav zadatak) nećeš morati izvesti sve do kraja, jer ima puno koraka, nego dok rezultantna lista ne dobije kojih 5-6 elemenata.
Nadam se da je ovo pomoglo...
Evo ovako, da vidim koliko znam za sutra 
| anekalo (napisa): | | Sto bih napisati za prednosti imane hash tablica? |
Prednost je da, ako sve radi kako treba, vrijeme za izvrsit pojedine operacije je minimalno (kod zatvorenog hasha i dobro "razbacane" tablice uglavnom O(1), kod otvorenog O(N/B)). Mane su što dosta toga može poć u krivom smjeru
Recimo, kod svakog hashiranja je problem ako hash funkcija nije takva da ravnomjerno rasporedjuje elemente. Dakle, treba pronaći dobru hash funkciju, a i opet ne možeš biti siguran da će unešeni elementi stvarno biti takvi da se najoptimalnije rasporede u tablicu.
Također, zatvoreno hashiranje ima manu da je maksimalna veličina polja koje ga sadrži unaprijed određena, pa ako dođe do prepunjenja... bude svašta 
| anekalo (napisa): |
-Kada dinamicko programiranje ne daje optimalno rjesenje?
|
Hm, ne znam. Kad ne definiraš dobro problem? 
Generalno, dinamičko programiranje dobro je primjenjivati u slučajevima kad problem možeš razbiti u više jednostavnijih, istovrsnih početnom (hint:rekurzija). Ono što čini dinamičko programiranje primjenjivijim nego recimo metodu "podijeli pa vladaj" (koja ima iste početne pretpostavke na prirodu problema), je u tome što vrlo često treba više puta računati iste vrijednosti za određenu funkciju. Rješenje je u pospremanju podataka u tablicu, pa ti onda treba manje koraka, i sve ostale lijepe stvari u vezi s tim. Uglavnom, dinamičko programiranje, ako je početna rekurzivna formula dobro definirana, i sve korektno iskodirano, treba dati optimalno rješenje. Problem je jedino ako je tablica jaaako velika i ne stane u memoriju, ali to je već nešto što smo uglavnom ignorirali
| anekalo (napisa): |
-Kada podijeli pa vladaj ne daje optimalno rjeseje?
|
Vidi gore. Opet vrijedi da "podijeli pa vladaj" daje, u konačnici, isto rješenje kao algoritam kreiran metodom dinamičkog programiranja (to nisu vrste problema u kojima se traži više ili manje optimalno konačno rješenje, ono je najčešće jedinstveno.) Opet, metoda "podijeli pa vladaj", kao što sam gore napisao (ali vrijedi ponovit) je vrlo slabo primjenjiva ako treba više puta pozivati funkciju s istom vrijednosti (primjer: Fibonaccijevi brojevi, imaš još toga ovdje)
| anekalo (napisa): |
INSERTION SORT- sto reci vise o njemu
|
Ajoj. Ovo je naporno. Ima valjda negdje u skripti ili onim vježbama na webu, a u krajnjem slučaju google is your friend
| anekalo (napisa): |
-Kako radi algoritam za sazimanje listi pomocu hrpe
|
Ovako radiš: ubacuješ prvi element svake liste u hrpu - bitno je da, uz vrijednost samog elementa koju uspoređuješ, čuvaš i podatak iz koje liste je element došao. Zatim pozivaš DELETE_MIN i izbacuješ najmanji element iz hrpe, a u hrpu dodaješ sljedeći element iz iste liste (iz koje je bio ovaj izbačeni najmanji). Zatim opet izbacuješ najmanji element iz hrpe i ubacuješ nazad sljedeći iz liste iza tog izbačenog (imaš neke kursore koji pokazuju na kojem si mjestu u svakoj od listi).
Znači, u svakom trenutku je u hrpi onoliko elemenata koliko ima listi, minus one kod kojih je kursor došao do kraja. Kad se isprazni hrpa, voila. Doduše, na ispitu najvjerojatnije (ako i ponove takav zadatak) nećeš morati izvesti sve do kraja, jer ima puno koraka, nego dok rezultantna lista ne dobije kojih 5-6 elemenata.
Nadam se da je ovo pomoglo...
_________________
Devious movements in your eyes moved me from relief
Breath comes out white clouds with your lies
and filters through me
|
|
| [Vrh] |
|
|
