Cours Algorithme : Introduction - Procédure - Fonctions - Tests - Boucles - Exemples

Cours Algorithme : Introduction - Procédure - Fonctions - Tests - Boucles - Exemples

1. DEFINITIONS 

Algorithme : Description en langage naturel de la suite des actions effectuées par un programme structuré. Un algorithme est écrit en utilisant un langage de description d’algorithme (LDA).
L’algorithme ne doit pas être confondu avec le programme proprement dit (tel que Pascal, C, ..) 

Algorigramme : Traduction graphique de l’algorithme. Aussi appelé Organigramme. 

Quelques symboles utilisés pour construire un algorigramme 

 

 

Syntaxe : Règles d’écriture d’un langage donné. 

Type de données :

Un programme peut-être amené à manipuler différents types de données :

- booléen : valeur pouvant être soit Vraie, soit Fausse. 
- entiers : valeur numériques entières pouvant être signées ou non signées (codées sur un ou plusieurs octets). 
- réels : valeurs numériques codées avec une mantisse et un exposant. 
- caractère : octet correspondant à un code ASCII. 
- chaîne de caractères : ensemble de caractères. 
- tableau de données : ensemble de données de même type (exemple : tableau d’entiers, tableau de réels). 

Toutes ces données sont codées sous forme d'octets en mémoire. 

Constante : donnée manipulée par un programme et ne pouvant être modifiée. 

Exemple : Constante Pi = 3.141559 

Variable : donnée manipulée par un programme et pouvant être modifiée.

Ce peut être :

- une donnée d’entrée ; 
- le résultat final d’un calcul ; 
- un résultat intermédiaire de calcul. 

Identificateur : nom explicite d’une constante, d’une variable ou d’une fonction.

Exemples : Conversion_BCD, Résultat, Lettre… 

Procédures et fonctions : Une procédure ou une fonction effectuent une suite d’actions élémentaires constituant un tout. 

Une fonction se différencie d’une procédure par le fait qu’elle fournit un résultat. 

2. ORGANISATION D’UN PROGRAMME 

L’algorithme d’un programme est organisé en plusieurs parties :

• déclaration des constantes 
• déclaration des variables 
• définition des fonctions et procédures 
• définition du programme principal 

 

 

2.1 Déclaration des constantes

Syntaxe : Constante NomConstante : [Type] = Valeur 

Exemples :   Constante Pi : Reel = 3.141559
                     Constante NombreLettres : Entier = 10 
  
2.2 Déclaration des variables

Syntaxe : Variable NomVariable : [Type] 

Exemples :   Variable Rayon : Reel
                     Variable Compteur : Entier 
                     Variable Lettre : Caractere

2.3 Définition des fonctions et procédures

Les procédures et fonctions peuvent nécessiter éventuellement un ou plusieursparamètres d’entrée ou de sortie. 

Un paramètre d’entrée est la référence à une variable manipulée par la procédureou la fonction.

Un paramètre de sortie est une valeur renvoyée par une fonction.

Une fonction ou une procédure peut elle-même appeler une ou plusieurs fonctionset procédures. 

Syntaxe de la déclaration d’une fonction : 

Fonction NomFonction (NomEntrée1 : [Type], NomEntrée2 : [Type],…) : [TypeDuRésultat]

         Constante ~ déclaration des constantes locales ~ 
         Variable ~ déclaration des variables locales ~

         Début 
                  ~ description des actions effectuées par la fonction ~ 
         Fin 

Syntaxe de l’appel d’une fonction :

Variable <-- NomFonction (NomEntrée1, NomEntrée2…) 

Exemple de déclaration de fonction :

Fonction Moyenne (Note1 : Reel, Note2 : Reel) : Reel 
         Variable Intermediaire : Reel 
         Début 
                  Intermediaire <-- Note1 + Note2 
                  Intermediaire <-- Intermediaire / 2 
                  Moyenne <-- Intermediaire 
         Fin 

Exemples d’utilisation de la fonction : 

Afficher (Moyenne(10.5,15)) ou NouvelleNote <-- Moyenne (10,5.5) 
  
  Nota : la déclaration et l’appel d’une procédure ne sont pas développés ici. 

2.4 Définition du programme principal

