Canale Informatica

1. Esercitazione 19 Ottobre 2005 (2 ore)

Complessita' asintotica, notazione O grande, Omega e Teta, algebra della notazione asintotica. Complessita' degli algoritmi: l'esempio della ricerca del massimo in un vettore.

2. Esercitazione 21 Ottobre 2005 (2 ore)

RICORSIONE: Metodo iterativo, esempio del fattoriale (complessita' temporale e spaziale), esempio dei numeri di Fibonacci (limitazione inferiore e superiore per la complessita'), implementazione ricorsiva delle liste, metodo dell'albero delle ricorsioni, complessita' del Merge Sort.

3. Esercitazione 28 Ottobre 2005 (2 ore)

RICORSIONE: Ricerca binaria ricorsiva. Procedura Partition ricorsiva. Complessita' del quick sort nel caso migliore e peggiore. Considerazioni sul caso medio. Esercizi sulla complessita' degli algoritmi ricorsivi.

4. Esercitazione 2 Novembre 2005 - Prof.ssa Marchioro (2 ore)

ALBERI: attraversamenti in pre-, in- e post-ordine; calcolo dell'altezza e del fattore di bilanciamento di un albero binario; albero delle espressioni; eliminazione di foglie con una certa proprieta'.

5. Esercitazione 4 Novembre 2005 (2 ore)

ALBERI: complessita' degli attraversamenti ricorsivi tramite equazione di ricorrenza; caratterizzazione degli alberi binari tramite stringhe di visita in pre- ed in-ordine; vettore dei padri; trasformazione da albero m-ario in binario e relazione tra le loro altezze.

6. Esercitazione 11 Novembre 2005 (2 ore)

HEAP: minimo di un heap massimo; fusione di due heap; inserimenti e cancellazioni.

ALBERI BINARI DI RICERCA: Confronto tra alberi binari, heap e alberi binari di ricerca; considerazioni sull'ordinamento tramite ABR; fusione di due ABR; considerazioni sul successore e predecessore di un nodo in un ABR.

7. Esercitazione 18 Novembre 2005 (2 ore)

ALBERI AVL: determinazione delle chiavi comuni a due AVL; rotazioni; inserimenti e cancellazioni; studio di vari tipi di funzioni di bilanciamento.

8. Esercitazione 25 Novembre 2005 (2 ore)

GRAFI: confronto tra varie strutture per memorizzare un grafo (liste di adiacenza, matrice di adiacenza, matrice di incidenza, lista di archi); trasformazione da una struttura ad un'altra; calcolo del trasposto di un grafo; calcolo del quadrato di un grafo; ordinamento delle liste di adiacenza.

9. Esercitazione 2 Dicembre 2005 (2 ore)

VISITA IN PROFONDITA' DI GRAFI: Problema del VIP. Classificazione degli archi nella visita in profondita'; aciclicita' di grafi orientati e non orientati; calcolo del matching massimale; visita in profondita' iterativa; applicazioni varie della visita in profondita'.

10. Esercitazione 14 Dicembre 2005 (2 ore)

VISITA IN AMPIEZZA DI GRAFI: Classificazione degli archi nella visita in ampiezza; cammini minimi da sorgente singola; grafi bipartiti e loro caratterizzazione; applicazioni varie della visita in ampiezza.

10. Esercitazione 16 Dicembre 2005 (2 ore)

Esercizi in aula.

Canale Tecnologie Informatiche

1. Esercitazione 7 Ottobre 2005 (2 ore)

Alcuni esempi di calcolo del numero di operazioni di programmi: bubble sort, insertion sort, inserimenti in una laista.

2. Esercitazione 24 Ottobre 2005 (2 ore)

VIP: soluzione quadratica e lineare. RICORSIONE: implementazione ricorsiva delle liste, determinazione di un elemento in comune tra due vettori, verifica dell'inclusione degli elementi di un vettore in un altro.

3. Esercitazione 28 Ottobre 2005 (2 ore)

RICORSIONE: Esercizi sulla complessita' degli algoritmi ricorsivi.

