Materia:Informatica teorica
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à.
Area 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
Dipartimento
Questa materia è curata dagli utenti del
Dipartimento: Tecnologie dell'informazione
Le conoscenze indispensabili sono due: una conoscenza di base delle tecniche di dimostrazione dei teoremi e i rudimenti della teoria dei linugaggi
Introduzione allo studio dell'informatica teorica
Modulo 1 - Modelli computazionali
Parte 1 - Modelli operazionali nel caso deterministico
- Automa a stati finiti
- Proprietà degli automi a stati finiti
- Minimizzazione degli stati di un automa
- Proprietà di chiusura dei linguaggi regolari
- Automa a pila
- Macchina di Turing
Parte 2 - Modelli operazionali nel caso non deterministico
- Automa a stati finiti non deterministico
- Automa a pila non deterministico
- Macchine di Turing non deterministica
Parte 3 - Modelli denotazionali
Modulo 2 - Teoria della computabilità
Modulo 3 - Teoria della complessità
È 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.
La Biblioteca del Dipartimento di Tecnologie dell'informazione contiene risorse utili per approfondire.