Three pillars of computer science: formalizing an algorithm; assessing complexity; running a program
- https://www.uniud.it/en/research/research-board/research-activities/2024/three-pillars-of-computer-science-running-a-program-formalizing-an-algorithm-assessing-complexity
- Three pillars of computer science: formalizing an algorithm; assessing complexity; running a program
- 2024-02-15T10:00:00+01:00
- 2024-02-15T13:00:00+01:00
- Course - Digital
- When Feb 15, 2024 from 10:00 to 01:00 (Europe/Rome / UTC100)
- All dates Feb 15, 2024 from 10:00 to 01:00 Feb 16, 2024 from 10:00 to 01:00 Feb 22, 2024 from 10:00 to 01:00
- Contact Name Area Servizi per la Ricerca - Formazione della ricerca
- Attendees Phd
-
Add event to calendar
iCal
Program
Three pillars of computer science: running a program; formalizing an algorithm; assessing complexity.
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.
Calendar
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)
Speaker
Prof. Dovier, Fontana, Policriti
Registration
Notebook
This course will be held in english.