Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Minimalna duzina najveceg sortiranog podniza

[es] :: Matematika :: Minimalna duzina najveceg sortiranog podniza

[ Pregleda: 2781 | Odgovora: 11 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

darkosos
Darko Šoš
Beograd

Član broj: 5053
Poruke: 1131
46.240.140.*



+64 Profil

icon Minimalna duzina najveceg sortiranog podniza30.06.2014. u 08:54 - pre 122 meseci
Da li bi ovako nesto moglo da se dokaze:
za svaki niz celih brojeva duzine n postoji podniz duzine kada je n parno, odnosno kada je n neparno, koji je sortiran - bilo neopadajuce ili nerastuce
?

Priznajem da nisam posebno pokusavao da nadjem dokaz :) Motiv je nastao kada sam bistrio algoritme za sortiranje, gde mi je zapao za oko tzv. Natural Merge. Poenta je da se iskoristi to da je deo niza vec sortiran, uradi dekompozicija niza i zatim stapanje (merge) sortiranih delova. Sa matematicke tacke gledista, ako je moja pretpostavka tacna, onda je bar pola svakog niza vec sortirano, pa bi se geometrijskom brzinom doslo do ove dekompozicije. Naravno, zackoljica je ovde efikasan algoritam za pronalazenje tog najveceg sortiranog podniza. Manji tehicki problem je to sto taj moze da bude i suprotnog smera od zeljenog sorta, ali to je sitnica, samo ga treba procitati unazad.

Eto, pa ako je neko zainteresovan, moze da da prilog.
 
Odgovor na temu

Sonec

Član broj: 284879
Poruke: 892



+332 Profil

icon Re: Minimalna duzina najveceg sortiranog podniza30.06.2014. u 11:17 - pre 122 meseci
Ja ne znam nesto posebno o datom problemu, ali brz search me je doveo do Longest_increasing_subsequence_problem, odnosno do takozvane Erdős–Szekeres teoreme. Takodje, ovde mozes naci i neke rezultate povezana sa njom. Ovo ovako na brzinu, al msm da mozes sam uz pomoc gugla da nadjes jos povezanih rezultata, a i verujem da Bojan i Nedeljko znaju dosta vise o samom problemu. Meni se ipak cini prema ovome sto sam pogledao da je tvoj zahtev previse optimistican (mada ti zelis neopadajuci/nerastuci niz, pa mozda i ima mesta za nadogradnju (il pak ne (u sta verujem), but we will see)).
Leonardo da Vinči

Nema istine u onim naukama u kojima se matematika ne primenjuje.

Milorad Stevanović

Bog postoji zato sto je matematika neprotivurečna.
 
Odgovor na temu

darkosos
Darko Šoš
Beograd

Član broj: 5053
Poruke: 1131
46.240.140.*



+64 Profil

icon Re: Minimalna duzina najveceg sortiranog podniza30.06.2014. u 11:43 - pre 122 meseci
Da, izgleda da jesam bio preoptimistican, mada je osnovna ideja naci taj najduzi podniz i na osnovu toga napraviti algoritam za sortiranje. Tu nije toliko bitno koliki je taj najduzi podniz, ove procene su bile vise intuitivne. Ono sto sam hteo da dobijem je neka procena efikasnosti algoritma, ali ocigledno da se nisam dovoljno raspitao :) Algoritam bi bio: nadji najduzi sortirani podniz, stavi u neki niz; sa ostatkom radi isto dok ne potrosis sve elemente; uradi merge dobijenih nizova. Zbog ustede prostora, merge moze da se radi cim se naprave dva podniza i onda uvek imamo najvise 3 aktivna.
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1369
*.WiMAX.Verat.NET.



+564 Profil

icon Re: Minimalna duzina najveceg sortiranog podniza30.06.2014. u 16:50 - pre 122 meseci
Citat:
darkosos:
Da li bi ovako nesto moglo da se dokaze:
za svaki niz celih brojeva duzine n postoji podniz duzine kada je n parno, odnosno kada je n neparno, koji je sortiran - bilo neopadajuce ili nerastuce
?


Bio si preoptimistican: za deset brojeva od 0 do 9 n/2 je 5 a u nizu: 7894561230 najduzi neopadajuci podniz je duzine 3 a nerastuci duzine 4, odnosno obrnuto ako citas unazad, tako da ces n/2 tesko da dokazes za bilo koji/svaki niz...

PozZ!
Nemoj da pricas?
 
Odgovor na temu

darkosos
Darko Šoš
Beograd

Član broj: 5053
Poruke: 1131
95.180.32.*



+64 Profil

