Foundations of Computer Science 1
A.Y. 2020/2021
Learning objectives
Main goal of this course is to introduce the notion of computability by means of simple programming languages. In particular we aim to illustrate and motivate Church's Thesis, the undecidable problems and the main results of the theory of recursive functions. A second part is devoted to computational complexity and in particular to NP-complete problems.
Expected learning outcomes
Comprehension of the main notions of computability. Capability to recognize undecidable or hard problems in the main cases. Capability to formalize computational models.
Lesson period: First 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
Single session
Responsible
Lesson period
First semester
Educational website(s)
Professor(s)