Teorija računanja
Osnovni podaci
- Nastavna cjelina koja predstavlja dio većeg kolegija.
- Predaje se na Zajedničkom poslijediplomskom doktorskom studiju
Sveučilišta u Osijeku, Rijeci, Splitu i Zagrebu.
- Predaje se kao drugi semestar standardnog kolegija
"Matematička logika i računarstvo".
- Služi kao podrška za polaganje pristupnog ispita iz
matematičke logike i računarstva.
- Satnica: 30 sati predavanja.
Ciljevi
- Steći osnovna znanja o teoriji računanja.
- Upoznati se s područjima kao što su formalni jezici, apstraktni
modeli računanja, odlučivost i izračunljivost, složenost računanja.
- Spoznati koje su temeljne mogućnosti i ograničenja računanja kao
takvog: što se uopće može izračunati, i uz koje troškove.
Svrha
- Razmatrane teme su važne zato što one predstavljaju temelj teorijskog
računarstva.
- Rezultati koje ćemo obraditi važni su zato jer imaju svojevrsnu
“filozofsku” težinu, naime oni pokazuju da računala nisu svemoguća,
te da postoje problemi koji ljudi ne mogu efikasno riješiti algoritmima.
- Znanja koja ćemo steći također su važna zato što se izravno primjenjuju
u drugim računarskim disciplinama, kao što su obrada teksta, interpretacija
programskih jezika, formalna verifikacija programa, umjetna inteligencija.
Sadržaj
- Regularni jezici. Konačni automati. Regularni izrazi.
Nedeterminizam. Svojstva regularnih jezika. Primjene konačnih automata.
- Kontekstno-slobodni jezici. Kontekstno-slobodne gramatike.
Potisni automati. Gramatike i ekvivalencije. Svojstva
kontekstno-slobodnih jezika. Primjene kontekstno-slobodnih gramatika.
- Turingovi strojevi. Standardni Turingovi strojevi. Varijante
Turingovih strojeva. Odlučivi problemi i rekurzivni jezici.
- Neodlučivost. Dijagonalizacija i problem zaustavljanja.
Daljnji neodlučivi problemi. Rekurzivne funkcije.
- Teorija složenosti. Vremenska složenost. Prostorna složenost.
NP-potpunost.
- NP-teški problemi. Općenito o NP-teškim problemima i njihovom
egzaktnom rješavanju. Približno rješavanje aproksimacijskim algoritmima.
Približno rješavanje pomoću heuristika.
Osnovna literatura
- Goddard W. Introducing the Theory of Computation. First Edition.
Jones & Bartlett Publishers. Sudbury, Massachusetts, 2008.
ISBN-13: 978-0763741259.
- Sipser M. Introduction to the Theory of Computation. Second Edition.
PWS Publishing Company, Boston, Massachusetts, 2005.
ISBN-13: 978-0534950972.
- Linz P. Introduction to Formal Languages and Automata. Fourth Edition.
Jones & Bartlett Publishers. Sudbury, Massachusetts, 2006.
ISBN-13: 978-0763737986.
Dodatna literatura
- Shallit J. A Second Course in Formal Languages and Automata Theory. First Edition.
Cambridge University Press, Cambridge, 2008. ISBN-13: 978-0521865722.
- Hopcroft J.E., Motwani R., Ullman J.D. Introduction to Automata Theory,
Languages, and Computation. Third Edition. Addison Wesley, Reading,
Massachusetts, 2006. ISBN-13: 978-0321462251.
- Martin J. Introduction to Languages and the Theory of Computation. Fourth Edition.
McGraw-Hill, New York, 2010. ISBN-13: 978-0073191461.
- Denning P.J., Dennis J.B., Qualitz J.E. Machines, Languages, and Computation.
Prentice Hall, Engle-wood Cliffs NJ, 1978.
- Horowitz E., Sahni S., Rajasekaran S. Computer Algorithms / C++.
Computer Science Press, New York, 1997. ISBN 0-7167-8315-0.
Način polaganja ispita
- Uobičajeni način: u sklopu pristupnog ispita “Matematička logika i računarstvo”.
- Alternativni način: izvan pristupnih ispita. Izraditi dvije domaće zadaće,
održati jedan seminar.
Nastavni materijali
- Prezentacija - Uvodno predavanje
(pdf) .
- Prezentacija - Regularni jezici
(pdf) .
- Prezentacija - Kontekstno-slobodni jezici
(pdf) .
- Prezentacija - Turingovi strojevi
(pdf) .
- Prezentacija - Neodlučivost
(pdf) .
- Prezentacija - Teorija složenosti
(pdf) .
- Prezentacija - NP-teški problemi
(pdf) .
- Pitanja na pristupnom ispitu
(pdf) .
- Prilog - dio skripte autora Cook-a
(pdf) .