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:
2009/2010
Codice corso:
500704
Crediti formativi:
6
Ambiti:
INF/01
Decreto Ministeriale:
270/04
Ore di lezione:
48
Lingua di insegnamento:
Italiano

Modalitą

Prova scritta

Prerequisiti

Nessuno.

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

Testi consigliati:

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

Juraj Hromkovic. Theoretical Computer Science, Springer, 2004.


Elenco appelli e prove

Nessuna prova presente

Credits: apnetwork.it