Parziale di Algoritmi e Strutture di Dati (A) Luned`ı 25 Marzo 2002
Nome:
Cognome:
Matricola:
Per un buon esito dell’esame, si consiglia di:
• scrivere in forma leggibile il proprio nome, cognome e matricola sul testo del compito e su ogni foglio consegnato;
• provare gli esercizi prima in brutta copia. Ricopiarli in bella copia e consegnare solo quest’ultima;
• non fatevi prendere dal panico, e neppure dalla noia. Un giusto livello di tensione `e ci`o che serve;
• svolgere il compito individualmente. Passare copiando `e dannoso per voi, e irrilevante per il docente.
Esercizio 1 (Punti: 4)
Si diano le definizioni di complessit`a computazionale di un algoritmo e di un problema.
Soluzione
La complessit`a computazione di un algoritmo `e la quantit`a di risorse che l’algoritmo richiede per terminare. Solitamente le risorse significative sono tempo e spazio. La complessit`a computazionale di un problema `e la complessit`a dell’algoritmo pi` u efficiente che lo risolve.
Esercizio 2 (Punti: 13)
1. L’operazione di forward shift su una sequenza sposta ogni elemento della sequenza di una posizione in avanti in modo circolare (quindi l’ultimo elemento viene spostato in prima posizione). Ad esempio il forward shift di h5, 4, 1, 3i `e h3, 5, 4, 1i. Sia A un vettore. Si scriva una procedura F orwardShif t(A) che implementa l’operazione di forward shift sulla se- quenza contenuta in A. Si calcoli la complessit`a computazionale pessima della procedura.
2. Sia k ≥ 0 un numero intero. L’operazione di forward k-shift su una se- quenza sposta ogni elemento della sequenza di k posizioni in avanti in modo circolare. Ad esempio il forward 2-shift di h5, 4, 1, 3i `e h1, 3, 5, 4i.
Sia A un vettore e k un numero intero tale che 0 ≤ k ≤ length(A). Si scri- va una procedura F astF orwardShif t(A, k) che implementa l’operazione di forward k-shift sulla sequenza contenuta in A. Si calcoli la complessit`a computazionale pessima della procedura.
3. Qual `e l’effetto delle chiamate di procedura F astF orwardShif t(A, 0) e
F astF orwardShif t(A, length(A))?
Soluzione Punto 1.
Algoritmo 1 ForwardShift(A) ForwardShift(A)
1:
x ← A[length(A)]
2:
for i ← langth(A) downto 2 do
3:
A[i] ← A[i − 1]
4:
end for
5:
A[1] ← x
Sia n = length(A). La complessit`a `e Θ(n).
Punto 2.
Ci sono almeno due soluzioni. La prima soluzione `e modulare (nel senso che usa la procedura F orwardShif t), non usa altre strutture di supporto, ma
`e inefficiente.
Algoritmo 2 FastForwardShift(A,k) FastForwardShift(A,k)
1:
for i ← 1 to k do
2:
F orwardShif t(A)
3:
end for
Sia n = length(A). Poich´e la complessit`a di F orwardShif t(A) `e Θ(n), la complessit`a di F astF orwardShif t(A, k) `e kΘ(n) = Θ(kn).
La seconda soluzione usa un vettore B di supporto ed `e pi` u efficiente.
Algoritmo 3 FastForwardShift(A,k) FastForwardShift(A,k)
1:
// 0 ≤ k ≤ length(A)
2:
j ← 1
3:
for i ← length(A) − k + 1 to length(A) do
4:
B[j] ← A[i]
5:
j ← j + 1
6:
end for
7:
for i ← length(A) downto k + 1 do
8:
A[i] ← A[i − k]
9:
end for
10:
for i ← 1 to k do
11:
A[i] ← B[i]
12:
end for
Sia n = length(A). Il primo ciclo for ha complessit`a Θ(k). Il secondo ciclo
Dunque la complessit`a di F astF orwardShif t(A, k) `e Θ(k)+Θ(n−k)+Θ(k) = Θ(n + k). Quindi questa versione `e pi` u efficiente.
Punto 3. L’effetto `e quello di lasciare inalterato il vettore A.
Esercizio 3 (Punti: 13)
Una lista singola `e una lista in cui gli oggetti hanno due campi: il campo chiave key e il campo next che punta all’oggetto successivo (manca quindi il campo prev).
1. Sia L una lista singola. Si scriva una procedura SingleListReverse(L) che inverte la sequenza contenuta in L senza usare altre strutture di dati come supporto. Si calcoli la complessit`a computazionale pessima della procedura.
2. Sia L una lista singola e x un puntatore ad un oggetto della lista L. Si scriva una procedura SingleListDelete(L, x) che cancella l’oggetto pun- tato da x dalla lista L. Si calcoli la complessit`a computazionale pessima della procedura.
Soluzione Punto 1.
Algoritmo 4 SingleListReverse(L) SingleListReverse(L)
1:
y ← NIL
2:
x ← head(L)
3:
while x 6= NIL do
4:
z ← next[x]
5:
next[x] ← y
6:
y ← x
7:
x ← z
8:
end while
9:
head(L) ← y
Sia n la lunghezza della lista. La procedura scorre per intero la lista e
dunque la complessit`a `e Θ(n).
Punto 2.
Algoritmo 5 SingleListDelete(L,x) SingleListDelete(L,x)
1:
v ← NIL
2:
w ← head(L)
3:
while key[x] 6= key[w] do
4:
v ← w
5:
w ← next[w]
6:
end while
7:
if v 6= N IL then
8:
next[v] ← next[x]
9:
else
10:
head(L) ← next[x]
11:
end if
Sia n la lunghezza della lista. Nel caso pessimo l’elemento da cancellare `e
in fondo alla lista. Quindi la complessit`a pessima `e Θ(n).
Parziale di Algoritmi e Strutture di Dati (B) Luned`ı 25 Marzo 2002
Nome:
Cognome:
Matricola:
Per un buon esito dell’esame, si consiglia di:
• scrivere in forma leggibile il proprio nome, cognome e matricola sul testo del compito e su ogni foglio consegnato;
• provare gli esercizi prima in brutta copia. Ricopiarli in bella copia e consegnare solo quest’ultima;
• non fatevi prendere dal panico, e neppure dalla noia. Un giusto livello di tensione `e ci`o che serve;
• svolgere il compito individualmente. Passare copiando `e dannoso per voi, e irrilevante per il docente.
Esercizio 1 (Punti 4)
Si dia la definizione di decidibilit`a di un problema.
Soluzione
Un problema `e decidibile se esiste almeno un algoritmo che lo risolve.
Esercizio 2 (Punti: 13)
1. L’operazione di backward shift su una sequenza sposta ogni elemento del- la sequenza di una posizione indietro in modo circolare (quindi il primo elemento viene spostato in ultima posizione). Ad esempio il backward shift di h5, 4, 1, 3i `e h4, 1, 3, 5i. Sia A un vettore. Si scriva una proce- dura BackwardShif t(A) che implementa l’operazione di backward shift sulla sequenza contenuta in A. Si calcoli la complessit`a computazionale pessima della procedura.
2. Sia k ≥ 0 un numero intero. L’operazione di backward k-shift su una sequenza sposta ogni elemento della sequenza di k posizioni indietro in modo circolare. Ad esempio il backward 2-shift di h5, 4, 1, 3i `e h1, 3, 5, 4i.
Sia A un vettore e k un numero intero tale che 0 ≤ k ≤ length(A). Si scriva una procedura F astBackwardShif t(A, k) che implementa l’oper- azione di backward k-shift sulla sequenza contenuta in A. Si calcoli la complessit`a computazionale pessima della procedura.
3. Qual `e l’effetto delle chiamate di procedura F astBackwardShif t(A, 0) e
F astBackwardShif t(A, length(A))?
Soluzione Punto 1.
Algoritmo 6 BackwardShift(A) BackwardShift(A)
1:
x ← A[1]
2:
for i ← 2 to langth(A) do
3:
A[i − 1] ← A[i]
4:
end for
5:
A[langth(A)] ← x
Sia n = length(A). La complessit`a `e Θ(n).
Punto 2.
Ci sono almeno due soluzioni. La prima soluzione `e modulare (nel senso che usa la procedura BackwardShif t), non usa altre strutture di supporto, ma `e inefficiente.
Algoritmo 7 FastBackwardShift(A,k) FastBackwardShift(A,k)
1:
for i ← 1 to k do
2:
BackwardShif t(A)
3:
end for
Sia n = length(A). Poich´e la complessit`a di BackwardShif t(A) `e Θ(n), la complessit`a di F astBackwardShif t(A, k) `e kΘ(n) = Θ(kn).
La seconda soluzione usa un vettore B di supporto ed `e pi` u efficiente.
Algoritmo 8 FastBackwardShift(A,k) FastBackwardShift(A,k)
1:
// 0 ≤ k ≤ length(A)
2:
for i ← 1 to k do
3:
B[i] ← A[i]
4:
end for
5:
for i ← k + 1 to length(A) do
6:
A[i − k] ← A[i]
7:
end for
8:
for i ← 1 to k do
9:
A[length(A) − k + i] ← B[i]
10:
end for
Sia n = length(A). Il primo ciclo for ha complessit`a Θ(k). Il secondo ciclo for ha complessit`a Θ(n − k). Infine, il terzo ciclo for ha complessit`a Θ(k).
Dunque la complessit`a di F astBackwardShif t(A, k) `e Θ(k)+Θ(n−k)+Θ(k) =
Punto 3. L’effetto `e quello di lasciare inalterato il vettore A.
Esercizio 3 (Punti: 13)
Una lista singola `e una lista in cui gli oggetti hanno due campi: il campo chiave key e il campo next che punta all’oggetto successivo (manca quindi il campo prev).
1. Sia L una lista singola. Si scriva una procedura SingleListReverse(L) che inverte la sequenza contenuta in L senza usare altre strutture di dati come supporto. Si calcoli la complessit`a computazionale pessima della procedura.
2. Sia L una lista singola e x un puntatore ad un oggetto della lista L. Si scriva una procedura SingleListDelete(L, x) che cancella l’oggetto pun- tato da x dalla lista L. Si calcoli la complessit`a computazionale pessima della procedura.
Soluzione Punto 1.
Algoritmo 9 SingleListReverse(L) SingleListReverse(L)
1:
y ← NIL
2:
x ← head(L)
3:
while x 6= NIL do
4:
z ← next[x]
5:
next[x] ← y
6:
y ← x
7:
x ← z
8:
end while
9:
head(L) ← y
Sia n la lunghezza della lista. La procedura scorre per intero la lista e
dunque la complessit`a `e Θ(n).
Punto 2.
Algoritmo 10 SingleListDelete(L,x) SingleListDelete(L,x)
1:
v ← NIL
2:
w ← head(L)
3:
while key[x] 6= key[w] do
4:
v ← w
5:
w ← next[w]
6:
end while
7:
if v 6= N IL then
8:
next[v] ← next[x]
9:
else
10:
head(L) ← next[x]
11:
