Calcolabilità e complessità

Fabrizio Baiardi    

Comprendere quali sono i problemi risolvibili meccanicamente, in assenza e in presenza di vincoli sulle risorse di calcolo

- Linguaggi Formali e Automi: grammatiche, linguaggi e operazioni su di essi, gerarchia di Chomsky; automi a stati finiti, grammatiche regolari, espressioni regolari; automi a pila, grammatiche libere da contesto; cenni sulle grammatiche contestuali - Calcolabilità: idea intuitiva di algoritmo; Macchina di Turing per accettare e calcolare - linguaggi FOR e WHILE; problemi e funzioni; funzioni ricorsive primitive; diagonalizzazione; funzioni ricorsive generali; teoremi di forma normale, di enumerazione, del parametro e del punto fisso; riduzioni; problemi insolubili e riducibilità - Complessità: misure di complessità deterministiche, con Macchine di Turing a k-nastri e I/O; complessità in tempo/spazio deterministico, con teoremi di accelerazione lineare e compressione dei nastri; misure di complessità non deterministiche, con Macchine di Turing non deterministiche; complessità in tempo/spazio non deterministico; funzioni di misura appropriate e loro giustificazione (teoremi di gerarchia e della lacuna e di accelerazione); problemi trattabili e problemi intrattabili, teoremi di completezza per P e NP