Ottobre 1998

PROVA SCRITTA DI ALGORITMI (1o anno) Ottobre '98

TESTO E SOLUZIONI

Nota: negli esercizi 1, 2, 4 c'erano delle lievi varianti; leggere quindi bene il testo, prima di guardare la soluzione

Esercizio 1 (punti 2 in prima approssimazione)

 
Consideriamo  il seguente codice C:

#include <stdio.h>

int z = 0 ;
void sss (void) ;
void ttt( void) ;

main( )  {    int z = 1 ;
              sss ();
              ttt ();
          }

void ppp( void) ;

void sss (void)  {   ppp();    }

void ttt (void)  {   int z = 2;
                     ppp ();
                 }

void ppp( void)  {   printf ("%d     " , z ) ;  }

Domanda: qual' e` l'output ?

Risposta: 0 0

Giustificazione (NON richiesta): la dichiarazione che ha valore per la procedura ppp e` quella a livello di file, cioe` la prima, int z = 0 (vedere dispense, la sezione sulle regole di visibilita`).

Esercizio 2 (punti 1 in prima approssimazione)

 
Consideriamo  il seguente codice C:

#include <stdio.h>
#include <stdlib.h>

void sss(int * x);

main()  {   int * p;
            int * q ;
            p = (int*) malloc (1*sizeof(int));
            *p = 5;
            q = p ;
            sss(q);
            printf ("%d ", *p);
 }

void sss(int * x)    { *x = 3 ;}

Domanda: qual'e` l'output ?

Risposta: 3

Giustificazione (NON richiesta): nel main, i due puntatori p e q puntano alla stessa cella; l'indirizzo di tale cella viene passato alla procedura sss che modifica il contenuto della cella stessa.

Esercizio 3 (punti 2 in prima approssimazione)

Per non perdere tempo, lo scrivo a parole:

Domanda 1) : (logaritmo in base 3 di (2 alla n)) appartiene a Theta(logaritmo in base 2 di (3 alla n)) ??

Risposta: SI

Giustificazione (NON richiesta): logaritmo in base 3 di (2 alla n) = n * (logaritmo in base 3 di 2) = n * costante logaritmo in base 2 di (3 alla n) = n * (logaritmo in base 2 di 3) = n * costante'

Domanda 2) : Se sappiamo che per ogni n maggiore di 3 : g(n) ed f(n) sono maggiori (strettamente) di 0 ed inoltre il rapporto f(n)/g(n) e` minore o uguale di 20 possiamo concludere che f e` in Theta(g) ??

Risposta: NO

Giustificazione (NON richiesta): Basta considerare f e g tali che f(n) = 1 ed g(n) = n.

In effetti, tutto quello che si puo' concludere e` che f e` in O(g).

Esercizio 4 (punti 2 in prima approssimazione)

Consideriamo espressioni formate usando lettere maiuscole, parentesi tonde ed i simboli # e %. Lettere = {A, B, C, ...., Z}. L'insieme X e` dato dalla seguente definizione (induttiva): (base) L'insieme Lettere e` contenuto in X (passo_1) se w, z appartengono a X allora w#z e w%z appartengono a X (passo_2) se w appartiene a X allora (w) appartiene a X L'insieme Y e` dato dalla seguente definizione (induttiva): (base) L'insieme Lettere e` contenuto in Y (passo) se w, z appartengono a Y allora (w#z) e w%z appartengono a Y Domanda: quali delle seguenti affermazioni sono vere ? (1) X e` contenuto in Y (2) Y e` contenuto in X (3) gli unici elementi a comune tra X e Y sono le lettere e le espressioni formate solo da lettere e da % (4) nessuna delle precedenti Sul foglio risposte indicare solo i numeri delle affermazioni che credete vere. Risposta: L'unica vera e` la (2).

Giustificazione (NON richiesta): poiche' la base e` uguale e la regola che, prese z e w, restituisce w%z e` presente nei due passi, basta osservare che quello che si ha, per Y, usando la regola che prese w e z restituisce (w#z), in X si ottiene in due passi combinando la regola che prese w e z restituisce w#z, con quella che mette le parentesi attorno ad una qualunque espressione. Una dimostrazione formale si puo' fare per induzione.

Esercizio 5 (punti 3 in prima approssimazione)

