Soluzioni 27/09/2012

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:

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 . 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 nel vettore . 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 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 ,  il numero di operazioni complessive sarà:

con , quindi per concludere si ha:

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:

  1. Righe 11-15, copio gli elementi della matrice nel vettore v. costo .
  2. Riga 17, li ordino, costo .
  3. Righe 20-23, conto gli elementi distinti, caso peggiore .
  4. 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 elementi, e per ognuno vengono svolte operazioni in tempo costante, il costo totale è

Quindi ricapitolando si ha: . Di gran lunga migliore del precedente.

Esercizio 2

Esercizio 3

Soluzioni 26/07/2012

Esercizio 1

 

#include <stdio.h>
#include <assert.h>
#include <string.h>

#define LEN 1000

// Confronta le due stringhe s,t, e trova il primo carattere k
// tale che s[k] != t[k] se esiste. Restituisce -1 se s == t.

int compare(char *s, char *t)
{
	int k = 0;
	while (s[k] != '\0' && t[k] != '\0' && s[k] == t[k]) k++;
	if (s[k] != t[k]) return k; else return -1;
}

// Stampa un intorno di (al +) 5 caratteri delle stringhe s e t intorno a k.
// Si usa una stringa temporanea buf, dove si copia il segmento s[start..end]
// ed il segmento t[start..end].  con start <= k <= end
// Bisogna assicurarsi che start >= 0 e end < strlen(s) e end < strlen(t)

void output(char *s, char *t, int linea, int k)
{
	char buf[100];

	int start = k;
	for (int i=0; i<5 && start > 0; i++) start--;
	int end = k;
	for (int i=0; i<5 && t[end]!='\0' && s[end]!='\0'; i++) end++;

	strncpy(buf,s+start,end-start+1);
	buf[end-start+1] = '\0';
	printf("%3d > %s\n",linea,buf);

	strncpy(buf,t+start,end-start+1);
	buf[end-start+1] = '\0';
	printf("%3d < %s\n",linea,buf);

	for (int i=0; i<k-start+1; i++) buf[i] = ' ';
	buf[k-start+1] = '\0';
	printf("     %s!\n",buf);
}

/* Apriamo i file in argv, in lettura, poi leggiamo
   riga per riga da entrambi i file, fino a quando non arriviamo
   alla fine di uno dei due. Confrontiamo le due stringhe e
   stampiamo eventualmente se sono diverse, con le funzioni sopra.
*/
int main(int argc, char *argv[])
{
	if (argc < 3) {
		printf("confronta <file1> <file2>\n");
		return 1;
	}
    FILE *file1 = fopen(argv[1],"r");
	FILE *file2 = fopen(argv[2],"r");
	if (file1 == NULL || file2 == NULL) return 1;

	char alpha[LEN];
	char beta[LEN];
	int linea = 1;

	while (!feof(file1) || !feof(file2))
	{
		fgets(alpha,LEN,file1);
		fgets(beta,LEN,file2);
		int k = compare(alpha,beta);
		if (k >= 0)
		   output(alpha,beta,linea,k);
		linea++;
	}

	fclose(file1);
	fclose(file2);
	return 0;
}

Esercizio 2

 

#include <stdio.h>
#include <stdbool.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>

#define N 200

#define MORTA 0
#define VIVA 1

// Prima di queste funzioni si consiglia di studiare la main.

// copiam ->  a = b  tra matrici n x m

void copiam(int a[N][N], int b[N][N], int n, int m)
{
	for (int i=0; i<n; i++)
		for (int j=0; j<m; j++)
			a[i][j] = b[i][j];
}

// uguali -> a == b tra matrici n x m

bool uguali(int a[N][N], int b[N][N], int n, int m)
{
	for (int i=0; i<n; i++)
		for (int j=0; j<m; j++)
			if (a[i][j] != b[i][j]) return false;
	return true;
}

// conto il numero di vicini della cellula (i,j) vive.
// ci si muove in a[][] come se fosse un toro, quindi le
// operazioni sugli indici di riga,colonna, sono fatte modulo n,m.
// Il ciclo k in -1,0,1 e l in -1,0,1 consente di visitare tutti 
// i vicini di una cella

int contavicini_vivi(int a[N][N], int i, int j, int n, int m)
{
	int count = 0;
	for (int l=-1; l <= 1; l++)
		for (int k=-1; k <= 1; k++) {
            if (l == 0 && k == 0) continue;
			if (a[(i+l+n) % n][(j+k+m) % m] == VIVA) count++;
        }
	return count;
}

// Inizializza la matrice a in modo che a[i][j] == VIVO con probabilità p.
// Se si vuole simulare una variabile di Bernulli (VIVO,MORTO) con
// P(VIVO) = p, P(MORTO) = 1-p, allora basta generare un punto x uniforme in [0,1]
// e porre a[i][j] = VIVO se x < p. Perche X unif. in [0,1] => P(X < p) = p

