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);
}