Les bases de l'algorithmique

L'algorithmique

L'algorithmique est la science  des algorithmes. Elle permet de résoudre différents problèmes en décrivant les étapes de résolution.

Algorithme

Un algorithme est  le découpage d'une tâche en une suite ordonnée d'instructions élémentaires.

Exemple d'algorithme

Une recette de cuisine peut être considérée comme un algorithme. La formulation est bien sûr assez libre mais elle décompose la tâche en plusieurs étapes. Chaque étape est une instruction donnée au cuisinier.   Un programme informatique est un algorithme écrit dans un langage compréhensible par l'homme et la machine.

Une instruction est un ordre simple. Pour la recette de cuisine la formulation est assez libre, mais techniquement, elle se formule par un verbe à l'infinitif suivi, éventuellement, de compléments et de paramètres. Par exemple : TOURNER A DROITE DE 90° STOPPER

Instruction

Langage

La notion de langage est très vaste : http://www.larousse.fr/dictionnaires/francais/langage/46165 Ici il n'est question que des langages informatiques qui sont très nombreux. Il existe plusieurs types de langage permettant de faire un algorithme, certains sont textuels d'autres graphiques. Une liste des langages informatiques est disponible sur Wikipedia. Le format que nous avons vu précédemment se nomme PSEUDO-CODE, car il ne s'agit pas d'un langage informatique précis, les règles sont relativement libres. Nous pourrions dire que c'est du "code-like". Il convient toutefois de respecter certaines règles d'écriture pour que l'algorithme soit compréhensible par le plus grand nombre de personnes. A noter que La plupart des langages informatiques sont en anglais

Les bases algorithmique : le pseudo-code

Un algorithme peut se créer grâce à  des langages textuels ou graphiques. Certains langages sont plus proches de la machine, d'autres de l'homme, mais en fin de compte il faudra produire des instructions que comprend l'ordinateur. Il faut donc traduire ce qu'écrit l'homme en instructions compréhensibles par l'ordinateur, des applications font cette traduction : les compilateurs et les interpréteurs. Ces applications ne peuvent fonctionner que si tout est écrit selon des règles strictes. Le pseudo-code peut être assimilé à ces langages, même s'il n'y a pas vraiment de compilateurs ou d'interpréteurs (il existe Algobox qui a été développé dans un but pédagogique). Nous allons voir les bases de l'algorithmique en pseudo-code. Il vous sera facile ensuite de transposer vers d'autres langages, notamment les langages graphiques sous forme d'organigramme ou par blocs

Syntaxe

