THEORETICAL COMPUTER SCIENCE

CFU: 5

SSD: ING-INF/05

Contents :

Mathematical glossary: enumerability, basic algebraic structures, homomorphism, isomorphism, lattice, boolean algebra. Models for computer science: grammars, finite-state automata (FA), push-down automata (PDA), Turing machines (TM), RAM machine, partial recursive functions; non deterministic models (NFA, NPDA, NTM); relations between models, Church's thesis. Computability theory: TM enumeration, universal TM; solvable and unsolvable problems,; recursive and recursively enumerable sets, Kleene's and Rice's theorems; problem reducibility and degrees of unsolvability. Basic elements of mathematical logic : syntax and semantics of propositional calculus, satisfiability and validity; syntax and semantics of first order predicate calculus, models and validity; basic concepts of modal logics; axiomatic models, soundness and completeness. Complexity of computation: asymptotic behaviour, complexity of models (FA, PDA, TM, RAM), complexity of algorithms, evaluation of recursive algoritms; complexity classes L, NL, P, NP, EXP, PSPACE, hierarchical relations, sample problems; reductions and completeness, P-complete and NP-complete problems.

Summary

Models of computation: grammars, automata, recorsive functions. Computability and related problems. Basic elements of mathematical logic: propositional calculus, first order predicate calculus, introduction to modal logics. Complexity of computation: complexity of automata (FA, PDA, TM, RAM), complexity lcasses L, NL, P, NP, EXP, PSPACE, reductions and completeness.