Uvod u teoriju računarstva

Opis predmeta

Predmet uvodi formalne modele automata i gramatika za potrebe opisa, definiranja, programskog i sklopovskog ostvarivanja te provjere ispravnosti rada računalnih i komunikacijskih procesa, protokola i sustava. Objašnjavaju se osnovna svojstva računalnih procesa i sustava, kao što su determinizam, odlučivost, izračunljivost, složenost i učinkovitost. Daje se osnova teorije automata, formalnih gramatika i jezika. Proučava se Chomskyeva hijerarhija jezika: regularni, kontekstno-neovisni, kontekstno-ovisni, rekurzivni i rekurzivno-prebrojivi jezici. Definiraju se razredi složenosti i hijerarhija razreda složenosti: potpuni i teški problemi, razredi P i NP te postupak svođenja.

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

Predavanja popraćena PowerPoint projekcijom s prikazom teorijskih načela, popratnim primjerima i rješavanjem zadataka

Laboratorij

Programsko ostvarenje konačnog automata, algoritama za minimizaciju konačnog automata, potisnog automata i tehnike parsiranja rekurzivnim spustom. Studenti samostalno programski ostvaruju laboratorijski zadatak i putem web-aplikacije predaju rješenja na automatizirano ocjenjivanje.

Način ocjenjivanja

Kontinuirana nastava Ispitni rok
Vrsta provjere Prag Udio u ocjeni Prag Udio u ocjeni
Laboratorijske vježbe 50 % 30 % 50 % 0 %
Međuispit: Pismeni 50 % 35 % 0 %
Završni ispit: Pismeni 50 % 35 %
Ispit: Pismeni 50 % 100 %
Ispit: Usmeni 100 %

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

Siniša Srbljić (2010.), Uvod u teoriju računarstva, Element
Juraj Hromkovič (2003.), Theoretical Computer Science, Springer Science & Business Media
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2007.), Introduction to Automata Theory, Languages, and Computation, Addison-Wesley
Peter Linz (2001.), An Introduction to Formal Languages and Automata, Jones & Bartlett Learning
Dexter C. Kozen (2007.), Automata and Computability, Springer Science & Business Media

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
Izv. prof. dr. sc.
Klemo Vladimir
Izv. prof. dr. sc.
Marin Šilić

Predavanja

Dr. sc.
Adrian Satja Kurdija

Laboratorijske vježbe

Dr. sc.
Adrian Satja Kurdija
Lucija Šikić
mag. ing.
Iva Jurković
mag. ing.
Ivan Grgurina
mag. ing.
Rudolf Lovrenčić
mag. ing.
Petar Paradžik
mag. inf. et math.

Za studente

Izvedba

ID 183412
  Ljetni semestar
5 ECTS
R1 Engleski jezik
R2 E-učenje
60 Predavanja
10 Laboratorijske vježbe

Ocjenjivanje

88 izvrstan
75 vrlo dobar
63 dobar
50 dovoljan

Sličan predmet