Politecnico di Milano
Facoltà di Ingegneria Industriale
INFORMATICA B
Prova in itinere del 24 Gennaio 2011
COGNOME E NOME
RIGA COLONNA MATRICOLA
Spazio riservato ai docenti
Il presente plico contiene 3 esercizi, deve essere debitamente compilato con cognome e nome, numero di matricola, posizione durante lo scritto (comunicata dal docente).
Il tempo a disposizione è di 2 ore.
Non separate questi fogli. Scrivete la soluzione solo sui fogli distribuiti, utilizzando il retro delle pagine in caso di necessità. Cancellate le parti di brutta (o ripudiate) con un tratto di penna.
Ogni parte non cancellata a penna sarà considerata parte integrante della soluzione.
È possibile scrivere a matita (e non occorre ricalcare al momento della consegna!).
È vietato utilizzare calcolatrici, telefoni o pc. Chi tenti di farlo vedrà annullata la sua prova. È ammessa la consultazione di libri e appunti, purché con pacata discrezione e senza disturbare. Qualsiasi tentativo di comunicare con altri studenti comporta l’espulsione dall’aula.
È possibile ritirarsi senza penalità.
Esercizio 1 (6 punti)
Scrivere una funzione non ricorsiva di nome frame che riceve un parametro N (intero pari positivo) e ritorna una matrice A di dimensione NxN in cui:
gli elementi della riga 1, riga N, colonna 1 e colonna N sono inizializzati a 1
gli elementi rimanenti della riga 2, riga N-1, colonna 2 e colonna N-1 sono inizializzati a 2 gli elementi rimanenti della riga 3, riga N-2, colonna 3 e colonna N-2 sono inizializzati a 3 così via fino a completare tutta la matrice
Ad esempio, per N = 8: > frame(8) ans = 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 1 1 2 3 3 3 3 2 1 1 2 3 4 4 3 2 1 1 2 3 4 4 3 2 1 1 2 3 3 3 3 2 1 1 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1
Nota: il massimo livello di annidamento tra istruzioni iterative (es. for) innestate utilizzabili per implementare la funzione è 2. Punto facoltativo: modificare la funzione frame, senza aggiungere ulteriori cicli, in modo tale che gli elementi appartenenti alle due diagonali della matrice siano uguali a -1; ad esempio:
> frame(8) ans = -1 1 1 1 1 1 1 -1 1 -1 2 2 2 2 -1 1 1 2 -1 3 3 -1 2 1 1 2 3 -1 -1 3 2 1 1 2 3 -1 -1 3 2 1 1 2 -1 3 3 -1 2 1 1 -1 2 2 2 2 -1 1 -1 1 1 1 1 1 1 -1 Soluzione
Sono possibili varie soluzioni. Quella che viene proposta qui sotto si basa sull’utilizzo dei sotto-array. In particolare, nella soluzione si identificano come sottoarray tutte le “cornici” concentriche che sono ricavabili dalla matrice, partendo dalla cornice più esterna, che è costituita dalla prima e ultima riga e dalla prima e ultima colonna e proseguendo verso il centro della matrice stessa. Agli elementi di ogni cornice vengono assegnati valori crescenti, da 1 (assegnato a tutti i valori della cornice esterna) a N/2 (assegnato agli elementi della “cornice” più interna.
function [A] = frame(N) for ii=1:N/2
A([ii,N-ii+1],ii:N-ii+1) = ii; A(ii:N-ii+1,[ii,N-ii+1]) = ii; end
Parte facoltativa: si aggiunge un’istruzione che, dopo aver selezionato un sotto-array composto da tutti gli elementi che si trovano in una delle due diagonali, assegna a tali elementi il valore -1.
function [A] = frame(N) for ii=1:N/2
A([ii,N-ii+1],ii:N-ii+1) = ii; A(ii:N-ii+1,[ii,N-ii+1]) = ii; A([ii,N-ii+1],[ii,N-ii+1]) = -1; end
Esercizio 2 (7 punti)
Si considerino la funzione e lo script seguenti: function [r] = MiaFunz(a, b) if b == 0 r = 1; elseif b < 0 r = a * MiaFunz(a, b+1); else r = 1/a * MiaFunz(a, b-1); end;
%script che chiama MiaFunz x = 2;
for y = -3:1:3 r = MiaFunz(x,y) end
1. Descrivere brevemente quale sia la funzione matematica calcolata dalla funzione MATLAB MiaFunz. Giustificare la risposta. 2. Quali risultati vengono stampati a video? Non è necessario calcolare i valori numerici esatti, ma è sufficiente riportare le espressioni aritmetiche necessarie per calcolarli. Giustificare la risposta.
Soluzione
1. La funzione matematica calcolata dal programma è a-b tranne che nel caso in cui sia a che b sono uguali a zero in cui viene restituito il valore 1.
Giustificazione
Nel caso base in cui b è uguale a zero, la funzione restituisce sempre il valore 1.
Nel caso in cui b è negativo, la funzione restituisce il valore di a moltiplicato per il risultato della funzione stessa chiamata ricorsivamente con parametri a e b+1. Questa chiamata ricorsiva restituisce il valore di a moltiplicato per il risultato della successiva chiamata ricorsiva ottenuto con stesso a e valore di b incrementato di un’ulteriore unità. La ricorsione termina quando b raggiunge il valore 0. Quindi si hanno esattamente|b| (-b considerando che b è negativo) passi ricorsivi in cui il valore a è moltiplicato per se stesso.
Nel caso generale si ha perciò la seguente situazione (ricordando che in questo caso il valore di b iniziale è negativo e viene incrementato ad ogni passo fino ad arrivare a zero):
MiaFunz(a,b)= (passo 1) = a MiaFunz(a,b+1)= (passo 2) = a2 *MiaFunz(a,b+2)= (passo 3) = a3 *MiaFunz(a,b+3)=… (passo -b-2) = a-b-2 *MiaFunz(a,b+(-b-2))= (passo -b-1) = a-b-1 *MiaFunz(a,b+(-b-1))= (passo -b) = a-b *MiaFunz(a,b+(-b))= =a-b
Nel caso in cui b è positivo, la funzione si comporta in modo simile al caso precedente, ma questa volta il valore che viene moltiplicato per se stesso è 1/a, mentre il valore di b viene decrementato di un’unità ad ogni passo di ricorsione. In questo modo si hanno esattamente b passi ricorsivi prima di chiamare la funzione con parametro b uguale a zero, corrispondente al caso base in cui il risultato viene moltiplicato per il valore 1.
Nel caso generale si ha perciò la seguente situazione (ricordando che in questo caso il valore di b iniziale è positivo e viene decrementato ad ogni passo fino ad arrivare a zero):
MiaFunz(a,b)=
(passo 1) = 1/a MiaFunz(a,b-1)= (passo 2) = 1/a2 *MiaFunz(a,b-2)= (passo 3) = 1/a3 *MiaFunz(a,b-3)=…
(passo b-2) = 1/ab-2 *MiaFunz(a,b-(b+2))= (passo b-1) = 1/ab-1 *MiaFunz(a,b-(b+1))= (passo b) = 1/ab *MiaFunz(a,b-(b))= =1/ab=a-b
2. I risultati stampati a video sono: r = 8 r = 4 r = 2 r= 1 r = 0.5 r = 0.25 r = 0.125 Giustificazione
Ad ogni iterazione del ciclo presente nello script viene chiamata la funzione MiaFunz con parametri x e y. Tale funzione produce come risultato un numero che viene assegnato alla variabile r. La mancanza di un punto e virgola nell’istruzione di assegnamento fa in modo che MATLAB stampi il valore assegnato a r in quell’iterazione del ciclo.
Il ciclo viene iterato per i valori di y che variano da -3 a 3 con incrementi di 1. La variabile x invece assume un valore costante assegnato prima del ciclo pari a 2. Per cui si hanno 7 invocazioni della funzione con le seguenti coppie di parametri (x,y): 3), (2,-2), (2,-1), (2,0), (2,1), (2,(2,-2), (2,3). I valori stampati a video si ottengono quindi ricordando dal punto 1 dell’esercizio che la funzione calcola x-y.
Esercizio 3 (4 punti)
Un sistema dotato solamente di memoria centrale ha un tempo di accesso ai dati pari a 150 ns. Per poter migliorare il tempo di accesso si decide di aggiungere una memoria cache con le seguenti caratteristiche:
Hit Rate = 75 % Hit Time = 80 ns
Rispondere alle seguenti domande (giustificando i risultati ottenuti con gli opportuni calcoli): a) Calcolare il tempo medio di accesso ai dati quando il Miss Penalty è pari a 400 ns
b) Qual è il valore massimo che deve avere il Miss Penalty affinché la cache offra un vantaggio in termini di prestazioni (cioè il tempo medio di accesso con la cache sia inferiore a 150 ns)?
c) Il progettista della cache deve scegliere fra due diverse politiche da utilizzare per la sostituzione dei dati nella cache quando questa è piena:
Politica 1. Verrà sostituito il dato nella cache più vicino (nella memoria centrale) all’ultimo dato richiesto Politica 2. Verrà sostituito il dato nella cache a cui si è richiesto l’accesso meno recentemente
Quale delle due politiche è preferibile? Giustificare la risposta.
Soluzione
a) T = 0.75 * 80 ns + 0.25 * 400 ns = 160 ns b) 0.75 * 80 ns + 0.25 * x < 150 ns => x < 360 ns
