API 2021 02 17

Page 1

Algoritmi e Principi dell’Informatica Soluzioni al T ema d’esame 27 Gennaio 2021 1 Informatica teorica Esercizio 1 Si consideri il seguente linguaggio L definito sull’alfabeto Σ ={a, b, c, d}: L ={anbicjdk, n ≥ 0, i≥ 0, j≥ 0, k≥ 0, n = i + j + k} 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 ogni a con la rispettiva b, c, o d a seconda della posizione della a stessa nella stringa. G =    S→ aSd| A A→ aAc| B B→ aBb| ε Esercizio 2 Si denoti con Mi la i-esima macchina di Turing e si denoti con L(Mi) il linguaggio da essa riconosciuto. Si considerino i seguenti insiemi: 1. S1 ={i|L(Mi) non contiene nessuna stringa di lunghezza pari} 2. S2 ={i|L(Mi) contiene almeno una stringa di lunghezza pari} 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).S2 ` e ricorsivamente enumerabile (tecnica diagonale). S1 non ` e ricorsivamente enumerabile perch´ e lo ` e il suo complementoS2, e quindi se lo fosse anche S1, S1 e S2 dovrebbero essere ricorsivi. 2 Algoritmi e strutture dati Esercizio 3 Sia T[1..n][1..n] una matrice n× n; si consideri la seguente procedura f(T,n) e se ne valuti la complessit` a temporale. Nota: floor(x) ` e l’intero pi` u grande minore o uguale a x; ceil(x) ` e l’intero pi` u 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 <= v and j <= v then T[i][j] = A1[i][j] if i…