Corsi di Studio del Dipartimento di Culture, Politica e Società

L'obiettivo del corso e' quello di fornire una panoramica ei fondamenti teorici dell'informatica.

Verranno analizzati modelli di computazione che sono alla base della nascita e sviluppo dell'informatica e che ancora oggi sono modelli per sistemi automatici.

partendo poi dal concetti di algoritmo verranno analizzati aspetti quali la calcolabilita', la correttezza e la complessita' degli algoritmi.

Questo presupporra' l'introduzione di basi di logica.

Verra' inoltre analizzata la teoria dei linguaggi, correlandola con i modelli di calscolo e con le probelmaticeh legate alla comprensione e traduzione di linguaggi di programmazioen ad alto livello e (accennato) al linguaggio naturale.

Verranno infine introdotti le basi fondazionali della Intelligenza Artificiale

Competenze di base per percorsi informatici successivi alla laurea triennale

Seminariale

Discussione degli argomenti trattati

Programma di massima:

1. Logica
   1. Fondamenti
   2. Calcolo proposizionale
   3. Logica Primo ordine
   4. Inferenza e Concetti di correttezza, completezza, …
   5. Logiche non standard
2. Modelli di calcolo e Teoria dei linguaggi
   
   1. Automi
   2. Classi di grammatiche e linguaggi formali
   3. Parser, traduttori, compilatori ed interpreti
3. Logica e specifica dei programmi
   1. Proprieta’, invarianti
   2. Verifiche di proprieta’ dei programmi
4. Cenni di calcolabilita’
   1. Modelli di calcolo (Automi, macchine Turing, …)
   2. Funzioni calcolabili e non calcolabili
5. Cenni di complessita’
   1. Misure di complessita’
   2. Algoritmi e Complessita’ concreta
6. Algoritmi su strutture dati ricorsive: liste, alberi, grafi