Secondo parziale di Algoritmi e Principi dell'Informatica per il corso di Computer Engineering presso Politecnico di Milano. Materiale proveniente dall’archivio storico Studwiz e classificato per la consultazione online.
Secondo parziale di Algoritmi e Principi dell'Informatica per il corso di Computer Engineering presso Politecnico di Milano. Materiale proveniente dall’archivio storico Studwiz e classificato per la consultazione online.
Qualità dell’importazione: il testo è stato estratto direttamente dal documento originale.
Passaggi rappresentativi riconosciuti nelle diverse parti del materiale. Il testo completo resta presente nella pagina per la ricerca, mentre l’anteprima compatta rende più semplice la lettura.
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 è…
Prima pagina del documento.
