Universitą degli Studi di Pavia - Facoltą di Scienze MMFFNN

Le informazioni di questo sito non sono pił aggiornate. Consultare il nuovo link
Home

HomeDidatticaCorsi › Fondamenti di informatica teorica

Fondamenti di informatica teorica

Corsi di laurea:
Matematica
Docenti:
Galbiati Giulia
Anno accademico:
2012/2013
Crediti formativi:
6
Ambiti:
INF/01
Decreto Ministeriale:
270/04
Ore di lezione:
48
Lingua di insegnamento:
Italiano

Modalitą

Un test scritto.

Prerequisiti

Un corso di programmazione in un linguaggio ad alto livello.

Programma

L'informatica teorica, diversamente da quella pił basata su aspetti tecnici ed applicati, č 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 pił 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 calcolabilitą, sulla teoria della complessitą, sui problemi NP-completi nel contesto della teoria della trattabilitą. Infine vengono dati alcuni cenni sulle classi di approssimabilitą dei problemi della classe NPO.

Bibliografia

1- Giorgio Ausiello, Fabrizio D'Amore, Giorgio Gambosi. Linguaggi Modelli Complessitą, Franco Angeli, 2003.

2- Lucidi del corso scaricabili alla home page del corso.


Elenco appelli e prove

Nessuna prova presente

Credits: apnetwork.it