Blog

Algorithmique

Un algorithme est une suite finie et non ambiguë d’opérations ou d’instructions permettant de résoudre une classe de problèmes.

Le mot algorithme vient du nom d’un mathématicien perse du ixe siècle, Al-Khwârizmî (en arabe : الخوارزمي). Une autre étymologie dit qu’un algorithme est un calcul (« arithmos » en grec), qui est tellement long et difficile à faire à la main qu’il en devient douloureux : « algos » signifie douleur en grec ; un algorithme est un calcul pénible à faire à la main. Étymologie elle aussi acceptable, puisqu’elle rend compte du g ; au XIIIe siècle, algorithme signifiait l’arithmétique avec les chiffres arabes.

Dans un Langage de Définition Algorithmique certains mots sont réservés pour un usage bien défini, on les nomme les mots clés. Ce sont les mots que le langage utilise pour son fonctionnement.

 Un mot clé ne peut pas être déclaré comme identificateur.  Ils ne peuvent être utilisés comme variables

 Quelques mots clés : dans notre langage de définition les mots clés commenceront toujours par une majuscule, seront soulignés.

Ceux qui nous permettent de définir la structure :

–       Algorithme : permet de définir ou de donner le nom à l’algorithme.

–       Début : marque le commencement de l’algorithme.

–       FinAlgo : marque la fin de l’algorithme

–       Variables : c’est une partie de l’algorithme qui Permet de déclarer des variables ; une variable est un objet dont le contenu peut changer au cours de l’exécution de l’algorithme.

–       Constantes : c’est une partie de l’algorithme  qui permet de  déclarer des constantes.  Une constante est un objet dont le contenu reste invariant lors de   l’exécution d’un algorithme.

–       Réel,  CaractèresEntiersChaine et Booléen  sont des mots clés qui permettent de définir des types (nous y reviendrons un peu plus loin dans cet ouvrage). 

–       SiFinsiTantqueFintantquePourFinpourRépéterJusqu ‘à… : mots clés permettant de définir les structures itératives, conditionnelles…

–       Les commentaires sont utilisés pour permettre une interprétation aisée de l’algorithme. Leur utilisation est vivement conseillée. De ce fait, tout texte placé entre les symboles  /*  */  sera considéré comme un commentaire.

—Identifiant : suite de caractères qui permet de nommer les choses

—Variable : une entité qui contient une information

Possède un identifiant

Possède une valeur (qui peut changer dans le temps)

Possède un type qui caractérise l’ensemble des valeurs

—Une constante : une valeur qui ne change jamais dans le temps.

—Un type : l’ensemble de valeur que peut prendre une variable.

Une variable peut contenir différents types de données et de tailles différentes.

Contrairement à la programmation, l’algorithmique ne gère pas le problème de l’allocation de mémoire ou la destruction des objets. Une variable sera par exemple de type Numérique pouvant représenter une fois transposée dans le langage de programmation souhaité aussi bien un entier, qu’un réel, un double …


Les types de contenu des variables les plus courants sont :

  • Booléen, représentant une valeur logique binaire oui ou nonouvert ou fermévrai ou faux
  • Numérique, représentant un nombre quelconque
  • Caractère, représentant un caractère seul
  • Chaîne de caractères, représentant un texte de zéro, un ou plusieurs caractères

De plus, le type de contenu peut être une structure d’objet personnalisée (par exemple un type Personne comprenant son nom, prénom…)


Par convention le contenu des variables de type :

  • Booléen sera Faux ou Vrai
  • Numérique utilisera le format d’écriture 12345.6789
  • Caractère sera noté avec une apostrophe simple (exemple 'c')
  • Chaîne de caractères (ou String) sera notée entre guillemets doubles (exemple "contenu de la chaine")


Ci-dessous un petit récapitulatif des types de variables :

TypeUtilitéExemple
BooléenReprésente un état binaire, vrai ou fauxVrai
NumériqueReprésente un nombre quelconque12345.6789
CaractèreReprésente un caractère unique (comme une touche du clavier)'c'
Chaîne de caractèresReprésente un texte"contenu de la chaîne"

l’instruction d’affectation se note avec le signe ←

a ← 24, veut dire attribue la valeur 24 à la variable a.

Elle permet d’effectuer tel ou tel traitement en fonction de la valeur d’une condition.

Principe de fonctionnement :

1 : la condition est évaluée

2 : Si la condition a la valeur vraie on exécute <action_alors>

Si la condition a la valeur fausse on exécute <action_sinon>

Remarque :

Les <action_alors> ou <action_sinon> peuvent être soit :

  • des actions élémentaires
  • des composées (bloc)

Dans ce cas on utilise les structures imbriquées.

Exemple de structure imbriquée:

SI (A ≥ 10)

ALORS

  • SI ( A ≥ 12)ALORS ECRIRE (‘’Admis mention”)SINON ECRIRE (‘’Admis passable”)FINSI

SINON ECRIRE (‘’Ajourné”)

La syntaxe de la structure conditionnelle Au cas ou…Sinon…Fin de cas est la suivante :

   Au cas ou
      : (Expression_booléenne)
         instruction(s)
      : (Expression_booléenne)
         instruction(s)
      .
      .
      .

      : (Expression_booléenne)
         instruction(s)
   Sinon
      instruction(s)
   Fin de cas

A noter que l’élément Sinon est optionnel, vous pouvez donc écrire :

   Au cas ou
      : (Expression_booléenne)
         instruction(s)
      : (Expression_booléenne)
         instruction(s)
      .
      .
      .

      : (Expression_booléenne)
         instruction(s)
   Fin de cas