ALBERI: complessita' degli attraversamenti ricorsivi di un albero binario tramite equazioni di ricorrenza. Caratterizzazione di un albero binario tramite coppie di attraversamenti. Albero delle espressioni. Vettore dei padri.

4. Esercitazione 7 Novembre 2005 (2 ore)

ALBERI: Albero delle espressioni; trasformazione da albero m-ario in binario e relazione tra le loro altezze.

HEAP: calcolo del minimo in un heap massimo; fusione di due heap con certe proprieta'; cancellazione di un elemento in un heap; inserimento di un elemento in un heap.

5. Esercitazione 21 Novembre 2005 (2 ore)

ALBERI BINARI DI RICERCA: Confronto tra alberi binari, heap e alberi binari di ricerca; considerazioni sull'ordinamento tramite ABR; fusione di due ABR; considerazioni sul successore e predecessore di un nodo in un ABR.

ALBERI AVL: determinazione delle chiavi comuni a due AVL.

6. Esercitazione 30 Novembre 2005 (1 ora)

ALBERI AVL: rotazioni; inserimenti e cancellazioni; studio di vari tipi di funzioni di bilanciamento.

6. Esercitazione 2 Dicembre 2005 (2 ore)

B-ALBERI: inserimenti e cancellazioni; calcolo del successore.

GRAFI: rappresentazione in memoria.

**************************************************

Esercitazioni A.A. 04/05

Esercitazione 22 Ottobre 2004 (2 ore)

Complessita' asintotica, notazione O grande, Omega e Teta, algebra della notazione asintotica. Complessita' degli algoritmi: l'esempio della ricerca del massimo in un vettore.

Esercitazione 27 Ottobre 2004 (2 ore)

Complessita' degli algoritmi (segue): l'esempio del bubble sort in due versioni. Ricorsione, equazioni di ricorrenza. Metodo si soluzione per iterazione: l'esempio del fattoriale (versione ric. e iterativa)

Esercitazione 28 Ottobre 2004 (1 ora)

Ricorsione (segue): l'esempio dei numeri di Fibonacci. Implementazione ricorsiva delle liste.

Esercitazione 5 Novembre 2004 (2 ore)

Calcolo della complessita' del Merge Sort. Il metodo dell'albero della ricorsione. Calcolo della complessita' del Quick Sort nel caso peggiore e migliore. Il metodo per sostituzione.

Esercitazione 12 Novembre 2004 (2 ore)

Correzione esercizi per casa. Complessita' del Quick Sort nel caso medio. Alcuni esempi di equazioni di ricorrenza.

Esercitazione 17 Novembre 2004 (2 ore)

Correzione esercizi per casa. Grafi e loro rappresentazione in memoria: liste di adiacenza, matrice di adiacenza, matrice di incidenza, lista di archi, e considerazioni sulla complessita'. Esercizi svolti in classe: VIP, ricerca dei nodi sorgente di un grafo orientato, G^2.

Esercitazione 18 Novembre 2004 (1 ora)

Visita in profondita': algoritmo e complessita', codice ricorsivo.

Esercitazione 19 Novembre 2004 (2 ore)

Visita in ampiezza: algoritmo e complessita', codice. Componenti connesse. Classificazione degli archi di una visita e proprieta' specifiche per gli archi delle due visite principali. Applicazioni della visita in profondita': aciclicita' di un grafo orientato con teorema di caratterizzazione.

Esercitazione 26 Novembre 2004 (2 ore)

Correzione esercizio per casa. Applicazioni della visita in profondita': matching massimale. Applicazioni della visita in ampiezza: cammini minimi da sorgente singola; bipartizione di un grafo e teorema di caratterizzazione.

Esercitazione 18 Dicembre 2004 (2 ore)

Correzione esercizio per casa. Alberi. Teorema di caratterizzazione. Modifica delle visite di alberi. Heap. Alberi binari di ricerca.

Esercitazioni AA 03-04

Elenco Studenti che hanno consegnato gli esercizi con indicazioni sul risultato della correzione

Attenzione:

- non sono accettati gli esercizi consegnati per e-mail

- non saranno corretti gli esercizi privi della stampa di una esecuzione.

• file doc