Naziv predmeta

Matematička logika u računarstvu

Detalji
Kod
VSITE206
Skr.
MLOG
ECTS
6
Godina
2
Semester
Ljetni semestar
Vrsta
izborni
Razina HKO 7
Diplomski studiji
E-Learning
0%
Aktivnosti
DIT zg - Zim 19/20
ECTS
Jedinice
Sati
Svega
P
1.5
15
3
45
A
1
15
2
30
L
0
0
0
0
S
0
0
0
0
KA
0
0
0
0
KP
0
2
2
0
PR
0
0
0
0
IP
0
0
0
0
IU
0
1
2
0
SU
3.5
1
105
105
NastavniciNositelji: dr. sc. Boris Čulina, prof. v. š.
Asistenti: Aleksandar Hatzivelkos, v. pred.
PreduvjetiNema
Sadržaj

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.

Ciljevi učenja

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

Ishodi učenja

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

Sposobnosti

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.

Preporučena literatura
Dodatna literatura
predavanja (P)
  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
auditorne vježbe (A)
  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
kolokvij - teorija (KP)
  1. Nije definirano
  2. Nije definirano
ispit - teorija (IU)
  1. Nije definirano
samostalno učenje (SU)
  1. testovi i kolokviji, konzultacije, samostalni rad u laboratoriju i samostalno učenje