20 02 2012

Page 1

Algoritmi e Principi dell’Informatica Appello del 20 Febbraio 2012 Chi deve sostenere l’esame integrato (API) deve svolgere tutti gli esercizi in 2h e 30’ Chi deve sostenere solo il modulo di Informatica te orica deve svolgere le parti a), b) e c) dell’Esercizio 1 e l’Esercizio 2 in 1h. Chi deve sostenere solo il modulo di Informatica 3 deve svolgere la parte d) dell’esercizo 1 e l’esercizio 3 in 1h e 30’. Esercizio 1 (punti 12/30-esimi) Si consideri il seguente linguaggio: L 1 = { ab, abab, ababab, ..., aabb, aabbaabb, aabbaabbaabb, …, …, a n bn, an bn an bn, an bn an bn an bn, …, …} a) Fornire una specifica logica del linguaggio L1. b) Sintetizzare un automa a potenza minima (tra FSA, PDA, TM) in grado di riconoscere L1. c) Si consideri il linguaggio L 2={ anbn }+. I linguaggi L 1 e L 2 sono equivalenti? d) Si valutino le seguenti complessità relative al riconoscimento di L 1: 1. Complessità spaziale minima ottenibile mediante una macchina di Turing a k nastri 2. Complessità temporale minima ottenibile mediante una macchina di Turing a k nastri 3. Complessità spaziale minima ottenibile mediante una RAM, a criterio di costo logaritmico 4. Complessità temporale minima ottenibile mediante un a RAM, a criterio di costo logaritmico Si giustifichino brevemente le risposte date Esercizio 2 (punti 8/30-esimi) Si considerino le seguenti funzioni: (si rammenta che il simbolo y denota il massimo intero ≤ y e y il minimo intero ≥ y; |y| denota il valore assoluto di y; Z denota l’insieme dei numeri interi.) f1: Z
Z, f 1(x) = e|x|  f2: Z
Z, f 2(x) = e x f3: Z
Z, f 3(x) = x2 + 1 f4: Z
Z, f 4(x) = log ( |x| ) Siano poi T l’insieme delle funzioni totali Z
Z, e H ≡ {f: Z
Z | ∃x(f(x) = 0)} Dire, giustificando la risposta, se sia decidibile il problema di…