Introduzione alla calcolabilità teorica ed effettiva

Authors

Massimiliano Goldwurm
University of Milan
https://orcid.org/0000-0003-0903-4699
Alberto Bertoni
University of Milan image/svg+xml
https://orcid.org/0000-0002-4018-5105
DOI: https://doi.org/10.54103/milanoup.284
Keywords: undecidable problems, recursively enumerable sets, time and space complexity, Np-complete problems, computable functions

Synopsis

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.

Downloads

Download data is not yet available.

Author Biographies

Massimiliano Goldwurm, University of Milan

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, University of Milan

Alberto Bertoni (1946-2014), graduated in Physics in 1970, full professor of Computer Science in 1981, later he joined the department of Information Science at the State University of Milan. He carried out scientific research in different branches of Theoretical Computer Science, including computational complexity, formal languages, probabilistic and quantum machines, computational learning and neural networks. On these subjects, for more than 30 years, he taught classes at any university-level and was supervisor of many PhD theses. Co-promotor and local chief of many research projects, he also held several academic and scientific positions; in particular he was one of the founders (and then president for 6 years) of the Italian Chapter of the European Association for Theoretical Computer Science.

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.

Cover of the book featuring an Euler-Venn diagram illustrating the relationships between NP and co-NP in PSPACE=NPSPACE
PDF
Published
May 11, 2026
Categories
Copyright (c) 2026 The Author(s)
License Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Details about this monograph

ISBN-13 (15)
979-12-5510-436-0