SERVIZIO CLIENTI 0541.628242 Lunedì - Venerdì / 8.30-17.30

Introduzione alla teoria della computazione

*

Autori Michael Sipser
Argomenti Apogeo Education > Matematica e Statistica > Informatica > Matematica >
Editore Maggioli Editore
Formato Cartaceo
Dimensione 17x24
Pagine 520
Pubblicazione Marzo 2016 (I° Edizione)
ISBN 9788891616180
Collana Apogeo Education
Prezzo Online:

44,00 €

37,40 €

Descrizione

La teoria della computazione nasce dalla necessità di una sistemazione teorica del concetto di procedura di calcolo. Ha due assi portanti: la computabilità e la complessità di calcolo. Studia ciò che può e non può essere calcolato 
e, nel caso dei problemi risolvibili, determina 
in quanto tempo, con quanta memoria 
e su quale tipo di modello computazionale. Il testo di Michael Sipser, giunto alla terza edizione inglese, è considerato un riferimento essenziale sull’argomento, adottato in numerosissime università in tutto il mondo in ambito informatico, ingegneristico e matematico.

Michael Sipser è professore di Applied Mathematics e Dean of Science presso il Massachusetts Institute of Technology.

L’edizione italiana è stata curata dai professori Clelia De Felice, Luisa Gargano e Paolo D’Arco, del Dipartimento di Informatica dell’Università di Salerno.


INDICE

0 Introduzione
0.1 Automi, computabilità e complessità
0.2 Terminologia e notazione matematica
0.3 Definizioni, teoremi e dimostrazioni
0.4 Tipi di dimostrazioni

Parte Prima: Automi e linguaggi

l Linguaggi regolari
1.1 Automi finiti
1.2 Non determinismo
1.3 Espressioni regolari
1.4 Linguaggi non regolari
Esercizi, Problemi, Soluzioni

2 Linguaggi context-free
2.1 Grammatiche context-free
2.2 Automi a pila
2.3 Linguaggi non context-free
2.4 Linguaggi context-free deterministici
Esercizi, Problemi, Soluzioni

Parte Seconda: Teoria della computabilità

3 La tesi di Church-Turing
3.1 Macchine di Turing
3.2 Varianti di macchine di Turing
3.3 La definizione di algoritmo
Esercizi, Problemi, Soluzioni

4 Decidibilità
4.1 Linguaggi decidibili
4.2 Indecidibilità
Esercizi, Problemi, Soluzioni

5 Riducibilità
5.1 Problemi indecidibili dalla teoria dei linguaggi
5.2 Un semplice problema indecidibile
5.3 Riducibilità mediante funzione
Esercizi, Problemi, Soluzioni

6 Argomenti avanzati nella teoria della computazione
6.1 Il teorema di ricorsione
6.2 Decidibilità delle teorie logiche
6.3 Turing riducibilità
6.4 Una definizione di informazione
Esercizi, Problemi, Soluzioni

Parte terza: Teoria della complessità

7 Complessità di tempo
7.1 Misure di complessità
7.2 La classe P
7.3 La classe NP
7.4 NP-completezza
7.5 Ulteriori problemi NP-completi
Esercizi, Problemi, Soluzioni

8 Complessità di spazio
8.1 Teorema di Savitch
8.2 La classe PSPACE
8.3 PSPACE-completezza
8.4 Le classi L ed NL
8.5 NL-completezza
8.6 NL coincide con coNL
Esercizi, Problemi, Soluzioni

9 Intrattabilità
9.1 I teoremi di gerarchia
9.2 Relativizzazione
9.3 Complessità dei circuiti
Esercizi, Problemi, Soluzioni

10 Argomenti avanzati nella teoria della complessità

10.1 Algoritmi di approssimazione
10.2 Algoritmi probabilistici
10.3 Alternanza
10.4 Sistemi di prova interattivi
10.5 Computazione parallela o Circuiti booleani uniformi
10.6 Crittografia
Esercizi, Problemi, Soluzioni

Bibliografia selezionata

Indice analitico