DiarioLezioniOld < Intro

Tags: view all tags
---++Diario delle lezioni (Introduzione agli Algoritmi, secondo canale, A.A. 2011-2012)

<font color="#AF0F0F"><b>Lunedì 5 Marzo</b></font> - Introduzione al corso. Administrivia. Come si misura il tempo di esecuzione? Analisi del numero di linee di codice eseguite da semplici programmi iterativi con cicli:

<table border="0">
   <tr>
      <td><PRE>
     Algoritmo 1 (int n)
      i=1
      while (i<=n) do i++
     </PRE></td>
     
     <td><PRE>
     Algoritmo 2 (int n) 
      i=0
      while (i<=n) do i=i+3
     </PRE></td>
      
     <td><PRE>
     Algoritmo 3 (int n) 
      i=1
      while (i<=n) do i=i+i
     </PRE></td>
  </tr>
</table> 

<font color="#AF0F0F"><b>Giovedì  8 Marzo</b></font> - Ancora analisi di programmi iterativi: cicli nidificati, serie aritmetica (con dimostrazione), cambiamento di variabile. Introduzione alla notazione asintotica O ed esempi.

<table border="0">
   <tr>
      <td><PRE>
     Algoritmo Count0 (int n) -> int 
     count=0
     i=1
     while (i<=n) do
         for j=1 to n
             count++
         i++
     return count
     </PRE></td>
     
     <td><PRE>
     Algoritmo Count1 (int n) -> int 
     count=0
     i=1
     while (i<=n) do
         for j=1 to i
             count++
         i++
     return count
     </PRE></td>

     <td><PRE>
     Algoritmo Count2 (int n) -> int 
     count=0
     while (n>=0) do
         for j=1 to n
             count++
         n--
     return count
     </PRE></td>
</table> 

<BLOCKQUOTE>
<B>Esercizi di riepilogo (A).</B> Quante volte viene stampato "Hello world" da ciascuno dei seguenti programmi?
<table border="0">
   <tr>
      <td><PRE>
     i=1
     if (n>5) i=n-5;
     while (i<=n) do 
       print "Hello world"
       i=i+1
     </PRE></td>
     
      <td><PRE>
     i=27
     while (i<=n) do 
       print "Hello world"
       i=i*3
     </PRE></td>
     
     <td><PRE>
     for i=1 to n
       for j=1 to i
         for k=1 to j
           print "Hello world"
     </PRE></td>

     <td><PRE>
     for i=1 to n
       for j=1 to i
         print "Hello world"
       for k=5 to 2i
         print "Hello world"
     </PRE></td>    

  </tr>
  <tr>
     <td align="center"><b>(A1)</b></td>
     <td align="center"><b>(A2)</b></td>    
     <td align="center"><b>(A3)</b></td>    
     <td align="center"><b>(A4)</b></td>    
  </tr>
</table>

*(A5)* Esercizio 2 della prova intermedia del 28 aprile 2011, traccia 1. Nel punto 2b, rimpiazzate &Theta;(_n<sup>2</sup>_) con _n<sup>2</sup>_.
</BLOCKQUOTE> 

<font color="#AF0F0F"><b>Lunedì  12 Marzo</b></font> - Operazione dominante. Ancora su programmi iterativi con cicli nidificati:
<table border="0">
   <tr>
     <td><PRE>
     Algoritmo count3 (int n) -> int 
     count=0
     x = n
     while (x>=1) do
         for j=1 to n
             count++
         x=x/2
     return count
     </PRE></td>
     
     <td><PRE>
     Algoritmo count4 (int n) -> int 
     count=0
     x = n
     while (x>=1) do
         for j=1 to x
             count++
         x=x/2
     return count
     </PRE></td>
  </tr>
</table>
Serie geometrica. Introduzione all'analisi di algoritmi ricorsivi: stack dei record di attivazione, albero delle chiamate ricorsive. Il problema dei conigli di Fibonacci: l'albero dei conigli, _F<sub>n</sub>=F<sub>n-1</sub>+F<sub>n-2</sub>_, sezione aurea, crescita esponenziale. 

