Theoretical computer science

A.Y. 2017/2018
6
Max ECTS
48
Overall hours
SSD
INF/01
Language
Italian
Learning objectives
L'insegnamento introduce le nozioni fondamentali della teoria della calcolabilità e della complessità. Viene affrontato il concetto di problema risolvibile per via algoritmica e di problema che non ammette algoritmi di risoluzione. Vengono poi presentate la classificazione e la suddivisione dei problemi in classi di complessità, definite in termini di limiti alla quantità di risorse a disposizione.
Expected learning outcomes
Undefined
Course syllabus and organization

Single session

Responsible
Lesson period
Second semester
Course syllabus
Computability
· Mathematical basics
· Cantor's pair function
· RAM and while programming languages
· Syntax and operational semantics
· Compilers
· Program encoding by numbers
· Interpreter and universal function
· "goto" elimination
· Partial recursive functions
· Church's thesis
· Undecidable problems
· Authomatic parameter passing
· Acceptable programming systems
· Recursion theorem
· Recursive and recursively enumerable sets
· Closure properties
· Rice's theorem
Complexity
· Introducing complexity theory
· Mathematical basics: "big O" notation
· Deterministic Turing machines
· Computational resources: time and space
· Time and space complexity classes
· The classes L, P, PSPACE
· Restricted Church's thesis
· Noneterministic Turing machines: time and space
· The classes NL, NP, NPSPACE
· Savitch's theorem
· Reductions among problems and completeness
· NP, P, PSPACE-complete problems
· Cook's theorem and examples of reductions
INF/01 - INFORMATICS - University credits: 6
Lessons: 48 hours
Professor(s)
Reception:
On appointment, via email
Uff. A/5/C13, Ed. LITA, V floor, Dipartimento di Fisica "Aldo Pontremoli"
Reception:
by appointment
Via Celoria, 18 - Room: 4011