Informatica 3: Novità

Salve a tutti,

ho finito di correggere i compiti. Metto i voti in bacheca lunedi' mattina. Visione compiti sempre lunedi' mattina alle 10:15 in aula PT1 al DEI.

G.

P.S.: registro i voti di API e di Informatica 3 la prossima settimana.

Applicheremo le seguenti regole:

• E' possibile recuperare una parte singola; nel momento in cui si consegna il nuovo compito si considera annullato il voto precedente;
• La media fra I3 e IT prevede arrotondamento all'intero superiore.

La visione dei compiti si terra' lunedi' alle 12 in Sala Seminari presso il DEI.

Soluzione

Questo tema e' stato preparato dal prof. Alessandro Campi.

Si consideri una tabella di hash con 12 posizioni. Si vuole gestirla usando il double hashing h1(n)+i*h2(n) (con n numero da inserire e i numero del tentativo).

Dire quale tra queste coppie di funzioni si adotterebbe motivando la risposta

1. h1=n mod 14 e h2=n mod 7
2. h1=n mod 13 e h2=n mod 7

Si supponga di dover gestire l'assegnazione automatica degli interventi durante le diverse sessioni di una conferenza. In ogni sessione presentano sei persone. Le persone che devono presentare appartengono a diverse società. Alcune coppie di società sono fortemente ostili l'una all'altra, si vuole perciò evitare di inserire nella stessa sessione due oratori appartenenti a società fortemente ostili. Si delinei una struttura dati per modellare il problema e si proponga un algoritmo per assegnare le persone alle sessioni.

Si calcoli la complessità del seguente frammento di codice (rispetto a n)

for(i=0;i<n;i++)
  for (j=i;j<2^n;j++)
    doSomething() /*si supponga doSomething costi log(n)*/

for(i=2;i<n;i=i*i)
  for (j=i;j<2^n;j=j*j)
    doSomething() /*si supponga doSomething costi log(n)*/

Si consideri il linguaggio L fatto di stringhe di parentesi tonde ben parentetizzate terminate dal simbolo $. Esempi di stringhe appartenenti ad L sono:

()()$, (())$, ((())()(()))()(())$

Esempi di stringhe non appartenenti ad L sono:

())$, )()($, (()))($

1. Si delinei la più semplice Macchina di Turing a k nastri che accetta il linguaggio L, e se ne valutino le complessità spaziale e temporale in funzione della lunghezza n della stringa in input.
   1. Come cambiano, se cambiano, le complessità se si usa una Macchina di Turing a nastro singolo invece di una a k nastri?
2. Si delinei la più semplice macchina RAM che accetta il linguaggio L, e se ne valutino le complessità temporale e spaziale in funzione della lunghezza n della stringa di input, usando il criterio di costo logaritmico.

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.