Cette page donne les explications de base permettant ensuite d'analyser des algorigrammes de complexité quelconque.

SOMMAIRE :

L'interface homme / machine : les LEDs et les interrupteurs

Les blocs de base : entrée, sortie, calcul, test et bouble

Les différents types de boucle : tant que, jusqu'à, x fois

Les tests multiples : le bloc Multi-Décision

L'opérateur modulo : symbolisé par %

Les opérateurs logiques : AND OR XOR et NOT

Les algorigrammes utilisant les masques binaires

 

 

Les algorigrammes permettent de programmer de manière graphique une carte électronique à base de microcontrôleur.

L'interface homme/machine (IHM) permet à l'utilisateur humain de communiquer avec la carte électronique :

• le seul moyen pour l'utilisateur d'envoyer une information à la carte est d'agir sur des interrupteurs
• le seul moyen pour la carte d'informer l'utilisateur est d'allumer des LED

Les LED comme les interrupteur sont connectés à un port de 8 bits (port A ou port B selon les cas) dont l'information numérique côté algorigramme est un octet dans lequel les bits sont à 0 ou à 1 selon l'état des LED ou des interrupteurs.

Pour les LED l'octet est envoyé vers le port et :

• si un bit est à 0 alors la LED de même rang est éteinte
• si un bit est à 1 alors la LED de même rang est allumée

Par exemple pour allumer la LED A5 il faut mettre 32 dans le port A (car 32 = 2 puissance 5) comme le montre l'algorigramme suivant :

Et pour allumer les LED A4 et A1 simultanément il faut mettre 18 dans le port A (car 18 = 16 + 2), etc. :

Chaque LED possède donc un POIDS (le nombre en rouge ci-dessous correspondant au résultat des puissances de 2) et pour allumer plusieurs LED il faut envoyer sur le port la somme des poids des LED à allumer :

A retenir : le lien entre la valeur de l'octet envoyé sur un port et l'état des LED correspond donc à une conversion décimal/binaire naturel.

Pour les interrupteurs l'octet est récupéré à partir du port et :

• si un interrupteur est ouvert alors le bit de même rang est à 0
• si un interrupteur est fermé alors le bit de même rang est à 1

Chaque interrupteur possède un POIDS (2 puissance son rang) et la valeur récupérée dans l'octet à partir du port où sont connectés les interrupteurs est égale à la somme des poids des interrupteurs fermés.

Exemple : quelle valeur est récupérée dans la variable n dans l'algorigramme ci-contre ?

Les seuls interrupteurs fermés sur le port A sont ici A4, A1 et A0, soit les interrupteurs de rang 4, 1 et 0. Il ont donc respectivement pour poids 16, 2 et 1. La valeur récupérée dans la variable n est la somme des poids des interrupteurs fermés, soit 19 dans cet exemple, car 16+2+1=19.

A retenir : le lien entre l'état des interrupteurs et la valeur de l'octet récupéré sur un port correspond donc à une conversion binaire naturel/décimal.

Un algorigramme permet de représenter simplement sous forme graphique un algorithme qui peut être complexe. La lecture de l'algorigramme ne nécessite aucun apprentissage dès lors qu'on connaît la signification des blocs de base.

Le bloc entrée

Symbole graphique du bloc entrée

Il permet de récupérer un octet à partir d'un port afin de connaître l'état des interrupteurs connectés à ce port. Les bits de l'octet récupéré sont à 0 ou à 1 selon que les interrupteurs sont ouverts ou fermés.

Le bloc sortie

Symbole graphique du bloc sortie

Il permet d'envoyer une valeur numérique (sous forme d'un octet) vers un port sur lequel sont connectées 8 LED afin de commander l'état des LED connectées à ce port. Les LED sont éteintes ou allumées selon que les bits de l'octet envoyé sont à 0 ou à 1.

Le bloc affectation

Symbole graphique du bloc affectation

Il permet d'effectuer un calcul simple, et d'enregistrer le résultat dans une variable.

A retenir : une affectation consiste à donner à une variable une valeur particulière.

Exemple d'affectation avec l'équivalent en Python :

Algorigramme	Syntaxe en Python
	n = 3

Remarque : l'opérateur d'affectation est le symbole "égale à" (=) dans les algorigrammes comme en Python.

Le bloc test

Symbole graphique du bloc test

