Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

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 (MTM 1). Una MTM 1 è 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 solament e S (stop ) o R (right ). 2) Si confronti la capacità espressiva delle MTM 1 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 . Ne lla 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. Denot iamo con nodi(t) il numero di nodi del sottoalbero radicato in t. Un albero binario si dice perfettamente bilanciato quando per ogni suo nodo t la differenza tra il numero dei nodi dei due sottoalberi di t è in valore assoluto al più 1: | nodi (t.left ) - nodi (t.right Si definisca un algoritmo che, dato in input un nodo t, t è perfettamente bilanciato. Tracce di soluzioni Esercizio 1 1) A = , stato iniziale q 0 Q, stati finali F Q Funzione di transizione : (Q \ F) (Q {S, R}2) Configurazione : per comodità usiamo come seconda componente la stringa in ingr esso ancora da leggere (cioè la parte destra della stringa , testina inclusa ); per la terza componente , che rappresenta il nastro , indichiamo la parte scritta e visitata dalla macchina (cioè la parte sinistra , testina inclusa ). | -- < , .x, y. .c>, se ( , , m1, m2) (q,a,b) dove = se m 1 = = a c = se m 2 = S altrimenti c = _ (blank ) x L(A) sse | -*- , qF F. 2) Una MTM 1 accede solo ad una cella di memoria (quella corrente ) e non può in alcun modo ritornare sulla parte sinistra del nastro di memoria . Questa informazione è finita ( ) e può . Per questo motivo le MTM 1 definisco no tutti e soli i linguaggi Regolari . 3) . Esercizio 2 S1 è ricorsivo (e quindi anche ricorsivamente enumerabile). Infatti basta verificare se la macchina si arresta entro 99 passi per qualche stringa di lunghezza