Foundations of Computing

Interdisciplinary Research Group in Socio-technical Cybersecurity

Foundations of Computing
Master of Information and Computer Sciences
Gabriele Lenzini

Foundations of Computing

Description of the course:

Mathematical Background/Definitions
–    Problems/Solving Problems
–    Computational Models
–    Algorithms/Procedures

Computability Theory
–    Unlimited Register Machine (URM)
–    URM-Computability
–    Partial /Primitive Recursive Primitive Functions
–    Computable Functions

Other approaches to Computability
–    Turing Computability
–    Other Model’s Computability
–    Church-Turing’s Thesis

Computational Complexity Theory
–    Time Complexity: the classes P and NP
–    Space complexity: Savitch’s theorem, PSPACE
–    Intractability: hierarchy theorems; exponential space completeness

Get in touch with us

SnT – Interdisciplinary Centre for Security, Reliability and Trust
29, Avenue J.F Kennedy L-1855 Luxembourg