Theoretical Computer Science
A.Y. 2018/2019
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
Lesson period: Second semester
Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi
Single course
This course cannot be attended as a single course. Please check our list of single courses to find the ones available for enrolment.
Course syllabus and organization
Milan
Responsible
Lesson period
Second semester
ATTENDING STUDENTS
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
· 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
Website
NON-ATTENDING STUDENTS
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
· 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
Professors:
Mereghetti Carlo, Palano Beatrice Santa
Professor(s)
Reception:
On appointment, via email
Room S 6008, VI floor, Dip. Informatica "Giovanni Degli Antoni", via Celoria 18, 20133 Milano, Italy