ALGORITMI E STRUTTURE DATI 1 (corso di laurea in Informatica)

Prof. Alan A .Bertossi

Oggetto e obiettivi del corso

• 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