AnnoAccademico2011-2012 < Infogen

Tags: view all tags
---+++ <font color=990000 size="+1"> A.A. 2011/2012</font>
<font color=blue> 
*Lezioni 1-2: lunedì 5 marzo 2012*

Presentazione del corso<br>
Introduzione
   * Concetti di algoritmo, di struttura dati, di efficienza; di complessita' computazionale.
   * Modello RAM; misura di costo uniforme e logaritmico.
</font>


<font color=blue> 
*Lezioni 3-4: martedì 6 marzo 2012*

Notazione asintotica (1)
   * Definizione e significato degli insiemi O, &Omega; e &Theta;.
   * Esempi.
   * Algebra della notazione asintotica.
   * Valutazione della complessita' computazionale.
</font>

<font color=green> 
*Esercitazioni 1-2: Venerdì 9 marzo 2012*

   * Discussione del programma di esempio:  [[%ATTACHURL%/esempio1.c][esempio1.c]]
   * Compilazione ed esecuzione di un programma C in Linux
   * Ripasso di nozioni elementari del linguaggio C:
      * Commenti 
      * Inclusione di librerie predefinite
      * Direttive del preprocessore C: #include e #define
      * Dal file C al file eseguibile: preprocessore, compilazione, linking
      * La funzione main
      * Variabili: tipi, dichiarazione, assegnamento
      * Operatori aritmetici, di uguaglianza,  relazionali e logici
      * Il comando if..else
      * Input e output standard in C: funzione printf e scanf
</font>

<font color=blue> 
*Lezioni 5-6: lunedi' 12 marzo 2012*

Notazione asintotica (2)
   * Esempi di valutazione della complessita' computazionale.

Il problema della ricerca
   * Ricerca sequenziale in un vettore disordinato;
   * complessita' nel caso migliore, peggiore e medio.
   * Ricerca binaria in un vettore ordinato (vers. iterativa);
   * complessita' nel caso migliore, peggiore e medio.
   * Formulazione ricorsiva della ricerca binaria.
</font>

<font color=green> 
*Esercitazioni 3-4: Martedì 13 marzo 2012*

Iterazione: 
   * Ciclo while, for e do..while
   * Istruzioni break e continue
   * Esercizio: determinare se un numero e' primo: [[%ATTACHURL%/is_prime.c][is_prime.c]]
Vettori: 
   * Allocazione statica
   * Indicizzazione e accesso agli elementi
   * Esercizio: trovare l'elemento di valore massimo: [[%ATTACHURL%/find_max_array.c][find_max_array.c]]
   * Esercizio: trovare la lunghezza del piu' lungo sottovettore composto da soli numeri pari: [[%ATTACHURL%/sottovettore_pari_lin.c][sottovettore_pari_lin.c]]
</font>

<font color=darkGreen>
*Esercizi assegnati:*

Iterazione: 
   * Scrivere un programma che prenda in input un intero n e:
      * Calcoli n!
      * Stampi un quadrato di * di dimensione nxn
      * Stampi i primi n numeri primi

Vettori:
   * Scrivere un programma che calcoli la somma degli elementi di un vettore
   * Scrivere un programma che trovi il minimo ed il massimo di un vettore
   * Modificare il programma [[%ATTACHURL%/sottovettore_pari_lin.c][sottovettore_pari_lin.c]] per fare in modo che stampi il sottovettore trovato
   * Scrivere un programma che dati due vettori A e B trovi la lunghezza del sottovettore comune pie' lungo
</font>

<font color=blue> 
*Lezioni 7-8: venerd' 16 marzo 2012*

Ricorsione
   * Funzioni matematiche ricorsive
   * Algoritmi ricorsivi
      * Fattoriale;
      * Numeri di Fibonacci;
      * Ricerca sequenziale;
      * Ricerca binaria.
</font>
<font color=darkBlue>
*Esercizi assegnati:*
   * Progettare degli algoritmi ricorsivi che risolvano i seguenti problemi ed esprimerli tramite pseudocodice:
      * sommare gli n elementi di un vettore di interi;
      * trovare il massimo fra gli n elementi di un vettore di interi;
      * dati due interi n e k, calcolare la potenza k-esima di n;
      * verificare se un vettore dato è palindromo;
      * trovare la somma del sottovettore di somma massima in un vettore di n interi (positivi e negativi). 
 </font>

