DIPARTIMENTO   DI   INFORMATICA
Università di Torino

Lezione del 22/11/04 [2 ore, in AULA C, dalle 14:00 alle 16:00]

di: Algoritmi & Laboratorio ( Modulo 1 )

"Riassunto" della lezione:

Sono stati svolti i seguenti esercizi (alla lavagna).

ESERCIZIO 1

Considerate la funzione F: nat -> nat (dove nat e' linsieme dei numeri naturali) definita come segue:
  • F(n) = 1, se n = 0, 1
  • F(n) = 3 * F(INF(n/3)) + F(SUP(n/3)), se n > 1
dove INF(r) e SUP(r) denotano, rispettivamente, la parte intera inferiore e la parte intera superiore del numero reale r. Si richiede di:
  1. Scrivere un algoritmo ricorsivo per calcolare F(n) dato n in input.
  2. Determinare la complessita' asintotica dell'algoritmo nel caso peggiore.

Svolgimento dell'ESERCIZIO 1

  1. Lo pseudo-codice Java-like dell'algoritmo e' il seguente: 
    /*
n >= 0
*/

int f (int n)
{    
    if (n < 2) 
       then return 1
       else return 3 * f(INF(n/3)) + f(SUP(n/3))
}

/*
ritorna F(n)
*/
  2. L'equazione di ricorrenza che descrive la complessita' in tempo dell'algoritmo e' la seguente (non c'e' distinzione tra i casi ottimo, medio, peggiore):
    • T(n) = 1, se n = 0, 1
    • T(n) = T(INF(n/3)) + T(SUP(n/3)) + 1, se n > 1
    Risolviamo l'equazione di ricorrenza assumendo che n sia una potenza di 3, ovvero n = 3k per un qualche k >= 1 (E FACILE OSSERVARE CHE LA COMPLESSITA' ASINTOTICA TROVATA E' LA STESSA ANCHE NEL CASO IN CUI n NON SIA UNA POTENZA DI 3). Se n e' una potenza di 3 allora:
    • INF(n/3) = SUP(n/3) = n/3, se n >= 3
    quindi l'equazione puo' essere riscritta come:
    • T(n) = 1, se n = 0 (CASO CHE NON SI PRESENTA MAI SE n E' POTENZA DI 3)
    • T(n) = 1, se n = 1
    • T(n) = 3, se n = 2 (CASO CHE NON SI PRESENTA MAI SE n E' POTENZA DI 3)
    • T(n) = 2 * T(n/3) + 1, se n > 2
    Applicando il Teorema Master (primo caso, perche': a = 2, b = 3, e 1 = O(nlog32-epsilon), per log32 > epsilon > 0) abbiamo: T(n) = THETA(nlog32).

Ulteriori osservazioni sullo svolgimento dell'ESERCIZIO 1

  • La complessita' in spazio dell'algoritmo e' la seguente (non c'e' distinzione tra i casi ottimo, medio, peggiore): S(n) = THETA(log3n).
  • L'equazione di ricorrenza potrebbe essere risolta, atrettando agevolmente con il metodo iterativo (disegnando l'albero di ricorsione). Infatti, quando n e' una potenza di 3, l'albero di ricorsione e' l'albero binario completo di altezza log3n. Il costo delle operazioni svolte in ogni nodo (ovvero il costo delle operazioni svolte quando il record di attivazione corrispondente al nodo e' in cima allo stack di attivazione) e' O(1). Quindi, la complessita' computazionale asintotica in tempo e' data dal numero di nodi dell'albero. Un albero binario completo di altezza k ha 2k+1-1 (si ricordi che, per convenzione, l'albero con un solo nodo ha altezza 0). Quando k = log3n il numero di nodi e' 2(log3n)+1-1 = 2*2(log3n)-1 = 2*nlog32-1 = THETA(nlog32).
  • Lo pseudo-codice Java-like d una versione "ottimizzata" dell'algoritmo potrebbe essere il seguente: 
    /*
n >= 0
*/

int f (int n)
{    
    if (n < 2) 
       then return 1
    else if ((n % 3) == 0) 
       then return 4 * f(n/3) 
    else 
       return 3 * f(INF(n/3)) + f(SUP(n/3))
}

/*
ritorna F(n)
*/
E' facile dimostrare che:
  • La complessita' asintotica in tempo nel caso ottimo (che si verifica quando n e' una potenza di 3) e' THETA(log3n).
  • La complessita' in spazio dell'algoritmo e' (non c'e' distinzione tra i casi ottimo, medio, peggiore): THETA(log3n).
Ovviamente la complessita' asintotica in tempo nel caso peggiore e' O(nlog32). Un'ulteriore ottimizzazione potrebbe ressere realizzata utilizzando la tecnica della "programmazione dinamica".

ESERCIZIO 2

Considerate la funzione F che, data una sequenza
  • A = (a1,a1,...,an)
di n >= 0 numeri interi, restituisca il valore:
  • F(A) = 3*a1 + 32*a1 + ... + 3n*an
Si richiede di:
  1. Scrivere un algoritmo iterativo per calcolare F(A) dato A in input. Analizzarne la complesita'.
  2. Scrivere un algoritmo (ricorsivo) "divide et impera" per calcolare F(A) dato A in input. Fornire l'equazione di ricorrenza che ne ne descrive la complessita' asintotica in tempo nel caso peggiore. Risolvere tale equazione.

Svolgimento dell'ESERCIZIO 2

Supponiamo che gli array siano indicizzati a partire da 1 (e non da 0, come avviene in Java).
  1. Lo pseudo-codice Java-like dell'algoritmo e' il seguente: 
    /*
A.I.: length[A] >= 0
*/

int f (int[] A )
{    
int n = lenght[A];
int r = 0;

int i = n;
for i = n downto 1 do
    s = 3 * (A[i] + s)
  
return s;
}

/*
A.F.: ritorna F(n)
*/

    Siccome il corpo del ciclo ha costo O(1) e ci sono n iterazioni (non c'e' distinzione tra i casi ottimo, medio, peggiore), la complessita' in tempo dell'algoritmo f e': THETA(n).

  2. Lo pseudo-codice Java-like dell'algoritmo e' il seguente: 
    /*
A.I.: length[A] >= 0
*/

int f (int[] A )
{    
   return fDI(A,1,length[A]);
}

/*
A.F.: ritorna F(n)
*/


/*
A.I.: i,j sono indici di A
*/

int fDI (int[] A, int i, int j)
{    
    if (i > j) 
       then return 0
    else if (i=j) return 3 * A[i]
    else {
	   int m = INF((i+j)/2);
	   return fDI(A,i,m)) + exp(3,m-i+1) * fDI(A,m+1,j)
         }
}

/*
A.F.: ritorna F(A[i..j])
*/
    dove INF e SUP sono stati definiti nell'ESERCIZIO 1, e exp(a,b) calcola a elevato alla potenza b (dove a e b sono numeri interi > 0).

    L'equazione di ricorrenza che descrive la complessita' in tempo dell'algoritmo fDI e' la seguente (non c'e' distinzione tra i casi ottimo, medio, peggiore), dove la dimensione del problema n e' data da MAX(j-i+1, 0). Se assumiamo i <= j, abbiamo semplicemente n = j-i+1.

    • T(n) = 1, se n = 0, 1
    • T(n) = T(INF(n/2)) + T(SUP(n/2)) + E(INF(n/2)), se n > 1
    dove E(m) esprime il tempo richiesto per calcolare 3m nel caso peggiore. A lezione abbiamo visto un algoritmo che, dati due interi x,y >0, permette di calcolare xy in tempo THETA(log y). Possiamo quindi riscrivere l'equazione come:
    • T(n) = 1, se n = 0, 1
    • T(n) = T(INF(n/2)) + T(SUP(n/2)) + log(INF(n/2)), se n > 1

    Risolviamo l'equazione di ricorrenza assumendo che n sia una potenza di 2, ovvero n = 2k per un qualche k >= 1 (E' FACILE OSSERVARE CHE LA COMPLESSITA' ASINTOTICA TROVATA E' LA STESSA ANCHE NEL CASO IN CUI n NON SIA UNA POTENZA DI 2). Se n e' una potenza di 2 allora:

    • INF(n/2) = SUP(n/2) = n/2, se n >= 2
    quindi l'equazione puo' essere riscritta come:
    • T(n) = 1, se n = 0 (CASO CHE NON SI PRESENTA MAI SE n E' POTENZA DI 2)
    • T(n) = 1, se n = 1
    • T(n) = 2 * T(n/2) + log(n/2), se n > 2
    Applicando il Teorema Master (primo caso, perche': a = 2, b = 2, e log(n/2) = O(nlog22-epsilon) = O(n1-epsilon), per 1 > epsilon > 0) abbiamo: T(n) = THETA(nlog22) = THETA(n).

Ulteriori osservazioni sullo svolgimento dell'ESERCIZIO 2

  1. Osservazioni sul punto 1.
    • La complessita' in spazio dell'algoritmo iterativo e' la seguente (non c'e' distinzione tra i casi ottimo, medio, peggiore): THETA(1), dove ovviamente non si tiene conto del vettore che memorizza l'input.
    • Il problema considerato e' un caso particolare del problema (spiegato a lezione) di calcolare il valore di un polinomio a0 + a1*x + a2*x2 + ... + an*xn. L'algoritmo fornito e' una "specializzazione" dell'algoritmo basato sulla formula di Horner.
  2. Osservazioni sul punto 2.
    • La complessita' in spazio dell'algoritmo ricorsivo e' la seguente (non c'e' distinzione tra i casi ottimo, medio, peggiore): THETA(log22), dove ovviamente non si tiene conto del vettore che memorizza l'input.
    • Risolvere l'equazione di ricorrenza con il metodo iterativo (anche disegnando l'albero di ricorsione) non e' immediato. Infatti, quando n e' una potenza di 2, l'albero di ricorsione e' l'albero binario completo di altezza log2n. Il costo delle operazioni svolte in ogni nodo (ovvero il costo delle operazioni svolte quando il record di attivazione corrispondente al nodo e' in cima allo stack di attivazione) e' THETA(log(n/(2k+1)) dove k e' la profondita' del nodo (si ricordi che, per convenzione, la radice ha profondita' 0). Quindi, la complessita' computazionale asintotica in tempo e' data dalla somma: SOMMATORIAda k=0 fino a log2n 2k * log(n/(2k+1)). Come potete vedere, non e' immediato dimostrare che tale funzione e' THETA(n).
    • Se, per calcolare 3m si usasse un algoritmo di complesita' in tempo lineare in m, l'equazione di ricorrenza che descrive l'algoritmo ricorsivo diventerebbe
      • T(n) = 1, se n = 0, 1
      • T(n) = T(INF(n/2)) + T(SUP(n/2)) + n/2, se n > 1
      In questo caso si applicherebbe il caso 2 del teorema master, e l'algoritmo avrebbe quindi complessita' THETA(n*log(n)).

      L'equazione di ricorrenza potrebbe essere risolta, atrettando agevolmente con il metodo iterativo (disegnando l'albero di ricorsione). Infatti, quando n e' una potenza di 2, l'albero di ricorsione e' l'albero binario completo di altezza log2n. Il costo delle operazioni svolte in ogni nodo (ovvero il costo delle operazioni svolte quando il record di attivazione corrispondente al nodo e' in cima allo stack di attivazione) e' THETA(n/(2k+1)) dove k e' la profondita' del nodo (si ricordi che, per convenzione, la radice ha profondita' 0). Quindi, la complessita' computazionale asintotica in tempo e' data dalla somma: SOMMATORIAda k=0 fino a log2n 2k * n/(2k+1) = SOMMATORIAda k=0 fino a log2n n/2 = THETA(n*log(n)).

    • Un'altra versione dell'algoritmo e' la seguente: 
      /*
A.I.: length[A] >= 0
*/

int f' (int[] A )
{    
   return fDI'(A,1,length[A]).first;
}

/*
A.F.: ritorna F(n)
*/


/*
A.I.: i,j sono indici di A
*/

CoppiaDiInt fDI' (int[] A, int i, int j)
{    
    if (i > j) 
       then return (0, 1)
    else if (i=j) return (3 * A[i], 3)
    else {
	   int m = INF((i+j)/2);
	   CoppiaDiInt p1 = fDI'(A,i,m);
	   CoppiaDiInt p2 = fDI'(A,m+1,j);
	   return (p1.first  + p1.second * p2.first , p1.second * p2.second)
         }
}

/*
A.F.: ritorna la coppia di interi (F(A[i..j], 3MAX(INF((j-i+1, 0)))
*/
      dove INF e SUP sono stati definiti nell'ESERCIZIO 1, e p.first e p.second denotano (ripettivamente) il primo e il secondo elemento della copia di interi p.

      L'equazione di ricorrenza che descrive la complessita' in tempo dell'algoritmo fDI' e' la seguente (non c'e' distinzione tra i casi ottimo, medio, peggiore), dove la dimensione del problema n e' data da MAX(j-i+1, 0). Se assumiamo i <= j, abbiamo semplicemente n = j-i+1.

      • T(n) = 1, se n = 0, 1
      • T(n) = T(INF(n/2)) + T(SUP(n/2)) + 1, se n > 1
      Riscrivendo l'equazione assumento che n sia una potenza di 2, e applicando il Teorema Master (primo caso, perche': a = 2, b = 2, e 1 = O(nlog22-epsilon) = O(n1-epsilon), per 1 > epsilon > 0) abbiamo: T(n) = THETA(nlog22) = THETA(n).

      L'equazione di ricorrenza potrebbe essere risolta, atrettando agevolmente con il metodo iterativo (disegnando l'albero di ricorsione). Infatti, quando n e' una potenza di 2, l'albero di ricorsione e' l'albero binario completo di altezza log2n. Il costo delle operazioni svolte in ogni nodo (ovvero il costo delle operazioni svolte quando il record di attivazione corrispondente al nodo e' in cima allo stack di attivazione) e' THETA(1) Quindi, la complessita' computazionale asintotica in tempo e' data dalla somma (ovvero dal numero di nodi dell'albero binario completo di altezza log2n): SOMMATORIAda k=0 fino a log2n 2k = THETA(n).



[Corso di Studi di Informatica]
Last update: Jan 17, 2006
} } /* A.F.: ritorna F(A[i..j]) */ dove INF e SUP sono stati definiti nell'ESERCIZIO 1, e exp(a,b) calcola a elevato alla potenza b (dove a e b sono numeri interi > 0).

