
Introduzione alla calcolabilità e alla complessità computazionale
- Massimiliano Goldwurm(author)
- Alberto Bertoni(author)
| Title | Introduzione alla calcolabilità e alla complessità computazionale |
|---|---|
| Contributor | Massimiliano Goldwurm(author) |
| Alberto Bertoni(author) | |
| DOI | https://doi.org/10.54103/milanoup.284 |
| Landing page | https://libri.unimi.it/index.php/milanoup/catalog/book/284 |
| License | https://creativecommons.org/licenses/by-sa/4.0 |
| Copyright | The Author(s) |
| Publisher | Milano University Press |
| Published on | 2026-05-11 |
| ISBN | 979-12-5510-436-0 (PDF) |
| Long abstract | 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. |
| Print length | 136 pages |
| Language | Italian (Original) |
| Keywords |
|
Contributors
Massimiliano Goldwurm
(author)Massimiliano Goldwurm obtained a PhD in Computer Science in 1988. Later he was researcher, associate professor and then full professor in the same field at the State University of Milan. His research interests are in the areas of formal languages, analysis of algorithms and computational complexity. Main tools in his research are based on probabilistic and analytic methods. On the same topics, since 1992, he has been teacher of several university classes at graduate and undergraduate level in university programs of Computer Science and Mathematics.
Alberto Bertoni
(author)Alberto Bertoni (1946-2014), laureato in Fisica nel 1970, professore ordinario di Informatica dal 1981, in seguito ha afferito al dipartimento di Scienze dell’Informazione dell’Università degli Studi di Milano. Ha svolto attività di ricerca nell’area dell’Informatica Teorica, in particolare in complessità computazionale, linguaggi formali, macchine probabilistiche e quantistiche, apprendimento computazionale e reti di neuroni, con più di 100 lavori a livello internazionale. Su questi temi ha svolto per oltre 30 anni attività didattica a tutti i livelli universitari ed è stato relatore di molte tesi di dottorato. Co-promotore e responsabile locale di numerosi progetti di ricerca, ha ricoperto varie cariche accademiche e scientifiche, in particolare è stato uno dei fondatori (e poi presidente per 6 anni) del Capitolo Italiano dell'Associazione Europea di Informatica Teorica.
References
- [1] A.V. Aho, J.E. Hopcroft, J.D. Ullman, The design and analysis of computer algorithms, Addison-Wesley, 1974.
- [2] S. Arora, B. Barak, Computational complexity: a modern approach, Cambridge University Press, 2009.
- [3] A. Bertoni, Introduzione alla calcolabilità, Dispense del corso di Informatica Teorica, Università degli Studi di Milano,1990, reperibile al sito https://bertoni.di.unimi.it/Calcolabilita.pdf
- [4] A. Bertoni, M. Goldwurm, Progetto e analisi di algoritmi, Dispense del corso di Algoritmi e Strutture Dati, Rapporto interno n.230-98, Dip. Scienze dell’Informazione - Università degli Studi di Milano, Settembre 2004, reperibile al sito https://bertoni.di.unimi.it/Algoritmi_e_Strutture_Dati.pdf
- [5] A. Bertoni, C. Mereghetti, Dispense del corso di Informatica Teorica (A.A. 2000/2001), Dip. Scienze dell’Informazione, Università degli Studi di Milano, reperibile al sito https://bertoni.di.unimi.it/Circuiti_e_complessita.pdf
- [6] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli algoritmi e strutture dati (quarta edizione),McGraw-Hill, 2023.
- [7] S. Crespi Reghizzi, Linguaggi formali e compilazione, Pitagora Editrice Bologna, 2006.
- [8] M.D. Davis, R. Sigal, E.J. Weyuker, Computability, complexity and languages, Academic Press, 1994.
- [9] A. de Luca, F. D’Alessandro, Teoria degli automi finiti, Springer-Verlag, 2013.
- [10] M. Dietzfelbinger, Primality testing in polynomial time, from randomized algorithms to “PRIMES is in P”, Lecture Notes in Computer Science, vol. 3000, Springer–Verlag, 2004.
- [11] C. Froidevaux,M.C.Gaudel,M. Soria, Types de données et algorithmes, Ediscience International, 1993.
- [12] M.R. Garey, D.S. Johnson, Computers and intractability: a guide to the theory of NP-completeness,W.H. Freeman and Company, 1979.
- [13] J.E. Hopcroft, R. Motwani, J.D. Ullman, Automi, linguaggi e calcolabilità, Pearson, Addison-Wesley, 2009.
- [14] J.E.Hopcroft, J.D.Ullman, Introduction to automata theory, languages and computation, Addison-Wesley, 1979.
- [15] A.J. Kfoury, R.N. Moll, M.A. Arbib, A programming approach to computability, Springer, 1982 (versione italiana: Programmazione e computabilità, ETAS Libri, 1986).
- [16] C. Papadimitriou, Computational complexity, Addison-Wesley, 1994.
- [17] H. Rogers, Theory of recursive functions and effective computability, MIT Press, 1967.
- [18] S. Skiena, The algorithm desing manual, Springer, 2020.
- [19] I. Wegener, The complexity of Boolean functions, John Wiley & Sons Inc, 1987.
