Tema d'esame di esempio (2)

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.