void inizializza(int a[N][N], double p, int n, int m)
{
	for (int i=0; i<n; i++)
		for (int j=0; j<m; j++)
		{
			double k = (double)rand() / RAND_MAX;  // k in [0,1]
			a[i][j] = (k < p) ? VIVA : MORTA;
		}
}

void printmatrix(int a[N][N], int n, int m)
{
	for (int i=0; i<n; i++) {
		for (int j=0; j<m; j++)
			if (a[i][j] == VIVA) printf("*"); else printf(" ");
		printf("\n");
	}
	printf("\n");
}

int main(int argc, char *argv[])
{
	srand(time(NULL));

	if (argc < 4) {
		printf("errore\n");
		return 1;
	}
// leggo gli argomenti dalla linea di comando
	int n = atoi(argv[1]);
	int m = atoi(argv[2]);
	double p = atof(argv[3]);

	printf("Simulo LIFE di dimensione %dx%d (p = %f)\n",n,m,p);

   /* Rappresentiamo lo stato del sistema con due matrici di interi.
     M0 e' lo stato corrente, per passare da tempo t a t+1, dobbiamo 
     cambiare i valori della matrice M0. Non possiamo farlo in loco
     perche se cambiamo i valori intorno ad una cellula, allora l'evoluzione
     non dipenderebbe solo dai valori del tempo corrente. Usiamo quindi due
     matrici, aggiorniamo M1, e poi, copiamo il contenuto di M1 su M0 */

	int M0[N][N], M1[N][N];
	inizializza(M0, p, n, m);

	int tempo = 0;
	printf("--------- T = %d ------------\n",tempo++);
	printmatrix(M0,n,m);
	getchar();    // usiamo una getchar per fare una pausa, ricordarsi di premere invio.
	while (1) {
		// Applichiamo le regole per passare dallo stato t in M0
		// allo stato t+1 in M1.
		for (int i=0; i<n; i++)
			for (int j=0; j<m; j++) {
				int k = contavicini_vivi(M0, i, j, n, m);
				if (M0[i][j] == VIVA) {
					if (k == 2 || k == 3)
						M1[i][j] = VIVA;
					else
						M1[i][j] = MORTA;
				} else
					if (k == 3)
						M1[i][j] = VIVA;
					else
						M1[i][j] = MORTA;
			}
		if (uguali(M0,M1,n,m)) break;
		system("CLS");
		printf("--------- T = %d ------------\n",tempo++);
		printmatrix(M1,n,m);
		getchar();
		copiam(M0,M1,n,m);
	}
}

 

Esercizio 3

 

 

 

Soluzioni 12/07/2012

Esercizio 1

// Le matrici sono da suggerimento del docente statiche, quindi basta definire
// una costante per la loro dimensione.
#define N 10

/* 1) Scrivere una funzione che calcola dot(Q,i,j,n)
      il prodotto scalare tra la colonna i e j
      della matrice Q di dimensione n x n. */

double dot(double m[][N], int i, int j, int n)
{
	double t = 0;
	for (int k=0; k<n; k++) t += m[k][i]*m[k][j];
	return t;
}

/* 2) Scrivere isOrtonormale(Q,n) predicato che testa l'ortonormalità di Q */
bool isOrtonormale(double m[][N], const int n)
{
    const double eps = 1e-10;
	for (int i=0; i<n; i++) {
		double len = sqrt(dot(m,i,i,n)) - 1;
		if (fabs(len) > eps) return false;
		for (int j=0; j<n; j++) {
			if (i == j) continue;
			double val = dot(m,i,j,n);
			if (fabs(val) > eps) return false;
		}
	}
	return true;
}

/* Scrivere una funzione normalizza(Q,i,n) che normalizza
   la colonna i, cioè q[.][i] = q[.][i]/||q[.][i]||
*/

void normalize(double m[][N], int i, int n)
{
	double d = sqrt(dot(m,i,i,n));
	for (int k=0; k<n; k++) m[k][i] /= d;
}

/* Scrivere una funzione che data una matrice Q applica Gram-Schmidt e ortonormalizza
   la matrice. */

void GramSchmidt(double m[][N], int n)
{
     // (per ogni colonna)
	for (int col=0; col<N; col++) {
        // (sommatoria nella formula) (nota che se col=0, viene saltato).
		for (int j=0; j<col; j++) {
			double d = dot(m,col,j,N);    // calcolo (q_col,q_j)
            // calcolo: m[.][col] = m[.][col] - (q_col,q_j)q_j
			for (int i=0; i<N; i++) m[i][col] -= d*m[i][j];
		}
        // normalizzo..
		normalize(m,col,N);
	}
}

