ALGORITMI E STRUTTURE DATI 1 (corso di laurea in Informatica)
A. A. 1999/00
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.