Le niveau general de la syntaxe des copies est assez
satisfaisant ce qui, independamment des notes finales, 
est deja une bonne chose : il y a peu de vraies erreurs 
de syntaxe, et peu d'erreurs vraiment elementaires 
(return immediat dans une boucle, variables magiques, 
etc).

----------
Exercice 1
----------
La condition "du haut vers le bas" etant par erreur 
inversee dans l'enonce, j'ai bien sur accepte deux 
solutions : celle de l'enonce, et celle de l'enonce 
corrige (curieusement, l'exemple contradictoire n'a 
pas suscite de reactions plus tot au cours de l'examen).
Cet exercice demandait un peu d'analyse. Les codes 
proposes sont parfois assez difficiles a dechiffrer 
compte tenu, trop souvent, de l'absence de commentaires 
(meme un simple developpement des noms de variables 
- e.g. "pcs : position de colonne suivante" - m'aurait 
suffi).

La correction ci-dessous est celle de l'enonce apres 
correction (on lit les colonnes du haut vers le bas).
Il faut d'une facon ou d'une autre (par un parcours
semi-diagonal ad-hoc, par memorisation d'information,
etc.) tester deux conditions :

(1) pour chaque ligne i, soit j_max[i] le plus grand
numero de colonne de valeur non nulle sur cette ligne. 
La suite j_max[0]... j_max[M-1] est croissante.

(2) pour chaque colonne j, soit i_min[j] le plus petit
numero de ligne de valeur non nulle sur cette colonne.
La suite i_min[0] ... i_min[N-1] est croissante.

Voici une solution, tres peu optimale (je n'en demandais
pas plus), mais facile a suivre : 

int en_escalier(int m[M][N]) {
  int j_max[M] = {};
  int i_min[N];
  int i,j;

  // initialisation de i_min
  for (j = 0; j < N; j++)
    i_min[j] = M - 1;
  
  for (i = 0; i < M; i++) 
    for (j = 0; j < N; j++) {
      // mises a jour de j_max[i] et de i_min[j]     
      if (m[i][j]) {
        if (j > j_max[i])
          j_max[i] = j;
        if (i < i_min[j])
          i_min[j] = i;
      }
    }
  
  // on verifie que j_max est trie
  for (i = 0; i < M - 1; i++)
    if (j_max[i] > j_max[i+1])
      return 0;

  // on verifie que i_min est trie
  for (j = 0; j < N - 1; j++)
    if (i_min[j] > i_min[j+1])
      return 0;

  return 1;
}

On pouvait aussi se contenter d'un seul tableau, par 
exemple pour memoriser les sommets de colonnes, tout 
en verifiant la condition sur les lignes dynamiquement. 
La verification du fait que ce tableau restait trie 
pouvait aussi se faire dynamiquement : dans le code 
ci-dessus, a cause de l'odre de parcours (ligne par 
ligne), le fait d'avoir i_min[j - 1] > i_min[j] 
immediatement apres une mise a jour est irrattrapable.

Voici une autre solution, basee sur un principe 
different : celui d'un parcours semi-diagonal depuis le 
coin inferieur droit de la matrice jusqu'a l'origine 
- il n'est pas completement immediat de voir pourquoi 
elle fonctionne, mais elle est algorithmiquement 
correcte :

int en_escalier(int m[M][N]) {
  // on part du coin inferieur droit de la matrice.
  int i = M-1;
  int j = N-1; 
  int ic;
  while (i >= 0 && j >= 0) {
    // on cherche la premiere valeur non nulle
    // a partir de (i,j) en allant vers la gauche.
    // si on est deja sur une valeur non nulle,
    // la boucle ci-dessous est ignoree : on 
    // remonte simplement d'une ligne.
    while (!m[i][j] && j > 0) {
      // avant de se deplacer (donc, au moment
      // ou l'on est encore sur une valeur nulle),
      // on verifie qu'il n'y a pas de valeur non 
      // nulle au dessus de la position courante...
      for (ic = i - 1; ic >= 0; ic--)
        if (m[ic][j]) 
          return 0;
      // ...ni de valeur nulle immediatement en 
      // dessous de la position courante.
      if (i < M - 1 && !m[i+1][j])
        return 0;
      j--;
    }
    // on remonte.
    i--;
  }
  return 1;
}
----------
Exercice 2
----------
Le traitement demande n'etait pas tres difficile, et 
l'exercice consistait surtout a trouver le moyen de 
le mettre en forme sans ecrire un code trop long ou 
trop dense, et sans se perdre dans les structures 
de controle - cet exercice a plutot ete reussi.