<font color=blue> 
*Lezioni 9-10: lunedi' 19 marzo 2012*

Soluzioni delle equazioni di ricorrenza (1)

   * Metodo di sostituzione.
   * Metodo iterativo.
   * Metodo dell'albero.
   * Esempi di applicazione dei vari metodi. 

</font>

<font color=blue> 
*Lezioni 11-12: martedi' 20 marzo 2012*

Soluzioni delle equazioni di ricorrenza (2)

   * Metodo del teorema principale.
   * Esempi di applicazione del metodo del teorema principale. 
   * Dimostrazione del teorema principale.
</font>

<font color=green> 
*Esercitazioni 5-6: Venerdì 23 marzo 2012*

   * Soluzione esercizio: Trovare il sottovettore comune di lunghezza massima di due vettori. [[%ATTACHURL%/sottovettore_comune_max.c][sottovettore_comune_max.c]]
   * Matrici di dati: 
      * Dichiarazione, rappresentazione in memoria
      * Esercizio: calcolare la somma degli elementi con valore positivo di una matrice: [[%ATTACHURL%/sum_positive_matrix.c][sum_positive_matrix.c]]
   * Assegnazione Homework di prova.

</font>

<font color=darkGreen>
*Esercizi assegnati:*

Matrici:
   * Scrivere un programma che allochi una matrice M di ROW righe e COL colonne e calcoli quanti elementi rispettano la relazione M[i,j] = i+j
   * Scrivere un programma che allochi una matrice quadrata M di dimensione SIZE x SIZE e:
      * Calcoli la somma degli elementi della diagonale primaria
      * Calcoli la somma degli elementi della diagonale secondaria
      * Verifichi se M è simmetrica, i.e. M[i,j] = M[j,i]
      * Calcoli la trasposta di M
      * Verifichi se M e' un quadrato magico, cioè se:
         * La somma di ogni riga e' pari a K
         * La somma di ogni colonna e' pari a K
         * La somma delle diagonali primaria e secondaria e' pari a K
</font>

<font color=blue> 
*Lezioni 13-14: lunedi' 26 marzo 2012*
</font>

<font color=darkBlue>
*Esercizi svolti in aula:*
   * Risolvere col metodo del teorema principale le seguenti equazioni di ricorrenza:
      * T(n)=2 T(n/2)+&Theta;(n); T(1)=&Theta;(1)
      * T(n)=2 T(n/3)+&Theta;(n); T(1)=&Theta;(1)
      * T(n)=3 T(n/2)+&Theta;(n); T(1)=&Theta;(1)
   * Risolverne una a scelta col metodo iterativo.
   * Progettare una soluzione iterativa ed una ricorsiva al seguente problema:
      * trovare la somma del sottovettore di somma massima in un vettore di n interi (positivi e negativi). 

*Esercizi assegnati:*
   * Risolvere col metodo iterativo le restanti equazioni di ricorrenza sopra elencate.
   * Risolvere col metodo del teorema principale e col metodo iterativo le seguenti equazioni di ricorrenza:
      * T(n)=4 T(n/2)+&Theta;(n); T(1)=&Theta;(1)
      * T(n)=4 T(n/2)+&Theta;(n^2); T(1)=&Theta;(1)
      * T(n)=4 T(n/2)+&Theta;(n^3); T(1)=&Theta;(1)
   * Risolvere la seguente equazione di ricorrenza:
      * T(n)= T(n-1)+&Theta;(n); T(1)=&Theta;(1)
   * Valutare la complessita'  delle soluzioni iterativa e ricorsiva al problema di trovare la somma del sottovettore di somma massima in un vettore di n interi (positivi e negativi). 
</font>

<font color=blue> 
*Lezioni 15-16: martedì 27 marzo 2012*

Il problema dell'ordinamento (1)

   * Algoritmi semplici: insertion sort, selection sort e bubble sort, pseudocodici e complessità nel caso migliore e peggiore.
   * Teorema sulla limitazione inferiore per la complessità di un algoritmo per confronti.
 </font>

