Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

Algoritmi e Principi dell'Informatica Tema d'esame del 14 Giugno 2021 1 Informatica teorica Esercizio 1 (8 punti + bonus) Si consideri il linguaggioL 1= :L 2, dove L 2= ( ab)+ . a)Si de niscaL 1nella logica MFO, se possibile, altrimenti se ne motivi l'impossibilita. b)Bonus.Con riferimento alle proprieta dei linguaggistar-free, si chiarisca se e possibile fornire un'espressione insiemistica perL 1facendo uso del simbolo dell'insieme vuoto ( ;), degli insiemi di una singola lettera (fagefbg), degli operatori di unione ([), intersezione (\), complemento (:) e concatenamento (
), senza usare gli operatori di Kleene ( e+ ). Suggerimento: si noti che:;=fa; bg . Soluzione a)Si puo de nireL 1in MFO mediante la formula seguente: :( 9x(x= 0^a(x))^ 8x(a(x)! 9y(succ(x; y)^b(y)))^ 8x((b(x)^ :last(x))! 9y(succ(x; y)^a(y)))^ 9x(last(x)^b(x)) ) b)Un'espressione perL 1che non usi gli operatori di Kleene e la seguente: (:;
fag
fag
:;) (parole che hanno dueaconsecutive) [ (:;
fbg
fbg
:;) (che hanno duebconsecutive) [ :(fag
:;) (parole che non iniziano cona) [ :(:;
fbg) (parole che non niscono conb) 1/3 Esercizio 2 (8 punti, solo a) e b) per studenti con riduzione della prova) Nel corso diProva nale di APIsi richiede di sviluppare in C una funzionefdaNaN. Un generatore di test, fornito agli studenti, enumera gli input perfe i corrispondenti output attesi. a) E decidibile il problema di stabilire se la codi ca diffatta da un generico studente e corretta rispetto ad ogni possibile caso di test fornito dal generatore? b)Ada e Pasquale si sono consultati prima di scrivere le proprie implementazioni. E decidibile il problema di stabilire se le loro codi che difsono equivalenti? c) E semidecidibile il problema del punto a)?„ Soluzione a)No per Rice (la correttezza e una proprieta non banale della funzione calcolata: esiste almenouna funzione corretta, ed almeno una funzione non corretta). b)S (domanda chiusa).c)No: come noto, la correttezza non e nemmeno semidecidibile. In particolare, testando unodopo l'altro i vari casi di test (con tecnica diagonale, mediante dovetailing) posso eventualmente trovare, se c'e, una discrepanza tra l'output predetto dal generatore e quello ottenuto con la codi ca dif; e quindi semidecidibile la presenza di una discrepanza, ed essendo indecidibile il problema della correttezza (cioe assenza di discrepanze), allora la correttezza non puo essere nemmeno semidecidibile. 2 Algoritmi e strutture dati Esercizio 3 (8 punti + bonus) Descrivere in modo rigoroso (o in pseudocodice) un algoritmo che riceve in ingresso una sequenza Sdi numeri interi e la riordina nel modo seguente: il primo numero e il piu grande diS, il secondo e il piu piccolo diS, il terzo e il secondo piu grande diS, il quarto e il secondo piu piccolo diS, e cos via. Per esempio, data in ingresso la sequenzaS= [4;8;23;10;17;0;3], l'algoritmo la deve riordinare nella seguente maniera: [23;0;17;3;10;4;8]. Si fornisca la complessita asintotica dell'al- goritmo scritto. L'algoritmo descritto deve avere complessita temporale minima; verra attribuito un punteggiobonusa fronte di una dimostrazione della minimalita della complessita temporale dell'algoritmo proposto. SoluzioneUn modo semplice di realizzare questo algoritmo consiste nell'ordinare l'array in ordine de- crescente, con un algoritmo a complessita ottimaO(nlog(n)), ad esempio Merge-Sort. Ottenuto l'array ordinato se ne costruisce uno nuovo con gli elementi ordinati dall'inizio se l'indice e pari e dalla ne se e dispari (complessitaO(n)). La complessita totale e pertantoO(nlog(n)). 1i n t * o s c i l l a n t e ( i n t * a r r a y , i n t n ) { 2m e r g e s o r t ( a r r a y , n ) ; 3i n t * r e s u l t = ( i n t * ) m a l l o c ( s i z e o f ( i n t ) * n ) ; 4f o r ( i n t i = 0 ; i < n ; i + + ) {„ Gli studenti con la riduzione della prova non devono arontare questo punto. 2/3 5 r e s u l t [ i ] = ( i % 2 ! = 0 ) ? a r r a y [ i / 2 ] : a r r a y [ n - 1 - i / 2 ] ; 6} 7r e t u r n r e s u l t ; 8}  E possibile dimostrare che la soluzione fornita ha complessita ottima, osservando che, se, per assurdo, fosse disponibile un algoritmo piu veloce diO(nlog(n)) che ordina un array dato secondo il criterio indicato, questo algoritmo consentirebbe anche di ordinare l'array stesso in un ordine crescente o decrescente. Detto infattiA(v) l'algoritmo che ordina secondo l'ordine descritto nella consegna e indicata conT A( n) la sua complessita temporale in funzione della lunghezza divpos- siamo costruire una procedura che ordinavin ordine decrescente invocandoA(v) suve poi, con una scansione lineare stampando prima gli elementi pari divdall'inizio alla ne, poi i dispari dalla ne all'inizio. Il costo di quanto fatto e quello di una scansione lineare (n) piuT A( n). Sapendo che il limite inferiore per la complessita dell'ordinamento per confronto eO(nlog(n)), abbiamo che la complessita per la proposta diA(n) e ottima. Esercizio 4 (8 punti, solo punti a e b per studenti con riduzione della prova) Risolvere le seguenti ricorrenze: a)T(n) = 3T(n2 ) + n; b)T(n) = 16T(n4 ) + n!; c)T(n) =12 T (n2 ) + n 1 ;y d)T(n) = 4T(n2 ) + n2 .y Soluzione a)Si applica il Master Theorem (caso 1):T(n) = (nlog 23 ). b)Si applica il Master Theorem (caso 3):T(n) = (n!). c)Non si puo applicare il Master Theorem perchea