## page was renamed from CalcolabilitaComplessita
## page was renamed from Calcolabilita e Complessita
#acl FrancescoScarcello:read,write,revert EditorsGroup:read,write,delete,admin,revert All:read

== Calcolabilita e Complessita  (DM 509) ==

'''Obiettivi Formativi'''

Il modulo si propone di fornire le conoscenze di base della teoria della calcolabilità e della complessità.

Al termine del modulo, gli studenti saranno in grado di capire cos’è un problema indecidibile o intrinsecamente difficile ed eventualmente dimostrarne tali proprietà mediante l’applicazione dei teoremi studiati durante il corso o mediante l’uso di tecniche basate sulla riduzione tra problemi.

'''Programma e Articolazione del Modulo'''

 * Introduzione al corso, testi consigliati, svolgimento dell’esame. Dagli algoritmi ai problemi. Ciò che si può risolvere e ciò che non si può risolvere (Calcolabilità) Ciò che si può risolvere: a che costo? (Complessità)

 * La tecnica della diagonalizzazione. Applicazione al Power Set dei numeri naturali.

 * Introduzione ai linguaggi. Linguaggi e problemi di decisione.

 * Indecidibilità del problema HELLO-WORLD e riducibilità tra problemi.

 * Esercitazione sulle riduzioni tra problemi. Introduzione alla macchina di Turing.

 * Esercitazione sulle macchine di Turing (es.: riconoscere i linguaggi  ww^r e wcw)

 * Macchine di Turing multitraccia e multinastro. Simulazione di una macchina multinastro con una mononastro e costi di esecuzione.

 * Introduzione alle macchine di Turing non deterministiche.

 * Esercitazione sulle macchine di Turing non deterministiche: data una coppia di stringhe, decidere se la prima è una sottostringa della seconda; colorabilità di un grafo.

 * Linguaggi ricorsivamente enumerabili, linguaggi ricorsivi. Teoremi sul complemento dei linguaggi. Il linguaggio Ld ed il linguaggio Lu.

 * Ancora sulla indecidibilità: il Teorema di Rice

 * Valutazione dei costi di esecuzione in termini di tempo e di spazio. Una gerarchia di classi di complessità.

 * Problemi Polinomiali e problemi NP.

 * Concetto di riduzione polinomiale tra problemi. Problemi NP-ardui ed NP-completi.

 * Esercitazione sulle riduzioni tra problemi.

 * Il teorema di Cook.

 * Altre classi di complessità. La classe co-NP. Problemi nell’intersezione tra NP e co-NP.

'''Modalità di Svolgimento dell'Esame'''

L’esame consiste di una prova scritta obbligatoria e di una prova orale facoltativa (obbligatoria nel caso in cui non sia stata conseguita una soglia minima nella parte scritta).

'''Materiale Didattico'''

 . [[http://wwwinfo.deis.unical.it/~frank/C&C/testi%20consigliati.htm|Testi Consigliati]]
 . [[http://wwwinfo.deis.unical.it/~frank/C&C/EserciziMacchineTuring.pdf|Esercizi su macchine di Turing]]
 . [[http://wwwinfo.deis.unical.it/~frank/C&C/Riduzioni.pdf|Esercizi sulla Complessità, in particolare sui problemi NP]]
 . [[http://wwwinfo.deis.unical.it/~frank/C&C/tracce/|Alcune Tracce d'Esame]]
 . Altro materiale è disponibile sulla pagina dedicata al corso di Informatica Teorica su [[http://icampus.dimes.unical.it|icampus]] (occorre registrarsi)

'''Orario di Ricevimento'''

Prof. Francesco Scarcello: mercoledì mattina presso il suo studio (DIMES, cubo 41/C, III piano).