Corso di Algoritmi e Strutture Dati—Informatica per il Management
Prova Scritta, 30/6/2016
• Chi deve recuperare il progetto del modulo 1 ha 1 ora e 30 minuti per svolgere gli esercizi 1, 2, 3
• Chi deve recuperare il progetto del modulo 2 ha 1 ora e 30 minuti per svolgere gli esercizi 4, 5, 6
• Chi deve sostenere la prova completa ha 2 ore e 30 minuti per svolgere tutti gli esercizi proposti.
• Durante la prova è consentito consultare libri e appunti.
• Non è consentito l'uso di dispositivi elettronici (ad esempio, cellulari, tablet, calcolatrici elettroniche...), né interagire in alcun modo con gli altri studenti pena l'esclusione dalla prova, che potrà avvenire anche dopo il termine della stessa.
• Le risposte devono essere scritte a penna su questi fogli, in modo leggibile e adeguatamente motivate. Le parti scritte a matita verranno ignorate. Eventuali altri fogli possono essere utilizzati per la brutta copia ma non devono essere consegnati e non verranno valutati.
• I voti saranno pubblicati su AlmaEsami e ne verrà data comunicazione all'indirizzo mail di Ateneo (@studio.unibo.it). Lo studente ha 7 giorni lavorativi di tempo per rifiutare il voto; tutti i voti non esplicitamente rifiutati entro tale data sono considerati accettati, e verranno in seguito verbalizzati.
BARRARE LA CASELLA CORRISPONDENTE ALLA PARTE SVOLTA
□ Svolgo solo la parte relativa al modulo 1 (esercizi 1, 2, 3);
□ Svolgo solo la parte relativa al modulo 2 (esercizi 4, 5, 6);
□ Svolgo tutto il compito
NON SCRIVERE NELLA TABELLA SOTTOSTANTE
Es. 1 Es. 2 Es. 3 Es. 4 Es. 5 Es. 6
/ 3 / 3 / 5 / 1 / 4 / 5 / 5 / 5 / 1
Esercizio 1. Determinare il costo asintotico degli algoritmi seguenti (non è richiesto di indicare cosa calcolano, basta solo determinarne il costo asintotico). Motivare adeguatamente le risposte. Il primo algoritmo, ricorsivo, viene inizialmente invocato come ALG1( A, 1, n)
ALG1( double A[1..n], integer i, integer j ) → double if ( i ≥ j ) then
return 1.0;
else
double tmp ← 0;
for integer k ← i to j do tmp ← tmp + A[k];
endfor
integer m ← FLOOR( ( i + j ) / 2 ); // arrotondamento per difetto return ALG1(A, i, m) + k + ALG1(A, m+1, j);
endfor
[punti 3]
ALG2( double A[1..n] ) → double double result ← 0;
integer k, j;
for k ← 1 to n - 10 do for j ← k to k + 10 do
result ← result + A[j];
endfor endfor return result;
[punti 3]
Soluzione. Alg1 ha costo O(n log n) in quanto il suo costo asintotico soddisfa l'equazione di rocorrenza T(n) = 2 T(n/2) + cn. Alg2 ha costo Θ(n): notare che il ciclo “for” piu' interno esegue un numero costante (11, per la precisione) di iterazioni.
Esercizio 2. Una rete di distribuzione idrica è rappresentata da un albero binario generico. L'acqua viene immessa nella radice con una portata di R metri cubi/secondo (valore reale positivo). Le foglie rappresentano “pozzi”, ossia punti in cui l'acqua viene estratta dal sistema per essere utilizzata. Tutti i nodi non foglia ricevono acqua dal proprio padre e la distribuiscono uniformemente tra figli. Questo significa che se un nodo riceve un flusso di x m3/sec dal proprio padre, e ha due figli, ciascuno di loro riceverà x/2 m3/sec; se il nodo ha un solo figlio, esso riceverà x m3/sec.
Scrivere un algoritmo ricorsivo che, dato in input l'albero T e il valore del flusso R ricevuto dalla radice, setta per ciascun nodo v di T l'attributo reale v.f al valore del flusso ricevuto da quel nodo, in base alle regole precedenti (la radice deve venire etichettata con v.f = R). E' vietato fare uso di variabili globali. Come esempio si consideri l'albero seguente, supponendo che la radice riceva R = 100 m3/s di acqua; i rimanenti nodi devono essere etichettati come indicato.
Notate che il flusso si conserva: se la radice riceve 100 m3/s, la somma complessiva dei flussi ricevuti dalle foglie (indicate in grassetto) sarà ancora 100 (25 + 12.5 + 12.5 + 25 + 25 = 100).
[punti 5]
Determinare il costo asintotico dell'algoritmo proposto, motivando la risposta. [punti 1]
Soluzione. La soluzione seguente ha costo O(n), essendo n il numero di nodi del grafo. L'algoritmo viene invocato con EtichettaAlbero(T, R), dove T è un riferimento (puntatore) alla radice
dell'albero; si suppone che l'albero sia rappresentato mediante nodi con puntatori ai figli.
ETICHETTAALBERO( Tree t, double val ) if ( t ≠ null ) then
t.f ← val;
if ( t.left ≠ null and t.right ≠ null ) then
ETICHETTAALBERO( t.left, val / 2);
ETICHETTAALBERO( t.right, val / 2);
else
// la soluzione è un po' “sporca”, anche se corretta: se siamo qui significa // che almeno uno tra i sottoalberi sx e dx è vuoto (anche entrambi) // di conseguenza, una delle due chiamate ricorsive (o entrambe) // non produrranno alcun risultato.
ETICHETTAALBERO(t.left, val );
ETICHETTAALBERO(t.right, val );
endif endif
100
50 50
25 25
12.5
50
25 25
25 12.5
Esercizio 3. Si consideri una tabella hash con m ≥ 10 slot, gestita mediante indirizzamento aperto;
la sequenza di ispezioni è prodotta dalla funzione:
h(k ,i)=(k +3 i)mod m
dove k rappresenta la chiave intera dell'elemento da memorizzare, e i rappresenta l'indice del
“tentativo di inserimento” i = 0, 1, …, m - 1; quindi la sequenza di ispezione per una chiave k è h(k, 0), h(k, 1), … h(k, m - 1).
Il prof. Carlo Ignazio Altrone (C. I. Altrone) afferma che la funzione hash di cui sopra funziona
“perfettamente” per qualsiasi valore di m ≥ 10. Ritenete questa affermazione corretta? Motivate la risposta. (Suggerimento: considerare m = 12, e tentare di inserire chiavi i cui valori siano tutti
multipli di 3, es., 0, 3, 6, 9, 12, ...) [punti 4]
Soluzione. Se la dimensione m della tabella hash è un multiplo di 3, allora la sequenza di ispezione h(k, 0), h(k, 1), … h(k, m - 1) non esamina tutti gli elementi della tabella. Nel caso m = 12, se le chiavi sono tutte multipli di 3 la sequenza di ispezione sarà sempre {0, 3, 6, 9}, e nessuno degli altri elementi della tabella verrà mai esaminato. Di conseguenza ci possono essere dei casi in cui non è possibile inserire nuove chiavi nonostante la tabella non sia piena.
Esercizio 4. Si consideri una famiglia di insiemi disgiunti mantenuta mediante un algoritmo merge- find di tipo QuickUnion con euristica “union by rank”: l'operazione merge(x, y) rende la radice dell'albero più basso figlia della radice dell'albero più alto; se entrambi gli alberi hanno la stessa altezza, rende la radice dell'albero contenente y figlia della radice di quello contenente x.
La struttura QuickUnion è inizialmente composta dagli elementi {1}, {2}, {3}, … {10}. Dopo un certo numero di operazioni merge(), risulta avere la struttura seguente:
Elencare una sequenza di operazioni merge() che al termine produca le struttura mostrata in figura.
Disegnare la struttura QuickUnion dopo ciascuna delle operazioni indicate, partendo dalla
situazione iniziale. [punti 5]
Soluzione. Una possibile sequenza di istruzioni è la seguente:
merge(1, 2) merge(3, 4) merge(6, 9) merge(1, 3) merge(1, 6) merge(7, 5) merge(8, 10) merge(7, 8)
1
3 6
4 9
7 5
2 8
10
Esercizio 5. Scrivere la tabella di istruzioni di una Macchina di Turing che risolve il problema seguente. La macchina opera su un alfabeto che contiene i simboli {blank, 0, 1}. Inizialmente il nastro contiene un numero binario composto dai simboli 0 e 1 e la testina di lettura-scrittura è posizionata sulla prima cifra a sinistra. La MdT deve scorrere il numero binario da sinistra a destra, senza modificarlo; deve quindi aggiungere una singola cifra binaria (0 oppure 1) a destra in modo tale che al termine sul nastro siano presenti un numero pari di cifre 1.
A titolo di esempio, la tabella seguente mostra quale deve essere il contenuto finale del nastro in alcuni casi (la cifra in grassetto è quella che viene aggiunta in coda al contenuto iniziale del nastro).
Notate come in tutti i casi alla fine il nastro contenga un numero pari di cifre “1” (zero è un numero pari)
Contenuto iniziale del nastro Contenuto finale del nastro
000 0000
000101 0001010
110010 1100101
00000001 000000011
(Suggerimento: usare due stati, q0 e q1; q0 significa “fino ad ora ho visto un numero pari di cifre 1”, mentre q1 significa “fino ad ora ho visto un numero dispari di cifre 1”). [punti 5]
Soluzione.
Stato corrente Simbolo corrente Nuovo simbolo Nuovo stato Spostamento
q0 0 0 q0 right
q0 1 1 q1 right
q0 blank 0 halt right
q1 0 0 q1 right
q1 1 1 q0 right
q1 blank 1 halt right
Esercizio 6. La cabina di una funivia è in grado di contenere un numero arbitrario di persone, purché il loro peso complessivo sia minore o uguale ad un certo valore C (numero reale positivo).
Alla stazione di partenza sono presenti in fila n ≥ 1 persone, aventi peso rispettivamente P[1], … P[n] (numeri reali positivi). Le persone vengono fatte salire una alla volta, nell'ordine in cui compaiono nell'array, fino a quando possibile ossia fino a quando il peso totale dei passeggeri in cabina rimane minore o uguale a C.
1. Scrivere un algoritmo efficiente che, dati in input il valore di C e l'array dei pesi P[1..n] dei passeggeri, restituisce il numero di viaggi che la funivia deve compiere per trasportare tutte le persone. Ad esempio, se C = 300 e P = [80, 70, 90, 60, 70, 100, 60, 90, 70, 70], allora la funzione restituisce 3, in quanto sono necessari tre viaggi (80+70+90+60 = 300 peso nel primo viaggio; 70+100+60 = 230 peso nel secondo viaggio; 90+70+70 = 230 peso nel terzo
viaggio) [punti 5]
2. Determinare il costo asintotico dell'algoritmo di cui al punto precedente, motivando la
risposta [punti 1]
Soluzione. Si usa un approccio greedy, ottenendo un algoritmo di costo Θ(n)
algoritmo Funivia( double C, array P[1..n] di double ) → int
int nv ← 0; // numero viaggi
int i ← 1;
while ( i ≤ n ) do
double Cres ← C; // capacità residua della cabina while ( i ≤ n and Cres ≥ P[i] ) do
Cres ← Cres – P[i];
i ← i + 1;
endwhile nv ← nv + 1;
endwhile return nv;
