Contenuti

The activity is in the form of a crash course, in which few basic concepts will be explained about three unavoidable questions in computer science.

1) Formalizing an algorithm: we will introduce and discuss the notion of algorithmically solvable problem. Then algorithms, and the very basic ideas -- and problems -- behind their formal presentation and classification, will be illustrated by examples. We will conclude with a few observations on how to tackle non-algorithmically solvable problems, with an algorithm.

2) Assessing complexity: in the class of algorithmically solvable problems there are those that can be solved in few second (by the execution of a carefully written program) and those for which running time even with the fastest computer in the world would exceed planet earth lifetime. Computational complexity deals with the issue of classifying problems from this perspective. In particular, in the lecture we will focus on the P-vs-NP problem (one among the 7 Millennium Problems listed by the Clay Mathematics Institute) and on the theoretical and practical relevance of the problem of establishing the satisfiability of a propositional logical formula (in short, SAT).

3) Running a program: the traditional CPU architecture based on Von Neumann’s processing principles will be explained, by clarifying how a computer program is translated in machine code and then processed through fast elementary operations.

By answering such three questions, the course sheds light on how a modern computer is able to deal with problems effectively, as soon as they can be formalized, assessed, and coded.  

Calendario

15 febbraio (10:00 - 13:00) – Formalizing an algorithm (A. Policriti)
16 febbraio (10:00 - 13:00) – Assessing complexity (A. Dovier)
22 febbraio (11:00 - 13:00, 14:00 - 16:00) – Running a program (F. Fontana)

Relatori

Prof. Dovier, Fontana, Policriti

Iscrizioni

I dottorandi devono iscriversi inserendo il corso sul Notebook.

Il corso è dedicato ai dottorandi, i cui dottorati hanno incluso la didattica transdisciplinare di informatica.