LABORATORIO DI INFORMATICA (m)
1oMODULO
A. A. 1997-98
Prof. Alan A .Bertossi
Oggetto e obiettivi del corso
Il termine "algoritmo" indica la descrizione delle azioni che un esecutore deve compiere per ricavare la soluzione di un problema computazionale. Scopo del corso è fornire i fondamenti per:
- Caratterizzare i dati da elaborare, organizzandoli e strutturandoli in modo da agevolarne l'uso da parte degli algoritmi che li elaborano;
- Progettare algoritmi corretti (cioè che risolvono sempre e solo il problema cui si è interessati) ed efficienti (cioè che lo risolvono il più velocemente possibile);
- Studiare le inerenti limitazioni e difficoltà di classi di problemi da risolvere;
- Illustrare proprietà di linguaggi di programmazione atti a descrivere algoritmi.
Programma
- Elementi di teoria dei linguaggi formali
Linguaggi formali. Metodi riconoscitivi, generativi e algebrici. Grammatiche a struttura di frase. Classificazione alla Chomsky. Forma di Backus-Naur. Alberi di derivazione ed ambiguità.
- Elementi di teoria della computabilità
Automi a stati finiti e Macchine di Turing (MdT). Universalità delle MdT. Tesi di Church. Indecidibilità del problema della terminazione. Non universalità di formalismi che calcolano solo funzioni totali. Random Access Machine (RAM). Esempio di interprete universale RAM.
- Strutture di dati elementari
Dati, tipi di dato e strutture di dati. Specifica sintattica, semantica e realizzazione. Vettori, record e matrici. Liste, pile e code. Pile e procedure ricorsive. Alberi liberi, radicati, ordinati e binari. Visite di alberi ordinati: anticipata, simmetrica e differita. Insiemi. Dizionari. Ricerca binaria ed interpolazione.
- Introduzione al progetto e all'analisi di algoritmi
Complessità computazionale nel caso pessimo e nel caso medio. Ordini di grandezza. Complessità polinomiale e super-polinomiale. Equazioni di ricorrenza. Algoritmi di ricerca e di ordinamento. Ottimalità del Mergesort nel caso pessimo e del Quicksort nel caso medio.
- Il linguaggio Pascal
Descrizione mediante grammatica in forma di Backus-Naur. Variabili, costanti, epressioni. Tipi di dato: booleani, interi, reali, caratteri, array, set, record, puntatori. Istruzioni semplici e composte, di assegnamento, ripetitive e condizionali. Procedure e funzioni. Visibilità e passaggio dei parametri. Ricorsione.
Testi adottati
A.A. BERTOSSI, Strutture, Algoritmi, Complessità, Edizioni Culturali Internazionali (ECIG), Genova, 1990
J. WELSH & J. ELDER, Introduzione al Pascal, ESA, Roma, 1987 (2a edizione)
Testi di consultazione
T.H. CORMEN, C.E. LEISERSON & R.L. RIVEST, Introduction to Algorithms, The MIT Press/McGraw-Hill, 1991
H.R. LEWIS & C.H. PAPADIMITRIOU, Elements of the Theory of Computation, Prentice-Hall, 1982
Modalità e svolgimento dell'esame
Per il Modulo I è prevista una prova scritta seguita da una verifica pratica di programmazione su personal computer.
Per il Modulo II è invece prevista una prova orale.