Videolezioni  

"Informatica teorica"     

 

Indietro  

I materiali possono risalire anche a parecchi anni fa; nonostante ci˛ i contenuti non risultano affatto obsoleti.

 

Segnalate a [email protected] eventuali problemi ed anomalie

Scopi Presentare vari modelli formali adatti a descrivere linguaggi ed a rappresentare macchine e programmi ed illustrarne i principali aspetti: proprietÓ sintattiche dei linguaggi e verifiche di correttezza sintattica potere computazionale dei vari modelli di calcolo varianti deterministiche e non deterministiche costi di computazione Approfondire le proprietÓ del concetto di calcolabilitÓ e comprendere i limiti teorici dei calcolatori (problemi non decidibili, funzioni non calcolabili) Approfondire il concetto di costo di risoluzione di un problema (complessitÓ computazionale) e comprendere i limiti pratici dei calcolatori (problemi computazionalmente intrattabili). Contenuti Linguaggi formali e automi. Macchine di Turing e calcolabilitÓ Macchine a registri Funzioni ricorsive e linguaggi funzionali ComplessitÓ di algoritmi e problemi. Prerequisiti Fondamenti di Informatica I e II