Fondamenti dell'informatica. Linguaggi formali, calcolabilità e complessità

Indice

Prefazione

1. Introduzione
1.1 Il quadro storico - 1.2 Una prima semplice classificazione - 1.3 Il problema del millennio - 1.4 Il presente volume

2. Notazione e concetti base
2.1 Insiemi - 2.2 Relazioni - 2.3 Diagrammi di Precedenza - 2.4 Induzione ben-fondata - 2.5 Funzioni - 2.6 Cenni di Logica Matematica - 2.7 Cardinalità di insiemi - 2.8 Ordinali

3. Il problema dell'informatica

I Liguaggi formali

4. Linguaggi regolari ed automi a stati finiti
4.1 Alfabeti e linguaggi - 4.2 Automi a stati finiti - 4.3 Automi deterministici - 4.4 Automi non-deterministici - 4.5 Equivalenza tra DFA e NFA - 4.6 Automi con Ɛ-transizioni - 4.7 Equivalenza di Ɛ-NFA e NFA - 4.8 Altri tipi di automi

5. Espressioni regolari
5.1 Operazioni sui linguaggi - 5.2 Espressioni regolari - 5.3 Equivalenze tra DFA e ER

6. Proprietà dei linguaggi regolari
6.1 Il teorema di Myhill-Nerode - 6.2 Minimazzazione di DFA - 6.3 Il "Pumping Lemma" - 6.4 Proprietà di chiusura - 6.5 Risultati di decibilità

7. Linguaggi liberi dal contesto ed automi a pila
7.1 Linguaggi liberi dal contesto - 7.2 Il linguaggio generato - 7.3 Alberi di derivazione - 7.4 Ambiguità delle derivazioni - 7.5 Forme normali - 7.5.1 Eliminazione di simboli inutili - 7.5.2 Eliminazione delle Ɛ-produzioni - 7.5.3 Eliminazione delle produzioni unitarie - 7.6 Forma normale di Chomsky - 7.7 Forma normale di Greibach - 7.8 Automi a pila - 7.9 Grammatiche Regolari

8. Proprietà di linguaggi liberi dal contesto
8.1 Il Pumping lemma per i linguaggi CF - 8.2 Proprietà di chiusura - 8.3 Algoritmi di decisione - 8.4 Altri tipi di grammatiche - 8.5 La Gerarchia di N. Chomsky

9. Esercizi

II Teoria della Calcolabilità

10. Nozione intuitiva di algoritmo e la Macchina di Turing
10.1 Requisiti di un algoritmo - 10.2 Funzioni calcolabili - 10.3 Algoritmi e Programmi - 10.4 Macchine di Turing - 10.5 Descrizione modellistica e matematica - 10.6 Funzioni calcolabili da MdT - 10.7 MdT generalizzate

11. Funzioni parziali ricorsive di S. C. Kleene
11.1 Funzioni primitive ricorsive - 11.2 Adeguatezza delle funzioni primitive ricorsive - 11.3 Ancora sulla diagonalizzazione - 11.4 Funzioni parziali ricorsive di S. C. Kleene - 11.5 Equivalenza tra MdT e funzioni parziali ricorsive

12. La Tesi di Church-Turing ed i limiti del calcolabile
12.1 Aritmizzazione e universalità - 12.2 La Macchina di Turing Universale - 12.3 Il Teorema s-m-n - 12.4 Problemi insolubili

13. Calcolabilità e Programmazione
13.1 Il linguaggio WHILE - 13.2 Strutture dati - 13.3 Sintassi - 13.4 Semantica - 13.5 Espressività di WHILE e Turing completezza - 13.6 For-calcolabilità e funzioni primitive ricorsive - 13.7 Interpreti e Metaprogrammazione - 13.8 Specializzazione e Compilazione

14. Insiemi ricorsivi e ricorsivamente enumerabili
14.1 Grammatiche di tipo 0

15. I Teoremi di Ricorsione ed il Teorema di Rice
15.1 Il primo Teorema di ricorsione - 15.2 Il secondo Teorema di Ricorsione - 15.3 Il Teorema di Rice - 15.4 Proprietà di programmi

16. Riducibilità funzionale e gradi di risolvibilità
16.1 La relazione di riducibilità - 16.2 Insiemi creativi e produttivi - 16.3 Insiemi semplici

17. Esercizi
17.1 Funzioni (primitive) ricorsive - 17.2 Macchine di Turing - 17.3 Teoremi di ricorsione - 17.4 Insieme ricorsivi - 17.5 Insiemi completi - 17.6 Insiemi produttivi

III Complessità Computazionale

18. Classi di complessità e principali risultati
18.1 Problemi, insiemi, linguaggi - 18.2 Classi di complessità in tempo e Tesi di Church computazionale - 18.3 Il non determinismo - 18.4 Una inclusione stretta - 18.5 Complessità in spazio

19. Riduzione e Completezza
19.1 Riduzione tra problemi - 19.2 I Teoremi di Cook-Levin - 19.3 Problemi NP-completi - 19.3.1 Varianti di SAT - 19.3.2 Problemi di Grafi - 19.4 Problemi con completi per le classi viste - 19.4.1 La classe L - 19.4.2 La classe NL - 19.4.3 Le classi P ed NP - 19.4.4 La classe PSACE - 19.4.5 La classe EXPTIME - 19.4.6 La classe NEXPTIME

20. Esercizi

Bibliografia