Esercitazioni < Algoritmi1

Tags: view all tags

<font size="+2" color=green> Esercitazioni A.A. 05/06 </font>

<font size="+1" color=red>Canale Informatica</font>

<font color=green>1. Esercitazione 19 Ottobre 2005 (2 ore)</font>

<font color=red>
Complessita' asintotica, notazione O grande, Omega e Teta, algebra della notazione asintotica.
Complessita' degli algoritmi: l'esempio della ricerca del massimo in un vettore.
</font>

<font color=green>2. Esercitazione 21 Ottobre 2005 (2 ore)</font>

<font color=red>
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.
</font>


<font color=green>3. Esercitazione 28 Ottobre 2005 (2 ore)</font>

<font color=red>
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.
</font>

<font color=green>4. Esercitazione 2 Novembre 2005 - Prof.ssa Marchioro (2 ore)</font>

<font color=red>
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'.</font>

<font color=green>5. Esercitazione 4 Novembre 2005 (2 ore)</font>

<font color=red>
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.
</font>

<font color=green>6. Esercitazione 11 Novembre 2005 (2 ore)</font>

<font color=red>
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.
</font>

<font color=green>7. Esercitazione 18 Novembre 2005 (2 ore)</font>

<font color=red>
ALBERI AVL:
determinazione delle chiavi comuni a due AVL;
rotazioni;
inserimenti e cancellazioni;
studio di vari tipi di funzioni di bilanciamento.
</font>

<font color=green>8. Esercitazione 25 Novembre 2005 (2 ore)</font>

<font color=red>
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.
</font>

<font color=green>9. Esercitazione 2 Dicembre 2005 (2 ore)</font>

<font color=red>
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'.
</font>

<font color=green>10. Esercitazione 14 Dicembre 2005 (2 ore)</font>

<font color=red>
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.
</font>

<font color=green>10. Esercitazione 16 Dicembre 2005 (2 ore)</font>

<font color=red>
Esercizi in aula.
</font>




<font size="+1" color=blue>Canale Tecnologie Informatiche</font>

<font color=green>1. Esercitazione 7 Ottobre 2005 (2 ore)</font>

<font color=blue>
Alcuni esempi di calcolo del numero di operazioni di programmi: bubble sort, insertion sort, inserimenti in una laista.
</font>

<font color=green>2. Esercitazione 24 Ottobre 2005 (2 ore)</font>

<font color=blue>
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.
</font>

<font color=green>3. Esercitazione 28 Ottobre 2005 (2 ore)</font>

<font color=blue>
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.
</font>

<font color=green>4. Esercitazione 7 Novembre 2005 (2 ore)</font>

<font color=blue>
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.

<font color=green>5. Esercitazione 21 Novembre 2005 (2 ore)</font>

<font color=blue>
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.

<font color=green>6. Esercitazione 30 Novembre 2005 (1 ora)</font>

<font color=blue>
ALBERI AVL:
rotazioni;
inserimenti e cancellazioni;
studio di vari tipi di funzioni di bilanciamento.


<font color=green>6. Esercitazione 2 Dicembre 2005 (2 ore)</font>

<font color=blue>
B-ALBERI:
inserimenti e cancellazioni;
calcolo del successore.

GRAFI:
rappresentazione in memoria.
  
  
  
  
  
  
****************************************************

<font size="+2"> [[Esercitazioni]]  A.A. 04/05 </font>

<font color=990000>Esercitazione 22 Ottobre 2004 (2 ore)</font>

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


<font color=990000>Esercitazione 27 Ottobre 2004 (2 ore)</font>

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)


<font color=990000>Esercitazione 28 Ottobre 2004 (1 ora)</font>

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

<font color=990000>Esercitazione 5 Novembre 2004 (2 ore)</font>

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. 

<font color=990000>Esercitazione 12 Novembre 2004 (2 ore)</font>

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

<font color=990000>Esercitazione 17 Novembre 2004 (2 ore)</font>

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.

<font color=990000>Esercitazione 18 Novembre 2004 (1 ora)</font>

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

<font color=990000>Esercitazione 19 Novembre 2004 (2 ore)</font>

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.

<font color=990000>Esercitazione 26 Novembre 2004 (2 ore)</font>

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.

<font color=990000>Esercitazione 18 Dicembre 2004 (2 ore)</font>

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


[[http://cesare.dsi.uniroma1.it/~asd1/ESERCITAZIONI03-04.htm][Esercitazioni AA 03-04]]

<font size="+2"><font color=green> Elenco Studenti che hanno consegnato gli esercizi con indicazioni sul risultato della correzione </font> </font>

Attenzione:

- non sono accettati gli esercizi consegnati per e-mail

- non saranno corretti gli esercizi privi della stampa di una esecuzione.
   * [[%ATTACHURL%/ELENCOAA04-05.doc][file doc]]