1. 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 e veloce,
torri di Hanoi, fiocco di neve di von Koch, numeri di Fibonacci.
2. Tipi di dato: richiami e integrazioni.
I tipi di dato primitivi del Pascal e TurboPascal. Il tipo record.
Vettori di record, strutture annidate. I tipi puntatore. L'operatore indirizzo
(@) del TurboPascal. Heap e gestione dinamica della memoria con controllo
esplicito del programmatore.
3. Programmazione con strutture concatenate: liste.
Sequenze e liste: definizione induttiva, realizzazione Pascal. Induzione
strutturale sulle liste, programmazione ricorsiva e iterativa con le liste
(in Pascal standard e in TurboPascal): 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 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, rappresentazione di insiemi per mezzo di liste ordinate,
operazioni su insiemi come liste ordinate (intersezione, unione, ecc.).
4. Tipi astratti di dati.
Nozione di tipo astratto; costruzione e uso di moduli (unit) in TurboPascal.
Il tipo astratto insieme. Il tipo astratto dizionario.
5. Pila e coda.
Il tipo astratto pila e le sue realizzazioni (vettore, lista concatenata).
Il tipo astratto coda e le sue realizzazioni: come vettore circolare, come
lista concatenata.
6. 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,
costruzione del vettore o della lista rappresentante una sequenza di visita
di un albero binario.
Alberi di ricerca binari: ricerca, inserimento, restituzione o estrazione
del minimo o del massimo, cancellazione, lettura in ordine. Analisi della
complessità delle operazioni. Tipo astratto dizionario: confronto
fra realizzazioni diverse.
Qualche cenno su registrazione in memoria secondaria di vettori, liste,
alberi.
Altri esempi ed esercitazioni sugli alberi: 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, alberi uguali,
simili, 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 rappresentante il cammino dalla radice a un nodo di dato valore,
albero binario pieno, numero dei nodi di livello uguale (o inferiore, o
superiore, ecc.) a un dato n, costruzione della lista dei nodi del cammino
dalla radice ad un elemento, "più recente antenato comune" di due
nodi, ...
7. 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, cenni
sulla realizzazione per vettori.
Ordinamento per mezzo di albero (treesort).
Confronto fra gli algoritmi di ordinamento presentati nei corsi di
Programmazione I e II.
Stabilità. Un algoritmo di ordinamento lineare, non per confronti:
il counting sort.
Dove studiare:
Copie dei lucidi con note e testi di esercizi, disponibili in biblioteca.
Manuali del TurboPascal 7.0 (disponibili in laboratorio).
G. Fiorentino e altri, Pascal Laboratorio di programmazione, McGrawHill,
1996.
Altri testi consigliati:
M. Gori e altri, Pascal e C guida pratica alla programmazione, McGraw-Hill,
1996.
Aho-Ullman, Fondamenti di Informatica, Zanichelli.