Preliminarije
- Istorija razvoja računara (kalkulatori i automati).
- Arhitektura i funkcionisanje fon Nojmanove mašine
- Struktura računara (engl. hardware). Računarski sistem
- Funkcionisanje računara (engl. software)
- Bit, bajt, karakter. ASCII-skup karaktera. Standardi o karakterskim skupovima.
- Azbuka S
, niska (reč), skup S
*, jezik nad S
, operacije nad jezicima. Sintaksa i semantika jezika
- Veštački i prirodni jezici. Formalna gramatika i njen opis. BNF, EBNF i sintaksni dijagrami. Primeri definicije identifikatora i celobrojne konstante
- Jezički procesori (kompilatori i interpretatori)
- Pojam algoritma. Tjuringova mašina. Čerčova hipoteza. Programski jezici
- Poređenje jezika: Paskal i C
HTML
- Jezici za opis strukture teksta (HTML): grafički logički izgled teksta. Pojam hiperteksta i realizacija hiperteksta u HTML-u
- Struktura dokumenta u HTML-u. Razlika između word- i html-dokumenta? Etikete u okviru etikete <head> i njihovi atributi
- Principi strukturiranja sadržaja dokumenta. Etikete u okviru tela dokumenta <body> i njihovi atributi
Specifikacija programa
- Prostor stanja. Formalna (funkcionalna) specifikacija. Preduslov i pauslov. Završavanje programa. Primeri specifikacije za skip, swap, koren.
- Izvođenje programa iz specifikacije nad celim brojevima.
- Iskaz dodele i kompozicija iskaza dodele, njihova specifikacija. Aksioma dodele. Primer "swap in place". Interpretacija u prostoru stanja
- Uslovni iskaz, njegova specifikacija i aksioma uslovnog iskaza. Primer izvođenja programa za maksimum dva broja
- Repetitivni iskaz. Njegova specifikacija i aksioma. Invarijanta. Primer - Euklidov algoritam
- Princip (teorema) linearnog pretraživanja. Specifikacija. Primer a = [ sqrt(N) ] - odnos Knutovog i Dejsktrinog rešenja.
- Transformacije programa. Primena na program za a = [ sqrt(N) ]. Efikasnost.
- Specifikacija celobrojnog nizovskog tipa. Izvođenje programa za određivanje maksimalnog elementa niza iz funkcionalne specifikacije
- Izvođenje programa za sortiranje niza iz funkcionalne specifikacije.
- Algoritmi nad nizovima. Specifikacija, izvođenje i analiza rešenja. Primeri programa za rotaciju niza i podudaranje nizova. Primer "trobojke"
- Osnovna svojstva jezika C. Struktura programa u jeziku C . Odvojena kompilacija
- Iskazi za kontrolu toka u programskom jeziku C (karakteristike njihove upotrebe)
Tipovi podataka
- Tipovi podataka. Klasifikacija. Konstrukcija tipova u C-u
- Operacije na bitu. Primene
- Pojam dvovalentne logike. Elementi sintakse logičkog izraza. Logički operatori. Izračunavanje logičkog izraza
- Celobrojni tip (integer). Svojstva i operacije. Interna reprezentacija. Implementacije
- Opis sintakse aritmetičkog izraza. Operatori, prioritet i asocijativnost u C-u
- Algoritmi za unos i ispis celih brojeva (niska karaktera u broj; dekadni u binarni i obratno)
- Karakterski tip (char) podataka u jeziku C.
- Realni tip (float). Svojstva i operacije. Interna reprezentacija.
- Algoritmi za unos i ispis realnih brojeva.
- Pokazivački tip. Nizovi i pokazivači. Primeri
- Karakterske niske. Funkcije za rad sa karakterima.
- Struktura i unija. Konstrukcija i svojstva. Primeri
- Nizovski tip, njegova svojstva, operacije nad njim, način implementiranja
- Apstraktni tipovi (skupovi, polinomi). Svosjtva. Način implementacije
- Pojam datoteke. Svojstva i operacije. Struktura FILE. Veza sa fizičkom datotekom
- Standardni ulaz i izlaz. Redirekcija (preusmeravanje).
- Opis i svojstva tekstuelne datoteke.
- Kopiranje datoteke u datoteku. Poređenje mogućih rešenja u C-u
Pojam funkcije
- Pojam funkcije. Deklaracija i poziv. Argumenti komandne linije
- Vrste prenosa parametara i način implementiranja u C-u
- Promenljivi broj argumenata funkcije u C-u. Primer funkcije za sabiranje
- Globalne i lokalne promenljive. Blok. Vidljivost promenljivih u C-u
- Modularizacija programa. Problemi i metode testiranja programa
- Čitljivost programa. Uloga komentara. Pismeno programiranje (Knut)
- Metodologija strukturnog programiranja. Pristupi u izgradnji programa. Odnos pouzdanosti i efikasnosti programa
- Rekurzivne funkcije. Izvršavanje rekurzivne funkcije. Glavni poziv. Primer rekurzivne funkcije za množenje dva cela broja
- Analiza rekurzivnih programa za Fibonačijev niz i binomni koeficijent. Problemi i rešenja. Hanojske kule
- Konstrukcija rekurzivnih procedura. Svođenje problema. Primer crtanje mustre kvadrata i mustre trouglova
- Konstrukcija rekurzivnih procedura. Konstrukcija procedure za brzo sortiranje (quicksort). Analiza složenosti
- Konstrukcija rekurzivnih procedura. Rekurzivna procedura za binarno pretraživanje. Interpolirano pretraživanje. Složenost
- Eliminacija repne rekurzije. Primeri
- Bočni (uzgredni) efekat. Primeri u C-u
Apstraktni tipovi podataka i klase algoritama
- Linearne liste. Svojstva i operacije nad listama. Načini implementacije liste.
- Problem alokacije i oslobađanja memorije. Funkcije za alokaciju memorije
- Primer sa ispisivanjem elemenata linearne liste u obrnutom redosledu. Analiza mogućih rešenja
- Strukture podataka: stek. Svojstva i operacije. Načini implementacije. Primer izračunavanja aritmetičkog izraza
- Strukture podataka: red. Svojstva i operacije. Način implementacije. Primeri
- Pojam drveta. Vrste drveta. Svojstva i implementacija drveta. Obilazak drveta u dubinu. Binarizacija drveta
- Binarno drvo. Svojstva i operacije nad binarnim drvetom. Obilazak drveta u dubinu.
- Prefiksni kodovi i kompresija
- Pretraživanje binarnog drveta. Pretraživanje binarnog drveta sa umetanjem. Primer rečnika
- Pojam grafa. Predstavljanje i implementacija grafa. Vrste grafova. Primeri
- Određivanje najkraćeg puta (Dejsktrin algoritam)
- Obilazak acikličnog grafa (određivanje čvora maksimalne težine). Markiranje. Primene
- Metode direktnog pretraživanja (hashing). Razrešenje kolizije. Otvoreno adresiranje i dvostruko heširanje
- Pretraživanje po osnovi (cifarsko pretraživanje, radix)
- Algoritmi poređenja niski. Gruba sila. KMP-algoritam. Pojam obrasca (engl. pattern)
|