icon Re: Minimalna duzina najveceg sortiranog podniza30.06.2014. u 18:03 - pre 122 meseci
Da, to smo vec konstatovali. U principu, ona madjarska teorema sto je dao link Sonec, daje odgovor na to pitanje. Jos cu malo pogledati to. Ako stignem da se posvetim malo ovome, trebalo bi uraditi sledece: ispitati teorijsku dobit nalazenja maksimalnog sortiranog podniza (ili vise njih), uzeti u obzir postojece alogritme za odredjivanje ovakvog podniza i konacno proceniti kompleksnost algoritma koji ovo koristi. Mislim, mozda tu nema niceg posebnog, ali eto nekako me vuce misao na tu stranu... Kad pogledam malo realnije, nije ovo tako mala tema, niti je od juce, tako da mogucnost da se tu nesto uradi ovako amaterski je veoma mala :)
 
Odgovor na temu

zzzz
milan kecman
bluka

Član broj: 11810
Poruke: 2156
..able.dyn.broadband.blic.net.



+197 Profil

icon Re: Minimalna duzina najveceg sortiranog podniza01.07.2014. u 00:40 - pre 122 meseci
Nekad davno kad sam na "Comodoreu" nešto sortirao sa onim programom BASIC to je išlo pomoću poređenja dva susjedna člana.Pa zamjena njihovih mjesta ako nisu bila redosljedno korektna.I tako polako od početka do kraja niza.Pa onda opet ispočetka dok se ne desi da od početka do kraja nema zamjena.To je išlo dosta brzo,a pogotovo ako se program ispiše u "mašinskom" obliku.Ja mislim da se tako nešto koristi i sada.
Meni izgleda da bi pretragom i uočavanjem parcijalnih dijelova koji su korektno sortirani samo zakomplicirali i dodatno usporili posao. Naprimjer 2,7,9,15,22,1,8,10,11,25. imamo prvi dio 2,7,9,15,22 i drugi 1,8,10,11,25 koji se nezgodno preklapaju.(Ako sam dobro shvatio ideju?)
________________________________

Najbolja kritika formule za Sagnac effect:
https://www.omicsonline.org/op...090-0902-1000189.php?aid=78500

OK evo prave formule:P=2wft^2 [period]
 
Odgovor na temu

darkosos
Darko Šoš
Beograd

Član broj: 5053
Poruke: 1131
46.240.140.*



+64 Profil

icon Re: Minimalna duzina najveceg sortiranog podniza01.07.2014. u 07:26 - pre 122 meseci
Da, to je ideja. Ja sam prilicno naivno krenuo u ovo, bio sam prvo upucen na Quick Sort, ali mi se nesto tu nije dopalo i tako sam smislio nesto drugacije, sto se ispostavilo da je Natural Merge sort. Taj algoritam mi se ucinilo da moze jos da se poboljsa ako se trazi taj najveci sortirani podniz. Naravno trazenje najveceg sortiranog podniza bi dodalo nesto na broj operacija koje su izvrsene, ali bi trebalo da smanji broj stapanja. To je bila moja ideja. Da li bi ovo zaista donelo nesto. nemam pojma.

Pogledaj Algoritme sortiranja. Merge sort je jedan od najefikasnijih algoritama za sortiranje (od onih koji koriste samo uporedjivanje).
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1369
*.WiMAX.Verat.NET.



+564 Profil

icon Re: Minimalna duzina najveceg sortiranog podniza01.07.2014. u 15:43 - pre 122 meseci
@ darkosos Napisao si "izgleda" da sam bio preoptimistican, pa reko' da nisi siguran :)
Nemoj da pricas?
 
Odgovor na temu

darkosos
Darko Šoš
Beograd

Član broj: 5053
Poruke: 1131
46.240.140.*



+64 Profil

icon Re: Minimalna duzina najveceg sortiranog podniza03.07.2014. u 11:41 - pre 122 meseci
Naravno da nisam siguran :)

Elem, izgleda da tu nema nicega. Samo da dodam, kad sam vec zapoceo ovo:

na osnovu pomenute teoreme, ako zelimo podniz od sortiranih clanova niza (u bar jednom od smerova), potreban je niz duzine bar . To naravno ne znaci da neki niz nema i vise, moze biti i potpuno sortiran. Evo kako to izgleda za nekoliko manjih brojeva:

2 do 4 clana - ima bar 2 sortirana (n=1)
5 do 9 clanova - ima bar 3 sortirana (n=2)
10 do 16 clanova - ima bar 4 sortirana (n=3)
itd..., gde je broj potrebnih clanova niza odredjen uslovom .

