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


Soluzioni 31/01/2012

Esercizio 1:

Testo: 

Dato il programma:

#include 

void f(int a, int b, int *c, int *d)
{
    *c = 0; *d = a;
    while (*d >= b) { *d -= b; (*c)++; }
    a = 0; b = 1;
}

int main ()
{
    int m , n , p , q ;
    scanf("%d %d %d %d ", &m , &n , &p , & q ) ;
    f(m,n,&p,&q) ;
    printf("%d %d %d %d ", m , n , p , q ) ;
}

Spiegare cosa calcola la funzione f, in modo formale. Scrivere che cosa stampa il programma se l’input è: .


Soluzione:

Dal prototipo della funzione:

void f(int a, int b, int *c, int *d)

possiamo subito notare che essendo il tipo di ritorno void, la f non è una funzione (matematicamente parlando) ma una procedura. Quindi per poter calcolare qualcosa essa deve modificare lo stato del chiamante. L'unico modo per far questo è modificare delle variabili passate per riferimento. Ed infatti le variabili c, d sono puntatori, attraverso cui modificare lo stato del chiamante. Per elimiare i puntatori dall'analisi della funzione possiamo riscrivere la funzione in questo modo (semanticamente equivalente):

void f(int a, int b, int *c, int *d)
{
    int x = 0, y = a;
    while (y >= b)    { y -= b; x++;  }
    a = 0; b = 1;
    *c = x; *d = y;
}

Notiamo quindi che le ultime istruzioni (riga 6) servono per passare il risultato del calcolo fuori dalla f, al chiamante. Le istruzioni alla riga 5 sono del tutto inutili poichè la modifica delle variabili locali a,b, non influenza dopo l'esecuzione della riga 5 il valore di x,y e non viene vista dal chiamante (perche le variabili sono locali alla funzione). Quindi il valore di x,y è determinato solo dal ciclo con le condizioni iniziali date da x=0, y=a;

Nel ciclo while, le sottrazioni ripetute nell'istruzione y -= b e il conteggio x++, ci portano intuitivamente a considerare che i valori di x,y corrispondano rispettivamente al quoziente ed al resto della divisione intera tra a e b.

Per formalizzare questa intuizione, notiamo che all'inizio del ciclo si ha: y = a; x = 0;

  • Dopo il primo passo del ciclo, si ha y = y - b, quindi y = a-b, e x = 1;
  • Dopo il secondo passo si ha: y = a - 2b, e x = 2;
  • Al passo i-esimo quindi si ha: che è l'invariante del ciclo. Il ciclo continua fino a quando y >= b, quindi quando si esce dal ciclo si ha: , e , da cui la tesi.

Esercizio 2: (Sudoku)

Testo: Dato uno schema di Sudoku, cioè una matrice quadrata 9x9, piena di interi compresi tra 1 e 9, verificare che tale matrice sia una soluzione valida del gioco. Tale soluzione e' valida se ogni riga, ogni colonna e le 9 sottomatrici che iniziano in posizione [3*i,3*j] con i=0,..2, j=0,..2 contengono i numeri da 1 a 9 senza ripetizioni.


Soluzione:


La soluzione richiede di scrivere una funzione che verifica se una matrice 9x9 è una soluzione del sudoku. Prima di presentare questa funzione, scriviamo un main per poter verificare che funzioni (il main non fa parte del compito).

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <assert.h>

#define N 9

bool check_sudoku(int m[N][N]);

int test[N][N] = {
  {5,3,4,6,7,8,9,1,2},
  {6,7,2,1,9,5,3,4,8},
  {1,9,8,3,4,2,5,6,7},
  {8,5,9,7,6,1,4,2,3},
  {4,2,6,8,5,3,7,9,1},
  {7,1,3,9,2,4,8,5,6},
  {9,6,1,5,3,7,2,8,4},
  {2,8,7,4,1,9,6,3,5},
  {3,4,5,2,8,6,1,7,9}
};

int main(int argc, char *argv[])
{
  // verifico che la matrice corretta venga riconosciuta tale.
  assert(check_sudoku(test) == true);

  // cambiamo un elemento:
  test[0][3] = test[3][0];
  assert(check_sudoku(test) == false);

  printf("ok\n");
  return 0;
}

Se la funzione check_sudoku è scritta correttamente, il main stampa "ok", in quanto su una matrice che è soluzione la funzione restituisce true, mentre se alteriamo leggermente la soluzione si deve ottenere false.
Ecco la soluzione con alcune funzioni di supporto:

// copia una sottomatrice 3x3 in posizione (a,b) da m in v
void copy_submatrix(int m[N][N], int v[N], int a, int b)
{
  int c = 0;
  for (int i=a; i<a+3; i++)
    for (int j=b; j<b+3; j++)
      v[c++] = m[i][j];
}

// true iff v e' una permutazione di {1,..9}.
bool completo(int v[N])
{
  int t[N] = { 0 };
  for (int i=0; i<N; i++) t[v[i]-1]++;
  int j = 1;
  while (j<N && t[j]) j++;
  return j == N;
}

bool check_sudoku(int m[N][N])
{
  // controllo le righe
  for (int i=0; i<N; i++)
    if (!completo(m[i])) return false;

  // controllo le colonne
  int temp[N];

  for (int i=0; i<N; i++) {
    // copio la colonna i di m in temp;
    for (int j=0; j<N; j++) temp[j] = m[j][i];
    if (!completo(temp)) return false;
  }

  // controllo le sottomatrici.
  for (int i=0; i<N; i+=N/3)
    for (int j=0; j<N; j+=N/3) {
      copy_submatrix(m,temp,i,j);
      if (!completo(temp)) return false;
    }
  return true;
}

