API 2018 09 14

Pagina 1

Algoritmi e Principi dell’Informatica Appello del 14 settembre 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 (9 punti) Come di consueto, si indichi con fi la funzione calcolata dalla i-esima macchina di Turing. Si definisce il numero reale t nel modo seguente: • La parte intera di t è 0 • L’espansione decimale di t è tale che la i-esima cifra dopo la virgola vale: o 0 se la funzione fi non è computabile; o altrimenti, 1 se fi non è totale; o altrimenti, 2 se fi non è la funzione che calcola il quadrato del suo ingresso; o altrimenti 3. Si indichi con la notazione t[n] la sequenza delle prime n cifre nell’espansione decimale di t. Si considerino quindi le funzioni g e h definite come segue: • g(x) = t[100] se x=0, altrimenti ^; • h(x) = t[x]. Sono calcolabili le funzioni g e h? Motivare opportunamente la risposta. Esercizio 2 (7 punti) Si consideri la seguente grammatica G (con le consuete convenzioni di notazione): S ® aABb A ® cC B ® Cc C ® cC| Cc |c CC ® D D ® dD |d Si costruisca un automa appartenente a una famiglia a potenza riconoscitiva minima che riconosca L(G). Esercizio 3 (9 punti) Si vuole realizzare un software per la ricerca anagrammi: si fornisce una parola in ingresso e si identificano gli anagrammi di tale parola all’interno di un elenco di N parole. La lunghezza di ciascuna parola è di al più M caratteri. Si descriva un algoritmo che risolva il problema in oggetto e se ne…