FESB NASTAVA
Loading...
    Diplomski
    250 Računarstvo
    1. semestar
    Nema predmeta
    Pretraži predmete po nazivu ili kôdu
    Upit treba biti dulji od 1 znaka...
    Nema rezultata
    U polje za pretragu upišite naziv ili kôd predmeta koji želite pronaći

      Modeli računarstva

      (FELK02)
      2024/25 godina
      preduvjeti za upis
      nema
      ciljevi predmeta

      Kolegij pruža temeljna teoretska znanja s područja automata, gramatika i jezika kao osnovu jezgre računarstva

      očekivani ishodi učenja

      Studenti će nakon uspješno savladanog predmeta moći:
      1. Organizirati leksičku, sintaktičku i semantičku analizu.
      2. Izgraditi i ocijeniti determinirani konačni automat.
      3. Kreirati i opravdati nedeterminirani konačni automat.
      4. Oblikovati regularne izraze.
      5. Prezentirati svojstvo napuhivanja.
      6. Generirati normalne oblike Chomskog i Greibacha.
      7. Razviti potisni automat.
      8. Opravdati Turingov stroj i gramatiku neograničenih produkcija.
      9.Opravdati linearno ograničeni automat.
      10. Rangirati klase jezika i automata.

      nositelji predmeta
      Čoko Duje
      nastava i predavači
       
      Predavanja
      30 sati
      2 sata tjedno × 15 tjedana
       
      Auditorne vježbe
      15 sati
      1 sat tjedno × 15 tjedana
       
      Laboratorijske vježbe
      15 sati
      1 sat tjedno × 15 tjedana
      ECTS
      5
      Diplomski 250
      Računarstvo
      1. semestar
      1. godina
      predmet napredne razine
      Način ocjenjivanja
      apsolutno
      sadržaj

      Programabilni strojevi. Programski opis algoritma. Jezični procesori. Leksička, sintaktička i semantička analiza. Generiranje međukoda. Formalna definicija abecede, niza i jezika. Operacije među jezicima. Regularni jezici. Konačni automati. Formalne gramatike. Regularne gramatike. Kontekstno neovisni jezici. Kontekstno neovisna gramatika. Potisni automat. Rekurzivno prebrojivi jezici. Turingov stroj. Gramatika neograničenih produkcija. Kontekstno ovisni jezici. Kontekstno ovisna gramatika. Linearno ograničeni automat. Razredba jezika, automata i gramatika: Strukturna složenost jezika. Složenost prihvaćanja jezika

      preporučena literatura

      • Srbljić, Siniša.: Uvod u teoriju računarstva, Element, Zagreb, 2010.

      dopunska literatura
      prazno
      jezik poduke
      Hrvatski
      način praćenja kvalitete i uspješnosti izvedbe svakog predmeta i/ili modula

      Mišljenja studenata o kvaliteti nastave putem anketa.
      Povremeno promatranje i evaluacija nastave od strane predstojnika zavoda za elektroniku.

      ispit (način polaganja, ispitni rokovi)

      Tijekom semestra održavaju se dva kolokvija. Prvi kolokvij je nakon 7 tjedana, a drugi nakon 13 tjedana neposredne nastave. Po završetku nastave održat će se tri ispitna roka (dva završna u ljetnom i popravni u jesenskom ispitnom roku).

      Tijekom semestra studenti pišu 5 domaćih radova rješavanja zadataka.
      Na početku svakog termina laboratorijskih vježbi pišu se ulazni testovi kako bi se potvrdila spremnost studenata da odrade laboratorijske vježbe.

      Uvjet za pozitivnu ocjenu je 50% bodova na svakom kolokviju / ispitu, pozitivno ocijenjeni svi domaći radovi i položene sve laboratorijske vježbe.

      Ukupni postotak utvrđuje se prema sljedećoj formuli:

      Ocjena(%)=0,2L + 0,1DR + 0,7(K1+K2)/2

      L - ocjena iz laboratorijskih vježbi izražena u postocima,
      DR - ocjena iz domaćih radova izražena u postocima,
      K1, K2 - bodovi na kolokvijima izraženi u postocima.

      Konačna se ocjena utvrđuje na sljedeći način:

      Postotak Ocjena
      50% do 61% dovoljan (2)
      62% do 74% dobar (3)
      75% do 87% vrlo dobar (4)
      88% do 100% izvrstan (5)

      Kolokviji i ispiti se održavaju u terminima određenim kalendarom nastavne djelatnosti u tekućoj akademskoj godini.

        Nastavne jedinice za Predavanja Broj sati
      1.

      1. UVODNA RAZMATRANJA
      1.1. Jezični procesor
      1.2. Procesi jezičnog procesora
      1.3. Znakovlje i oznake
      2. DETERMINISTIČKI KONAČNI AUTOMAT (DKA)
      2.1. Regularni jezik i konačni automat
      2.2. Deterministički konačni automat i niz
      2.3. Model DKA i programsko ostvarenje
      2.4. Definicije ekvivalentnosti

      		 2 sata
      2.

      3. MINIMIZACIJA KONAČNOG AUTOMATA
      3.1. Algoritam primitivne tablice
      3.2. Algoritam huffman-Mealy
      3.3. Algoritam tablice implikanata
      3.4. Nedohvatljiva stanja
      4. NEDETERMINISTIČKI KONAČNI AUTOMAT (NKA)
      4.1. Pristup i rad NKA
      4.2. Definicija NKA
      4.3. Izgradnja DKA iz zadanog NKA
      4.4. Istovjetnost NKA i DKA

      		 2 sata
      3.

      5. EPSILON - NEDETERMINISTIČKI KONAČNI AUTOMAT (-NKA)
      5.1. Pristup i rad -NKA
      5.2. Definicija -NKA
      5.3. Izgradnja NKA iz zadanog -NKA
      5.4. Istovjetnost -NKA i NKA
      6. KONAČNI AUTOMATI SA IZLAZOM
      6.1. Moore automat
      6.2. Mealy automat
      6.3. Konstrukcija Mealy iz zadanog Moore DKA
      6.4. Konstrukcija Moore iz zadanog Mealy DKA

      		 2 sata
      4.

      7. REGULARNI JEZICI I IZRAZI
      7.1. Definicija regularnih izraza
      7.2. Rekurzivna pravila za RI
      7.3. Konstrukcija -NKA iz RI
      7.4. Generator konačnog automata
      8. SVOJSTVA REGULARNIH JEZIKA
      8.1. Klase jezika
      8.2. Zatvorenost regularnih jezika
      8.3. Regularne definicije
      9. SVOJSTVO NAPUHAVANJA
      9.1. Definicija svojstva napuhavanja
      9.2. Dokaz neregularnosti

      		 2 sata
      5.

      10. REGULARNA GRAMATIKA
      10.1. Kontekstno neovisna gramatika
      10.2. Formalna gramatika i jezici
      10.3. Regularna gramatika
      10.4. Sinteza NKA iz regularne gramatike
      10.5. Desno linearna gramatika
      10.6. Lijevo linearna gramatika
      11. NEJEDNOZNAČNOST GRAMATIKE, JEZIKA I NIZA
      11.1. Nejednoznačnost niza
      11.2. Sistematizacija zamjene
      11.3. Promjena gramatike
      11.4. Promjena jezika

      		 2 sata
      6.

      12. POJEDNOSTAVLJENJE GRAMATIKE
      12.1. Definicija pojednostavljenja gramatike
      12.2. Odbacivanje beskorisnih znakova
      12.3. Odbacivanje -produkcija i jediničnih produkcija
      13. NORMALNI OBLIK CHOMSKOG
      13.1. Definicija normalnog oblika Chomskog
      13.2. Postupak pojednostavljenja gramatike u CNF

      		 2 sata
      7.

      14. NORMALNI OBLIK GREIBACHA
      14.1. Definicija normalnog oblika Greibacha
      14.2. Algoritam zamjene krajnje lijevog znaka
      14.3. Algoritam razrješenja lijeve rekurzije
      14.4. Koraci postizanja GNF
      15. RAZLAGANJE (PARSIRANJE) NIZA
      15.1. Definicija razlaganja niza
      15.2. LL(1) gramatika i razlaganje
      15.3. Razlaganje od dna prema vrhu
      15.4. LR(k) razlaganje

      		 2 sata
      8.

      1. kolokvij

      		 2 sata
      9.

      16. POTISNI AUTOMAT (PA)
      16.1. Model i rad potisnog automata
      16.2. Formalna definicija potisnog automata
      16.3. Deterministički i nedeterministički PA
      17. TRANSFORMACIJE POTISNOG AUTOMATA
      17.1. Konstrukcija ESPA iz ASPA
      17.2. Dokaz istovjetnosti ESPA i ASPA
      17.3. Konstrukcija ASPA iz ESPA
      18. POTISNI AUTOMAT I CFG
      18.1. Konstrukcija ESPA iz CFG
      18.2. Sinteza CFG iz ESPA

      		 2 sata
      10.

      19. SVOJSTVA KONTEKSTNO NEOVISNIH JEZIKA
      19.1. Kontekstno neovisni jezik i PA
      19.2. Svojstva zatvorenosti KNJ na uniju, nadovezivanje
      19.3. . Svojstva zatvorenosti KNJ na Kleene, supstituciju
      19.4. Zatvorenost presjeka KNJ i RJ
      20. SVOJSTVO NAPUHAVANJA KNJ
      20.1. Svojstvo napuhavanja KNJ

      		 2 sata
      11.

      21. TURINGOV STROJ
      21.1. Formalna definicija Turingovog stroja
      21.2. Prihvaćanje jezika Turingovim strojem
      21.3. Cjelobrojna aritmetika Turingovim strojem
      22. SVOJSTVA TURINGOVOG STROJA
      22.1. Višekomponentna stanja i znakovi trake
      22.2. Proširenja i pojednostavljenja Turingovog stroja
      22.3. Generiranje jezika Turingovim strojem
      22.4. Istovjetnost rekurzivnog jezika i kanonskog slijeda

      		 2 sata
      12.

      23. GRAMATIKA NEOGRANIČENIH PRODUKCIJA
      23.1. Formalna specifikacija gramatike neograničenih produkcija
      23.2. Konstrukcija TS iz GNP
      23.3. Konstrukcija GNP iz TS24. SVOJSTVA REKURZIVNIH JEZIKA
      24.1. Zatvorenost RekJ i RPJ obzirom na uniju
      24.2. Zatvorenost RekJ i RPJ obzirom na komplement
      25. IZRAČUNLJIVOST I ODLUČIVOST
      25.1. Izračunljivost
      25.2. Odlučivost

      		 2 sata
      13.

      26. KONTEKSTNO OVISNI JEZICI
      26.1. Definicija kontekstno ovisnog jezika i gramatike
      26.2. Linearno ovisni automat
      26.3. Konstrukcija linearno ovisnog automata iz KOG
      27. SVOJSTVA KONTEKSTNO OVISNIH JEZIKA
      27.1. Unija, nadovezivanje i Kleenee
      27.2. Presjek i komplement
      27.3. Odlučivost kontekstno ovisnih jezika

      		 2 sata
      14.

      28. STRUKTURNA SLOŽENOST JEZIKA
      28.1. Klase i hijerarhija jezika
      28.2. Hijerarhija gramatika i automata
      29. SLOŽENOST PRIHVAĆANJA JEZIKA
      29.1. Prostorna složenost
      29.2. Vremenska složenost
      29.3. Broj traka i složenost
      29.4. Sažimanje prostora i ubrzanje vremena
      30. KLASE JEZIKA PO SLOŽENOSTI
      30.1. Model složenosti i odnosi među klasama
      30.2. Vremenska složenost DTS i NTS i prostorna izgradivost
      30.3. Klasa jezika polinomne složenosti

      		 2 sata
      15.

      2. kolokvij

      		 2 sata
        Nastavne jedinice za Auditorne vježbe Broj sati
      1.

      DETERMINISTIČKI KONAČNI AUTOMAT (DKA)
      MINIMIZACIJA KONAČNOG AUTOMATA

      		 1 sat
      2.

      NEDETERMINISTIČKI KONAČNI AUTOMAT (NKA)
      EPSILON - NEDETERMINISTIČKI KONAČNI AUTOMAT (-NKA)
      KONAČNI AUTOMATI SA IZLAZOM

      		 1 sat
      3.

      REGULARNI JEZICI I IZRAZI
      REGULARNA GRAMATIKA

      		 1 sat
      4.

      NEJEDNOZNAČNOST GRAMATIKE, JEZIKA I NIZA
      POJEDNOSTAVLJENJE GRAMATIKE

      		 1 sat
      5.

      NORMALNI OBLIK CHOMSKOG

      		 1 sat
      6.

      NORMALNI OBLIK GREIBACHA

      		 1 sat
      7.

      NORMALNI OBLIK GREIBACHA

      		 1 sat
      8.

      1. kolokvij

      		 1 sat
      9.

      POTISNI AUTOMAT (PA)
      TRANSFORMACIJE POTISNOG AUTOMATA

      		1 sat
      10.

      POTISNI AUTOMAT I CFG

      		 1 sat
      11.

      TURINGOV STROJ
      GRAMATIKA NEOGRANIČENIH PRODUKCIJA

      		 1 sat
      12.

      SVOJSTVA REKURZIVNIH JEZIKA
      IZRAČUNLJIVOST I ODLUČIVOST

      		 1 sat
      13.

      KONTEKSTNO OVISNI JEZICI
      SVOJSTVA KONTEKSTNO OVISNIH JEZIKA

      		 1 sat
      14.

      STRUKTURNA SLOŽENOST JEZIKA
      KLASE JEZIKA PO SLOŽENOSTI

      		 1 sat
      15.

      2. kolokvij
        Nastavne jedinice za Laboratorijske vježbe Broj sati
      1.

      KONAČNI AUTOMAT
      REGULARNI JEZICI I IZRAZI

      		 4 sata
      2.

      POJEDNOSTAVLJENJE GRAMATIKE
      NORMALNI OBLIK CHOMSKOG
      NORMALNI OBLIK GREIBACHA

      		 4 sata
      3.

      POTISNI AUTOMAT (PA)
      TRANSFORMACIJE POTISNOG AUTOMATA
      POTISNI AUTOMAT I CFG

      		 4 sata
      4.

      TURINGOV STROJ
      GRAMATIKA NEOGRANIČENIH PRODUKCIJA

      		 4 sata
      © 2025 FESB, sva prava pridržana.
      Niste više prijavljeni

      Istekla vam je prethodna prijava te se morate ponovno prijaviti.

      Nastao je problem u radu sustava

      Informacije o problemu smo pohranili i nastojat ćemo ga riješiti. Ako vas ova greška sprječava da obavite nešto važno, možete nas odmah kontaktirati na helpdesk@fesb.hr.

      Vaš preglednik nije podržan

      Koristite web preglednik koji nije podržan. Za puno korisničko iskustvo, preuzmite najnoviju inačicu vašeg preglednika.