Algorithmique impérative/TP

Le langage de programmation le plus simple permettant d'implémenter directement un algorithme impératif par simple traduction de celui-ci est le langage Pascal, qui a été développé dans cette optique. Ainsi, un travail pratique qui peut accompagner l'apprentissage peut être simplement d'expérimenter des programmes en les recopiant et en visionnant le résultat en situation, sur une machine.

« Tester un programme peut montrer la présence de bugs, pas leur absence ».
(Edsger Dijkstra : Notes On Structured Programming, 1970)

Prérequis

Prérequis cognitif

• l'algorithmique impérative, il est évidemment nécessaire d'avoir créé des algorithmes avant de vouloir les mettre sur une machine.
• Utilisation simple de l'ordinateur (édition de texte).

Prérequis logiciels

Un éditeur de texte : le plus simple suffit. Toutefois, il existe des éditeurs de texte qui facilitent l'édition d'un code source. On les appelle les éditeurs de code-source. En plus du simple éditeur de texte, ils proposent les fonctionnalités suivantes :

• Coloration syntaxique
• Complétion automatique des mots clés
• Numérotation des lignes (vous verrez que c'est indispensable : en effet, si le compilateur trouve une erreur dans votre code source, il vous indiquera le numéro de la ligne où elle se trouve)
• Aide à l'indentation

Quelques éditeurs de code source : Notepad++ (Windows), TextMate (Mac OS), SciTE (Windows et Linux) pour les plus abordables mais aussi emacs, vi (voir la catégorie éditeur de texte sur Wikipédia pour une liste exhaustive).

Un compilateur Pascal : Free Pascal est bon, libre, gratuit et fonctionne sûrement sur votre plateforme.

Un terminal, pour lancer et tester vos programmes. Vous pouvez utiliser un terminal classique sous Linux et Mac OS X. Sous Windows, cela s'appelle « Ligne de commande DOS ».

Il existe des logiciels qui réunissent toutes ces fonctionnalités : éditeur de code + compilateur + terminal. On les appelle les environnements de développement, certains sont complexes mais il en existe de très simples qui vous permettent de compiler le code et de lancer le programme simplement en appuyant sur un bouton. Geany (Linux) est parfait à notre niveau.

Note aux étudiants : votre salle de Travaux Pratiques sera sûrement équipée, votre enseignant vous indiquera comment accéder à tout ça.

Prérequis matériels

Un ordinateur, n'importe lequel et de n'importe quelle architecture (PC ou Mac), du moment que les prérequis logiciels sont respectés.

Les limites de l'ordinateur

Un ordinateur est une machine finie (par curiosité, vous pouvez voir la notion d'automate fini). De ce fait on ne peut pas tout calculer en un temps fini. Votre algorithme peut être bon mais ne pas fonctionner sur ordinateur. La finitude se voit aussi dans les grandeurs. Vous ne pouvez pas manipuler des nombres aussi grand que vous voulez. Les technologies ont leur limite. Cependant, les ordinateurs d'aujourd'hui sont assez développés pour que vous ayez une assez grande marge de manœuvre.

Problème de la valeur entière maximale

Petit TP : faites un algorithme qui prend une valeur entière, l'augmente et l'affiche sans cesse et observez à partir de quand le programme commence à donner des valeurs incohérentes.

En Pascal par exemple : l'entier maximal représentable est contenu dans la constante MAXINT (qui vaut 32 767). Cela a pour effet d'avoir 32 767 + 1 = -32 768.

Note hors-sujet : pour comprendre pourquoi ce problème se pose : voir la partie codage des entiers signés dans le cours d'architecture des ordinateurs.

Éviter ce problème

Si vous êtes confronté au problème : essayez de changer votre algorithme en privilégiant les calculs approchant les 0. Voici un exemple plus clair : a et b sont deux entiers entre 5 000 et 10 000 avec a > b

c:=30000+a 
c:=c-b

peut ne pas fonctionner car on a dépassé 32 767. Par contre,

c:=30000-b
c:=c+a

peut fonctionner car on n'a pas dépassé 32 767.

Comment programme-t-on ?

Vous avez donc votre algorithme, comme vous êtes doué(e) : vous êtes sûr(e) qu'il fonctionne, cependant vous voulez le vérifier in situ sur un ordinateur. Voici les étapes (toutes expliquées ci-après) à suivre pour obtenir votre programme informatique :

1. Traduire l'algorithme en Pascal : cette étape peut se faire sur papier, au brouillon. Comme c'est simple et rapide on peut traduire en même temps qu'on fait l'étape suivante.
2. Recopier la traduction (le code source) dans un éditeur de texte.
3. Compiler le code source pour le transformer en programme machine (ou binaire).

Le compilateur a engendré un programme, il ne vous reste qu'à l'exécuter pour vous en servir ou le tester.

Traduire l'algorithme en Pascal

Pascal ayant été prévu dans cette optique, il est très facile de convertir un algorithme (sur papier) en un programme exécutable (fichier texte sur un ordinateur). Voici un exemple de traduction afin de vous montrer que la ressemblance est réelle et que la traduction est facile. Cet exemple reprend l'algorithme donné dans le chapitre d'introduction.

Voici l'algorithme :

Algorithme cercle
Constantes
  pi = 3.1415
Lexique
  rayon     : réel (* le rayon donné par l'utilisateur *)
  périmètre : réel (* le périmètre du cercle *)
Début
  Afficher("Donner le rayon : ")
  Lire(rayon)
  périmètre←2*pi*rayon
  Afficher("Le périmètre est de : ", périmètre)
  Afficher("L'aire du cercle est de ", pi*rayon²)
  Afficher("Le volume de la sphère est de ",(4/3)*pi*rayon³)
Fin

et le code source en langage Pascal

program cercle;
const
  pi = 3.1415;
var
  rayon     : real; (* le rayon donné par l'utilisateur *)
  perimetre : real; (* le périmètre du cercle *)
begin
  writeln('Donner le rayon : ');
  readln(rayon);
  perimetre:=2*pi*rayon;
  writeln('Le périmètre est de : ', perimetre);
  writeln('L''aire du cercle est de ', pi*sqr(rayon));
  writeln('Le volume de la sphère est de ',(4/3)*pi*power(rayon,3))
end.

Pour traduire n'importe quel algorithme dans le langage Pascal, il suffit de respecter un certain nombre de règles de syntaxe simples. Tout ceci est développé dans le guide de traduction en Pascal.

Pour ce qui est de l'indentation : utiliser la caractère de tabulation prévu pour et surtout pas d'espaces. Il s'agit de la touche à gauche de la touche A (clavier AZERTY) ou de la touche Q (en clavier QWERTY). Il est possible que vous trouviez ce caractère trop large, un bon éditeur permet de régler cette largeur en donnant la taille souhaitée en largeurs de caractères, par exemple donner 4 comme valeur fera que les tabulations ont une largeur de 4 caractères si vous utiliser une police mono-espacée (ce qui doit être le cas dans un éditeur de code). Dans le cas contraire, c'est la taille du caractère d'espacement qui est considérée (dans notre exemple, la tabulation aura la même largeur que 4 espaces). Par défaut la taille des tabulations est de 8, nous vous recommandons 2,3 ou 4 à régler selon que me nombre des niveaux d'indentations est très élevé ou plus modéré. À noter qu'on peut essayer avec un réglage à 4 puis décrémenter a posteriori si besoin est.

Avant l'exécution, la compilation

Étape (que beaucoup trouvent la plus agréable, allez savoir pourquoi...) où il n'y a rien à faire puisque le compilateur se débrouille tout seul. Il vous suffit de lui demander de compiler votre code source. Nous n'allons pas décrire ici toutes les façons de faire car il y en a de multiples : cela dépend de vos choix logiciels. (si vous êtes étudiant, votre responsable de TP est censé vous expliquer tout ça).

Lancez la compilation, deux issues sont possibles :

Premier cas : la compilation échoue. Ne paniquez pas car rien n'est joué ! C'est très courant, même les informaticiens qui ont 20 ans de métier font encore parfois des erreurs. La plupart des compilateurs vous diront pourquoi ils refusent de compiler, ils vous indiqueront même où se situe l'erreur (ligne du code source) voire, dans certains cas, ils vous donnerons l'erreur et la correction à faire. Retournez éditer votre code source et corrigez l'erreur. Vous verrez que la plupart du temps il s'agit de fautes d'inattention (des '=' à la place des ':=', d'oublis de points-virgules en fin d'instructions, etc). Relancez la compilation. Parfois il faut recompiler vingt fois avant d'arriver à finir la compilation (c'est fou ce qu'il peut y avoir comme point-virgules...).

Second cas : la compilation fonctionne. Le compilateur vous indique qu'il a réussi. Vous devriez avoir maintenant à côté de votre fichier source un exécutable.

Exécuter le programme

Là encore, il existe tellement de possibilités de faire que nous ne les expliquerons pas ici. Assurez-vous de connaître un moyen d'arrêter un programme récalcitrant. (les étudiants se tourneront encore une fois vers leur enseignants de TP).

Pour tester votre programme, entrez des valeurs comme si vous l'utilisiez. Essayez de tester "toutes" les combinaisons en faisait des essais représentatifs. à expliciter...

Un problème ?

Voici les erreurs que vous pourriez constater en exécutant votre programme et des pistes pour les résoudre :

Erreur d'exécution	Où chercher l'erreur
Le programme boucle sans fin	Assurez-vous que le programme boucle sans fin en attendant un temps assez long pour en être sûr (certains calculs peuvent être très longs) ou que le programme indique qu'il s'est arrêté car il ne peut plus continuer à consommer autant. Si le programme boucle effectivement sans fin : vous avez dans votre code source une boucle répéter ou tant que dont la condition n'est jamais atteinte. Vérifiez que vous avez une instruction qui fait tendre la ou les variables d'arrêt vers le cas d'arrêt (par exemple, n'avez-vous pas oublié d'incrémenter le i ?).
Le programme ne donne pas les bons résultats (un « bogue »)	Vérifiez votre code source (oubli d'une instruction ?). Il est très peu probable que l'ordinateur fasse des erreurs de calculs donc si vous êtes sûr de votre code source : c'est peut-être votre algorithme qui est faux (retour à la case départ :(). Si votre algorithme est bon alors faites un déboguage.
Le programme donne des résultats complètement hors de propos (comme une opération sur deux chiffres donnant = 29876 ???)	Votre programme traite de trop grands nombres et vous avez dépassé les limites de Pascal.
erreur de segmentation (ou « segfault »)	arg :(
Vous n'avez touché à rien (promis) et pourtant ça fonctionnait tout-à-l'heure" (problème le plus courant : confirmé par nombre de professeurs...)	le problème ne vient pas de l'ordinateur qui, lui, n'est pas de mauvaise foi ;)

Le déboguage

Il existe des logiciels débogueurs dont c'est le rôle, cependant nous allons expliquer la démarche « manuelle » ici. Le déboguage manuel a pour but de déceler les bogues récalcitrants qu'on a cherchés pendant des heures en mettant à contribution les collègues. Il faut comprendre par là que ce doit être un (ultime) recours et non une pratique courante. Pédagogiquement, il est préférable, pour votre apprentissage, que vous trouviez l'erreur en raisonnant et en relisant attentivement votre code source ou en revérifiant votre algorithme.

Si vous décidez malgré tout de vous lancer dans ce processus fastidieux, pénible et coûteux en temps, si plus personne ne peut vous en dissuader, voici la situation et sa solution :

Vous avez donc relu votre code source 15 fois, revérifié votre algorithme 15 fois, demandé à vos collègues qui n'ont rien pu vous dire, même votre professeur a laissé tomber et pourtant il subsiste, le bogue. Introuvable, à la fois nulle part et partout. Si vous n'en dormez plus, voilà la solution.

Le déboguage (ou debugging) consiste à afficher ce que votre programme fait en arrière plan. Concrètement, cela revient à placer des « afficher » partout dans votre code. Chaque Affichage doit être unique, de sorte que dès que vous voyez une ligne en particulier vous devez pouvoir retrouver la ligne de code ayant produit cet affichage.

Exemple, considérons le programme suivant :

...
writeln('Donnez a');
readln(a);
writeln('Donnez b');
readln(b);
c:=a+b;
if c >= 100 then
  b:=4*c+15;
else
  b:=b*c+10;
c:=b-a;
writeln(c);
repeat
  readln(a);
  c:=c+a
until (a=0);
writeln(c);
...

Créons un autre fichier .pas contenant la version déboguage du code précédant :

...
writeln('Donnez a');
readln(a);
writeln('Donnez b');
readln(b);
writeln('on va faire c:=a+b avec a valant',a,' et b valant ', b);
c:=a+b;
writeln('on a maintenant c valant : ',c)
if c >= 100 then begin
  writeln('on est passé dans le cas c >= 100');
  b:=4*c+15;
  writeln('b vaut maintenant ',b);
  end;
else begin
  writeln('on est passé dans le cas c < 100');   
  b:=b*c+10;
  writeln('b vaut maintenant ',b);
end;
writeln('on est sorti du if c >= 100 ');
writeln('on a a,b,c qui valent ',a,b,c);
writeln('on fait c:=b-a');
c:=b-a;
writeln('c vaut maintenant ',c);
writeln('on l affiche ');
writeln(c);
writeln('on est avant le repeat');
repeat
  writeln('on est dans la boucle');
  readln(a);
  writeln('on fait c:=c+a avec a et c qui valent',a,c);
  c:=c+a
  writeln('c vaut maintenant ',c);
  writeln('fin de l interieur de boucle');
until (a=0);
writeln('on est sorti de la boucle');
writeln('on affiche c');
writeln(c);
...

L'idée étant que à chaque étape, vous pouvez vérifier que toutes les données sont valides. En suivant l'exécution avec ce qui s'affiche vous devriez voir à partir de quand l'erreur se produit.

Exemple complet

Dans cette partie, nous allons voir un cycle de programmation complet.

gedit

Comme environnement de travail, on a choisi de travailler sur le système d'exploitation Ubuntu pour PC. On utilisera gedit comme éditeur de texte et le compilateur Free Pascal car tous deux sont disponibles sur Ubuntu.

Nous allons implémenter l'algorithme suivant :

Algorithme inversion_calcul
Variables
  a : entier
  b : entier
Début
  Afficher("Donnez a")
  Lire(a)
  Afficher("Donnez b")
  Lire(b)
  a := a+b
  b := a-b
  a := a-b
  Afficher("a vaut ",a)
  Afficher("b vaut ",b)
Fin

Il s'agit de l'algorithme demandant deux nombres et les inversant avant de les afficher (inutile mais c'est un exemple). Traduisons-le :

program inversion_calcul;
Var
  a : integer;
  b : integer;
begin
  writeln('Donnez a');
  readln(a);
  writeln('Donnez b');
  readln(b);
  a := a+b;
  b := a-b;
  a := a-b;
  writeln('a vaut ',a);
  writeln('b vaut ',b);
end.

On recopie la traduction dans gedit, puis on enregistre dans un fichier inversion.pas :

notre code source dans gedit

Remarquez que gedit colorie le code de façon à le rendre plus lisible (on parle de coloration syntaxique).

Passons à la compilation : on a ouvert un terminal et taper la commande

fpc inversion.pas

capture d'écran d'un terminal dans lequel on a entré la commande fpc inversion.pas pour compiler notre code source inversion.pas

Le terminal affiche alors :

Free Pascal Compiler version 2.0.4 [2006/08/22] for i386
Copyright (c) 1993-2006 by Florian Klaempfl
Target OS: Linux for i386
Compiling inversion.pas
Linking inversion
15 Lines compiled, 0.0 sec

Les 15 lignes ont bien été compilées (ligne 6), le compilateur à créé un binaire inversion. Testons-le : dans le terminal, on donne la commande ./inversion pour lancer le programme.

Le programme se lance. Voici un test :

le programme nous demande, comme prévu, d'entrer a et b. Testons avec 21 et 39

On a entré nos deux nombres : notre programme va nous donner le résultat.

affichage du résultat : 39 et 21

Notre programme semble fonctionner. Les deux nombres ont bien été inversés. L'expérience est concluante, cependant, voyons ce qu'il se passe si on atteint les limites du codage des entiers.

Testons avec deux grands nombres :

le programme nous demande, comme prévu, d'entrer a et b. Testons avec 34567 et 5123

Le programme nous indique les résultats 5123 et -30969. Notre programme, comme tous les programmes a donc ses limites même si notre algorithme est bon.