Algoritmi u programskom jeziku C

Knjiga sadrži prikaz nekih vrlo poznatih i dosta korišćenih algoritama i njihovu implementaciju u programskom jeziku C. Autor je odabrao probleme koji se najčešće pojavljuju u praksi i u sličnoj literaturi na stranim jezicima. Knjiga ne pretpostavlja dublje poznavanje programskog jezika C. Prva glava daje kratak prikaz sintakse i semantike jezika C zajedno s nekim detaljima koji se obično ne pominju u knjigama. Pretpostavlja se poznavanje MS-DOS-a i nekog od C-prevodilaca rasprostranjenih na PC-računarima (Microsoft, Borland, Zortech itd.) Ukratko o programskom jeziku C Autor ukratko prikazuje programski jezik C s prostim i složenim leksičkim konstrukcijama, definisane tipove podataka, definisane operacije nad podacima, skup naredbi i strukturu programa. Pošto pročitate ovaj sažet prikaz programskog jezika, moći ćete da napišete svoje prve programe na jeziku C. O algoritmima Definiše se pojam algoritma i način njegovog zapisivanja pomoću algoritamske šeme na prirodnom jeziku, na pseudojeziku (jezik između prirodnog jezika i programskih jezika) i na nekom programskom jeziku. Daje se prikaz postupka za ocjenjivanje karakteristika nekog algoritma (tzv. složenost algoritma). Programski jezik C i mikroračunari Prikazuje se programiranje na PC - kompatibilnim računarima na programskom jeziku C. Prikazano je povezivanje (sprezanje) djelova programa napisanih na jeziku C i na asembleru, pozivanje nekih DOS-ovih i BIOS-ovih servisa (sistemskih funkcija ili poziva), rad u različitim video-režimima (tekst, grafika), primjer dvodimenzione i trodimenzione grafike (razvijena je notacija za zapis funkcije (slična notaciji u većini programskih jezika) i razvijena funkcija za leksičku 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 najčešće javlja u programiranju. Potrebno je skup vrjednosti, koje se mogu porediti, urediti u neopadajući ili nerastući poredak. Prikazani su različiti postupci sortiranja: od onih koje je jednostavnije napisati (koji se duže izvršavaju) do složenih (koje je teže razumjeti, ali su zato veoma efikasni). Prikazani su postupci: heap, quick, merge, shell, radix. Pretraživanje Pretraživanje je drugi problem koji se vrlo često sreće u svakodnevnom programiranju. Potrebno je utvrditi da li se u nekom skupu vrjednosti nalazi određena (zadata) vrijednost. Skup može biti proizvoljne veličine i od njegove organizacije zavisi i koliko će trajati pretraživanje. Prikazani su različiti postupci za predstavljanje skupa, pomoću niza i pomoću drvoidnih struktura: binarno drvo za pretraživanje, balansirano binarno drvo, crveno-crno drvo, B-drvo, radix drvo (drvo zasnovano na zapisu vrjednosti) itd. Grafovi Intuitivno, graf je skup čvorova i skup ivica koje povezuju pojedine parove čvorova (ne mora između bilo koja dva čvora postojati ivica). Pomoću grafova se modeliraju stvari iz realnog svijeta: putna ili željeznička mreža, PTT-mreža, vodovod itd. Tako izučavanje grafova ima veliki praktični značaj. Prikazani su algoritmi za neke poznate probleme: obilazak grafa, određivanje artikulacionih tacaka grafa (to su čvorovi čijim bi izbacivanjem iz grafa, graf bio razbijen na više djelova) određivanje mostova grafa (ivice čijim bi brisanjem graf bio razbijen), razbijanje grafa na komponente, najkraća rastojanja, drvo razapinjanja grafa. Obrada rječi Ova glava se bavi pronalaženjem pojavljivanja jedne rječi u okviru druge rječi (engl. String matching). To je još jedan problem koji se često sreće u svakodnevnom programiranju. Prikazano je nekoliko vrlo efikasnih algoritama za taj problem. Rad s velikim cjelim brojevima Kao većina programskih jezika, i C omogućava rad s relativno malim cjelim brojevima (u najpovoljnijem slučaju mogu biti registrovani brojevi manji od 232, što je negdje oko 4 milijarde). U praksi se nekad (posebno u teoriji brojeva) radi s daleko većim brojevima. Prikazan je način predstavljanja takvih brojeva u računaru i osnovne aritmetičke operacije nad takvim brojevima. Prikazani su i neki postupci za faktorisanje velikih brojeva (prikaz broja u obliku proizvoda dva ili vise cjelih brojeva). Pretraživanje sa vraćanjem (engl. Backtracking) Ovo je jedna dosta korištena tehnika za određivanje rješenja nekih problema (najčešće su to problemi u bliskoj vezi s kombinatorikom ili vještačkom inteligencijom). Korištenje tehnike je prikazano na više poznatih primjera kao što su: postavljanje kraljica na šahovsku tablu tako da se ne tuku, obilazak šahovske table pomoću skakača tako da svako polje bude posjećeno tačno jedanput, obilazak table skakačem tako da skakač ne preseče svoju putanju itd. Tehnika dinamičkog programiranja Pod dinamičkim programiranjem se podrazumjeva tehnika u kojoj se ubrzanje računanja postiže memorisanjem određenih međurezultata tako da kasnije ne moraju ponovo da se izračunavaju. Prikazano je nekoliko poznatih primjera koji su karakteristični za tehniku dinamičkog programiranja: lančano množenje matrica, pronalaženje najdužeg zajedničkog podniza dva niza, triangulacija konveksnog poligona i jedno rješenje problema trgovačkog putnika.