Programma 1995-96

Notazione asintotica e analisi degli algoritmi: richiami

La notazione asintotica (O grande, Omega grande, Theta grande) e alcune proprietà. Complessità (temporale e spaziale) di algoritmi e complessità di problemi, delimitazioni inferiore e superiore, nel caso peggiore, nel caso migliore, e nel caso medio.

Introduzione alla programmazione ricorsiva

Il principio di induzione matematica e le dimostrazioni per induzione. Definizioni induttive e ricorsive di funzioni, e calcolo con il modello a sostituzione. Sottoprogrammi ricorsivi in Pascal: ricorsione e pila (stack) dei record di attivazione. Analisi della complessità temporale degli algoritmi ricorsivi: equazioni di ricorrenza e loro soluzione. Analisi dello spazio di esecuzione. Ricorsione lineare e ricorsione ramificata. Ricorsione di coda e iterazione: eliminazione delle chiamate ricorsive di coda (trasformazione in cicli). Confronto fra soluzioni ricorsive e iterative di alcuni problemi.
Esempi illustrativi: fattoriale, esponenziale ingenuo, torri di Hanoi, fiocco di neve di von Koch, numeri di Fibonacci.

Induzione e iterazione: cenni e richiami

Invarianti e induzione, progettazione di cicli iterativi corretti.
Esempio illustrativo: il ciclo esterno dell'algoritmo di ordinamento per inserimento.

Tipi di dato: richiami e integrazioni

I tipi di dato primitivi del Pascal e TurboPascal. Il tipo record. Strutture-dati, tipi astratti, tipi di valore e di variabile.
I tipi puntatore e lo heap, gestione dinamica della memoria con controllo esplicito del programmatore.

Programmazione con strutture concatenate: liste concatenate

Sequenze e liste: definizione induttiva, realizzazione Pascal. Induzione strutturale sulle liste, programmazione ricorsiva e iterativa con le liste, in Pascal standard e in TurboPascal (6.0 o 7.0): costruzione di una lista e inserimento in testa, input/output di una lista, cancellazione e copia di una lista, inserimento e cancellazione nella posizione successiva ad un dato nodo, concatenazione di due liste. Liste bidirezionali. Liste ordinate: inserimento e ricerca, confronto fra vettori ordinati e liste ordinate. Fusione di liste ordinate.
Altri esempi ed esercitazioni sulle liste: inversione costruttiva e distruttiva, estrazione degli elementi di posto pari, differenza fra due liste, ...

Un esempio di problema di programmazione e di possibili soluzioni: l'ordinamento di una sequenza

Ordinamento per fusione: definizione ricorsiva astratta dell'algoritmo, analisi di complessità, realizzazione per liste concatenate, realizzazione per vettori, realizzazione iterativa per vettori.
Ordinamento rapido di Hoare (quicksort): definizione ricorsiva astratta dell'algorimo, analisi di complessità nel caso migliore e nel caso peggiore, intuizione del caso medio. Realizzazione di Dijkstra per i vettori e analisi della sua correttezza.

Programmazione con strutture concatenate: alberi

Alberi binari: definizione induttiva, terminologia e proprietà di base. Induzione strutturale sugli alberi binari e ricorsione sugli alberi: i tre ordini di visita (versione completamente ricorsiva, e versione semiiterativa di preordine e inordine), visualizzazione e immissione di un albero binario. Visita in preordine completamente iterativa con uso di stack esplicito, visita per larghezza (o per livelli). Ricostruzione di un albero binario a partire dalla coppia di sequenze di visita in preordine e in inordine.
Alberi di ricerca binari: ricerca, inserimento, restituzione o estrazione del minimo o del massimo, cancellazione, ricerca dell'elemento successivo a un valore dato, lettura in ordine di un albero di ricerca binario. Treesort.
Alberi generali (cioè non binari).
Altri esempi ed esercitazioni sugli alberi: "circumnavigazione" di un albero binario, somma dei valori dei nodi, massimo dei valori dei nodi, numero dei nodi, deallocazione di un albero, binario, altezza di un albero, stampa delle foglie, costruzione del vettore o della lista rappresntante una sequenza di visita di un albero binario, alberi simili e alberi speculari, ricerca di un valore in un albero (non di ricerca), ricerca di un nodo percorrendo l'albero in un dato ordine, costruzione della lista rappresntante il cammino dalla radice a un nodo di dato valore, albero binario pieno, ...

Esempi di tipi astratti: coda, pila, dizionario

Definizioni, e confronto fra realizzazioni diverse (vedi corso di Laboratorio).

Memorizzazione di strutture-dati in memoria secondaria: cenni

Files tipati e primitive ad essi relative, in Turbo-Pascal; salvataggio su memoria secondaria - e recupero - di vettori, liste, alberi.

Dove studiare: