API 2018 02 14

Page 1

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 risposta, se le seguenti funzioni sono calcolabili: 1) g1(x) = f(m); 2) g2(x) = f(x); 3) g3(x) = f(x)-9 se f(x) > 10,  altrimenti; 4) g4(x) = fx(x) se x = m, 1 altrimenti. Esercizio 3 (8 punti) Considerato il linguaggio L dell’esercizio 1, definire la complessità 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. Il 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 del 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…