[es] - Java zadatak sa stringom

olp29
Dusan Punosevac
Senior Software Developer
Comtrade Group
Kragujevac

Član broj: 324655
Poruke: 14
*.dynamic.sbb.rs.

Sajt: rs.linkedin.com/in/dpunos..

+5 Profil

Re: Java zadatak sa stringom

^{14.10.2014. u 10:08 - pre 116 meseci}

@blakmor U pravu si. Koliko god da je ovo resenje meni "izgledalo" dobro, zapravo radi samo za odredjen broj slucaja. Kada se prica o valjanosti i sigurnosti da li je neki algoritam tacan ili ne, nakon ovih reci i pregleda ja to ne mogu da tvrdim za moje resenje. Ovo znaci da je moje resenje lose i ne radi u 100% slucajeva i da bi verovatno negde u firmi dobio od QA gomilu stvari da promenim i popravim. Ja nemam bas mnogo vremena u poslednje vreme ali cu poceti da resavam problem tvojim algoritmom, pa ako bas ne ide ja cu ti pustiti PM.

Sto se vozova tice, veoma zivopisno. Hvala. :)

@djoka_I U pravu si. Izvini. Moje resenje nije dobro kao sto napomenuh gore. Trenutno imam nekih obaveza na fakultetu i nekih intervjua, ali se nadam da cu do vikenda nakupiti vremena da krenem da slusam i radim kako je ovde predlozeno. Zato su ovi forumi odlicna stvar, uvek mozes da dobijes drugo ili pak trece misljenje.

Javljam kada i ako odradim nesto.

Pozdrav.

Dusan Punosevac

Odgovor na temu

blekmor
fax
fax

Član broj: 309532
Poruke: 55
*.dynamic.sbb.rs.

+30 Profil

Re: Java zadatak sa stringom

^{14.10.2014. u 16:17 - pre 115 meseci}

Bitno je naglasiti poslednju rečenicu koju je napisao djoka_l, da nakon nekoliko hiljada ovakvih eksperimenata možeš da se nadaš da program radi kako treba, ali ne možeš to da kažeš sa sigurnošću. Bitno je naglasiti tu činjenicu, jer se nekome može učiniti da nakon ovakvog eksperimenta može reći sa sigurnošću da mu algoritam radi. Da bi bio siguran da ti algoritam radi, a dokazuješ valjanost ovakvim eksperimentom, moraš ili izlistati sve moguće ulaze i izvršiti eksperiment za svaki mogući broj pomjeranja, ili nekako razbiti skup svih ulaza na klase ekvivalencije ili nešto slično. Izlistavanje svih mogućih ulaza i pomjeranja je prilično vremenski kompleksno, te je pitanje da li se uopšte može uraditi u nekom prihvatljivom vremenskom periodu.

@djoka_l
Druga stvar se tiče samog eksperimenta kojeg si ti napisao.
Ako izvršim k slučajnih transformacija, a moj algoritam mi izbaci rešenje r<=k, to ne znači da je r zaista najmanji mogući broj koraka, odnosno da algoritam radi kako treba.
Primjer:
1.Neka imamo ulaz 12345,
2.Neka je k = 3,
3.Neka se izvrši sledećni slučajan niz pomjeranja : 12345 -> 21345 -> 12345 -> 21354,
4.Neka algoritam rješi problem u r=3 koraka (npr, baš isti niz slučajnih koraka iz 3.)
Rješio si problem za r<=k koraka, ali to ne znači da ti je algoritam našao najmanji broj koraka potrebnih za rešavanje, jer se ovaj ulaz može rješiti sa jednim pomjeranjem.

@olp29
Piši ako budeš imao ikakvih pitanja ili slično

Pozdrav

Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3453

Jabber: djoka_l

+1462 Profil

Re: Java zadatak sa stringom

^{14.10.2014. u 18:57 - pre 115 meseci}

Ja se slažem sa tobom, blekmor, ali uz jednu veliku ogradu!

