Quelques remarques sur l'examen en attendant les notes 
definitives. Au final, et malgre un bareme tres favorable,
le niveau est seulement moyen : environ une moitie des copies
sont a peu pres au niveau (dont certaines seulement grace au 
projet). Dans les autres, la syntaxe du langage est a peu 
pres globalement acquise, mais les bases de la programmation 
(capacite a analyser un probleme, a le decomposer en elements
simples, a en trouver une methode de resolution puis a 
l'implementer sans trop d'erreurs) sont encore tres 
insuffisantes.

VP.

--------
Partie I
--------
Theme : boucles imbriquees.

Cet partie, de niveau elementaire, a ete largement aborde
et dans l'ensemble relativement bien comprise, meme si 
presque toutes les copies effectuent au moins un acces 
en dehors de m dans l'une ou l'autre des fonctions.

Question I.1
------------
On doit avoir, pour chaque ligne i autre que la derniere 
(donc en faisant varier i de 0 a TAILLE - 1 exclus): 

- m[i][0] == m[i+1][1]
- ...
- m[i][j] == m[i+1][j+1]
- ...
- m[i][TAILLE-2] == m[i+1][TAILLE-1]
- m[i][TAILLE-1] == m[i][0]

On peut donc, pour chaque i, soit faire tous ces tests sauf 
le dernier via une boucle en j allant de 0 a TAILLE - 2 inclus
et ajouter un test singulier pour la case m[i][TAILLE-1], 
soit mieux encore, ecrire un test uniforme en utilisant 
l'operateur modulo (TAILLE % TAILLE == 0) :

int enroulement(int m[TAILLE][TAILLE]) {
  int i, j;
  for (i = 0; i < TAILLE - 1; i++) 
    for (j = 0; j < TAILLE; j++) 
      if (m[i][j] != m[i+1][(j + 1)%TAILLE])
         return 0;
  return 1;
}

Noter que la boucle en i gere correctement le cas ou
TAILLE est egal a 1 ou 0 - dans ce cas, le corps de la
boucle externe n'est pas execute, et la matrice est
trivialement un enroulement droit. 

erreurs-type I.1
----------------
- oubli de la gestion singuliere de la derniere colonne. 
(e.g. test m[i][j] == m[i+1][j+1] pour chaque case, avec
en particulier acces en dehors de m sur la derniere colonne
et la derniere ligne) 

- copie de la premiere ligne dans un tableau auxiliaire, avec
rotation du tableau auxiliaire a chaque changement via une 
fonction auxiliaire. Meme menee a bout (ce qui n'est
pas toujours le cas dans les copies ayant tente cette 
approche) cette methode est inefficace. Sans etre fausse 
dans son principe, elle montre plutot que vous n'avez pas 
reussi a analyser vraiment le probleme.

