Uvod u teoriju računarstva

Prijava

HrvatskiEnglishen

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,