Pre svega ne volim Monte Karlo metodu. Moj profesor sa faksa je voleo da kaže (pokojni profesor Slavić): čuvajte se Monte Karla, grada i metode!
Međutim, pretpostavi da generišeš niz od 1000 znakova. Koliko treba da napraviš pomeranja, a da dva puta pomeriš isti element (sa verovatnoćom većom od 50%)? Odgovor je 30-35 (odnosno oko 1.2*sqrt(n)).

Dakle, za jako dugačke nizove i mali broj pomeranja, velika je verovatnoća da postoji samo jedno rešenje koje je optimalno i tačno ima broj koraka koliko si ti uradio puta slučajnu permutaciju. Zato sam rekao da će MOŽDA biti siguran POSLE NEKOLIKO HILJADA eksperimenata da je rešenje tačno.

Heuristika, sa druge strane, ne garantuje optimalno rešenje, zato što je prostor stanja ogroman.

Prednost Monte Karla, u ovom primeru, je u tome što možeš da uradiš hiljade AUTOMATSKIH eksperimenata i da ne razmišljaš mnogo o ishodu dokle god dobijaš "dobar" rezultat.

Odgovor na temu

olp29
Dusan Punosevac
Senior Software Developer
Comtrade Group
Kragujevac

Član broj: 324655
Poruke: 14
*.dynamic.sbb.rs.

Sajt: rs.linkedin.com/in/dpunos..

+5 Profil

Re: Java zadatak sa stringom

^{14.10.2014. u 19:14 - pre 115 meseci}

Znate kako, ja mislim da A* algoritam ne bi pruzio optimalno resenje kao ni bubble sort. Bubble sort bi pravio neka nepotrebna pomeranja. Znas vec o cemu pricam, da ne davim dublje.

Pozdrav.

Dusan Punosevac

Odgovor na temu

blekmor
fax
fax

Član broj: 309532
Poruke: 55
*.dynamic.sbb.rs.

+30 Profil

Re: Java zadatak sa stringom

^{15.10.2014. u 22:21 - pre 115 meseci}

@djoka_l
Ne možeš nikako "možda biti siguran", ili si siguran ili nisi. Ako si možda siguran, to znači da nisi siguran. Slažem se sa tobom da je velika vjerovatnoća da ti algoritam radi, ako uradiš eksperiment koji si ti predložio dovoljan broj puta. Poenta je samo u tome da ne možeš biti siguran. No, da ne cjepidlačim više, na istim smo "talasnim dužinama".

@olp29
Nema tu šta da se misli. Očigledno nisi pročitao tekstove koje sam ti poslao u mom drugom odgovoru na ovu temu. A* daje optimalno rešenje ako heuristička funkcija zadovoljava neke uslove.
Oprosti mi ako griješim, ali meni se čini da ti ovde nisi najbolje shvatio zadatak, odnosno šta je to minimalano/optimalano rješenje. Ne traži se da algoritam uradi optimalan broj koraka kako bi našao rješenje, nego da rešenje bude optimalno. To su dvije različite stvari. Optimalnost i efikasnost su dvije različite stvari. Neka je prvi string aba, a drugi string aab i neka algoritam "vrti" sledeće:
aba -> baa -> aba -> baa -> aba -> aab , i neka izbaci rešenje k = 1. Algoritam je uradio šta se od njega traži, odnosno našao je optimalan broj pomjeranja. To što mu je trebalo 5*k koraka kako bi on to izvrtio i zaključio, to nema veze.

Pomislio sam da mješaš ove pojmove zbog toga što si napisao da "babl sort bi pravio neka nepotrebna pomjeranja". Algoritam može da pomjera šta hoće i koliko hoće, ako na kraju izbaci tačno rešenje. Sa druge strane, algoritam koji si ti napisao povećava broj koraka kad god se izvrši neka zamjena, što me takodje navodi na zaključak da nisi baš najbolje suštinski razumio zadatak.

Odgovor na temu