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 Principi dell’Informatica Appello del 7 febbraio 2019 Chi deve sostenere l’esame integrato (API) deve svolgere tutti gli esercizi in 2 ore. Chi deve sostenere solo il modulo di Informatica teorica deve svolgere gli Esercizi 1 e 2 in 1 ora. Chi deve sostenere solo il modulo di Informatica 3 deve svolgere gli Esercizi 3 e 4 in 1 ora. NB: i punti attribuiti ai singoli esercizi hanno senso solo con riferimento all’esame integrato e hanno valore puramente indicativo. Esercizio 1 (7 punti) Utilizzare un formalismo a potenza minima (tra tutti quelli visti a lezione) che caratterizzi il linguaggio costituito da tutte e sole le stringhe binarie tali per cui il numero di 0 nella stringa sia divisibile per 5. Esercizio 2 (9 punti) Si consideri la funzione f(x,y) = fz(x), dove z = fy(y). f è computabile? Motivare brevemente la risposta. Esercizio 3 (8 punti) Si consideri il seguente codice: FUN(A) : if A.length < 5 then return FUN1(A) a = A.length-1 FUN(A[0..a-1]) FUN(A[1..a]) FUN2(A) Sapendo che FUN1 ha complessità Q(n) e FUN2 ha complessità Q(n2), dove n è la lunghezza dell’array passato a entrambi come argomento, si valuti la complessità temporale di FUN fornendo un estremo superiore asintotico. Esercizio 4 (8 punti) Siano dati k array di n elementi ciascuno, già ordinati. Si descriva, preferibilmente mediante pseudocodice, un algoritmo per ottenere un array ordinato contenente tutti e soli gli elementi degli array dati, valutandone la complessità in funzione di k e n. Tracce delle soluzioni Esercizio 1 L’espressione regolare (1*01*01*01*01*01*)*, facilmente traducibile in un automa a stati finiti, definisce il linguaggio richiesto. Esercizio 2 f(x,y) può essere calcolata mediante il seguente algoritmo: 1. Calcolo fy(y). Se il calcolo non termina (proprietà…
First page of the document.
