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 Prin Informatica Appello del 2 Settembre 2014 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 singol i esercizi hanno senso solo con hanno valore puramente indicativo. Esercizio 1 (punti 6) Si consideri il linguaggio L={ ambn | m n, m, n > 0 }. Esempi di stringhe di L sono: aabbb e aaabb, mentre ab, aabb, aba, sono stringhe non appartenenti ad L. 1. Si fornisca una grammatica, preferibilmente a potenza generativa minima tra le classi conosciute, che generi L. 2. Si fornisca un automa, preferibilmente a potenza riconoscitiva minima tra le classi conosciute, che riconosca L. Esercizio 2 (punti 6 senza la parte opzionale, 8, con la parte opzionale) Una procedura P riceve in ingresso un numero naturale n > 1 e due array, in e out, entrambi contenenti 2 n numeri naturali (l n inclusi). Preliminarmente si specifichino i predicati odd(n) e even(n contenenti esclusivamente variabili e costanti in tere, il predicato di uguaglianza, i simboli delle operazioni di somma e prodotto, in modo tale che i due predicati assumano il loro naturale significato, ossia odd(n) risulti vero se e solo se n è un numero naturale dispari, e even(n) se e solo se n è un numero naturale pari. Successivamente: 1) Si specifichino le precondizioni seguenti che devono quin zione di P. a) array in è diverso da ogni altro elemento dello stesso array in. b) array in in posizioni dispari sono dispari, e tutti quelli in posizione pari sono pari. La procedura copia tutti gli elementi array in array out, piazzando i n umeri dispari nelle prime n posizioni e quelli pari nelle n…
First page of the document.
