# La rédaction d'un algorithme

Lorsqu'on rédige un algorithme, il faut toujours garder à l'esprit qu'il doit pouvoir être lu et compris par quelqu'un d'autre. Au fur et à mesure de la pratique, les rédacteurs ont dégagé quelques principes dont les plus simples sont expliqués ici. Il convient de respecter ces principes d'une façon rigoureuse.
Remarque pour les étudiants : il est parfaitement admis que le respect de ces règles de rédaction soit pris en compte dans la note finale. Quand vous écrivez une dissertation, il convient de respecter la grammaire et l'orthographe même si ce n'est pas ce qui doit être évalué, il en est de même ici.

## Indenter son code

L'indentation d'une ligne est l'espace qui la sépare de la marge gauche.

### Problème

Considérons l'algorithme (incomplet) suivant :
Voici le même algorithme mais sans l'indentation :
Il est déjà moins évident de comprendre le fonctionnement de l'algorithme. Ce dernier est toutefois plus abordable que :
et pourquoi pas...

### Comment faire

Pour bien indenter, considérez les blocs et mettez au même niveau le début du bloc et la fin du bloc. Par exemple, un fin devrait se trouver au même niveau que son début : on devrait l'apercevoir immédiatement étant donné que tout ce qu'il y a entre les deux devrait se trouver un niveau d'indentation plus loin.
Procédez ainsi avec
* SI...FINSI
* TANTQUE...FTQ
* REPETER...JUSQU'A
* POUR...FP
De même : placez les alors et les sinon au même niveau.
Vous pouvez transformer ces règles, l'important étant de les fixer et de s'y tenir. Il existe plusieurs façons d'indenter et chaque auteur a ses préférences.

## Utiliser des identifiants pertinents

