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 Prin Informatica Appello del 25 Febbraio 2016 2 ore e 30 minuti. Chi deve sostenere solo il modulo di Informatica teorica deve svolgere gli Esercizi 1 e 2 in 1 ora e 15 minuti. Chi deve sostenere solo il modulo di Informatica 3 deve svolgere gli Esercizi 3 e 4 in 1 ora e 15 minuti. NB: i punti attribuiti ai singol i esercizi hanno senso solo con hanno valore puramente indicativo. Esercizio 1 (Punti 9) 1) Si definisca formalmente il seguente modello di automa, chiamato macchina di Turing monodirezionale ad un nastro (MTM1). Una MTM1 è un accettore nondeterministico (non effettua quindi traduzioni) dotato di un nastro di ingresso e un nastro di memoria. Il funzionamento è analogo a quello di una MT tradizionale, a parte il movimento delle due testine dei nastri: esso può essere solamente S (stop) o R (right). 2) Si confronti la capacità espressiva delle MTM1 con i modelli visti a lezione. 3) 1 e se ne valuti l 'eventuale differenza di capacità espressiva. Esercizio 2 (Punti 8) Si consideri il seguente insieme. S = { i | La macchina di Turing Mi termina la sua esecuzione in meno di 100 passi per qualche ingresso } S è ricorsivamente enumerabile? S è ricorsivo? Giustificare brevemente le risposte. Esercizio 3 (Punti 7) Sia dato un insieme di n interi distinti. Si descriva un algoritmo che restituisce il k -esimo elemento più piccolo e se ne valuti la complessità; ov viamente la valutazione della soluzione proposta terrà conto della complessità ottenuta. Nella specifica della soluzione è possibile far riferimento ad algoritmi noti, specificandone con precisione funzionalità e complessità. Esercizio 4 (Punti 9) Sia T un albero binario. Sia t un suo nodo e siano t.left e t.right il sottoalbero sinistro e destro di t. Denotiamo con nodi(t) il numero di nodi del…
First page of the document.
