Foundations of Computer Science 1
A.Y. 2019/2020
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
Course syllabus
Introduction to computability: intuitively computable functions, existence of non-computable functions, pairing functions and its extensions. Reduced RAM model, sintax and semantics of its programming language. Sintax and semantics of While language. Example of compiler and interpreter. Equivalence between RAM programs and While programs. Coding of RAM programs by integer numbers. Partial recursive functions. Church's thesis.
Acceptable programming systems. Recursion theorem. Isomorphism theorem. Undecidable problems.
Special decision problems: halting, totality, equivalence. Recursive sets and recursively enumerable sets. Equivalent definitions of r.e. sets. Reducibility between problems. Rice's theorem.
Formal languages and grammars. Chomsky hierarchy: regular, context-free, context-sensitive and type 0 languages. Deterministic and nondeterministic finite state automata and their simulation properties. Closure properties and Pumping lemma for regular languages.
Turing machines. Deterministic and non-deterministic models and their simulation. Time and space complexity. Classes P and NP. Polynomial time reducibility and its main examples. NP-complete problems. Cook's theorem. Introduction to space complexity: classes L, NL, Pspace and Savitch's theorem.
Acceptable programming systems. Recursion theorem. Isomorphism theorem. Undecidable problems.
Special decision problems: halting, totality, equivalence. Recursive sets and recursively enumerable sets. Equivalent definitions of r.e. sets. Reducibility between problems. Rice's theorem.
Formal languages and grammars. Chomsky hierarchy: regular, context-free, context-sensitive and type 0 languages. Deterministic and nondeterministic finite state automata and their simulation properties. Closure properties and Pumping lemma for regular languages.
Turing machines. Deterministic and non-deterministic models and their simulation. Time and space complexity. Classes P and NP. Polynomial time reducibility and its main examples. NP-complete problems. Cook's theorem. Introduction to space complexity: classes L, NL, Pspace and Savitch's theorem.
Prerequisites for admission
General knowledge of basic algorithms, main data structures and at least one imperative programming language, with an elementary experience of developing programming.
It is strongly suggested to pass the examinations of a course of Programming and of a course of Algorithms, at an undergraduate level.
It is strongly suggested to pass the examinations of a course of Programming and of a course of Algorithms, at an undergraduate level.
Teaching methods
The course is based on traditional lessons.
Teaching Resources
- Web site of the course:
http://users.mat.unimi.it/users/goldwurm/Fondamenti_Informatica/
- Class notes:
M. Goldwurm, Computabilità e complessità computazionale, Università degli Studi di Milano, Gennaio 2019,
available at the web site given above
- Ather references:
A. Bertoni, Introduzione alla calcolabilità, Dispense del corso di Informatica Teorica, parte 1, Univ. degli Studi di
Milano, 1990. Available at the Ariel web site of the course mentioned below.
A. Kfoury, R. Moll, M. Arbib, A Programming Approach to Computability, Springer-Verlag, 1982.
Versione italiana (stessi autori): Programmazione e computabilità, Etas Libri, 1986.
J. Hopcroft, J. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1997.
C. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
J. Hopcroft, R. Motwani, J. Ullman, Introduction to Automata Theory, Languages, and Computation, 2001.
- At the Ariel site of our university, with address https://ariel.unimi.it/ ,
there is a web page of the present course.
http://users.mat.unimi.it/users/goldwurm/Fondamenti_Informatica/
- Class notes:
M. Goldwurm, Computabilità e complessità computazionale, Università degli Studi di Milano, Gennaio 2019,
available at the web site given above
- Ather references:
A. Bertoni, Introduzione alla calcolabilità, Dispense del corso di Informatica Teorica, parte 1, Univ. degli Studi di
Milano, 1990. Available at the Ariel web site of the course mentioned below.
A. Kfoury, R. Moll, M. Arbib, A Programming Approach to Computability, Springer-Verlag, 1982.
Versione italiana (stessi autori): Programmazione e computabilità, Etas Libri, 1986.
J. Hopcroft, J. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1997.
C. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
J. Hopcroft, R. Motwani, J. Ullman, Introduction to Automata Theory, Languages, and Computation, 2001.
- At the Ariel site of our university, with address https://ariel.unimi.it/ ,
there is a web page of the present course.
Assessment methods and Criteria
The final examination consists of an oral exam concerning the subjects contained in the program. It is required to students a precise knowledge of the definitions of the fundamental notions of the program, the ability to yield significant examples of their properties and to present the proof of some relevant theorems shown at class.
Final marks lie in the numerical range 0-30 and will be communicated immediately after the oral examination.
Final marks lie in the numerical range 0-30 and will be communicated immediately after the oral examination.
INF/01 - INFORMATICS - University credits: 6
Lessons: 42 hours
Professor:
Goldwurm Massimiliano
Shifts:
-
Professor:
Goldwurm MassimilianoProfessor(s)