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 |
