Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

Algoritmi e Principi dell’Informatica Appello del 17 gennaio 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 co n riferimento all’esame integrato e hanno valore puramente indicativo. Esercizio 1 (6 punti) Si considerino i seguenti linguaggi: • L 1 = {a m b n | 1 £ m £ n £ 2m}. • L 2 = {a m b n | 1 £ m < n < 2m}. Per ciascuno di essi, si fornisca una grammatica a potenza generativa minima che lo generi. Esercizio 2 (9 punti) In uno spazio a d dimensioni, un punto p domina un punto q se • in ogni dimensione, la coordinata di p è maggiore o uguale a quella corrispondente di q ; • c’è almeno una dimensione in cui la coordinata di p è strettamente maggiore di quella di q . Ad esempio, a 3 dimensioni, il punto p =(1,2,3) domina il punto q =(0,2,1), mentre non domina il punto r =(0,1,4). E’ già disponibile una funzione binaria elem che, con argomenti a (array) e i (indice), restituisce l’ ( i +1) - esimo elemento dell’array a (il primo elemento ha indice 0). Si conviene inoltre che, per un array a di k elementi, sia elem ( a , i )= ^ per i ³ k . Un punto d - dimensionale viene rappresentato come un array di d elementi, cui si può accedere tramite la suddetta funzione elem . Oltre a elem , si possono considerare già disponibili i comparatori (>, ³ , =) e il simbolo ^ , mentre la costante d, se ritenuta necessaria, deve essere definita attraverso un’opportuna formula. a) Si specifichino in logica del prim’ordine i seguenti predicati binari: • uguale , che indica che i suoi due argomenti sono due punti uguali; • stessaDim , che indica che i suoi due argomenti sono due punti di uguale dimensionalità; • domina , che indica che il primo argomento è un punto che domina il secondo argomento. Il programma SKYLINE riceve in ingresso un insieme P di punti tutti diversi e tutti con la stessa dimensionalità , e restituisce in uscita S, la cosiddetta “skyline” di P, ossia l’insieme dei punti di P che non sono dominati da nessun altro punto di P. b) Si utilizzi la notazione di Hoare per specificare opportune pre - condizioni e post - condizioni per il programma SKYLINE. Si possono considerare già disponibili unicamente i predicati definiti al punto a nonché il simbolo di appartenenza insiemistica ( Î ) applicato a P e a S. Esercizio 3 (7 punti) Trovare un limite superiore per la seguente ricorrenza: T(n) = n 2 + T( ë n/2 û ) + T( ë n/4 û ) + T( ë n/8 û ) + … + T( ë n/2 k û ), dove k è una costante intera maggiore di 1 e n è una potenza di 2. Esercizio 4 (8 punti) Si descriva, preferibilmente mediante uso di adeguato pseudocodice, un algoritmo che implementi la SKYLINE specificata nell’esercizio 2, ossia che riceva in ingresso un insieme di punti P e produca in uscita un sottoinsieme di punti S di P che soddisfino la specifica di SKYLINE. Si valuti la complessità temporale asintotica dell’algoritmo rispetto ai due parametri n (cardinalità dell’insieme di punti P) e d (numero di dimensioni). Tracce delle soluzioni Esercizio 1 Per L 1 : S ® ab | abb | aSb | aSbb Per L 2 : S ® aabbb | aSb | aSbb Esercizio 2 a) " x " y ( uguale (x,y) « ( " i elem (x,i)= elem (y,i))) " x " y ( stessaDim (x,y) « ( " i ( elem (x,i)= ^ « elem (y,i)= ^ ))) " x " y ( domina (x,y) « ( stessaDim (x,y) Ù " i ( elem (x,i) ¹ ^ ® elem (x,i) ³ elem (y,i)) Ù $ i ( elem (x,i) ¹ ^ Ù elem (x,i) > elem (y,i))) ) b) Pre - condizione: specifichiamo che tutti i punti sono diversi e che hanno tutti la stessa dimensionalità. " x " y(x Î P Ù y Î P ® stessaDim (x,y) Ù (x ¹ y ® ¬ uguale (x,y))) SKYLINE Post - condizione: specifichiamo che i punti di S sono esattamente quei punti di P non dominati da nessun altro punto di P. " x(x Î S « x Î P Ù ¬ $ y (y Î P Ù domina (y,x)) ) Esercizio 3 Utilizziamo il metodo di sostituzione, ipotizzando che T(n) £ c n 2 , per una qualche costante positiva c. Otteniamo: T(n) = n 2 + T( ë n/2 û ) + T( ë n/4 û ) + T( ë n/8 û ) + … + T( ë n/2 k û ) £ n 2 + cn 2 /4 + cn 2 /4 2 + cn 2 /4 3 + … + cn 2 /4 k = n 2 (1+ c/4+ c/4 2 + c/4 3 + … + c/4 k ) = n 2 (1+ c/4 × (1+ 1/4 + 1/4 2 + … + 1/4 k - 1 )) < n 2 (1+ c/4 × 1/(1 - 1/4)) = n 2 (1+ c/4 × 4/3) = n 2 (1+ c/3) L’espressione ottenuta soddisfa l’ipotesi se n 2 (1+ c/3) £ c n 2 ossia se c ³ 3/2. Poniamo T(0)=0, verificando così l’ipotesi anche nel caso base n=0. In definitiva, T(n)=O(n 2 ). Esercizio 4 Uno schema di algoritmo che segue in modo naturale la specifica del problema consiste in 1. Definire una procedura che dati due punti A e B stabilisca se uno dei due domina l’altro. Una tale procedura, e. g . domina(A,B) che restituisce il risultato ternario A domina B, o B domina A o non - dominanza, è facilmente codificabile con una complessità lineare rispetto alla dimensione dei punti d. 2. Il main non fa altro che scandire tutti i punti di P . Per ognuno di e ssi, diciamolo A , verifica, mediante la procedura domina , se A domina o è dominato dai punti già in S (inizialmente vuoto). a. Se A domina qualche punto di S , A viene inserito in S e vengono eliminati tutti i punti dominati da A . b. Se A è dominato da qualche punto di S , A non viene inserito in S . c. Se A non domina alcun punto di S né è dominato da essi, A viene inserito in S . 3. Si noti che non è possibile che A domini e sia dominato da qualche punto di S perché la proprietà di dominanza è transitiva e i punti di S sono dall’inizio non reciprocamente dominanti e tale proprietà è mantenuta dopo l’esame di ogni nuovo punto. La complessità del main è palesemente O(n 2 ) (secondo lo schema della classica ∑ " # $ ). Siccome ogni chiamata della procedura domina costa O(d) ed è indipendente da n, la complessità totale è O(d.n 2 ).