Commenti: 1) notare l'uso di $$fabs(..)2) usando le funzioni dot, normalize, il codice è molto modulare, e presenta un alto
grado di riusabilità. 3) la variabile n, passata alle varie funzioni poteva essere evitata
se si considera comunque fissa la dimensione, usando al suo posto nei for la costate N.

Errori gravi nei compiti svolti:

  • Mischiare uno stile di scrittura dei programmi che alterna codice C e pseudocodice tipico del corso di Algoritmi. Il compito riguarda programmazione, ogni singola riga di codice scritta deve essere C valido.
  • Non si possono introdurre nomi senza definire il loro tipo, esempio: normalize(m, i,  n) non è codice valido. Non si possono usare variabili non definite.
  • Non si possono svolgere calcoli tra vettori, tanto meno tra le colonne di un array bidimensionale (matrice), esempio: Q[i] = Q[i] + ....
  • Sbagliare a definire i limiti dei cicli è un errore GRAVE. Se si accede ad elementi non definiti, esempio, se si dichiara double Q[N][N]; e si accedere a Q[k][i] con k=N, è un errore GRAVE di accesso fuori dai limiti della matrice. Fare questo tipo di errori significa non saper ragionare su semplici proprietà aritmetiche sulle variabili del programma e sulla semantica delle operazioni di lettura di un array.

Aggiungo un programma (main) per testare le funzioni definite sopra su una matrice casuale di valori, questa è un aggiunta fuori dal compito per permettere a casa di verificare il tutto:

void print(double m[][N])
{
	for (int i=0; i<N; i++) {
		for (int j=0; j<N; j++)
			printf("%+4.3f ",m[i][j]);
		printf("\n");
	}
}

int main(int argc, char *argv[])
{
	double Q[N][N];

	// genero una matrice casuale.
	srand(1);
	for (int i=0; i<N; i++)
		for (int j=0; j<N; j++)
			Q[i][j] = (double)rand() / RAND_MAX;

	// stampo
	print(Q,N); printf("\n");

	if (isOrtonormale(Q,N))
		printf("La matrice Q e' Ortonormale\n");
	else
		printf("La matrice Q non e' Ortonormale\n");

	GramSchmidt(Q,N);
	print(Q,N); printf("\n");

	if (isOrtonormale(Q,N))
		printf("La matrice Q e' Ortonormale\n");
	else
		printf("La matrice Q non e' Ortonormale\n");
	return 0;
}

Se si vuole capire bene tutto il procedimento e testarlo anche con calcoli manuali, si consiglia di ridurre il valore di N, (N=4 va benissimo) e inserire una print della matrice dentro il primo loop della funzione di GramSchimdt per stampare i cambiamenti colonna per colonna.

Esercizio 2

/* Dichiarazione di un albero di espressioni sugli interi */

typedef struct tn {
      int val;
      struct tn *left, *right;
} Tree;

/* Nota: il valore deve (almeno) un int, per ovvi
    motivi visto che le operazioni sono sugli interi.
    Inserire un char non va bene,
    perche il tipo int è un sovrainsieme del char ma l'opposto è falso.
    Per distinguere se val è un intero o un operatore, basta controllare
    se un nodo è interno all'albero oppure è una foglia */

bool isleaf(Tree *t)
{
	return (t->left == NULL && t->right == NULL);
}

/* Stampa il contenuto dell'albero su FILE "albero_op.txt", generando la sequenza
   di assegnamenti e operazioni base, come da testo dell'esercizio 
*/

int StampaEspressione(Tree *root, FILE *f, int v)
{
	if (isleaf(root)) { fprintf(f,"t%d = %d\n",v,root->val); return ++v; }
	else {
		int t1 = StampaEspressione(root->left,v);
		int t2 = StampaEspressione(root->right,t1);
		fprintf(f,"t%d = t%d %c t%d\n",t2,t1-1,root->val,t2-1); return ++t2;
	}
}

void GeneraFile(Tree *root, char *s)
{
    FILE *f = fopen(s,"w");
    if (f == NULL) return;
    StampaEspressione(root,f,1);
}

/* Funzione EstraiRighe che stampa le righe da i a j di 
   albero_op.txt in albero_new.txt */

void EstraiRighe(int i, int j)
{
   FILE *f1 = fopen("albero_op.txt","r");
   FILE *f2 = fopen("albero_new.txt","w");
   if (f1 == NULL || f2 == NULL) return;
   char line[200];
   int k;

   for (k=0; !feof(f1) && k<i; k++) 
      fgets(line,200,f1);

   for(k=i; !feof(f1) && k<=j; k++) {
      fgets(line,200,f1);
      fputs(line,f2);
   }
   fclose(f1); fclose(f2);
}