API 2019 01 17

Page 1

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 con riferimento all’esame integrato e hanno valore puramente indicativo. Esercizio 1 (6 punti) Si considerino i seguenti linguaggi: • L1 = {ambn | 1 £ m £ n £ 2m}. • L2 = {ambn | 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; •…