Pour choisir un identifiant de variable ou de fonction, souvenez-vous qu'il doit remplir deux utilités principales
* décrire son rôle (sans toutefois remplacer le commentaire en déclaration)
* distinguer des autres (ne pas se retrouver avec deux fonctions calculer_nombre et calculer_nb, quotient et division...)
Évitez :
* de répéter le type de la variable dans son identifiant (entier_n, chaine_départ)
* les conventions utilisées en maths (n ou x ne suffisent pas pour décrire le rôle d'un entier/réel)
Pensez également aux conventions, notamment :
* i (j, k...) comme variable de boucle
* utiliser un préfixe pour signaler les variables entrées du programme qui seront données par l'utilisateur.

## Commenter utile

Il ne faut pas décrire ce que vous faites mais pourquoi vous le faites
Pour cet algorithme le commentaire :
* (* il y a 24 heures dans une journée donc 24 instructions *) est pertinent. Plus particulièrement, le commentaire répond à la question "pourquoi 24 et pas 25 ?".
* (* i va de 1 à 24 *) n'est pas pertinent. Il ne répond pas à la question "pourquoi 24 et pas 23 ?".
Servez-vous également des commentaires pour indiquer ce que vous supposez : les conditions dans lesquelles votre algorithme fonctionne.

# Travaux pratiques, tester un algorithme sur une machine

« Tester un programme peut montrer la présence de bugs, pas leur absence ». (Edsger Dijkstra : Notes On Structured Programming, 1970)
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 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
peut ne pas fonctionner car on a dépassé 32 767. Par contre,
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 :
* 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.
* Recopier la traduction (le code source) dans un éditeur de texte.
* 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 :
et le code source en langage Pascal
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 :
Créons un autre fichier .pas contenant la version déboguage du code précédant :
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 :
Il s'agit de l'algorithme demandant deux nombres et les inversant avant de les afficher (inutile mais c'est un exemple). Traduisons-le :
On recopie la traduction dans gedit, puis on enregistre dans un fichier inversion.pas :
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
Le terminal affiche alors :
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 :
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.

# Guide de traduction Pascal

Voici un guide de traduction d'un algorithme impératif en Pascal.

## Le Squelette

Pour le squelette de l'algorithme :
On traduit ainsi :

## Commentaires

Les commentaires notés
s'écrivent de la même façon

## Types

Voici l'équivalence des types
| type | Pascal |
| booléen | bool |
| entier | integer |
| réel | real |
| caractère | char |
| chaîne de caractères | string |
* Les valeurs booléennes sont true et false.
* Les parties entière et décimale d'un réel sont séparées par un point et non une virgule.
* les chaînes sont déclarées entre deux apostrophes ' pour échapper un caractère on le double.
Exemple sur ce dernier point : pour inclure une apostrophe dans une chaîne,
affiche

## Constantes et variables

Les constantes et les variables ont des identifiants qui doivent respectées une syntaxe précise.
* l'identifiant ne peut comporter que des caractères alpha-numériques (de A à Z, de a à z et de 0 à 9) et des tirets-bas ou underscore : _.
* le premier caractère est une lettre.
les variables sont déclarées dans le Lexique du programme délimité par sa partie Var. Chaque déclaration est de la forme
Ainsi le lexique
se traduit
Les accents ne sont généralement pas acceptés par les compilateurs Pascal.
Les identifiants des constantes respectent les mêmes règles. Par convention, on préférera les noter en majuscules. La déclaration d'une constante a pour syntaxe
Ceci
s'écrit en pascal :

## Instructions et blocs d'instructions

Pour exécuter une instruction (assignation, appel de fonction ou procédure) il suffit de l'écrire. Les paramètres sont précisés entre parenthèses et séparés par des virgules.
Les bloc d'instructions débutent par un begin et se terminent par un end. Les instructions du bloc sont séparées par des point-virgules. On gardera la convention algorithmique préférant une instruction par ligne.
Voici une ligne comportant une instruction unique :
Voici un bloc de k d'instructions :
Remarquez qu'aucun point-virgule ne ponctue la dernière instruction. En effet le ';' est un séparateur : il sépare les instructions entre elles. Il n'y a donc pas de point-virgule après la dernière instruction, pas plus qu'il n'y en a avant la première. Cela explique également pourquoi lorsqu'on écrit une seule instruction, elle n'est pas suivie d'un point-virgule.
Il est souvent affirmé à tort que « toutes les instructions se terminent par un point-virgule ». Ce n'est pas tout à fait vrai, comme nous venons de le voir. Cependant, cette croyance répandue a été prise en considération par les développeurs des compilateurs qui ignorent cette erreur.
Il convient de remarquer que le programme principal est un bloc d'instructions ponctué d'un point, ni plus ni moins.

## Lecture et Écriture (affichage)

L'affichage s'effectue à l'aide de la procédure write. Elle peut prendre de un à plusieurs paramètres de n'importe quel type de base. Elle affiche tous les paramètres les uns après les autres (résultat identique à celui d'une concaténation).
Il existe une variante de write ayant la même spécification mais effectuant un retour à la ligne à la fin : il s'agit de la procédure writeln. On peut également appeler la procédure writln sans préciser de paramètres, cela effectue un retour à la ligne.
La lecture se fait à l'aide de la fonction read qui prend en paramètre l'identifiant de la variable qui sera assignée.
readln est indentique à read mais fait un retour à la ligne une fois la donnée lue.
Exemple
affiche
alors que
affiche

## Assignation

L'assignation est une instruction et à ce titre elle doit respecter les règles sur les instructions (points-virgules...)
L'opérateur d'assignation est := (et non = qui est le test d'égalité)
La syntaxe de l'assignation est (espaces facultatifs) :
Il va sans dire que le type de l'expression doit être compatible avec celui de la variable assignée.

## Exécution conditionnelle

On rappelle qu'une exécution conditionnelle est une instruction. Elle ne comporte pas de point-virgule sauf si elle est à l'intérieur d'un bloc. On suppose ici que l'instruction est au sein d'un bloc.
donne
S'il y a plusieurs instructions, on utilise un bloc :
Avec une instruction à exécuter quand la condition est fausse (sinon) :
se traduit
De même on peut utiliser des blocs :

## Structures itératives

Une boucle à compteur
donne
On peut toujours utiliser un bloc comme instruction pour grouper plusieurs instructions à exécuter :
De même, une boucle répétée jusqu'à ce qu'une condition soit vraie (testée après chaque itération) :
et une boucle répétée tant qu'une condition est vraie (testée avant chaque itération) :

## Tableaux

donne :
Par exemple un tableau de 10 entiers, indicé de 1 à 10 :

## Le type enregistrement

donne
Exemple :