Il permet d'orienter l'algorigramme vers une branche ou une autre. Le bloc test est en forme de losange contenant une contition logique :

• si la condition logique est VRAIE alors l'exécution de l'algorigramme se poursuit vers la sortie OUI
• si la condition logique est FAUSSE alors l'exécution de l'algorigramme se poursuit vers la sortie NON

Le bloc test permet d'implémenter une structure conditionnelle dans l'algorigramme.

A retenir : une structure contidionnelle effectue un test afin d'orienter la suite du programme.

Exemple de tests avec l'équivalent en Python :

Algorigramme	Syntaxe en Python
	if n==3:       a = 4    else:       a = a+1
	if n!=3:       a = 4    else:       a = a+1

Remarque :

• en Python le test d'égalité (==) est différent de l'opérateur d'affectation (=)
• dans les algorigrammes le test d'égalité comme l'affectation utilisent le symbole =
• seul le contexte d'application permet de distinguer un test d'égalité d'une affectation dans un algorigramme

Les blocs boucle

Symbole graphique d'une boucle

Une boucle permet de répéter plusieurs fois une séquence de l'algorigramme. La boucle est encodrée par 2 blocs :

• le premier bloc contient une condition logique
• toute la séquence comprise entre les 2 blocs sera répétée tant que la condition est VRAIE

La boucle permet d'implémenter une structure itérative dans l'algorigramme.

A retenir : une structure itérative répète plusieurs fois une partie du programme.

La boucle Tant que avec le test en début de boucle est la structure itérative par défaut utilisée dans les algorigrammes.

Mais il existe d'autres types de boucles permettant d'implémenter une structure itérative, les voici.

Boucle x fois avec un nombre d'itérations défini à l'avance (équivalent à une boucle for) :

Algorigramme	Syntaxe en Python
	for i in range(5):       n = n+1

Remarque : une boucle x fois effectura un nombre d'itérations défini à l'avance, sans attendre la vérification d'une condition logique.

Boucle Tant que avec test au début de la boucle : on sort de la boucle si le test est FAUX

Algorigramme	Syntaxe en Python
	while n<5:       n = n+1

Remarque : la boucle while de Python correspond naturellement à un bloc Tant que avec test au début de la boucle.

Boucle Jusqu'à avec test au début de la boucle : on sort de la boucle si le test est VRAI

Algorigramme	Syntaxe en Python
	while not(n>5):       n = n+1

Remarque : en Python une boucle Jusqu'à est implémentée par une boucle while avec complémentation de la contition. Le complément logique d'une condition A s'écrit not(A) en Python.

Boucle Tant que avec test à la fin de la boucle : on sort de la boucle si le test est FAUX

Algorigramme	Syntaxe en Python
	while True:       n = n+1       if not(n<5):          break

Remarque : lorsque le test est à la fin de la boucle on entrera obligatoirement au moins une fois dans la boucle, même si la contidion logique est fausse dès le départ.

Boucle Jusqu'à avec test à la fin de la boucle : on sort de la boucle si le test est VRAI

Algorigramme	Syntaxe en Python
	while True:       n = n+1       if n>5:          break

Remarque : lorsque le test est à la fin de la boucle, en Python on commence une boucle while inifie puis on sort de la boucle grâce à l'instruction  break dès que la condition de sortie est atteinte.

Rappel sur le contrôle des boucles en Python :

• l'instruction break dans une boucle permet de sortir immédiatement de la boucle
• l'instruction continue dans une boucle permet de passer à l'itération suivante sans finir le bloc de la boucle

Les tests multiples réalisés par un bloc Multi-Décision sont une nouvelle structure contidionnelle bien pratique.

Un bloc Multi-Décision remplace une succession de blocs Décision de base qui auraient été imbriqués entre eux.

Exemple d'algorigramme utilisant un bloc Multi-Décision :

L'algorithme du bloc Multi-Décision de cet algorigramme est le suivant :

Si n=0 alors affecter à la variable x la valeur x+3
Sinon si n=1 alors affecter à la variable x la valeur x+2
Sinon si n=2 alors affecter à la variable x la valeur x+4
Sinon si n=3 alors affecter à la variable x la valeur x+1
Sinon si n=4 alors affecter à la variable x la valeur x+5
Sinon affecter à la variable x la valeur x+n

Et voici l'algorigramme équivalent à ce bloc Multi-Décision avec des blocs Decision de base :

