Corso di Algoritmi e Strutture Dati—Informatica per il ManagementProva Scritta, 12/1/2017

Corso di Algoritmi e Strutture Dati—Informatica per il Management

Prova Scritta, 12/1/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

/ 5 / 4 / 2 / 5 / 4 / 2 / 4 / 2 / 4

Esercizio 1. La curva di Koch è una figura frattale che può essere disegnata in modo ricorsivo: si parte da un segmento S che viene diviso in tre parti uguali S

, S

, S

; si rimuove S

, e lo si rimpiazza con due nuovi segmenti T

, T

della stessa lunghezza di quello rimosso e disposti come i lati di un triangolo equilatero avente come base S

(si faccia riferimento alla figura sotto). A questo punto si applica nuovamente il procedimento su S

, T

, T

e S

. L'algoritmo può essere rappresentato con lo pseudocodice seguente:

K OCH ( segmento S, int n ) if (n == 0) then

draw(S); // (*)

else

dividi S in tre parti uguali S

, S

, S

// (*) siano T

, T

i lati di un triangolo equilatero con base S

// (*)

K OCH (S

, n – 1);

K OCH (T

, n – 1);

K ^OCH (T

, n – 1);

K OCH (S

, n – 1);

endif

La figura mostra alcuni esempi di curva di Koch che si possono ottenere con vari valori di n; si nota come a valori elevati corrisponda una curva più dettagliata.

Assumendo che le righe contrassegnate con (*) richiedano tempo di esecuzione O(1), determinare il costo asintotico dell'algoritmo K ^OCH (S, n) in funzione di n, motivando la risposta. [punti 5]

Soluzione. L'algoritmo ha costo Θ(4

); per rendersi conto di ciò è possibile contare i nodi dell'albero di ricorsione, oppure “srotolare” l'equazione di ricorrenza T(n) = 4 T(n - 1) + c (tale equazione di ricorrenza non può essere risolta col Master Theorem, perché non ha la struttura richiesta per la sua applicazione)

In questo esercizio sono state indicate le equazioni di ricorrenza più fantasiose, come ad esempio T(n) = 4 T(n/4), T(n) = 4 T((n - 1)/4), eccetera.

n = 0

n = 1

S

S

T

T

n = 2

n = 3

Esercizio 2. Una rete di distribuzione dell'energia elettrica ha la struttura di un albero binario. Alla radice dell'albero si trova la centrale elettrica, mentre ciascuna foglia rappresenta un punto di consumo (ad esempio, uno stabilimento industriale). Ad ogni nodo v è associato un valore reale v.val; inizialmente, a ciascuna foglia è associata l'energia consumata (in Kw), mentre i valori di tutti gli altri nodi sono indefiniti.

Scrivere un algoritmo ricorsivo che, dato in input un riferimento alla radice T dell'albero, memorizzi in ciascun nodo n diverso da una foglia la somma dei valori presenti in tutte le foglie del sottoalbero avente n come radice. L'albero T è garantito essere non vuoto Ad esempio, considerando l'albero a sinistra in cui le foglie sono etichettate con i consumi indicati, l'algoritmo deve modificare i valori negli altri nodi come riportato a destra. Notare che il valore presente nella radice (16, in questo caso) indica l'energia che la centrale elettrica deve fornire per poter soddisfare tutte le richieste.

[punti 4]

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

Soluzione. Si può applicare un algoritmo di post-visita modificato. L'algoritmo seguente setta il valore contenuto nel nodo v pari alla somme dei valori presenti nei figli (che vengono ricorsivamente calcolati sul valore dei loro figli, fino alle foglie).

C ^ONSUMO E ^LETTRICO ( Tree v ) if (v = null) then

return;

else

if ( v.left = null and v.right = null ) then

return; // è una foglia, non modifichiamo niente else

C ONSUMO E LETTRICO (v.left);

C ^ONSUMO E ^LETTRICO (v.right);

v.val ← 0;

if ( v.left ≠ null ) then v.val ← v.val + v.left.val;

endif

if ( v.right ≠ null ) then v.val ← v.val + v.right.val;

endif endif endif

3

2

4 1 6

16

8 8

5 3 8

2

4 1 6

Centrale elettrica

Punti di consumo

Si presti attenzione al fatto che l'esercizio chiedeva di modificare il contenuto dei nodi non foglia

con i valori corretti. Alcune soluzioni presentate erano “quasi” corrette, nel senso che calcolavano

i valori ma non li memorizzavano nei nodi come richiesto.

Esercizio 3. Si consideri un min-heap binario contenente valori interi, inizialmente vuoto.

Disegnare la struttura dell'albero che rappresenta il min-heap dopo ciascuna delle operazioni seguenti (ogni operazione viene eseguita sullo heap che risulta al termine di quella precedente):

