Esercizio 1
Soluzione semplice:
#include <stdio.h>
#include <stdlib.h>
/* Anche se la dimensione esatta della matrice NON è nota
* a tempo di compilazione, sappiamo che è superiormente
* limitata da 50, quindi possiamo dichiarare matrici allocate
* staticamente.
*/
#define MAXSIZE 50
/* Procedura: modifica la sottomatrice Mat[0..n-1 ][ 0..n-1 ]
* inserendo in ogni elemento un numero scelto uniformemente
* in [-m,m]. */
void riempiacaso(const int m, const int n, int Mat[n][n])
{
for (int i=0; i<n; i++)
for (int j=0; j<n; j++) {
Mat[i][j] = rand() % (2*m + 1) - m;
printf("%3d%c", Mat[i][j], j==n-1?'\n':' ');
}
}
/* Per calcolare le frequenze serve
v - un vettore dei valori unici
f - il numero di occorrenze di v[i]
*/
struct freq {
int *v;
int *f;
int size;
};
typedef struct freq Freq;
La funzione richiesta nella prima parte dell’esercizio deve restituire il vettore che contiene i valori (unici) presenti nella matrice e per ognuno la sua frequenza. La struttura Freq che conterrà questi vettori è una soluzione corretta se soddisfa la seguente specifica formale:
$$\forall\; i,j \in [0,n), \exists\; ! k\; \mbox{ with } v_k = Mat_{ij} \;\wedge\; \forall\; i, f_i = |\{ \forall l,h \in [0,n), v_i = Mat_{lh} \}|$$
Freq distribuzione(int n, int Mat[n][n])
{
int *v = malloc(sizeof(int)*n*n);
int *f = malloc(sizeof(int)*n*n);
int count = 0;
for (int i=0; i<n; i++)
for (int j=0; j<n; j++) {
// vediamo se mat[i][j] sta in v[0..count-1]
int k = 0;
while (k < count && v[k] != Mat[i][j])
k++;
if (k == count) {
v[k] = Mat[i][j]; f[k] = 1; count++;
} else {
f[k]++;
}
}
Freq r = { v, f, count };
return r;
}
#define N 20
int main(int argc, char *argv[])
{
if (argc < 2) {
printf("%s intero\n",argv[0]);
return -1;
}
int m = atoi(argv[1]);
int Mat[MAXSIZE][MAXSIZE];
riempiacaso(m, N, Mat);
Freq result = { NULL, NULL, 0 };
result = distribuzione(N,Mat);
printf("size = %d\n",result.size);
printf("v = (");
for (int i=0; i<result.size; i++)
printf("%3d,",result.v[i]);
printf(")\n");
printf("f = (");
for (int i=0; i<result.size; i++)
printf("%3d,",result.f[i]);
printf(")\n");
return 0;
}
Valutazione della Complessità Computazionale:
La funzione distribuzione riempie il vettore v con gli elementi unici della matrice, a causa dei due for quindi possiamo dire subito che la complessità ti tempo appartiene a $$\Omega(n^2)$$. Questo però non è un limite stretto in quanto dobbiamo ancora contare le altre operazioni.
Adesso studiamo il costo delle operazioni svolte per ognuno degli elementi della matrice. Le operazioni associate all’if-else delle linee 13-17 possono essere eseguite in tempo costante quindi non aumentano il costo computazionale, concentriamoci invece sul while di linea 11-12.
Il while esegue una ricerca lineare del valore $$Mat[i][j]$$ nel vettore $$v[0..count)$$. Il costo nel caso peggiore si verifica quando l’elemento NON è presente, quindi siamo costretti a scorrere ed eseguire esattamente count confronti.
Notiamo che count dipende dall’iterazione che stiamo eseguendo, ed in particolare esso parte da $$0$$ viene incrementato in ogni iterazione perche nel caso peggiore tutti gli elementi della matrice sono diversi e vengono sempre eseguite le istruzioni del ramo if. Poichè quindi count viene incrementato da 0 a $$n^2$$, il numero di operazioni complessive sarà:
$$S(N) = \sum_{i=1}^{N} = \frac{N(N+1)}{2}$$ con $$N = n^2$$, quindi per concludere si ha: $$T_{distribuzione}(n) \in \Theta(\frac{n^2(n^2+1)}{2}) = \Theta(n^4)$$
E’ possibile fare di meglio? cioè esiste un altro algoritmo con complessità computazionale minore? E’ evidente che il costo dovuto alla ricerca lineare è il fattore che penalizza la soluzione proposta, un algoritmo migliore dovrebbe quindi diminuire il tempo necessario per aggiornare la frequenza di un elmento. Ecco come fare:
int cmp(const void *a, const void *b)
{
int x = *(int*)a;
int y = *(int*)b;
return x - y;
}
Freq distribuzione2(int n, int Mat[n][n])
{
// Copiamo Mat su un vettore v;
int *v = malloc(sizeof(int)*n*n);
int c = 0;
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
v[c++] = Mat[i][j];
// Ordiniamo il vettore
qsort(v, n*n, sizeof(int), cmp);
// Controlliamo quanti sono i valori distinti presenti (ottimizzazione)
int count = 0;
for (int i=0; i<n*n-1; i++)
if (v[i] != v[i+1]) count++;
count++;
// allochiamo il risultato
int *p = malloc(sizeof(int)*count);
int *f = malloc(sizeof(int)*count);
int i = 0, k = 0;
do {
//printf("%d %d %d\n",k,i,v[i]);
p[k] = v[i++]; f[k] = 1;
while (i < n*n && p[k] == v[i]) { f[k]++; i++; }
k++;
} while (i < n*n);
free(v);
Freq r = { p, f, count };
return r;
}
Vediamo come funziona questo algoritmo e la sua complessità computazionale:
- Righe 11-15, copio gli elementi della matrice nel vettore v. costo $$\Theta(n^2)$$.
- Riga 17, li ordino, costo $$\Theta(n^2\log{n^2})$$.
- Righe 20-23, conto gli elementi distinti, caso peggiore $$\Theta(n^2)$$.
- Righe 29-34: per calcolare la complessità computazionale di questo ciclo, bisogna prima di tutto capire intuitivamente cosa fa. L’idea è la seguente, si considera un elemento di v, poichè il vettore è ordinato, gli elementi uguali sono memorizzati nelle posizioni immediatamente successive, quindi il ciclo di riga 32 conta tali elementi calcolando la loro frequenza, se alla fine abbiamo esaurito gli elementi di v, allora abbiamo finito, altrimenti si passa all’elemento successivo, poichè complessivamente ci sono $$n^2$$ elementi, e per ognuno vengono svolte operazioni in tempo costante, il costo totale è $$\Theta(n^2)$$
Quindi ricapitolando si ha: $$$T_{distribuzione2}(n) \in \Theta(n^2\log n^2)$$. Di gran lunga migliore del precedente.