Esame I.A. 1 settembre 2020
Soluzioni
1 Esercizio 1
Data la famiglia di equazioni di ricorrenza indicata sotto, per valori dia interi positivi, individuare i limiti superiori e inferiori più stretti possibile:
T (n) = aT (bn/2c) + na−1 n ≥ 2
1 n < 2
Soluzione Data la forma della ricorrenza, è possibile utilizzare il Master Theorem:
• Pera = 1, abbiamo α = log21 = 0, β = 0, da cui T (n) = Θ(log n);
• Pera = 2, abbiamo α = log22 = 1, β = 1, da cui T (n) = Θ(n log n);
• Pera = 3, abbiamo α = log23 = 2, β = 2, da cui T (n) = Θ(n2);
• Proseguendo, si ottiene che in generalelog2a < a − 1 per tutti i valori interi a ≥ 3, pertanto si ottieneT (n) = Θ(na−1).
2 Esercizio 2
Un albero binario è simmetrico se il sottoalbero sinistro della radice è un’immagine speculare del sottoal- bero destro della radice. Nella figura sotto, l’albero binario a sinistra non è simmetrico, mentre quello di destra lo è. Scrivere un programma in python isSymmetric(T ) che prenda in input un albero binario T non vuoto e restituiscaTrue se T è simmetrico, False altrimenti.
1
Soluzione Un sottalbero è simmetrico se i suoi sottoalberi destro e sinistro sono speculari. Due sot- toalberi t1, t2 sono speculari se il sottoalbero sinistro di t1 è speculare al sottoalbero destro di t2 e il sottoalbero destro dit1 è speculare al sottoalbero sinistro di t1. Il caso base è dato da due nodi nulli (si ritornaTrue) o da uno nodo nullo e un nodo non nullo (si ritorna False). Una possibile implementazione è la seguente:
c l a s s T r e e N o d e:
def _ _ i n i t _ _( self , tL , tR ): s e l f . l e f t = tL
s e l f . r i g h t = tR
def i s S y m m e t r i c ( T ):
r e t u r n i s M i r r o r e d ( T . left , T . r i g h t )
def i s M i r r o r e d ( tL , tR ):
if tL is N o n e and tR is N o n e : r e t u r n T r ue
e l i f tL is not N o n e and tR is not N o ne :
r e t u r n i s M i r r o r e d ( tL . right , tR . l e f t ) and i s M i r r o r e d ( tL . left , tR . r i g h t ) e l s e :
r e t u r n F a l s e
Per testarla sugli alberi di esempio forniti nell’immagine sopra, è possibile utilizzare il seguente pro- gramma:
# A l b e r o n e l l a f i g u r a di e s e m p i o a s i n i s t r a
T l e f t = T r e e N o d e ( T r e e N o d e ( T r e e N o d e ( T r e e N o d e (None, N o n e) , T r e e N o d e (None, N o n e) ) , T r e e N o d e ( T r e e N o d e (None, No n e) , N o n e) ) , T r e e N o d e ( T r e e N o d e (None, No n e) , T r e e N o d e ( None, N o n e) ) )
p r i n t(" Il p r i m o a l b e r o e ‘ s i m m e t r i c o : ", i s S y m m e t r i c ( T l e f t ) )
# A l b e r o n e l l a f i g u r a di e s e m p i o a d e s t r a
T r i g h t = T r e e N o d e ( T r e e N o d e ( T r e e N o d e (None, T r e e N o d e (None, N o n e) ) , T r e e N o d e (None, N o n e) ) , T r e e N o d e ( T r e e N o d e (None, N on e) , T r e e N o d e ( T r e e N o d e (None, No n e) , N o n e) ) ) p r i n t(" Il s e c o n d o a l b e r o e ‘ s i m m e t r i c o : ", i s S y m m e t r i c ( T r i g h t ) )
La procedura effettua una visita su entrambi gli alberi, e quindi ha complessitàΘ(n).
3 Quiz
Dato un vettore composto dai seguenti elementi: 15,20,10,18. Quali sono i passi intermedi di ordinamento quando questo viene ordinato utilizzando l’algoritmo Insertion Sort?
X 15,20,10,18 – 10,15,20,18 – 10,15,18,20 – 10,15,18,20.
• 15,18,10,20 – 10,18,15,20 – 10,15,18,20 – 10,15,18,20.
• 15,10,20,18 – 15,10,18,20 – 10,15,18,20.
• 10, 20,15,18 – 10,15,20,18 – 10,15,18,20.
2
Se tutti gli elementi di un vettore sono uguali, ad esempio [1,1,1,1,1,1], qual è la complessità computazionale dell’Insertion Sort?
• O(2n)
• O(n2) X O(n)
• Nessuna delle altre risposte
Affinché l’algoritmo di ricerca binaria possa funzionare correttamente, è necessario che il vet- tore di elementi all’interno del quale effettuare la ricerca sia:
• Inserito in una pila
• Inserito in un mucchio
• Non ordinato X Ordinato
Quali dei seguenti algoritmi di ordinamento non sono stabili?
• Bubble sort
• Merge sort X Selection sort
• Insertion sort
In quale caso una coda circolare può essere considerata piena?
• read = (read + 1) % size
• write = (write + 1) % size X read = (write + 1) % size
• read = -1
3
