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