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 :) )

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.

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.

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.