<font color=darkblue>
*Esercizi assegnati:*

   * scrivere una funzione che, dato un vettore, trovi il minimo e lo metta in prima posizione. Riscrivere il codice del selection sort in modo che chiami ripetutamente questa funzione.
   * scrivere lo pseudocodice di una funzione che determini se una sequenza arbitraria di n numeri contiene occorrenze ripetute dello stesso numero. Valutare la complessità.
   * dati n+1 coefficienti a_0, ..., a_n ed un reale y, scrivere lo pseudocodice di una funzione che calcoli il valore del polinomio P(x)=a_0 + a_1x+ ... +a_n x^n nel punto y. Scrivere un'altra funzione che risolva lo stesso problema che sfrutti la regola di Horner: P(x)=(...(a_n x + a_{n-1})x+ ... +a_1)x+a_0. Calcolare la complessità di entrambe le funzioni.
</font>

<font color=black> 
*Tutoraggio 1-2: mercoledì 28 marzo 2012*
   * Assistenza agli studenti per la compressione e l'invio delle soluzioni agli homework.
   * Assistenza agli studenti per la soluzione degli esercizi assegnati nelle lezioni ed esercitazioni precedenti.
 </font>

<font color=green> 
*Esercitazioni 7-8: Venerdì 30 marzo 2012*

   * Soluzione esercizio quadrato magico:  [[%ATTACHURL%/quadrato_magico.c][quadrato_magico.c]]

Funzioni: 
   * Motivazioni: modularità, riusabilità del codice
   * Dichiarazione
   * Variabili locali e valori di ritorno
   * Passaggio di parametri per valore
   * Esercizio: somma degli elementi di un vettore: [[%ATTACHURL%/sum_vect_iterative.c][sum_vect_iterative.c]]
</font>

<font color=darkgreen>
*Esercizi assegnati:*

Scrivere un programma che allochi una matrice quadrata M:NxN rappresentante i rapporti di conoscenza di un gruppo di N persone, tale che:
   * contenga 2 sulla diagonale principale, M[i,i] = 2 per i = 0,..,N-1
   * contenga 1 in posizione i,j se i conosce j, M[i,j] = 1 se i conosce e j, j ! = i
Il programma deve verificare se esiste un VIP nel gruppo, cioè se esiste un indice i t.c. i e' conosciuto da tutti e non conosce nessuno. Formalmente:
   * M[i,j] = 0 per i ! = j
   * M[j,i] = 1 per i ! = j

Notare che il problema può essere risolto in O(n).
   
</font>

<font color=blue> 
*Lezioni 17-18: lunedì 2 aprile 2012*
   * Il problema dell'ordinamento (2)
      * algoritmi efficienti: merge sort
 </font>

<font color=darkblue>
*Esercizi assegnati:*
   * scrivere lo pseudocodice di una funzione che determini se una sequenza arbitraria di n numeri contiene occorrenze ripetute dello stesso numero. Valutare la complessità, che dovrebbe essere &Theta;(n log n).
   * Nonostante il merge sort funzioni in tempo &Theta;(n log n), l'insertion sort è più veloce del merge sort per valori piccoli di n. Quindi ha senso usare insertion sort dentro il merge sort quando i sottoproblemi diventano sufficientemente piccoli. Si consideri una modifica del merge sort in cui il caso base diviene una porzione del vettore di lunghezza k, con k che deve essere determinato, la quale viene ordinata usando insertion sort. Le porzioni ordinate vengono poi combinate usando il meccanismo standard di fusione. Determinare il massimo valore di k come funzione di n per cui l'algoritmo modificato ha lo stesso tempo di esecuzione asintotico del merge sort.
 </font>

<font color=green> 
*Esercitazioni 9-10: Martedì 3 aprile 2012*

   * Prototipi di funzione: motivazioni e sintassi
   * Funzioni ricorsive:
      * Scrittura di una funzione ricorsiva: caso base e passo ricorsivo
      * Schema "generale" funzione ricorsiva
   * Esercizi sulle funzioni ricorsive:
      * Trovare il massimo di un vettore: [[%ATTACHURL%/max_vect_ric.c][max_vect_ric.c]]
      * Somma degli elementi di un vettore: [[%ATTACHURL%/sum_vect_ric.c][sum_vect_ric.c]]
      * Trovare il numero di occorrenze di un valore in un vettore: [[%ATTACHURL%/conta_occorrenze_ric.c][conta_occorrenze_ric.c]]
      * Verificare che un vettore sia palindromo:  [[%ATTACHURL%/palindromo_ric.c][palindromo_ric.c]]
 </font>

