Esame completo di Algoritmi e Principi dell'Informatica per il corso di Computer Engineering presso Politecnico di Milano. Materiale proveniente dall’archivio storico Studwiz e classificato per la consultazione online.
Esame completo di Algoritmi e Principi dell'Informatica per il corso di Computer Engineering presso Politecnico di Milano. Materiale proveniente dall’archivio storico Studwiz e classificato per la consultazione online.
Qualità dell’importazione: il testo è stato estratto direttamente dal documento originale.
Passaggi rappresentativi riconosciuti nelle diverse parti del materiale. Il testo completo resta presente nella pagina per la ricerca, mentre l’anteprima compatta rende più semplice la lettura.
Algoritmi e Principi dell’Informatica Appello del 12 Luglio 2012 Chi deve sostenere l’esame integrato (API) deve svolgere tutti gli esercizi in 2 h 30’ Chi deve sostenere solo il modulo di Informatica te orica deve svolgere l’Esercizio 1 e l’Esercizio 2 in 1 ora 15’. Chi deve sostenere solo il modulo di Informatica 3 deve svolgere l’esercizio 3 e l’esercizo 4 in 1 h 15’. NB: i punti attribuiti ai singoli esercizi hanno se nso solo con riferimento all’esame integrato e hanno valore puramente indicativo. Esercizio 1 (punti 7/30-esimi) Si consideri la seguente macchina di Turing M, dove q 0 è stato iniziale e q 4 finale: δ(q 0,a,Z 0,Z 0) = <q 1,Z 0,Z 0,S,R,S> δ(q 1,a,_,Z 0) = <q 1,A,Z 0,R,R,S> δ(q 1,b,_,Z 0) = <q 2,_,Z 0,S,L,R> δ(q 2,b,A,_) = <q 2,A,B,R,S,R> δ(q 2,c,A,_) = <q 3,C,_,R,L,L> δ(q 3,c,A,B) = <q 3,C,B,R,L,S> δ(q 3,_,Z0,B) = <q 4,Z0,B,S,S,S> Si definisca un automa a potenza minima che accetti lo stesso linguaggio di M. Esercizio 2 (punti 9/30-esimi) Siano A e G, rispettivamente una generica famiglia di automi e una di grammatiche; siano poi L(A) e L(G) le rispettive classi di linguaggi definiti da esse. Di esse si sappia che: • L(A) è ricorsivamente contenuta in L(G); ossia esiste un algoritmo che dato un automa A in A costruisce una G in G ad esso equivalente, ossia tale che L(A) = L(G). • L(A) è ricorsivamente chiusa rispetto al complemento; ossia esiste un algoritmo che dato un automa A in A costruisce un automa A’ in A che accetta il complemento di L(A). • L(G) è ricorsivamente chiusa rispetto all’intersezione; ossia esiste un algoritmo che date due grammatiche G e G’ in G costruisce una grammatica G” in G tale che L(G”) = L(G) ∩ L(G’). Sulla base di queste e solo queste informazioni è p ossibile concludere che il segente problema: Dati una generica G in G e…
Prima pagina del documento.
