Introduzione alla teoria della computazione

 
Prezzo speciale 41,80 €
SCONTO 5%
5%
Anzichè 44,00 €
Disponibile

Autori Michael Sipser

Pagine 520
Data pubblicazione Febbraio 2016
Data ristampa
Autori Michael Sipser
ISBN 8891616180
ean 9788891616180
Tipo Cartaceo
Collana Apogeo Education
Editore Maggioli Editore
Dimensione 17x24
  • Spedizione in 48h
  • Paga alla consegna senza costi aggiuntivi

Autori Michael Sipser

Pagine 520
Data pubblicazione Febbraio 2016
Data ristampa
Autori Michael Sipser
ISBN 8891616180
ean 9788891616180
Tipo Cartaceo
Collana Apogeo Education
Editore Maggioli Editore
Dimensione 17x24

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. 

Edizione italiana del Manuale di Michael Sipser

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
Stai recensendo:Introduzione alla teoria della computazione