====== Tema d'esame di esempio (2) ======

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


==== Esercizio 1 ====


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

  - h1=n mod 14 e h2=n mod 7
  - h1=n mod 13 e h2=n mod 7


==== Esercizio 2 ====


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.

==== Esercizio 3 ====


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)*/




==== Esercizio 4 ====


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: 
  ())$, )()($, (()))($

  - 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. 
    - Come cambiano, se cambiano, le complessità se si usa una Macchina di Turing a nastro singolo invece di una a k nastri?
  - 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.