Introduzione alla calcolabilità e alla complessità computazionale

Massimiliano Goldwurm; Alberto Bertoni

doi:10.54103/milanoup.284

Autori/Autrici

Massimiliano Goldwurm

University of Milan

https://orcid.org/0000-0003-0903-4699

Alberto Bertoni

University of Milan

https://orcid.org/0000-0002-4018-5105

DOI: https://doi.org/10.54103/milanoup.284

Keywords: funzioni calcolabili, problemi indecidibili, insiemi ricorsivamente numerabili, complessità in tempo e spazio, problemi NP-completi

Scheda

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.

Downloads

I dati di download non sono ancora disponibili.

Biografia autore/autrice

Massimiliano Goldwurm, University of Milan

Laureato in Matematica, Massimiliano Goldwurm ha ottenuto il dottorato di ricerca in Informatica nel 1988. E’ stato ricercatore, professore associato e poi ordinario nel settore s.d. di Informatica, presso l’Università degli Studi di Milano. Svolge attività di ricerca nei settori dei linguaggi formali, dell’analisi di algoritmi e della complessità computazionale, applicando principalmente metodi probabilistici e analitici. Sugli stessi temi, a partire dal 1992 è stato titolare di vari insegnamenti in corsi di laurea triennale e magistrale di Informatica e di Matematica.

Alberto Bertoni, University of Milan

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.

Riferimenti bibliografici

[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.

Libri / Books