Université d'Aix-Marseille 3
DEUG Sciences - Mention MIAS
I3 - Informatique - juin 2004

Avant propos. Toutes les réponses de programmation devront impérativement être rédigées dans le langage C. Les problèmes 1, 2 et 3 peuvent être traités indépendamment.

Problème 1 - Question de cours - notion de preuve par assertions - (2 pts)

Dans ce problème, nous considérons les déclarations de variables et la séquence d'instructions qui suivent :

int x, y, z, t ;

z = x + y ;
t =x - y ;
x = z + t;
y = t - z;

Donnez la sémantique de cette séquence d'instructions en ce qui concerne la modification des valeur des variables x et y, c'est-à-dire ce que réalise cette séquence d'instructions. Justifiez votre réponse par une preuve (cf.. notion de preuve vue en cours).

Problème 2 - Fonctions et récursivité - (6 pts)

Question 1. Définissez une fonction C récursive prenant en entrée un entier strictement positif n et calculant la valeur de u_noù u_o = 2 et u_n = 3*u_n-1*u_n-1+ 2u_n-1+ 1 pour n > 0.

Question 2. Définissez une fonction C récursive prenant en entrée un entier strictement positif n et calculant la valeur de v„ où v₁ = 1, v₂= 2 et
v_n = 3*v_n-1*v_n-2 +2*v_n-2 pour n > 1.

Question 3. Définissez une fonction C récursive prenant en entrée un tableau de caractères déclaré dans le type tabcar défini ci-dessous et qui affiche toutes les lettres situées dans des cases d'indice impair.
#define n ...
typedef char tabcar[n];

Vous pouvez avoir recours à plus d'un paramètre pour définir votre fonction. Vous donnerez également la forme d'un appel à cette fonction.

Problèmes 3 - Relation binaires, tables et listes - (12 pts)

L'objectif de ce problème est d'étudier la manipulation de relations binaires quand celles-ci sont représentées dans des tableaux à 2 dimensions, puis à l'aide de listes simplement chaînées.

Partie 1. Représentation par tables

Dans cette première partie, nous considérons la structure de données définie ci-dessous qui permet de représenter des matrices booléennes, c'est-à-dire des tableaux à deux dimensions dont les éléments valent 0 ou 1

#define n ...
typedef int mat[n][n];

Dans ce problème, les matrices booléennes nous servirons à représenter des relations binaires sur l'ensemble des entiers E = {0,1,...,n-1}. Par exemple, si R est de type mat, on aura R [ i ] [ j ] qui vaudra 1 si (i,j) est un élément de la relation représentée et R [ i ] [ j ] vaudra 0 dans le cas contraire.
On rappelle qu'une relation R est dite réflexive si tout élément est en relation avec lui-même, on dira qu'elle est symétrique pour le cas où si on a (i,j) élément de la relation, alors (j,i) est aussi élément de la relation, et on dira qu'elle est transitive si, quand on a (i,j) et (j,k) éléments de la relation, alors (i,k) l'est aussi. Enfin, une relation est une relation d'équivalence si elle est réflexive, symétrique et transitive.

Question 1. Ecrire une fonction dont l'objet est de tester si une relation est réflexive.

Question 2. Ecrire une fonction permettant de vérifier qu'une relation R est une relation d'équivalence.

Partie 2. Représentation par listes simplement chaînées

Dans cette partie, les relations binaires seront représentées à l'aide de listes simplement chaînée. Vous utiliserez le type C donné ci-dessous :

#define n ...
struct chainon { int info;
                          struct chainon *suiv;};

typedef struct chainon cellule;
typedef struct chainon *liste;

Question 1. Représentez schématiquement l'état de la mémoire (tel que présenté dans le cours) à l'issue de l'exécution des lignes d'instructions données ci-dessous. L'état lors des étapes intermédiaires n'est pas demandé. Indiquez ensuite les valeurs affichées.

liste a,b,c ;

a = (liste) malloc(sizeof(cellule));
b = (liste) malloc(sizeof(cellule));
c = b;
a -> info = 12;
b -> info = 5 ;
a -> suiv = b;
b -> suiv = NULL;
c -> suiv = a;
printf(" %d " , a->info) ;
printf("%d ",b->info);
printf (" %d " , c->info) ;

Ecrivez les lignes d'instructions C permettant d'insérer entre les variables dynamiques pointées par a et par b, un nouvel élément dont la valeur sera l'entier 10.

Question 2. A partir de cette question, nous manipulons les relations binaires à l'aide de listes ainsi que du type C défini ci-dessous

typedef liste relation[n];

Il s'agit d'un tableau de pointeurs, c'est-à-dire que chaque élément R [ i ] d'une variable R de type relation, est un pointeur vers une liste simplement chaînée. Si l'on considère la liste pointée par R [ i ] , dans cette liste, nous aurons tous les entiers j tels que (i,j) est un élément de la relation représentée. Pour le cas où un couple (i,j) n'est pas élément de la relation, alors j ne figure pas dans la liste pointée par R [ i ]. Par exemple, si 4 est en relation uniquement avec 1, 6 et 12, alors la liste pointée par R [ i ] contiendra 3 éléments, dont les valeurs seront 1, 6 et 12 (dans un ordre quelconque). Si un élément i n'est en relation avec aucun autre, alors le pointeur R [ i ] aura pour valeur NULL.

Définir la fonction C suivante :

int couple(relation R, int i, int j)
/* spécifications : a pour résultat 1 si le couple (i,j) est */
/* élément de la relation R, et 0 sinon. */

Question 3. Ecrire une fonction dont l'objet est de tester si une relation est réflexive.

Question 4. Ecrire une fonction dont l'objet est de transformer une relation quelconque en relation réflexive et symétrique.

Question 5. Ecrire une fonction dont l'objet est de tester si une relation est transitive.