algorithme(part1)

Définitions

1- Algorithmique et programmation

Pourquoi apprendre l’algorithmique pour apprendre à programmer ? En quoi a-t-on besoin d’un langage spécial, distinct des langages de programmation compréhensibles par les ordinateurs ?
Parce que l’algorithmique exprime les instructions résolvant un problème donné indépendamment des particularités de tel ou tel langage. Pour prendre une image, si un programme était une dissertation, l’algorithmique serait le plan, une fois mis de côté la rédaction et l’orthographe. Or, vous savez qu’il vaut mieux faire d’abord le plan et rédiger ensuite que l’inverse…
Apprendre l’algorithmique, c’est apprendre à manier la structure logique d’un programme informatique. Cette dimension est présente quelle que soit le langage de programmation ; mais lorsqu’on programme dans un langage (en C, en Visual Basic, etc.) on doit en plus se colleter les problèmes de syntaxe, ou de types d’instructions, propres à ce langage. Apprendre l’algorithmique de manière séparée, c’est donc sérier les difficultés pour mieux les vaincre.
A cela, il faut ajouter que des générations de programmeurs, souvent autodidactes (mais pas toujours, hélas !), ayant directement appris à programmer dans tel ou tel langage, ne font pas mentalement clairement la différence entre ce qui relève de la structure logique générale de toute programmation (les règles fondamentales de l’algorithmique) et ce qui relève du langage particulier qu’ils ont appris. Ces programmeurs, non seulement ont beaucoup plus de mal à passer ensuite à un langage différent, mais encore écrivent bien souvent des programmes qui même s’ils sont justes, restent laborieux. Car on n’ignore pas impunément les règles fondamentales de l’algorithmique… Alors, autant l’apprendre en tant que telle !
Bon, maintenant que j’ai bien fait l’article pour vendre ma marchandise, on va presque pouvoir passer au vif du sujet…

2. Avec quelles conventions écrit-on un algorithme ?

Historiquement, plusieurs types de notations ont représenté des algorithmes.
Il y a eu notamment une représentation graphique, avec des carrés, des losanges, etc. qu’on appelait des organigrammes. Aujourd’hui, cette représentation est quasiment abandonnée, pour deux raisons. D’abord, parce que dès que l’algorithme commence à grossir un peu, ce n’est plus pratique du tout du tout. Ensuite parce que cette représentation favorise le glissement vers un certain type de programmation, dite non structurée (nous définirons ce terme plus tard), que l’on tente au contraire d’éviter.
C’est pourquoi on utilise généralement une série de conventions appelée « pseudo-code », qui ressemble à un langage de programmation authentique dont on aurait évacué la plupart des problèmes de syntaxe. Ce pseudo-code est susceptible de varier légèrement d’un livre (ou d’un enseignant) à un autre. C’est bien normal : le pseudo-code, encore une fois, est purement conventionnel ; aucune machine n’est censée le reconnaître. Donc, chaque cuisinier peut faire sa sauce à sa guise, avec ses petites épices bien à lui, sans que cela prête à conséquence.
Comme je n’ai pas moins de petites manies que la majorité de mes semblables, le pseudo-code que vous découvrirez dans les pages qui suivent possède quelques spécificités mineures qui ne doivent qu’à mes névroses personnelles.
Rassurez-vous cependant, celles-ci restent dans les limites tout à fait acceptables.
En tout cas, personnellement, je les accepte très bien.




Les Variables

1. A quoi servent les variables ?

