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.

 

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

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

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:

  1. 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;
  2. 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;
  3. 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.