Introduzione alla calcolabilità e alla complessità computazionale
The computability of functions and the computational complexity of problems are classical subjects of Theoretical Computer Science. This work presents the main aspects of these topics with a didactic and educational goal. The notion of computability is related to the existence of an algorithm to det...
Saved in:
| Format: | Online |
|---|---|
| Language: | Italian |
| Published: |
Milano University Press
2026
|
| Subjects: | |
| Online Access: | https://directory.doabooks.org/handle/20.500.12854/176901.2 |
| Tags: |
No Tags, Be the first to tag this record!
|
| Summary: | The computability of functions and the computational complexity of problems are classical subjects of Theoretical Computer Science. This work presents the main aspects of these topics with a didactic and educational goal. The notion of computability is related to the existence of an algorithm to determine the values of a function or to solve a problem. In this context it is also relevant the study of problems and functions that do not admit algorithms. On the other hand, computational complexity concerns the analysis of the resources (usually time and space) required by an algorithm to solve a given problem or compute a certain function. These topics are considered at the basis of a university curriculum in Computer Science or in Mathematics, and this presentation is devoted in particular to the students of scientific degree programs |
|---|