La syntaxe est une partie de la grammaire. Retenons que pour un langage informatique c'est la façon d'écrire une instruction. Par exemple en langage C (comme dans beaucoup d'autres langages), la plupart des instructions doivent se terminer par un point-virgule (;). Les programmeurs qui utilisent ce langage sont habitués. Mais il suffit d'oublier un seul point virgule pour que le programme ne fonctionne pas. Ne fonctionne pas ne veut pas dire qu'il donne des résultats faux mais qu'il est impossible de le traduire en langage machine, donc de l'exécuter.

Syntaxe d'une instruction

Le format d'une instruction est :  Verbe à l'infinitif + [complément(s)] + [paramètre(s)] Les crochets [ ] indiquent que certains éléments sont facultatifs. Attention ! Ceci ne veut pas dire que l'on peut toujours s'en affranchir mais que pour certaines instructions ils ne sont pas nécessaires. Exemples : TOURNER : il est obligatoire de dire dans quel sens, STOPPER : peut s'utiliser seul.

Exemple en Pseudo-code : tracer un carré

Sujet : faire l'algorithme qui permet de tracer un carré de 4 unités de côté.   Il faut considérer que nous nous adressons à une machine. Cette dernière ne sait pas extrapoler. Il faut donc tout lui indiquer. Nous allons considérer qu'elle comprend certaines choses, les ordres de base, donc les instructions élémentaires que nous lui donnons.

Dans cet algorithme nous considérons que la machine que nous programmons comprend les ordres PRENDRE, POSER, TOURNER, DEPLACER,  POSITIONNER, LEVER. Nous considérons aussi qu'elle comprend ce que veut dire REGLE, CRAYON, FEUILLE QUADRILLEE, LIGNE et aussi qu'elle sait prendre compte certains paramètres chiffrés. Mais l'algorithme ainsi écrit fait apparaître des séquences de lignes identiques. Nous allons considérer que la machine comprends une autre instruction REPETER x FOIS.  

Pseudo Code Carré (binary/octet-stream)

Tracé d'un carré : version 1

Pseudo Code Carré Repeter (binary/octet-stream)

Tracé d'un carré : V2

Bien que nous tracions 4 côtés identiques les opérations pour tracé le premier côté sont différentes, il faut donc les effecteur à part. Il y a ici deux exemples d'indentation (retrait des lignes) qui permettent de bien comprendre le code. La diapositive suivante vous présente le code non indenté.      

Pseudo Code Carré Repeter Nonindente (binary/octet-stream)

Tracé d'un carré v2 indentation

Pseudo Code Carré Repeter (binary/octet-stream)

Pie de foto: : L'algorithme non indenté : il est très difficile de le comprendre au premier coup d’œil !

Pie de foto: : L'algorithme indenté permet de voir sa structure et de le comprendre plus rapidement.

Tracé d'un carré

Même en réduisant le code grâce à l'instruction REPETER, nous voyons qu'il y a 2 endroits où nous indiquons la longueur d'un côté. Nous ne sommes pas à l'abri d'une erreur lors de l'écriture de l'instruction. Si nous nous trompons et mettons un mauvais chiffre dans une des instructions de déplacement il y aura alors un tracé incorrect. Sur cet algorithme simple ceci est à 2 endroits mais parfois ce peut être à plusieurs endroits. Imaginons aussi que nous souhaitions changer la longueur du côté de notre carré il faut penser à la changer à tous les endroits où cette valeur est utilisée, ce qui est fastidieux sur un long algorithme. Le mieux est donc d'indiquer cette valeur en début d'algorithme.. Pour cela il faut créer une variable.

Variable

Une variable est une case qui contient une valeur. A un instant T elle ne peut contenir qu'une seule valeur. Cette valeur peut être du texte, des nombres, ... Quand on met une nouvelle valeur elle remplace la valeur qui est présente et l'efface. Il n'y a pas d'historique. Mettre une valeur dans une variable se nomme l'affectation. On affecte une valeur à une variable. L'opérateur d'affectation est une flèche vers la gauche Pour utiliser une variable il faut la déclarer (cela crée la case). La variable porte un nom. Quand ce nom est utilisé dans l'algorithme c'est la valeur que contient la variable qui est prise en compte.

Pseudo Code Carré Variable01 (binary/octet-stream)

Pie de foto: : la syntaxe que nous employons maintenant est d'écrire les noms des variables en minuscule afin de ne pas les confondre avec les instructions et leurs paramètres.

Pseudo Code Carré Repeter (binary/octet-stream)

Pseudo Code Carré Variable01 (binary/octet-stream)

Variable

Pie de foto: : Ici si nous souhaitons modifier la longueur du côté il faut modifier les 2 lignes DEPLACER. Imaginez un code de 1000 lignes avec un grand nombre de lignes utilisant la même valeur.

Pie de foto: : Ici le seul fait de changer la valeur dans la deuxième ligne (longueur ← 4) permet que cette valeur soit prise en compte à chaque fois que l'on fait référence à la variable. Par exemple si on veut un carré de 5 de côté on remplace par longueur ← 5)

Les variables : connaître le contenu

Nous allons faire ce que l'on appelle faire tourner un algorithme à la main. Nous allons construire un tableau et noter la valeur de la variable au début et à la fin  chaque ligne. Pour cela nous allons numéroter nos lignes. Nous allons faire changer la valeur de la variable. dans l'algorithme. Pour voir ce que cela donne nous allons "tracer" l'algorithme

Le point sur la syntaxe

Il est question ici de la syntaxe que nous employons dans ce cours, il n'y a pas de syntaxe officielle pour le pseudo-code. Toutefois quand on écrit un algorithme il faut respecter une syntaxe dans tout cet algorithme et ceux associés. Les instructions et leurs paramètres sont écrits en lettres capitales, Il n'y a qu'une instruction par ligne le code doit être indenté   Une variable doit être déclarée grâce à l'instruction VARIABLE Le nom des variables est écrit en minuscule   Il est possible de commenter les lignes de code : on ajoute le signe ' devant le commentaire (ce qui suit n'est donc pas lu pour l'exécution)

Interactions avec l'utilisateur

Pour l'instant nous avons créé un algorithme qui trace un carré avec une longueur de côté indiquée directement dans l'algorithme. On dit que la valeur est mise en dur dans l'algorithme. Si l'on veut changer cette longueur nous devons modifier l'algorithme. Ce qui ne sera pas très pratique si l'utilisateur de la machine ne sait pas modifier l'algorithme. Il faut donc que l'utilisateur et la machine puissent discuter. Pour cela nous ajoutons 2 instructions : AFFICHER pour que la machine envoie un message à l'utilisateur (via l'écran) SAISIR pour que l'utilisateur envoie son message à la machine (via le clavier)

