API 2017 06 27

Page 1

Algoritmi e Principi dell’Informatica Appello del 27 giugno 2017 II prova: durata 1 ora e 15 minuti. Esercizio 1 (7 punti) Si consideri il linguaggio L = {x.y.xR.x.y.xR | x{a, b}+, y{a, b, c}*}. Si descrivano una MT a k nastri e una macchina RAM che accettano L, valutandone le complessità temporali e spaziali, a criterio di costo costante e logaritmico. Esercizio 2 (9 punti) Un ipotetico nucleo di valutazione del sistema universitario di un’ipotetica nazione ha deciso di valutare i docenti universitari utilizzando la seguente procedura: - A ciascun docente i è associato un indice di produttività IPi (un valore reale non negativo). - I docenti sono ordinati in modo che i loro IP siano in ordine non decrescente. - Il nucleo di valutazione definisce una soglia, cioè un numero non negativo k, per cui avanzeranno in carriera i soli docenti con un IP strettamente maggiore di k. Si scriva un algoritmo che, dato il vettore ordinato IP[1..n] e la soglia k, calcola il numero totale di ricercatori che possono essere promossi. Se ne discuta la complessità. La valutazione terrà conto della complessità dell’algoritmo definito. Soluzioni Esercizio 1 Per prima cosa notiamo come per verificare che una sottostringa abbia la forma x.y.x R basti controllare che il primo e l’ultimo carattere siano uguali e in {a, b}. Una MT M può riconoscere L calcolandone prima la lunghezza in unario sul primo nastro, per poi sfruttarne il contenuto per copiare la prima metà della stringa in ingresso sul secondo nastro e la seconda metà sul terzo nastro. La passata finale controlla che il secondo e il terzo nastro contengano la stessa stringa, che deve iniziare e terminare con lo stesso carattere a o b. Chiaramente TM(n) = (n) = SM(n). Una macchina RAM R copia in memoria la stringa in ingresso,…