Le programme principal consiste en une suite d’opérations élémentaires faisant souvent appel à des fonctions ou procédures. Ces différentes opérations sont mentionnées en utilisant les structures algorithmiques décrites au paragraphe 5. 

Le programme principal est délimité par les mots-clefs Début et Fin 
  
3. AFFECTATION 

Une affectation consiste à attribuer une valeur à une variable.

La syntaxe générale est la suivante : NomVariable <-- Expression 

 

« Expression » peut être :

• une constante. ......................................................................................Ex : surface ¬ 40
• une autre variable. .................................................…........Ex : Donnee <-- ValeurMemorisee
• le résultat d’une fonction. .......................................……....... Ex : resultat <-- racine (nombre)
• un calcul portant sur ces différents éléments. .……... Ex : surface <-- (PI * Carre (Diametre)) / 4

Nota : Un abus d’écriture nous amène parfois à voir le signe = à la place de la flèche. 

 

C’est valable normalement pour l’écriture en langage de programmation (Basic compilé, Pascal, …) mais pas dans un algorithme. 

4. OPERATEURS – CONDITIONS 

4.1 Opérateurs 
 

Les opérateurs permettent d’élaborer une expression en vue d’effectuer un calcul ou une comparaison.

L’usage des parenthèses est vivement conseillé dans le cas d’expressions complexes. 

 

4.2 Conditions

Dans les structures algorithmiques qui vont suivre, le terme « Condition » peut représenter :

• une condition simple : Ex : x 1 0 Indice 3 80
• une condition complexe : Ex : (x > 0) ET ((y > 0) OU (z > 0))
• (Indice ≥ 1) ET (Indice ≤ 10) ~ pour 1 ≤ Indice ≤10 ~

  
5. LES STRUCTURES ALGORITHMIQUES 

Les structures algorithmiques sont réparties en 3 catégories :

- structures linéaire d'opérations; 
- structures alternatives (ou conditionnelles) ou de choix : en fonction d'une condition, le programme exécute des opérations différentes; 
- structures itératives ou répétitives: sous contrôle d'une condition, une séquence d'opérations est exécutée répétitivement. 

5.1 Structure linéaire 

Les actions successives sont mentionnées les unes après les autres. 

 Syntaxe   

Action1 
Action2 
... 
ActionN 

Remarque : dans la suite, la notation « Actions » ou « ActionsN » représentera une succession d’actions comme ci-dessus. 

Exemple : Calcul d’un produit de 2 nombres

Variable 
        a,b : réel ~ opérandes ~ 
        p : réel ~ résultat du produit ~  

Début 
        Afficher (‘Saisir le nombre a ‘) 
        Saisir (a) 
        Afficher (‘Saisir le nombre b ‘) 
        Saisir (b) 
        p <-- a * b 
        afficher (p) 
Fin 

5.2 Structures alternatives 

5.2.1 Structure SI ... ALORS ... 

Une condition est testée pour déterminer si l’action ou le groupe d’actions suivant doit être exécuté. 

Syntaxe            

Si Condition   Alors 
Actions 
FinSi 

Remarque : au lieu de FinSi on écrit aussi fsi 

Exemple : Calcul d’une racine carrée

   
Variable 
        x: réel ~ opérande ~ 
        r: réel ~ résultat de la racine carrée ~ 
Début 
        Afficher (‘Saisir le nombre x‘) 
        Saisir (x) 
        Si x > 0 Alors 
                r <-- racine (x) 
                afficher (r) 
        FinSi 
Fin 
 

5.2.2 Structure SI ... ALORS ...SINON ... 

Une condition est testée pour déterminer quelle action ou quel groupe d’actions doit être exécuté. 

Syntaxe           

Si Condition  Alors 
Actions1 
  Sinon 
Actions2 
FinSi 

Exemple : Calcul d’une racine carrée

 Variables : 
        x: réel ~ opérande ~ 
        r: réel ~ résultat de la racine carrée ~ 
Début 
        Afficher (‘Saisir le nombre x‘) 
        Saisir (x) 
        Si x < 0 Alors 
                afficher (‘x est négatif’) 
        Sinon 
                r <-- racine (x) 
                afficher (r) 
        FinSi 
Fin 

5.2.3 Structure de choix multiple 