Pour copier et couper, le plus simple etait de commencer 
par calculer mecaniquement, a l'aide de calculs de mins 
et de maxs, les limites inferieure et superieure de la 
partie effectivement copiee ou coupee. On peut ensuite 
ecrire un seul traitement (et non deux, trois, quatre, 
voire plus) ne se servant plus que de ces limites. Pour 
eviter de trop saturer le code en if..else, on peut 
commencer par ecrire :

int max(int x, int y) {
  return x > y ? x : y;
}
int min(int x, int y) {
  return x < y ? x : y;
}

Copier
------
//(1) longueur de s
//(2) position de depart de la partie effectivement
//    copiee (au moins 0)
//(3) position qui suit le dernier caractere de la 
//    partie effectivement copiee (au plus ls)
//(4) longueur de la partie effectivement copiee.
//(5) copie
//(6) ajout du marqueur de fin

char *copier(char *s, int pos, int nbr) {
  int ls, debut, fin, i, lt;
  char *t;
  ls    = strlen(s);           //(1)
  debut = max(min(pos, pos + nbr - 1),      0); //(2)   
  fin   = min(max(pos, pos + nbr - 1) + 1, ls); //(3)
  lt    = fin - debut;         //(4)
  t = malloc((1 + lt)*sizeof(char));
  for (i = 0; i < lt; i++)     //(5)
    t[i] = s[debut + i];
  t[i] = '\0';                 //(6)          
  return t;
}

Couper
------
//(1) longueur de s
//(2) position de depart de la partie effectivement 
//    coupee (au moins 0)
//(3) position qui suit le dernier caractere de la partie
//    effectivement coupee (au plus ls)
//(4) longueur de la partie effectivement coupee.
//(5) longueur de la partie qui suit la partie 
//    effectivement coupee
//(6) copie de la partie avant celle coupee
//(7) copie de la partie apres celle coupee
//    ("<= lf" pour copier aussi le '\0' de s).

char *couper(char *s, int pos, int nbr) {
  int ls, debut, fin, i, j, lf, lt;
  char *t;
  ls    = strlen(s);           //(1)
  debut = max(min(pos, pos + nbr - 1),      0); //(2)   
  fin   = min(max(pos, pos + nbr - 1) + 1, ls); //(3) 
  lt    = fin - debut;         //(4)
  lf    = ls  - fin;           //(5)
  t = malloc((1 + (ls - lt))*sizeof(char));
  for (i = 0; i < debut; i++)  //(6)
    t[i] = s[i];
  for (j = 0; j <= lf; j++)    //(7)
    t[i + j] = s[fin + j];
  return t;
} 

Coller
------
//(1) longueur de s
//(2) point d'insertion effectif (au moins 0)
//(3) longueur de la partie inseree (t)
//(4) longueur de la partie qui suit dans s la position
      effective d'insertion
//(5) copie de la partie qui precede le point d'insertion
//(6) copie de la partie inseree
//(7) copie de la partie qui suit le point d'insertion
//    ("<= lf" pour copier aussi le '\0' de s).
char *coller(char *s, int pos, char *t) {
  int ls, debut, i, j, k, lf, lt;
  char *u;
  ls    = strlen(s);    //(1)
  debut = max(pos, 0);  //(2)
  lt    = strlen(t);    //(3)
  lf    = ls  - debut;  //(4)
  u = malloc((1 + ls + lt)*sizeof(char));
  for (i = 0; i < debut; i++)  //(5)
    u[i] = s[i];
  for (j = 0; j < lt; j++)     //(6)
    u[i + j] = t[j];
  for (k = 0; k <= lf; k++)    //(7)
    u[i + j + k] = s[i + k];
  return u;
} 
 
