Introduction à l’algorithmique
Définition
Un algorithme, c’est tout simplement une façon de décrire dans ses moindres détails comment procéder pour faire quelque chose. Un algorithme, c’est une suite d’instructions qui, une fois exécutée correctement, conduit à un résultat donné. Pour fonctionner, un algorithme doit donc contenir uniquement des instructions compréhensibles par celui qui devra l’exécuter.
Les algorithmes reçoivent des paramètres en entrée. Ce sont des quantités qui lui sont données avant qu’un algorithme ne commence. Un algorithme doit toujours se terminer après un nombre fini d’étapes. Chaque étape d’un algorithme doit être définie précisément, les actions à transposer doivent être spécifiées rigoureusement et sans ambiguïté pour chaque cas. Toutes les opérations que l’algorithme doit accomplir doivent être suffisamment basiques pour pouvoir être en principe réalisées dans une durée finie par un homme utilisant un papier et un crayon. L’utilisateur profite du résultat de l’algorithme, en sortie, une fois qu’il est terminé.
L’algorithmique intervient dans la vie de tous les jours. Une recette de cuisine peut être considérée comme un algorithme, puisqu’elle contient :
- Des entrées : Les ingrédients, le matériel utilisé, …
- Des instructions : Découper, cuire, préparer, … dont les exécutions dans un ordre précis amènent au résultat voulu.
- Un résultat : le plat préparé.
Les instructions élémentaires
L’instruction de lecture permet à l’utilisateur de rentrer des valeurs au clavier pour qu’elles soient utilisées par le programme. Dans l’autre sens, l’instruction d’écriture, permet au programme de communiquer des valeurs à l’utilisateur en les affichant à l’écran. Dans ce cours, elles sont respectivement appelées LIRE et ÉCRIRE.
Dans un programme informatique, on va avoir en permanence besoin de stocker provisoirement des valeurs. Pour ce faire, il faut déclarer une variable, c’est-à-dire demander à l’ordinateur de nous réserver de la mémoire à notre programme. Une variable est une boîte, que le programme 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. Dans ce cours, elles sont déclarées avec l’instruction VARIABLE. Il est également possible de concevoir une variable qui ne pourra jamais changer de valeur. Dans ce genre de cas de figure, il faut privilégier l’instruction CONSTANTE.
La principale utilité d’une variable, c’est de lui affecter une valeur. C’est-à-dire remplir le contenu de la boite. Dans ce cours, nous utiliserons le signe <- pour effectuer cette opération. Les variables peuvent par ailleurs être utilisées avec les instructions LIRE ou ÉCRIRE. Plus tard, elles seront également utilisées avec des structures logiques afin de concevoir des algorithmes de plus en plus complexes.
Les conteneurs
Les variables doivent être déclarées comme respectant un type particulier (des nombres entiers, des nombres réels, des booléens, des chaines de caractère, …). Une fois que le type est déclaré, celui-ci ne peut plus être changé.
En informatique, un entier est un type de donnée qui représente un sous-ensemble fini de nombres entiers relatifs. On utilise aussi le terme INT. La représentation des nombres passe par une représentation binaire (à l’aide des chiffres 0 et 1). Les ordinateurs utilisent la position de chaque bit pour y faire correspond à une puissance de 2. Le bit le plus à droite correspond à 20, celui à sa gauche 2¹, suivit de 2², etc. Le tout dernier chiffre de gauche correspond au signe. Le nombre 0 correspond à un nombre positif, alors que le nombre 1 correspond à un nombre négatif. Ainsi, la valeur 0101 en binaire correspond à 0 + 2² + 0 + 2⁰, donc à la valeur 5 en décimale.
La mémoire des ordinateurs sont limités, c’est pourquoi il existe de nombreuses alternatives au type ENTIER pour minimiser l’empreinte mémoire des programmes informatique. Les ordinateurs modernes possèdent tellement d’espace mémoire que les développeurs utilisent généralement ce type, sans donner plus de précision. Toutefois, il existe des cas particuliers (ex: les communications sur le réseau) où l’on souhaite toujours tout réduire l’espace mémoire.
Avec le système binaire, les nombres réels ne peuvent pas tous être représentés. Les ordinateurs utilisent un système de virgule flottante, ce qui rend la précision variable selon la grandeur du nombre. Comme pour les entiers, il est possible de préciser la quantité de mémoire que doit utiliser un RÉEL. Il faut savoir également que l’arithmétique des nombres à virgule est également une tâche beaucoup plus difficile pour un ordinateur. C’est d’ailleurs pour cella que les jeux-vidéos et certaines intelligences artificielles tournent sur du matériel conçu exclusivement prévu pour ce genre de calcul.
Enfin le dernier conteneur standard concerne le texte. Un CARACTÈRE informatique peut représenter une lettre minuscule, une lettre majuscule, un chiffre, un signe de ponctuation ; mais aussi une espace, un émoji, un retour à la ligne plein d’autres caractères spéciaux. Comme les ordinateurs fonctionnent en binaire, un numéro est attribué à chaque caractère. Il existe plusieurs normes de codage de caractères dont, parmi les plus connues, ASCII et UNICODE. Un CARACTÈRE ne peut contenir qu’un seul caractère et doit être délimité par l’apostrophe : ‘C’. Une CHAÎNE de caractères est tout simplement un ensemble de caractère, comme une phrase, et doit être délimité par des guillemets : “Je suis une chaîne !”. Dans la mémoire de l’ordinateur, une chaine de caractère se termine toujours par le caractère spécial appelé NUL. Par conséquent, la chaîne “hello” est un ensemble de 6 caractères.
Les opérations élémentaires
Dans tous les langages de programmation, il est possible d’utiliser les opérateurs mathématiques pour évaluer une expression. Les quatre opérations élémentaires sont naturellement supportés sur toutes les machines. Les symboles utilisés sont naturellement le + pour l’addition, le – pour la soustraction, le * pour la multiplication et le / pour la division.
Il faut faire particulièrement attention au type des variables lorsqu’on souhaite diviser un nombre. En effet l’ordinateur distingue la division entière de la division par des réels. Ainsi la division entière de 5/2 vaudra 2 (avec 1 comme reste), alors que la division en nombre flottant 5/2.0 aura un résultat le nombre flottant 2.5. Le résultat de la division sera toujours un nombre flottant si le numérateur ou le dénominateur le sont aussi. Par ailleurs, il existe une autre opération élémentaire pour l’ordinateur, qui est l’opérateur modulo %. Ce dernier renvoi le reste de la division entière, c’est-à-dire 1 dans le cas de 5%2. Ce dernier est très souvent employé pour savoir si un nombre est paire ou impaire, mais nous verrons d’autre utilisation.
Attention, n’oubliez jamais que la précision des nombres flottant est limitée.
Concernant l’opération mathématique d’élever un nombre à une puissance, ce n’est malheureusement pas quelque chose de trivial pour un ordinateur. Il existe l’instruction PUISSANCE pour élever un nombre à une puissance donnée, mais certains langages possèdent une notation raccourcis. Pour ce cours, nous écrirons directement les exposants et les racines comme des instructions standards.
Enfin, il existe une dernière opération élémentaire pour un ordinateur : le décalage de bit. Étant donné que les machines travaillent en binaire, il est naturel qu’elles puissent effectuer des opérations particulières sur ces bits. L’opérateur << décalera les bits d’autant de cran que vous le voulez à gauche, alors que l’opérateur >> effectuera cette même action sur la droite. Par exemple, le chiffre 2 est représenté en binaire par 00 00 00 10. Si l’on effectue l’opération 2<<1, nous décalons tous les bits d’un cran à gauche: 00 00 01 00, ce qui correspond cette fois au chiffre 4. Cet opérateur est assez rare comparé aux autres, il s’applique généralement à des cas d’utilisation très particulier. Sachez toutefois que cette opération élémentaire existe.
La séquence d’instruction
Les bonnes pratiques veulent que les algorithmes soient séparés en trois parties distingue pour faciliter leur lecture. La première partie concerne déclaration des variables et leurs initialisations. La seconde partie est le cœur de l’algorithme puisqu’il s’agit du traitement des données. La dernière concerne l’envoi des données à l’utilisateur de l’algorithme. Gardez toujours à l’esprit que même si aujourd’hui votre algorithme vous semble claire, dans 6 mois ce ne sera plus forcément le cas. Pensez donc à être le plus clair possible, car la plupart des algorithmes présentés dans ce cours seront réutilisés.
Dans l’exemple ci-dessous, l’algorithme permet d’additionner deux variables. On distingue la phase d’initialisation où l’utilisateur est invité à entrer les valeurs. La phase de traitement où les nombres sont additionnés. La dernière partie affiche le résultat à l’utilisateur.
DÉBUT VARIABLE a, b, c: ENTIER LIRE "Veuillez compléter la valeur de A:", a LIRE "Veuillez compléter la valeur de B:", b c<-a+b ÉCRIRE "La somme de a+b: vaut: ", c FIN
2 Comments
Quand j’ exécute cet algorithme et je rends a=1 et b=1, à la place d’avoir 2, mon code en python additionne les deux variables donc j’ai a+b = 1+1 = 11. D’un coté c’est logique parce que additionne une variable à l’autre, mais si je veux avoir réponse =2, où est mon erreur?
Et en plus je pense que l’algorithme est ambiguë car il n’explique pas si on veut a+b= ab ou a+b=2.
Possible que je me trompe, mais je suis ici pour apprendre.
Hello,
En python, lorsqu’on crée une variable, il essaye de comprendre par lui-même le type. Dans ton cas de figure, il déduit que le type de variable est “texte”. Il effectue donc l’addition de “texte + texte”, et c’est pour cela qu’il t’affiche 11.
Tu peux guider Python à identifier le type pour que l’addition se fasse correctement. Dans l’exemple ci-dessous, nous forçons que l’entrée au clavier soit interprété comme des int, des nombres entiers.:
a = int(input())b = int(input())
print(a+b)
Bàt,
Steve.