Algoritmi u programskom jeziku C

Knjiga sadrzi prikaz nekih vrlo poznatih i dosta koriscenih algoritama i njihovu implementaciju u programskom jeziku C. Autor je odabrao probleme koji se najcesce pojavljuju u praksi i po slicnoj literaturi na stranim jezicima. Knjiga ne pretpostavlja dublje poznavanje programskog jezika C. Prva glava daje kratak prikaz sintakse i semantike programskog jezika C zajedno sa nekim detaljima koji se obicno ne pominju u knjigama. Pretpostavlja se poznavanje MS-DOS-a i nekog od C-prevodilaca rasprostranjenih na PC-racunarima (Microsoft, Borland, Zortech itd.)

Ukratko o programskom jeziku C Autor ukratko prikazuje programski jezik C sa prostim i slozenim leksickim konstrukcijama, definisane tipove podataka, definisane operacije nad podacima, skup naredbi i strukturu programa. Posto procitate ovaj sazet prikaz programskog jezika, moci cete da napisete svoje prve programe na jeziku C. O algoritmima Definise se pojam algoritma i nacin njegovog zapisivanja pomocu algoritamske seme na prirodnom jeziku, na pseudojeziku (jezik izmedju prirodnog jezika i programskih jezika) i na nekom programskom jeziku. Daje se prikaz postupka za ocenjivanje karakteristika nekog algoritma (tzv. slozenost algoritma).

Programski jezik C i mikroracunari Prikazuje se programiranje na PC-kompatibilnim racunarima na programskom jeziku C. Prikazano je povezivanje (sprezanje) delova programa napisanih na programskom jeziku C i na asembleru, pozivanje nekih DOS-ovih i BIOS-ovih servisa (sistemskih funkcija ili poziva), rad u razlicitim video-rezimima (tekst, grafika), primer dvodimenzione i trodimenzione grafike (razvijena je notacija za zapis funkcije (slicna notaciji u vecini programskih jezika) i razvijena funkcija za leksicku i sintaksnu analizu tako zapisane funkcije; ako je funkcija ispravno zapisana crta se njen grafik), kao i programiranje modema. Sortiranje Sortiranje je jedan od problema koji se najcesce javlja u programiranju.

Potrebno je skup vrednosti, koje se mogu porediti, urediti u neopadajuci ili nerastuci poredak. Prikazani su razliciti postupci sortiranja: od jednostavnijih za pisanje (koji se duze izvrsavaju) do slozenih (koji je teze razumeti, ali su zato vrlo efikasni). Prikazani su postupci: heap, quick, merge, shell, radix. Pretrazivanje Pretrazivanje je drugi problem koji se vrlo cesto srece u svakodnevnom programiranju. Potrebno je utvrditi da li se u nekom skupu vrednosti nalazi odredjena (zadata) vrednost. Skup moze biti proizvoljne velicine i od njegove organizacije zavisi i koliko ce trajati pretrazivanje. Prikazani su razliciti postupci za predstavljanje skupa, pomocu niza i pomocu drvoidnih struktura: binarno drvo za pretrazivanje, balansirano binarno drvo, crveno-crno drvo, B-drvo, radix drvo (drvo zasnovano na zapisu vrednosti) itd. Grafovi Intuitivno, graf je skup cvorova i skup ivica koje povezuju pojedine parove cvorova (ne mora izmedju bilo koja dva cvora postojati ivica).

Pomocu grafova se modeliraju stvari iz realnog sveta: putna ili zeleznicka mreza, PTT-mreza, vodovod itd. Tako izucavanje grafova ima veliki prakticni znacaj. Prikazani su algoritmi za neke poznate probleme: obilazak grafa, odredjivanje artikulacionih tacaka grafa (to su cvorovi cijim bi izbacivanjem iz grafa, graf bio razbijen na vise delova) odredjivanje mostova grafa (ivice cijim bi brisanjem graf bio razbijen), razbijanje grafa na komponente, najkraca rastojanja, drvo razapinjanja grafa. Obrada reci Ova glava se bavi pronalazenjem pojavljivanja jedne reci u okviru druge reci (engl. string matching). To je jos jedan problem koji se cesto srece u svakodnevnom programiranju. Prikazano je nekoliko vrlo efikasnih algoritama za taj problem. Rad sa velikim celim brojevima Kao i vecina programskih jezika i programski jezik C omogucava rad sa relativno malim celim brojevima (u najpovoljnijem slucaju mogu biti registrovani brojevi manji od 232 sto je negde oko 4 milijarde).

U praksi se nekad (posebno u teoriji brojeva) radi sa daleko vecim brojevima. Prikazan je nacin predstavljanja takvih brojeva u racunaru i osnovne aritmeticke operacije nad takvim brojevima. Prikazani su i neki postupci za faktorisanje velikih brojeva (prikaz broja u obliku proizvoda dva ili vise celih brojeva). Pretrazivanje sa vracanjem (engl. backtracking) Ovo je jedna dosta koriscena tehnika za odredjivanje resenja nekih problema (najcesce su to problemi u bliskoj vezi sa kombinatorikom ili vestackom inteligencijom). Koriscenje tehnike je prikazano na dosta poznatih primera kao sto su: postavljanje kraljica na sahovsku tablu tako da se ne tuku, obilazak sahovske table pomocu skakaca tako da svako polje bude poseceno tacno jedanput, obilazak table skakacem tako da skakac ne presece svoju putanju itd.

Tehnika dinamickog programiranja Pod dinamickim programiranjem se podrazumeva tehnika u kojoj se ubrzanje racunanja postize memorisanjem odredjenih medjurezultata tako da kasnije ne moraju ponovo da se izracunavaju. Prikazano je nekoliko poznatih primera koji su karakteristicni za tehniku dinamickog programiranja: lancano mnozenje matrica, pronalazenje najduzeg zajednickog podniza dva niza, triangulacija konveksnog poligona i jedno resenje problema trgovackog putnika.