1. Inserimento 15 2. Inserimento 7 3. Inserimento 10 4. Inserimento 2 5. Inserimento 1

6. Cancellazione del minimo 7. Inserimento 5

8. Inserimento 3

9. Cancellazione del minimo

[Punti 5]

In questo esercizio è fondamentale ricordarsi che uno heap gode di due proprietà: 1) proprietà di struttura, e 2) proprietà di contenuto. La proprietà di struttura richiede che lo heap sia rappresentato da un albero completo fino al penultimo livello, e tutte le foglie dell'ultimo livello siano “accatastate” a sinistra. Questo significa che nessuno degli alberi seguenti è uno heap, perché questa proprietà viene violata (i primi due non sono completi fino al penultimo livello; il terzo non ha le foglie “accatastate” a sinistra):

Oltre a questo, occorre riportare il contenuto dei nodi in modo consistente: spesso ho visto che il

contenuto dei figli sinistro e destro veniva scambiato arbitrariamente, il che non è corretto.

Esercizio 4. La cabina di una funivia ha una portata massima di 1000 kg ed è in grado di contenere al massimo 10 persone per volta. Alla partenza sono presenti n > 0 persone aventi pesi rispettivamente p[1], p[2], … p[n]. Le persone vengono fatte salire una alla volta, iniziando da quella di peso p[1], poi p[2] e così via, riempiendo la cabina il più possibile rispettando i vincoli di cui sopra. Naturalmente, ogni passeggero pesa molto meno 1000 kg!

Scrivere un algoritmo efficiente che, dato in input l'array p[1..n] di numeri reali, determina il numero minimo di viaggi che sono necessari per trasportare tutte le persone a destinazione (si

considerino solo i viaggi di andata). [punti 4]

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

Soluzione.

integer algoritmo F ^UNIVIA ( double p[1..n] )

int nv ← 0; // numero viaggi

int i ← 1;

while ( i ≤ n ) do

double Cres ← 1000; // capacità residua della cabina int nres ← 10; // numero residuo di passeggeri while ( i ≤ n and Cres ≥ p[i] and nres > 0 ) do

Cres ← Cres – p[i];

nres ← nres – 1;

i ← i + 1;

endwhile nv ← nv + 1;

endwhile return nv;

Costo Θ(n)

Esercizio 5. Un investitore dispone di S euro (valore intero positivo) che intende investire per un certo periodo di tempo, ad esempio 10 anni. A questo scopo gli vengono proposte n quote di fondi di investimento; egli può acquistare oggi la quota i-esima per C[i] euro (valori interi positivi), ottenendo fra 10 anni un guadagno netto di G[i] euro. L'investitore deve quindi scegliere un opportuno sottoinsieme delle n quote, rispettando i vincoli seguenti: (i) ogni quota può essere acquistata al più una volta; (ii) il costo totale delle quote acquistate deve essere minore o uguale a S;

(iii) il guadagno totale deve essere massimo possibile. Più formalmente, è chiesto di determinare un opportuno sottoinsieme di quote tali che il loro costo sia minore o uguale a S, e il loro guadagno netto sia massimo possibile.

1. Scrivere un algoritmo efficiente per determinare il massimo guadagno complessivo che è possibile ottenere (per risolvere il problema in modo corretto è necessario usare la

programmazione dinamica). [punti 4]

2. Determinare il costo asintotico dell'algoritmo proposto. [punti 2]

Soluzione. Algoritmo dello zaino basato sulla programmazione dinamica.

Esercizio 6. Determinare l'albero dei cammini di costo minimo nel seguente grafo orientato pesato, utilizzando il nodo s come sorgente. Scrivere all'interno di ciascun nodo la sua distanza dalla sorgente, ed evidenziare gli archi che fanno parte dell'albero dei cammini di costo minimo. Quale algoritmo tra quelli visti a lezione utilizzate per determinare i cammini di costo minimo? [punti 4]

Soluzione. Occorre usare l'algoritmo di Bellman-Ford, perché sono presenti archi di peso negativo.

L'albero risultante dei cammini minimi è il seguente:

L'algoritmo di Dijkstra non può essere utilizzato, perché ci sono archi di peso negativo. Non è possibile sommare un peso costante per eliminare i pesi negativi: questo è riportato nei lucidi per mostrare che non produce il risultato corretto!!!

L'algoritmo di Prim non può essere utilizzato, perché serve a calcolare un Minimum Spanning Tree, che è diverso dall'albero dei cammini minimi.

s 5

6

4

3 -2

12

-4 4

-8

3

s

5

3

7

9

4 5

6

4

3 -2

12

-4 4

1 -8

3