Obiettivi formativi



L'informatica teorica, diversamente da quella piu' basata su aspetti tecnici ed applicati, e' fortemente legata a domande fondamentali circa l'esistenza di soluzioni algoritmiche, i limiti fisici del calcolo automatico, le metodologie usate nel disegno di algoritmi. In questo corso si introducono alcune delle tematiche piu' classiche della disciplina.



Prerequisiti



Una conoscenza di base di un linguaggio di programmazione e' utile, anche se non indispensabile.



Contenuti



Linguaggi formali e gerarchia di grammatiche di Chomsky, automi a stati finiti e linguaggi regolari, macchine a registri, macchine di Turing e macchina di Turing universale.



Nozioni sulle funzioni ricorsive, sulla teoria generale della calcolabilita', sulla teoria della complessita', sui problemi NP-completi nel contesto della teoria della trattabilita'.



Cenni sulle classi di approssimabilita' dei problemi della classe NPO.



Programma esteso



Testi di riferimento



Giorgio Ausiello, Fabrizio D'Amore, Giorgio Gambosi. Linguaggi Modelli Complessita', Franco Angeli, 2003.



Metodi didattici



Lezioni



Modalita' d'esame



Esame scritto



Altre informazioni







http://mate.unipv.it/~galbiati/corsi/fondamenti_inf_teoricaLucidi/G1-presentazione.pdf