Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

Algoritmi e Principi dell’Informatica Appello del 14 Febbraio 2018 Chi deve sostenere l’esame integrato (API) deve svolgere tutti gli esercizi in 2 ore. Chi deve sostenere solo il modulo di Informatica teorica deve svolgere gli Esercizi 1 e 2 in 1 ora. Chi deve sostenere solo il modulo di Informatica 3 deve svolgere gli Esercizi 3 e 4 in 1 ora. NB: i punti attribuiti ai singoli esercizi hanno senso solo con riferimento all’esame integrato e hanno valore puramente indicativo. Esercizio 1 (8 punti) Sia L il linguaggio delle parole in {a,b,c}* della forma a n bn/3 cn mod 3 , con n>1. Usando il formalismo a potenza minima, definire il linguaggio L. Esercizio 2 (8 punti) Sia m il numero di Goedel di una MT che calcola la funzione f(x). Si dica, motivando la ri sposta, se le seguenti funzioni sono calcolabili: 1) g 1(x) = f(m); 2) g 2(x) = f(x); 3) g 3(x) = f(x) -9 se f(x) > 10,  altrimenti; 4) g 4(x) = f x(x) se x = m, 1 altrimenti. Esercizio 3 (8 punti) Considerato il linguaggio L dell’esercizio 1, definire la comp lessità temporale e spaziale di una MT a nastro singolo e di una macchina RAM che riconoscano L. Nel caso della macchina RAM, si consideri sia il criterio di costo costante che quello di costo logaritmico. Esercizio 4 (8 punti) Si consideri un vettore di numeri interi, contenente l numeri. I l valore massimo contenuto all’ interno del vettore è m. Si progetti un algoritmo che controlla quali degli interi contenuti nel vettore sono quadrati perfetti e se ne calcoli la complessità in funzione della lunghezza d el vettore l e del valore massimo m. Tracce delle soluzioni Esercizio 1 Il linguaggio L è definibile mediante PDA. L’automa carica sulla pila i primi n simboli a. Alla prima occorrenza di b in izia a spilare tre simboli dalla pila ogni b letta (mediante una transizione che consuma una b dall’input e due successive epsilon mosse). Se sulla pila non avanzano simboli allora l’automa va in accettazione con una epsilon mossa che verifica la presenza di Z0 sulla pila. Altrimenti, deve essere presente un resto, costituito da una o due simboli c che possono essere letti mediante due transizioni (ciascuna rimuove un simbolo dalla pila). L’automa va in accettazione con epsilon mosse che controllano la presenza di Z0 sulla pila. Esercizio 2 Sono tutte fun zioni computabili: 1) è costante; 2) è computabile per definizione; 3) si calcola usando la macchina m e, in caso di terminazione, sottraendo 9 al contenuto del nastro; 4) confrontando x con m: in caso positivo si calcola f(x), in caso negativo, si restitu isce 1. Esercizio 3 MT: La complessità spaziale è Ө(n). Per leggere l’input, la macchina deve verificare che ogni 3 simboli a sia presente un simbolo b (la lunghezza del suffisso di c è al più 2). Se n è la lunghezza della stringa, l’automa percorre n/3 v olte una porzione di nastro che è lunga al più ¾ n (lunghezza del prefisso di a) e almeno ¼ n (lunghezza della sottoparola di b), dunque dell’ordine Ө(n). Pertanto la complessità termporale complessiva è Ө(n 2). RAM: La macchina RAM usa tre celle di memori a per contare la lunghezza dei simboli a, b e c che sono letti in successione. Le lunghezza sono memorizzate nelle celle M[1], M[2] e M[3] rispettivamente. Al termine della lettura verifica che M[2] sia M[1]/3 e che M[3] sia M[1] mod 3. Costo costante: T( n)=Ө(n), S(n)=Ө(1). Costo logaritmico: Ogni operazione di calcolo ha costo Ө(log(n)). Siccome la stringa è lunga n si ottiene T(n)=Ө(n log(n)), S(n)=Ө(log(n)). Esercizio 4 Un metodo per effettuare il controllo richiesto è quello di scorrere il vettore ed operare su ognuno dei suoi elementi un test efficiente per controllare se esso è un quadrato perfetto. Allo scopo di individuare se un numero x è un quadrato perfetto è possibile effettuare la ricerca binaria della sua radice quadrata intera all’ interno de ll’ intervallo che va da 1 a x stesso. Questa ricerca binaria ha quindi complessità log( x) considerando le operazioni aritmetiche a costo costante. La complessità totale del test richiesto è quindi O( l log( m)).