<font color="#AF0F0F"><b>Giovedì  15 Marzo</b></font> - Analisi dell'algoritmo ricorsivo per il calcolo di _F<sub>n</sub>_: calcolo del numero di linee di codice eseguite tramite analisi dell'albero della ricorsione, proprietà dell'albero della ricorsione (numero di foglie, numero di nodi interni), impostazione equazione di ricorrenza. Due algoritmi iterativi con tempo lineare, analisi della quantità di memoria richiesta. Soluzione degli esercizi A3 ed A5.

<BLOCKQUOTE>
<B>Esercizi di riepilogo (B).</B> 

_Esercizio B1._ Disegnate gli alberi delle chiamate ricorsive corrispondenti alle esecuzioni degli algoritmi algo1 e algo2 assumendo che n=10:
<table border="0">
   <tr>
      <td><PRE>
     algo1(intero n) -> intero
       if (n<=7) return n;
       else
          sum=0;
          for i=1 to n-1
             sum = sum + algo1(i)
       return sum
     </PRE></td>
     
     <td><PRE>
     algo2(intero n) -> intero
       if (n<=2) return 5;
       else
          return 8+algo2(n-2)
     </PRE></td>
  </tr>
  <tr>
     <td align="center">(1)</td>
     <td align="center">(2)</td>    
  </tr>
</table>

_Esercizio B2._ Sia Fib un array di n interi, inizializzati tutti a 0. Progettate un algoritmo che memorizzi in Fib[i] l'i-esimo numero di Fibonacci F<sub>i</sub>, per ogni i in [1,n]. L'algoritmo, a partire dal calcolo di F<sub>n</sub>, deve operare ricorsivamente secondo la seguente strategia: a) se i=1 o i=2, pone Fib[i]=1 ed esce; b) se Fib[i-1]=0, calcola Fib[i-1] ricorsivamente; c) se Fib[i-2]=0, calcola Fib[i-2] ricorsivamente; d) memorizza in Fib[i] la somma Fib[i-1]+Fib[i-2] ed esce.
   * Date lo pseudocodice dell'algoritmo
   * Disegnate l'albero della ricorsione per il calcolo di F<sub>6</sub>
   * Analizzate il tempo di esecuzione dell'algoritmo
   * Ripetete i punti precedenti assumendo che i passi b) e c) siano invertiti
<!--   * [[[%ATTACHURL%/FibonacciWithMemoization.pdf][Soluzione]]] -->
     
_Esercizio B3._ Il Professor Bifolcacci sostiene di saper sfruttare la relazione di ricorrenza che definisce i numeri di Fibonacci per ottenere un algoritmo ricorsivo con tempo di esecuzione subesponenziale. In particolare, l'algoritmo del Professor Bifolcacci  prima calcola ricorsivamente F<sub>n-2</sub> e F<sub>n-3</sub>, e poi restituisce F<sub>n</sub>=2F<sub>n-2</sub>+F<sub>n-3</sub>. 
   * Dimostrate che l'algoritmo è corretto
   * Impostate una relazione di ricorrenza per il tempo di esecuzione
   * [Diff] Dimostrate che il professore ha commesso un errore: il tempo di esecuzione è ancora esponenziale! E' sufficiente dare una minorazione al tempo di esecuzione, ovvero far vedere che il tempo di esecuzione _T(n)&ge;g(n)_, dove _g(n)_ è una opportuna funzione con crescita esponenziale.