Dans un programme informatique, on va avoir en permanence besoin de stocker provisoirement des valeurs. Il peut s’agir de données issues du disque dur, fournies par l’utilisateur (frappées au clavier), ou que sais-je encore. Il peut aussi s’agir de résultats obtenus par le programme, intermédiaires ou définitifs. Ces données peuvent être de plusieurs types (on en reparlera) : elles peuvent être des nombres, du texte, etc. Toujours est-il que dès que l’on a besoin de stocker une information au cours d’un programme, on utilise une variable.
Pour employer une image, une variable est une boîte, que le programme (l’ordinateur) va repérer par une étiquette. Pour avoir accès au contenu de la boîte, il suffit de la désigner par son étiquette.
En réalité, dans la mémoire vive de l’ordinateur, il n’y a bien sûr pas une vraie boîte, et pas davantage de vraie étiquette collée dessus (j’avais bien prévenu que la boîte et l’étiquette, c’était une image). Dans l’ordinateur, physiquement, il y a un emplacement de mémoire, repéré par une adresse binaire. Si on programmait dans un langage directement compréhensible par la machine, on devrait se fader de désigner nos données par de superbes 10011001 et autres 01001001 (enchanté !). Mauvaise nouvelle : de tels langages existent ! Ils portent le doux nom d’assembleur. Bonne nouvelle : ce ne sont pas les seuls langages disponibles.
Les langages informatiques plus évolués (ce sont ceux que presque tout le monde emploie) se chargent précisément, entre autres rôles, d’épargner au programmeur la gestion fastidieuse des emplacements mémoire et de leurs adresses. Et, comme vous commencez à le comprendre, il est beaucoup plus facile d’employer les étiquettes de son choix, que de devoir manier des adresses binaires.

2. Déclaration des variables
La première chose à faire avant de pouvoir utiliser une variable est de créer la boîte et de lui coller une étiquette. Ceci se fait tout au début de l’algorithme, avant même les instructions proprement dites. C’est ce qu’on appelle la déclaration des variables. C’est un genre de déclaration certes moins romantique qu’une déclaration d’amour, mais d’un autre côté moins désagréable qu’une déclaration d’impôts.
Le nom de la variable (l’étiquette de la boîte) obéit à des impératifs changeant selon les langages. Toutefois, une règle absolue est qu’un nom de variable peut comporter des lettres et des chiffres, mais qu’il exclut la plupart des signes de ponctuation, en particulier les espaces. Un nom de variable correct commence également impérativement par une lettre. Quant au nombre maximal de signes pour un nom de variable, il dépend du langage utilisé.
En pseudo-code algorithmique, on est bien sûr libre du nombre de signes pour un nom de variable, même si pour des raisons purement pratiques, et au grand désespoir de Stéphane Bern, on évite généralement les noms à rallonge.
Lorsqu’on déclare une variable, il ne suffit pas de créer une boîte (réserver un emplacement mémoire) ; encore doit-on préciser ce que l’on voudra mettre dedans, car de cela dépendent la taille de la boîte (de l’emplacement mémoire) et le type de codage utilisé.

2.1 Types numériques classiques
Commençons par le cas très fréquent, celui d’une variable destinée à recevoir des nombres.
Si l’on réserve un octet pour coder un nombre, je rappelle pour ceux qui dormaient en lisant le chapitre précédent qu’on ne pourra coder que 28 = 256 valeurs différentes. Cela peut signifier par exemple les nombres entiers de 1 à 256, ou de 0 à 255, ou de –127 à +128… Si l’on réserve deux octets, on a droit à 65 536 valeurs ; avec trois octets, 16 777 216, etc. Et là se pose un autre problème : ce codage doit-il représenter des nombres décimaux ? des nombres négatifs ?
Bref, le type de codage (autrement dit, le type de variable) choisi pour un nombre va déterminer :
• les valeurs maximales et minimales des nombres pouvant être stockés dans la variable
• la précision de ces nombres (dans le cas de nombres décimaux).
Tous les langages, quels qu’ils soient offrent un « bouquet » de types numériques, dont le détail est susceptible de varier légèrement d’un langage à l’autre. Grosso modo, on retrouve cependant les types suivants :

Type Numérique Plage
Byte (octet) 0 à 255
Entier simple -32 768 à 32 767
Entier long -2 147 483 648 à 2 147 483 647
Réel simple -3,40x1038 à -1,40x1045 pour les valeurs négatives
1,40x10-45 à 3,40x1038 pour les valeurs positives
Réel double 1,79x10308 à -4,94x10-324 pour les valeurs négatives
4,94x10-324 à 1,79x10308 pour les valeurs positives

