[ DuX @ 21.08.2002. 02:25 ] @
Evo jednog, nadam se, zanimljivog problema. Ja se vec godinu dana patim sa njim (doduse, ne intenzivno) i stvarno ne znam gde jos nisam pitao. Istina, problem mi se cini poznatim, definitivno je tipski, a i veoma podseca na neki od zadataka sa recimo ACM takmicenja. Nevolja je sto ja bas i nemam bogzna kako bogatu literaturu iz teorije algoritama, a na net-u nisam uspeo nista da iskopam. Rezultat nije bio nista povoljniji ni u slucaju ES foruma "Art of Programming" kao i nekih stranih news grupa koje se bave slicnom tematikom. Program za koji mi je ovo trebalo verovatno i nema neku upotrebnu vrednost, ali me zivo interesuje (sada samo teoretsko) resenje problema. Posto se zadatak pogresno prelama (i pored `code' tagova u poruci), zakacio sam ga uz poruku, a najnoviju "verziju" uvek mozete naci na: http://tesla.rcub.bg.ac.yu/~dux64/algo/x-rle.txt. Problem (zamalo) spada u kategoriju neresivih (bar njegova optimalna solucija) jer je slozenost algoritma oko 2^N (ili veca). Ne trazim gotovo resenje, potrebna mi je samo pomoc oko heuristike; interesuje me da li postoje bilo kakve zakonitosti koje bi mogle znacajno (zapravo, drasticno) da smanje broj pokusaja/proba prilikom ispitivanja, a samim tim i vreme potrebno za pronalazenje optimalne kombinacije. Posto je problem kombinatorne prirode, mislim da se moze naci i na jednom ovakvom, strogo-matematickom forumu ("okoreli" matematicari neka mi ne zamere, oni mogu posmatrati kompresiju kao `k(x)' i sl.). Hvala unapred. $dux |