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. Faktor i podreč. Poredak nad S *
- Sintaksa i semantika programskih 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
- Osnovna svojstva jezika C. Struktura programa u jeziku C. Odvojena kompilacija
- Iskazi za kontrolu toka u programskom jeziku C (karakteristike njihove upotrebe)
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
- Program - formalna (funkcionalna) specifikacija. Preduslov i pauslov. Završavanje programa. Primeri specifikacije za skip, swap, koren.
- 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. Logaritamska redukcija
- Specifikacija celobrojnog nizovskog tipa. Izvođenje programa za određivanje maksimalnog elementa niza iz funkcionalne specifikacije
- Algoritmi nad nizovima. Specifikacija, izvođenje i analiza rešenja. Primer programa za rotaciju niza. Primer "trobojke"
TIPOVI PODATAKA
- Tipovi podataka. Klasifikacija. Konstrukcija tipova u C-u
- Operacije na bitu. Primene
- Relacijski operatori. Elementi sintakse logičkog izraza. Izračunavanje logičkog izraza
- Celobrojni tip (int). Svojstva i operacije. Interna reprezentacija. Implementacije
- Opis sintakse aritmetičkog izraza. Aritmetički 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
- Pojam datoteke. Svojstva i operacije. Struktura FILE. Veza sa fizičkom datotekom. Funkcije za rad sa datotekama
- Standardni ulaz i izlaz. Redirekcija (preusmeravanje). Povezivanje komandi
- Opis i svojstva tekstuelne datoteke.
- Kopiranje datoteke u datoteku. Poređenje mogućih rešenja u C-u
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. Složenost
- Eliminacija repne rekurzije. Primeri
- Bočni (uzgredni) efekat. Primeri u C-u
APSTRAKTNI TIPOVI I ALGORITMI NAD NJIMA
- Apstraktni tipovi (skupovi, polinomi). Svosjtva. Način implementacije
- Metode sortiranja. Poređenje algoritama. Karakteristike implementacije
- Linearno, binarno i interpolirano pretraživanje.
- 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. Hafmanovi kodovi
- 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)
- Problem poređenja niski. Gruba sila. KMP-algoritam. Pojam obrasca (engl. pattern)
|