Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

Algoritmi e Principi dell'Informatica Soluzioni al Tema d'esame27 Gennaio 2021 1 Informatica teorica Esercizio 1 Si consideri il seguente linguaggioLde nito sull'alfabeto  =fa; b; c; dg: L=fan bi cj dk ; n0; i0; j0; k0; n=i+j+kg Si descriva la grammatica a potenza minima che lo genera. Soluzione E' possibile generare il linguaggio tramite una grammatica non ambigua, libera dal contesto. In particolare, la grammatica mette in corrispondenza ogniacon la rispettivab,c, oda seconda della posizione dellaastessa nella stringa. G=8 > < > :S !aS djA A!aAcjB B!aBbj" Esercizio 2 Si denoti conM ila i-esima macchina di Turing e si denoti conL(M i) il linguaggio da essa riconosciuto. Si considerino i seguenti insiemi: 1.S 1= fijL(M i) non contiene nessuna stringa di lunghezza pari g 2.S 2= fijL(M i) contiene almeno una stringa di lunghezza pari g Per entrambi gli insiemi, si indichi, motivando opportunamente la risposta, se sono ricorsivi o ricorsivamente enumerabili. Soluzione (Traccia schematica) Nessuno dei due e ricorsivo (teorema di Rice).S 2e ricorsivamente enumerabile (tecnica diagonale).S 1non e ricorsivamente enumerabile perche lo e il suo complemento S 2, e quindi se lo fosse ancheS 1, S 1e S 2dovrebbero essere ricorsivi. 2 Algoritmi e strutture dati Esercizio 3 SiaT[1..n][1..n]una matricenn; si consideri la seguente proceduraf(T,n)e se ne valuti la complessita temporale. Nota:floor(x)e l'intero piu grande minore o uguale a x;ceil(x)e l'intero piu piccolo maggiore o uguale a x. 1/2 f(T, n) : v = floor(n/2) if v < 1 then return T w = ceil(n/2) if v == w then w = w+1 A = T[1..v][1..v] A1 = f(A, v) B = T[w..n][w..n] B1 = f(B, n-w+1) for i from 1 to n:for j from 1 to n: if i = w then T[i][j] = B1[i-w+1][j-w+1] else T[i][j] = T[i][j] * T[i][j] return T Soluzione Si denoti conN=n2 il numero di elementi della matriceT. La complessita della procedura e espressa dalla seguente ricorrenza:T(N) = 2T(N4 ) + ( N). E possibile applicare il terzo caso del Master Theorem, ottenendo quindi:T(N) = (N) = (n2 ). Esercizio 4 Si descriva il funzionamento di una macchina di Turing aknastri che, date due stringhe in ingresso xeysull'alfabetoA=fa; bg, restituisce 0 sexnon e un susso diy, altrimenti restituisce in uscita il pre sso che non e in comune. Si assuma che l'ingresso sia del tipox$y, dove $ e un carattere usato come separatore. Si speci chino le complessita temporale e spaziale della macchina. Soluzione Con una macchina di Turing a 3 nastri si puo fare una lettura sequenziale dell'ingresso, trascrivendo la stringax(prima del $) sul primo nastro di memoria e la stringay(dopo il $) sul secondo nastro. A questo punto si puo procedere con una lettura parallela da destra a sinistra dei due nastri di memoria, ntantoche i caratteri letti sono uguali. Se alla ne di questo passaggio non si e riavvolto completamente il primo nastro, vuol dire chexnon e un susso diye si puo quindi scrivere 0 in uscita. Altrimenti si procede alla stampa dei caratteri rimanenti sul secondo nastro. Per farlo, continuiamo la lettura da destra a sinistra sul secondo nastro e ne trascriviamo i caratteri sul terzo nastro di memoria (da sinistra a destra). In ne, riavvolgiamo il terzo nastro di memoria e lo rileggiamo da sinistra a destra, stampandone il contenuto in uscita. Le complessita sono lineari. 2/2