L'affectation

Déroulement linéaire

La forme la plus simple de l’algorithme est le déroulement linéaire (enchaînement).

Le déroulement linéaire en comporte aucune prise de décision. Les lignes de programme qui s’y trouvent seront toujours éxécutées dans le même ordre.
Le déroulement linéaire est le mode implicite d’exécution d’un programme. Sans instruction qui suspend ou modifie le déroulement linéaire, l’ordinateur passe toujours à l’instruction suivante après l’exécution de l’instruction courante.
La caractéristique d’un algorithme linéaire est de n’utiliser que l’enchaînement séquentiel d’actions dont la plus simple est l’affectation.

Propriété de l’affectation

Nous noterons /* $\ldots$ */ une description d’état, c’est à dire une relation entre les variables du programme et des constantes. Lorsque l’on fait une affectation, on poursuit un objectif : se rapprocher d’un résultat escompté. La nouvelle valeur de la variable modifie l’état du programme, c’est à dire les relations entre les variables.

/* n > n   */
   x = x + 1 ;
/* x > n+1 */

Dans l’exemple ci-dessus,partant de la situation $(P)\quad x > n$ on exécute l’instruction $x = x + 1$ , pour établir la relation $(Q)\quad x > n+1$ . Ce type d’affectation est si fréquemment utilisé qu’il porte un nom : incrémentation, et une écriture abrégée en langage C : $x++$ . Autre exemple :

/* 0 < x < 1 */ 
  x = (1/x) + y ;  
/*  x > y+1  */

Pour avoir la relation de la ligne 3, $x > y + 1$ , lorsque l’on a la relation de la ligne 1, $0 < x < 1$ « , il faut exécuter : $x = \frac{1}{x} +y$ . Supposons que, à la ligne 1, $x$ vaut $x_0$ , à la ligne 3, $x$ vaut $\frac{1}{x_0} + y \Rightarrow \frac{1}{x_0} + y > y +1$ , donc $0<x_0<1 \Rightarrow \frac{1}{x_0} > 1 \Rightarrow \frac{1}{x_0} + y > y +1$ .

Proprièté de l’enchaînement

Le déroulement linéaire, ou enchaînement, est une succession d’instructions pour se rapprocher d’un résultat prévu ; les relations entre les variables sont modifiées. Bien entendu, l’état final est le résultat de la succession des états intermédiares. Exemple : Supoosons $x$ et $y$ avec $0 < x < 1$ et que nous voulions $x > y +2$ nous savons que

/* 0 < x < 1 */ 
  x = (1/x) + y ;  
/*  x >  y+1  */

et que

/* x > n   */
   x = x + 1 ;
/* x > n+1 */

On exécute donc :

/* 0 < x < 1 */ 
  x = (1/x) + y ;
  x = x + 1 ;   
/*  x > y+2  */

Un exemple (dé)trompeur

Considérons l’algorithme suivant :

Saisir (x) ; Saisir (y) ; 
x = x + y ; 
y = x - y ; 
x = x - y : 
Afficher (x) ; Afficher (y) ;

Par nature, une instruction d’affectation réalise une transformation : elle change l’état d’une variable. Pour expliquer l’effet de la séquence

x = x + y ; y = x - y ; x = x - y ;

il nous faut décrire la suite engendrée par les 3 instructions. Soient donc $a$ et $b$ les valeurs initiales des variables $x$ et $y$ .

/* x == a et y == b */

Si l’on exécute l’instruction $x = x+y$ seul $x$ est modifié :

/* x == a et y == b */ 
   x = x + y ; 
/* x == a + b et y == b */

L’instruction suivante modifie $y$

/* x == a + b et y == b */ 
   y = x - y ; 
/* x == a + b et y == a  */

La dernière instruction modifie $x$

/* x == a + b et y == a */ 
   x= x - y ; 
/* x ==  (a +b) -a == b et y == a  */

Ainsi donc, les valeurs finales de $s$ et $y$ sont les permutations des valeurs initiales. On appelle « assertion » l’affirmation d’une relation vraie entre les variables du programme en un point donné. Dire comment une instruction modifie l’assertion qui la précède (pré-assertion) pour donner celle qui la suit (post-assertion) c’esrt définir la sémantique de cette instruction. Supposons que les nombres $a$ et $b$ soient des rééls et que $b$ soit très petit devant $a$ . Les calculs étants faits avec un nombre constant de chiffres significatifs, à la précision des calculs $b$ est négligeable devant $a$ et l’addition de $b$ à $a$ ne modifie pa $a$

/* x == a et y == b */     x = x + y ;
/* x == a et y == b */     y = x - y  ;

De même, retrancher $b$ de $a$ ne change pas $a$ :

/* x == a et y == a */     x = x - y ;
/* x == 0 et y == a */

L’échange des valeurs ne s’est pas fait. Il y a $0$ dans $x$ et $a$ dans $y$ . Ainsi le mécanisme des assertions peut être un mécanisme très fin décrivant même la façon dont les calculs sont éxécutés dans l’ordinateur. Il permet une interprétation très précise de l’effet d’une séquence d’instructions. C’est lui qui nous permettra de donner un sens à un programme.

002_Variables