Uvod u teoriju računarstva

Ishodi učenja

  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

Oblici nastave

Predavanja

Mješovito e-učenje

Laboratorij

Tjedni plan nastave

  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.

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,

Nositelji

Izv. prof. dr. sc.
Goran Delač
Doc. dr. sc.
Ante Đerek
Izv. prof. dr. sc.
Zoran Kalafatić
Prof. dr. sc.
Siniša Srbljić
Izv. prof. dr. sc.
Dejan Škvorc
Doc. dr. sc.
Klemo Vladimir
Izv. prof. dr. sc.
Marin Šilić

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