Study material for Algoritmi e Principi dell'Informatica, shared by the Studwiz community and reviewed by moderators.
Study material for Algoritmi e Principi dell'Informatica, shared by the Studwiz community and reviewed by moderators.
Import quality: text was extracted directly from the original document.
Representative passages recognised in different parts of the material. The full extracted text remains available to search, while this compact preview makes the page easier to read.
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…
First page of the document.