<font color=darkgreen>
*Esercizi assegnati:*
   * Dato un vettore di interi ed un intero k, verificare che la somma degli elementi del vettore sia pari a k.
   * Dato un vettore, verificare se esiste un elemento che si ripeta più di una volta.
   
</font>

<font color=black> 
*Tutoraggio 3-4: mercoledì 4 aprile 2012*
   * Assistenza agli studenti per la soluzione degli esercizi assegnati nelle lezioni ed esercitazioni precedenti.
 </font>

<font color=red> 
*Venerdì 6 aprile - martedì 10 aprile 2012: Vacanze di Pasqua*
 </font>

<font color=black> 
*Tutoraggio 5-6: mercoledì 11 aprile 2012*
   * Assistenza agli studenti per la soluzione degli esercizi assegnati nelle lezioni ed esercitazioni precedenti.
 </font>

<font color=green> 
*Esercitazioni 11-12: Venerdì 13 aprile 2012*

Esercizi sulla ricorsione:

   * Dato un vettore di interi ed un intero k, verificare che la somma degli elementi del vettore sia pari a k: [[%ATTACHURL%/check_sum_vect_ric.c][check_sum_vect_ric.c]]
   * Dato un vettore, verificare se esiste un elemento che si ripeta più di una volta: [[%ATTACHURL%/repeated_elem.c][repeated_elem.c]]

Esercizio sulle matrici:

   * Data una matrice quadrata M:NxN rappresentante i rapporti di conoscenza di un gruppo di N persone, tale che:<br>
    contenga 2 sulla diagonale principale, M[i,i] = 2 per i = 0,..,N-1<br>
    contenga 1 in posizione i,j se i conosce j, M[i,j] = 1 se i conosce e j, j ! = i<br>
    Il programma deve verificare se esiste un VIP nel gruppo, cioè se esiste un indice i t.c. i e' conosciuto da tutti e non conosce nessuno. Formalmente:<br>
      * M[i,j] = 0 per i ! = j
      * M[j,i] = 1 per i ! = j

   * Soluzione: [[%ATTACHURL%/vip_quadratico.c][vip_quadratico.c]]

Assegnazione homework 2.

 </font>

<font color=darkgreen>
*Esercizi assegnati:*
   * Date due matrici quadrate A:axa e B:bxb t.c. a>b. Dire se B e' una sottomatrice di A.
</font>

<font color=blue> 
*Lezioni 19-20: lunedì 16 aprile 2012*
   * Il problema dell'ordinamento (3)
      * algoritmi efficienti: quicksort (pseudocodice e complessità nei casi migliore, peggiore e medio)
 </font>

