Uvod u teoriju računarstva
Opis predmeta
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
- opisati ponašanje računalnog sustava i komunikacijskog protokola 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
Oblici nastave
Predavanja popraćena PowerPoint projekcijom, praktični primjeri primjene formalnih jezika, automata i gramatika
Provjere znanjaDva pismena ispita
Auditorne vježbeRješavanje zadataka popraćeno PowerPoint projekcijom, priprema za pismene provjere znanja
Laboratorijske vježbeProgramsko 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.
KonzultacijePojedinač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 | Prag | 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
- 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)
- 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)
- 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)
- 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)
- Potisni automat: primjer i definicija; ([1], str. 103-114) Potisni automat (nastavak); Svojstva kontekstno-neovisnih jezika; ([1], str. 114-125)
- Auditorne vježbe: regularni jezici;
- Auditorne vježbe: kontekstno-neovisni jezici;
- Prvi međuispit: regularni jezici, kontekstno-neovisni jezici;
- Rekurzivno-prebrojivi jezici; Turingov stroj; Metode izrade Turingovog stroja; ([1], str. 126-138) Prošireni modeli Turingovog stroja; ([1], str. 139-146)
- 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)
- 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)
- Razredi problema s obzirom na složenost; ([1], str. 187-190) Svojstva hijerarhije jezika s obzirom na složenost; ([1], str. 190-194)
- 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)
- Auditorne vježbe: rekurzivno-prebrojivi jezici, kontekstno-ovisni jezici, teorija složenosti;
- Završni ispit: cjelokupno gradivo predmeta;
Studijski programi
Sveučilišni preddiplomski
Za upis predmeta treba položiti predmete
Predmet je preduvjet za upis predmeta
Literatura
Auditorne vježbe

Laboratorijske vježbe

