Corso di Algoritmi e Strutture Dati—Informatica per il ManagementProva Scritta, 18/7/2016

Corso di Algoritmi e Strutture Dati—Informatica per il Management

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

/ 4 / 2 / 2 / 2 / 4 / 2 / 4 / 2 / 4 / 6

Esercizio 1. Scrivere un algoritmo che, dato in input un array A[1..n] di interi arbitrari avente lunghezza n ≥ 2, restituisce:

• 1 se A è ordinato in senso non decrescente, ossia se A[1] ≤ A[2] ≤ … ≤ A[n];

• -1 se A è ordinato in senso decrescente, ossia se A[1] > A[2] > … > A[n];

• 0 se non vale nessuno dei due casi precedenti; [punti 4]

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

Soluzione. Si puo' fare tutto in una unica passata, confrontando i primi due elementi di A per decidere quale tra i primi due casi si puo' applicare, e verificare poi il resto

integer C

V

(integer A[1..n])

if ( A[1] ≤ A[2] ) then // siamo nel caso 1 oppure 0 for integer i ← 2 to n - 1 do

if ( A[i] > A[i+1] ) then return 0;

endif endfor return 1;

else // siamo nel caso -1 oppure 0

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

return 0;

endif endfor return -1;

endif

L'algoritmo di cui sopra ha costo O(n) nel caso peggiore, e O(1) nel caso migliore. Il caso migliore

si verifica, ad esempio, quando A = [1, 2, 1, …]. Si noti che è SBAGLIATO scrivere (come ha fatto

qualcuno) che “il caso migliore è O(1) e si verifica quando l'array ha due soli elementi”.

Esercizio 2. Si consideri il seguente albero binario:

Scrivere nelle caselle sottostanti i nomi dei nodi come comparirebbero durante una visita in profondità in ordine anticipato (pre-visita: visita radice; visita ricorsiva sottoalbero sinistro; visita

ricorsiva sottoalbero destro) [punti 2]

Scrivere nelle caselle sottostanti i nomi dei nodi come comparirebbero durante una visita in profondità in ordine posticipato (post-visita: visita ricorsiva sottoalbero sinistro; visita ricorsiva

sottoalbero destro; visita radice) [punti 2]

A

B C

D E

G H J

F

I

Esercizio 3. La mappa stradale di una città in cui tutte le strade sono a doppio senso di circolazione è organizzata come un grafo non orientato G = (V, E), dove V = {1, … n} è un insieme di n incroci, ed E  V  V è l'insieme dei tratti di strada (a doppio senso) che collegano due incroci. A causa di lavori di ristrutturazione, alcuni degli incroci non sono agibili, quindi nessuna delle strade a loro incidenti puo' essere attraversata. Ad esempio, nel caso sottostante gli incroci 2, 6, 8 non sono agibili, per cui il cammino minimo (quello che attraversa il numero minimo di archi) per chi deve spostarsi dall'incrocio 1 all'incrocio 9 è 1 → 3 → 5 → 4 → 7 → 9

Scrivere un algoritmo efficiente che, dato in input il grafo non orientato G = (V, E) e un array booleano P[1..n] (dove n è il numero di nodi in G) tale che P[i] = true se e solo se il nodo i è percorribile, determina la lunghezza del cammino minimo (cioé quello che attraversa il numero minimo di archi, se esiste) che collega il nodo 1 con il nodo n. Se tale cammino non esiste

l'algoritmo restituisce +. [punti 4]

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

Soluzione. Si modifica l'algoritmo di visita in ampiezza, evitando gli archi che portano a nodi non percorribili (cioè evitando i nodi w per i quali si abbia P[w] = false).

1

2

3

4

5

6 7

8

9

Esercizio 4. A lezione è stato illustrato il seguente algoritmo che esegue le mosse necessarie per risolvere il problema delle Torri di Hanoi con n dischi:

H

(Stack p1, Stack p2, Stack p3, integer n) if (n = 1) then

p3.push(p1.pop()) else

H

(p1, p3, p2, n-1) p3.push(p1.pop())

H

(p2, p1, p3, n-1) endif

Scrivere un algoritmo (modificando quello sopra, o sviluppandone uno diverso) che restituisca il numero di mosse necessarie per risolvere il problema delle Torri di Hanoi con n dischi. [punti 4]

Dare una stima del costo asintotico dell'algoritmo proposto, motivando la risposta. [punti 2]

Soluzione. La soluzione piu' semplice consiste nel modificare l'algoritmo di cui sopra (non serve tenere traccia dei tre stack, basta solo il parametro n = numero dischi)

integer H

(integer n) if ( n = 1 ) then