Primer 3,2,1,6,5,4,9,8,7 je u granicni u tom smislu da jedan vise clan niza znaci i za jedan duzi sortirani podniz. Naravno, primenjujuci istu stvar na ostatak niza, dolazimo do razbijanja niza na sortirane podnizove, sto je bila originalna ideja. Evo jedne ilustracije, za niz od 9 clanova:
9 clanova znaci bar jedan sortirani podniz od 3 clana; izuzmemo ta 3 clana, ostaje 6
6 clanova takodje znaci bar jedan sortirani podniz od 3 clana; ostaje jos 3
3 clana znaci bar jedan sortirani duzune 2; ostaje jedan element;
Dakle, distribucija u ovom slucaju izgleda 3 + 3 + 2 + 1. Ovo je naravno najgori slucaj (cela prica se vodi o tome). Koristan citat:
Citat:
For inputs in which each permutation of the input is equally likely, the expected length of the longest increasing subsequence is approximately


To je otprilike to, koga interesuje, ima vise na ovoj wiki stranici.
 
Odgovor na temu

blekmor
fax
fax

Član broj: 309532
Poruke: 55
*.teol.net.



+30 Profil

icon Re: Minimalna duzina najveceg sortiranog podniza09.07.2014. u 01:26 - pre 122 meseci
Ok je ideja, zanimljiva za diskusiju.
Algoritmi koji se zasnivaju na poredjenju elemenata medjusobnom ne mogu da probiju granicu O(nlogn). Činjenica da postoji tako "optimistično" duga sekvenca sortiranih elemenata ne bi mogla da zamjeni poredjenja elemenata, ili bi mogla? Moraš proći kroz niz, kako god. Jedino možda nekada ne bi morao da prolaziš kroz "kraj" niza, ukoliko se ispostavi da "kraj" mora biti sortiran samo na osnovu analiza prethodnih članova, što bi možda bio čest slučaj, pod pretpostavkom da je "optimistična" pretpostavka tačna?
Quicksort, u praksi, daje bolje rezultate u odnosu na mergesort, iako je worst-case merge-a bolji u odnosu na worst-case quick-a. Naravno, oba su u prosjeku asimptotski optimalna(kada pričamo o comparison-based algoritmima)

Ako je neko zainteresovan, možemo da diskutujemo na sledeću temu,
Pretpostavimo da je "optimistična" pretpostavka tačna(ili je oslabimo malo). Kako bi se to moglo iskoristiti? Konstruiši algoritam koji je brži od quicksort ili mergesort.

Pozdrav
 
Odgovor na temu

darkosos
Darko Šoš
Beograd

Član broj: 5053
Poruke: 1131
46.240.140.*



+64 Profil

icon Re: Minimalna duzina najveceg sortiranog podniza09.07.2014. u 08:32 - pre 122 meseci
@blekmor (ritchie?)

Pa, na zalost, krenuo sam ovu temu previse naivno, iako osnovna ideja jeste da se iskoristi znanje od postojecim sortiranim podnizovima. Kao sto je vec vise puta receno, ono sto sam napisao na pocetku nema sanse :) S' druge strane, interesantna je cinjenica u vezi ocekivane duzine sortiranog podniza (). Ta procena i nije tako losa. Postoji mozda jedna slicna stvar, http://en.wikipedia.org/wiki/Patience_sorting. Ovaj algoritam na izvestan nacin koristi sortirane podnizove, iako nema merge deo. Pritom ne mislim na cinjenicu da taj algoritam efektivno nalazi najduzi sortirani podniz, jer je to njegov produkt a ne nesto sto se koristi u samom algoritmu.

Svakako nisam mislio da ne prolazim kroz niz. Ovde ima neko objasnjenje zasto je granica bas O(n log n).

Pravo pitanje jeste kako iskoristiti postojece sortirane podnizove, imam neke ideje, pa ako napravim nesto, napisacu ovde.
 
Odgovor na temu

darkosos
Darko Šoš
Beograd

Član broj: 5053
Poruke: 1131
46.240.140.*



+64 Profil

icon Re: Minimalna duzina najveceg sortiranog podniza18.07.2014. u 12:54 - pre 121 meseci
Evo jedne male analize merge sorta, koja verovatno ima objašnjena po mnogim knjigama, ali eto, time sam se bavio ovih dana, pa da zapišem.

