API 2017 07 14

Page 1

Algoritmi e Principi dell’Informatica Appello del 14 Luglio 2017 Chi deve sostenere l’esame integrato (API) deve svolgere tutti gli esercizi in 2 ore e 30 minuti. Chi deve sostenere solo il modulo di Informatica teorica deve svolgere gli Esercizi 1 e 2 in 1 ora e 15 minuti. Chi deve sostenere solo il modulo di Informatica 3 deve svolgere gli Esercizi 3 e 4 in 1 ora e 15 minuti. NB: i punti attribuiti ai singoli esercizi hanno senso solo con riferimento all’esame integrat o e hanno valore puramente indicativo. Esercizio 1 (8 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, in 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 . a) Si specifichino in logica del prim’ordine i seguenti predicati binari: • stessaDim, che indica che i suoi due argomenti sono due punti di uguale dimensionalità; • uguale, che indica che i suoi due argomenti sono due punti uguali; • 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…