Skip to main content

DIT - Mathematical logic in computer science

Subject name

Mathematical logic in computer science

Details
Code
VSITE206
Abbrev.
MLOG
ECTS
6
Year
2
Semester
Summer semester
Type
elective
NQF Level 7
Master's study
E-Learning
0%
Activities
DIT zg - Win 24/25
ECTS
Units
Hours
Total
T
1.5
15
3
45
N
1
15
2
30
L
0
0
0
0
S
0
0
0
0
PN
0
0
0
0
PT
0
2
2
0
PR
0
0
0
0
EN
0
0
0
0
ET
0
1
2
0
AL
3.5
1
105
105
TeachersLeaders: dr. sc. Aleksandar Hatzivelkos, v. pred.
PrerequisitsNone
Content

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.

Learning objectives

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

Learning outcomes

1. Know the diagonal method
2. Differentiate computable and incomputable functions and problems on intuitive level
3. Know how to construct Turing machines,programs for unlimited register machines and programs in flow diagram language for algorithmic solution of simpler problem
4. Know how to construct Post Systems and Markov algorithms for algorithmic solving of a simpler problem.
5. Know how to construct formal grammar for simpler languages.
6. Know how to build finite automata for recognizing simpler languages.
7. Know how to calculate, by the rules of formal semantics, the value of arithmetic and boolean expressions in the given state and the state in which the initial state will be changed when executing the program command.
8. Know how to write a program in the lambda calculus, Scheme and Haskell for algorithmic solving of a simpler problem
9. Know how to write a program in Prologue for algorithmic solving of a simpler problem

Competencies

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.

Recommended Literature
Additional Literature
lectures (T)
  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
numeric exercises (N)
  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
preliminary exam - theory (PT)
  1. Not defined
  2. Not defined
exam - theory (ET)
  1. Not defined
autonomus learning (AL)
  1. testovi i kolokviji, konzultacije, samostalni rad u laboratoriju i samostalno učenje

Ulica Vjekoslava Klaića 7, 10000 Zagreb, tel. 01/3764200 fax. 01/3764264