[es] - Priprema za takmicenje?

peromalosutra
Ivan Rajkovic
Software engineer
Luxoft
Berlin

Član broj: 54774
Poruke: 871
*.dialup.blic.net.

+148 Profil

Priprema za takmicenje?

^{14.06.2005. u 23:44 - pre 229 meseci}

Pripremam se za takmicenje iz programiranja (Pascal) pa me zanima, posto sam relativno neupucen, sta bih sve iz teorije trebalo da znam. Moje iskustvo iz Pascala se svodi na pravljenje jednostavnijeih igrica (tipa zmijice) i "komercijalnih" programa (tel. imenika, baza podataka) sto i nema neke velike veze sa logikom. Na primjer nisam upoznat sa pojmom "DRVO" (jesam povrsno), za koji sam vidio da se dosta koristi u zadacima. Koju bi mi literaturu preporucili?
I glavno, da li to sve moze da se odradi za jedan ljetni raspust?!

HVALA!

Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.10.*

+1 Profil

Re: Priprema za takmicenje?

^{15.06.2005. u 00:07 - pre 229 meseci}

Da moze! Tu i bas nema velike teorije, mnoge stvari mozes i sam da provalis. Nazalost tvoje trenutno znanje nema velike veze sa takmicarskim zadacima. Sto se tice teorije grafova ona se pada tek na saveznom takmicenju, tako da ti je najbitnije u pocetku na naucis dinamicko programiranje. Kao sto reko, tu nemas teoriju vec je to samo jedan princip gde neko resenje svodis na trazenje manjih resenja. Npr. evo jednog banalnog primer:

Data je matrica

popunjena celim brojevima. Patuljak krece iz gornjeg levog ugla i treba stici u donje desno polje, ali tako da je ukupan zbir brojeva u poljima na koje stane patuljak maximalan. Patuljak moze da se krece na dole ili u desno.

Normalno, ovde da generises sve moguce puteve je stvarno glupo, jer broj tih puteva raste eksponencionalnom brzinom. E zato cemo probati da problem najveceg zbira matrice NxM svesti na neke manje matrice od nje, pa sasvim logicno dobijas da je najveci zbir od polja (1,1) do polja (N,M) jednak:

,
jer ti u polje (n,m) mozes doci samo reko polja (n,m-1) i polja (n-1,m) i naravno toj sumi dodas broj u polju (n,m)...

Pored dinamickog programiranja, traba na naucis neke koriste "algoritme" tipa: Binarna pretraga, QuickSort, Heap, LIS, LCS... Zatim tu imas i geometriju gde imas: Konveksi omotac, Point in Poly, Dve najblice tacke, Dve naudaljenije tacke...

Literatura:
[1] "Dinamicko programiranje", Milan Vugdelija
[2] "Algoritmi", Miodrag Zivkovic
[3] "Introduction to Algotirhms", Udi Manber
[4] i naravno da provezbas poslednjih 10-ak godina

Takodje preporucio bi na radis zadatke na online testeru USACO! Tamo je sve to postupno i odradjeno i objasnjeno tako da je za pocetnike super napravljeno...

Math is like love. A simple idea but it can get complicated.

Odgovor na temu

Danica Porobic
Novi Sad

Član broj: 13847
Poruke: 28
212.200.6.*

Profil

Re: Priprema za takmicenje?

^{15.06.2005. u 07:31 - pre 229 meseci}

Moram da se ne slozim oko literature, knjizica iz dinamickog je cist krsh, kao ima mnogo zadataka, ali su svi na isti fazon. Ako ti padne po ruku procitaj prvih dva-tri i poslednjih par, interesantni su, ostalo uzas... Sto se tice generalno knjige o algoritmima, na nasem jeziku nema skoro nista, a i to sto ima su neuspeli prevodi sa engleskog... Ako ozbiljno hoces da se pripremas (citaj savezno/olimpijada) uzmi Cormen, Leisseron, Rivest, Stein: "Introduction to Algorithms". Malo je teze, ali vredi se potruditi.
Svakako za pocetak treba raditi USACO (www.usaco.org), kad uradis prva dva dela, bice ti otprilike jasno da li te to zanima. Ako je odgovor DA, onda predjes na neku ozbiljnu knjigu (tipa introduction-a), a predlazem ti i sajt sa domacim takmicenjima iz prethodnih godina www.z-trening.com

Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
195.252.87.*

