Algorithmique impérative/TP
« Tester un programme peut montrer la présence de bugs, pas leur absence ».
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.
Prérequis.
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 :
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 ). Cela a pour effet d'avoir + 1 = -.
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 et avec a > b
c:=30000+a 
c:=c-b
peut ne pas fonctionner car on a dépassé . Par contre,
c:=30000-b
c:=c+a
peut fonctionner car on n'a pas dépassé .
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 :
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 :
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.
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 codice_1 : 
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
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 codice_2 pour lancer le programme.
Le programme se lance. Voici un test :
On a entré nos deux nombres : notre programme va nous donner le résultat.
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 indique les résultats 5123 et -30969. Notre programme, comme tous les programmes a donc ses limites même si notre algorithme est bon.