Fakultet tehničkih nauka

Predmet: Teorija automata (17.0M512)

Matične organizacione jedinice predmeta: Departman za opšte discipline u tehnici
Osnovne informacije:
 
Kategorija Teorijsko-metodološki
Uža naučna oblast Teorijska i primenjena matematika
ESPB 5

Osnovni cilj predmeta jeste sticanje osnovnih znanja iz teorije automata, uključujući regularne jezike, konačne automate, formalne jezike i potisne automate. Studenti će biti upoznati sa ovim fundamentalnim formalnim modelima, ali i sa njihovom primenom u nekim granama računarstva (pre svega uticaju na razvoj kompajlera, razvoj programskih jezika i formalnih modela za konkurentne sisteme). Tokom izvođenja predmeta, biće proučavani navedeni formalni modeli, kao i tehnike za njihovu analizu, kroz primere i diskusiju. Konačni cilj jeste da studenti razviju veštine za postavljanja formalnih modela i korišćenje formalnih alata i tehnika za analizu kompleksnih sistema.

Kao ishod predmeta, student će posedovati osnovna znanja iz teorije automata i formalnih jezika. Pored toga, studenti će ovladati veštinom postavljanja formalnih metoda i analiziranjem njihovih osobina, koristeći poznate metode iz navedenih oblasti. Studenti će naučiti formalne tehnike koje se najčešće koriste u nekim oblastima računarstva (npr. razvoju programskih jezika).

Deteministički konačni automati, definicija i primeri. Regularni jezici i regularne operacije. Nedeterministički konačni automati, definicija i primeri. Regularni izrazi i njihova veza sa konačnim automatima. Jezička ekvivalencija nad konačnim automatima. Kontekstno nezavisni jezici. Potisni automati. Veza izmedju potisnih automata i kontekstno nezavisnih jezika.

Na predavanjima se izlaže teoretski deo gradiva propraćen karakterističnim primerima radi lakšeg razumevanja gradiva. Student samostalno proučava dodatnu literaturu i diskutuje je sa nastavnikom na konsultacijama.

Autori Naziv Godina Izdavač Jezik
S. Crvenković , R. Madaras, N. Mudrinski Zbirka zadataka iz teorije automata 2005 PMF, Novi Sad Srpski jezik
Hopcroft, J.E., Ullman, J.D. Introduction to automata theory, languges and computation 1979 Adison-Wesley, Reading, Mass. Engleski
Shawn Hedman A First Course in Logic 2008 Oxford University Press Engleski
Madarász, R., Crvenković, S. Uvod u teoriju automata i formalnih jezika 1995 Stylos, Novi Sad Srpski jezik
Sipser, M. Introduction to the Theory of Computation 2006 Thomson Course Technology, Boston Engleski
Dexter C. Kozen Automata and Computability 1997 Springer Engleski
Predmetna aktivnost Predispitna Obavezna Broj poena
Predmetna aktivnost
Prisustvo na predavanjima
Predispitna
Da
Obavezna
Da
Broj poena
5.00
Predmetna aktivnost
Test
Predispitna
Da
Obavezna
Da
Broj poena
10.00
Predmetna aktivnost
Teorijski deo ispita
Predispitna
Ne
Obavezna
Da
Broj poena
30.00
Predmetna aktivnost
Pismeni deo ispita - kombinovani zadaci i teorija
Predispitna
Ne
Obavezna
Da
Broj poena
40.00
Predmetna aktivnost
Test
Predispitna
Da
Obavezna
Da
Broj poena
10.00
Predmetna aktivnost
Prisustvo na vežbama
Predispitna
Da
Obavezna
Da
Broj poena
5.00
Predavanja
Auditorne vežbe