Materia:Informatica teorica

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.

Informatica teorica

Tutte le lezioni in ordine alfabetico

Aree di riferimento

Per questa materia non è ancora stata specificata un'area.

Corsi

Questa materia fa parte dei seguenti corsi:
Corso di Ingegneria informatica
Corso di Informatica

Dipartimenti

Questa materia è curata dagli utenti del
Dipartimento: Tecnologie dell'informazione

Presentazione

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

Programma

Introduzione allo studio dell'informatica teorica

Modulo 1 - Modelli computazionali

Parte 1 - Modelli operazionali nel caso deterministico

Parte 2 - Modelli operazionali nel caso non deterministico

Parte 3 - Modelli denotazionali

Modulo 2 - Teoria della computabilità

Modulo 3 - Teoria della complessità

Verifiche d'apprendimento

È 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.