Une donnée est comparée successivement à des valeurs constantes : 

Syntaxe       
 

 Suivant Donnée faire 
Valeur1 : Actions1 
Valeur2 : Actions2 
... 
ValeurN : ActionsN 
Sinon  
ActionsN+1 
FinSuivant 

 

Remarques : la partie « ActionsN+1 » peut ne pas exister.

Plusieurs valeurs différentes peuvent être regroupées sur une même ligne si les actions correspondantes sont identiques. 

Exemple : Affichage de la nature d’un caractère

Variable

        c: caractère ~ caractère saisi au clavier ~

Début 
        Afficher (‘Taper un caractère‘) 
        Saisir (c) 
        Suivant c Faire 
                ‘A’..’Z’ : afficher (‘Lettre majuscule’) 
                ‘a’..’z’ : afficher (‘Lettre minuscule’) 
                ‘0’..’9’ : afficher (‘Chiffre’) 
        Sinon  
                afficher (‘Ni Lettre Ni Chiffre’) 
        FinSuivant 
Fin 

5.3 Structures itératives (ou répétitives) 

5.3.1 Structure REPETER ... JUSQUA ...

Une action ou un groupe d’actions est exécuté répétitivement jusqu'à ce qu’une condition soit vérifiée. 

Syntaxe  

      
Répéter  
Actions 
Jusqu’a Condition

Remarque : la vérification de la condition s’effectue après les actions. Celles-ci sont donc exécutées au moins une fois. 

Exemple : exécution répétitive d’un programme

Variables : 
        a,b : réel ~ opérandes ~ 
        p : réel ~ résultat du produit ~ 
        c : caractère ~ réponse de l’utilisateur ~ 

Début         Répéter 
                Afficher (‘Saisir le nombre a ‘) 
                Saisir (a) 
                Afficher (‘Saisir le nombre b ‘) 
                Saisir (b) 
                p <-- a * b 
                afficher (p) 
                afficher (‘encore un calcul ? Non touche N ; Oui autre touche’) 
                saisir (c) 
        Jusqu'à c = ‘N’ 
Fin

5.3.2 Structure TANT QUE ... FAIRE ...

Une action ou un groupe d’actions est exécuté répétitivement tout le temps où une condition est vraie. 

Syntaxe      

 
TantQue Condition 
Faire  
Actions 
FinFaire 

Remarque : la vérification de la condition s’effectue avant les actions. Celles-ci peuvent donc ne jamais être exécutées. 

Exemple : Exécution répétitive d’une action 

Début 
        Tant Que Non (ToucheAppuyée) 
                Faire 
                        Afficher (‘Attente’) 
                FinFaire 
Fin

5.3.3 Structure POUR Indice DE ... A .... FAIRE ...

Une action ou un groupe d’actions est exécuté répétitivement un certain nombre de fois : le nombre dépend des valeurs initiale et finale données à la variable « Indice ». 

 Syntaxe       

Pour Indice De Val1 A Val2 

Faire 
Actions 
FinFaire 

Remarque : les valeurs initiale (Val1) et finale (Val2) sont incluses dans le comptage. 

Il est éventuellement possible de spécifier un autre pas d’incrémentation (+2,+10,-1....) 

Exemple : Affichage d’une ligne d’étoiles

Variable 
        i : entier ~ compteur de boucles ~ 
Début 
        Pour i de 1 à 80 
        Faire 
                  Afficher (‘*’) 
          FinFaire 
Fin 
  
Remarque : cette structure algorithmique peut en fait être remplacée par une structure TANT QUE ... FAIRE … 

Variable 
        i : entier ~ compteur de boucles ~ 
Début 
        i <-- 1 
        Tant Que i ≥ 80 
        Faire 
                Afficher (‘*’) 
                i <-- i +1 
        FinFaire 
Fin 

Par la suite, nous nous intéresserons plus particulièrement aux structures algorithmiques du programme principal.

    

Résolution d'un problème de combinatoire