return 1;

else

return H

(n – 1) + 1 + H

(n – 1) ; endif

Questa soluzione ha costo O(2

), come l'algoritmo che “esegue” le mosse (la dimostrazione è stata vista a lezione; si noti che non si puo' applicare il Master Theorem perché l'equazione di ricorrenza non è del tipo che puo' essere risolta con esso).

Possiamo migliorare l'algoritmo osservando che le due chiamate ricorsive Hanoi(n – 1) restituiscono lo stesso valore, quindi possiamo effettuarne solo una:

integer H

(integer n) if ( n = 1 ) then

return 1;

else

return 2 * H

(n – 1) + 1;

endif

ottenendo un algoritmo di costo O(n).

In realtà si puo' risolvere il problema analiticamente: il numero di spostamenti S(n) soddisfa l'equazione di ricorrenza S(n) = 2S(n - 1) + 1, S(1) = 1, che ha come soluzione S(n) = 2

– 1. Il calcolo di S(n) può essere effettuato in tempo O(log n) usando l'algoritmo “veloce” per l'elevamento a potenza intera (https://en.wikipedia.org/wiki/Exponentiation_by_squaring); questa ulteriore ottimizzazione comunque non era richiesta, e tutti coloro che hanno descritto l'implementazione in tempo O(n) hanno ottenuto punteggio pieno.

Si noti che soluzioni del tipo:

integer H

(Stack p1, Stack p2, Stack p3, integer n)

integer k = 1;

if (n = 1) then

p3.push(p1.pop());

return k;

else

H

(p1, p3, p2, n-1) p3.push(p1.pop()) k ← k + 1;

H

(p2, p1, p3, n-1) endif

return k;

e simili sono errate, in quanto la variabile k è locale a ciascuna invocazione della procedura Hanoi(),

quindi il suo valore non viene “ereditato” in alcun modo dal chiamante. Il fatto che la funzione

sopra sia errata è evidente considerando che Hanoi() restituisce un valore, ma tale valore è ignorato

nell'invocazione delle chiamate ricorsive (nel ramo “else” dell'”if”). Come regola generale, ogni

funzione ricorsiva il cui valore venga ignorato dalle chiamate ricorsive denota quasi sicuramente un

errore.

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 scritti su celle adiacenti, e la testina di lettura-scrittura è posizionata sulla prima cifra a sinistra. La MdT deve scorrere il numero binario da sinistra a destra, e rimpiazzare la prima occorrenza della cifra 1 con 0.

A titolo di esempio, la tabella seguente mostra quale deve essere il contenuto finale del nastro in alcuni esempi.

Contenuto iniziale del nastro Contenuto finale del nastro

000 000

000101 000001

110010 010010

00001 00000

[punti 4]

Soluzione. Basta un unico stato q0:

Stato corrente Simbolo corrente Nuovo simbolo Nuovo stato Spostamento

q0 0 0 q0 right

q0 1 0 halt right

q0 blank blank halt right

Esercizio 6. Una emittente televisiva deve organizzare il palinsesto di una singola giornata di trasmissioni, composta da 24 ore (1440 minuti). L'emittente deve comporre il palinsesto scegliendo un opportuno sottoinsieme di n programmi a disposizione, aventi durate T[1], ... T[n] minuti rispettivamente. Tutte le durate sono numeri interi. Ciascun programma puo' essere mandato in onda al massimo una volta; inoltre, dopo ogni programma è necessario inserire un intervallo di 5 min da destinare agli spot pubblicitari. Tale intervallo deve essere inserito anche dopo l'ultimo programma della giornata.

Scrivere un algoritmo efficiente, basato sulla programmazione dinamica, che dati in input l'array delle durate T[1..n], restituisce true se e solo se esiste un opportuno sottoinsieme di programmi la cui durata complessiva, sommata alla durata degli intervalli pubblicitari in coda a ciascuno, sia esattamente uguale a 1440 minuti (cioè 24 ore). Ad esempio, considerando un caso semplice con n = 10 programmi aventi durate T = [500, 140, 180, 80, 310, 300, 200, 295, 60, 30] l'algoritmo deve restituire true in quanto scegliendo i programmi numero 1, 2, 3, 6, 8, si ottiene una durata totale pari a (500 + 5) + (140 + 5) + (180 + 5) + (300 + 5) + (295 + 5) = 1440 minuti. [punti 6]

Soluzione: E' il problema dello zaino, con l'unica variante che la durata effettiva di ciascun brano,

da considerare ai fini della programmazione dinamica, non è T[i] ma T[i] + 5, in quanto bisogna

sempre tenere conto dei 5 minuti in coda di pubblicità.