Esame completo di Algoritmi e Principi dell'Informatica per il corso di Computer Engineering presso Politecnico di Milano. Materiale proveniente dall’archivio storico Studwiz e classificato per la consultazione online.
Esame completo di Algoritmi e Principi dell'Informatica per il corso di Computer Engineering presso Politecnico di Milano. Materiale proveniente dall’archivio storico Studwiz e classificato per la consultazione online.
Qualità dell’importazione: il testo è stato estratto direttamente dal documento originale.
Passaggi rappresentativi riconosciuti nelle diverse parti del materiale. Il testo completo resta presente nella pagina per la ricerca, mentre l’anteprima compatta rende più semplice la lettura.
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…
Prima pagina del documento.
