Corso di Algoritmi e Strutture Dati—Informatica per il ManagementProva Scritta, 9/2/2017

Corso di Algoritmi e Strutture Dati—Informatica per il Management

Prova Scritta, 9/2/2017

• 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 / 4 / 6 / 6 / 4 / 2 / 2 / 2

Esercizio 1. Una colonia di batteri viene posta all'interno di un contenitore da laboratorio. Sia B(n) il numero di batteri presenti nel contenitore dopo n giorni, n = 1, 2, … . Supponiamo che B(n) soddisfi la regola seguente:

B(n)= { B(n−3)+ B(n−4) ^{1 se 1≤n≤4} se 5≤n≤10 B(n−3)+ B(n−4)−B(n−10) se n>10

1. Scrivere un algoritmo efficiente che, dato in input un intero n ≥ 1, restituisca il valore B(n).

[punti 4]

2. Determinare il costo asintotico dell'algoritmo di cui al punto precedente, motivando la

risposta [punti 2]

Soluzione. Questo esercizio può essere risolto in modo simile al calcolo dei numeri di Fibonacci.

Un possibile algoritmo che richiede tempo O(n) e spazio O(n) è il seguente integer B

(integer n)

integer B[1..n];

for integer i ← 1 to n do if (i ≤ 4) then

B[i] ← 1;

else

if (i ≤ 10) then

B[i] ← B[i - 3] + B[i – 4];

else

B[i] ← B[i – 3] + B[i – 4] – B[i – 10];

endif endif endfor return B[n];

E' anche possibile una soluzione più complessa, che richiede tempo O(n) ma spazio O(1), usando un buffer circolare per tenere traccia degli ultimi 10 valori di B, che sono quelli realmente necessari per calcolare il valore successivo.

La soluzione ricorsiva basata sull'implementazione dell'equazione di ricorrenza era estremamente inefficiente:

integer B

(integer n) if (n ≤ 4) then

return 1;

else

if (n ≤ 10) then

return B

(n - 3) + B

(n - 4);

else

return B

(i – 3) + B

(i – 4) – B

(i – 10);

endif

endif

Il costo asintotico T(n) soddisfa l'equazione di ricorrenza seguente:

T (n)= { T (n−3) + T (n−4) + 1 ^{1 se 1≤n≤4} se 5≤n≤10 T (n−3) + T (n−4) + T (n−10) + 1 se n>10

Si presti attenzione che nel caso n > 10 l'espressione si differenzia da quella di B(n) perché ha tutte somme! T(n) indica il numero di chiamate ricorsive della funzione B

, quindi se n > 10 il numero di invocazioni ricorsive è pari alla somma del numero di invocazioni necessarie per calcolare B

(n – 3), più il numero di invocazioni necessarie per calcolare B

(n – 4), più il numero di invocazioni necessarie per calcolare B

(n – 10).

La soluzione dell'equazione di ricorrenza può essere calcolata in modo simile a quanto fatto per i numeri di Fibonacci (dato che i dettagli non sono banali, mi aspettavo che tutti avrebbero scritto l'algoritmo lineare, che è molto simile a quello visto a lezione per i numeri di Fibonacci).

Osservando che T(n) è una funzione crescente, possiamo scrivere:

T (n) = T (n−3)+T (n−4)+T (n−10)+1

≥ T (n−10)+T (n−10)+T (n−10)+1

≥ 3 T (n−10)

≥ 9T (n−20)

≥ …

≥ 3

T (n−k×10)

da cui si può concludere che T(n) = (3

), cioè il costo asintotico dell'algoritmo ricorsivo è

almeno esponenziale in n con base 3

.

Esercizio 2. Per ciascuna delle seguenti relazioni, indicare nella colonna di destra se è vera (V) o

falsa (F). [punti 4]

Vero (V) o Falso (F)

n(n+1)

2 = O(n

) ^V n

+1000 n

=O(n

) ^F

n log n = O(n

) ^V n

log n = O(n

) ^F

n log n = O(n) ^F

log n = O(n) ^V

n = O(n log n) ^V

n

= O (n log n) ^F

n+log(n) = O(log n) ^F

n(n+1)(n+2) = O(n

) ^F

Esercizio 3. Un albero binario non vuoto si definisce degenere se ogni nodo diverso da una foglia ha un solo figlio (per convenzione, si assume che l'albero vuoto sia degenere). Ad esempio, gli alberi seguenti sono degeneri:

Scrivere un algoritmo D

(t) che, dato in input un riferimento alla radice t di un albero binario non vuoto, rappresentato mediante puntatori ai figli, restituisce true se e solo se l'albero è degenere.

[punti 6]

Soluzione.

bool

D

return true;

else

if ( T.left ≠ null and T.right ≠ null) then return false;

else

// se arriviamo in questo punto siamo certi che (i) T non è vuoto, e // (ii) Almeno uno tra T.left e T.right è vuoto (anche entrambi) return

D

D

endif endif

Esercizio 4. Consideriamo una sequenza S[1..n] di n ≥ 1 caratteri, composta solamente di lettere minuscole dell'alfabeto. Scrivere un algoritmo efficiente per determinare la lunghezza della sottosequenza più lunga, composta da caratteri che occupano posizioni adiacenti in S, che risulti ordinata in senso non decrescente (in base al consueto ordinamento alfabetico 'a' < 'b' < … < 'z'). In altre parole, vogliamo determinare la lunghezza della più lunga sottostringa S[i..j] tale che S[i] ≤ S[i + 1] ≤ … ≤ S[j].

Ad esempio, se S = “algoritmi”, l'algoritmo restituisce 3 in quanto la sottosequenza più lunga composta da caratteri adiacenti non decrescenti è “gor”; se S = “dijkstra”, l'algoritmo restituisce 6 in quanto la sottosequenza più lunga è “dijkst”. Infine, se S = “abcaabdfgazaz", l'algoritmo restituisce 6. (Suggerimento: sia L[i] la lunghezza massima delle sottostringhe non

decrescenti di S aventi S[i] come ultimo carattere...) [punti 6]

Soluzione. Si applica quasi lo stesso algoritmo che è stato visto a lezione per il calcolo del sottovettore di somma massima. Sia L[i] la lunghezza massima delle sottostringhe di S i cui caratteri siano in ordine non decrescente, con il vincolo che l'ultimo carattere sia S[i]. Possiamo calcolare L[i], i = 1, … n usando la programmazione dinamica. Alla fine, il risultato sarà il massimo tra i valori L[i]. L'algoritmo seguente risolve il problema in tempo Θ(n).

integer

S

S

C

L[1] ← 1;

integer Lmax ← 1;

for integer i ← 2 to n do if (S[i - 1] ≤ S[i]) then L[i] ← L[i - 1] + 1;

else

L[i] ← 1;

endif

if ( L[i] > Lmax ) then Lmax ← L[i];

endif endfor return Lmax;

Per questo esercizio sono state presentate le “soluzioni” più fantasiose, basate su esercizi di programmazione dinamica che nulla avevano a che fare con quanto richiesto dal problema.

Esercizio 5. Una rete stradale viene rappresentata mediante un grafo orientato pesato G = (V, E, w), dove gli n nodi rappresentano altrettanti incroci, e sono indicati dagli interi 1, 2, … n, e gli archi rappresentano segmenti stradali che connettono coppie di nodi. Trattandosi di un grafo orientato, gli archi possono essere attraversati solo lungo la direzione corretta. Una auto elettrica si trova inizialmente nel nodo 1 con la batteria totalmente carica. Supponiamo che la batteria possa immagazzinare P Joule di energia. La funzione peso w associa a ciascun arco orientato (u, v) un valore reale positivo w(u, v) che rappresenta l'energia (in Joule) che l'auto consuma per attraversare il tratto di strada rappresentato dall'arco (u, v). In corrispondenza di alcuni incroci sono disponibili dei punti di ricarica, in cui è possibile caricare completamente la batteria. In particolare, è dato un array R[1..n] di valori booleani, tali che R[i] = true se e solo se nel nodo i è presente una stazione di ricarica.

Definire un algoritmo efficiente che, dato in input il grafo G = (V, E, w), la capacità P della batteria e l'array R[1..n], restituisca true se e solo se esiste un cammino che consente all'auto elettrica di andare dal 1 al nodo n senza esaurire la batteria lungo una strada; se necessario, l'auto può fare rifornimento presso uno o più nodi lungo il tragitto presso i quali sono presenti stazioni di ricarica.

(Suggerimento: sia d[v] l'energia minima che si consuma per raggiungere il nodo v partendo dal nodo 1, dopo aver eventualmente fatto il pieno in v se è presente una stazione di ricarica) [punti 4]

Determinare il costo asintotico dell'algoritmo proposto, motivando la risposta. [punti 2]

Soluzione. Si può applicare l'algoritmo di Dijkstra o Bellman-Ford per il calcolo dei cammini minimi usando il nodo 1 come sorgente. L'algoritmo deve essere modificato: per ogni nodo v si denota con d[v] il consumo minimo di energia richiesto per andare dalla sorgente al nodo v. Se v è un nodo di ricarica (R[v] = true) e il nodo v è raggiungibile senza restare a piedi lungo la strada, occorre settare d[v] = 0. Questo si giustifica considerando che in v si può caricare completamente la batteria, quindi ripartendo dal nodo v è come se si fosse consumato zero.

Supponendo di usare l'algoritmo di B-F, si ottiene lo pseudocodice seguente. Possiamo eliminare le parti dell'algoritmoche non servono, come ad esempio l'array dei predecessori; le modifiche sono evidenziate.

boolean

R

double d[1..n];

for v ← 1 to n do d[v] ← +∞;

endfor d[1] ← 0;

for i ← 1 to n - 1 do for each (u,v) in E do

if ( d[u] + w(u,v) ≤ P and d[u] + w(u,v) < d[v] ) then if ( R[v] ) then

d[v] ← 0;

else

d[v] ← d[u] + w(u,v);

endif endif endfor endfor

return (d[n] < +∞);

Il costo asintotico dell'algoritmo è quello dell'algoritmo di B-F, cioè O(nm)

Qualcuno ha proposto soluzioni in cui il valore di P veniva decrementato per ogni arco attraversato. Questo non è corretto, in quanto l'algoritmo di Dijkstra o B-F esplora percorsi alternativi in cui i consumi possono risultare diversi. Quindi non si può usare una unica variabile P per tenere traccia del consumo, ma occorre fare riferimento alla quantità d[u] + w(u, v)

Esercizio 6. Si consideri il seguente grafo non orientato.

1. Supponiamo che gli archi evidenziati rappresentino l'albero prodotto da una visita in ampiezza (visita BFS). Rappresentare il grafo mediante liste di adiacenza in modo che l'algoritmo di visita produca l'albero mostrato. Si assuma che l'algoritmo di visita prenda in considerazione gli archi nell'ordine in cui sono indicati nelle liste di adiacenza. Indicare da

quale nodo è iniziata la visita. [punti 2]

2. Supponiamo che gli archi evidenziati rappresentino un Minimum Spanning Tree (MST) del grafo. Nell'ipotesi in cui i pesi dei dieci archi siano tutti e soli gli interi dell'insieme {1, 2, … 10}, assegnare un peso a ciascun arco in modo da ottenere il MST mostrato. E' richiesto l'uso di tutti i pesi {1, 2, … 10}; archi diversi devono avere pesi diversi. [punti 2]

Soluzione. La visita inizia dal nodo B. Per ottenere un MST come quello indicato è sufficiente assegnare agli archi evidenziati i pesi minori (da 1 a 6).

D

A B

E

C

F

G