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 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 Grammatiche Espressioni regolari Funzioni ricorsive parziali Equazioni negli spazi dei linguaggi 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.

• Torna all'area:
• Torna al corso:
  • Ingegneria informatica
  • Informatica
• Torna al Dipartimento di Tecnologie dell'informazione