----------
Exercice 3
----------
Un exercice assez difficile, et peu traite - je ne 
m'attendais pas a ce qu'il le soit beaucoup plus. Il 
etait possible d'ecrire progr_dr de maniere a avoir 
presque gratuitement progr_ga, comme ci-dessous.

A noter que l'enonce ne fait aucune hypothese sur les
caracteres du mot dont on decline la suite de prefixes 
ou de suffixes : "abcde" n'etait qu'un exemple, et 
ces lettres n'ont aucune raison d'etre distinctes 
et/ou triees par code ascii croissant.

Question 1
----------
On discerne le cas ou s est de longueur 0 : dans ce 
cas, s est une progression droite. Sinon, on lance
la lecture de s. Dans le code ci-dessous, k designe la
longueur du prefixe courant examine a la position i. 
Les suites de caracteres 
- (s[i +     0], ..., s[i +     (k - 1)]), et 
- (s[i + k + 0], ..., s[i + k + (k - 1)])
doivent etre egales, ce qui est verifie par la boucle
interne. On saute ensuite en i + k, en incrementant la
longueur de prefixe teste. La lecture s'arrete lorsque
le dernier prefixe est en fait la fin de la chaine.

Noter que la boucle principale est ignoree si s ne 
contient qu'un seul caractere (s[1] == '\0') - dans 
ce cas, s est une progression droite, et la valeur de 
retour est bien 1.

int progr_dr(char *s) {
  int i = 0, j, k = 1;
  if (s[0] == '\0')
    return 1;
  while (s[i + k] != '\0') {
    for (j = 0; j < k; j++) {
      if (s[i + j] != s[i + k + j])
        return 0;
    }
    i = i + k;
    k = k + 1;
  }
  return 1;
}

Question 2
----------
En reprenant presque exactement le code precedent, il 
suffit de decaler les seconds membres du test interne.
Les suites de caracteres 
- (s[i + 0    ], ..., s[i +         (k - 1)]), et 
- (s[i + k + 1], ..., s[i + k + 1 + (k - 1)])
doivent etre egales.

int progr_ga(char *s) {
  int i = 0, j, k = 1;
  if (s[0] == '\0')
    return 1;
  while (s[i + k] != '\0') {
    for (j = 0; j < k; j++)
      if (s[i + j] != s[i + k + 1 + j])
       return 0;
    i = i + k;
    k = k + 1;
  }
  return 1;
}

----------
Exercice 4
----------
Trois exercices ultra-classiques, sans difficulte
particuliere - a condition bien sur d'avoir compris 
les notions de liste chainee et de recurrence.

Incrementale
------------
La premiere clef est de valeur min. La liste qui suit la 
premiere cellule a une cellule de moins, et sa valeur 
minimale est min + 1.

struct cell *incrementale(int n, int min) {
  struct cell *npc;
  if (n == 0)
    return null;
  npc = malloc(sizeof(struct cell));
  npc -> clef = min;
  npc -> suiv = incrementale(n - 1, min + 1);
  return npc;
}

Decrementale
------------
La liste a produire contient n clefs. Si la derniere vaut
min, la premiere vaut min + (n - 1). La liste qui suit la
premiere cellule a le meme min, et une cellule de moins.

struct cell *decrementale(int n, int min) {
  struct cell *npc;
  if (n == 0)
    return null;
  npc = malloc(sizeof(struct cell));
  npc -> clef = min + (n - 1);
  npc -> suiv = decrementale(n - 1, min);
  return npc;
}

Type d'increment
----------------
La valeur de retour est ID si la liste ne contient pas 
plus de deux clefs. Sinon, la valeur de retour est 
determinee par celle de l'appel recursif et la 
comparaison des valeurs des deux premieres clefs, comme 
suit :

int type_increment(struct cell *pc) {
  int ts;
  if (pc == null) return ID;
  if (pc -> suiv == null) return ID;
  ts = type_increment(pc -> suiv);
  if ((pc -> suiv -> clef == pc -> clef + 1) && 
      (ts == ID || ts == D))
    return D;
  if ((pc -> suiv -> clef == pc -> clef - 1) && 
      (ts == ID || ts == I))
    return I;
  return N;
}