Cilj i ishod predmeta
Sticanje opštih i stručnih znanja teorije algoritama, automata i jezika Studenti će usvojiti važne pojmove i znanja teorije algoritama, automata i jezika – o determinističkim i nedeterminističkim konačnim automatima, regularnim izrazima i regularnim jezicima, osobinama regularnih jezika, kontekst-slobodnim gramatikama i jezicima, potisnim automatima, osobinama kontekst-slobodnih jezika, Tjuringovoj mašini, odlučivosti, klasama problema polinomijalne i eksponencijalne složenosti.
Teorijska nastava
Alfabet. String i jezik nad alfabetom. Formalne gramatike. Jezik definisan gramatikom. Hijerarhija formalnih gramatika prema Čomskom. Deterministički konačni automati. Funkcija prelaza, proširena funkcija prelaza i jezik DKA. Nedeterministički konačni automati. Proširena funkcija prelaza i jezik NKA. Ekvivalentnost DKA i NKA, konstrukcija metodom podskupova. NKA sa praznim prelazima (ɛ – NKA). ɛ-zatvorenje. Proširena funkcija prelaza i jezik ɛ – NKA. Ekvivalentnost ɛ – NKA i DKA. Regularni izrazi. Konačni automati i regularni izrazi. Ekvivalentnost regularnih izraza i DKA kao formalizama. Konstrukcija regularnog izraza na osnovu datog DKA. Konstrukcija DKA na osnovu datog regularnog izraza. Primena regularnih izraza – leksička analiza. Regularni jezici. Pumpung lemma. Ekvivalentnost i minimizacija automata. Minimizacija DKA. Kontekst-slobodne gramatike. Izvođenja. Jezik definisan gramatikom. Stablo izvođenja. Primena kontekst–slobodnih gramatika – parseri. Potisni automati. Prihvatanje završnim stanjem. Prihvatanje praznim stekom. Ekvivalentnost kontekst- slobodnih gramatika i PA. Deterministički PA. Osobine kontekst-slobodnih jezika. Normalna forma Čomskog za kontekst-slobodne gramatike. Pumpung lemma. Testiranje da li data reč pripada datom kontekst-slobodnom jeziku. Tjuringova mašina. Tjuringova mašina sa više traka. Nedeterministička Tjuringova mašina. Neodlučivost. Rekurzivno nabrojivi i rekurzivni jezici. Klase problema P i NP. NP – kompletni problemi. Dokaz NP – kompletnosti problema CSAT i 3SAT.
Praktična nastava
Predavanja i vežbe. Predavanja se izvode kombinovano. Na predavanjima se izlaže teorijski deo gradiva propraćen karakterističnim primerima radi lakšeg razumevanja gradiva. Na vežbama, koja prate predavanja, rade se karakteristični zadaci i produbljuje se izloženo gradivo sa predavanja. Pored predavanja i vežbi redovno se održavaju i konsultacije.