Tout comme la structure Si…Sinon…Fin de si, la structure Au cas ou…Sinon…Fin de cas permet également à votre méthode de choisir parmi plusieurs séquences d’instructions.

A la différence de la structure précédente, le Au cas ou…Sinon…Fin de cas peut tester un nombre illimité d’expressions booléennes et exécuter la séquence d’instructions correspondant à la valeur VRAI.

Il est fréquent que le nombre de répétitions soit connu à l’avance, et que l’on ait besoin d’utiliser le numéro de l’itération afin d’effectuer des calculs ou des tests. Le mécanisme permettant cela est la boucle POUR.

Cette boucle permet de parcourir un intervalle en répétant un traitement pour chacune des valeurs de cet intervalle

Syntaxe :

POUR <id_variable> DE <val_inférieure> A <val_supérieure>

[ PAR PAS de <val_pas>] →facultatif

FAIRE <actions>

FINPOUR

Les actions peuvent être simples ou composées.

Fonctionnement :

1 : Automatiquement, on a id_variable  val_inférieure

Donc, on n’a pas besoin d’initialiser, la structure se charge de la faire

2 : id_variable > val_supérieure ? :

Si oui alors STOP, on quitte la structure

Sinon :

  • on exécute le programme
  • automatiquement, l’incrémentation se fait (+1 ou + pas si l’on a définit un pas particulier, par défaut, le Pas est 1)
  • on remonte au début du 2 pour tester la condition id_variable > val_supérieure ?

La structure REPETER permet de répéter un traitement 1 ou plusieurs fois.

Pour choisir entre REPETER et tant que il faut se poser la question : faut-il éventuellement ne jamais faire le traitement ? Si oui : il faut utiliser tant que, sinon utiliser la structure REPETER qui exécute au moins une fois l’action.

La structure est dowhile : c’est à dire FaireTANTQUE . Alors que la structure algorithmique est répéter…jusqu’à.

BOUCLE TANQUE :

______________________________________________________________________

BOUCLE REPETER :

1. Pourquoi plusieurs dimensions ?

Une seule ne suffisait-elle pas déjà amplement à notre bonheur, me demanderez-vous ? Certes, répondrai-je, mais vous allez voir qu’avec deux (et davantage encore) c’est carrément le nirvana.Prenons le cas de la modélisation d’un jeu de dames, et du déplacement des pions sur le damier. Je rappelle qu’un pion qui est sur une case blanche peut se déplacer (pour simplifier) sur les quatre cases blanches adjacentes.Avec les outils que nous avons abordés jusque là, le plus simple serait évidemment de modéliser le damier sous la forme d’un tableau. Chaque case est un emplacement du tableau, qui contient par exemple 0 si elle est vide, et 1 s’il y a un pion. On attribue comme indices aux cases les numéros 1 à 8 pour la première ligne, 9 à 16 pour la deuxième ligne, et ainsi de suite jusqu’à 64.Arrivés à ce stade, les fines mouches du genre de Cyprien L. m’écriront pour faire remarquer qu’un damier, cela possède 100 cases et non 64, et qu’entre les damiers et les échiquiers, je me suis joyeusement emmêlé les pédales. A ces fines mouches, je ferai une double réponse de prof :

  1. C’était pour voir si vous suiviez.
     
  2. Si le prof décide contre toute évidence que les damiers font 64 cases, c’est le prof qui a raison et l’évidence qui a tort. Rompez.

Reprenons. Un pion placé dans la case numéro i, autrement dit la valeur 1 de Cases(i), peut bouger vers les cases contiguës en diagonale. Cela va nous obliger à de petites acrobaties intellectuelles : la case située juste au-dessus de la case numéro i ayant comme indice i-8, les cases valables sont celles d’indice i-7 et i-9. De même, la case située juste en dessous ayant comme indice i+8, les cases valables sont celles d’indice i+7 et i+9.Bien sûr, on peut fabriquer tout un programme comme cela, mais le moins qu’on puisse dire est que cela ne facilite pas la clarté de l’algorithme.

Syntaxe d’une fonction

FONCTION <nom_fonction> ( <liste des paramètres> ) : <type de résultat>

< déclaration des objets locaux à la fonction>

DEBUT

{ corps de la fonction}

RETOURNER(résultat)

FIN

Une procédure est un bloc d’instructions nommé et déclaré dans l’entête de l’algorithme et appelé dans son corps à chaque fois que le programmeur en a besoin.

Déclaration d’une procédure :

L’appel d’une procédure peut être effectué en spécifiant, au moment souhaité, son nom et éventuellement ses paramètres ; cela déclenche l’exécution des instructions de la procédure.

Tout simplement, pour que l’utilisateur entre une valeur x , on mettra :Lire x

Dès que le programme rencontre une instruction Lire, l’exécution s’interrompt, attendant la frappe d’une valeur au clavier. L’interruption peut durer quelques secondes, quelques minutes ou plusieurs heures : la seule chose qui fera exécuter la suite des instructions, c’est que la touche Entrée (Enter) ait été enfoncée.Aussitôt que c’est le cas, il se passe deux choses. Pour commencer, tout ce qui a été frappé avant la touche Entrée (une suite de lettres, de chiffres, ou un mélange des deux) est rentré dans la variable qui suit l’instruction Lire (ici, x). Et ensuite, immédiatement, la machine exécute l’instruction suivante. Lire est donc une autre manière d’affecter une valeur à une variable. Avec l’instruction d’affectation, c’est le programmeur qui choisit à l’avance quelle doit être cette valeur. Avec l’instruction Lire, il laisse ce choix à l’utilisateur.Dans le sens inverse, pour écrire quelque chose à l’écran, c’est aussi simple que : Ecrire y .