Introduzione alla teoria della computazione
di Michael Sipser
scopri di più
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
| Pagine | 520 |
| Data pubblicazione | Marzo 2016 |
| Data ristampa | |
| Autori | Michael Sipser |
| ISBN | 8891616180 |
| ean | 9788891616180 |
| Tipologia prodotto | Cartaceo |
| Collana | Apogeo Education |
| Editore | Maggioli Editore |
| Dimensione | 17x24 |
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
-
-
Python - Introduzione alla programmazioneCartaceoSpecial Price 34,20 €SCONTO 5%5%Anzichè 36,00 €
