Skip to main content
Thoth
Introduzione alla calcolabilità e alla complessità computazionale
Milano University Press

Introduzione alla calcolabilità e alla complessità computazionale

Export Metadata
Metadata
TitleIntroduzione alla calcolabilità e alla complessità computazionale
ContributorMassimiliano Goldwurm(author)
Alberto Bertoni(author)
DOIhttps://doi.org/10.54103/milanoup.284
Landing pagehttps://libri.unimi.it/index.php/milanoup/catalog/book/284
Licensehttps://creativecommons.org/licenses/by-sa/4.0
CopyrightThe Author(s)
PublisherMilano University Press
Published on2026-05-11
ISBN979-12-5510-436-0 (PDF)
Long abstract
Print length136 pages
LanguageItalian (Original)
Keywords
  • funzioni calcolabili
  • problemi indecidibili
  • insiemi ricorsivamente numerabili
  • complessità in tempo e spazio
  • problemi NP-completi

Contributors

Massimiliano Goldwurm

(author)

Alberto Bertoni

(author)

References

  1. [1] A.V. Aho, J.E. Hopcroft, J.D. Ullman, The design and analysis of computer algorithms, Addison-Wesley, 1974.
  2. [2] S. Arora, B. Barak, Computational complexity: a modern approach, Cambridge University Press, 2009.
  3. [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. [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. [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. [6] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli algoritmi e strutture dati (quarta edizione),McGraw-Hill, 2023.
  7. [7] S. Crespi Reghizzi, Linguaggi formali e compilazione, Pitagora Editrice Bologna, 2006.
  8. [8] M.D. Davis, R. Sigal, E.J. Weyuker, Computability, complexity and languages, Academic Press, 1994.
  9. [9] A. de Luca, F. D’Alessandro, Teoria degli automi finiti, Springer-Verlag, 2013.
  10. [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. [11] C. Froidevaux,M.C.Gaudel,M. Soria, Types de données et algorithmes, Ediscience International, 1993.
  12. [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. [13] J.E. Hopcroft, R. Motwani, J.D. Ullman, Automi, linguaggi e calcolabilità, Pearson, Addison-Wesley, 2009.
  14. [14] J.E.Hopcroft, J.D.Ullman, Introduction to automata theory, languages and computation, Addison-Wesley, 1979.
  15. [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. [16] C. Papadimitriou, Computational complexity, Addison-Wesley, 1994.
  17. [17] H. Rogers, Theory of recursive functions and effective computability, MIT Press, 1967.
  18. [18] S. Skiena, The algorithm desing manual, Springer, 2020.
  19. [19] I. Wegener, The complexity of Boolean functions, John Wiley & Sons Inc, 1987.