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 2015 2 ore e 30 minuti. Chi deve sostenere solo il modulo di Informatica teorica deve svolgere gli Esercizi 1 e 2 in 1 ora e 15 minuti. Chi deve sostenere solo il modulo di Informatica 3 deve svolgere gli Esercizi 3 e 4 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 8) Si considerino i linguaggi seguenti: L1 = { z {a,b,c}* | x ( y (z = x.y) (#a(x) #b(x) #c(x)) (#a(x) - #b(x) 2) } L2 = { z {a,b,c}* | x ( y (z = x.y) (#a(x) #b(x) #c(x)) (#b(x) - #c(x) 2) } L3 = { z {a,b,c}* | x ( y (z = x.y) (#a(x) #b(x) #c(x)) (#a(x) - #c(x) 2) } dove, per un carattere e una stringa x (x) denota il numero di volte in cui il carattere si ripete nella stringa x. Ad es. #a(ababaccc) = 3. Si costruisca una macchina astratta che riconosca L = L 1 L2 L3. Tra le diverse macchine alla categoria di automi a minor potenza riconoscitiva possibile. Esercizio 2 (9 punti) Sia d : N × N N la biiezione tra N e N × N definita come segue: d(x,y) = (x+y)(x+y+1)/2 + x Si considerino i seguenti insiemi: S1 = { d(x,y) | fx(y) } S2 = { x | fx(0) } S3(k) = { x | fk(x) }, dove k è un parametro. Per ciascuno dei predetti insiemi, si dica se esso è ricorsivo, motivando brevemente la risposta. Esercizio 3 (8 punti) Si definisca un algoritmo per determinare se due alberi binari di ricerca T 1 e T2 sono uguali sia per il valore delle chiavi sia per la definito. Esercizio 4 (punti 8) Si consideri il seguente insieme di numeri interi: {5, 60, 18, 23, 10, 15}. Si individui una sequenza di inserimenti (senza cancellazioni) di questi valori come chiavi di un albero r-b (rosso- nvenzione la radice di un nodi T-NIL, neri) vengono computate. Si mostri il risultato finale ottenuto…
First page of the document.