L'esercizio riguarda le funzioni di hashing.
Indichiamo con ST l'insieme di tutte le stringhe sull'alfabeto delle lettere maiuscole italiane: {A, B, C, D, E, F, G, H, I, L, M, N, O, P, Q, R, S, T, U, V, Z}
Consideriamo tabelle hash con 100 buckets.
Per definire delle funzioni di hashing, codifichiamo le lettere usando due cifre decimali, come segue
cod(A) = 01
cod(B) = 02
cod(C) = 03
....
cod(N) = 12
.....
Consideriamo due funzioni (in quel che segue le xj sono lettere dell'alfabeto):

h1 : ST ---> { 0, ..., 99 } data da: h1( x1 x2 ... xn ) = ( cod(x1) cod(x2) ... cod(xn) ) mod 100 esempio h1(ABCD) = (01020304) mod 100 = 1020304 mod 100 = 4 (quindi, i codici si concatenano in modo da formare un numero decimale ...)

h2 : ST ---> { 0, ..., 99 } data da: h2( x1 x2 ... xn ) = ( cod(x1) + cod(x2) + ... + cod(xn) ) mod 100 esempio h2(ABCD) = (01+02+03+04) mod 100 = 10 mod 100 = 10

Domanda: come funzioni di hashing, le due funzioni sono ugualmente valide, oppure una e` migliore dell'altra, e quale?? Giustificare brevemente la risposta (senza giustificazione, la risposta, anche giusta, non e` valida).

Risposta: La funzione h2 e` decisamente migliore. Infatti:
--- mod 100 = prendere il resto della divisione per 100, quindi considerare solo le ultime 2 cifre decimali;
-- per questo motivo, la funzione h1 considera solo l'ultima lettera di ogni stringa e quindi lascia inutilizzati circa 80 dei 100 buckets !!!!
--- la h2 invece utilizza tutti i buckets.

Esercizio 6 (punti 4 in prima approssimazione)

Consideriamo:

il tipo di dato code di caratteri di lunghezza arbitraria; con le sorti: code, char, bool, ed i corrispondenti insiemi: CODE, CHAR, BOOL ;
l'operazione
conc : CODE x CODE ---> CODE definita da conc( <x1, ..., xk> , <y1, ..., yn> ) = <x1, ..., xk , y1, ..., yn> (qui le x e le y rappresentano singoli caratteri e x1 , y1 sono le teste)
l'implementazione delle code che utilizza liste (piu' tutto quello che serve per ottenere che le operazioni di base siano a costo costante).

Sul foglio risposte:

scrivere, in C oppure in Pascal (ma senza mescolare) il tipo corrispondente alla sorte code, nell'implementazione detta sopra;
disegnare la struttura che rappresenta, nell'implementazione detta sopra, la coda vuota e quella che rappresenta la coda < A, B, C>, dove A e` la testa;
scrivere, in pseudo-codice, o in C, oppure in Pascal, un'implementazione dell'operazione conc che abbia le seguenti caratteristiche:
--- code implementate come dichiarato sopra
--- l'implementazione di conc(c1, c2) modifica c1 "attaccando c2 in fondo a c1"
--- costo costante