Pourquoi ne pas déclarer toutes les variables numériques en réel double, histoire de bétonner et d’être certain qu’il n’y aura pas de problème ? En vertu du principe de l’économie de moyens. Un bon algorithme ne se contente pas de « marcher » ; il marche en évitant de gaspiller les ressources de la machine. Sur certains programmes de grande taille, l’abus de variables surdimensionnées peut entraîner des ralentissements notables à l’exécution, voire un plantage pur et simple de l’ordinateur. Alors, autant prendre dès le début de bonnes habitudes d’hygiène.
En algorithmique, on ne se tracassera pas trop avec les sous-types de variables numériques (sachant qu'on aura toujours assez de soucis comme ça, allez). On se contentera donc de préciser qu'il s'agit d'un nombre, en gardant en tête que dans un vrai langage, il faudra être plus précis.
En pseudo-code, une déclaration de variables aura ainsi cette tête :
Variable g en Numérique
ou encore
Variables PrixHT, TauxTVA, PrixTTC en Numérique
2.2 Autres types numériques
Certains langages autorisent d’autres types numériques, notamment :
• le type monétaire (avec strictement deux chiffres après la virgule)
• le type date (jour/mois/année).
Nous n’emploierons pas ces types dans ce cours ; mais je les signale, car vous ne manquerez pas de les rencontrer en programmation proprement dite.

2.3 Type alphanumérique
Fort heureusement, les boîtes que sont les variables peuvent contenir bien d’autres informations que des nombres. Sans cela, on serait un peu embêté dès que l’on devrait stocker un nom de famille, par exemple.
On dispose donc également du type alphanumérique (également appelé type caractère, type chaîne ou en anglais, le type string – mais ne fantasmez pas trop vite, c’est loin d’être aussi excitant que le nom le suggère…).
Dans une variable de ce type, on stocke des caractères, qu’il s’agisse de lettres, de signes de ponctuation, d’espaces, ou même de chiffres. Le nombre maximal de caractères pouvant être stockés dans une seule variable string dépend du langage utilisé.
Un groupe de caractères (y compris un groupe de un, ou de zéro caractères), qu’il soit ou non stocké dans une variable, d’ailleurs, est donc souvent appelé chaîne de caractères.
En pseudo-code, une chaîne de caractères est toujours notée entre guillemets
Pourquoi diable ? Pour éviter deux sources principales de possibles confusions :
• la confusion entre des nombres et des suites de chiffres. Par exemple, 423 peut représenter le nombre 423 (quatre cent vingt-trois), ou la suite de caractères 4, 2, et 3. Et ce n’est pas du tout la même chose ! Avec le premier, on peut faire des calculs, avec le second, point du tout. Dès lors, les guillemets permettent d’éviter toute ambiguïté : s’il n’y en a pas, 423 est quatre cent vingt trois. S’il y en a, "423" représente la suite des chiffres 4, 2, 3.
• …Mais ce n'est pas le pire. L'autre confusion, bien plus grave - et bien plus fréquente – consiste à se mélanger les pinceaux entre le nom d'une variable et son contenu. Pour parler simplement, cela consiste à confondre l'étiquette d'une boîte et ce qu'il y a à l'intérieur… On reviendra sur ce point crucial dans quelques instants.

2.4 Type booléen
Le dernier type de variables est le type booléen : on y stocke uniquement les valeurs logiques VRAI et FAUX.
On peut représenter ces notions abstraites de VRAI et de FAUX par tout ce qu'on veut : de l'anglais (TRUE et FALSE) ou des nombres (0 et 1). Peu importe. Ce qui compte, c'est de comprendre que le type booléen est très économique en termes de place mémoire occupée, puisque pour stocker une telle information binaire, un seul bit suffit.
Le type booléen est très souvent négligé par les programmeurs, à tort.

Il est vrai qu'il n'est pas à proprement parler indispensable, et qu'on pourrait écrire à peu près n’importe quel programme en l'ignorant complètement. Pourtant, si le type booléen est mis à disposition des programmeurs dans tous les langages, ce n'est pas pour rien. Le recours aux variables booléennes s'avère très souvent un puissant instrument de lisibilité des algorithmes : il peut faciliter la vie de celui qui écrit l'algorithme, comme de celui qui le relit pour le corriger.

Alors, maintenant, c'est certain, en algorithmique, il y a une question de style : c'est exactement comme dans le langage courant, il y a plusieurs manières de s'exprimer pour dire sur le fond la même chose. Nous verrons plus loin différents exemples de variations stylistiques autour d'une même solution. En attendant, vous êtes prévenus : l'auteur de ce cours est un adepte fervent (mais pas irraisonné) de l'utilisation des variables booléennes.

; homme).