L’algorithmique est à la base de l’informatique, c’est l’art de découper un problème complexe en tâches élémentaires, c’est une suite d’instructions, qui une fois exécutée correctement, conduit à un résultat donné. Pour bien fonctionner, un algorithme doit donc contenir uniquement des instructions compréhensibles par celui qui devra l’exécuter. Quant à lui, un ordinateur n’est capable d’exécuter uniquement que quatre types d’instruction:
- la traitement de données
- la lecture et écriture de données depuis/sur des supports physiques
- le choix d’exécuter une instruction plutôt qu’une autre en fonction d’une condition booléenne
- la répétition
Un algorithme informatique est donc toujours combinaison de ces quatre commandes, quelque soit la complexité du problème à résoudre. Il exprime, dans un pseudo-langage, les instructions résolvant un problème donné indépendamment des particularités de tel ou tel langage informatique.
Langage algorithmique
D’un point de vue algorithmique on convient de distinguer les trois activités suivantes:
- Analyse: Écriture d’un Schéma d’algorithme
- Conception: Transcription du schéma de d’algorithme en Schéma de programme
- Construction: Traduction du schéma de programme dans un Langage de programmation
Ce processus de modélisation d’un problème par le biais de l’algorithme permet de faciliter la programmation en se rapprochant progressivement, en trois étapes, de la syntaxe d’un langage de programmation.
Algorithme & Programmation
Un algorithme s’exprime dans une sorte de pseudo-langage langage dont le forme et le choix de la syntaxe et des mots-clés, est en grande partie arbitraire, et peut donc varier. Le but est d’être compréhensible par tous et facilement traduisible dans un langage de programmation, puisque l’algorithme, dans le cadre de la programmation n’est qu’une étape avant le codage.
Un algorithme est la représentation abstraite d’un programme informatique écrit dans un langage descriptif qui a pour but de mettre en forme le processus par lequel un problème est formalisé.
Un algorithme est énoncé sous la forme d’un langage que l’on appelle Schéma d’algorithme et que l’on défini comme:
- Lisible, pour être compréhensible même par un non-informaticien
- Simple, pour pouvoir être traduit en n’importe quel langage de programmation
- Précis: pour ne pas porter à confusion
- Concis: un algorithme ne doit pas dépasser une page
- Structuré: pour identifier les différentes parties
Exemple d’algorithme : Calcul d’une moyenne de notes
Pour illustrer de façon concrète l’usage d’un algorithme pour résoudre un problème, prenons le cas d’une machine simple à calculer dont on veut expliquer le fonctionnement. Cette machine à calculer comprend une mémoire, un afficheur, un clavier numérique et les deux opérations: addition et division. Pour expliquer à Steve comment calculer la moyenne de ses notes de math de chaque trimestre, on pourrait écrire l’algorithme suivant.
1-Entrer la note de math du premier trimestre
2-Placer la note dans la mémoire avec la touche "addition"
3-Entrer la note de math du deuxième trimestre
4-Placer la note dans la mémoire avec la touche "addition"
5-Entrer la note de math du troisième trimestre
6-Placer la note dans la mémoire avec la touche "addition"
7-Activer la touche "division" et Entrer le nombre 3
8-Afficher le résultat
Cette exemple nous permet d’appréhender quelques notions de bases, parmi lesquelles:
- La suite d’instructions ou d’ordres permettant d’exécuter des actions
- L’enchainement des commandes réalisées en séquence
- le nom donné à la valeur d’une note « la note de math du premier trimestre » représente la valeur de la donnée « note »
- le calcul de la note est réalisé par les fonctions addition et division
- La lecture des notes, et l’affichage du résultat sont ce que l’on appelle généralement des entrées et sorties
Nous allons améliorer notre algorithme en introduisant la notion de itération . L’algorithme précédent est modifié sans changer son comportement. Steve rentre successivement les 3 notes de maths du trimestre.
1-Faire 3 fois les 2 instructions Suivantes
2-Entrer "la note de math"
3-Placer "la note de math" dans la mémoire avec la touche "addition"
4-Activer la touche "division"
5-Entrer le nombre 3
6-Afficher le résultat
Cet nouvel algorithme introduit deux notions importantes, parmi lesquelles:
- La répétition d’une suite d’instructions, ou faire quelque chose un certain nombre de fois
- Le traitement d’une donnée (calcul de la moyenne)
Nous allons encore améliorer notre algorithme en introduisant la notion de choix. On suppose que si la moyenne est inférieure à 12, il faut signaler à Steve qu’il doit fournir plus d’efforts dans son travail pour l’année prochaine. Ce nouvel algorithme est légèrement modifié par l’ajout d’une instruction de type Choix qui permet d’exécuter une instruction en fonction d’une condition, ici le résultat de la moyenne.
1-Faire 3 fois les 2 instructions Suivantes
2-Entrer "la note de math"
3-Placer "la note de math" dans la mémoire
4-Activer la touche "division" Entrer le nombre 3
5-Afficher le résultat
6-Si le résultat est inférieur à 12
alors
7- Afficher le message "Doit mieux faire"
sinon
8-Afficher "Excellent travail"
Elément du langage algorithmique
Pour exprimer de façon plus formelle les algorithme sous forme de schéma d’algorithmes on introduit les notions de
- Schéma élémentaire
- Primitive
- Variables
Schémas élémentaires
Le schéma TantQue est composé des mots-clefs TantQue, Faire et Fin-Faire. Cette instruction composées permet de répéter une séquence d’instructions délimitées par les mots-clefs Faire et Fin-Faire. Une expression booléenne, la Condition qui délivre une valeur VRAI ou FAUX permet l’arrêt de la boucle de répétition.
TantQue Condition
Faire
Séquence d'instructions
Fin-Faire
Le schéma Si est composé des mots-clefs Alors et Fin-Si. Cette instruction composées permet de faire exécuter une séquence d’instruction délimitée par les mots-clefs Alors et Fin-Si. Une expression booléenne, la Condition qui délivre une valeur VRAI ou FAUX permet d’exécuter la séquence d’instruction si la condition retourne VRAI.
Si Condition
Alors
Séquence d'instruction
Fin-Si
Le schéma Si Alors Sinon est composé des mots-clefs Si, Alors, Sinon et Fin-Si. Cette instruction composée permet de faire exécuter une séquence d’instruction délimitée par les mots-clefs Sinon et Fin-Si, dans la cas ou la Condition délivre une valeur FAUX.
Si Condition
Alors
Séquence d'instruction
Sinon
Séquence d'instruction
Fin-Si
Primitive
Pour gérer les entées-Sorties de valeur on définit deux mot réservés de langage algorithmique Afficher et Prendre. Ils sont considérés comme des Primitives dés lors que l’on ne s’intéresse pas à leur implémentation mais seulement à leur fonctionnalité.
Valeur
On attribue un nom à chaque valeur des données traitées dans le schéma d’algorithme. Le type des données n’est jamais spécifié puisqu’il n’apporte généralement aucune valeur ajoutée.
Algorithme de calcul de moyenne
Nous allons faire une première tentative d’écriture du schéma d’algorithme pour calculer la moyenne des trois trimestres à l’aide des schémas élémentaires et primitives présentés ci-dessus.
Assigner(0 à Somme)
Assigner(0,Compteur)
TantQue (Compteur est inférieur à 3)
Faire
Prendre("la note de math",Val)
Ajouter(Val à Somme)
Ajouter(1 à Compteur)
Fin-Faire
Diviser (Somme par 3)
Afficher(Somme)
Si (Somme est inférieur à 12)
alors
Afficher("Doit mieux faire")
Sinon
Afficher("Excellent travail")
Fin-Si
Pour les besoins de l’algorithme on a défini trois nouvelles primitives:
- Prendre: Permet d’entrer les données utiles à l’exécution de l’algorithme
- Assigner: Affecter une valeur à une donnée
- Ajouter: Ajoute une valeur à une autre
- Diviser: Divise une valeur par une autre
A ce stade de la lecture les notions de schémas étant posées, nous allons réécrire le schéma ci- dessus afin d’établir la syntaxe définitive de notre langage. L’objectif de cette nouvelle version est de simplifier la syntaxe du langage pour le rendre plus précis et moins verbeux.
Assigner (0,Compteur)
Assigner (0,Somme)
TantQue Inferieur(Compteur,3)
Faire
Prendre ("la note de math",Val)
Ajouter (Val,Somme)
Ajouter (1,Compteur)
Fin-Faire
Diviser (Somme,3)
Afficher (Somme)
Si Inferieur (Somme,12)
alors
Afficher ("Doit mieux faire")
Sinon
Afficher ("Excellent travail")
Fin-Si
On note dans cette version, un nouveau type de primitive que l’on nomme Prédicat. Le prédicat Inferieur() est une primitive qui retourne une valeur booléenne (Vrai, Faux) après évaluation des deux paramètres entre parenthèse. L’introduction de primitives telles que Assigner, Diviser, Afficher, Ajouter etc…, permet d’éviter l’emploi de signes mathématiques qui peuvent rendre la compréhension difficile pour un non informaticien ou non mathématicien.
En Résumé
Ce qu’il faut retenir:
- Un algorithme manipule des données en entrée ou en sortie
- Un algorithme exécute une suite d’instructions en séquence
- Un nom symbolique représente la valeur d’une donnée
- Pour contrôler l’enchainement des instructions on dispose de la séquence, l’itération et du choix
- Les phases de réalisation d’un logiciel (schéma d’algorithme, schéma de programme, langage de programmation)
- Les trois schémas élémentaires Tant-Que, Si Alors, Si Alors Sinon
- Les primitives qui sont des fonctions abstraites indispensables pour la réalisation d’algorithmes