DIT - Matematička logika u računarstvu

Pojam izračunljivosti i modeli izračunljivosti. Imperativni modeli: Turingov stroj, strojevi s neograničenim registrima, programski jezik dijagrama toka, strukturirani programski jezici. Formalna sintaksa: Postovi sustavi, Markovljevi algoritmi, formalne gramatike, konačni automati. Formalna semantika: semantika aritmetičkih izraza, semantika booleovskih izraza, operacijska semantika naredbi. Funkcijski modeli: lambda račun, Scheme, Haskell. Logički model: deduktivni račun, Prolog.

Razumjeti klasične modele izračunljivosti i na njima zasnovane programske paradigme.

Znati modelirati računske probleme u odgovarajućem računskom modelu i programskom jeziku

1. Znati dijagonalnu metodu
2. Razlikovati na intuitivnom nivou izračunljive i neizračunljive funkcije i probleme.
3. Znati konstruirati Turingove strojeve, programe za stroj s neograničenim registrima i programe u jeziku dijagrama toka za algoritamsko rješavanje jednostavnijeg problema.
4. Znati konstruirati Postove sisteme i Markovljeve algoritme za algoritamsko rješavanje jednostavnijeg problema.
5. Znati konstruirati formalne gramatike za jednostavnije jezike.
6. Znati konstruirati konačne automate za prepoznavanje jednostavnijih jezika.
7. Znati izračunati po pravilima formalne semantike vrijednost aritmetičkih i boleovskih izraza u danom stanju i stanje u koje će prijeći početno stanje pri izvršenju programske naredbe.
8. Znati napisati program u lambda računu, Sheme i Haskellu za algoritamsko rješavanje jednostavnijeg problema.
9. Znati napisati program u Prologu za algoritamsko rješavanje jednostavnijeg problema

1. vladati osnovnim teorijskim principima računarstva, pojmom izračunljivosti, klasičnim modelima izračunljivosti, formalnom sintaksom i semantikom programskih jezika.

2. znati primijeniti imperativni, funkcijski i logički pristup u algoritamskom rješavanju problema

3. znati pisati jednostavnije programe u jezicima Scheme, Haskell i Prolog.

1. Klasični modeli izračunljivosti Matematičko logički korijeni računarstva Intuitivni pojam izračunljivosti
2. Imperativni model: Turingovi strojevi
3. Imperativni model: URM strojevi
4. Imperativni model: programski jezici višeg nivoa
5. Rekurzivni model: Postovi sustavi
6. Jednostavniji modeli od Postova: string rewriting systems, Markovljevi algoritmi i formalne gramatike
7. Ponavljanje i priprema za prvi kolokvij
8. Funkcijski model: lambda račun 1
9. Funkcijski model: lambda račun 2
10. Funkcijski model: programski jezik SCHEME 1
11. Funkcijski model: programski jezik SCHEME 2
12. Logički model: programski jezik PROLOG 1
13. Logički model: programski jezik PROLOG 2
14. Logički model: rezolucija i unifikacija
15. Ponavljanje i priprema za drugi kolokvij

1. argumentiranje dijagonalnim metodom prepoznavanje izračunljivosti i poluizračunljivosti
2. Programiranje Turingovih Strojeva
3. Programiranje URM strojeva
4. Programiranje u jeziku dijagrama toka
5. Programiranje u Postovim sustavima
6. Programiranje u Markovljevim algoritmima Konstrukcija formalnih gramatika
7. prvi kolokvij
8. Izvršavanje lambda računa
9. Programiranje u lambda računu
10. Programiranje u jeziku Scheme - osnove
11. Programiranje u jeziku Scheme - funkcije višeg reda i liste
12. Programiranje u Prologu
13. Izvršenje Prolog programa i rezolucija
14. Izvršenje Prolog programa i unifikacija
15. Drugi kolokvij

1. Nije definirano
2. Nije definirano

1. Nije definirano

1. testovi i kolokviji, konzultacije, samostalni rad u laboratoriju i samostalno učenje