1. Najveći broj poređenja u stapanju dva sortirana niza u novi sortirani niz je jednak zbiru njihovih dužina manje jedan.
ovo će se najlakše videti iz algoritma stapanja, neka su datu nizovi A i B, i recimo da sortiramo u neopadajućem poretku
1. postavimo indekse oba niza na 1 (recimo da je indeks prvog člana niza 1), i=1, j=1
2. uporedimo A(i] sa B[j]
3. manji od ta dva stavimo u rezultujući niz, i pomerimo indeks onog niza čiji je element manji (ako povećanje za jedan ne prelazi dužinu niza)
4. ponavljamo 2. 3. dok nismo došli ili do kraja niza A ili do kraja niza B
5. ostatak (ako ga ima, a može biti samo na jednom od nizova) dodamo na formirani niz

U najgorem slučaju je i jednako dužini niza A a j dužini niza B. U svakom koraku, (osim u prvom) smo uradili jedno povećanje i ili j, i jedno poređenje. Odavde se vidi da je broj poređenja jednak i+j-1, dakle koliko pomeranja po nizovima toliko i provera, osim u prvom koraku kada imamo jednu proveru, a postavljanje oba indeksa.

Kako bi to izgledalo za niz koji je Milan (zzzz) dao? Podnizove 2,7,9,15,22 i 1,8,10,11,25 bi dakle mogli da stopimo u 5+5-1 = 9 koraka!

Naravno, generalno, stapanja u ovom algoritmu ne mora da bude samo dva, i postavlja se pitanje da li ima neke veze kojim redom vršimo stapanja? Ako smo recimo razbili skup na sortirane podnizove od 4, 3, 2, 1 element (mislim na nešto tipa [a,b,c,d], [e,f,g], [h,i], [j]), kako izvršiti stapanja? Hajde baš navedenim redom:
4+3-1 = 6 poređenja, sa rezultujućim nizom od 7 elemenata
7+2-1 = 8 poređenja, 9 el.
9+1-1 = 9 poređenja, 10 el., što daje ukupno 23 poređenja. Može li bolje?

Da, ako krenemo od manjih podnizova, redosledom 1, 2, 3, 4 elementa:
1+2-1 = 2:3 (2 por., 3 el.)
3+3-1 = 5:6
6+4-1 = 9:10, što daje samo 16 poređenja!

Ova razlika se može objasniti na sledeći način: svaki put stapamo dva podniza, i u svakom koraku se vrši kumulativno stapanje sa narednim. Tako oni koji su ranije stopljeni više puta učestvuju u narednim stapanjima, pa bi taktika bila da se prvo stapaju manji podnizovi pa sve veći. Uostalom, rezultat se dobija sabiranjem parcijalnih suma, umanjenim za jedan. U slučaju 4,3,2,1 to je 7-1 + 9-1 + 10-1 = 6+8+9, a u slučaju 1,2,3,4 to je 3-1 + 6-1 + 10-1 = 2+5+9.

Naravno, originalni merge algoritam ne radi ovako, već rekurzivno lomi niz na podjednake delove (za paran broj elemenata su isti, za neparne je jedan veći za jedan), pa se stapanje vrši uvek na najnižem nivou i time obezbeđuje optimalnost (ovo nisam proverio, ali tako izgleda). Ali, ovde je priča o tome da nemamo slepo deljenje niza, već neko koje nam kasnije može obezbediti bolje rezlutate. Iako slepo deljenje niza ima tu prednost što ne košta ništa, makar ne u smislu broja poređenja.

Ovo je neki odgovor na pitanje šta bi radili ako bi imali te sortirane podnizove. Drugi deo priče je kako doći do njih i koliko to košta? Ispisao sam brdo primera i nisam došao do zadovoljavajućeg rešenja. Traženje maksimalnog sortiranog podniza je preskupo.

Natural merge algoritam bi mogao da se poboljša sortiranjem run-ova, od manjeg ka većem, ili stapanjem uvek dva trenutno najmanja. Recimo run-ove 2, 2, 2, 2, 5 je bolje spojiti 2 i 2 (3:4), 2 i 2 (3:4), 5; 4 i 4 (7:8), 5; 8 i 5 (12:13) nego ići redom 2 i 2 (3) i 2 (5) i 2 (7) i 5 (12). Opet, overhead je traženje najmanjih, ali na duže staze (odnosno veće nizove) mislim da bi ovo dalo rezultate.

S' druge strane, traženjem sortiranih podnizova, ali od elemenata koji ne moraju biti uzastopni (u natural merge algoritmu se gledaju samo uzastopni), možda može da se nešto dobije, iako ne tako lako. Ovaj post je već predugačak pa ću ovde stati.

[Ovu poruku je menjao darkosos dana 18.07.2014. u 19:49 GMT+1]
 
Odgovor na temu

[es] :: Matematika :: Minimalna duzina najveceg sortiranog podniza

[ Pregleda: 2781 | Odgovora: 11 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.