Se volessimo implementare la funzione completo, senza usare un vettore d'appoggio, per valori di N<64, potremmo riscriverla usando delle semplici proprietà delle potenze, (che nel caso particolare della base 2, diventano degli shift) in questo modo:

bool completo2(int v[N])
{
  unsigned int x = 0;
  for (int i=0; i<N; i++) x += 1L << (v[i]-1); // x += pow(2,v[i]-1);
  return x == (1L << N)-1;                     // x == pow(2,N)-1;
}

Esercizio 3

Testo:
Considerate una base di dati di studenti, per ogni studente conservate la matricola (un intero), nome, cognome ed email (stringhe di al più 50 caratteri). Tali informazioni sono contenute in un file binario
studenti.dat, ordinati sul campo matricola. Scrivere:

  1. Una funzione che dato un numero di matricola m, trova (se esiste) e stampa le informazioni relative allo studente con matricola m, usando il minimo numero di letture possibili dal file.
  2. Considerate un albero binario che contiene solo la matricola e il cognome, ordinato sul campo cognome. Scrivere una funzione che legge i record degli studenti, e li inserisce nell’albero (in
    modo da tenerlo ordinato per il campo cognome).
  3. Scrivere una funzione che ricerca uno studente per cognome, visitando prima l’albero costruito al punto precedente, trovando la matricola corrispondente e usando poi la funzione scritta nel
    primo punto.

Soluzione:

Cominciamo con il dichiarare una struttura dati adeguata:

#define LEN 50

typedef struct s {
	int matricola;
	char nome[LEN];
	char cognome[LEN];
	char email[LEN];
} Studente;

3.1 - Ricerca Binaria

Bene, adesso per risolvere il primo problema (trovare un elemento data la matricola), possiamo sfruttare l'ordinamento dei record all'interno del file binario.
Usiamo quindi una ricerca binaria per trovare l'elemento con matricola data.

/* Esercizio 3.1, trova lo studente con matricola m,
   e stampa i dati: deve minimizzare le letture da file.
*/

void CercaStudente(FILE *fin, int m)
{
	// troviamo quanti studenti sono memorizzati:
	fseek(fin,0,SEEK_END);
	int len = ftell(fin) / sizeof(Studente);
	int low = 0, mid = 0, hi = len;
	bool trovato = false;
	Studente s;

	while (hi>low && !trovato)
	{
		// ci spostiamo nel punto di mezzo e leggiamo un record:
		mid = (low + hi) / 2;
		fseek(fin,sizeof(Studente)*mid,SEEK_SET);
		if (fread(&s,sizeof(Studente),1,fin) < 1) {
			printf("Errore in lettura\n");
			exit(EXIT_FAILURE);
		}
		// vediamo se l'abbiamo trovato
		if (s.matricola == m) {
			trovato = true;
		} else if (s.matricola < m)
			low = mid+1;
		else
			hi = mid-1;
	}

	if (trovato)
		printf("Trovato lo studente:\n"
	       "matricola: %d\n"
		   "nome: %s\n"
		   "cognome: %s\n"
		   "email: %s\n", s.matricola, s.nome, s.cognome, s.email);
}

3.2 - Costruzione Albero

Cominciamo con il dichiarare un albero con matricola e cognome, e scriviamo una piccola funzione che faccia da "costruttore" per un elemento dell'albero.

typedef struct node {
	int matricola;
	char cognome[LEN];
	struct node *l, *r;
} TreeNode;

TreeNode *newNode(int m, const char* cognome)
{
    TreeNode *p = malloc(sizeof(TreeNode));
    strcpy(p->cognome,cognome);
    p->matricola = m;
    p->l = p->r = NULL;
    return p;
}

A questo punto possiamo scrivere una funzione che inserisce un certo studente nell'albero, e quindi usare questa funzione per inserire i dati letti dal file:

void Insert(TreeNode **p, const Studente *s)
{
	TreeNode *tree = *p;
	if (tree == NULL) {
		TreeNode *new = newNode(s->matricola, s->cognome);
		*p = new;
	} else if (strcmp(s->cognome, tree->cognome) > 0) {  // s > p
		Insert(&tree->r, s);
	} else {
		Insert(&tree->l, s);
	}
}

TreeNode *CreaAlbero(FILE *f)
{
	TreeNode *radice = NULL;
	Studente s;
	int i = 0;
	while (!feof(f))
	{
		fread(&s,sizeof(Studente),1,f);
		Insert(&radice, &s);
	}
	return radice;
}

3.3 - Ricerca usando l'albero

A questo punto possiamo usare l'albero costruito per trovare (velocemente) la matricola associata ad un certo cognome. Notiamo che questo meccanismo per accelerare le ricerche per cognome vale solo se la relazione cognome<->matricola è bigettiva, cosa in generale non vera.

int TrovaMatricola(TreeNode *radice, char *cognome)
{
	if (radice == NULL) return 0;
	int cmp = strcmp(radice->cognome,cognome);
	if (cmp == 0)
		return radice->matricola;
	else if (cmp > 0)
		return TrovaMatricola(radice->l, cognome);
	else
		return TrovaMatricola(radice->r, cognome);
}

void TrovaFastCognome(TreeNode *radice, char *cognome, FILE *fin)
{
	// Ricerca per cognome, non leggo i singoli record
	// dal file ma uso l'albero.
	int matricola = TrovaMatricola(radice,cognome);
	if (matricola == 0)
		printf("Nessun studente con cognome %s\n",cognome);
	else
		CercaStudente(fin, matricola);
}