Foundations of Computer Science 1

A.Y. 2020/2021
Overall hours
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.
Course syllabus and organization

Single session

Lesson period
First semester
1) Lectures
In the academic year 2020/21 the course, planned in the first semester, will be provided by online distance lectures in an asynchronous way. Lectures will be videorecorded in files MP4 and will be made available to students in the Ariel web page of the course twice a week, mainly on monday and wednesday, according to the official calendar of teaching activity. During the teaching period, on the same Ariel web page, a forum will be provided to all students of the course, devoted to question and discussion concerning the subjects presented in the lectures.

2) Program and material
The program and material of the course will remain the same as in the periods of traditional teaching activity.

3) Exames
Exams consist of an oral discussion, concerning the subjects of the program, which will take place on-line by using the application Zoom. Students that have to take the exam are required to subscritp to an exam session and then arrange with the teacher, by e-mail, the effective date of the exam (which cannot occurs earlier than the official day of the session exam). Few minutes before the exam candidates will receive by e-mail specific instructions (the address of a web site) to attend at the on-line meeting. Candidates to exams are required to have a computer with microphone and videocamera, they will have to be alone in the room where the connection takes place, and they also should have the necessary devices to write; during the exam they can aswer the question, writing the formal details on paper, occasionally they will be asked to show at video the written parts.
Course syllabus
Introduction to computability: intuitively computable functions, existence of non-computable functions, pairing functions and their 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.
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.
Teaching methods
The course is based on traditional lessons.
Teaching Resources
- Web site of the course:

- At the Ariel site of our university, with address ,
there is a web page of the present course.

- Class notes:
M. Goldwurm, Computabilità e complessità computazionale, Università degli Studi di Milano, Gennaio 2019,
available at the web site given above

- Other 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.
Assessment methods and Criteria
The final examination consists of an oral exam concerning the subjects contained in the program. It is required 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.
INF/01 - INFORMATICS - University credits: 6
Lessons: 42 hours
Educational website(s)