Fondamenti di informatica (SSE e Statistica)

Prova scritta del 3 luglio 2001

Domanda 1

Scrivere un programma C che legge da tastiera 20 numeri reali (che si assumono distinti) ed un intero k compreso tra 0 e 19, e stampa il k-mo elemento dell’insieme (per k-mo elemento si intende un elemento che è maggiore di esattamente k-1 elementi dell’insieme).

Discutere la complessità asintotica del programma proposto.

Soluzione domanda 1

Vedi testi consigliati.

Domanda 3

Descrivere le codifiche conosciute per rappresentare valori numerici interi (positivi e negativi) all’interno dell’elaboratore, ed i metodi per trasformare tali codifiche da e verso la consueta notazione decimale.

Soluzione domanda 3

Vedi testi consigliati.

Domanda 2

Data una sequenza di valori reali v₀, v₁, ..., v_n-1, si definisce “media mobile” di passo k la media di k elementi adiacenti nella sequenza (assumendo k £ n). Naturalmente è possibile calcolare n–k+1 diverse medie mobili sulla stessa sequenza, al variare del punto d’inizio della porzione considerata. Tale media permette ad esempio di evidenziare l’andamento temporale di una variabile, filtrando oscillazioni di breve periodo.

Scrivere una funzione C di nome min_media_mobile che, dati come parametri un array di interi V, il numero di elementi in esso contenuti, ed un naturale k non maggiore del numero di elementi, restituisce la minima media mobile di passo k determinata dalla sequenza V.

Esempio:

se alla funzione venissero passati i seguenti parametri

array: 4 5 6 5 7 2 8 4 3 2 6 7

lunghezza: 12

passo: 6

dovrebbe essere restituito il valore 4.1666667 (è determinato dall’intervallo sottolineato, il quale fornisce il valore minimo della media tra 6 elementi consecutivi)

4 5 6 5 7 2 8 4 3 2 6 7

Soluzione domanda 2

#include<limits.h> /* contiene la definizione di INT_MAX */

float min_media_mobile(int a[], int n, int k)

{

float media_minima, media;

int inizio, j, somma;

media_minima=INT_MAX; /* serve ad inizializzare la variabile con un valore

sicuramente maggiore di qualsiasi media mobile */

for(inizio=0; inizio<n-k+1; inizio++){

/* calcolo la media mobile a partire dalla posizione inizio */

somma = 0;

for(j=inizio; j<inizio+k; j++)

somma = somma+a[j];

media = somma/(k*1.0);

/* se minore del minimo corrente aggiorno */

if(media < media_minima)

media_minima = media;

}

return media_minima;

}

Soluzione alternativa:

Quella che segue è una versione ottimizzata, che impiega tempo O(n) invece di O(nk), come la precedente.

float min_media_mobile_ottim(int a[], int n, int k)

{

float media_minima, media;

int inizio, j, somma;

somma = 0;

for(j=0; j<k; j++)

somma = somma+a[j];

media_minima = somma/(k*1.0);

for(inizio=1; inizio<n-k+1; inizio++){

/* calcolo la somma per la nuova media mobile a partire dalla somma precedente,

considerando che il nuovo intervallo ha un elemento in meno (a sinistra)

ed uno in piu' (a destra) del precedente */

somma = somma - a[inizio-1] + a[inizio+k-1];

media = somma/(k*1.0);

/* se minore del minimo corrente aggiorno */

if(media < media_minima)

media_minima = media;

}

return media_minima;

}