Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

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) D ati 2 formalismi riconoscitivi F1 e F2, se F1 è strettamen te più potente di F2, allora, p r e so 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 r ispetto 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 (pun ti 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 sia no 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 determin arne la complessità asintotica. Si può assumere che la funzione f sia calcolabile in tempo O(1), a criterio di costo costante. Tracce di soluzioni Esercizio 1 a) Falsa : è ben noto che il linguaggio wcw R non è riconoscibile da una MT a nastro singolo con complessità temporale inferiore a Q (n 2 )). b) Falsa: i linguaggi definibili mediante formule MFO sono una sottoclasse dei linguaggi regolari, quindi si possono riconoscere usando memoria finita . D ata una MT a nastro singolo che riconosce un linguaggio, ad esempio comportandosi mossa per mossa come un automa a stati finiti, si può scrivere una RAM che esegue un'istruzione per ogni mossa della MT, sempre usando un numero finito di celle; ogni mossa costa un tem po O(1) anche a criterio di costo logaritmico perché i dati in ingresso sono caratteri di un alfabeto finito. Esercizio 2 Può convenire usare una hash table. In primo luogo, si inseriscano gli n elementi di A in una hash table. Successivamente, per ogni elemento A[i] di A, cerchiamo X - A[i] nella tabella. Se si trova un j tale che A[j ] = X - A[i], la coppia è una soluzione del problema. Assumendo una dimensione m della tabella hash non troppo piccola rispetto ad n, ad esempio con riempimento α = ½ nel caso di indirizzamento aperto, o anche leggermente superiore nel caso di tabella a liste concatenate, una singola operazione sia di inserimento che di ricerca costa mediamente O(k), con k “vicino” all’unità a seconda dei vari casi. Occorrendo n inserim enti e al più n ricerche (mediamente un po’ meno se la probabilità che esista la coppia cercata non è troppo bassa), il tempo medio di esecuzione complessiva sarà dunque O(n). Esercizio 3 Una soluzione elementare consiste nel provare tutte le n*m coppie d i elementi e, per ciascuna di esse, verificare se soddisfino la relazione richiesta, tenendo traccia del massimo elemento di A con queste caratteristiche. La complessità risultante è O(n*m). Una soluzione più efficiente è la seguente: • Riordinare A e B per valori decrescenti • Scandire linearmente gli array ordinati, con elemento corrente a di A e b di B: o Se a=f(b) stop o Se a>f(b), passa al successivo elemento di A o Se a