Uvod u teoriju računarstva

Prikazani su podaci za akademsku godinu: 2023./2024.

Nositelji

Izv. prof. dr. sc.
Marin Šilić
Izv. prof. dr. sc.
Goran Delač
Prof. dr. sc.
Dejan Škvorc
Izv. prof. dr. sc.
Klemo Vladimir
Izv. prof. dr. sc.
Zoran Kalafatić
Doc. dr. sc.
Ante Đerek

Predavanja

Doc. dr. sc.
Adrian Satja Kurdija

Laboratorijske vježbe

Helena Čeović
Stjepan Požgaj
mag. inf. et math.
Petar Paradžik
mag. inf. et math.
Doc. dr. sc.
Adrian Satja Kurdija
Davor Vukadin
mag. ing.

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.

Studijski programi

Sveučilišni preddiplomski
[FER3-HR] Računarstvo - studij
(4. semestar)

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

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

Za studente

Izvedba

ID 183412
  Ljetni semestar
5 ECTS
R3 Engleski jezik
R2 E-učenje
60 Predavanja
0 Seminar
0 Auditorne vježbe
10 Laboratorijske vježbe
0 Konstrukcijske vježbe

Ocjenjivanje

88 izvrstan
75 vrlo dobar
63 dobar
50 dovoljan

Sličan predmet