Uvod u teoriju računarstva
Ishodi učenja
- opisati ponašanje računalnog sustava i komunikacijskog protokola formalnim jezikom
- opisati ponašanje računalnog sustava, komunikacijskog protokola ili nekog drugog tehničkog sustava formalnim jezikom
- dizajnirati računalni proces primjenom formalnog modela
- primijeniti formalne modele za provjeru valjanosti računalnog sustava
- klasificirati problem s obzirom na Chomskyevu hijerarhiju formalnih jezika
- odabrati formalni model optimalne složenosti za potrebe opisa, oblikovanja i izgradnje računalnog sustava
- ocijeniti vremensku i prostornu složenost računalnog procesa
- ocijeniti učinkovitost računalnog sustava i komunikacijskog protokola
- ocijeniti razred složenosti problema
Oblici nastave
Predavanja
Mješovito e-učenje
Laboratorij
Mješovito e-učenje
Laboratorij
Tjedni plan nastave
- Generiranje i parsiranje niza. Deterministički konačni automat.
- Minimizacija determinističkog konačnog automata. Nedeterministički konačni automat. Nedeterministički konačni automat s epsilon prijelazima.
- Istovjetnost determinističkog. nedeterminističkog i nedeterminističkog konačnog automata s epsilon prijelazima.
- Regularni jezici. Regularni izrazi. Operacije nad automatima. Svojstva regularnih. kontekstno-neovisnih. rekurzivnih i rekurzivno-prebrojivih jezika. svojstvo napuhavanja.
- Kontekstno-neovisni jezici. Svojstva regularnih. kontekstno-neovisnih. rekurzivnih i rekurzivno-prebrojivih jezika. svojstvo napuhavanja.
- Kontekstno-ovisni jezici.
- Potisni automat.
- Međuispit.
- 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).
- Chomskyjeva hijerarhija formalnih jezika. gramatika i automata. Kontekstno-ovisni jezici. kontekstno-ovisna gramatika i linearno-ograničeni automat.
- 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.
- 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).
- 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.
- 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.
- Završni ispit.
Studijski programi
Sveučilišni preddiplomski
Računarstvo (studij)
(4. semestar)
Literatura
(.), Uvod u teoriju računarstva; S. Srbljić; Element Zagreb; 2007; ISBN: 978-953-197-624-4,
(.), Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography; J. Hromkovic; Springer; 2003; ISBN: 978-3540140153,
(.), Introduction to Automata Theory, Languages, and Computation; J. E. Hopcroft, R. Motwani, J. D. Ullman; Addison-Wesley; 2000; ISBN: 978-0201441246,
(.), An Introduction to Formal Languages and Automata; P. Linz; Jones & Bartlett Publishers; 2000; ISBN: 978-0763714222,
(.), Automata and Computability; D. C. Kozen; Springer; 1997; ISBN: 978-0387949079,
Laboratorijske vježbe
Izvedba
ID 183412
Ljetni semestar
5 ECTS
R1 Engleski jezik
R1 E-učenje
60 Predavanja
0 Auditorne vježbe
10 Laboratorijske vježbe
0 Konstrukcijske vježbe
Ocjenjivanje
izvrstan
vrlo dobar
dobar
dovoljan