La syntaxe de l'instruction AFFICHER est simple. Il faut mettre à la suite le message à afficher. Ce message peut être littéral ou être une variable ou une combinaison des 2. Quand on affiche une variable c'est son contenu qui est affiché. Quand un message comprends plusieurs éléments, on les sépare par une virgule.   Quand on met un texte il faut l'entourer de guillemets afin qu'il ne soit pas confondu avec une instruction ou une variable : voir la différence entre la seconde instruction et la troisième instruction ci-contre

Syntaxe Afficher (binary/octet-stream)

Syntaxe AFFICHER

Interaction

Syntaxe Saisir (binary/octet-stream)

La syntaxe de l'instruction SAISIR est très simple. Le paramètre est le nom de la variable dans laquelle sera affecté ce qui est saisi. L'affectation de la saisie à la variable se fait quand l'utilisateur appuie sur la touche entrée.   Vous pouvez maintenant écrire l'algorithme qui permet de demander à l'utilisateur la longueur du côté. La solution se trouve page suivante.

Tracé avec interaction

Carré Interaction (binary/octet-stream)

Pie de foto: : On suppose ici que l'utilisateur ne fait pas d'erreur de saisie.

Structure de contrôle : SI.

Nous allons maintenant considérer que nous pouvons tracer un carré seulement si la valeur saisie est supérieure à 3. Il faut donc tester le contenu de la variable longueur. L'instruction vérifie une condition et exécute les instructions si elle est vérifiée.   La solution se trouve page suivante.

Syntaxe Si (binary/octet-stream)

Pie de foto: : Syntaxe de l'instruction SI. Attention à bien respecter l'indentation.

Pseudo Code Si (binary/octet-stream)

Tracé du carré avec un côté > 3

Pie de foto: :

Les instructions du tracé ne seront effectuées que si la valeur de la variable longueur est supérieure à 3.   Maintenant nous allons rajouter une condition, il faut que la longueur soit supérieure à 3 mais inférieure à 9.   Astuce : il faut imbriquer les instructions SI

