Obiettivi e contenuti



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: 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. Vengono fornite anche nozioni sulle funzioni ricorsive, sulla teoria generale della calcolabilita', sulla teoria della complessita', sui problemi NP-completi nel contesto della teoria della trattabilita'. Infine vengono dati alcuni cenni sulle classi di approssimabilita' dei problemi della classe NPO.



Riferimenti bibliografici



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







http://mate.unipv.it/~galbiati/corsi/fondamenti_inf_teoricaHome.html