# click the upper-left icon to select videos from the playlist
source: Ryo Saeba 2013年7月11日
UniNettuno - Informatica Teorica
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
01 Introduzione 38:23
02 Grammatiche di Chomsky 40:35
03 Linguaggi Regolari e Automi a Stati Finiti 40:14
04 Proprietà dei Linguaggi Regolari 40:25
05 Proprietà dei Linguaggi non Contestuali 40:35
06 Riconoscimento di Linguaggi non Contestuali 41:01
07 Macchine di Turing 42:01
08 Calcolabilità Secondo Turing 41:07
09 Limiti della Calcolabilità 41:28
10 Macchine a registri 40:30
11 Funzioni Ricorsive e Linguaggi Funzionali 40:14
12 Introduzione al Lisp 41:57
13 Analisi di Algoritmi e Complessità di Problemi 40:14
14 Le Classi P, NP, PSPACE 41:43
15 I Problemi NP - Completi 41:27
No comments:
Post a Comment