Questa materia è incompleta Tutti i contributi sono ben accetti perché sono state scritte poche lezioni di questa materia (o nessuna). Se vuoi contribuire è consigliato (ma non obbligatorio) prendere visione della pagina del dipartimento che si occupa dello sviluppo delle lezioni di tuo interesse.
Nel corso di Informatica Teorica vengono forniti i concetti di teoria alla base dell'informatica.
Panoramica
Il cuore dell'informatica è il concetto di computazione. L'informatica teorica si propone di studiare ed analizzare le proprietà di una serie di modelli formali impiegati per rappresentare la computazione stessa.
A questo scopo, la disciplina è organizzata in tre parti:
modelli computazionali: vengono studiate le più diffuse tecniche per la rappresentazione della computazione, ponendo l'accento su quelle che sono anche in grado di analizzare le qualità e le prestazioni delle computazioni svolte;
computabilità: viene studiata la possibilità di risolvere problemi ricorrendo alla computazione. Dal momento che non sempre questo è possibile, la teoria della computabilità stabilisce dei limiti per l'applicabilità di queste tecniche alla soluzione dei problemi;
complessità: viene studiata l'efficienza con cui le due risorse fondamentali vengono impiegate nella computazione, ossia lo spazio di memoria ed il tempo di calcolo.
In base a questa organizzazione della disciplina è possibile articolare il corso in tre moduli: uno dedicato ai modelli computazionali, uno alla teoria della computabilità ed uno alla teoria della complessità.
Prerequisiti
Le conoscenze indispensabili sono due: una conoscenza di base delle tecniche di dimostrazione dei teoremi e i rudimenti della teoria dei linugaggi
È possibile, e fortemente consigliato, integrare le lezioni e valutare la propria preparazione attraverso queste esercitazioni. È possibile verificare la conoscenza di un argomento specifico o dell'intero programma.
Questa materia al momento non prevede verifiche d'apprendimento.
Risorse
La Biblioteca del Dipartimento di Tecnologie dell'informazione contiene risorse utili per approfondire.