FONDAMENTI DELL'INFORMATICA

Crediti: 
9
Settore scientifico disciplinare: 
INFORMATICA (INF/01)
Anno accademico di offerta: 
2017/2018
Semestre dell'insegnamento: 
Secondo Semestre
Lingua di insegnamento: 

Italiano

Obiettivi formativi

Fondamenti matematici dell'informatica:

Il corso fornisce gli strumenti formali e le nozioni fondamentali per studiare problemi trattabili e non mediante calcolatore. Viene presentata la teoria degli automi e dei linguaggi formali, teoria a fondamento della descrizione e dell'implementazione dei linguaggi di programmazione. Vengono poi illustrati i concetti e la natura dei problemi che ammettono soluzione effettiva, ovvero dei problemi risolvibili mediante calcolatore.

Principi e paradigmi dei linguaggi di programmazione:

L'interazione con i computer avviene in molti modi: quando il comportamento che si desidera ottenere è semplice o già codificato, si possono usare formalismi poveri ed intuitivi. Per comunicazioni più sofisticate non si può prescindere dall'impiego di formalismi dall'elevato potere espressivo. I linguaggi di programmazione offrono una vastissima gamma di notazioni per la specifica dei comportamenti che si richiedono ad un computer. Lo studio dei linguaggi di programmazione è affascinante ed importante. In primo luogo perché lo studio dei principi fondamentali (valori, legami, controllo, astrazione, incapsulazione, oggetti, moduli, nondeterminismo, tipi, ...) e della loro realizzazione nei vari linguaggi (C, C++, Fortran, Pascal, OCaml, Java, Python, ...) aiuta a capire ciò che veramente conta nella scelta di un linguaggio di programmazione, ben al di là della "moda" del momento. In secondo luogo, perché lo studio comparato dei linguaggi conduce ad affinare l'abilità e lo stile di programmazione quali che siano i linguaggi che, in un dato momento della propria vita professionale, si usano maggiormente. Infine, più spesso di quanto non si creda la soluzione di un problema informatico passa per la definizione di un linguaggio e dalla realizzazione di una "macchina" che lo interpreta.

Prerequisiti

Fondamenti di programmazione.

Contenuti dell'insegnamento

Il corso comprende due parti distinte e complementari: una parte sui fondamenti matematici dell'informatica, l'altra sui principi e paradigmi dei linguaggi di programmazione.

Programma esteso

Fondamenti matematici dell'informatica:

* Cenni introduttivi sul concetto di algoritmo, sulla rappresentazione dell'informazione, e sull'architettura del calcolatore.
* Linguaggi formali.
* Espressioni regolari.
* Automi a stati finiti.
* Grammatiche generative.
* Linguaggi liberi dal contesto.
* Macchine di Turing.
* Funzioni calcolabili e non.
* Calcolabilità e linguaggi di programmazione.
* Cenni su insiemi ricorsivi e ricorsivamente enumerabili.

Principi e paradigmi dei linguaggi di programmazione:

* Descrizione dei linguaggi di programmazione.
* Nomi e ambiente.
* Gestione della memoria.
* Strutture e astrazioni del controllo.
* Strutture e astrazioni dei dati.

Bibliografia

* A. Dovier, R. Giacobazzi. Fondamenti dell'Informatica: Linguaggi Formali e Calcolabilità.
* A. M. Pitts. Regular Languages and Finite Automata.
* I. Mastroeni. Eserciziario per il corso ``Fondamenti dell'Informatica: Linguaggi Formali e Calcolabilità''.
* U. Solitro. Linguaggi Formali, Computabilità e Complessità: Esercizi risolti, 2006.
* A. Pettorossi. Automata Theory and Formal Languages, Aracne Editrice, 2006. ISBN: 88-548-0889-X.
* A. Pettorossi. Elements of Computability, Decidability, and Complexity, Aracne Editrice, 2006. ISBN: 88-548-0682-X.
* M. Gabbrielli e S. Martini. Linguaggi di programmazione: principi e paradigmi, Seconda edizione. McGraw-Hill Italia, 2011. ISBN 88-386-6573-8.

Metodi didattici

Lezioni ed esercitazioni.

Modalità verifica apprendimento

Esame scritto, orale e pratico (esecuzione di un progetto individuale o di gruppo sulla parte riguardante i linguaggi di programmazione).

Altre informazioni