Automati i formalni jezici (ETF RII AFJ 3545)

Opšte informacije

Naziv kursa

Automati i formalni jezici

Oznaka (šifra) predmeta

ETF RII AFJ 3545

Studij

ETF-B

Odsjek

Računarstvo i informatika

Godina

3

Semestar

5

Tip

Izborni

ECTS

4.5

Ukupno sati nastave

45

Sati predavanja

30

Sati vježbi

0

Sati tutorijala

15

Cilj kursa - Znanje i vještine koje treba postići student
  Ovaj kurs ima za cilj naučiti studenta osnovne koncepte teorije formalnih jezika, teorije konačnih automata i teorije kompleksnosti. U teoriji formalnih jezika proučavaju se jezici iz različitih tački gledišta s ciljem razumijevanja različitih tipova formalnih jezika. Proučavajući teoriju konačnih automata i teoriju kompleksnosti student usvaja opće modele računarstva i upoznaje se sa fundamentalnim svojstvima algoritama i digitalnih kompjutera.

Program
  1.Uvod u teoriju računarstva.

2.Konačni automati. Deterministički konačni automati. Nedeterministički konačni automati.

3.Regularni izrazi. Regularni jezici i regularna gramatika. Osobine regularnih jezika.

4.Konačni automati s izlazom. Pushdown automati. Nedeterministički i deterministički pushdown automati.

5.Kontekstno neovisni jezici i konteksno neovisna gramatika. Tehnike parsiranja.

6.Turingova mašina. Turingova teza. Univerzalna Turingova mašina. Nedeterminističke Turingove mašine.

7.Rekurzivni i rekurzivno prebrojivi jezici. Linearno ograničeni automat.

8.Konteksno ovisni jezici i konteksno ovisna gramatika. Chomskyeva hijerarhija jezika.

9.Odlučivi i neodlučivi problemi.

10.Kompleksnost automata i jezika. Klase kompleksnosti P i NP.

Literatura
Obavezna1.Bilješke i slajdovi s predavanja (moći će se preuzeti na WEB siteu Fakulteta);

2.Michael Sipser, Introduction to the Theory of Computation, Course Technology, 2005.

3.Peter Linz , An Introduction to Formal Languages and Automata, Jones and Bartlett Publishers, 2000

4.Martin, John, Introduction to Languages and the Theory of Computation, McGraw-Hill , 1997.
Preporučena...

Didaktičke metode
  Predavanja imaju za cilj dati ključne koncepte, defincije i dovoljan broj primjera koji ilustriraju teorijsku podlogu izloženu kroz predavanja. Nastavnik na predavanjima koristi prikladne prezentacijske alate. Predavanja uključuju i određeni broj primjera koji ilustriraju teoretsku podlogu koja je prethodno izložena na predavanjima. Određeni broj primjera i zadataka razmatra se i rješava na tutorijalima (pod vođenjem i pratnjom tutora), na način da se može kontinuirano pratiti dostignuti stupanj znanja koje student treba postići u okviru ovog kursa.

Način provjere znanja
  Tokom trajanja kursa student prikuplja bodove prema slijedećem sistemu:

prisustvo satima predavanja, vježbi i tutorijala: 10 bodova, student koji više od tri puta izostane s predavanja,vježbi i/ili tutorijala ne može ostvariti bodove po ovoj osnovi;

izrada domaćih zadaća: maksimalno 10 bodova; predviđena je izrada od 5 do 10 domaćih zadaća ravnomjerno raspoređenih tokom semestra;

parcijalni ispiti: dva pismena parcijalna ispita, pri čemu svaki pozitivno ocijenjen parcijalni ispit donosi 20 bodova;

Student koji je tokom trajanja semestra ostvario manje od 20 bodova ponovno upisuje ovaj kurs.

Student koji je tokom trajanja semestra ostvario 40 i više bodova pristupa usmenom završnom ispitu; ovaj ispit sastoji se iz diskusije zadataka s parcijalnih ispita, domaćih zadaća i odgovora na jednostavna pitanja koja se odnose na teme kursa.

Usmeni završni ispit donosi maksimalno 40 bodova. Da bi postigao pozitivnu završnu ocjenu, student na ovom ispitu mora ostvariti minimalno 20 bodova. Student koji ne ostvari ovaj minimum pristupa usmenom dijelu popravnog ispita.

Student koji je tokom trajanja semestra ostvario 20 i više bodova, a manje od 40 bodova, pristupa popravnom ispitu. Popravni ispit struktuiran je na slijedeći način:

pismeni dio koji je struktuiran na isti način kao i pismeni parcijalni ispit; u okviru ovog ispita student polaže zadatke iz tema za koje nije postigao prolaznu ocjenu (10 i više bodova) polažući parcijalne pismene ispite,

usmeni dio koji je struktuiran na isti način kao usmeni dio završnog ispita.

Usmenom dijelu popravnog ispita može pristupiti student koji je nakon polaganja pismenog dijela popravnog ispita uspio stvariti ukupan skor od 40 i više bodova; ovaj skor sastoji se od bodova ostvarenih kroz: prisustvo nastavi, izradu domaćih zadaća, polaganje parcijalnih sipita i polaganje pismenog dijela popravnog ispita.

Usmeni popravni ispit donosi maksimalno 40 bodova. Da bi postigao pozitivnu završnu ocjenu student na ovom ispitu mora ostvariti minimalno 20 bodova. Student koji ne ostvari ovaj minimum ponovno upisuje ovaj kurs.

Napomene
  Prilikom polaganja pismenog ispita, student može koristiti od strane nastavnika pripremljenu listu formula koje mogu biti od koristi prilikom rješavanja zadataka. Nije dozvoljeno korištenje drugih bilješki, knjiga, mobilnih telefona niti drugih elektronskih pomagala, osim džepnog elektronskog kalkulatora.



Zadaci koje student treba riješiti na ispitu su istog tipa kao oni rješavani tokom izvođenja predavanja i tutorijala.