Profil

Re: Priprema za takmicenje?

^{15.06.2005. u 10:23 - pre 229 meseci}

Chek bre, shta fali onoj knjizi M. Zivkovica "Algoritmi"?

mmmmmm.. aahhhhhh..
e, nije sex nego serem!

Odgovor na temu

peromalosutra
Ivan Rajkovic
Software engineer
Luxoft
Berlin

Član broj: 54774
Poruke: 871
*.dialup.blic.net.

+148 Profil

Re: Priprema za takmicenje?

^{15.06.2005. u 10:38 - pre 229 meseci}

Sto se tice knjiga, za sada imam samo "Takmicenja iz informatike" (1995-1998) Dragana Urosevica sa rjesenim zadacima i to cu sad da obradjujem zadatak po zadatak. Hvala svima, >cassey< sad cu da googlam za

Citat:

Binarna pretraga, QuickSort, Heap, LIS, LCS... Konveksi omotac, Point in Poly, Dve najblice tacke, Dve naudaljenije tacke...

Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.10.*

+1 Profil

Re: Priprema za takmicenje?

^{15.06.2005. u 12:23 - pre 229 meseci}

Da, dobro stoji da gnjiga "Dinamicko programiranje" nije dobra, ali za pocetnika da uvidi sta je to uopste je dobra. Drugo, da "Algoritmi" su prevod "Intorudction to algorithms". Knjiga nije u celosti prevedena, ali dobrih 80% jeste. Nabavi jednu od tih knjiga (imas ih i na netu u pdf) i iz njih uci...

Math is like love. A simple idea but it can get complicated.

Odgovor na temu

Danica Porobic
Novi Sad

Član broj: 13847
Poruke: 28
212.200.6.*

Profil

Re: Priprema za takmicenje?

^{15.06.2005. u 14:53 - pre 229 meseci}

Citat:

RooTeR: Chek bre, shta fali onoj knjizi M. Zivkovica "Algoritmi"?

Los je prevod. A i zasto bi neko citao prevod, ako moze original. I jos su mu zadaci uglavnom na engleskom, osim ono malo na srpskom.

Citat:

peromalosutra: Sto se tice knjiga, za sada imam samo "Takmicenja iz informatike" (1995-1998) Dragana Urosevica sa rjesenim zadacima i to cu sad da obradjujem zadatak po zadatak.7

Iskreno, ovo ti ne preporucujem. Ja sam kupila knjigu, otvorila, procitala prva tri zadatka, a zatim okrenula na resenja... U prva dva zadatka sam videla vise od pet nepoznatih pojmova, a objasnjenja su tipa: "ovo je cist primov algoritam". Googlanje "Primov algoritam" ce te momentalno odvesti na granicu samoubistva... Isto vazi i za veliku vecinu ostalih ovde pomenutih algoritama...

Ima dosta vremena do takmicenja, bolje idi polako, nego da ti se takmicenja smuce vec na pocetku... Mozda je dobro da nadjes nekog iz tvoje skole/grada ko je bio dobar na takmicenjima da ti kaze kako se najbolje pripremiti za konkretno takmicenje... Za sta se pripremas?

Odgovor na temu

peromalosutra
Ivan Rajkovic
Software engineer
Luxoft
Berlin

Član broj: 54774
Poruke: 871
*.dialup.blic.net.

+148 Profil

Re: Priprema za takmicenje?

^{15.06.2005. u 16:51 - pre 229 meseci}

