Teoria della computabilità e della complessità

Copertina
Titolo
Indice
Premessa
Parte A - Teoria della computabilità
	1 Introduzione
		1.1 Breve preistoria della computabilità
		1.2 Problemi di matematica
		1.3 Un decalogo per i bravi algoritmi
	2 Le Macchine di Turing
		2.1 Macchine che calcolano
		2.2 Alfabeti, stringhe, linguaggi
		2.3 La Macchina di Turing
		2.4 Macchine di Turing e linguaggi
		2.5 Macchine di Turing e funzioni
		2.6 Codifiche di stringhe
		2.7 Numeri e coppie
		2.8 Numeri e macchine
		2.9 La Tesi di Church-Turing
		2.10 Macchine di Turing a più nastri
		2.11 Macchine di Turing non deterministiche
		2.12 Esercizi
	3 Problemi senza Soluzione
		3.1 Diagonalizzare e ridurre
		3.2 Problemi risolubili algoritmicamente
		3.3 La Macchina Universale
		3.4 Il Problema dell'Arresto
		3.5 Insiemi decidibili e semidecidibili
		3.6 Un'altra funzione non calcolabile
		3.7 Il Decimo Problema di Hilbert
		3.8 l teoremi di Kleene e di Rice
		3.9 Esercizi
	4 Funzioni Ricorsive
		4.1 Calcolabilità secondo Church
		4.2 Le funzioni parziali ricorsive
		4.3 Esempi a volontà
		4.4 Church o Turing?
		4.5 Esercizi
	5 Calcolabilità e Grammatiche
		5.1 Grammatiche e Automi
		5.2 Linguaggi
		5.3 Grammatiche e Linguaggi
		5.4 La Gerarchia di Chomsky
		5.5 Alberi di Derivazione
		5.6 Linguaggi regolari
		5.7 Linguaggi Liberi dal Contesto
		5.8 Linguaggi Dipendenti dal Contesto
		5.9 Linguaggi e Macchine di Turing
		5.10 Automi di Riconoscimento
		5.11 Esercizi
	6 Calcolabilità e Linguaggi di Programmazione
		6.1 Il linguaggio WHILE
		6.2 La Sintassi del Linguaggio WHILE
		6.3 La Semantica dei linguaggi WHILE
		6.4 Funzioni WHILE-Calcolabili
		6.5 Programmi e Macchine di Turing
		6.6 Il Teorema di Kleene per i Programmi
		6.7 Esercizi
Parte B - Teoria della complessità
	7 Complessità
		7.1 Introduzione
		7.2 Come misurare la complessità
		7.3 Un esempio
		7.4 Esercizi
	8 Classi di Complessità Temporale
		8.1 La classe P e la Tesi di Edmonds-Cook-Karp
		8.2 La classe NP
		8.3 Un'altra caratterizzazione di NP : le macchine di Turing non deterministiche
		8.4 Il problema P = NP
		8.5 Problemi NP-completi
		8.6 Il teorema di Cook-Levin
		8.7 Altri problemi NP-completi
		8.8 P e NP : qualche commento ulteriore
		8.9 coNP e la gerarchia polinomiale
		8.10 Oracoli
		8.11 Tempi esponenziali
		8.12 P = NP nella pratica
		8.13 Esercizi
	9 Complessità, Logica e Circuiti
		9.1 Un po' di logica
		9.2 Ancora logica: le formule Booleane quantificate
		9.3 Circuiti
		9.4 Circuiti e complessità
		9.5 Circuiti e NP-completezza
		9.6 Esercizi
	10 Classi di Complessità Spaziale
		10.1 Il parametro spazio
		10.2 PSPACE e L
		10.3 NPSPACE e NL
		10.4 Il teorema di Savitch
		10.5 NL = coNL
		10.6 PSPACE-completezza
		10.7 Esercizi
	11 Classi di Complessità Probabilistiche
		11.1 Probabilmente primi
		11.2 Montecarlo o Las Vegas?
		11.3 La classe PP, e altre variazioni sul tema
		11.4 BPP e NP
		11.5 Esercizi
	12 Contare e Approssimare
		12.1 Soddisfacibilità unica
		12.2 Contare
		12.3 Approssimare
		12.4 Il teorema di Valiant-Vazirani
		12.5 Esercizi
	13 Algoritmi lnterattivi
		13.1 Artù e Merlino
		13.2 La classe lP
		13.3 Il teorema di Shamir
		13.4 Un tentativo di conclusione
		13.5 Esercizi
Parte C - Teoria quantistica della computazione
	14 Dal Bit al Quantum Bit
		14.1 Nozioni preliminari
		14.2 l postulati della Meccanica Quantistica
		14.3 Qubits versus Bits
		14.4 Esercizi
	15 Modelli di Computazione Quantistica
		15.1 Dalla macchina di Turing classica a quella quantistica
			15.1.1 Macchina di Turing reversibile
			15.1.2 Macchina di Turing quantistica
		15.2 Classi di complessità quantistiche
		15.3 Porte logiche quantistiche
		15.4 Circuiti quantistici
			15.4.1 Insiemi universali
			15.4.2 Aritmetica con circuiti quantistici
		15.5 Esercizi
	16 Algoritmi Quantistici
		16.1 Algoritmo di Deutsch-Jozsa
		16.2 Algoritmo di Simon
		16.3 Trasformata di Fourier quantistica
		16.4 Algoritmo di fattorizzazione (Shor)
			16.4.2 Il caso generale
			16.4.4 Il problema del sottogruppo nascosto
		16.5 Algoritmo di ricerca (Grover)
			16.5.1 Interpretazione geometrica
		16.6 l limiti della computazione quantistica
		16.7 Conclusioni
		16.8 Esercizi
Bibliografia
Indice analitico