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.

Opće kompetencije

Predmet osposobljava studente za primjenu formalnih modela u inženjerstvu za potrebe oblikovanja računalnih i komunikacijskih procesa, protokola i sustava. Studenti će biti sposobni na osnovi definicije problema izraditi formalni model, ispitati valjanost, procijeniti učinkovitost i složenost, programski ili sklopovski ostvariti te dokumentirati i ispitati predloženo rješenje. Nadalje, studenti stječu dovoljno osnovnih znanja za daljnje proučavanje teorije složenih računalnih procesa i sustava.

Ishodi učenja

  1. opisati ponašanje računalnog sustava i komunikacijskog protokola formalnim jezikom
  2. dizajnirati računalni proces primjenom formalnog modela
  3. primijeniti formalne modele za provjeru valjanosti računalnog sustava
  4. klasificirati problem s obzirom na Chomskyevu hijerarhiju formalnih jezika
  5. odabrati formalni model optimalne složenosti za potrebe opisa, oblikovanja i izgradnje računalnog sustava
  6. ocijeniti vremensku i prostornu složenost računalnog procesa
  7. ocijeniti učinkovitost računalnog sustava i komunikacijskog protokola

Oblici nastave

Predavanja

Predavanja popraćena PowerPoint projekcijom, praktični primjeri primjene formalnih jezika, automata i gramatika

Provjere znanja

Dva pismena ispita

Auditorne vježbe

Rješavanje zadataka popraćeno PowerPoint projekcijom, priprema za pismene provjere znanja

Laboratorijske vježbe

Programsko ostvarenje algoritama vezanih uz teoriju formalnih jezika, automata i gramatika. Programsko ostvarenje praktične primjene automata i gramatika. Online predaja i automatsko ocjenjivanje studentskih rješenja.

Konzultacije

Pojedinačne konzultacije s nastavnicima i asistentima organiziraju se po potrebi na zahtjev studenta.

Način ocjenjivanja

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

Kontinuirana nastava: Prag (Međuispit: Pismeni + Završni ispit: Pismeni + Prisutnost i sudjelovanje u nastavi) = 50 %

Tjedni plan nastave

  1. Znak, abeceda, niz i formalni jezik; Primjer formalnog jezika, automata i gramatike; ([1], str. 1-14) Deterministički konačni automat: primjer i definicija; Deterministički konačni automat: programsko ostvarenje i minimizacija; ([1], str. 15-29)
  2. Determinizam i nedeterminizam; Nedeterministički konačni automat; Nedeterministički konačni automat s e-prijelazima; ([1], str. 29-39) Konačni automati s izlazom; Regularni izrazi; Generator konačnog automata; ([1], str. 39-51)
  3. Svojstva regularnih jezika; Formalna gramatika: primjer i definicija; Regularna gramatika; ([1], str. 51-63) Regularna gramatika (nastavak); Kontekstno-neovisni jezici; Kontekstno-neovisna gramatika; Nejednoznačnost gramatike i jezika; Pojednostavljenje kontekstno-neovisne gramatike; ([1], str. 63-78)
  4. Pojednostavljenje kontekstno-neovisne gramatike (nastavak); ([1], str. 78-88) Prepoznavanje i parsiranje niza; Programsko ostvarenje parsiranja od vrha prema dnu; Tehnika rekurzivnog spusta; Parsiranje od dna prema vrhu; LR parsiranje; ([1], str. 89-102)
  5. Potisni automat: primjer i definicija; ([1], str. 103-114) Potisni automat (nastavak); Svojstva kontekstno-neovisnih jezika; ([1], str. 114-125)
  6. Auditorne vježbe: regularni jezici;
  7. Auditorne vježbe: kontekstno-neovisni jezici;
  8. Prvi međuispit: regularni jezici, kontekstno-neovisni jezici;
  9. Rekurzivno-prebrojivi jezici; Turingov stroj; Metode izrade Turingovog stroja; ([1], str. 126-138) Prošireni modeli Turingovog stroja; ([1], str. 139-146)
  10. Pojednostavljeni modeli Turingovog stroja; Generiranje jezika Turingovim strojem; ([1], str. 146-151) Gramatika neograničenih produkcija; Svojstva rekurzivnih jezika i rekurzivno-prebrojivih jezika; Izračunljivost; Odlučivost; ([1], str. 152-164)
  11. Kontekstno-ovisni jezici; Kontekstno-ovisna gramatika; Linearno ograničeni automat; Svojstva kontekstno-ovisnih jezika; ([1], str. 165-172) Svojstva kontekstno-ovisnih jezika (nastavak); Chomskyeva razredba formalnih jezika, gramatika i automata; Definicija prostorne i vremenske složenosti; Složenost automata i jezika; Svojstva funkcija prostorne i vremenske složenosti; ([1], str. 173-187)
  12. Razredi problema s obzirom na složenost; ([1], str. 187-190) Svojstva hijerarhije jezika s obzirom na složenost; ([1], str. 190-194)
  13. Razredi problema polinomne složenosti; Učinkovitost; Postupak svođenja; Definicija potpunih i teških problema; P-potpuni (teški) i NP-potpuni (teški) problemi; ([1], str. 194-199)
  14. Auditorne vježbe: rekurzivno-prebrojivi jezici, kontekstno-ovisni jezici, teorija složenosti;
  15. Završni ispit: cjelokupno gradivo predmeta;

Studijski programi

Sveučilišni preddiplomski
Računarstvo (studij)
(4. semestar)

Za upis predmeta treba položiti predmete

Literatura

S. Srbljić (2007.), Uvod u teoriju računarstva, Element Zagreb
J. Hromkovic (2003.), Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography, Springer
J. E. Hopcroft, R. Motwani, J. D. Ullman (2000.), Introduction to Automata Theory, Languages, and Computation, Addison-Wesley
P. Linz (2000.), An Introduction to Formal Languages and Automata, Jones & Bartlett Publishers
D. C. Kozen (1997.), Automata and Computability, Springer

Predavanja

Auditorne vježbe

Laboratorijske vježbe