Table of Contents

Informatica 3: Novità

Quest'area è dedicata agli aggiornamenti relativi al corso di Informatica 3.

Voti e visione compiti 25/2

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.

Regole per i recuperi parziali e le medie

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.

Voti Prova in Itinere 2011

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

Matricola VOTO
765003 17
714833 17
729329 25
728995 21
726932 19
729651 25
764024 INS
749478 22
726634 INS
727440 16
726617 24
729952 15
729606 17
728425 22
728005 25
727193 26
728382 21
713947 17
730500 INS
733147 INS
727669 19
729894 30
714463 22
727979 15
727349 INS
664165 INS
729327 INS
728205 15
727252 22
728780 26
727052 19
727523 INS
713799 INS
726478 24
727485 30
726606 17
729100 17
729709 20
729588 23

Soluzione

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

  1. h1=n mod 14 e h2=n mod 7
  2. 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:

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

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.

Esercizio 1: Strutture Dati

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.

Esercizio 2: Ricorrenze e complessita'

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)

Esercizio 3: Progetto di algoritmi

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.

· 2011/01/18 16:14 · Giovanni Agosta

Older entries >>