Uvod u teoriju računarstva

Prijava

HrvatskihrEnglishen

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

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)

Predmet je preduvjet za upis predmeta

Oblikovanje programske potpore

Projekt iz programske potpore

Prevođenje programskih jezika

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,