Teoria della computabilita' e della complessita'
di Toffalori Carlo ; Corradini Flavio ; Leonesi Stefano; Mancini Stefano
Che cos’è un algoritmo? Quali problemi si possono risolvere con un
algoritmo? E in quali casi un algoritmo di soluzione richiede risorse
accessibili nella pratica?
Il libro affronta questi problemi, trattando anzitutto la teoria della
computabilità sia dal punto di vista classico - macchine di Turing,
funzioni ricorsive, grammatiche - che da prospettive più attuali, come
quella dei programmi while, legate ai linguaggi di programmazione e in
particolare al Pascal.
Si discutono poi i vari possibili criteri di misura delle risorse
disponibili (tempo, memoria, casualità) e si sviluppa la corrispondente
teoria della complessità computazionale, dalla classica questione P =
NP al teorema di Savitch, dai circuiti booleani alle procedure
probabilistiche e interattive.
Un moderno approccio alla computazione e
alla complessità basato sulla teoria quantistica è introdotto nella
parte finale del volume.
Il testo si rivolge agli studenti di Informatica, Matematica, Fisica o Ingegneria interessati a corsi di Informatica teorica.
Gli autori
Gli autori insegnano presso la Facoltà di Scienze e Tecnologie dell’Università di Camerino.
Carlo Toffalori è docente di Logica Matematica.
Flavio Corradini è docente di Ingegneria del Software.
Stefano Leonesi è docente di Didattica della Matematica.
Stefano Mancini è docente di Informazione Quantistica.
More blogs
