11 09 2013

Pagina 1

Algoritmi e Principi dell’Informatica Appello dell’11 Settembre 2013 Chi deve sostenere l’esame integrato (API) deve svolgere tutti gli esercizi in 3 ore. Chi deve sostenere solo il modulo di Informatica teorica deve svolgere gli Esercizi 1, 2 e 3, in 1 ora e 30 minuti. Chi deve sostenere solo il modulo di Informatica 3 deve svolgere gli Esercizi 4, 5, 6 in 1 ora e 30 minuti. NB: i punti attribuiti ai singoli esercizi hanno senso solo con riferimento all’esame integrato e hanno valore puramente indicativo. Esercizio 1 (punti 4) Sia data la seguente grammatica G: S → B S a | C BC → C b b C → c 1. Si dica quale è il linguaggio generato da G. 2. Si scriva un automa che riconosce il linguaggio generato da G. L’automa deve appartenere alla classe di potenza riconoscitiva minima tra quelle che riconoscono il linguaggio generato da G. Esercizio 2 (punti 5) Si consideri il seguente programma (in pseudocodice), il cui scopo è ordinare un generico array A di lunghezza variabile il cui valore è memorizzato nel campo length (si supponga che il campo key dei vari elementi sia un intero in valore assoluto ≤ 100): INSERTION-SORT(A) 1 for j := 2 to A.length 2 key := A[j] 3 //Inserisce A[j] nella sequenza ordinata A[1..j−1] 4 i := j − 1 5 while i > 0 and A[i] > key 6 A[i + 1] := A[i] 7 i := i − 1 8 A[i + 1] := key 1. E’ decidibile il problema di stabilire se il programma suddetto ordina correttamente un generico array di lunghezza ≤ 100? 2. E’ decidibile il problema di stabilire se il programma suddetto ordina correttamente un generico array di lunghezza qualsiasi? Esercizio 3 Prima parte (obbligatoria:punti 6) Si consideri un sistema costituito da un processo che gestisce una risorsa R utilizzata da due processi utenti U1 e U2. • Ognuno dei due utenti richiede di tanto in tanto…