Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

UNE INTRODUCTION A L’ALGORITHMIQUE SUPPORT DE COURS D’ALGORITHMIQUE - BOLI KUYO

UNE INTRODUCTION A L’ALGORITHMIQUE SUPPORT DE COURS D’ALGORITHMIQUE - BOLI KUYO ANDRE Page 1 1. MOTIVATION 1.1 Le Problème Un algorithme peut se définir comme un cheminement à suivre dans la résolution d’un problème donné. A l’analyse, cette définition souffre de deux insuffisances majeures qui sont : - la liberté de choix d’un langage et d’une méthode pour poser un problème peut entrainer différentes interprétations d’un même problème ; - la liberté de choix d’un langage et d’une méthode pour la description du cheminement proposé peut entrainer différentes interprétations d’un même algorithme. Afin de garantir une convergence des différentes interprétations, l’on doit définir une démarche dite objective qui sera adoptée pour poser correctement un problème et pour la description d’un algorithme exempte de toute forme et de toute espèce d’ambigüité. Une démarche dite objective se caractérise par : - le principe de base (ou l’axiome définissant la condition initiale : une définition de l’être en question) ; - les notions de base (les outils nécessaires au développement de la démarche) ; - les étapes et les relations existant entre celles – ci (les actions à développer au niveau de chaque étape). Afin d’exclure toute forme et toute espèce d’ambigüité, une démarche objective et un langage formel seront adoptés pour la description des outils et pour la formulation des actions à développer. 1.2 L’Objet du cours L’objet du cours est donc l’apprentissage de la démarche objective préconisée et des structures du langage formel qui seront adoptés. SUPPORT DE COURS D’ALGORITHMIQUE - BOLI KUYO ANDRE Page 2 2. UNE PRESENTATION DE LA DEMARCHE 2.1 Objectif L’objectif est la présentation de la démarche qui sera adoptée pour la description ou la construction d’un algorithme. Rappel : une démarche se caractérise par : - le principe de base ou l’axiome de base ; - les mécanismes ou les outils de base ; - les étapes et les relations existant entre elles. 2.2 Le principe de base L’on souhaite construire un algorithme permettant de résoudre un problème se caractérisant par : - l’énoncé du problème : les données nécessaires (ou données disponibles) et les relations existant entre celles – ci ; les résultats escomptés et les relations existant ceux – ci ; - l’objectif : les contraintes décrivant le contexte et la recherche du cheminement à suivre pour passer des données aux résultats escomptés Alors, poser un problème consiste à demander les actions à développer pour passer des données aux résultats escomptés tout en observant les contraintes. Un algorithme devient alors une machine logique développant un ensemble fini d’actions sur des données qu’elle admet en entrée, pour fournir en sortie les résultats escomptés. Elle peut être représentée à l’aide du schéma ci – dessous. Schéma 1 : une représentation schématique d’un algorithme Un algorithme est une machine logique qui converge au voisinage des résultats escomptés : un algorithme s’arrête dès l’obtention des Actions Résultats escomptés Données UNE PRESENTION DES ALGORITHMES DE BASE - BOLI KUYO ANDRE Page 3 résultats escomptés. 2.3 Les notions de base Les caractéristiques d’un algorithme deviennent alors les données disponibles, les résultats escomptés et les actions. Les notions de base sont celles nécessaires pour : - la description et la spécification des données et des résultats (les résultats intermédiaires et les résultats escomptés); - la formulation des actions à développer. L’ensemble des résultats est composé des résultats escomptés et des résultats intermédiaires. 2.4 Les étapes Pour la description d’un algorithme l’on devra procéder par : - la description et la spécification de l’ensemble des données et de l’ensemble des résultats ; - la formulation des actions à développer pour passer des données aux résultats escomptés tout en observant les contraintes. Afin d’éviter toute forme et toute espèce d’ambigüité l’on devra adopter un langage formel. Un langage est dit formel quand il exclue toute forme et toute espèce d’ambigüité (par opposition au langage naturel). 2.5 La préoccupation Notre préoccupation est l’apprentissage de la démarche pour la construction des algorithmes de base (ou algorithmes élémentaires): - la présentation des notions de base ; - la présentation de la structure d’un algorithme ; - la présentation des structures de base du langage formel qui sera adopté pour la description d’un algorithme. 3. LES NOTIONS DE BASE 3.1 Objectif SUPPORT DE COURS D’ALGORITHMIQUE - BOLI KUYO ANDRE Page 4 L'objectif est la définition des notions de base nécessaires pour la description d'un algorithme. 3.2 Notion de variable Une variable représente soit une donnée soit un résultat ; alors ses caractéristiques sont les suivantes : - un identificateur qui est un moyen permettant de désigner de façon unique un être ou une entité ; - un type décrivant sa structure algébrique à savoir : - sa forme logique qui est l’ensemble des composants et leur mode d’agencement ; - l'ensemble des opérateurs autorisés ou applicables à la forme logique ; - l'espace de valeurs possibles. Nous ne parlerons pour l’instant que des types de base en vue de faciliter l’apprentissage. Les types qui sont obtenus par combinaisons linéaires des types de base feront l’objet d’autres cours. 3.3 Notion de type de base (élémentaire) Nous distinguons quatre types de base qui sont : - le type Réel dont les caractéristiques sont les suivantes : - la forme est : <Signe> < Séquence de chiffres> . < Séquence de chiffres> ; - l'ensemble d'opérateurs autorisés est {+,-,*,/} ; - l'espace de valeurs possibles est IR. - le type Entier dont les caractéristiques sont les suivantes : - la forme est <Signe> < Séquence de chiffres> ; - l'ensemble d'opérateurs autorisés est {+,-,*,/} ; - l'espace de valeurs possibles est ZZ (l’ensemble des entiers relatifs). - le type Booléen dont les caractéristiques sont les suivantes : - la forme est un code ; - l'ensemble d'opérateurs autorisés est {┐,V,^} ; UNE PRESENTION DES ALGORITHMES DE BASE - BOLI KUYO ANDRE Page 5 - l'espace de valeurs possibles est {0,1}. - le type Caractère dont les caractéristiques sont les suivantes : - la forme est un code ; - l'ensemble d'opérateurs autorisés est vide ; - l'espace de valeurs possibles est l’ensemble des symboles élémentaires. 3.4 Notion d'opérateur de base Les opérateurs de base sont les suivants : - ceux qui sont autorisés sur les types de base à savoir {+,-,*,/, ┐,V,^ } ; - les comparateurs à savoir {≤,< , ≥,>,=,≠}. 3.5 Notion d'expression de base Une expression est l’application d’opérateurs à des variables ; une expression est donc une combinaison linéaire d'opérateurs et de variables. Si les variables sont de types de base et les opérateurs sont de base alors l'expression est dite de base. Elle est dite élémentaire quand ne combine que des variables et des opérateurs en observant leur compatibilité. Les variables et l’opérateur doivent être compatibles (de types identiques ou de types imbriqués) : - si l’opérateur est arithmétique alors les variables doivent être de type Réel ou Entier et l’expression est de type Réel ou Entier ; - si l’opérateur est logiques alors les variables doivent être de type Booléen et l’expression est de type booléen ; - si l’opérateur un comparateur alors les variables doivent être de type Entier ou de type Réel et l’expression est de type booléen. • Question : Quel devra être le type des variables et celui de l’expression dans les cas suivants : - x * y - a < b 3.6 Notion d'affectation SUPPORT DE COURS D’ALGORITHMIQUE - BOLI KUYO ANDRE Page 6 Une affectation est l'évaluation d'une expression et l'attribution du résultat à une variable. Alors dans une affectation l'expression et la variable doivent être de types identiques. L’affectation est notée ← et se lit reçoit. • Question : Quel devra être le type de chacune des variables dans l'affectation suivante : Z ← X + Y L’on peut distinguer différentes familles d'affectation dont : - l'affectation classique (celle dont nous venons de parler) ; - l'initialisation ; - l'incrémentation ; - le cumul. 3.6.1 Initialisation Une initialisation est une affectation dans laquelle l'expression est substituée par une constante. Elle est de la forme x ← Cte 3.6.2 Incrémentation Une incrémentation est une affectation de la forme : x <— x + Cte 3.6.2.1.1 Interprétation L'on peut noter la présence de la même variable à gauche et à droite de l'affectation. Cette formulation s'interprète de la façon suivante : - la variable de gauche représente la valeur courante (ou nouvelle valeur) ; - la variable de droite représente la valeur précédente ; - pour obtenir la valeur courante ; la valeur précédente sera augmentée de la valeur d’une constante. UNE PRESENTION DES ALGORITHMES DE BASE - BOLI KUYO ANDRE Page 7 Question : Que vous rappelle cette formulation et comment s’appelle – t – elle ? 3.6.2.1.2 Simulation Exemple : - L’on voudrait qu’une variable (x) parcourt les valeurs 0 , 5, 10 , 15 - La formulation est la suivante : - x <— 0 {définition de la valeur initiale} ; - x <— x + 5 {définition de l’incrémentation}. Si nous exécutons l’incrémentation un uploads/s3/ support-complet-algo-de-base-pdf.pdf