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

Durante il mese di agosto le spedizioni potranno subire rallentamenti.

Le spedizioni riprenderanno regolarmente a partire dal 27 agosto 2018

Sconto 15%
Introduzione alla teoria della computazione

Introduzione alla teoria della computazione

Autori Michael Sipser
Editore Maggioli Editore
Formato Cartaceo
Dimensione 17x24
Pagine 520
Pubblicazione Marzo 2016 (I Edizione)
ISBN / EAN 8891616180 / 9788891616180
Collana Apogeo Education

Edizione italiana del Manuale di Michael Sipser

Prezzo Online:

44,00 €

37,40 €

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

 


Scrivi la tua recensione

Solo gli utenti registrati possono scrivere recensioni. Accedi oppure Registrati

Prodotti consigliati

Back to top