DiarioLezioni1011 < Intro

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


<!--
<font color="#AF0F0F"><b>Lunedì 14 Marzo</b></font> - Introduzione al corso. Administrivia. Analisi del numero di linee di codice mandate in esecuzione da semplici programmi iterativi con cicli e cicli nidificati (serie aritmetica):
<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>

      <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>
</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>
  </tr>
  <tr>
     <td align="center">(1)</td>
     <td align="center">(2)</td>    
     <td align="center">(3)</td>    
  </tr>
</table>
</BLOCKQUOTE>


<font color="#AF0F0F"><b>Giovedì 17 Marzo</b></font> - lezione annullata causa festa nazionale

<font color="#AF0F0F"><b>Lunedì 21 Marzo</b></font> - Operazione dominante. Analisi del numero di linee di codice mandate in esecuzione da 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. Notazione asintotica: introduzione alla notazione O, &Omega;, &Theta;. Definizioni ed esempi.

<BLOCKQUOTE>
<B>Esercizi di riepilogo (B).</B> Quante volte viene stampato "Hello world" dai seguenti programmi?
<table border="0">
   <tr>
     <td><PRE>
     while (n>=1) do
       j=0
       while (j<=n) do 
         print "Hello world"
         j=j+4
       n=n/4
     </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">(1)</td>
     <td align="center">(2)</td>    
  </tr>
</table>
[[[%ATTACHURL%/esercizi_riepilogo_01.pdf][Soluzioni]]]
</BLOCKQUOTE>

<font color="#AF0F0F"><b>Giovedì 24 Marzo</b></font> - Esercizi su notazione asintotica. Dimostrazione che ogni polinomio in _n_ di grado _d_ è in O(_n<sup>d</sup>_). Risoluzione dell'esercizio (3) del 14 Marzo.

<BLOCKQUOTE>
<B>Esercizio.</B> Dimostrare che ogni polinomio in _n_ di grado _d_ è in &Omega;(_n<sup>d</sup>_) assumendo che il coefficiente del termine di grado massimo sia a<sub>0</sub> > 0.
</BLOCKQUOTE>

<font color="#AF0F0F"><b>Lunedì 28 Marzo</b></font> - Introduzione all'analisi di algoritmi ricorsivi. I conigli di Fibonacci. Albero delle chiamate ricorsive, equazioni di ricorrenza. Analisi algoritmo ricorsivo per il calcolo dei numeri di Fibonacci. Dimostrazione per induzione delle seguenti proprietà: (1) il numero di foglie dell'albero della ricorsione T<sub>n</sub> è F<sub>n</sub>; (2) sia T un albero in cui ogni nodo interno ha grado 2: il numero di nodi interni di T è pari al numero di foglie -1.

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

_Esercizio C1._ Disegnare 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 C2._ Sia Fib un array di n interi, inizializzati tutti a 0. Progettare 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.
   * Dare lo pseudocodice dell'algoritmo
   * Disegnare l'albero della ricorsione per il calcolo di F<sub>6</sub>
   * Analizzare il tempo di esecuzione dell'algoritmo
   * Ripetere i punti precedenti assumendo che i passi b) e c) siano invertiti
   * [[[%ATTACHURL%/FibonacciWithMemoization.pdf][Soluzione]]]
     
_Esercizio C3._ 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>. 
   * Dimostrare che l'algoritmo è corretto
   * Impostare una relazione di ricorrenza per il tempo di esecuzione
   * Dimostrare 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 è Omega(g(n)), dove g(n) è una opportuna funzione con crescita esponenziale.
</BLOCKQUOTE>