<font color=darkblue>
*Esercizi assegnati:*
   * Determinare la complessità del Quicksort se il vettore dato in input contiene n elementi uguali e se è già ordinato in senso decrescente (nell'ipotesi che non contenga elementi uguali).
 </font>

<font color=green> 
*Esercitazioni 13-14: Martedì 17 aprile 2012*

Esercizi sulla ricorsione:

   * Dati due vettori A e B di dimensione n verificare che siano uguali: [[%ATTACHURL%/equal_vect_ric.c][equal_vect_ric.c]]
   * Dato un vettore A di dimensione n ed un vettore B di dimensione m, verificare che B sia sottovettore di A: [[%ATTACHURL%/subvect_ric.c][subvect_ric.c]]

Esercizio sulle matrici:

   * Date due matrici quadrate A:axa e B:bxb t.c. a>b. Dire se B e' una sottomatrice di A: [[%ATTACHURL%/submatrix.c][submatrix.c]]

 </font>

<font color=black> 
*Tutoraggio 7-8: mercoledì 18 aprile 2012*
   * Assistenza agli studenti per la soluzione degli esercizi assegnati nelle lezioni ed esercitazioni precedenti.
 </font>

<font color=blue> 
*Lezioni 21-22: venerdì 20 aprile 2012*
   * Il problema dell'ordinamento (4)
      * Counting sort e relativa analisi della complessità.
   * Esercizi sulle equazioni di ricorrenza.
 </font>

<font color=darkblue>
*Esercizi assegnati:*
   * Scrivere lo pseudocodice di una funzione che determini se una data una sequenza arbitraria di n numeri compresi tar 1 e k, con k=O(n), contiene occorrenze ripetute dello stesso numero. Valutare la complessità, che dovrebbe essere O(n).
 </font>

<font color=red> 
*Lunedì 23 aprile - venerd' 27 aprile 2012: Sospensione della didattica per lo svolgimento delle prove in itinere.*
 </font>

</font>

<font color=green> 
*Esercitazioni 15-16: Venerdì 4 Maggio 2012*

Puntatori:
   * Definizione, dichiarazione, inizializzazione, assegnamento.
   * Operatori & e *
   * Allocazione dinamica della memoria: funzioni malloc e free
   * Esempio di uso dei puntatori: [[%ATTACHURL%/es_puntatori.c][es_puntatori.c]]

Vettori e matrici:
   * Allocazione e deallocazione dinamica di vettori: [[%ATTACHURL%/alloc_dyn_vect.c][alloc_dyn_vect.c]]
   * Allocazione e deallocazione dinamica di matrici: [[%ATTACHURL%/alloc_dyn_matrix.c][alloc_dyn_matrix.c]]
 </font>

<font color=blue> 
*Lezioni 23-24: lunedì 7 maggio 2012*
   * Il problema dell'ordinamento (5)
      * algoritmi efficienti: heapsort (struttura dati heap, pseudocodice e complessità)
 </font>


<font color=darkblue>
*Esercizi assegnati:*
   * Scrivere lo pseudocodice di Heapsort nel caso in cui, come struttura dati, si usi un heap minimo (cioè tale che A[i]>=A[parent(i)]), che mantiene il minimo nella radice.
   * Scrivere lo pseudocodice di una funzione che, dato un heap, ritorni l'elemento con chiave minima. Valutare la complessità.
 </font>

<font color=blue>
*Lezioni 25-26: martedì 8 maggio 2012*

Strutture dati fondamentali (1)

   * insiemi dinamici ed operazioni su di essi
   * implementazione di un insieme dinamico su un vettore non ordinato
   * implementazione di un insieme dinamico su un vettore ordinato
   * la struttura dati lista
   * operazioni elementari su liste: scorrimento, ricerca, inserimento in testa
   * realizzazione della struttura dati lista tramite vettore


<font color=green> 
*Esercitazioni 17-18: Venerdì 11 Maggio 2012*

Strutture dati:
   * Definizione, dichiarazione.
   * Accesso ai campi di strutture allocate staticamente 
   * Confronti tra strutture
   * Definizione di alias per i tipi, istruzione typedef
   * Typedef e strutture
   * Allocazione dinamica di strutture
   * Accesso ai campi di strutture allocate dinamicamente

Passaggio di parametri per riferimento a funzioni in C:
   * Motivazioni
   * Ottenere il passaggio per riferimento in C. Esempio:  [[%ATTACHURL%/read_point.c][read_point.c]]
   * Riflessioni sui vettori passati a funzioni
  </font>


<font color=blue>
*Lezioni 27-28: lunedì 14 maggio 2012*

Strutture dati fondamentali (2)

   * la struttura dati lista doppiamente puntata
   * eliminazione di un elemento dalla lista doppiamente puntata
   * cancellazione logica e cancellazione fisica
   * la lista circolare
   * la struttura dati coda
   * le operazioni enqueue e dequeue

</font>

<font color=darkblue>
*Esercizi assegnati:*
   * Scrivere lo pseudocodice, in versione iterativa, dell'eliminazione di un elemento (di cui si fornisce il puntatore) da una lista semplice.
   * Scrivere lo pseudocodice, in versione ricorsiva, dell'eliminazione di un elemento (di cui si fornisce il puntatore) da una lista semplice.
   * Scrivere lo pseudocodice, in versione iterativa, di una funzione che restituisce il puntatore al massimo elemento contenuto in una lista semplice.
   * Scrivere lo pseudocodice, in versione ricorsiva, di una funzione che restituisce il puntatore al massimo elemento contenuto in una lista semplice.

 </font>

<font color=blue>
*Lezioni 29-30: martedì 15 maggio 2012*

Strutture dati fondamentali (3)

   * la struttura dati pila
   * le operazioni push e pop
   * la struttura dati albero
      * definizione come grafo connesso e aciclico
      * alberi radicati, alberi ordinati ed alberi binari
      * limitazioni sul numero di nodi, numero di foglie ed altezza negli alberi binari
</font>

<font color=darkblue>
*Esercizi assegnati:*
   * Scrivere lo pseudocodice, in versione iterativa, di una funzione che restituisce il puntatore al predecessore di un elemento (di cui si conosce il puntatore) contenuto in una lista semplice nella quale tutti gli elementi sono diversi fra loro. Nota: il predecessore di un elemento è quello che lo precederebbe se gli elementi fossero ordinati.
   * Scrivere lo pseudocodice di una funzione che, dato un puntatore che indica la testa di una lista contenente chiavi intere, la scomponga in due liste, una contenente gli elementi con chiave pari e una contenente gli elementi con chiave dispari
   * Scrivere lo pseudocodice di una funzione che, dati due puntatori a due liste contenenti ciascuna chiavi intere ordinate, produca una terza lista contenente tutte le chiavi ordinate

</font>

<font color=green> 
*Esercitazioni 19-20: Venerdì 18 Maggio 2012*

Liste:
   * Definizione
   * Dichiarazione struttura dati in C
   * Definizione ricorsiva
   * Code
      * Inserimento: Enqueue
      * Estrazione: Dequeue
      * Implementazione: [[%ATTACHURL%/coda.c][coda.c]]
   * Pile
      * Inserimento: Push
      * Estrazione: Pop
      * Implementazione: [[%ATTACHURL%/pila.c][pila.c]]

Esercizi sulle liste:
   * Stampa elementi: [[%ATTACHURL%/stampa_lista.c][stampa_lista.c]]
   * Somma elementi: [[%ATTACHURL%/sum_list.c][sum_list.c]]
 </font>

<font color=green> 
*Esercitazioni 21-22: Lunedì 21 Maggio 2012*

Esercizi sulle liste:
   * Restituire il puntatore all'elemento con valore massimo: [[%ATTACHURL%/max_list.c][max_list.c]]
   * Scomporre una lista L in due liste, L_p ed L_d, contenenti rispettivamenti gli elementi di L pari e dipsari (senza creare copie degli elementi): [[%ATTACHURL%/scomponi_lista.c][scomponi_lista.c]]
   * Data una lista p ed un elemento x di p, trovare il predecessore di x in p: [[%ATTACHURL%/predecessore.c][predecessore.c]]
 </font>



<font color=blue>
*Lezioni 31-32: martedì 22 maggio 2012*

Strutture dati fondamentali (4)

   * la struttura dati albero
      * memorizzazione di alberi
         * rappresentazione posizionale
         * memorizzazione tramite record e puntatori
         * vettore dei padri
         * raffronto delle strutture in termini di spazio e di complessità delle operazioni di ricerca del padre di un nodo e di calcolo del numero dei figli di un nodo
      * visita di alberi: pre-ordine, in-ordine e post-ordine
      * complessità delle visite tramite equazione di ricorrenza  
      * Esercizio: calcolo del numero di nodi contenuti in un albero binario 
      * Esercizio: calcolo dell'altezza di un albero binario 
</font>

<font color=darkblue>
*Esercizi assegnati:*
   * Scivere lo pseudocodice di una funzione che, dato il puntatore ad un albero binario, calcoli la somma dei valori delle chiavi contenute nell'albero
   * Scivere lo pseudocodice di una funzione che, dato il puntatore ad un albero binario, stampi la sua rappresentazione parentetica
   * Scivere lo pseudocodice di una funzione che, dato il puntatore ad un albero binario, calcoli il numero dei nodi a distanza k dalla radice. La complessità dovrebbe essere dell'ordine del numero dei nodi a distanza minore o uguale di k dalla radice. 
</font>

<font color=blue>
*Lezioni 33-34: venerdì 25 maggio 2012*

Dizionari (1)

   * definizione di dizionario e problematiche associate
   * tabelle ad indirizzamento diretto
   * tabelle hash
   * il problema delle collisioni
   * soluzione al problema delle collisioni tramite liste di trabocco
   * soluzione al problema delle collisioni tramite indirizzamento aperto
      * scansione lineare
      * scansione quadratica
      * hashing doppio
      * analisi delle prestazioni nel caso medio
</font>

<font color=blue>
*Lezioni 35-36: lunedì 28 maggio 2012*

Dizionari (2)

   * alberi binari di ricerca
      * definizione
      * algoritmo di ricerca e sua complessita'
      * algoritmi di ricerca del massimo, minimo, successore e predecessore e loro complessita'
      * algoritmo di inserimento e sua complessita'
   * Esercizio svolto in classe: fusione di due liste ordinate
</font>

<font color=blue>
*Lezioni 37-38: martedì 29 maggio 2012*

Dizionari (3)

   * alberi binari di ricerca
      * algoritmo di cancellazione e sua complessità
      * la problematica del bilanciamento per la limitazione della complessità
      * alberi red-black

Grafi (1)

   * definizione di grafo, grafo diretto, grafo pesato
   * definizine di passeggiata, cammino, cammino semplice
   * definizine di circuito e ciclo
   * relazione di raggiungibilità e sue caratteristiche
   * definizione di componente connessa

</font>

<font color=green> 
*Esercitazioni 23-24: Venerdì 1 Giugno 2012*

Alberi binari:
   * Generalità
   * Definizione struttura dati in C
   * Definizione ricorsiva di albero binario

Progettazione di funzioni ricorsive su strutture dati dinamiche:
   * Funzioni che non modificano la struttura dati (es. somma chiavi degli elementi di una lista, altezza di un albero, ...).
      * Esempio, massimo degli elementi in una lista: [[%ATTACHURL%/max_list_int.c][max_list_int.c]]
   * Funzioni che modificano la struttura dati (inserimento, cancellazione, ecc.).
      * Esempio, inserimento ordinato ricorsivo in una lista: [[%ATTACHURL%/insert_sorted_list.c][insert_sorted_list.c]]


Esercizi sugli alberi binari:
   * Inserimento su albero binario di ricerca
   * Rapresentazione parentetica di un albero
   * Somma delle chiavi del cammino radice-foglia avente somma delle chiavi massima
   * Codice degli esercizi sopra elencati: [[%ATTACHURL%/insert_bin_tree.c][insert_bin_tree.c]]

 </font>

<font color=blue>
*Lezioni 39-40: lunedì 4 giugno 2012*

Grafi (2)

   * rappresentazioni in memoria
      * liste di adiacenza
      * matrice di adiacenza
      * matrice di incidenza
      * lista di archi
      * confronto della complessita' spaziale e temporale per alcune operazioni elementari

   * visita in ampiezza (BFS)
      * definizione di albero ricoprente
      * pseudocodice della visita in ampiezza e sua complessità 
      * proprietà degli archi non dell'albero 
      * proprieta' della distanza dalla radice

</font>

<font color=blue>
*Lezioni 41-42: martedì 5 giugno 2012*

Grafi (3)

   * visita in profondità DFS)
      * pseudocodice della visita in profondità e sua complessità 
      * proprietà degli archi non dell'albero 
      * relazione fra lunghezza dei cammini e numero di archi del grafo

   * Esercizio svolto in classe: conteggio del numero di nodi a distanza k dalla radice in un albero binario

</font>

<font color=green> 
*Esercitazioni 25-26: Mercoledì 6 Giugno 2012*

Esercizi su liste:
   * Data una lista ed un intero x, rimuovere dalla lista gli elementi con chiave < x
   * Data una lista, rimuovere gli elementi in posizione pari
   * Soluzioni esercizi precedenti: [[%ATTACHURL%/remove_list.c][remove_list.c]]

Esercizi su alberi binari:
   * Dato un albero, restituire l'albero opposto (albero opposto = albero in cui per ogni nodo il figlio sx e quello dx sono scambiati)
   * Dato un albero e due interi a e b, con a < b, stampare tutte le chiavi comprese nell'intervallo [a,b]
   * Soluzioni esercizi precedenti: [[%ATTACHURL%/es_alberi.c][es_alberi.c]]
 </font>



-- Users.GiancarloBongiovanni - 05 Apr 2016