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 18 Settembre 2014 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, 2, 3 in 1 ora e 15 minuti. Chi deve sostenere solo il modulo di Informatica 3 deve svolgere gli Esercizi 4, 5 e 6 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 5) Si consideri il linguaggio L delle stringhe anbn, anbnanbn, ... dove anbn può essere ripetuto 1 o più volte, con 0 < n < 4. Esempi di stringhe in L sono: aabb, abab. Esempi di stringhe non in L sono invece: abb, aabbab. Si scrivano un automa e/o una grammatica a potenza minima per L e per L1 = L ∩ {(ambm)+, m > 0}. NB: è preferita una soluzione che presenti sia una grammatica che un automa ma è accettabile anche uno solo dei due formalismi. Esercizio 2 (punti 8) Punto a. Specificare in logica del prim’ordine il predicato binario substring(x,y) che indica che il primo argomento x è una sottostringa del secondo argomento y, ossia una sequenza di caratteri consecutivi che compare in y. NB: come caso particolare la stringa nulla è sottostringa di qualsiasi stringa. Ad esempio substring(ac,abcd) è falso substring(bc,abcd) è vero Per la specifica, oltre al predicato di uguaglianza, si può usare solo la funzione binaria concat (concatenazione tra stringhe), che restituisce la concatenazione dei suoi argomenti. Ad esempio: concat(ab,cd) restituisce abcd Punto b. Si specifichi poi il predicato substring2(x,y,i,j) che indica che x è uguale alla sottostringa di y che va dal carattere in posizione i di y al carattere in posizione j ≥ i di y…
Prima pagina del documento.
