Eto, nakon dugog vremena opet pišem. Malo sam se ulijenio ali bilo je i tu drugih stvari i obaveza. Još uvijek nikako da krenem s treningom algoritama ali nadam se da ubrzo hoću. A koja je tema danas? Rekao bih par stvari o odnosu fizike i čovjeka.
Zanimljiva je ta ljudska rasa koja ima veliko znanje a opet ga ne koristi. U svom shvaćanju svijeta oko sebe, vidio sam kako zapravo ljudi ne koriste svoje znanje iz škole u svakodnevnom životu. Čovjek je zapravo jedan veliki heuristički stroj, koji na temelju svojeg iskustva odlučuje. U to iskustvo spadaju znanja koje je stekao, ali što ako ih nema?
Fizika je najniža znanost koja se može vidjeti očima. A zašto je onda ne gledamo. Možda ju dovoljno ne razumijemo, a možda nam se ne da jer je dosadna, ima puno formula, puno aproksimacija, malo precizne matematike. Ali to je to, fizika je ono što nas okružuje. Fizičari su zapravo hakeri svemira. Gledao sam nedavno dokumentarac o Tesli, po meni je on najveći haker koji je hodao Zemljom (iako on sebe nije zvao fizičarem).
Kad bi ljudi samo znali što je vrijeme. To je jedina dimenzija kojom ne možemo upravljati na lak način. A problem je što vrijeme nikad nemamo, uvijek nam fali. Ali da li je to istina? Koliko glupih stvari napravimo kroz dan, a zapravo su beskorisne. Prije svega čovjek bi se trebao pomiriti sa svojim granicama, a to je da mora tu i tamo odspavati, da mu od točke A do točke B treba neko t vrijeme (a nije 0), da procesi traju i ništa nije trenutno na našoj razini, tek kad to shvatimo biti ćemo sretni, pomireni s vremenom i moći ćemo promatrati kako se svijet mijenja bez da smo u strahu, stresu ili nekom od tih glupih i beskorisnih osjećaja.
Fizika je alat s kojim otvaramo um prema svemiru - i to je cijela priča o fizici i ljudima.
Monday, December 10, 2012
Saturday, August 4, 2012
Koliko je složena analiza složenosti?
Algoritam
Probati ću pokazati kako analiza jednostavnog algoritma može biti dosta zahtjevna. Analizirati će se algoritam koji generira slučajnu permutaciju brojeva 1 do N. Jednostavan programski kod u jeziku Python dan je u nastavku:N = int(sys.stdin.read())
memory = set()
while(len(memory) < N):
genNumber = random.randrange(0, N) #0 to N-1
memory.add(genNumber)
print(genNumber)
Pretpostavka
Pretpostavka za analizu je da struktura set radi u O(1) vremenu. Na kraju će biti dano rješenje u O(N) vremenu i algoritam koji je posve jednostavan za analizu jer se odmah iz algoritma vidi složenost.
Iz algoritma se vidi da broj koraka za zadani N nije određen. Zbog slučajne prirode koja se zbiva, teoretski ovaj program ne mora nikad završiti. Pa kako onda raditi analizu? Ideja je slična kao i kad bi radili analizu QSort-a gdje se pivot odabire slučajno. Vremenska složenost će biti očekivani (matematičko očekivanje) broj koraka za zadani N.
Nekako intuitivno se čini da će složenost algoritma u prosjeku biti eksponencijalna, što naravno nije dobro. Ali da li je to istina?
Probajte si u ovom trenutku zapisati Vašu pretpostavku koja je složenost, čisto ovako od oka, pa na kraju usporedite s rezultatom.
Izvod
Za izvod prvo nam je potreban model tj. slučajna varijabla s kojom ćemo prikazati dati proces (algoritam). Broj koraka k definirat ćemo kao broj koraka koji algoritam mora napraviti nakon što je već napravio N koraka. Razlog tome je što algoritam mora napraviti barem N koraka, pa da se ne komplicira s tim dodatnim N-om bolje je uzeti samo taj dodatak. Vidimo iz definicije problema da je najmanja vremenska složenost O(N), pa ako se i dobije da očekivani broj koraka tj. taj dodatak manji od N, ukupna vremenska složenost će biti O(N).
Do sada ništa pametno. Idemo na model. Kolika je vjerojatnost da algoritam završi u 0 dodatnih koraka: $$\frac{N!}{N^{N}}$$ Kolika je vjerojatnost za k dodatnih koraka? Ovo je već malo teži problem. Kolika je vjerojatnost za jednu permutaciju tj. da baš u tom redoslijedu program izgenerira N+k brojeva. Zbog neovisnosti vrijedi: p(1)*p(2)...p(N)...p(N+k). Ako si zamislimo generator kao bubanj s lopticama, vjerojatnost da u svakom koraku izvučemo neki broj je $$\frac{1}{N} \ tj.\ ukupno\ je\ to\ p = \frac{1}{N^{(k+N)}}$$ To je lakši dio. Teži dio je naći broj permutacija za koje igra završava baš u tom koraku k. Ono što je očito da zadnji generirani broj prije zaustavljanja algoritma je jedinstven u cijelom generiranom nizu, zato što je on jedini nedostajao. Znači na zadnje mjesto može ići jedan od N brojeva. Na preostalih N+k-1 mjesta svrstava se N-1 brojeva. Bitno je da se svaki od N-1 brojeva mora pojaviti barem jednom na intervalu od prvog generiranog do predzadnjeg generiranog broja jer postoji samo jedan broj koji je zadnji i taj je jedinstven. Npr. za N = 5, jedan od mogućih ishoda za k=5 dodatnih koraka je: 1112444335. Npr. niz za koji algoritam ne prestaje u k=5 koraku 1112444333 jer nema 5-ice i kada se ona pojavi biti će kraj, i biti će to jedina 5-ica u nizu. Dakako postoje i nizovi koji nisu nikako mogući npr. 1234512345, zbog toga što algoritam završi u 5-om koraku i ne može generirati sljedećih 12345. Pitanje je koliko takvih "dobrih" permutacija ima, tj. one koje zaustavljaju algoritam u k-tom koraku. Ovaj problem veoma se lako rješi s funkcijama izvodnicama, ali još bolje je odmah primijetiti da je taj broj jednak broju surjekcija iz skupa s N+k-1 članova u skup s N-1 članom. Ili bolje rečeno za svaku poziciju u generiranom nizu možemo odabrati N-1 član ali na takav način da do kraja niza tj. do predzadnjeg člana imamo svih N-1 brojeva barem jednom. I taj broj pomnožimo sa N zbog toga što imamo N slučajeva u kojem na kraju niza dolazi po jedan N.
Vjerojatnost da algoritam završi u k-tom koraku:
$$p(X=k)=\frac{N\cdot \sum_{i=0}^{N-1} \binom{N-1}{i} \cdot (-1)^{i} \cdot (N-1-i)^{N-1+k}}{N^{N+k}}$$
Matematičko očekivanje je:
$$E(k)=\sum_{k=0}^{\infty}k\cdot\frac{N\cdot \sum_{i=0}^{N-1} \binom{N-1}{i} \cdot (-1)^{i} \cdot (N-1-i)^{N-1+k}}{N^{N+k}}$$
Definiramo vremensku složenost algoritma kao matematičko očekivanje koje ovisi o broju N.
$$f(N)=\sum_{k=0}^{\infty}k\cdot\frac{N\cdot \sum_{i=0}^{N-1} \binom{N-1}{i} \cdot (-1)^{i} \cdot (N-1-i)^{N-1+k}}{N^{N+k}}$$
Rezultati
Teorijski:
Ograničimo očekivanje:$$f(N)=\sum_{k=0}^{\infty}k\cdot\frac{N\cdot \sum_{i=0}^{N-1} \binom{N-1}{i} \cdot (-1)^{i} \cdot (N-1-i)^{N-1+k}}{N^{N+k}}<N \cdot ln(N)$$
Kada se riješimo beskonačne sume tako što zamijenimo ove dvije sume a beskonačna suma je zapravo poznati red i skraćivanjem nejednakosti s N dobije se:
$$\frac{1}{N^{N-1}}\sum_{i=1}^{N}\binom{N-1}{i-1}(-1)^{i+1}\frac{(N-i)^{N}}{i^{2}} < \sum_{i=1}^{N}\frac{1}{i} < ln(N) + 1$$
Probajmo izračunati razliku između sume recipročnih brojeva i našeg izraza:
$$\sum_{i=1}^{N}\left [ \frac{1}{i}-\frac{1}{N^{N-1}}\binom{N-1}{i-1}(-1)^{i+1}\frac{(N-i)^{N}}{i^{2}}\right ] = 1.$$
Dokaz (hvala Maks!):
http://fly.srk.fer.hr/~dsantl/dokaz_rand.pdf
Dakle, vremenska složenost ovog algoritma je: $$O(Nlog(N))$$
Eksperimentalno:
Testiranjem algoritma i mjerenjem vremena ili koraka dobiju se pravi rezultati u izvođenju. Kako je algoritam nedeterministički, potrebno je za svaki N rezultate usrednjiti. U nastavku su dati grafovi koji prikazuju koliko koraka je potrebno da bi se algoritam izvršio u ovisnosti broja N. Može se uočiti da je funkcija N ln(N) gornja granica izmjerenih rezultata. Dvije su slike, prva prikazuje srednju vrijednost 50 rezultata za svaki N, a druga 100 rezultata za svaki N.
Sljedeća slika pokazuje kako izgleda teorijska funkcija koja je dobivena (očekivanje) i iz toga se može vidjeti da nejednakost vrijedi na prikazanom intervalu (plava boja je N ln(N), a ljubičasta matematičko očekivanje) :
I za kraj, kolika je vrijednost ovog izraza (barem na prikazanom intervalu):
$$\sum_{i=1}^{N}\left [ \frac{1}{i}-\frac{1}{N^{N-1}}\binom{N-1}{i-1}(-1)^{i+1}\frac{(N-i)^{N}}{i^{2}}\right ]$$
Bolji algoritam
Napravi se niz od N članova i to tako da je A[i] = i, 1<=i<=N. Stvorimo novi niz, niz pokazivača (niz indeksa) B[i] = index_od_i, gdje svaki član niza B pamti nekoga iz niza A. Generira se slučajni broj 1 do N i pogleda se na koji broj pokazuje B[ rand() ], to je sada baš broj rand(). U element B[ rand() ] stavi se indeks zadnjeg elementa koji još nije generiran. Sada se generira slučajni broj od 1 do N-1, i odabire se element B[rand], tj. broj A[B[rand()]], taj sigurno nije generiran, i nakon toga se opet u B[rand()] stavi indeks zadnjeg koji nije generiran (najvećeg). U svakom koraku generiramo jedan broj, tako da je složenost očigledna i iznosi O(N) (Uz pretpostavku da je funkcija rand() u O(1)).
Zaključak
Hm... analiza boljeg algoritma je puno kraća i ako sam to znao zašto sam išao raditi ono gore. Pa pokazano je da onaj gornji algoritam uopće nije tako loš kako se čini. A osim toga neki od razloga su to što sam se nadao nećem što će biti fora, a to sam i dobio.
"Ne samo moćno oružje u borbi za opstanak, matematika je simbol naše intelektualne snage i jamstvo da će se ljudski duh vazda boriti za uzvišene ciljeve." - Danilo Blanuša (1903-1987)
Sunday, July 1, 2012
Brojanje inverzija u permutacijama
Zadan je niz brojeva od 1 do N. Koliko permutacija toga niza postoji? N!. Broj inverzija u nekoj permutaciji definiran je kao broj parova gdje je lijevo pozicionirani broj veći od desnoga. Matamatička definicija: Ako je $$1\leq i < j \leq N$$ tada je inverzija ako a[j] < a[i], gdje je a zadani niz. Broj inverzija je ukupan broj ovakvih parova u nekoj permutaciji. Npr. za N = 3 i permutaciju 231 broj inverzija je 2 (2 i 1, 3 i 1). Koliko je maksimalni broj inverzija za neku permutaciju niza od N članova? $$\binom{N}{2} = \frac{N\cdot\left ( N - 1 \right )}{2}$$ Ako je zadan broj N, i broj k, pri čemu k označuje broj inverzija u nizu duljine N, potrebno je odrediti koliko permutacija toga niza ima točno k inverzija.
Prva ideja je da se prođe kroz sve permutacije i za svaku se izračuna koliko inverzija ima. Ako je to baš k tada pribrojimo broj 1 rješenju. Koja je vremenska složenost ovog rješenja: O( N! ). Ovo je loše, možemo li bolje? Naravno, i tražit ćemo rješenje koje radi u polinomnom vremenu, tj. složenost nam mora biti O( N^c) gdje je c konstanta.
Druga ideja je da nađemo neku pravilnost, tj. neku ovisnost broja permutacija u ovisnosti broja inverzija i duljini niza. Inženjerski pristup nam sugerira da si prvih nekoliko nizova zapišemo:
N = 1, k = 0 => 1, ostali su 0, jer postoji samo jedna permutacija
N = 2, k = 0 => 1, to je permutacija 1,2
N = 2, k = 1 => 1, to je permutacija 2,1
N = 3, k = 0 => 1, permutacija 1,2,3
N = 3, k = 1 => 2 permutacije: 1,3,2 i 2,1,3
N = 3, k = 2 => 2 permutacije: 3, 1, 2 i 2, 3, 1
N = 3, k = 3 => 1, permutacija 3,2,1
U primjeru N=3 vidimo da imamo ukupno 6=3! permutacija i sve smo prebrojali. Već sada može se primjetiti određena simetrja, ali ne možemo tvrditi da za veće N to vrijedi prije nego što dokažemo (ali nećemo sada).
Neka svojstva se lako vide, npr. uvijek će za broj inverzija 0 i broj inverzija N! postojati samo jedna permutacija za svaku a to će uvijek biti početni niz i okrenuti niz.
Ideja je sljedeća: Da li možemo ako znamo za N-1 rješenje (za svaki k) konstruirati rješenje za N (za svaki k).
Pokušajmo to ručno izvesti:
Prvo imamo niz [ 1 ], sad možemo dodati broj 2 na početak ili na kraj niza.
N = 2 dobijemo [1 2] ili [2 1]. Idemo pogledati koliki je broj inverzija za svaku od ovih permutacija. Za [1 2] je 0, za [2 1] je 1. Ok, ništa posebno ali radoznalost nas tjera da napravimo sljedeći korak i ubacimo na svaku od tih permutacija broj 3.
N=3 dobijemo [1 2 3], [1 3 2], [3 1 2] i za [2 1] i 3 dobijemo [ 2 1 3 ], [ 2 3 1] i [ 3 2 1]. Koliko je njihov broj inverzija (po istom redosljedu): 0, 1, 2, 1, 2, 3. Možda se već iz ovoga vidi da postoji lijepa veza između nizova duljine N i N-1.
Sad se već dinamika nameće kao rješenje. Znači za N=1, mogući k-ovi su {0}. To se može granati na dvije grane (dodavanje broja 2), mogući k-ovi su {0, 1}. Zatim dodajemo 3 i granamo dalje. Mogući k-ovi su sada {0, 1, 2, 3}, tj od sad na dalje općenito vrijedi da je k iz intervala $$ Od \,\, 0 \,\, do \,\, \frac{N\cdot\left ( N - 1 \right )}{2}$$ Na ovako nacrtanom stablu (koje trenutno nije nacrtano u ovome postu) vidimo da na svakoj razini ima točno N! čvorova. Neka roditelj ima Q inverzija, djeca će imati od Q do Q+N-1 inverzija. Sad je lako. Možemo napraviti DFS i doći do razine koja nam treba te ukupnom rješenju pridodati to što smo našli. Malo memonizacije i složenost je O(N^3). Moguće je napraviti i dinamiku od dna prema vrhu, gdje se prvo nadzire rješenje u O(N^4) ali uoćavanjem da u jednoj petlji zapravo ne trebamo vrtiti još jednu dobije se O(N^3).
Zadatak: http://www.spoj.pl/problems/PERMUT1/
Prva ideja je da se prođe kroz sve permutacije i za svaku se izračuna koliko inverzija ima. Ako je to baš k tada pribrojimo broj 1 rješenju. Koja je vremenska složenost ovog rješenja: O( N! ). Ovo je loše, možemo li bolje? Naravno, i tražit ćemo rješenje koje radi u polinomnom vremenu, tj. složenost nam mora biti O( N^c) gdje je c konstanta.
Druga ideja je da nađemo neku pravilnost, tj. neku ovisnost broja permutacija u ovisnosti broja inverzija i duljini niza. Inženjerski pristup nam sugerira da si prvih nekoliko nizova zapišemo:
N = 1, k = 0 => 1, ostali su 0, jer postoji samo jedna permutacija
N = 2, k = 0 => 1, to je permutacija 1,2
N = 2, k = 1 => 1, to je permutacija 2,1
N = 3, k = 0 => 1, permutacija 1,2,3
N = 3, k = 1 => 2 permutacije: 1,3,2 i 2,1,3
N = 3, k = 2 => 2 permutacije: 3, 1, 2 i 2, 3, 1
N = 3, k = 3 => 1, permutacija 3,2,1
U primjeru N=3 vidimo da imamo ukupno 6=3! permutacija i sve smo prebrojali. Već sada može se primjetiti određena simetrja, ali ne možemo tvrditi da za veće N to vrijedi prije nego što dokažemo (ali nećemo sada).
Neka svojstva se lako vide, npr. uvijek će za broj inverzija 0 i broj inverzija N! postojati samo jedna permutacija za svaku a to će uvijek biti početni niz i okrenuti niz.
Ideja je sljedeća: Da li možemo ako znamo za N-1 rješenje (za svaki k) konstruirati rješenje za N (za svaki k).
Pokušajmo to ručno izvesti:
Prvo imamo niz [ 1 ], sad možemo dodati broj 2 na početak ili na kraj niza.
N = 2 dobijemo [1 2] ili [2 1]. Idemo pogledati koliki je broj inverzija za svaku od ovih permutacija. Za [1 2] je 0, za [2 1] je 1. Ok, ništa posebno ali radoznalost nas tjera da napravimo sljedeći korak i ubacimo na svaku od tih permutacija broj 3.
N=3 dobijemo [1 2 3], [1 3 2], [3 1 2] i za [2 1] i 3 dobijemo [ 2 1 3 ], [ 2 3 1] i [ 3 2 1]. Koliko je njihov broj inverzija (po istom redosljedu): 0, 1, 2, 1, 2, 3. Možda se već iz ovoga vidi da postoji lijepa veza između nizova duljine N i N-1.
Sad se već dinamika nameće kao rješenje. Znači za N=1, mogući k-ovi su {0}. To se može granati na dvije grane (dodavanje broja 2), mogući k-ovi su {0, 1}. Zatim dodajemo 3 i granamo dalje. Mogući k-ovi su sada {0, 1, 2, 3}, tj od sad na dalje općenito vrijedi da je k iz intervala $$ Od \,\, 0 \,\, do \,\, \frac{N\cdot\left ( N - 1 \right )}{2}$$ Na ovako nacrtanom stablu (koje trenutno nije nacrtano u ovome postu) vidimo da na svakoj razini ima točno N! čvorova. Neka roditelj ima Q inverzija, djeca će imati od Q do Q+N-1 inverzija. Sad je lako. Možemo napraviti DFS i doći do razine koja nam treba te ukupnom rješenju pridodati to što smo našli. Malo memonizacije i složenost je O(N^3). Moguće je napraviti i dinamiku od dna prema vrhu, gdje se prvo nadzire rješenje u O(N^4) ali uoćavanjem da u jednoj petlji zapravo ne trebamo vrtiti još jednu dobije se O(N^3).
Zadatak: http://www.spoj.pl/problems/PERMUT1/
Sunday, June 3, 2012
Analiza algoritama
Nakon što se upoznamo s nekim programskim jezikom i naučimo ga relativno dobro, teoretski možemo napisati bilo kakvu aplikaciju. Evo primjer: Dolazi do Vas školski kolega i kaže kako ima određene obaveze ali ne zna kako ih rasporediti. Vi naravno, kao vrhunski programer prihvatite ponudu i kažete, eto prijatelju gotov sam za 10 minuta, samo da natipkam to. I super, zaista natipkali ste to, i to radi. Kolega napiše obaveze, označi kada bi koje obaveze mogao obavljati, a program mu izbaci raspored (ili više njih). I tako prođe neko vrijeme, i vidite oglas u kojem piše da se traži honorarni programer koji će napraviti generator rasporeda za jednu poveću tvrtku. Trebalo bi sinkronizirati sve radnike, s time da svaki radnik ponudi svoje vrijeme kada bi htio raditi. Odmah pomislite, pa to sam napravio već za kolegu, samo malo prilagodim aplikaciju, stavim neki super GUI i eto zarade. I eto Vi to napišete, uredite i kreće testiranje. Imate datoteku od 10 ljudi i generira se lijep raspored. Pokažete riješenje upravi, oni sretni jer ste brzo napraviti i odmah Vam daju test datoteku s 200 ljudi (samo 20 puta više) i Vi pokrenete program. U 90% (i više) Vaša aplikacija radi i radi i radi... Što se dogodilo? Problem je što algoritam nije "brz". Pomislite to je zato jer pišem nekom visokom jeziku, ajde da prebacim to u strojni kod. I opet algoritam je spor. Pretpostavimo da algoritam radi tako da isproba sve kombinacije i kao rezultat vrati one dobre. Ovo rješenje je iscrpna pretraga (engl. brute-force). Vremenska složenost je O( n! ). Ok, ali što je vremenska složenost? Za početak budimo neprecizni pa kažemo da je vremenska složenost mjera koja pokazuje kako algoritam "brzo" radi u ovisnosti ulaznih podataka. Prostorna složenost je isto to samo za memoriju.
Na ovom primjeru vidjeli smo da je analiza algoritma bitna. Kada se jamči mali broj ulaznih podataka i najgore rješenje je dobro, ako ono radi u vremenskom ograničenju. Općenito kada se pojava faktorijeli to je jako jako loše, iako ponekad teorijski ne možemo brže. Postoji cijela teorija koja se bavi formalnim opisima složenosti i ima puno lijepe matematike u tome. Sada ćemo se posvetiti načinu na koji se izračunava vremenska i prostorna složenost algoritma. Bez ulaženja u dubinu, prva stvar koja se obično radi s analizom algoritama je "veliko O notacija". Što znači O( n! ) ili pak O( log n ). Ideja je da se traži funkcija koja će reći kako je algoritam brz, tj. koja će reći kako vrijeme izvođenja teoretski ovisi o ulaznim podacima (analogno za memoriju). Ako je vremenska složenost algoritma O( n ), to znači da vrijeme raste linearno u ovisnosti ulaznih podataka. Može biti da je f(n) = 5*n ili f(n) = 10n + 120023, navedene funkcije spadaju u O( n ), pri čemu je f(n) broj operacija koje se obave. Primijetimo da konstante nisu bitne. Zadan je program koji učitava dimenzije matrice i popunjava ih slučajnim brojevima. Koja je vremenska složenost? (neka je n broj redaka i broj stupaca) Imamo dvije for-petlje, jedna unutar druge. Ukupni broj operacija pridjeljivanja je n*n. Vremenska složenost je O( n^2 ). Tvrdim da je vremenska složenost i O( n! ), za navedeni algoritam popunjavanja matrice. Pa kako sad to? Problem je što ne znamo što zapravo veliko O predstavlja. Kratko napisano ali matematički neprecizno, funkcija f pripada O( g(n) ) ako za neki n0 i za neku konstantu c vrijedi da je f(n) = c*g(n). Iz ovoga se vidi da f(n) mora biti nakon nekog n0 pa sve do beskonačnosti manja ili jednaka c*g(n). Ako je f(n) = n^2, tada vrijedi f(n) = c*n!, za neki n0 i c. U praksi je bitno da g(n) bude ona koja je najmanja. Konkretno, najmanja je g(n) = n^2. Veliko O notacija najčešće se koristi kako bi se opisalo ponašanje algoritma za najgori slučaj.
Kako mogu analizirati program? Najjednostavnije je brojati koliko se jednostavnih operacija izvrši. Pod jednostavnim operacijama mislim na one čija je vremenska složenost O( 1 ). Evo primjera:
Kolika je vremenska složenost algoritma za množenje matrica: O( n^3).
Kolika je vremenska složenost algoritma koji traži najveći broj u nizu: O( n ).
Zadani program: ucitaj n, za i = 1 do n: i = i * 10 vremenska složenost je O( log( n ) ).
Memorijske složenost za navedene primjere su redom: O( n^2 ), O( n ), O( 1 ).
Za prvi primjer koristimo matrice i ako je svaka dimenzije n^2, ukupno je to 3*n^2 memorije, što je prema prethodnoj definiciji O( n^2 ). Treći primjer koristi samo jednu varijablu, što znači da korištenje memorije ne ovisi o ulaznom podatku n.
Osim veliko O notacije postoje i druge notacije, koje se koriste (neke više neke manje) ako Vas zanima pogledajte u literaturi koju sam naveo par postova prije.
Nadam se da će ovo biti dovoljno za daljnje razumijevanje jednostavnih analiza koje će biti rađene kod algoritama. Sljedeći korak je master teorem, za kojeg će se samo pokazati kako se računa ali neće biti izvod (barem ne u sklopu ovih tutorial postova). Ali prije toga par jednostavnih ali korisnih algoritama (i struktura podataka)
Na ovom primjeru vidjeli smo da je analiza algoritma bitna. Kada se jamči mali broj ulaznih podataka i najgore rješenje je dobro, ako ono radi u vremenskom ograničenju. Općenito kada se pojava faktorijeli to je jako jako loše, iako ponekad teorijski ne možemo brže. Postoji cijela teorija koja se bavi formalnim opisima složenosti i ima puno lijepe matematike u tome. Sada ćemo se posvetiti načinu na koji se izračunava vremenska i prostorna složenost algoritma. Bez ulaženja u dubinu, prva stvar koja se obično radi s analizom algoritama je "veliko O notacija". Što znači O( n! ) ili pak O( log n ). Ideja je da se traži funkcija koja će reći kako je algoritam brz, tj. koja će reći kako vrijeme izvođenja teoretski ovisi o ulaznim podacima (analogno za memoriju). Ako je vremenska složenost algoritma O( n ), to znači da vrijeme raste linearno u ovisnosti ulaznih podataka. Može biti da je f(n) = 5*n ili f(n) = 10n + 120023, navedene funkcije spadaju u O( n ), pri čemu je f(n) broj operacija koje se obave. Primijetimo da konstante nisu bitne. Zadan je program koji učitava dimenzije matrice i popunjava ih slučajnim brojevima. Koja je vremenska složenost? (neka je n broj redaka i broj stupaca) Imamo dvije for-petlje, jedna unutar druge. Ukupni broj operacija pridjeljivanja je n*n. Vremenska složenost je O( n^2 ). Tvrdim da je vremenska složenost i O( n! ), za navedeni algoritam popunjavanja matrice. Pa kako sad to? Problem je što ne znamo što zapravo veliko O predstavlja. Kratko napisano ali matematički neprecizno, funkcija f pripada O( g(n) ) ako za neki n0 i za neku konstantu c vrijedi da je f(n) = c*g(n). Iz ovoga se vidi da f(n) mora biti nakon nekog n0 pa sve do beskonačnosti manja ili jednaka c*g(n). Ako je f(n) = n^2, tada vrijedi f(n) = c*n!, za neki n0 i c. U praksi je bitno da g(n) bude ona koja je najmanja. Konkretno, najmanja je g(n) = n^2. Veliko O notacija najčešće se koristi kako bi se opisalo ponašanje algoritma za najgori slučaj.
Kako mogu analizirati program? Najjednostavnije je brojati koliko se jednostavnih operacija izvrši. Pod jednostavnim operacijama mislim na one čija je vremenska složenost O( 1 ). Evo primjera:
Kolika je vremenska složenost algoritma za množenje matrica: O( n^3).
Kolika je vremenska složenost algoritma koji traži najveći broj u nizu: O( n ).
Zadani program: ucitaj n, za i = 1 do n: i = i * 10 vremenska složenost je O( log( n ) ).
Memorijske složenost za navedene primjere su redom: O( n^2 ), O( n ), O( 1 ).
Za prvi primjer koristimo matrice i ako je svaka dimenzije n^2, ukupno je to 3*n^2 memorije, što je prema prethodnoj definiciji O( n^2 ). Treći primjer koristi samo jednu varijablu, što znači da korištenje memorije ne ovisi o ulaznom podatku n.
Osim veliko O notacije postoje i druge notacije, koje se koriste (neke više neke manje) ako Vas zanima pogledajte u literaturi koju sam naveo par postova prije.
Nadam se da će ovo biti dovoljno za daljnje razumijevanje jednostavnih analiza koje će biti rađene kod algoritama. Sljedeći korak je master teorem, za kojeg će se samo pokazati kako se računa ali neće biti izvod (barem ne u sklopu ovih tutorial postova). Ali prije toga par jednostavnih ali korisnih algoritama (i struktura podataka)
Sunday, May 20, 2012
Podijeli pa vladaj
Zamislite da je pred vama jedan veliki izazov, neka to bude novi projekt, fakultet ili nešto slično. Kada bi u trenutku započinjanja pred sobom vidjeli sve poteškoće koje Vas čekaju, teško da bi započeli, bilo bi previše obeshrabrujuće. Zaključak ove tvrdnje govori o tome da je neke stvari nemoguće riješiti odmah, pa odrađujemo malo po malo dok ne dođemo do cilja. Na toj ideji počiva paradigma podijeli pa vladaj.
Ako je neki problem moguće rastaviti na manje dijelove, onda zaista možemo biti sretni iz više razloga. Probleme koje je moguće riješiti dinamičkim programiranjem, najčešće je i najbrže rješenje za njih, a dinamičko programiranje upravo počiva na paradigmi podijeli pa vladaj. Ako rješavamo manje probleme i u nekom trenutku počinjemo rješavati problem koji smo već prethodno riješili, trivijalno smo riješili i taj isti novi problem. Najčešće se problemi dijele u rekurziji, što opet može biti jako loše ako postoji iterativna implementacija, ali neke probleme je nemoguće ili jako teško riješiti bez rekurzije.
Neki lagani matematički problemi kao što je množenje matrica, mogu se pomoću paradigme podijeli pa vladaj riješiti brže nego što se na pravi pogled čini. Složenost množenja matrica (ako je kvadratna) je O(n^3). To izravno slijedi iz definicije matričnog produkta. Ali može li brže? Naravno, može se dokazati da je algoritam izvediv i za nešto manje od kuba. Ideja je da se matrice rastave na manje dijelove i onda množe. Jedan post će možda biti posvećen samo tom rješenju (Strassenov algoritam). Pitanje je da li se može i brže od toga, odgovor je da, ali ne znam ništa više od toga.
A sad nešto još bolje. Zamislite da potprobleme možemo rješavati paralelno (istovremeno). Ne moramo zamišljati jer danas se proizvode procesori sa sve više i više jezgara. Računarska disciplina koja se bavi rješavanjem paralelnih problema zove se neočekivano paralelno programiranje. Prednost problema koji se mogu rastaviti je baš u tome što se trivijalno vidi kako treba nešto paralelizirati.
Ali to nije sve... Brzi razvoj grafičkih kartica pokazao je da se grafičke kartice ne moraju koristiti samo za prikazivanje grafike (izračun rastera i geometrije). Grafičke kartice imaju puno više jezgri od procesora i to za red veličine (~100). Pitanje je zašto onda ne koristimo grafičke kartice kao centralne procesore. Zbog toga što jezgre u grafičkoj kartici rade isti posao, samo na drugim podacima. Razlog je prava namjena grafičke kartice. Na primjer, kada želimo rotirati neki objekt u 3D prostoru, svaki vrh objekta moramo nekako transformirati, što se radi množenjem matrica, pa svaka jezgra grafičke kartice računa transformaciju za jedan vrh. Naravno da postoji manja granulacija od samih jezgri ali skužili Ste poantu. GPGPU je disciplina koja se bavi rješavanjem općih problema na grafičkoj kartici, pa tako i integriranje problema koji se mogu podijeliti, a zatim nad njima vladati. Ako vas zanima paralelno programiranje ali na visikoj razini (tokovnim modelom) pogledajte jezik StreamIt. Ideja je da se opisuju apstraktne strukutre toka podataka, a sam kompajler učini sav prljav posao za Vas.
Za algoritme morati ću pronaći malo vremena, što trenutno nije moguće. U planu su redom sljedeće teme: izračun vremenske i memorijske složenosti, binarno pretraživanje (ternarno), brza sortiranja i neuobičajene primjene, master teorem za izračun složenosti podjeli i vladaj algoritama... Ideja je da se algoritmi objasne od početka, ali nikako ne strogo formalno već više pogled na ideju i implementaciju (inženjerski pristup :) )
Ako je neki problem moguće rastaviti na manje dijelove, onda zaista možemo biti sretni iz više razloga. Probleme koje je moguće riješiti dinamičkim programiranjem, najčešće je i najbrže rješenje za njih, a dinamičko programiranje upravo počiva na paradigmi podijeli pa vladaj. Ako rješavamo manje probleme i u nekom trenutku počinjemo rješavati problem koji smo već prethodno riješili, trivijalno smo riješili i taj isti novi problem. Najčešće se problemi dijele u rekurziji, što opet može biti jako loše ako postoji iterativna implementacija, ali neke probleme je nemoguće ili jako teško riješiti bez rekurzije.
Neki lagani matematički problemi kao što je množenje matrica, mogu se pomoću paradigme podijeli pa vladaj riješiti brže nego što se na pravi pogled čini. Složenost množenja matrica (ako je kvadratna) je O(n^3). To izravno slijedi iz definicije matričnog produkta. Ali može li brže? Naravno, može se dokazati da je algoritam izvediv i za nešto manje od kuba. Ideja je da se matrice rastave na manje dijelove i onda množe. Jedan post će možda biti posvećen samo tom rješenju (Strassenov algoritam). Pitanje je da li se može i brže od toga, odgovor je da, ali ne znam ništa više od toga.
A sad nešto još bolje. Zamislite da potprobleme možemo rješavati paralelno (istovremeno). Ne moramo zamišljati jer danas se proizvode procesori sa sve više i više jezgara. Računarska disciplina koja se bavi rješavanjem paralelnih problema zove se neočekivano paralelno programiranje. Prednost problema koji se mogu rastaviti je baš u tome što se trivijalno vidi kako treba nešto paralelizirati.
Ali to nije sve... Brzi razvoj grafičkih kartica pokazao je da se grafičke kartice ne moraju koristiti samo za prikazivanje grafike (izračun rastera i geometrije). Grafičke kartice imaju puno više jezgri od procesora i to za red veličine (~100). Pitanje je zašto onda ne koristimo grafičke kartice kao centralne procesore. Zbog toga što jezgre u grafičkoj kartici rade isti posao, samo na drugim podacima. Razlog je prava namjena grafičke kartice. Na primjer, kada želimo rotirati neki objekt u 3D prostoru, svaki vrh objekta moramo nekako transformirati, što se radi množenjem matrica, pa svaka jezgra grafičke kartice računa transformaciju za jedan vrh. Naravno da postoji manja granulacija od samih jezgri ali skužili Ste poantu. GPGPU je disciplina koja se bavi rješavanjem općih problema na grafičkoj kartici, pa tako i integriranje problema koji se mogu podijeliti, a zatim nad njima vladati. Ako vas zanima paralelno programiranje ali na visikoj razini (tokovnim modelom) pogledajte jezik StreamIt. Ideja je da se opisuju apstraktne strukutre toka podataka, a sam kompajler učini sav prljav posao za Vas.
Za algoritme morati ću pronaći malo vremena, što trenutno nije moguće. U planu su redom sljedeće teme: izračun vremenske i memorijske složenosti, binarno pretraživanje (ternarno), brza sortiranja i neuobičajene primjene, master teorem za izračun složenosti podjeli i vladaj algoritama... Ideja je da se algoritmi objasne od početka, ali nikako ne strogo formalno već više pogled na ideju i implementaciju (inženjerski pristup :) )
Saturday, May 12, 2012
Algoritmi (klasični)
Zašto je poznavanje algoritama bitno? Postoji više razloga zašto je bitno. Pravim entuzijastima bitno je napisati nešto što nitko do sad nije napisao i da radi brže i bolje. Komercijalno algoritmi su bitni da uz što manju potrošnju resursa, program može raditi brže od konkurencije. Općenito postoji puno algoritama koji se koriste za različite svrhe. Ipak jedna skupina algoritama koju možemo nazvati generičkim algoritmima (klasičnim), su algoritmi koji se mogu primijeniti na velik skup problema koji se javljaju u "svakodnevnom" programiranju.
Jedan od takvih problema je sortiranje. Ako se zna kako najbrže sortirati niz brojeva, onda uvijek kada se pojavi problem sortiranja možemo primijeniti taj algoritam, i možemo biti sigurni da je to najbolje što se može napraviti. Još važnija činjenica je da se algoritmi mogu prilagoditi za probleme koje inicijalno ne rješavaju. I tu se zapravo krije prava ljepota algoritama.
Ako se pogleda algoritam za sortiranje "Merge sort" ispod haube, vidi se da se tu krije "Podjeli i vladaj" (engl. "Divide and conquer") algoritam. Ova, nazovimo ju paradigma veoma je popularna u rješavanju problema, i to bi trebao biti jedan od osnovnih alata svakog programera.
Svi programeri bi kroz svoju edukaciju morali proći kroz klasične algoritme, ali to najčešće nije slučaj. Zašto? Ne znam, ima puno uzroka. Jedan je zasigurno nezainteresiranost za matematiku koja stoji iza toga, odnosno neopravdani strah. Drugi razlog mogao bi biti što se formalno u obrazovanju ne daje prevelika pažnja proučavaju klasičnih algoritama. Kasnije, ovo može prouzročiti puno problema, jer pisanje vlastitih ad-hoc algoritama gotovo uvijek rezultira puno gorim rješenjem od optimalnog. Puno ljudi neće se složiti da u biti tehnologija u kojoj se pišu programi nije važna. Naravno da programski jezik utječe na kvalitetu aplikacije, ali stvarna moć aplikacije je u kvalitetnoj izvedbi algoritma.
E sad smo se dotakli i implementacije algoritma. Veoma važno je pisati brze algoritme dobro. Da bi se algoritmi pisali dobro potrebno je dobro poznavati jezik u kojem se algoritam piše ili pisati u programskom jeziku koji jako dobro optimira kod. Danas visoki programski jezici jako dobro optimiraju kod, što zapravo programeru pruža da više vremena utroši na apstraktno rješavanje umjesto da ga troši na detalje koji na prvi pogled nisu bitni ali na kraju se uspostavi da su itekako bitni.
Ovaj post je uvod u tutorial koji će biti dio bloga. Tutorial će biti uvod u algoritme i strukture podataka koje se mogu generički primijeniti na puno problema. Početi će od samih osnova i prikaza kako se na drugačiji način može vidjeti problem. Pokušat ću sve tutoriale prevesti na engleski jezik. Ako nekog zanima više od toga preporučujem knjigu Domagoja Kusalića: Napredno programiranje i algoritmi u C-u i C++-u. Za sve one koji konkretno žele rješavati probleme evo nekih dobrih stranica:
http://www.topcoder.com/
http://www.spoj.pl/
http://p4.tel.fer.hr/~agrbin/pimp/login
http://www.z-training.net/training.php
Naravno tu je i stranica HSIN-a s velikim skupom zadataka.
Najvažnija stvar kod bilo kakvog proučavanja (učenja) je pristup bez straha, uzeti si dovoljno vremena, volje i upornosti da se savladaju različiti problemi koji će se pojaviti.
May the Force be with you.
Jedan od takvih problema je sortiranje. Ako se zna kako najbrže sortirati niz brojeva, onda uvijek kada se pojavi problem sortiranja možemo primijeniti taj algoritam, i možemo biti sigurni da je to najbolje što se može napraviti. Još važnija činjenica je da se algoritmi mogu prilagoditi za probleme koje inicijalno ne rješavaju. I tu se zapravo krije prava ljepota algoritama.
Ako se pogleda algoritam za sortiranje "Merge sort" ispod haube, vidi se da se tu krije "Podjeli i vladaj" (engl. "Divide and conquer") algoritam. Ova, nazovimo ju paradigma veoma je popularna u rješavanju problema, i to bi trebao biti jedan od osnovnih alata svakog programera.
Svi programeri bi kroz svoju edukaciju morali proći kroz klasične algoritme, ali to najčešće nije slučaj. Zašto? Ne znam, ima puno uzroka. Jedan je zasigurno nezainteresiranost za matematiku koja stoji iza toga, odnosno neopravdani strah. Drugi razlog mogao bi biti što se formalno u obrazovanju ne daje prevelika pažnja proučavaju klasičnih algoritama. Kasnije, ovo može prouzročiti puno problema, jer pisanje vlastitih ad-hoc algoritama gotovo uvijek rezultira puno gorim rješenjem od optimalnog. Puno ljudi neće se složiti da u biti tehnologija u kojoj se pišu programi nije važna. Naravno da programski jezik utječe na kvalitetu aplikacije, ali stvarna moć aplikacije je u kvalitetnoj izvedbi algoritma.
E sad smo se dotakli i implementacije algoritma. Veoma važno je pisati brze algoritme dobro. Da bi se algoritmi pisali dobro potrebno je dobro poznavati jezik u kojem se algoritam piše ili pisati u programskom jeziku koji jako dobro optimira kod. Danas visoki programski jezici jako dobro optimiraju kod, što zapravo programeru pruža da više vremena utroši na apstraktno rješavanje umjesto da ga troši na detalje koji na prvi pogled nisu bitni ali na kraju se uspostavi da su itekako bitni.
Ovaj post je uvod u tutorial koji će biti dio bloga. Tutorial će biti uvod u algoritme i strukture podataka koje se mogu generički primijeniti na puno problema. Početi će od samih osnova i prikaza kako se na drugačiji način može vidjeti problem. Pokušat ću sve tutoriale prevesti na engleski jezik. Ako nekog zanima više od toga preporučujem knjigu Domagoja Kusalića: Napredno programiranje i algoritmi u C-u i C++-u. Za sve one koji konkretno žele rješavati probleme evo nekih dobrih stranica:
http://www.topcoder.com/
http://www.spoj.pl/
http://p4.tel.fer.hr/~agrbin/pimp/login
http://www.z-training.net/training.php
Naravno tu je i stranica HSIN-a s velikim skupom zadataka.
Najvažnija stvar kod bilo kakvog proučavanja (učenja) je pristup bez straha, uzeti si dovoljno vremena, volje i upornosti da se savladaju različiti problemi koji će se pojaviti.
May the Force be with you.
Sunday, May 6, 2012
Latex
Ako ste se kada zapitali zašto je pisanje u alatima za obradu teksta tako naporno i željeli ste nešto drugačije, svakako pogledajte LaTeX. LaTeX je jezik za oblikovanje dokumenata. Sve što korisnik tipično radi je samo pisanje teksta, a za tipografiju se brine tekst procesor. Za razliku od popularnih "office" tekst procesora nema gnjavaže i igranja mišem, tj. klikanja na tisuće ikona (osim ako niste vješti u korištenju kratica). LaTeX dokument može se pisati u bilo kojem tekst editoru, i to neovisno o platformi.
Prvi susret s LaTeX-om može biti neugodan, zbog toga što odjednom nestaje vizualan prikaz teksta, a sve što korisnik vidi je hrpa "čudnih" znakova koji se pojavljuj usred teksta. Dobra stvar je što se na LaTeX može brzo naviknuti, pa svi oni znakovi zapravo postaju jasni, a oni predstavljaju specijalne znakove (simbole) u samom tekstu ili pak naredbe kojima želimo promijeniti stil teksta. Korisnik se često služi gotovim predlošcima, koji su već pripremljeni za određene namjene (pisanje članaka, dokumentacija, završnih i diplomskih radova). Za nešto naprednije korištenje LaTeX-a potrebno je jako dobro poznavati pozadinu, ali kako je navedeno najčešće korisnik ne mora brinuti o tome.
A sada konkretno, zašto je LaTeX dobar? Prvenstveno zbog toga što koristi tipografska pravila, što znači ako je predložak dobar, dokument će lijepo izgledati. A i sam LaTeX forsira tipografska pravila, pa se u početku korištenja često zna dogoditi da nešto ne želimo na tom mjestu ali npr. slika se jednostavno postavila na tom mjestu i ne miče se od tamo. Dobra stvar je što se uz svaki element nude opcije s kojima se jednostavno upravlja, pa korisnik može forsirati svoje ideje.
Tek sam početnik u korištenju LaTeX-a ali preporučio bih ga svakome tko kreće u pisanje ozbiljnih dokumenata. Prvi susret možda može biti naporan, ali na kraju se isplati. Više od 60% vremena gubio sam na oblikovanje dokumenata u standardnim alatima. Sada je trošenje vremena na oblikovanje svedeno je na minimum. Loša strana bi moglo biti to što na pravi pogled LaTeX nije intuitivan, ali kako sam već prije napisao isplati se naučiti ovaj jezik.
Trenutno koristim gummi editor, koji možda nije najbolji izbor što se tiče naprednih mogućnosti kao što su nadopunjivanje naredbi ili automatsko predlaganje naredbi. Ali bojanje sintakse i to što se dokument uvijek vidi kakav će biti nakon export-a u pdf-u čini ovaj editor lakim za korištenje. GUI jako podsjeća na gedit, ako koristite gedit kao primarni editor onda je gummi ono što tražite.
Prvi susret s LaTeX-om može biti neugodan, zbog toga što odjednom nestaje vizualan prikaz teksta, a sve što korisnik vidi je hrpa "čudnih" znakova koji se pojavljuj usred teksta. Dobra stvar je što se na LaTeX može brzo naviknuti, pa svi oni znakovi zapravo postaju jasni, a oni predstavljaju specijalne znakove (simbole) u samom tekstu ili pak naredbe kojima želimo promijeniti stil teksta. Korisnik se često služi gotovim predlošcima, koji su već pripremljeni za određene namjene (pisanje članaka, dokumentacija, završnih i diplomskih radova). Za nešto naprednije korištenje LaTeX-a potrebno je jako dobro poznavati pozadinu, ali kako je navedeno najčešće korisnik ne mora brinuti o tome.
A sada konkretno, zašto je LaTeX dobar? Prvenstveno zbog toga što koristi tipografska pravila, što znači ako je predložak dobar, dokument će lijepo izgledati. A i sam LaTeX forsira tipografska pravila, pa se u početku korištenja često zna dogoditi da nešto ne želimo na tom mjestu ali npr. slika se jednostavno postavila na tom mjestu i ne miče se od tamo. Dobra stvar je što se uz svaki element nude opcije s kojima se jednostavno upravlja, pa korisnik može forsirati svoje ideje.
Tek sam početnik u korištenju LaTeX-a ali preporučio bih ga svakome tko kreće u pisanje ozbiljnih dokumenata. Prvi susret možda može biti naporan, ali na kraju se isplati. Više od 60% vremena gubio sam na oblikovanje dokumenata u standardnim alatima. Sada je trošenje vremena na oblikovanje svedeno je na minimum. Loša strana bi moglo biti to što na pravi pogled LaTeX nije intuitivan, ali kako sam već prije napisao isplati se naučiti ovaj jezik.
Trenutno koristim gummi editor, koji možda nije najbolji izbor što se tiče naprednih mogućnosti kao što su nadopunjivanje naredbi ili automatsko predlaganje naredbi. Ali bojanje sintakse i to što se dokument uvijek vidi kakav će biti nakon export-a u pdf-u čini ovaj editor lakim za korištenje. GUI jako podsjeća na gedit, ako koristite gedit kao primarni editor onda je gummi ono što tražite.
Saturday, May 5, 2012
Uvod
Ideja ovog bloga je da svoje misli stavim na "papir". Smatram da premalo pišem otkako sam na faksu, pa na ovaj način zapravo treniram pisanje. Neki od postova biti će na engleskom jeziku, iz istog razloga.
Subscribe to:
Posts (Atom)