API 2019 06 27

Page 1

Algoritmi e Principi dell'Informatica Seconda Prova in Itinere 27 Giugno 2019 Avvisi importanti Il tempo a disposizione è di 1 ora e 30 minuti. Esercizio 1 (punti 4/15-esimi) Si dica, spiegandone brevemente il motivo se le seguenti affermazioni sono vere o false: a) Dati 2 formalismi riconoscitivi F1 e F2, se F1 è strettamente più potente di F2, allora, preso un qualunque linguaggio L riconoscibile sia mediante F1 che mediante F2, L è sicuramente riconoscibile da F1 con complessità temporale asintoticamente non superiore rispetto ad F2. b) I linguaggi definibili mediante formule MFO sono riconoscibili da MT a nastro singolo con complessità temporale inferiore rispetto a quella delle macchine RAM. Il criterio di costo adottato per ogni formalismo deve essere realistico anche in caso di dati “estremi” (numeri o strutture di grandezza illimitata). Esercizio 2 (punti 6/15-esimi) Sono dati un array A di n interi distinti e un valore intero X. Si vuole determinare se esistano due elementi di A la cui somma sia X. Progettare un algoritmo e una struttura dati che minimizzino il tempo di esecuzione a criterio di costo costante, nel caso medio, senza eccessivo spreco di memoria. Si assuma che i valori interi contenuti nell’array A siano distribuiti in modo uniforme, ossia che all’interno di un certo intervallo, ad esempio [MININT ..MAXINT], abbiano tutti uguale probabilità di comparire in A. Esercizio 3 (punti 6/15-esimi) Sono dati in ingresso due array A e B, rispettivamente di n e di m elementi in N (numeri naturali), e una funzione f da N a N monotona crescente. Si vuole trovare la coppia di elementi (a,b), se esiste, con a in A e b in B, dove a è il più grande elemento di A tale per cui a=f(b). Descrivere un algoritmo che risolva il problema e determinarne la complessità…