- 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 karakterskom skupu. Karakterski tip podataka
- 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.
- Jezički procesori (kompilatori i interpretatori)
- Formalna (funkcionalna) specifikacija. Preduslov i postuslov (pauslov). Invarijanta petlje. Završavanje programa. Primeri.
- Izvođenje programa iz specifikacije nad celim brojevima. Primeri.
- Celobrojni tip (integer). Svojstva i operacije. Interna reprezentacija. Opis sintaksa aritmetičkog izraza.
- Algoritmi za unos i ispis celih brojeva (niska karaktera u broj; dekadni u binarni i obratno)
- Bulovski (logički) tip. Svojstva i operacije. Opis sintakse bulovskog izraza.
- Realni tip (real). Svojstva i operacije. Interna reprezentacija.
- Algoritmi za unos i ispis realnih brojeva.
- Iskaz dodele i kompozicija iskaza dosdele, njihova specifikacija. Aksioma dodele
- Uslovni iskaz, njegova specifikacija i aksioma uslovnog iskaza. Primer.
- Repetitivni iskaz. Njegova specifikacija i aksioma. Invarijanta. Primer.
- Princip (teorema) linearnog pretraživanja. Specifikacija. Primeri.
- Transformacija programa. Program za izračunavanje a = [ sqr(N) ].
- Nizovski tip, njegova svojstva, specifikacija i operacije nad njim.
- 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.
- Pojam datoteke. Sekvencijalna datoteka kao struktura podataka. Svojstva i operacije. Formalna definicija i veza sa fizičkom datotekom
- Konstrukcija datoteke. Elementarni datotečki operatori. Baferska promenljiva. read i write i njihova semantika.
- Tekstuelna datoteka.
- Struktura sloga. Svojstva i vrste sloga. Operacije nad slogom.
- Procedure i funkcije. Deklaracija i poziv. Vrste prenosa parametara (primer Paskala).
- Globalni i lokalni objekti.
- Modularizacija programa. Blokovska struktura programa i njena formalizacija.
- Metodologija strukturnog programiranja. Pristupi u izgradnji programa. (Odnos pouzdanosti i efikasnosti programa?)
- Rekurzivne procedure. Izvršavanje rekurzivne procedure. Glavni poziv. Prmeri.
- Konstrukcija rekurzivnih procedura. Primer.
- Konstrukcija procedure za brzo sortiranje (quicksort). Analiza složenosti
- Rekurzivna procedura za binarno pretraživanje. Interpolirano pretraživanje. Složenost
- Eliminacija repne rekurzije. Primeri
- Pokazivački tip. Promlem alokacije i oslobađanja memorije.
- Bočni (uzgredni) efekat. Primeri
- Prednosti i nedostaci Paskala
- Linearne liste. Svojstva i operacije nad listama. Način implementacije. Primeri
- Strukture podataka: stek. Svojstva i operacije. Način implementacije. Primeri
- Strukture podataka: red. Svojstva i operacije. Način implementacije. Primeri
- Pojam drveta. Struktura i implementacija drveta. Obilazak drveta
- Binarno drvo. Svojstva i operacije nad binarnim drvetom. Obilazak drveta.
- Pretraživanje binarnog drveta. Pretraživanje binarnog drveta sa umetanjem. Stražar.
- Algoritmi nad drvetima. Primeri
- Pojam grafa. Implementacija grafa. Vrste grafova. Algoritmi na grafu.
- 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 algoritma. Tjuringova mašina. Čerčova hipoteza. Programski jezici
- Klasifikacije programskih jezika. Programske paradigme.
|