Carré avec côté ]3.9[

L'algorithme teste en premier si le nombre saisi pour la longueur est plus grand que 3. Si cette condition est avérée, et seulement dans ce cas, alors il teste si la longueur est inférieure à 9 et si cette seconde condition est avérée alors il trace le carré.   Nous voulons maintenant afficher un message quand le tracé ne peut être effectuer. Il faut dans ce cas utiliser une autre syntaxe de l'instruction SI, baptisée SI... ALORS...SINON....FINSI.   La solution est sur la diapositive suivante.

Pseudo Code Si Imbriqué (binary/octet-stream)

Algorithme complet du tracé d'un carré

Pseudo Code Si Imbriqué Sinon (binary/octet-stream)

Pie de foto: :

Cet algorithme demandent à l'utilisateur de saisir la longueur du côté du carré. Si la longueur saisie est supérieure à 3 et si elle est inférieure à 9 alors il trace le carré. Si elle est inférieure ou égale à 3 il affiche le message "tracé impossible avec une longueur x qui est trop petite". Si elle est supérieure ou égale à 9 il affiche le message "tracé impossible avec une longueur x qui est trop grande". La façon de l'exprimer en langage courant est différente que celle utilisée dans l'algorithme

Plusieurs variables

Nous allons maintenant faire l'algorithme qui permet de tracer le rectangle après avoir demandé la longueur et la largeur à l'utilisateur.   Nous allons considérer que la machine possède 2 nouvelles instructions : LIGNE qui lui permet de tracer une ligne de manière autonome (donc nous n'avons plus besoin de lui indiquer de poser la règle, de poser et de le ver me crayon,...) Cette instruction prend pour paramètre la longueur de la ligne. Syntaxe : LIGNE [longueur de la ligne]   POSITIONNER qui permet de se positionner à un point précis grâce à ses coordonnées. Syntaxe : POSITIONNER [abscisse],[ordonnée]   La solution se trouve sur la diapositive suivante.

Algorithme de tracé d'un rectangle

Algo Rectangle (binary/octet-stream)

On commence par déclarer les variables pour réserver les cases mémoire. Ensuite on initialise les variables pour ne pas risquer d'avoir des informations résiduelles dans la mémoire On effectue le dialogue avec l'utilisateur   On se positionne sur le point d'origine coordonnées (0,0) On trace les lignes. On considère qu'en l'absence d'indication d'orientation le mouvement de tracé se fait vers la droite.

Pie de foto: : On considère que l'utilisateur ne fait pas d'erreur de saisie.

Calculs

Il est bien sûr possible de faire des calculs. Les opérateurs de calcul que nous avons à notre disposition sont l'opérateur d'addition : + l'opérateur de soustraction : - l'opérateur de multiplication : * l'opérateur de division : / Par exemple pour additionner le chiffre 3 et le chiffre 4 on note 3 + 4, attention si on veut multiplier on note 3 * 4 On peut le faire avec des variables, supposons  les variables prix et paiement, pour calculer le rendu de monnaie : paiement - prix. Mais où va le résultat ? Il faut le mettre dans une variable : monnaie <- paiement - prix. Faîtes l'algorithme qui trace le rectangle puis qui affiche le périmètre et l'aire du rectangle..

Algorithme avec calculs

Nous avons besoin de 4 variables que nous déclarons.   Nous initialisons les 4 variables. Nous effectuons le dialogue avec l'utilisateur et enregistrons la saisie. Nous traçons le rectangle. Nous effectuons les calculs. Nous affichons les résultats.

Algo Rectangle Aire Perimetre (binary/octet-stream)

Pie de foto: : Il est possible de mélanger des valeurs en dur et des variables dans les calculs. Les parenthèses sont utilisées avec les mêmes règles qu'en algèbre.

Contrôle de la saisie

On suppose que l'utilisateur ne peut saisir que des nombres. Nous ajoutons une condition : les rectangles que nous traçons ne doivent pas être des carrés. Nous avons vu l"instruction REPETER x fois.... FINREPETER. Nous allons nous servir d'une instruction qui au lieu de répéter un nombre de fois défini répète jusqu'à ce qu'une condition soit  remplie. Syntaxe REPETER jusqu'à [condition]             FINREPETER Nous avons vu les opérateurs de comparaison =, <, >. Mais quel est l'opérateur qui permet de constater une différence, le = barré n'existe pas sur le clavier. Les opérateur "plus petit ou égale", "plus grand ou égale" et "différent de" sont composés de 2 signes et sont respectivement <=, >= et <> (si un nombre plus grand ou plus petit il est différent) Faîtes l'algorithme en prenant en compte la condition ci-dessus

Algo Rectangle Contrôle Saisie (binary/octet-stream)

Contrôle de la saisie

Dans cet algorithme on répète la demande de saisie des valeurs de la longueur et de la hauteur jusqu'à ce qu'elle soient différentes. On indique à l'utilisateur que l'on ne veut pas qu'elles soient égales (ce manière détournée en lui disant que l'on ne veut pas saisir un carré) Pour terminer nous allons calculer la longueur des diagonales du du rectangle. L'opérateur qui permet d'élever un nombre à une puissance est ^ exemple : 3 au carré : 3 ^ 2 Pour obtenir la racine carrée d'un nombre on utilise la fonction RACINECARREE(nombre) Exemple : √ 9 : RACINECARREE(9) Astuce, il faut utiliser le théorème de Pythagore.

Algo Rectangle Diagonale (binary/octet-stream)

Pie de foto: : L'algorithme est complet. Une explication sur le calcul est donné sur la diapositive suivante.

Algorithme complet du rectangle

Explication du calcul

Algo Calcul Diagonale (binary/octet-stream)

Pie de foto: : .

Exemple avec largeur = 3 et hauteur=4 Dans la première ligne on fait le calcul de la somme des carrés de chaque côté. Nous affectons le résultat à la variable diagonale.  Donc après la première ligne diagonale vaut : 3^2 + 4^2 = 9 + 16 =25 Ensuite nous utilisons cette valeur pour calculer le résultat final puis nous affectons le résultat à la variable diagonale.          Rappel : quand on met une nouvelle valeur dans une variable cette nouvelle valeur remplace la valeur contenue dans la variable. Le calcul est donc √ 25 = 5  Quand le calcul est fait le résultat de ce calcul est donc mis dans la case nommée diagonale donc 5 remplace 25. Après la deuxième ligne  de ce calcul la case mémoire dont le nom est diagonale contient la dernière valeur qui la été affectée soit le nombre 5.  

Tracer un algorithme

Quand on veut savoir ce que produit un algorithme comme résultat il est intéressant de le "tracer". Le tracer va permettre aussi de le mettre au point donc de déceler et de corriger d'éventuels  dysfonctionnements (connu sous le nom de bug). Pour tracer l'algorithme il est faut que les lignes soient repérables nous allons donc les numérotées. Il existe pour les langages de programmation des outils que l'on nomme "débogueurs" mais là on le fait soit même on dit souvent que l'on fait tourner l'algorithme à la main. Nous allons prendre l'algorithme du rectangle et regarder le contenu des variables après l'exécution de chaque ligne.

Algo Numerote (binary/octet-stream)

Pie de foto: : L'algorithme du simple tracé d'un rectangle comprend 40 lignes.

Tracer un algorithme.

Tableau Trace Variable (binary/octet-stream)

Dans le tableau ci-contre nous avons tracé uniquement le contenu des variables. Quand la case est barrée d'une croix ceci veut dire que la variable n'existe pas. Quand il est marqué "vide" ceci veut dire que la variable n'a pas de contenu, donc qu'aucune valeur ne lui a été affectée. Le lignes de commentaires ne sont pas exécuter, donc il est inutile de les tracer, pour la machine ces lignes n'existent pas. Les répétitions, n'ont pas été marquées pour simplifier et rendre le tableau lisible mais les lignes 27, 28 et 9 devraient se trouver en double. Pour tracer il a fallu considérer un cas pour donner des valeurs correspondantes à la saisie. Ici on considère que l'utilisateur saisi 3 pour la longueur et 4 pour la hauteur. Pour être sur de l'algorithme il aurait fallu prendre plusieurs cas de figure. On considère que l'algorithme détruit les variables à la fin.    

Pie de foto: : Le tableau avec le contenu des variables

Algo Numerote (binary/octet-stream)

Tableau Trace Variable (binary/octet-stream)

Trace de l'algorithme du rectangle

Trace d'un algorithme

Tracer un algorithme permet de vérifier son comportement et donc les résultats. Il faut numéroter les lignes afin d'avoir des repères Il faut choisir un cas de figure puis faire la trace de l'algorithme, ce qui signifie qu'il faut faire un scénario des saisies. Il faut normalement regarder l'action de chaque ligne, Donc il se peut que l'on retrouve plusieurs fois le même numéro de ligne dans le tableau. Un exemple est donné sur la diapositive suivante. Quand il y a des répétitions liées au scénario choisi il faut aussi trace ces répétition.s

Tableau Extrait Repetition (binary/octet-stream)

Dans cet extrait du tableau correctement écrit nous voyons que les lignes 27, 28 et 29 sont répétées 2 fois. Essayer de faire la trace de l'algorithme pour le scénario suivant : L'utilisateur saisi 3 pour la longueur puis 3 pour la hauteur, ensuite il saisi 20 pour la longueur et 15 pour la hauteur.

Trace d'un algorithme

Trace d'un algorithme

Tableau Scenario2 01 (binary/octet-stream)

Tableau Scenario2 02 (binary/octet-stream)

Pie de foto: : Nous voyons que les lignes 16 à 21 sont répétées car la condition longueur <> hauteur n'est pas respectée au premier passage.

Pie de foto: : Les lignes 27, 28, 29 sont répétées 2 fois.

Les structures algorithmiques

A travers le pseudo-code nous avons vu les structures algorithmique.s. Quand on traduit l'algorithme dans un langage on parle de programmation structurée. Il y a plusieurs structures ; elles sont décrites dans les diapositives suivantes. Pour un algorithme les structures sont souvent imbriquées les unes dans les autres. Pour repérer les structures et leurs imbrications on utilise l'indentation.

Structure conditionnelle

Algo Structure Conditionnelle (binary/octet-stream)

Pie de foto: : .

Cette structure est utilisée quand on doit effectuer certaines instructions sous condition. Si la condition est avérée alors on exécute les instructions. Si la condition n'est pas avérée on saute les instructions pour passer à la suite de l'algorithme., donc on passe directement après le FINSI

Structure alternative

Algo Structure Alternative (binary/octet-stream)

Pie de foto: : La structure alternative prévoit ce qu'il faut faire si la condition n'est pas avérée.

Elle ressemble à la structure conditionnelle, mais propose une alternative dans le cas ou la condition n'est pas avérée.. Si la condition est avérée on exécute le premier groupe d'instructions, si elle est infirmée on exécute le tive  d'instructions.

Structures répétitives

Algo Structures Répétitives (binary/octet-stream)

La première de ces structures va répéter les instruction jusqu'à ce qu'une condition soit remplie. Attention si la condition est remplie dès le début les lignes ne seront jamais exécutées. La seconde structure répète x fois les lignes   La dernière structutre répète les lignes indéfiniment. Elle est surtout utilisée pour les automatismes.   On appelle aussi ces structures des boucles

Pie de foto: : Les structures répétitives sont aussi nommées des boucles.

Synthèse

Les algorithmes permettent de programmer des machines. On parle de langage de programmation et de programmation structurée. : structure conditionnelle, structure alternative, structure répétitive. Les langages on des règles stricte notamment sur la syntaxe.   Les informations peuvent être contenu dans des cases mémoire appelées variables. Chaque variable est repérée par un nom. Une variable ne peut contenir qu'une seule valeur à un instant T Quand on met une valeur dans une variable on dit que l'on affecte la valeur à la variable. L'opérateur d'affectation est ←.

Les opérateurs de comparaison sont <, >, =, <=, >=, <> soit respectivement : inférieur à, supérieur à, égale à, inférieur ou égale à, supérieur ou égale à, différent de. Les opérateurs de calcul sont +, -, *, / respectivement addition, soustraction, multiplication et division. L'opérateur de puissance est ^ L'indentation permet de faciliter la lecture d'un algorithme et de bien distinguer les structure   Pour déboguer un algorithme on le fait tourner à la main et on trace le contenu des variables.