API 2016 02 25

Pagina 1

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…