API 2019 02 07

Pagina 1

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à…