Page MenuHomePhabricator

Introduction à l'algorithmique
Updated 55 Days AgoPublic

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 également ê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 complexe.

Les conteneurs

Ces 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.

Le codage des caractères est indépendant de leurs valeurs décimales. Ainsi, le caractère '0' correspond à la valeur décimale 48 en ASCII. Il n'est donc pas possible de comparer un caractère chiffré d'une variable entière '0' ≠ 0.

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 beaucoup 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
Last Author
Steve
Last Edited
Aug 25 2020, 11:23 AM

Document Hierarchy

Event Timeline

Steve edited the content of this document. (Show Details)Aug 10 2020, 12:39 AM
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)Aug 10 2020, 7:15 AM
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)Aug 10 2020, 7:25 AM
Steve edited the content of this document. (Show Details)Aug 10 2020, 7:27 AM
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)Aug 10 2020, 7:30 AM
Steve edited the content of this document. (Show Details)Aug 10 2020, 7:34 AM
Steve edited the content of this document. (Show Details)Aug 10 2020, 8:12 AM
Steve edited the content of this document. (Show Details)Aug 10 2020, 3:19 PM
Steve edited the content of this document. (Show Details)Aug 10 2020, 4:07 PM
Steve edited the content of this document. (Show Details)Aug 10 2020, 4:27 PM
Steve edited the content of this document. (Show Details)Aug 10 2020, 4:32 PM
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)Aug 10 2020, 4:43 PM
Steve edited the content of this document. (Show Details)Aug 10 2020, 4:46 PM
Steve edited the content of this document. (Show Details)Aug 10 2020, 4:49 PM
Steve edited the content of this document. (Show Details)Aug 10 2020, 4:56 PM
Steve edited the content of this document. (Show Details)Aug 10 2020, 6:51 PM
Steve edited the content of this document. (Show Details)Aug 10 2020, 6:53 PM
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)Aug 10 2020, 6:58 PM
Steve edited the content of this document. (Show Details)Aug 10 2020, 10:35 PM
Steve edited the content of this document. (Show Details)Aug 11 2020, 3:26 PM
Steve edited the content of this document. (Show Details)Aug 11 2020, 3:39 PM
Steve edited the content of this document. (Show Details)Aug 11 2020, 3:45 PM
Steve edited the content of this document. (Show Details)Aug 11 2020, 3:47 PM
Steve edited the content of this document. (Show Details)Aug 11 2020, 3:56 PM
Steve edited the content of this document. (Show Details)Aug 11 2020, 3:58 PM
Steve edited the content of this document. (Show Details)Aug 11 2020, 4:11 PM
Steve edited the content of this document. (Show Details)Aug 11 2020, 4:29 PM
Steve edited the content of this document. (Show Details)Aug 11 2020, 4:36 PM
Steve edited the content of this document. (Show Details)Aug 11 2020, 6:33 PM
Steve edited the content of this document. (Show Details)Aug 16 2020, 10:05 AM
Steve edited the content of this document. (Show Details)Aug 16 2020, 11:12 AM
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)Aug 16 2020, 11:16 AM
Steve edited the content of this document. (Show Details)Aug 16 2020, 2:58 PM
Steve edited the content of this document. (Show Details)Aug 16 2020, 3:31 PM
Steve edited the content of this document. (Show Details)Aug 18 2020, 1:52 PM
Steve edited the content of this document. (Show Details)Aug 18 2020, 2:40 PM
Steve edited the content of this document. (Show Details)Aug 18 2020, 2:48 PM
Steve edited the content of this document. (Show Details)Aug 18 2020, 2:52 PM
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)Aug 18 2020, 3:09 PM
Steve edited the content of this document. (Show Details)Aug 21 2020, 12:29 PM
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)Aug 21 2020, 12:32 PM
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)Aug 23 2020, 10:06 AM
Steve edited the content of this document. (Show Details)Aug 23 2020, 10:13 AM
Steve edited the content of this document. (Show Details)Aug 23 2020, 10:15 AM
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)Aug 23 2020, 2:38 PM
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)Aug 23 2020, 2:40 PM
Steve edited the content of this document. (Show Details)Aug 23 2020, 2:45 PM
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)Aug 23 2020, 2:48 PM
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)Aug 23 2020, 2:50 PM
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)Aug 23 2020, 3:00 PM
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)Aug 23 2020, 3:03 PM
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)Aug 23 2020, 3:07 PM
Steve edited the content of this document. (Show Details)Aug 23 2020, 3:09 PM
Steve edited the content of this document. (Show Details)
Steve edited the content of this document. (Show Details)Aug 24 2020, 10:23 AM
Steve edited the content of this document. (Show Details)Aug 25 2020, 11:23 AM