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:
| Main Authors: | , |
|---|---|
| Format: | Online |
| Language: | Italian |
| Published: |
Milano University Press
2026
|
| Subjects: | |
| Online Access: | https://directory.doabooks.org/handle/20.500.12854/176901.4 |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1869517184260112384 |
|---|---|
| author | Bertoni, Alberto Goldwurm, Massimiliano |
| author_browse | Bertoni, Alberto Goldwurm, Massimiliano |
| author_facet | Bertoni, Alberto Goldwurm, Massimiliano |
| author_sort | Bertoni, Alberto |
| collection | Directory of Open Access Books |
| description | 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 |
| format | Online |
| id | doab-20.500.12854ir-176901.4 |
| institution | Directory of Open Access Books |
| language | ita |
| publishDate | 2026 |
| publishDateRange | 2026 |
| publishDateSort | 2026 |
| publisher | Milano University Press |
| publisherStr | Milano University Press |
| record_format | ojs |
| spelling | doab-20.500.12854ir-176901.42026-05-28T09:30:14Z Introduzione alla calcolabilità e alla complessità computazionale Bertoni, Alberto Goldwurm, Massimiliano undecidable problems recursively enumerable sets time and space complexity Np-complete problems computable functions thema EDItEUR::P Mathematics and Science 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 Published La calcolabilità delle funzioni e la complessità computazionale dei problemi sono due argomenti classici di Informatica Teorica. In questo testo si presentano gli aspetti principali di queste tematiche con uno scopo didattico e divulgativo. La nozione di calcolabilità è legata all’esistenza di algoritmi in grado di calcolare una funzione o di risolvere un problema. In questo contesto sono di interesse anche le funzioni e i problemi che non ammettono algoritmi. La complessità computazionale invece riguarda l’analisi delle risorse (tipicamente tempo e spazio) richieste da un algoritmo per risolvere un dato problema o calcolare una certa funzione. Entrambe queste tematiche sono considerate di base per una laurea in Informatica o in Matematica e il presente testo si rivolge in particolare agli studenti dei corsi di laurea a carattere scientifico che possono ritrovare questi argomenti in diversi insegnamenti nel loro percorso di studi. 2026-05-28T09:30:11Z 2026-05-25T08:11:20Z 2026-05-25T08:25:20Z 2026-05-28T08:24:09Z 2026-05-28T09:30:11Z 2026-05-11 book 979-12-5510-436-0 979-12-5510-438-4 979-12-5510-440-7 https://directory.doabooks.org/handle/20.500.12854/176901.4 ita application/octet-stream n/a https://libri.unimi.it/index.php/milanoup/catalog/book/284 Milano University Press Milano University Press 10.54103/milanoup.284 La calcolabilità delle funzioni e la complessità computazionale dei problemi sono due argomenti classici di Informatica Teorica. In questo testo si presentano gli aspetti principali di queste tematiche con uno scopo didattico e divulgativo. La nozione di calcolabilità è legata all’esistenza di algoritmi in grado di calcolare una funzione o di risolvere un problema. In questo contesto sono di interesse anche le funzioni e i problemi che non ammettono algoritmi. La complessità computazionale invece riguarda l’analisi delle risorse (tipicamente tempo e spazio) richieste da un algoritmo per risolvere un dato problema o calcolare una certa funzione. Entrambe queste tematiche sono considerate di base per una laurea in Informatica o in Matematica e il presente testo si rivolge in particolare agli studenti dei corsi di laurea a carattere scientifico che possono ritrovare questi argomenti in diversi insegnamenti nel loro percorso di studi. 10.54103/milanoup.284 6248ff0f-e85a-4c84-b1c8-9820a67d3d31 979-12-5510-436-0 979-12-5510-438-4 979-12-5510-440-7 Milano University Press 136 Milano open access |
| spellingShingle | undecidable problems recursively enumerable sets time and space complexity Np-complete problems computable functions thema EDItEUR::P Mathematics and Science Bertoni, Alberto Goldwurm, Massimiliano Introduzione alla calcolabilità e alla complessità computazionale |
| title | Introduzione alla calcolabilità e alla complessità computazionale |
| title_full | Introduzione alla calcolabilità e alla complessità computazionale |
| title_fullStr | Introduzione alla calcolabilità e alla complessità computazionale |
| title_full_unstemmed | Introduzione alla calcolabilità e alla complessità computazionale |
| title_short | Introduzione alla calcolabilità e alla complessità computazionale |
| title_sort | introduzione alla calcolabilita e alla complessita computazionale |
| topic | undecidable problems recursively enumerable sets time and space complexity Np-complete problems computable functions thema EDItEUR::P Mathematics and Science |
| topic_facet | undecidable problems recursively enumerable sets time and space complexity Np-complete problems computable functions thema EDItEUR::P Mathematics and Science |
| url | https://directory.doabooks.org/handle/20.500.12854/176901.4 |
| work_keys_str_mv | AT bertonialberto introduzioneallacalcolabilitaeallacomplessitacomputazionale AT goldwurmmassimiliano introduzioneallacalcolabilitaeallacomplessitacomputazionale |