Goals of the course

Computer science has undergone a very rapid evolution from its start until today. This has brought significant benefits to the quality of life but has also created problems with the reliability of computer based systems. In many cases, in fact, the adopted design techniques proved to be inadequate to the complexity of the addressed problems.

Among the causes of the unsatisfactory reliability of computer systems one of the most frequently mentioned is the lack of a solid theoretical background on which effective design techniques must be founded.

The goal of the course of Theoretical Computer Science is to fill this gap by addressing systematically the fundamental problems of computer science and showing that a rigorous approach based on the theoretical foundations of the discipline has a great relevance on practical applications.

Expected learning outcomes

 The course covers the following topics:

1. The models of Computer Science

• Automata (finite state and stack automata, Turing Machines)
• Grammars
• Nondeterministic models
• Use of mathematical logic for modeling systems and describing their properties: relations between logic, languages and automata.

2. Computation theory

• Power of the models of computation
• Church Thesis
• Undecidable problems
• Techniques for proving undecidability

3. The complexity of computing

• Fundamental notions of complexity analysis
• Models of computation and relations among their computational complexity
• Linear speed-up. Complexity hierarchies.
• Hints towards intractable problems and NP-completeness.

Prerequisites

The course program assumes the knowledge of topics that are typically covered in Computer Science 1 courses. A further requirement is knowledge of the content of the Logic and Algebra course.

Assessment

The exam is based on written questions, possibly integrated, upon request by the teacher, by a further oral interrogation. The written part of the exam is open book (textbook and personal notes allowed).