Tema d'esame di esempio

Nota: questo compito non e' ancora del tutto rappresentativo, cercheremo di migliorarlo al piu' presto. Inoltre, ho fatto le soluzioni un po' di fretta – se c'e' qualcosa che non vi torna ne parliamo a lezione.

a) Dato un 2-3-4 Tree vuoto, inserire nell'ordine i seguenti caratteri: a u k b q o g s v i x z

soluzione:

['k']
   ['b']
     ['a']
     ['g', 'i']
   ['q', 'u']
     ['o']
     ['s']
     ['v', 'x', 'z']

Nota: implementate l'inserimento nei BTree in un qualsiasi linguaggio di programmazione ed usate il programma realizzato per generare soluzioni di esercizi simili. Lo stesso approccio si puo' usare per quasi tutti gli algoritmi visti a lezione.

b) Date le seguenti coppie < valore, probabilita' di ricerca >, costruire un BST con tempo di ricerca medio ottimo:

a    b    c    d    e    f
0.26 0.12 0.2  0.21 0.15 0.06

soluzione:

     d
 a       e
   c       f
  b

Nota: implementate l'inserimento nei BTree in un qualsiasi linguaggio di programmazione ed usate il programma realizzato per generare soluzioni di esercizi simili.

a) Determinare la complessita' computazionale in funzione di n ed m per il seguente frammento di codice:

for(i=1; i<n; i*=2)
 for(j=i; j<n; j++)
  if (j%2) {
   for(k=m; k>0; k-=2)
      A[i,j,k]=B[i,j,k]
  } else {
   for(k=0; k<m; k+=2)
      A[i,j,k]=C[i,j,k]+k
  }

soluzione:

for(i=1; i<n; i*=2)        // lg n
 for(j=i; j<n; j++)        // n/2 (valore atteso)
  if (j%2) {               // max()
   for(k=m; k>0; k-=2)     // m/2
      A[i,j,k]=B[i,j,k]    // O(1)
  } else {
   for(k=0; k<m; k+=2)     // m/2
      A[i,j,k]=C[i,j,k]+k  // O(1)
  }

⇒ O(m n lg n)

b) Determinare i limiti inferiori e superiori piu' stretti possibile per T(n) per le seguenti ricorrenze:

1) T(n) = 3 T(n/4) + 2 sqrt(n)
2) T(n) = T(n-3) + n lg n
3) T(n) = 4 T(n/3) + n lg n
4) T(n) = T(n-1) + T(n-2) + n2

soluzione:

1) Th(n^(lg_4 3)) (caso r<1 del T. maestro semplificato)
2) Th(n2 lg n)
3) Th(n^(lg_3 4)) (caso 1 del T. maestro generale)
4) Th(n2 2^n)

Progettare un algoritmo che risolva il problema dello zaino con disponibilita' illimitata di elementi di ciascun tipo. Valutarne la complessita' computazionale [bonus].

soluzione: Il problema dello zaino con disponibilita' illimitata si puo' affrontare con il metodo della programmazione dinamica. Lo zaino ha un peso totale massimo k, calcoliamo per ogni sotto-zaino di peso h, 0<h<k la soluzione ottima. La soluzione per k e' data dalla combinazione di due zaini piu' piccoli (ovvero, e' analogo al problema del taglio delle aste). La complessita' e' dell'ordine di O(n*k), dove n e' il numero di classi di oggetti e k e' il peso massimo dello zaino.