1. opisati ponašanje računalnog sustava i komunikacijskog protokola formalnim jezikom
2. opisati ponašanje računalnog sustava, komunikacijskog protokola ili nekog drugog tehničkog sustava formalnim jezikom
3. dizajnirati računalni proces primjenom formalnog modela
4. primijeniti formalne modele za provjeru valjanosti računalnog sustava
5. klasificirati problem s obzirom na Chomskyevu hijerarhiju formalnih jezika
6. odabrati formalni model optimalne složenosti za potrebe opisa, oblikovanja i izgradnje računalnog sustava
7. ocijeniti vremensku i prostornu složenost računalnog procesa
8. ocijeniti učinkovitost računalnog sustava i komunikacijskog protokola
9. ocijeniti razred složenosti problema

Predavanja popraćena PowerPoint projekcijom s prikazom teorijskih načela, popratnim primjerima i rješavanjem zadataka

Programsko ostvarenje konačnog automata, algoritama za minimizaciju konačnog automata, potisnog automata i tehnike parsiranja rekurzivnim spustom. Studenti samostalno programski ostvaruju laboratorijski zadatak i putem web-aplikacije predaju rješenja na automatizirano ocjenjivanje.

1. Generiranje i parsiranje niza, Deterministički konačni automat
2. Minimizacija determinističkog konačnog automata, Nedeterministički konačni automat. Nedeterministički konačni automat s epsilon prijelazima
3. Istovjetnost determinističkog. nedeterminističkog i nedeterminističkog konačnog automata s epsilon prijelazima
4. Regularni jezici, Regularni izrazi, Operacije nad automatima, Svojstva regularnih. kontekstno-neovisnih. rekurzivnih i rekurzivno-prebrojivih jezika. svojstvo napuhavanja
5. Kontekstno-neovisni jezici, Svojstva regularnih. kontekstno-neovisnih. rekurzivnih i rekurzivno-prebrojivih jezika. svojstvo napuhavanja
6. Kontekstno-ovisni jezici
7. Potisni automat
8. Međuispit
9. Rekurzivno-prebrojivi jezici, Turingov stroj, Gramatika neograničenih produkcija, Svojstva regularnih. kontekstno-neovisnih. rekurzivnih i rekurzivno-prebrojivih jezika. svojstvo napuhavanja, Svojstvo napuhavanja (dokazivanje neregularnosti jezika. dokazivanje nepripadnosti jezika klasi kontekstno-neovisnih jezika)
10. Chomskyjeva hijerarhija formalnih jezika. gramatika i automata, Kontekstno-ovisni jezici. kontekstno-ovisna gramatika i linearno-ograničeni automat
11. Definicija vremenske i prostorne složenosti prihvaćanja jezika, Problem zaustavljanja, Deterministički i nedeterministički način računanja, Traktabilnost / Prikladnost, Izračunljivost s primjerima neizračunljivih funkcija, Odlučivost s primjerima neodlučivih funkcija
12. Uvod u P i NP klase složenosti. NP-potpuni i NP-teški problemi, Uvod u klasu NP-potpunih problema s primjerima (npr. problem zadovoljivosti logičke funkcije. problem naprtnjače)
13. Pregled klasa složenosti P i NP. uvod u klase složenosti PSPACE i EXP, Hijerarhija problema polinomne složenosti, NP-potpunost (Cook-Levinov teorem), Klasični NP-potpuni problemi
14. Tehnike svođenja, Klase složenosti, Klase problema polinomne složenosti (klase P i NP), Definicija potpunih i teških problema, Razlika između P-potpunih (teških) i NP-potpunih (teških) problema
15. Završni ispit