Diario delle lezioni
NB: Il materiale integrativo non subirā variazioni sostanziali rispetto a quello fornito lo scorso A.A. Le variazioni presenti saranno evidenziate.
- 1) 05.10.2011 Presentazione del corso. Richiami di C. [slides-LASD09-parte1.pdf, pagg. 1--36]
- 2) 07.10.2011 Richiami di C. Strutture autoreferenzianti. Liste (semplici). [slides-LASD09-parte1.pdf, pagg. 37--61]
- 3) 12.10.2011
Liste: implementazione di funzioni per l'inserimento e la cancellazione di elementi. Ricorsione. [slides-LASD09-parte1.pdf, pagg. 62--73]
Esercitazione: creazione di una lista; cancellazione ed inserimento del k-mo elemento; stampa, conteggio e somma dei valori contenuti in una lista di interi; inserimento in una lista ordinata. Puntatori a funzione. [01-esercitazioni.zip] - 4) 14.10.2011 Esercitazione (continua da lezione precedente).
- 5) 19.10.2011
Introduzione ai tipi di dato astratti - ADT [slides-LASD09-parte1.pdf, pagg. 74--84] (Rif: capp. 3 e 4).
Applicazione: Interfacce per la gestione di una sequenza di elementi e relative implementazioni mediante liste semplici ed array dinamici (versione semplificata a scopo didattico). Uso dell'interfaccia per la definizione di alcune funzioni derivate: creazione di una sequenza casuale di elementi, inversione dell'ordine degli elementi della sequenza, stampa degli elementi. [02-interfacce-sequenze.zip].
Interfaccia per l'elaborazione di liste semplici [03-liste-semplici.zip]. - 6) 21.10.2011
ADT Stack [slides-LASD09-parte1.pdf, pagg. 85--92].
Interfacce per l'elaborazione di stack.
[04-stack.zip] (Rif: cap. 4). Applicazioni: valutazione di un'espressione postfissa; conversione di un'espressione da forma infissa a forma postfissa.
Stack di puntatori generici [05-postfissa-gen.zip]. Approfondimento: il linguaggio Postscript e relativi esempi di file PS (Rif: cap. 4).
- 7) 26.10.2011
Implementazioni del ADT Stack mediante array e liste [rif. 04-stack.zip, cap. 4].
Esercitazione: soluzione di esercizi tratti dalle precedenti prove d'esame [08-soluzioni-ex-stack.zip].
La compilazione condizionale: direttive #ifdef, #ifndef e loro uso nell'implementazione del ADT Stack mediante liste [09-dichiarazioni-annidate.zip]. - 8) 28.10.2011
ADT Queue. Interfacce per l'elaborazione delle code e relative implementazioni mediante array (buffer circolare) e liste semplici
[10-code.zip] (Rif: cap. 4).
Alberi: definizioni, proprietā, ADT Btree [slides-LASD09-parte1.pdf, pagg. 96--107]. - 9) 02.11.2011 Definizione di una interfaccia per l'elaborazione degli alberi binari. Uso dell'interfaccia per la definizione di alcune funzioni derivate (calcolo del numero di nodi e dell'altezza di un albero binario) [11-btree.zip] (Rif: cap. 5)
- 10) 04.11.2011
Visite di alberi: visite iterative in profonditā (preorder, inorder, postorder); visita in ampiezza (levelorder)
[12-visite-btree.zip] (Rif: cap. 5).
- 11) 09.11.2011
Ordinamento di array. Richiami sugli algoritmi di ordinamento. Definizione di un'interfaccia
[13-ordinamento-array.zip] (Rif: capp. 6-7-8).
Applicazione: misura delle prestazioni degli algoritmi di ordinamento di array di interi). - 12) 16.11.2011
Ordinamento di array (continua): Quicksort ricorsivo ed iterativo. Ordinamento di array "generici" (avanzato)
[14-ordinamento-array-gen.zip]
Ordinamento di liste: Insertionsort, Selectionsort, Mergesort [15-ordinamento-liste.zip] (Rif: §6.9) - 13) 18.11.2011 Esercitazione preparatoria per la prova intermedia. Svolgimento di esercizi tratti dalle precedenti prove d'esame.
- 14) 30.11.2011
La struttura dati heap: ripristino dei vincoli di uno heap (funzioni FixUp, FixDown), inserimento e cancellazione di elementi.
Costruzione top-down e bottom-up di uno heap. Heapsort. (Rif: cap. 9)
[16-Heap-Heapsort.zip]
Ordinamento indiretto mediante indicizzazione di array e uso dei puntatori (Rif: §6.8) [17-Heapsort-indiretto.zip] - 15) 02.12.2011
Dizionari. Ricerca indicizzata da chiave. Ricerca binaria.
Alberi binari di ricerca (BST): definizione, ricerca ed inserimento di un elemento (versioni ricorsiva ed iterativa). Rotazioni, inserimento di un elemento alla radice.
(Rif: cap. 12) [18-Dizionari.zip] - 16) 07.12.2011
Soluzione prova intermedia.
BST: cancellazione di un elemento, unione di BST.
BST 2-3-4 bilanciati: scomposizione di 4-nodi; Inserimento bottom-up e inserimento top-down (Rif: §13.3)
- 17) 14.12.2011
Alberi red-black. Inserimento in un BST red-black con rotazioni (Rif. § 13.4)
[19-RBtree.zip]
- 18) 16.12.2011 Grafi: definizioni e rappresentazioni mediante matrice di adiacenza, liste di adiacenza, matrice di incidenza e liste di archi. Definizione di interfacce per la gestione di grafi non etichettati rappresentati mediante liste di adiacenza e matrice di adiacenza (Rif. § 3.7; [ALG] § 11.2) [20-Grafi.zip]
- 19) 19.12.2011
Visite di grafi. Implementazione della visita in ampiezza di un grafo (Rif. § 5.8)
[21-Grafi-visite.zip]
Esercitazione: soluzione di esercizi tratti dalle precedenti prove d'esame - 20) 21.12.2011
Implementazione della visita in profonditā di un grafo (versioni ricorsiva ed iterativa) (Rif. § 5.8)
Esercitazione: soluzione di esercizi tratti dalle precedenti prove d'esame. - 21) 11.01.2012 Strutture dati Union-Find (UF). Definizione di interfacce per la gestione di strutture dati UF: rappresentazione di insiemi disgiunti tramite liste collegate (cenni) ed array; implementazione degli algoritmi Quick-Find e Quick-Union. Applicazione: verifica della connessione di un grafo non orientato. [22-union-find.zip]
- 22) 18.01.2012
Strutture dati UF (continua):
implementazione di euristiche di bilanciamento nell'operazione Union (Union by rank e Union by size) ed euristiche di compressione
nell'operazione Find (Find by compression e Find by splitting).
Esercitazione: soluzione di esercizi tratti dalle precedenti prove d'esame.
ADT Coda con prioritā. Implementazioni elementari. Coda con prioritā basata su heap. Applicazione: uso delle code con prioritā per l'ordinamento di valori (Rif: cap. 9) [23-Pqueue.zip]. - 23) 20.01.2012 (4h)
Grafi etichettati: definizione e rappresentazione mediante matrice di adiacenza e liste di adiacenza.
Definizione di interfacce per la gestione di grafi etichettati rappresentati mediante liste di adiacenza. [24-Grafi-etichettati.zip].
Esercitazione: soluzione di esercizi sui grafi tratti dalle precedenti prove d'esame. - 24) 25.01.2012
Costruzione dell'albero dei cammini minimi a sorgente singola in grafi etichettati con valori non negativi sugli archi (Dijkstra).
[25-Dijkstra.zip]
Costruzione del minimo albero ricoprente in grafi non orientati e connessi, etichettati con valori non negativi sugli archi. (Kruskal). [26-Kruskal.zip] - Fine corso