Corso di Algoritmi e Strutture Dati—Informatica per il Management
Prova Scritta, 15/9/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 dei moduli 2/3 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 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 ai moduli 2/3 (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
/ 4 / 2 / 2 / 2 / 4 / 2 / 4 / 1 / 3 / 1 / 1 / 2 / 2 / 2
Esercizio 1. La sequenza di Fibonacci di ordine p, p ≥ 2, è una estensione della sequenza di Fibonacci vista a lezione, in cui ciascun valore si ottiene sommando i p valori precedenti.
Formalmente, la sequenza di Fibonacci di ordine p, Fp(1), Fp(2), … Fp(n), ... è definita come:
- Fp(i) = 1 per ogni 1 ≤ i ≤ p
- Fp(n) = Fp(n - 1) + Fp(n - 2) + … + Fp(n - p) per ogni n > p
Si noti che ponendo p = 2 si ottiene la consueta sequenza di Fibonacci 1, 1, 2, 3, 5, 8, 13, ...
1. Scrivere un algoritmo efficiente che, dati in input i valori n e p, restituisce Fp(n), ossia l'n- esimo valore della sequenza di Fibonacci di ordine p. [punti 4]
2. Determinare il costo asintotico dell'algoritmo precedente, espresso in funzione di n e p.
[punti 2]
Soluzione. Una possibile soluzione ricalca la versione iterativa del calcolo della successione di Fibonacci, utilizzando un array F[1..n] per evitare la ricorsione.
integer FibonacciP(integer p, integer n) if (n ≤ p) then
return 1;
else
integer F[1..n], i, j;
for i ← 1 to p do F[i] ← 1;
endfor
for i ← p + 1 to n do F[i] ← 0;
for j ← 1 to p do F[i] ← F[i] + F[i - j];
endfor endfor return F[n];
endif
Questa soluzione richiede spazio O(n) e tempo O(np), a causa dei due cicli “for” annidati che sono necessari per calcolare F[i]. In realtà il ciclo più interno non è necessario, perché ad ogni iterazione del ciclo più esterno è possibile ricalcolare la somma partendo da quella disponibile dopo il passo precedente:
integer FibonacciP(integer p, integer n) if (n ≤ p) then
return 1;
else
integer F[1..n], i, sum;
for i ← 1 to p do F[i] ← 1;
endfor sum ← p;
for i ← p + 1 to n do F[i] ← sum;
sum ← sum – F[i - p] + F[i];
endfor return F[n];
endif
Questa nuova soluzione richiede sempre spazio O(n) ma costo O(n) (che è indipendente da p). In modo più laborioso è possibile ridurre lo spazio da O(n) a O(p), lasciando inalterato il tempo O(n);
questo può essere vantaggioso nel caso in cui p sia molto minore di n, che appare uno scenario ragionevole. Utilizziamo un array F[0..p] di (p + 1) elementi, che gestiamo come un buffer circolare in cui memorizzare i valori precedenti Fp(i - 1) + Fp(i - 2) + … + Fp(i - p) e il valore corrente Fp(i).
L'indice np indica la posizione in F[] corrispondente al valore Fp(i - p), mentre nn indica la posizione in F[] in cui memorizziamo Fp(i):
integer FibonacciP(integer p, integer n) if (n ≤ p) then
return 1;
else
integer F[0..p], i, sum, np, nn, last;
for i ← 0 to p - 1 do F[i] ← 1;
endfor
sum ← p; np ← 0; nn ← p;
for i ← p to n - 1 do F[nn] ← sum;
last ← sum;
sum ← sum – F[np] + F[nn];
np ← (np + 1) mod (p + 1);
nn ← (nn + 1) mod (p + 1);
endfor return last;
endif
Molti si sono limitati a trascrivere l'algoritmo per il calcolo dei normali numeri di Fibonacci, che si ottengono sommando i due valori precedenti. Non basta cambiare l'estremo iniziale del ciclo
“for” dell'algoritmo di Fibonacci con un “for i <- p to n do ...” perche' sia corretto.
Questo esercizio e' estremamente semplice, almeno nella sua soluzione base (la prima che e' stata mostrata sopra, che avrebbe comunque consentito di ottenere punteggio pieno). Chi non e' riuscito a impostarlo correttamente e' invitato a migliorare il proprio livello di preparazione..
Fp(i-p) F
p(i)
np nn
Fp(i-1) ...
sum
Esercizio 2. L'algoritmo seguente restituisce true se e solo se nell'array A[1..n] (che deve contenere n ≥ 2 elementi) sono presenti due valori contigui uguali.
bool CONTIGUIUGUALI( intger A[1..n] ) for integer i ← 1 to n - 1 do
if ( A[i] == A[i + 1] ) then // (*) return true;
endif endfor return false;
1. Assumendo n “grande”, determinare il minimo numero di volte in cui il test A[i] == A[i+1]
(riga marcata con (*)) viene eseguito, in funzione di n. E' richiesto di indicare il valore esatto; motivare la risposta, indicando con quali input la riga (*) viene eseguita il numero
minimo di volte. [punti 2]
2. Assumendo n “grande”, determinare il massimo numero di volte in cui il test A[i] == A[i+1]
(riga marcata con (*)) viene eseguito. E' richiesto di indicare il valore esatto; motivare la risposta, indicando con quali input la riga (*) viene eseguita il numero massimo di volte.
[punti 2]
Soluzione. Il minimo numero di volte è 1, che si verifica quando i primi due elementi di A sono uguali; il massimo numero di volte è n - 1, che si verifica quando l'array A non contiene valori adiacenti uguali.
Esercizio 3. Consideriamo un albero binario di struttura arbitraria T in cui a ciascun nodo v sia associato un valore intero v.val. L'albero è rappresentato mediante nodi con puntatori ai figli.
Scrivere un algoritmo ricorsivo che, dato in input un riferimento alla radice di T, restituisce il numero di nodi i cui figli hanno lo stesso valore. Ad esempio, considerando l'albero seguente:
l'algoritmo restituisce 2, in quanto ci sono due nodi (la radice, e il suo figlio sinistro) in cui entrambi
i figli hanno lo stesso valore. [punti 4]
Determinare il costo asintotico dell'algoritmo proposto, motivando la risposta. [punti 2]
Soluzione.
integer ALG( Tree T ) if (T == NULL) then
return 0;
else
integer c ← 0;
if ( T.right ≠ NULL and T.left ≠ NULL and T.right.val == T.left.val ) then c ← 1;
endif
return c + ALG(T.left) + ALG(T.right);
endif
L'algoritmo ha costo (n), dove n -il numero di nodi dell'albero.
7
1 1
-3 -3 0
2
4 0 13
Ho visto diverse soluzioni simili alla seguente (con varianti):
integer FIGLIUGUALI(Tree T) if ( T == null ) then
return 0;
else if (T.left == T.right) then return 1;
else
return FIGLIUGUALI(T.left) + FIGLIUGUALI(T.right);
endif
L'algoritmo precedente contiene diversi errori:
1. Il test “if (T.left == T.right) ...” avrebbe dovuto essere scritto come “if (T.left.val ==
T.right.val) ...”; in realtà anche così non sarebbe stato corretto (vedi punto successivo) 2. T.left indica il riferimento alla radice del sottoalbero sinistro (in modo simile, T.right
indica il riferimento alla radice del sottoalbero destro). Prima di controllare il valore associato a tale nodo, è necessario verificare che il sottoalbero sinistro esista, cioè che T.left sia diverso da null (stessa cosa per T.right)
3. Una volta assicurati che i figli sinistro e destro esistano, e che i loro valori siano uguali, non è corretto ritornare subito 1; occorre invece effettuare una chiamata ricorsiva per contare anche il numero di nodi con figli aventi lo stesso valore nei sottoalberi sinistro e destro.
Esercizio 4. Un traghetto può trasportare al massimo N veicoli, e può sostenere un peso complessivo minore o uguale a W kg (entrambi questi vincoli devono essere rispettati). All'imbarco sono presenti n ≥ 1 veicoli aventi pesi P[1..n]. I veicoli devono essere imbarcati nell'ordine in cui sono presenti nell'array (prima quello di peso P[1], poi quello di peso P[2] e così via). Quando non è più possibile imbarcare ulteriori veicoli (perché si supererebbe il numero massimo di veicoli consentiti N oppure il peso massimo W), il traghetto effettua un viaggio per portare il carico a destinazione e torna indietro vuoto. Tutti i pesi sono numeri reali positivi; nessun veicolo ha peso superiore a W (quindi tutti i veicoli possono essere caricati)
1. Scrivere un algoritmo greedy che dati in input il numero massimo di veicoli N, la capacità W del traghetto e i pesi P[1..n] dei veicoli, restituisce il numero di viaggi (considerando solo l'andata) che è necessario effettuare per trasportare tutti i veicoli. Ad esempio, se N = 3, W = 1000 e P = [100, 300, 200, 400, 100, 400, 300, 400, 350, 500], l'algoritmo deve
restituire 4 in quanto sono necessari 4 viaggi (100 + 300 +200, 400 + 100 + 400, 300 + 400
e 350 + 500). [punti 4]
2. Determinare il costo asintotico dell'algoritmo proposto, motivando la risposta. [punti 1]
Soluzione.
integer TRAGHETTO( integer N, double W, double P[1..n] ) integer nv ← 0; // numero viaggi
integer i ← 1;
while ( i ≤ n ) do
// Imbarchiamo più veicoli possibili
double Wres ← W; // capacità residua del traghetto integer Nres ← N; // numero residuo di veicoli imbarcabili while ( i ≤ n and Wres ≥ R[i] and Nres > 0) then
Wres ← Wres – R[i];
Nres ← Nres - 1;
i ← i + 1;
endwhile nv ← nv + 1;
endwhile return nv;
Il costo asintotico è (n).
Un esercizio vagamente simile è presente nella dispensa di esercizi svolti. Però l'esercizio proposto qui differisce da quello nella dispensa perché include un ulteriore vincolo sul numero N di veicoli che il traghetto può trasportare per ogni viaggio. L'algoritmo deve quindi essere adattato di conseguenza.
Esercizio 5. Si consideri un file contenente unicamente i caratteri 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'; le frequenze con cui questi caratteri compaiono nel file sono indicate nella tabella sottostante:
A B C D E F G H
2% 15% 13% 21% 19% 18% 9% 3%
Eseguire manualmente l'algoritmo di compressione di Huffman visto a lezione utilizzando i caratteri e le frequenze date. Disegnare l'albero di compressione man mano che viene costruito, e mostrare
l'albero di compressione finale. [punti 3]
Scrivere la codifica della stringa 'ABECE' usando l'albero di compressione ottenuto al punto
precedente. [punti 1]
Esercizio 6. Un commesso viaggiatore ha clienti che risiedono in n città, tutte situate lungo una strada rettilinea. La città i-esima si trova a distanza d[i] (in Km, numero reale maggiore o uguale a zero) dall'inizio della strada, e ha c[i] clienti (intero maggiore o uguale a zero) del commesso viaggiatore; le città sono numerate da 1 a n, in ordine crescente di distanza dall'origine. Si faccia riferimento all'esempio seguente con n = 5 città
Il commesso viaggiatore parte dall'origine della strada e si muove verso la fine, senza mai tornare indietro. Poiché non ha abbastanza tempo per fermarsi in tutte le città, decide di non visitare una città se dista meno di 100km da quella precedentemente visitata (la distanza tra due città j e i, 1 ≤ j ≤ i ≤ n è d[i] – d[j]). Il commesso viaggiatore vuole risolvere il seguente problema:
determinare il massimo numero di clienti che può visitare, scegliendo un opportuno sottoinsieme di città che soddisfano il vincolo descritto sopra. Per risolvere il problema usa un algoritmo basato sulla programmazione dinamica (la soluzione greedy di visitare sempre la prima città a distanza
≥ 100km dall'ultima visitata non garantisce sempre di trovare il valore ottimo). A tale scopo, definisce m[i] come il massimo numero di clienti che può visitare scegliendo un opportuno sottoinsieme delle città {1, 2, … i}, nell'ipotesi che visiti la città i.
1. Quanto vale m[1]? [punti 1]
2. Scrivere la regola per calcolare m[i], 2 ≤ i ≤ n [punti 2]
3. Supponendo di aver calcolato i valori m[1], m[2], … m[n], come si fa a determinare la soluzione del problema, cioè il massimo numero di clienti che il commesso viaggiatore può visitare scegliendo un opportuno sottoinsieme delle n città? (Attenzione...) [punti 2]
4. Scrivere un programma che calcola la soluzione del problema (non è richiesto di calcolare le città da visitare, ma solo il massimo numero di clienti raggiungibili). [punti 2]
Soluzione. Si ha:
• m[1] = c[1]
• m[i] = c[i] + max{ m[j] | 1 ≤ j < i and d[i] – d[j] ≥ 100 }
Attenzione al fatto che la soluzione al problema NON è m[n], ma è max{ m[i] | 1 ≤ i ≤ n }
integer COMMESSOVIAGGIATORE( real d[1..n], integer c[1..n] ) integer m[1..n]; integer i, j, result;
m[1] ← c[1];
result ← m[1];
for i ← 2 to n do integer max ← 0;
for j ← 1 to i – 1 do
if (d[i] – d[j] ≥ 100 and m[j] > max) then max ← m[j];
endif;
endfor
m[i] ← c[i] + max;
if (m[i] > result) then result ← m[i];
0
d[2]
d[1]
d[3]
d[4]
d[5]
città
endif;
endfor return result;