_Esercizio B4._ Considerate il famoso gioco delle [[http://en.wikipedia.org/wiki/Tower_of_Hanoi][torri di Hanoi]]. 
   * Progettate un algoritmo ricorsivo che risolva il problema con n dischi e 3 torri
   * Impostate una relazione di ricorrenza per il numero di spostamenti di dischi eseguiti dall'algoritmo
   * Disegnate l'albero della ricorsione per n=5.
   * [Diff] Analizzando l'albero, dimostrate che il numero di spostamenti effettuati è _2<sup>n</sup>-1_. Suggerimento: dopo aver capito come etichettare cascun nodo, calcolate il numero di nodi dell'albero sommando i numeri di nodi che si trovano su ciascun livello (dovete ottenere una serie geometrica).

</BLOCKQUOTE> 

<font color="#AF0F0F"><b>Lunedì  19 Marzo</b></font> - Notazione asintotica &Omega; e &Theta;. Dimostrazione della seguente proprietà: _f(n)=&Theta;(g(n))_ se e solo se _f(n)=O(g(n))_ e _f(n)=&Omega;(g(n))_. Un algoritmo logaritmico per il calcolo di _F<sub>n</sub>_: numeri di Fibonacci e potenze di matrice. Esponenziazione di interi tramite il metodo dei quadrati ripetuti: algoritmo per il calcolo della n-esima potenza di un numero in tempo _O(log n)_, analisi dell'albero della ricorsione, impostazione dell'equazione di ricorrenza e soluzione per iterazione.

<font color="#AF0F0F"><b>Giovedì  22 Marzo</b></font> - Ancora sulla notazione asintotica. Dualità di _O_ e _&Omega;_. Dimostrazione della seguente proprietà: ogni polinomio di grado _d&ge;0_ il cui termine di grado massimo abbia coefficiente positivo è in _&Theta;(n<sup>d</sup>)_. Metodo analitico. Soluzione degli esercizi A4, B1(1), B2, e dell'esercizio 3 della prova intermedia del 29/4/2010.

<font color="#AF0F0F"><b>Lunedì  26 Marzo</b></font> - Esponenziazione di matrici tramite il metodo dei quadrati ripetuti: algoritmo per il calcolo di _F<sub>n</sub>_ in tempo _O(log n)_. Come analizzare l'occupazione di memoria di algoritmi ricorsivi. Analisi del tempo di esecuzione in funzione della dimensione dell'input.  Definizione di tempo di esecuzione nel caso migliore, nel caso peggiore e nel caso medio. Analisi dell'algoritmo di ricerca sequenziale nei tre casi. Analisi del tempo di esecuzione dell'algoritmo di ricerca binaria (implementazione iterativa) nel caso peggiore.

<BLOCKQUOTE>
<B>Esercizi di riepilogo (C).</B> 

_Esercizio C1._ Proporre ed analizzare un algoritmo iterativo ed un algoritmo ricorsivo per risolvere il seguente problema: dati due vettori A e B, entrambi di dimensione n, calcolare il prodotto scalare A x B. Il prodotto A x B è definito come la somma dei prodotti A[i] x B[i], dove A[i] è il valore dell'i-esima coordinata di A e B[i] è il valore dell'i-esima coordinata di B. Analizzare il tempo di esecuzione degli algoritmi proposti.

_Esercizio C2._ Proporre ed analizzare un algoritmo che, date due matrici quadrate A e B, entrambe di lato n, calcoli la matrice prodotto A x B. Qual è il tempo di esecuzione dell'algoritmo proposto in funzione di n? 

_Altri esercizi._ Dal libro di testo: 
   * esercizi 2.1, 2.2, 2.3, 2.9
   * problemi 2.2, 2.4, 2.9, 2.10 
Da prove d'esame: 
   * esercizio 2 della prova intermedia del 29/4/2010
   * esercizio 2 dell'appello del 24/6/2010
</BLOCKQUOTE> 

<font color="#AF0F0F"><b>Giovedì  29 Marzo</b></font> - Ricerca binaria con algoritmo ricorsivo con suddivisione bilanciata e sbilanciata del vettore. Serie geometrica.
Soluzione degli esercizi B3 e B4.

<font color="#AF0F0F"><b>Lunedì  2 Aprile</b></font> - Come ordinare 1GB di dati... in meno di cento anni: il mergesort (implementazione ricorsiva ed analisi).

<BLOCKQUOTE>
<B>Esercizi di preparazione all'esonero (D).</B> Buon lavoro, e buona Pasqua!

_Esercizio D1._ Nella implementazione del mergesort proposta sul libro di testo, rimpiazzate la scelta dell'indice m come segue: m=(2i+f-2)/3. Con tale scelta, l'array da ordinare viene partizionato in due sottoarray, il secondo dei quali è grande  il doppio del primo. Disegnate l'albero della ricorsione ed impostate (senza risolverla, per ora) l'equazione di ricorrenza che descrive il numero di confronti eseguiti dall'algoritmo nel caso peggiore. Per semplificare i calcoli, potete assumere che la dimensione n dell'array da ordinare sia una potenza di 3.
     
_Esercizio D2._ Nella implementazione del mergesort proposta sul libro di testo, rimpiazzate la scelta dell'indice m come segue: m=min { (i+f)/2, i+3 }. Con tale scelta, se c'e' un numero di  elementi sufficiente, l'array da ordinare viene partizionato in due sottoarray, il primo dei quali ha dimensione 4. Disegnate l'albero della ricorsione ed impostate l'equazione di ricorrenza che descrive il numero di confronti eseguiti dall'algoritmo nel caso peggiore. Risolvete per iterazione l'equazione di ricorrenza impostata. Per semplificare i calcoli, osservate che se l'input ha dimensione costante, il numero di passi eseguito dall'algoritmo è O(1).

_Esercizio D3._ Quanti confronti tra elementi sono eseguiti nel caso migliore dall'algoritmo merge per fondere due sequenze ordinate di lunghezza n1 e n2? Si può assumere senza perdita di generalità che n1<=n2. Qual è il tempo di esecuzione dell'algoritmo nel caso migliore?

_Esercizi da prove d'esame._ Esercizio 2 dell'appello del 17 giugno 2008; esercizio 2 degli appelli del 22 gennaio 2009; esercizi 1 e 2 degli appelli del 5 febbraio 2009 e 9 settembre 2008; esercizi 2 e 3 della prova intermedia del 27 novembre 2008; 
esercizio 2 della prova intermedia del 14 novembre 2007; esercizi 1, 3 e 4 della prova intermedia del 23 aprile 2009; tutti gli esercizi della prova intermedia del 29 aprile 2010 (nell'esercizio 4 omettere il punto 1);  esercizi 1.1 e 1.2 dell'appello del 14 luglio 2009; esercizio 3 dell'appello del 15 settembre 2009; esercizio 2 dell'appello del 2 marzo 2010; esercizio 1 dell'appello del 21 luglio 2010; esercizi 2 e 3 dell'appello del 6 luglio 2009; esercizio 3 dell'appello del 10 settembre 2009.

</BLOCKQUOTE>


<font color="#AF0F0F"><b>Giovedì  5 Aprile</b></font> - vacanze di Pasqua

<font color="#AF0F0F"><b>Lunedì  9 Aprile</b></font> - vacanze di Pasqua

<font color="#AF0F0F"><b>Giovedì  12 Aprile</b></font> - Bubble Sort e Insertion Sort. Soluzione problema 2.2 ed esercizio 2 della prova intermedia del 5/02/2009.

<font color="#AF0F0F"><b>Lunedì  16 Aprile</b></font> - Quicksort: partizionamento in loco, analisi nel caso peggiore, intuizione nel caso medio. Alberi della ricorsione bilanciati e non: analisi di equazioni di ricorrenza della forma _T(n) = T(n/k) + T(n(k-1)/k) + &Theta;(n)_. Soluzione esercizi D1 e D2.

<font color="#AF0F0F"><b>Giovedì  19 Aprile</b></font> - Esercizi di preparazione all'esonero:
   * Problema 2.9 del libro di testo
   * Esercizio 1 prova intermedia del 23 aprile 2009
   * Esercizio 3 prova intermedia del 23 aprile 2009
   * Problema 3 appello del 6 luglio 2009
   * Esercizio 1 appello del 20 settembre 2010

<font color="#AF0F0F"><b>Lunedì  23 Aprile</b></font> - interruzione didattica per prove intermedie

<font color="#AF0F0F"><b>Giovedì  26 Aprile</b></font> - *prova intermedia*

<font color="#AF0F0F"><b>Lunedì  30 Aprile</b></font> - didattica sospesa per il ponte del 1 maggio (come da delibera del Consiglio di Area Didattica)

<font color="#AF0F0F"><b>Giovedì  3 Maggio</b></font> - Selection sort, integer sort e correzione della prova intermedia

<font color="#AF0F0F"><b>Lunedì  7 Maggio</b></font> - Heap binari: definizioni, calcolo dell'altezza, procedura fixheap e cancellazione del massimo. Rappresentazione tramite vettore posizionale, heapsort, ordinamento in loco.

<font color="#AF0F0F"><b>Giovedì  10 Maggio</b></font> - Costruzione ricorsiva di un heap e soluzione dell'equazione di ricorrenza per sostituzione. Suggerimenti e tranelli nell'uso del metodo di sostituzione. Svolgimento del problema 4.3 del libro di testo: inserimento di un nuovo elemento in un heap. Svolgimento del problema 4.11 e primi esempi di delimitazioni inferiori (lower bound).

<BLOCKQUOTE>
<B>Esercizi di riepilogo (E).</B> 

_Dal libro di testo_: 
   * esercizi 4.3, 4.4, 4.5
   * problemi 4.4, 4.5, 4.8, 4.10

_Prova d'esame del 21 luglio 2010:_ esercizio 3

_Prova d'esame del 24 giugno 2010:_ esercizio 3

_Prova d'esame del 2 marzo 2010:_ esercizio 1

_Prova d'esame del 15 settembre 2009:_ esercizi 1 e 2

</BLOCKQUOTE> 

<font color="#AF0F0F"><b>Lunedì  14 Maggio</b></font> - Alberi di decisione. Lower bound per il problema dell'ordinamento basato su confronti.

<font color="#AF0F0F"><b>Giovedì  17 Maggio</b></font> - Rappresentazioni di alberi mediante un strutture indicizzate (vettore padri e vettore posizionale) e mediante un strutture collegate (puntatoria figlio sinistro e destro, liste di figli, primo-figlio fratello successivo). Visite di alberi: visita generica, frangia, visita in ampiezza (con code), visita in profondità (con pile), implementazione ricorsiva della visita in profondità di alberi binari (preorder, inorder, postorder). Esercizi: problema 3.3 del libro di testo, variante del problema 3.7.

<font color="#AF0F0F"><b>Lunedì  21 Maggio</b></font> - Il tipo di dato astratto dizionario. Implementazioni banali mediante liste ed array ordinati e non. Alberi binari di ricerca: proprietà, operazioni search, insert e delete (con calcolo del predecessore). Analisi dei tempi di esecuzione in funzione dell'altezza _h_ dell'albero. 

<BLOCKQUOTE>
<B>Esercizi di riepilogo (F).</B> 

_Dal libro di testo_: 
   * esercizi 4.13, 4.14, 3.4, 3.5, 6.1, 6.10
   * problemi 3.6, 3.7, 3.8, 6.1

_Prova d'esame del 20 giugno 2011:_ esercizio 4

_Prova d'esame del 15 novembre 2011:_ esercizi 2 e 3

_Prova d'esame del 2 febbraio 2011:_ esercizio 3

_Prova d'esame del 21 luglio 2010:_ esercizi 3 e 4

_Prova d'esame del 2 marzo 2010:_ esercizio 3

_Prova d'esame del 14 luglio 2009:_ esercizio 2.1

_Prova d'esame del 23 giugno 2009:_ esercizio 2 della parte 1, esercizi 1 e 2 della parte 2

</BLOCKQUOTE> 

<font color="#AF0F0F"><b>Giovedì  24 Maggio</b></font> - Esercizi 3 e 4 della prova d'esame del 21 luglio 2010.
Esercizio 3 della prova d'esame del 2 marzo 2010.  Esercizio 2 parte 1 della prova d'esame del 23 giugno 2009.  Esercizio 2 della prova d'esame del 15 novembre 2011.

<font color="#AF0F0F"><b>Lunedì  28 Maggio</b></font> - Alberi AVL. Bilanciamento in altezza. Dimostrazione del fatto che l'altezza è logaritmica tramite alberi di Fibonacci. Operazione di inserimento. Rotazione di base e classificazione delle rotazioni: SS, DD, SD e DS.

<font color="#AF0F0F"><b>Giovedì  31 Maggio</b></font> - Dimostrazione della seguente proprietà: nel caso di inserimenti, le rotazioni ribilanciano l'albero localmente ed una sola rotazione è sufficiente. Cancellazione. Sottoalbero fonte dello sbilanciamento non univoco. Rotazioni a cascata. Svolgimento di esercizi: problemi 6.4 e 6.5 del libro, ricerca del quarto minimo in un min-heap, creazione di un albero di ricerca a partire da tre vettori ordinati in tempo _&Theta;(n)_.

<font color="#AF0F0F"><b>Lunedì  4 Giugno</b></font> - Esercizi di preparazione all'esame.

<font color="#AF0F0F"><b>Giovedì  7 Giugno</b></font> - Esercizi di preparazione all'esame.