Il existe plusieurs fonctions de base : NON (no), OU (or), ET (and), OU NON (nor), ET NON (nand).
Ces fonctions sont réalisées dans différentes technologies (électriques, électroniques, pneumatiques, ...) et peuvent, suivant le cas, traiter 2, 3, 4... variables ce qui conduit à utiliser un grand nombre de modules différents.Comme il est moins onéreux d'acheter en grande quantité une même fonction que plusieurs fonctions différentes en faible quantité, et d'autre part, plus facile de gérer un stock de quelques composants qu'une multitude, les montages sont souvent réalisés avec 1 ou 2 fonctions seulement.

Etapes de la résolution

Pour résoudre le problème il faut :

1. Poser le problème correctement en envisageant tous les cas possibles, ce qui revient généralement à mettre l'énoncé sous la forme d'une table de vérité en faisant apparaître toutes les variables indépendantes d'entrées.
   L'énoncé peut ne pas préciser l'état de sortie pour certaines combinaisons des variables, en raison des impossibilités technologiques, par exemples.
2. Etablir le tableau de Karnaugh correspondant.
   Certaines cases peuvent ne correspondre ni à l'état 1, ni à l'état 0 de la grandeur de sortie.
3. Lire la fonction à partir du tableau en minimisant.
4. Etablir le schéma.

L'établissement du schéma dépend de la technologie choisie pour la réalisation.
En électromécanique à relais, la fonction logique permet d'établir le schéma développé par la mise en série ou parallèle des contacts.
En électronique ou en pneumatique, on dispose de blocs logiques correspondant aux fonctions de base du type :

• Fonction NO,
• fonction OR,
• fonction AND,
• fonction NOR,
• fonction NAND.

Le montage sera réalisé soit par association des fonctions "NON" "OU" "ET", soit uniquement à l'aide de NAND ou uniquement à l'aide de NOR ; le schéma établi porte alors le nom de logigramme.

Établissement du logigramme

Avec des fonctions élémentaires ET, OU, NON

Soit la fonction :
Y = d + (a + b) c
Nous avons toujours intérêt à mettre la fonction sous la forme d'une somme de produits.
Y = a.c + b.c + d
Ce qui conduit au logigramme :

Avec des fonctions NAND

Présenter la fonction sous la forme d'une somme de produits (conforme au groupement des 1 dans le diagramme de Karnaugh).
Méthode :
la fonction NAND de sortie est prise comme un OU,
les fonctions NAND d'entrée sont prises comme des ET.
Exemple :
Réalisation de la même fonction :
Y = d + (a + b) c

Ce qui conduit au logigramme :

Remarque :
Toute fonction écrite sous la forme d'une somme de produits peut être réalisée en deux couches d'opérateurs NAND.

Avec des fonctions NOR

Présenter la fonction sous la forme d'une somme de produits (conforme au groupement des 0 dans le diagramme de Karnaugh).
Méthode :
la fonction NOR de sortie est prise comme un ET
les fonctions NOR d'entrée sont prises comme des OU.
Exemple :
réalisation de la même fonction :
Y = d + (a + b) c
Il faut mettre sous forme de circuit NOR

Ce qui nous conduit au logigramme suivant :

Cours sur les Tableaux de Karnaugh cours et execices corrigés

Le cours sur les Tableaux de KARNAUGH, en fichier PDF ci-dessous :

Cours KARNAUGH

Fichier PDF du cours sur Karnaugh

et les exercices :

Exercices Karnaugh

et le corrigé :

Correction Exercices Karnaugh

les exercices d’application :

Ex. Bincomp

Ex CTRLQUAL

Ex. Distributeur de Boissons

Ex. Rose des vents

 

Cours sur l’Algèbre de BOOLE cours et exercices corrigés

Le cours sur l’algèbre de BOOLE, en fichier PDF ci-dessous :

Cours BOOLE

Fichier PDF du Cours sur l’algèbre de BOOLE.

les exercices :

Ex_Boole

Exercice de simplification de fonctions par l’algèbre de BOOLE

Correction Ex Boole.PDF

Correction des exercices sur l’agèbre de BOOLE.

Ex_Boole1

Correction Ex Boole1.PDF

Correction des exercices sur boole N°1

exercices2

la feuille de synthèse :

Synthese.pdf

Fichier PDF de la synthèse des portes logiques.

ASCII Character Base Converter

ASCII Character Base Converter
';

Multiplication And Division of Hex Numbers Calculator

Multiplication And Division of Hex Numbers Calculator
';