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 2 Marzo 2015 Chi deve sostenere l’esame integrato (API) deve svolgere tutti gli esercizi in 2 ore e 30 minuti. Chi deve sostenere solo il modulo di Informatica teorica deve svolgere gli Esercizi 1 e 2 in 1 ora e 15 minuti. Chi deve sostenere solo il modulo di Informatica 3 deve svolgere gli Esercizi 3 e 4 in 1 ora e 15 minuti. NB: i punti attribuiti ai singoli esercizi hanno senso solo con riferimento all’esame integrato e hanno valore puramente indicativo. Esercizio 1 (punti 8) Una macchina di Turing si dice n-generatrice se, quando riceve 0 in ingresso, termina entro n+1 passi scrivendo il numero n in uscita (n≥0). Fissata una qualsiasi enumerazione algoritmica E delle macchine di Turing, il generatore minimo di un numero n, indicato con gm(n), è il più piccolo indice, secondo E, di macchina di Turing n-generatrice. Si risponda alle seguenti domande fornendo brevi ma chiare spiegazioni per le risposte date: a) La funzione gm è totale? b) La funzione gm è computabile? Esercizio 2 (punti 9) Si consideri il seguente linguaggio: L = {anb3n | n ≥ 0} ∪ {an(bbbc)n | n ≥ 0} Si forniscano: a) Una grammatica, preferibilmente a potenza generativa minima, che generi L b) Un automa, preferibilmente a potenza minima tra le famiglie tradizionali a stati finiti, a pila (deterministici o no), macchine di Turing, che riconosca L c) Una rete di Petri che riconosca L Esercizio 3 (punti 9) Si consideri il seguente linguaggio: L = {an1ban2b…ank | 1 ≤ k ≤ 100, ∀ 1 ≤ i ≤ k.(ni ≥ 1), ∃ 1 ≤ i < j ≤ k.(ni = nj)} Si descrivano a grandi linee, ma in maniera sufficientemente precisa, una MT e una RAM che riconoscano L e se ne valutino le complessità temporali, nel caso della RAM sia a criterio di costo costante che a criterio logaritmico. Sono…
First page of the document.