- adaptation approximative de la fonction "cascade" de 
l'examen de 2004 pour cette question et la suivante
(et la, aucune analyse du probleme... un enroulement est 
en particulier une cascade, mais l'inverse est faux).

Question I.2
------------
Avec le meme operateur %, l'enroulement peut etre ecrit en 
notant que la case n. 0 de t doit apparaitre sur la colonne 
i de la ligne i pour chaque i :

void enrouler(int t[TAILLE], int m[TAILLE][TAILLE]) {
  int i, j;
  for (i = 0; i < TAILLE; i++) 
    for (j = 0; j < TAILLE; j++) 
      m[i][(i + j) % TAILLE] = t[j];
}

On peut sinon decomposer la boucle interne en deux parties,
corespondant aux copies de deux tranches de t :

- m[i][j] = t[j - i] pour j allant de i a TAILLE - 1
- m[i][j] = t[TAILLE - i + j] pour j allant de 0 a i - 1.

On peut encore recopier t sur la premiere ligne, puis 
recopier chaque ligne sur la suivante en effectuant sa 
rotation, sur le modele du test.


erreurs-type I.2
----------------
- principe de la copie en deux tranches compris, mais erreurs
dans les calculs de decalages.

- rotation de t apres chaque copie de ligne via une fonction 
auxiliaire (c.f. ci-dessus).

- enroulement gauche au lieu de droit.

---------
Partie II
---------
Theme : parcours de structure lineaire avec mise en memoire 
d'information.

Les questions de cette partie n'etaient pas toutes du meme
niveau de difficulte. La question 4 (tableau des positions
a partir du tableau des longueurs) etait la plus simple. Les
questions 1 et 3 (pyramidal, tableau des longueurs), assez 
similaires dans leur traitement, etaient de difficulte 
moyenne. La question 2 (incremental) etait plus difficile, 
et la 5 (symetrique) assez difficile. Les erreurs communes 
aux questions de cette partie, tres frequentes meme dans
les reponses pour lesquelles le principe du traitement a ete
plutot bien compris, ont ete :

- erreurs dans les calculs de decalages (\n non pris en 
compte ou mal pris en compte).

- erreurs dans les mises a jour d'indices (indice non mis 
a jour, erreur de replacement d'un indice)

- controle confus : tests inutiles, gestion approximative de
3, 4, 5 indices dependants, confusion entre position absolue
et position relative a un autre indice, confusions d'indices.

Question II.1
-------------
Il faut, d'une facon ou d'une autre, calculer la longueur
de chaque ligne en ayant memorise la longueur de la ligne
precedente, afin de comparer ces deux longueurs.

int pyramidal(char *s) {
    /* lp : longueur de la ligne precedente (ou 0)
     * lc : longueur de la ligne courante
     */
  int i = 0, lp = 0, lc = 0;
  for (i = 0; s[i] != '\0'; i++) {
    if (s[i] == '\n') {
      if (lc < lp) 
        return 0;
      lp = lc;
      lc = 0;
    }
    else lc++;
  }
  return 1;
}

erreurs-type II.1
-----------------
- pompage vraiment trop primaire.

Question II.2
-------------
Il faut pour cette question memoriser la position de depart
de la ligne precedente, de maniere a pouvoir la comparer a
la ligne courante.

// dlp est place au debut de la ligne 
// precedente apres la premiere iteration,
// et sinon, au debut de la premiere ligne :
// a la premiere iteration, la premiere
// ligne sera comparee avec elle-meme.
//
// (1) on verifie que la ligne precedente
// est prefixe de la ligne courante.
//
// (2) on memorise dans dlp le debut
// de la ligne courante.
//
// (3) on cherche la fin de la ligne 
// courante

// (4) on place i apres la fin de celle-ci.

int incremental(char *s) {
  int i = 0, dlp = 0, j;
  while (s[i] != '\0') {
    j = 0;
    while (s[dlp + j] != '\n') {   // (1)
      if (s[dlp + j] != s[i + j]) 
        return 0;
      j++;
    }
    dlp = i;                       // (2)
    while (s[i + j] != '\n')       // (3)
      j++;
    i += j + 1;                    // (4)
  }
  return 1;
}

erreurs-type II.2
-----------------
- utilisation assez incertaine d'un ou plusieurs tableaux
auxiliaires.


Question II.3
-------------
Cette question ressemble assez a la premiere : il faut 
calculer la longueur de la ligne courante, et la stocker 
dans le tableau des longueurs. On doit d'abord parcourir 
integralement s pour compter le nombre de lignes (i.e. le 
nombre de \n) pour connaitre la longueur de t.

int *tableau_longeurs(char *s) {
    /* nl : nombre de lignes
     * lc : longueur de la ligne courante
     * it : position d'ecriture dans t
     */
    int i, it, nl = 0, *t, lc = 0;

    /* calcul du nombre de lignes */
    for (i = 0; s[i] != '\0'; i++)   
	nl += (s[i] == '\n');
    /* allocation de t */
    t = malloc((1 + nl) * sizeof(int));

    /* placement en 0 dans t */
    it = 0;
    /* parcours de s */
    for (i = 0; s[i] != '\0'; i++) {
	/* a chaque fin de ligne */
	if (s[i] == '\n') {
	    /* transfert de la longueur de la ligne
	     * courante dans t
	     */
	    t[it] = lc;
	    it++;
	    /* reinitialisation de la longeur */
	    lc = 0;
	}
	/* incrementation de la longueur */
	else lc++;
    }
    t[it] = -1;                        
    return t;
}

erreurs-type II.3
-----------------
Les erreurs les plus frequentes concernent moins le 
remplissage du tableau (un traitement elementaire) 
que son allocation :

- extension magique du tableau alloue par mallocs repetes,

- taille d'allocation magiquement initialisee a la bonne
valeur, ou allocation a posteriori apres ecriture dans
un tableau non alloue.

- ecriture et retour de tableau non alloue

- retour d'un tableau local.

- oubli du +1 dans l'allocation pour le marqueur de fin.

- allocation d'un tableau de meme longueur que s (+1) et 
non de taille egale au nombre de lignes de s (+1)

- tableau en int t, retour de *t ou &t.


Question II.4
-------------
Le calcul du tableau des positions a partir du tableau des
longueur est un traitement elementaire. La seule chose a
ne pas oublier est de tenir compte des \n en fin de ligne.

// i   : indice de lecture dans t et d'ecriture dans p
// pos : position courante dans le texte d'origine.
//
// (1) calcul de la longeur de t
// 
// (2) calcul des positions successives de debuts
// de lignes dans le texte d'origine. noter le +1
// pour tenir compte du \n a la fin de chaque ligne.


int *tableau_positions(int *t) {
  int i, *p, pos = 0;

  for (i = 0; t[i] != -1; i++);    // (1)
  p = malloc((1 + i)*sizeof(int));

  for (i = 0; t[i] != -1; i++) {   // (2)
    p[i] = pos;
    pos += t[i] + 1;
  }
  p[i] = -1;
  return p;
}

erreurs-type II.4
-----------------
- pas d'allocation du tableau ou retour de tableau local


Question II.5
-------------
Un exercice, comme indique dans l'enonce, difficile, et 
resolu (a quelques erreurs pres) dans une seule copie. 
Voici une maniere de l'ecrire :

// nl : nombre de lignes du texte symetrique
// nc : nombre de colonnes du texte symetrique.
//
// (1) recherche du max de t, egal au 
// nombre de lignes du symetrique,
// et calcul de la longueur de t,
// egal au nombre de colonnes sans la colonne de \n
//
// (2) remplissage

char *symetrique(char *s) {
  int *t, *p, i, j, nl = 0, nc = 0;
  char *ts;
  t = tableau_longueurs(s);
  p = tableau_positions(t);

  for (i = 0; t[i] != -1; i++) {  // (1)
    nc++;
    if (t[i] > nl) 
      nl = t[i];
  }
  ts = malloc((nc + 1) * nl + 1);
 
  for (i = 0; i < nl; i++) {      // (2)
    for (j = 0; j < nc; j++) 
      if (i < t[j]) 
	ts[i * (nc + 1) + j] = s[p[j] + i];
      else ts[i * (nc + 1) + j] = ' ';
    ts[i * (nc + 1) + nc] = '\n';
  }
  ts[(nc + 1) * nl] = '\0';
  free(t);
  free(p);
  return ts;
}
    
----------
Partie III
----------
Theme : recurrence.

Cette partie ne presentait aucune difficulte majeure, a 
condition d'avoir compris les notions de chainage et de 
recurrence. Si la premiere notion semble a peu pres acquise,
la seconde semble encore tres incertaine, comme en temoigne
l'assez joyeuse proliferation de syntaxe semi-aleatoire
dans l'ecriture des fonctions :

- appels recursifs ecrits de facon imperative (suivis ou 
non d'un return), melange confus entre iteration et 
recurrence,

- affectation d'appel recursif a pc -> suiv, a pc -> clef 
(??), pas d'appel recursif, retour de pc -> suiv ou de
pc -> clef.

- utilisation de compteurs locaux magiquement partages par 
tous les appels, ou un peu mieux (mais pas encore ca), 
compteur global.

Question III.1
--------------

// (1) par definition, la liste vide est duplicante
// (2) par definition, la liste singleton ne l'est pas
// (3) si une liste contient au moins deux clefs, elle
//  est duplicante si ses deux premieres clefs sont 
//  egales, et si la liste commencant a la seconde clef 
//  est duplicante.

int duplicante(struct cell *pc) {
  if (pc == NULL)             // (1)
    return 1;
  if (pc -> suiv == NULL)     // (2)
    return 0;
  return 
    (pc -> clef == pc -> suiv -> clef) // (3)
    && duplicante(pc -> suiv -> suiv);
}

erreurs-type III.1
------------------
- oubli ou mauvaise gestion des cas de base (liste vide, 
liste a une seule clef)
- definition de "duplicante" mal comprise.

Question III.2
--------------
Noter que l'enonce precise que la fonction suppose
que la liste contient au moins i + 1 clefs (en fait,
supposer qu'elle contient i clefs suffit) : inutile, 
donc, de faire des tests pour verifier que pc -> suiv
est bien defini.

// (1) la liste commencant a la clef de rang 0
// dans pc est pc elle-meme
// (2) si i > 0, la liste commencant a la clef
// de rang i dans pc est la liste commencant a 
// la clef de rang i - 1 dans la liste commencant 
// a la clef de rang 1 dans pc, c'est-a-dire la
// liste pc -> suiv.

struct cell *suite(int i, struct cell *pc) {
  if (i == 0)   // (1)
    return pc;
  return        // (2)
    suite(i - 1, pc -> suiv);
}

erreurs-type III.2
------------------
- pas de condition d'arret (1)
- premiere clef de rang 1 au lieu 0.

Question III.3
--------------
// On suppose k positif ou nul.
// (1) si k == 0, pc commence bien par 0 clefs identiques.
// (2) si k == 1, pc ne doit pas etre vide.
// (3) si k >= 2, pc doit contenir au moins deux elements.
// (4) de plus, ses deux premiers elements doivent etre
// egaux, et la liste commencant apres la clef de rang 0 
// doit commencer par k - 1 valeurs de clefs identiques.

int *clef_prefixe(int k, struct cell *pc) {
  if (k == 0) // (1)
    return 1;
  if (k == 1) // (2)
    return pc != NULL;
  if (pc -> suiv == NULL) // (3)
    return 0;
  return                  // (4)
    pc -> clef == pc -> suiv -> clef &&
    clef_prefixe(k - 1, pc -> suiv);
}

erreurs-type III.3
------------------
- enonce mal compris.


Question III.4
--------------
// (1) si la liste est vide, elle est bien n-replicante
// (2) sinon, elle doit commencer par n clefs identiques,
// et la liste commencant a la clef de rang n doit aussi
// etre n-replicante.

int replicante(int n, struct cell *pc) {
  if (pc == NULL) // (1)
    return n;
  return          // (2)
    clef_prefixe(n,pc) &&
    replicante(suite(n,pc));
}

----------------
Casse-tete final
----------------
Theme : calcul de composante connexe d'un graphe par 
construction de sa cloture transitive.

Il faut determiner toutes les pieces que l'on peut atteindre 
a partir de l'entree du labyrinthe pour lesquelles il existe
un chemin de retour. Le plus simple est de commencer par
surcharger le plan en indiquant, pour chaque piece i, 
l'ensemble de toutes les pieces que l'on peut atteindre 
en partant de i et en se deplacant au hasard de piece en 
piece. Il suffit d'iterer sur la matrice l'operation 
suivante, jusqu'a ce qu'elle ne fasse plus passer a 1 
aucune case :

  pour chaque i, j, k, si m[i][j] et m[i][k] sont a 1 et 
  m[i][k] est a 0, on fait passer a 1 la case m[i][k].


On peut montrer qu'apres ce traitement, m[i][j] est a 1 si 
et seulement si il existe une suite non vide de passages 
menant de i a j. Pour chaque couple de pieces i, j distincts,
on peut donc immediatement savoir si on peut aller de i 
jusqu'a j puis revenir en i (en particulier pour i == 0) : 
m[i][j] et m[j][i] doivent etre tous les deux a 1.