L'equazione di ricorrenza che descrive la complessita' in tempo dell'algoritmo fDI e' la seguente (non c'e' distinzione tra i casi ottimo, medio, peggiore), dove la dimensione del problema n e' data da MAX(j-i+1, 0). Se assumiamo i <= j, abbiamo semplicemente n = j-i+1.

dove E(m) esprime il tempo richiesto per calcolare 3m nel caso peggiore. A lezione abbiamo visto un algoritmo che, dati due interi x,y >0, permette di calcolare xy in tempo THETA(log y). Possiamo quindi riscrivere l'equazione come:

Risolviamo l'equazione di ricorrenza assumendo che n sia una potenza di 2, ovvero n = 2k per un qualche k >= 1 (E' FACILE OSSERVARE CHE LA COMPLESSITA' ASINTOTICA TROVATA E' LA STESSA ANCHE NEL CASO IN CUI n NON SIA UNA POTENZA DI 2). Se n e' una potenza di 2 allora:

quindi l'equazione puo' essere riscritta come: Applicando il Teorema Master (primo caso, perche': a = 2, b = 2, e log(n/2) = O(nlog22-epsilon) = O(n1-epsilon), per 1 > epsilon > 0) abbiamo: T(n) = THETA(nlog22) = THETA(n).

Ulteriori osservazioni sullo svolgimento dell'ESERCIZIO 2

  1. Osservazioni sul punto 1.
  2. Osservazioni sul punto 2.


[Corso di Studi di Informatica]
Last update: Jan 17, 2006