Study material for Algoritmi e Principi dell'Informatica, shared by the Studwiz community and reviewed by moderators.
Study material for Algoritmi e Principi dell'Informatica, shared by the Studwiz community and reviewed by moderators.
Import quality: text was extracted directly from the original document.
Representative passages recognised in different parts of the material. The full extracted text remains available to search, while this compact preview makes the page easier to read.
Algoritmi e Principi dell'Informatica Seconda Prova in Itinere 14 Febbraio 2014 Avvisi importanti Il tempo a disposizione è di 1 ora e 30 minuti. Se non verranno risolti in maniera soddisfacente gli esercizi 1, 2, (ossia ottenendo almeno 6 punti in totale tra i due) non si procederà alla correzione degli altri esercizi; l’esercizio facoltativo 4, sarà valutato solo se si saranno ottenuti almeno 13 punti nei primi 3. Esercizio 1 (punti 4/15-esimi) Si consideri un albero binario in cui ogni nodo o sia una foglia o abbia entrambi i figli. Quali sono l’altezza minima e massima di un tale albero con n nodi? NB: si richiede il valore preciso della funzione di n, non basta l’ordine di grandezza! Esercizio 2 (punti 3/15-esimi) E’ noto che esistono linguaggi riconoscibili in tempo lineare da automi a pila deterministici e da macchine di Turing a k nastri ma non da macchine di Turing a nastro singolo. Esistono anche linguaggi regolari non riconoscibili in tempo lineare da macchine di Turing a nastro singolo? Giustificare brevemente la risposta. Esercizio 3 (punti 8/15-esimi) Si descriva un algoritmo che, dato un BST (Binary Search Tree) stabilisca se esso possa essere colorato in modo tale da diventare un albero rosso-nero (RB). NB: non si chiede di costruire un algoritmo di colorazione, ma solo di stabilire se ciò sia possibile. Si ricordi inoltre che per convenzione in un albero RB tutte le foglie sono NIL, T.NIL per la precisione, e nere. Si valuti la complessità temporale dell’algoritmo. Esercizio 4, facoltativo (punti 3/15) Si formalizzi la seguente definizione informale di complessità spaziale di una macchina di Turing a nastro bidimensionale: Il nastro della macchina è costituito dal primo quadrante di un piano cartesiano a coordinate intere. La complessità spaziale è…
First page of the document.