Pa ne znam ni ja, profesorica informatike je odabrala nas nekoliko iz skole da se pripremamo za to takmicenje pa dokle ko dogura. Organizacija je nikakva, nema nigdje da se pita ono sto te interesuje, zato u ostalom i visim na ovom forumu.

Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
195.252.87.*

Profil

Re: Priprema za takmicenje?

^{15.06.2005. u 17:45 - pre 229 meseci}

Ovaj Danice, jel bi mogla da mi dash taj original da fotokopiram? :)

mmmmmm.. aahhhhhh..
e, nije sex nego serem!

Odgovor na temu

Danica Porobic
Novi Sad

Član broj: 13847
Poruke: 28
212.200.6.*

Profil

Re: Priprema za takmicenje?

^{15.06.2005. u 18:05 - pre 229 meseci}

Rajko, zar preko foruma podstices pirateriju...cccccc

Javi se na mail/sms/fixni/pricaj s mojim bratom (preporucujem)...

Da se vratim na temu, reci koje je takmicenje tacno u pitanju i kada se odrzava, ako nam das neke zadatke s prethodnih takmicenja mocicemo i da ti pomognemo. Mozda nije ova vrsta takmicenja, mozda je nesto multimedijalno (kao siemens-ov JM, ili ovaj novi MS-ov Imagine Cup).

Odgovor na temu

Srđan Krstić
Srđan Krstić
Princeton, NJ

Član broj: 7526
Poruke: 416
*.rcub.bg.ac.yu.

Jabber: srkiboy@elitesecurity.org
ICQ: 193836365
Sajt: www.princeton.edu/~skrsti..

Profil

Re: Priprema za takmicenje?

^{15.06.2005. u 18:16 - pre 229 meseci}

Ma svako ce da ti prica drugu pricu...

Evo ja cu da ti kazem, vec je receno, ali i iz mog iskustva, pocni sa knjigom Udi Manbera - Introduction to algorithms, a creative approach. I sama ova rec "creative" u nazivu knjige kaze da nije nesto suvoparno i neshvatljivo, lako se cita, i u potpunosti se slazem da joj prevod (algoritmi) nije ni do kolena.

I HAD A NIGHTMARE
IT ALL STARTED NORMAL
10101010
10110011
THEN ALL OF A SUDDEN
1100102
GAAAAH
_____________________________
www.princeton.edu/~skrstic
www.niwifi.co.sr

Odgovor na temu

peromalosutra
Ivan Rajkovic
Software engineer
Luxoft
Berlin

Član broj: 54774
Poruke: 871
*.dialup.blic.net.

+148 Profil

Re: Priprema za takmicenje?

^{17.06.2005. u 12:56 - pre 229 meseci}

A ima li neka dobra knjiga na tu temu u PDF formatu, da moze da se skine sa interneta? Sad sam trazio "Introduction to algorithms", pa nisam uspio naci nista upotrebljivo.

Odgovor na temu

Danica Porobic
Novi Sad

Član broj: 13847
Poruke: 28
212.200.7.*

Profil

Re: Priprema za takmicenje?

^{17.06.2005. u 17:46 - pre 229 meseci}

Potrazi na nekom emule-u, kazaa ili slicnom. Ima sigurno. Imam ja, ali je malo velik fajl 13.9 MB, u djvu formatu, koji je malo bolji za kompresiju od pdf-a a skoro jednako upotrebljiv. Ali introduction uopste nije naivan, to je jaci undergraduate kurs na MIT-u, a ne nesto od cega se pocinje. Pogledaj ti prvo usaco...

Odgovor na temu

D3adly

Član broj: 43272
Poruke: 35
*.net.t-com.hr.

ICQ: 281458481

Profil

Re: Priprema za takmicenje?

^{21.06.2005. u 10:45 - pre 229 meseci}

Jedno malo pitanje za koje mi se ne isplati otvarati novi topic, a donekle se tiče ove teme: postoje li još koji dobri online testeri kao što su ACM, USACO i Ztrening ( osim ovih navedenih)?

#include <D3adly.h>

Odgovor na temu