L'opérateur modulo calcule le reste de la division entière entre 2 entiers.

Dans un algorigramme (comme dans Python) il se symbolise par le caractère % (caractère "pour cent").

Exemple de résultats donnés par l'opérateur modulo (symbolisé par %) :

6 % 2 = 0 (car 6 est multiple de 2)

6 % 3 = 0 (car 6 est multiple de 2)

9 % 2 = 1 (car 9=2*4 et il reste 1)

9 % 3 = 0 (car 9=3*3 et il reste 0 : 9 est multiple de 3)

9 % 4 = 1 (car 9=4*2 et il reste 1)

9 % 5 = 4 (car 9=5*1 et il reste 4)

9 % 6 = 3 (car 9=6*1 et il reste 3)

etc.

Exemple d'algorigramme utilisant l'opérateur modulo (symbolisé par le caractère pour cent) :

Dans cet algorigramme la variable n prend la valeur du reste de la division entière de x par 7 : n ne peut donc prendre que 7 valeurs différentes (un entier de 0 à 6). Ensuite le bloc Multi-Décision effectue une opération en fonction de la valeur de n comme vu précédemment.

Autre exemple d'algorigramme utilisant l'opérateur modulo (symbolisé ici par le caractère pour cent) :

Ici la variable n prend la valeur du reste de la division entière de x par a puis le bloc décision teste si n égale 0 :

• le bloc décision sortira par OUI si x est un multiple de a
• le bloc décision sortira par NON si x n'est pas un multiple de a

La question posée par le bloc décision dans cet algorigramme est donc "Est-ce que x est un multiple de a ?" : OUI ou NON ?

Dans un algorigramme il est possible de trouver les 4 opérateurs logiques suivants :

Remarque : les opérateurs logiques sont écrit en anglais et en majuscule.

Les fonctions logiques ET-NON, OU-NON et OU-Exclusif-NON n'existant pas directement on pourra les créer avec les équations suivantes :

S = NOT (A AND B)

S = NOT (A OR B)

S = NOT (A XOR B)

Mais dans un algorigramme les opérateurs logiques sont des opérateurs binaires agissant sur tout un octet (et non sur un seul bit).

• dans un algorigramme un test est considéré faux si son résultat est nul (valeur numérique de l'opération égale à zéro) : dans ce cas l'algorigramme est dirigé vers la sortie NON du test
• un test est considéré vrai si son résultat est non nul (valeur numérique de l'opération égale à 1, à 2, à 3, à 4, etc. à 255 ou tout autre nombre autre que zéro) : dans ce cas l'algorigramme est dirigé vers la sortie OUI du test

L'opérateur AND, qui est un ET logique bit à bit appliqué sur tout un octet, permet d'écrire un masque binaire afin d'effectuer des tests sur certains bits d'un octet.

Exemples de masques binaires pour différentes valeurs de n afin d'effectuer un test sur les 3 bits de poids faible d'un nombre n (bits de rang 0, 1 ou 2 seulement) :

Par exemple dans l'algorigramme suivant le test i AND 1 permet juste de distinguer si i est pair ou impair :

• si i est impair l'opération i and 1 vaudra 1, donc considéré VRAI, et le test sortira par OUI
• si i est pair l'opération i and 1 vaudra 0, donc considéré FAUX, et le test sortira par NON

A retenir : le test i AND 1 peut être remplacé par la question "i est-il impair ?" : OUI ou NON

Autre exemple d'utilisation des opérateurs logiques avec un OU-Exclusif bit à bit dans une boucle :

Rappel :

• les itérations se poursuivent tant que la condition x XOR n est VRAI, c'est-à-dire différente de 0
• on sortira de la boucle lorsque x XOR n sera FAUX, c'est-à-dire égal à 0

Or x XOR n vaut 0 si et seulement si x et n sont égaux (égalité de chaque bit de même rang sur les 2 nombres).

Conclusion : la condition x XOR n dans la boucle est strictement équivalente à la condition x est différent de n :

• la boucle se poursuit tant que x ≠ n
• on sortira de la boucle losque x = n

Dans le thème "Les algorigrammes utilisant les masques biniares" il y a seulement 8 algorigrammes différents.

Pour tout savoir sur ces algorigrammes, cliquez ici.

Réalisé par Jean-Christophe MICHEL

© Novembre 2020