<font color="#AF0F0F"><b>Giovedì 31 Marzo</b></font> - Notazione asintotica: log<sub>a</sub>(_n_) = &Theta;(log<sub>b</sub> _n_).
Metodo Analitico: studiamo il limite per n &rarr; &infin; del rapporto tra due funzioni per capire quale delle due domina l&#8217;altra (O o &Omega;) o se sono asintoticamente equivalenti (&Theta;).
Dimostrazione che ogni polinomio in _n_ di grado _d_ è in &Theta;(_n<sup>d</sup>_) con il metodo analitico.
Dimostrazione che, per ogni d > 0 e a > 1, _n<sup>d</sup>_ = O(_a<sup>n</sup>_) e _a<sup>n</sup>_ = &Omega;( _n<sup>d</sup>_)  studiando il limite con il metodo del rapporto.
Dimostrazione che, per ogni d > 0, log _n_ = O(_n<sup>d</sup>_) e _n<sup>d</sup>_ = &Omega;(log _n_) utilizzando sostituzione di variabili.

Calcolo del numero di spostamenti richiesti per risolvere la _torre di Hanoi_ con _n_ dischi (Esercizio 2 dell&#8217;appello del 24 giugno 2010, punto 1) analizzando l'albero della ricorsione. Data la funzione ricorsiva definita di seguito, la chiamata iniziale =Hanoi(n, A, C, B)= richiederà S(_n_) = &Theta;(2<sup>n</sup>) spostamenti.

<table border="0">
   <tr>
      <td><PRE>
     Hanoi(n, P_iniziale, P_finale, P_appoggio)
       if (n<=1) sposta_un_disco(P_iniziale, P_finale)
       else
          Hanoi(n-1, P_iniziale, P_appoggio, P_finale)
          sposta_un_disco(P_iniziale, P_finale)
          Hanoi(n, P_appoggio, P_finale, P_iniziale)
     </PRE></td>
  </tr>
</table>
<BLOCKQUOTE>
<B>Esercizio.</B> Risolvere il punto 2 dell'esercizio 2 dell'appello del 24 giugno 2010: Hanoi con quattro paletti.
</BLOCKQUOTE>

<font color="#AF0F0F"><b>Lunedì 4 Aprile</b></font> - Caso migliore, peggiore e medio. Analisi del tempo di esecuzione in funzione della dimensione dell'input. Ricerca sequenziale: analisi nel caso migliore, peggiore e medio. Ricerca binaria: implementazione iterativa e ricorsiva. Soluzione dell'equazione di ricorrenza della ricerca binaria per iterazione.

<BLOCKQUOTE>
<B>Esercizi di riepilogo (D).</B> Dal libro di testo: esercizi 2.1 (con il metodo analitico), 2.2, 2.9, problemi 2.4, 2.9, 2.10. 
</BLOCKQUOTE>

<font color="#AF0F0F"><b>Giovedì 7 Aprile</b></font> - Risoluzione dell'esercizio di riepilogo C2 utilizzando il metodo iterativo per risolvere l'equazione di ricorrenza al punto 3 e sommando i costi sui nodi dell'albero della ricorsione al punto 4.

Risoluzione dell'esercizio di riepilogo C3 esplicitando la relazione tra risoluzione di un'equazione di ricorrenza con metodo iterativo e analisi dei costi sull'albero della ricorsione.

<font color="#AF0F0F"><b>Lunedì 11 Aprile</b></font> - Introduzione al problema dell'ordinamento. Insertion sort. Risoluzione equazioni di ricorrenza per iterazione e con albero della ricorsione.

<font color="#AF0F0F"><b>Giovedì 14 Aprile</b></font> - Bubble sort. Risoluzione Esercizio 2.9 dal libro di testo (pagina 56). Risoluzione Problema 2.9 dal libro di testo (pagina 59).

<BLOCKQUOTE>
<B>Esercizio.</B> Dal libro di testo: esercizio 4.2 (pagina 114) considerando solo =insertionSort= e risolvendo l'equazione di ricorrenza solo con il metodo dell'iterazione.
</BLOCKQUOTE>

<font color="#AF0F0F"><b>Lunedì 18 Aprile</b></font> - Selection Sort e Merge Sort con analisi del numero di confronti nel caso peggiore. Impostazione della soluzione dell'esercizio 4.2 a pagina 114.
<table border="0">
   <tr>
      <td><PRE>
    Algoritmo selSortRic(A, n)
      if (n <= 1) return
      m = 1
      for j = 2 to n do
        if (A[j] < A[m]) m = j
      scambia(A[1], A[m])
      selSortRic(A[2;n], n-1)
     </PRE></td>
     
     <td><PRE>
      Algoritmo insSortRic(A, n)
        if (n <= 1) return
        insSortRic(A, n-1)
        for i = n-1 to 1 do
          if (A[i] > A[i+1]) scambia(A[i], A[i+1])
          else return
&nbsp;
     </PRE></td>
  </tr>
</table>
<BLOCKQUOTE>
<B>Esercizio.</B> Calcolare tempo di esecuzione T(n) e numero di confronti C(n) dei due algoritmi =selSortRic= e =insSortRic=.
</BLOCKQUOTE>


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

_Esercizio E1._ 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 E2._ Proporre ed analizzare un algoritmo per risolvere il seguente problema: date due matrici quadrate A e B, di lato n, calcolare la matrice prodotto A x B. Qual è il tempo di esecuzione dell'algoritmo proposto?

_Esercizio E3._ Generalizzare l'esercizio E2 al caso di matrici rettangolari, assumendo che A e B abbiano rispettivamente dimensione (n x k) e (k x m). In funzione di quali parametri analizzereste il tempo di esecuzione? Qual è il tempo di esecuzione dell'algoritmo proposto?

_Esercizio E4._ 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 E5._ 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 E6._ 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; esercizi 1 e 2 degli appelli del 22 gennaio 2009, 5 febbraio 2009, 9 settembre 2008; esercizi 2 e 3 della prova intermedia del 27 novembre 2008; esercizio 4 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 1 e 2 dell'appello del 24 giugno 2010; esercizio 2 dell'appello del 6 luglio 2009; esercizi 2 e 3 dell'appello del 10 settembre 2009.

</BLOCKQUOTE>

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

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

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

<font color="#AF0F0F"><b>Lunedì 2 Maggio</b></font> -  Interruzione della didattica

<font color="#AF0F0F"><b>Giovedì 5 Maggio</b></font> - Heap binari: proprietà, extractMax, rappresentazione con vettore posizionale. Heapsort e ordinamento in loco.

<font color="#AF0F0F"><b>Lunedì 9 Maggio</b></font> - Costruzione di un heap in tempo lineare. Algoritmo heapsort. Implementazione in loco.

<font color="#AF0F0F"><b>Giovedì 12 Maggio</b></font>  Teorema master: enunciato ed esempi.  Soluzione prova intermedia.

<font color="#AF0F0F"><b>Lunedì 16 Maggio</b></font> - didattica sospesa  per elezioni amministrative (come da comunicato rettorale)

<font color="#AF0F0F"><b>Giovedì 19 Maggio</b></font> Quicksort. Ordinamenti lineari: counting sort.

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

   * _Teorema master:_ esercizi 2.6 e 2.7, problemi 2.5 (prime quattro ricorrenze) e 2.6
   * _Heap, heapsort:_ esercizi 4.4 e 4.5, problemi 4.3, 4.4, 4.5
   * _Quicksort:_ esercizi 4.9 e 4.12, problema 4.7
   * _Ordinamenti lineari:_ problemi 4.8, 4.9, 4.11 (parte 1)
   * _Misc:_ esercizio 4.3

</BLOCKQUOTE>

<font color="#AF0F0F"><b>Lunedì 23 Maggio</b></font>  Alberi di decisione e lower bound al numero di confronti. Rappresentazioni indicizzate di alberi

<font color="#AF0F0F"><b>Giovedì 26 Maggio</b></font> - Rappresentazioni di alberi: figlio sinistro-figlio destro, lista di figli, primo figlio-fratello successivo. Visite di alberi iterative e ricorsive: in profondità, ampiezza, preordine, simmetrica e postordine. Uso di una visita ricorsiva per il calcolo del numero di nodi di un albero.

<BLOCKQUOTE>Esercizio: modificare la visita ricorsiva per calcolare l'altezza di un albero.</BLOCKQUOTE>

<font color="#AF0F0F"><b>Lunedì 30 Maggio</b></font>  - didattica sospesa  per elezioni amministrative (come da comunicato rettorale)

<font color="#AF0F0F"><b>Martedì 31 Maggio</b></font> - _Recupero lezione, ore 14:00 aula 3 fisica._ Realizzazione di dizionari tramite alberi binari di ricerca.

<font color="#AF0F0F"><b>Giovedì 2 Giugno</b></font> - festa

<font color="#AF0F0F"><b>Lunedì 6 Giugno</b></font> - Alberi AVL: bilanciamento in altezza, fattore di bilanciamento, alberi di Fibonacci, delimitazione altezza, rotazione di base.

<font color="#AF0F0F"><b>Giovedì 9 Giugno</b></font> - Alberi AVL: rotazioni semplici e doppie, operazioni insert e delet, dimostrazione del fatto che il fattore di bilanciamento viene correttamente ripristinato dalle rotazioni.

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

   * _Esercizio G1._ Disegnare l'albero di decisione associato al mergesort per n=4.

   * _Esercizio G2._ Progettate un algoritmo per verificare se un albero binario soddisfa la proprietà di ricerca. Risolvete l'esercizio sia in modo iterativo che ricorsivo. In entrambi i casi, il tempo di esecuzione deve essere lineare nel numero n di nodi dell'albero.

   * _Esercizio G3._ Supponete di avere un albero binario di ricerca rappresentato tramite vettore padri. Quanto costa eseguire le operazioni search, insert e delete?

   * _Esercizio G4._ Supponete di avere un albero binario di ricerca rappresentato tramite vettore posizionale. Quanto costa eseguire le operazioni search, insert e delete? Qual è nel caso peggiore lo spazio richiesto per rappresentare l'albero?

   * _Dal libro di testo:_  esercizi 3.1, 3.4, 3.5, 4.3, 4.13, 4.14, 6.1, 6.2, 6.3, 6.4, 6.5, 6.6, 6.10 (sostituire "discusse in questo capitolo" con "viste in classe"); problemi 3.3, 3.4, 3.5, 3.6, 3.7, 3.8, 6.1, 6.2, 6.3, 6.4, 6.5, 6.6

   * _Compiti d'esame:_  a questo punto dovreste poter svolgere qualunque esercizio, esclusi quelli su tabelle hash e grafi.

</BLOCKQUOTE>

<font color="#AF0F0F"><b>Lunedì 13 Giugno</b></font> - didattica sospesa  per referendum (come da comunicato rettorale)

<font color="#AF0F0F"><b>Martedì 14 Giugno</b></font> - _Recupero lezione, ore 14:00 aula 3 fisica._ Esercizi preparazione esami.

<font color="#AF0F0F"><b>Giovedì 16 Giugno</b></font> Esercizi preparazione esami: Esercizio di riepilogo G2; Problema 6.6; Problema 4.5; Problema 4.7; Esercizio 6.1. 

<font color="#AF0F0F"><b>Primo appello estivo:</b></font> *Scritto 20 giugno, orale 22 giugno*

<font color="#AF0F0F"><b>Secondo appello estivo:</b></font> *Scritto 12 luglio, orale 14 luglio*

-->

<!-- 

<font color="#AF0F0F"><b>Giovedì 10 Giugno</b></font> - Esercizi su heap (calcolo del terzo minimo), alberi (es. 2.1 del 14 luglio 2009), alberi AVL (es. 2.2 del 14 luglio 2009, problemi 6.4 e 6.5 del libro) .

-->