Risposta 1.
Per poter avere le operazioni di base (in particolare, l'inserimento in fondo) a costo costante le soluzioni standard sono: usare le liste circolari oppure record formato da 2 puntatori; vediamo quest'ultima soluzione, in C:

typedef   struct nodo * lista;  /* lista e` un puntatore a nodo */

struct nodo { char  info;
              lista next;} ;

typedef struct { lista first ;  /* puntatore alla testa */
                 lista  last ;  /* puntatore alla coda */
               }  coda  ;

Risposta 2.
Sul foglio risposte bastava fare un disegno; qui descrivo a parole.
La coda vuota si implementa con un recod di tipo coda che ha i due puntatori nulli.
La coda formata da A, B, C si implementa con un record in cui il puntatore first punta alla testa di una lista semplice, di 3 elementi (cioe` record); il primo contiene A, il secondo B, il terzo C; il puntatore last punta al record che contiene C.

Risposta 3. (usando pseudo-codice)

procedura conc ( c1 : coda  --- Parametro IN/OUT
                 c2 : coda  --- Parametro IN,   ma anche IN/OUT )

 { if  c2 non e` vuota  
              /* per questo test, basta controllare il puntatore first */

   then {   if c1 non e` vuota

            then  { (c1.last ->next)  <---  c2.first
                     c1.last  <--- c2.last
                   }
             else   c1  <--- c2 
  
            /* volendo ora si puo` modificare il valore di c2,
               MA SENZA LIBERARE MEMORIA
            */
         }
  }

Esercizio 7 (punti 7 in prima approssimazione)

Il "pezzo di programma" che segue calcola la distanza di Hamming per un codice di lunghezza fissa con p bits e n configurazioni significative (cioe` che interessano), ma l'esercizio si puo` risolvere anche senza sapere nulla di codici e di Hamming. Qui:

cod e` una matrice con n righe e p colonne di booleani ( cod : array [1.. n, 1.. p] of boolean )
ham e` una variabile intera che alla fine conterra` la distanza di Hamming
continua e` una variabile booleana
le altre variabili sono intere e servono da indici o da ausiliari
per j =1, 2, ...., p : ....... equivale al Pascal for j := 1 to p do .......
usiamo le { } come in C

Pezzo di programma

(1)    ham <-- p ;	righe <-- 1 ;	continua <-- true

(2)    while (righe <  n)  and  continua  do	{

       (2.1)    k <-- righe +1

       (2.2)    while  ( k <= n )  and  continua  do	{

                (2.2.1)    aux <-- 0

                (2.2.2)    per j = 1, 2, ..., p :  
                                 if  cod[righe, j]   e` diverso da   cod[k, j]  
                                 then  aux <--  aux + 1

                (2.2.3)    if  ham > aux   then   ham <-- aux

                (2.2.4)    if  ham = 0   then   continua <-- false   else   k <-- k+1

       			}    chiude il while (2.2)

       (2.3)    righe <-- righe+1

		}    chiude il while (2)

(3)    scrivi( ham )

Domanda:
Determinare la complessita` del pezzo di programma, in funzione di n e di p , nel caso peggiore, possibilmente in Theta( ... ).
Non fare conti troppo dettagliati (esplicitando tutte le costanti,....), ma non limitarsi nemmeno a dare il risultato, o a quattro chiacchiere; in particolare: precisare se c'e` un caso peggiore (o caso pessimo) e qual'e`.

Soluzione:
Scriviamo: x^y per indicare "x elevato a y" La complessita` di tutto e` in Theta(p * n^2) . Infatti:

il caso peggiore si ha quando le righe sono diverse tra loro, e quindi la distanza di Hamming (ham) non diventa mai 0, cosi' che i due cicli while non vengono interrotti prima del tempo; tutti i costi sono costanti, tranne quelli delle istruzioni indicate sotto; il costo di tutto e`, a meno di una costante, uguale a quello del while piu' esterno; il costo di (2.2.2) e` lineare in p; quindi tutto il corpo del while (2.2) ha un costo della forma a' p + b' (con a', b' costanti); il ciclo si ripete (n - righe) volte circa; quindi tutto il while (2.2) ha un costo della forma a(n - righe) p + b(n - righe) + c (con a.b.c costanti) il costo del while (2.2) , a meno di costanti, si ha sommando a(n - righe) p + b(n - righe) + c per righe = 1,2,,,,n-1 la somna (n-righe) per righe = 1,2, ..., n-1 e` la solita somma che e` in Theta(n^2) Quindi Si arriva alla conclusione con un po' di manipolazioni algebriche (che sono noiose da scrivere in HTML).

Alternativamente, si poteva ragionare con le operazioni dominanti (ed era piu' semplice): caso peggiore come sopra; operazione dominante: il calcolo della distanza tra due codici (righe); il costo di questa operazione e` della forma: a p + b l'operazione si ripete n-1 volte, per righe = 1 n-2 volte per righe = 2 eccetera quindi l'operazione si ripete (n-1) + (n-2) + ... + 1 volte si ha quindi la solita sommatoria .... Il costo totale e` quindi in Theta(p * n^2)

Esercizio 8 (punti 7 in prima approssimazione)

Consideriamo alberi binari (ogni nodo ha 2 figli: figlio sinistro e figlio destro, che pero` possono essere vuoti) implementati nel modo solito:

un albero e` un puntatore a nodo; un nodo e` un record con 3 campi: info (di tipo che non interessa), sin, des (di tipo albero).

La procedura che segue calcola, in modo poco furbo, l'altezza dell'albero; per comodita`, all'albero vuoto attribuiamo altezza -1.

Usiamo { } e -> come in C.

function  alt ( t :  albero binario) : integer

{   if   t e` vuoto  then	return( -1 )

    else     if alt( t-> sin ) <  alt( t->des )
             then   return( 1 +  alt( t->des ) )
             else   return( 1 +  alt( t->sin ) )
}

Domanda:
Determinare la complessita` di una generica chiamata alt( t ) in funzione dell'altezza dell'albero, sia h, nel caso peggiore, possibilmente in Theta( ... ).
Non fare conti troppo dettagliati (esplicitando tutte le costanti,....), ma non limitarsi nemmeno a dare il risultato, o a quattro chiacchiere; in particolare: precisare se c'e` un caso peggiore (o caso pessimo) e qual'e`.

Soluzione:
La complessita` della chiamata e` in Theta(3^h), dove (3^h) indica (3 elevato alla h). Infatti:

tutti i costi sono costanti a parte quelli delle chiamate ricorsive; e` sufficiente quindi calcolare quante sono le chiamate nel caso peggiore
il caso peggiore si ha quando ogni nodo, non foglia, ha figlio destro e figlio sinistro non vuoti; questo corrisponde all'albero binario completo di altezza h
per ogni nodo ci sono 3 chiamate: a sinistra, a destra, a sinistra/destra; quindi l'albero delle chiamate e` un albero TERNARIO completo di altezza h; da cui la conclusione (infatti, il numero delle foglie e` 3^h mentre quello di tutti i nodi e` circa 3/2 del numero delle foglie).

Alternativamente, si poteva considerare il sistema:

T(0) = c
T(h) = 3 T(h-1) + d con c, d costanti

e risolverlo per sostituzioni successive.