INF0101: Introduction aux Outils Informatiques - Chapitre 3 - Initiation à l'algorithmique - PDF

École Polytechnique de Montréal Département de Génie Informatique INF0101: Introduction aux Outils Informatiques CHAPITRE 3 Initiation à l'algorithmique Ali CHAMAM©2006...

École Polytechnique de Montréal Département de Génie Informatique INF0101: Introduction aux Outils Informatiques CHAPITRE 3 Initiation à l'algorithmique Ali CHAMAM©2006 1
   


       
     
    
                     
       
       2     ! )  &    ( !                "        #            $ %#         $ %   
&     ' 3 8                 !     $ % *  +  ,!-   ←3  $%.  $ 5%*3  # /  !$ %  $010#2 %/ $ 3/ + / 44%. $ 15%.    #   #   ,,,  $016 0# %/ 7 7 7 9  :   ! 4  &     "    )  &     ( !   : ;       :  
(:  ( !  ?            6 
   (       &    &! 


   

    

  



  




  
 

 

       &!  $ OUVRIR (ou ÉDITER) monProg.c $ COMPILER monProg.c EN monProg $ EXÉCUTER monProg 7
    (ex: Matlab)    


   

    

  



  




  
 

 

     &! 
OUVRIR (ou ÉDITER) ,m
INTERPRÉTER ,m (matlab monProg.m) 8  Partie 1 : Concepts de base 9 Plan de cette partie... Le formalisme utilisé Qu’est ce qu’une variable ? Qu’est ce qu’un type ? Qu’est ce qu’une expression ? Qu’est ce qu’une affectation Les entrées / sorties ? 10 Formalisme... Un algorithme doit être lisible et compréhensible par plusieurs personnes Il doit donc suivre des règles Il est composé d’une entête et d’un corps : l’entête, qui spécifi : le nom de l’algorithme (Nom :) son utilité (Rôle :) les données “en entrée”, c’est-à-dire les éléments qui sont indispensables à son bon fonctionnement (Entrée :) les données “en sortie”, c’est-à-dire les éléments calculés, produits, par l’algorithme (Sortie :) les données locales à l’algorithmique qui lui sont indispensables (Déclaration :) Ceci dit, on peut déclarer toutes les variables de l'algorithme à la suite du mot clé "Déclaration", sans avoir besoin de différencier entre les entrées et les sorties. Formalisme... le corps, qui est composé : du mot clef début d’une suite d’instructions indentées du mot clef fi 12 Formalisme... Exemple de code : Nom : addDeuxEntiers Rôle : Additionner deux entiers a et b et mettre le résultat dans c Entrée : a,b : entier Sortie : c : entier Déclaration : - début c ←a+b fin 13 Qu’est ce qu’une variable... Une variable est une entité qui contient une information : une variable possède un nom, on parle d’identifiant une variable possède une valeur une variable possède un type qui caractérise l’ensemble des valeurs que peut prendre la variable L’ensemble des variables sont stockées dans la mémoire de l’ordinateur 14 Qu’est ce qu’une variable... On peut faire l’analogie avec une armoire d’archive qui contiendrait des tiroirs étiquetés : l’armoire serait la mémoire de l’ordinateur les tiroirs seraient les variables (l’étiquette corresponderait à l’identidiant) le contenu d’un tiroir serait la valeur de la variable correspondante la couleur du tiroir serait le type de la variable (bleu pour les factures, rouge pour les bons de comande, etc.) 15 Qu’est ce qu’un type de données... Le type d’une variable caractérise : l’ensemble des valeurs que peut prendre la variable l’ensemble des actions que l’on peut effectuer sur une variable Lorsqu’une variable apparaît dans l’entête d’un algortithme on lui associe un type en utilisant la syntaxe suivante Identifiant de la variable : Son type Par exemple : age : Naturel nom : Chaîne de Caractères Une fois qu’un type de données est associé à une variable, cette variable ne peut plus en changer Une fois qu’un type de données est associé à une variable le contenu de cette variable doit obligatoirement être du même type 16 Qu’est ce qu’un type de données... Par exemple, dans l’exemple précédent on a déclaré a et b comme des entiers a et b dans cet algorithme ne pourront pas stocker des réels a et b dans cet algorithme ne pourront pas changer de type Il y a deux grandes catégories de type : les types simples les types complexes (que nous verrons dans la suite du cours) 17 Les types simples... Il y a deux grandes catagories de type simple : Ceux dont le nombres d’éléments est fini les dénombrables Ceux dont le nombre d’éléments est infini les indénombrables 18 Les types simples dénombrables... booléen, les variables ne peuvent prendre que les valeurs VRAI ou FAUX intervalle, les variables ne peuvent prendre que les valeurs entières déf nies dans cet intervalle, par exemple 1..10 énuméré, les variables ne peuvent prendre que les valeurs explicitées, par exemple les jours de la semaine (du lundi au dimanche) Ce sont les seuls types simples qui peuvent être déf nis par l’informaticien caractères Exemples : masculin : booléen mois : 1..12 jour : JoursDeLaSemaine 19 Cas des énumérés... Si l’informaticien veut utiliser des énumérés, il doit définir le type dans l’entête de l’algorithme en explicitant toutes les valeurs de ce type de la façon suivante : nom du type = {valeur1, valeur2,..., valeurn} Par exemple : JoursDeLaSemaine = {Lundi, Mardi, Mercredi, Jeudi, Vendredi, Samedi, Dimanche} 20 Les types simples indénombrables... entier (positifs et négatifs) naturel (entiers positifs) réel chaîne de caractères, par exemple ’cours’ ou ’algorithmique’ Exemples : age : naturel taille : réel nom : chaîne de caractères 21 Opérateur, opérande et expression... Un opérateur est un symbole d’opération qui permet d’agir sur des variables ou de faire des “calculs” Une opérande est une entité (variable, constante ou expression) utilisée par un opérateur Une expression est une combinaison d’opérateur(s) et d’opérande(s), elle est évaluée durant l’exécution de l’algorithme, et possède une valeur (son interprétation) et un type 22 Opérateur, opérande et expression... Par exemple dans a+b : a est l’opérande gauche + est l’opérateur b est l’operande droite a+b est appelé une expression Si par exemple a vaut 2 et b 3, l’expression a+b vaut 5 Si par exemple a et b sont des entiers, l’expression a+b est un entier 23 Opérateur... Un opérateur peut être unaire ou binaire : Unaire s’il n’admet qu’une seule opérande, par exemple l’opérateur non Binaire s’il admet deux opérandes, par exemple l’opérateur + Un opérateur est associé à un type de donnée et ne peut être utilisé qu’avec des variables, des constantes, ou des expressions de ce type Par exemple l’opérateur + ne peut être utilisé qu’avec les types arithmétiques (naturel, entier et réel) ou (exclusif) le type chaîne de caractères On ne peut pas additionner un entier et un caractère Toutefois exceptionnellement dans certains cas on accepte d’utiliser un opérateur avec deux opérandes de types différents, c’est par exemple le cas avec les types arithmétiques (2+3.5) 24 Opérateur... La signification d’un opérateur peut changer en fonction du type des opérandes Par exemple l’opérateur + avec des entiers aura pour sens l’addition, mais avec des chaînes de caractères aura pour sens la concaténation 2+3 vaut 5 "bonjour" + " tout le monde" vaut "bonjour tout le monde" 25 Les opérateurs booléens... Pour les booléens nous avons les opérateurs non, et, ou, ouExclusif non a non a Vrai Faux Faux Vrai et a b a et b Vrai Vrai Vrai Vrai Faux Faux Faux Vrai Faux Faux Faux Faux 26 Les opérateurs booléens... ou a b a ou b Vrai Vrai Vrai Vrai Faux Vrai Faux Vrai Vrai Faux Faux Faux ouExclusif a b a ouExclusif b Vrai Vrai Faux Vrai Faux Vrai Faux Vrai Vrai Faux Faux Faux 27 Les opérateurs sur les naturels, entiers et réels... On retrouve tout naturellemment +, -, /, * Avec en plus pour les naturels et les entiers div et mod, qui permettent respectivement de calculer une division entière et le reste de cette division, par exemple : 11 div 2 vaut 5 11 mod 2 vaut 1. 28 L’opérateur d’égalité, d’inégalité, etc... L’opérateur d’égalité C’est l’opérateur que l’on retrouve chez tous les types simples qui permet de savoir si les deux opérandes sont égales Cet opérateur est représenté par le caractère = Une expression contenant cet opérateur est un booléen On a aussi l’opérateur d’inégalité = Et pour les types possédant un ordre les opérateurs de comparaison 29 Priorité des opérateurs... Tout comme en arithmétique les opérateurs ont des priorités Par exemple * et / sont prioritaires sur + et - Pour les booléens, la priorité des opérateurs est non, et, ouExclusif et ou Pour clarifier les choses (ou pour dans certains cas supprimer toutes ambiguités) on peut utiliser des parenthèses 30 Actions sur les variables... On ne peut faire que deux choses avec une variable : 1. Obtenir son contenu Cela s’effectue simplement en nommant la variable 2. Lui affecter un (nouveau) contenu (mettre une (nouvelle) valeur dans la variable) Cela s’effectue en utilisant l’opérateur d’affectation représenté par le symbole ← La syntaxe de cet opérateur est : identifiant de la variable ← expression sans operateur d’affectation 31 Actions sur les variables... Par exemple, l’expression c ← a + b se comprend de la façon suivante : On prend la valeur contenue dans la variable a On prend la valeur contenue dans la variable b On additionne ces deux valeurs On met le résultat dans la variable c Si c avait auparavant une valeur, cette dernière sera perdue ! 32  Les entrées/sorties... Un algorithme peut avoir des interactions avec l’utilisateur Il peut affiche un résultat (du texte ou le contenu d’une variable) et demander à l’utilisateur de saisir une information afi de la stocker dans une variable En tant qu’informaticien on raisonne en se mettant “à la place de la machine”, donc : Pour afficher une information on utilise la commande écrire suivie entre parenthèses de la chaîne de caractères entre guillemets et/ou des variables de type simple à aff cher séparées par des virgules, par exemple : écrire("Le valeur de la variable a est", a) Pour donner la possibilité à l’utilisateur de saisir une information on utilise la commande lire suivie entre parenthèses de la variable de type simple qui va recevoir la valeur saisie par l’utilisateur, par exemple : lire(b) 33 Exemple d’algorithme... Nom : euroVersDollar1 Rôle : Convertisseur des sommes en euros vers le dollar, avec saisie de la somme en euro et affichage de la somme en dollar Entrée : - Sortie : - Déclaration : valeurEnEuro, valeurEnDollar, tauxConversion : Réel début tauxConversion ← 1.45 écrire("Votre valeur en euro :") lire(valeurEnEuro) valeurEnDollar ←valeurEnEuro * tauxConversion écrire(valeurEnEuro," euros = ",valeurEnDollar,"CAN $") fin 34  Exemple d’algorithme... Nom : euroVersDollar2 Rôle : Convertisseur des sommes en euros vers le dollar Entrée : valeurEnEuro : Réel Sortie : valeurEnDollar : Réel Déclaration : tauxConversion : Réel début tauxConversion ←1.45 valeurEnDollar ←valeurEnEuro * tauxConversion fin 35 Partie 2 : Conditionnelles et itérations 36 Rappels sur la logique booléenne... Valeurs possibles : Vrai ou Faux Opérateurs logiques : non et ou optionellement ouExclusif mais ce n’est qu’une combinaison de non , et et ou a ouExclusif b = (non a et b) ou (a et non b) Priorité sur les opérateurs : non , et , ou Associativité des opérateurs et et ou a et (b et c) = (a et b) et c Commutativité des opérateurs et et ou a et b = b et a a ou b = b ou a 37 Rappels sur la logique booléenne... Distributivité des opérateurs et et ou a ou (b et c) = (a ou b) et (a ou c) a et (b ou c) = (a et b) ou (a et c) Involution non non a = a Loi de Morgan non (a ou b) = non a et non b non (a et b) = non a ou non b 38 Les conditionnelles... Jusqu’à présent les instructions d’un algorithme étaient toutes interprétées séquentiellement Nom : euroVersDollar2 Rôle : Convertisseur des sommes en euros vers le dollar Entrée : valeurEnEuro : Réel Sortie : valeurEnDollar : Réel Déclaration : tauxConversion : Réel début tauxConversion ←1.45 valeurEnDollar ← valeurEnEuro * tauxConversion fi Mais il se peut que l’on veuille conditionner l’exécution d’un algorithme Par exemple: la résolution d’une équation du second degré est conditionnée par le signe de ∆ 39 L’instruction si alors sinon... L’instruction si alors sinon permet de conditionner l’éxecution d’une suite d'instructions à la valeur d’une expression booléenne Sa syntaxe est : si expression booléenne alors suite d’instructions exécutées si l’expression est vraie sinon suite d’instructions exécutées si l’expression est fausse fin si Le deuxième partie de l’instruction est optionnelle, on peut avoir la syntaxe suivante : si expression booléenne alors suite d’instructions exécutées si l’expression est vraie fin si 40  Exemple... Nom : abs Rôle : Calcule la valeur absolue d’un entier Entrée : unEntier : Entier Sortie : laValeurAbsolue : Entier Déclaration : - début si unEntier ≥ 0 alors laValeurAbsolue ←unEntier sinon laValeurAbsolue ←-unEntier fin si fin 41 Exemple... Nom : max Rôle : Calcule le maximum de deux entiers Entrée : lEntier1,lEntier2 : Entier Sortie : leMaximum : Entier Déclaration : - début si lEntier1 < lEntier2 alors leMaximum ←lEntier2 sinon leMaximum ←lEntier1 fin si fin 42  Exemple... Nom : max Rôle : Calcule le maximum de deux entiers Entrée : lEntier1,lEntier2 : Entier Sortie : leMaximum : Entier Déclaration : - début leMaximum ←lEntier1 si lEntier2 > lEntier1 alors leMaximum ←lEntier2 fin si fin 43 Les itérations... Lorsque l’on veut répéter plusieurs fois un même traitement, plutôt que de copier n fois la ou les instructions, on peut demander à l’ordinateur d’éxecuter n fois un morceau de code Il existe deux grandes catégories d’itérations : Les itérations déterministes : le nombre de boucles est défin à l’entrée de la boucle les itérations indéterministes : l’exécution de la prochaine boucle est conditionnée par une expression booléenne 44  Les itérations déterministes... Il existe une seule instruction permettant de faire des boucles déterministes, c’est l’instruction pour Sa syntaxe est : pour identifiant d’une variable de type scalaire ←valeur de début à valeur de fin faire instructions à exécuter à chaque boucle fin pour dans ce cas la variable utilisée prend successivement les valeurs comprises entre valeur de début et valeur de fin 45 Exemple... Nom : somme Rôle : Calculer la somme des n premiers entiers positifs, s=0+1+2+... +n Entrée : n : Naturel Sortie : s : Naturel Déclaration : i : Naturel début s←0 pour i ←0 à n faire s ← s+i ; fin pour fin 46  Les itérations indéterministes... La boucle s'exécutera jusqu'à ce que l'expression booléenne devienne fausse. L’instruction tant que : tant que expression booléenne faire instructions fin tant que Ce qui signifie: "tant que l’expression booléenne est vraie, on exécute les instructions". Si vous ne voulez pas que votre algorithme “tourne” indéfiniment, l’expression booléenne doit faire intervenir des variables dont le contenu doit être modifié par, au moins, une des instructions du corps de la boucle 47 Un exemple... Nom : invFact Rôle : Détermine le plus grand entier e telque e! ≤ n Entrée : n : Naturel ≥ 1 Sortie : e : Naturel Déclaration : fact : Naturel début fact ← 1 e←1 tant que fact ≤ n faire e ← e+1 fact ← fact*e fin tant que e ← e-1 fin 48  Explication avec n=10... Nom : invFact Rôle : Détermine le plus grand entier e telque e! ≤ n Entrée : n : Naturel≥ 1 Sortie : e : Naturel Déclaration : fact : Naturel n e fact fact ≤ n début fact ← 1 fact ←1 10 ? 1 vrai e←1 e ←1 10 1 1 vrai tant que fact ≤ n faire e ←e+1 10 2 2 vrai e ← e+1 fact ←fact*e fact ← fact*e e ←e+1 10 3 6 vrai fin tant que e ← e-1 fact ←fact*e fin e ←e+1 10 4 24 faux fact ←fact*e e ←e-1 10 3 24 faux 49 Partie 3: Pseudo-code schématique (selon la norme de représentation adoptée à l'école polytechnique) 50 Pseudo-code schématique ƒ Nous décrirons les tâches à partir des opérations élémentaires suivantes: ¾Lire ¾Additionner ¾Écrire ¾Soustraire ¾TANT QUE condition FAIRE ¾Multiplier ¾POUR ensemble_de_données FAIRE ¾Diviser ¾SI condition ALORS --- SINON ¾Affecter = 51 Pseudo-code schématique: Exemple 1 ƒ Lire un nombre et écrire la valeur absolue de ce nombre ƒ Quelles sont les entrées? Un nombre. ƒ Quelles sont les sorties? Écriture d'un nombre. ƒ Comment trouvons-nous une valeur absolue? Il faut changer le signe du nombre s'il est négatif. ƒ Est-ce qu'il y a des répétitions ? Non. ƒ Est-ce que des décisions ou vérifications sont requises? Oui. Combien? 1. Quelles sont les alternatives? Inversion du signe si le nombre est négatif, sinon on fait rien. Elles influencent quelles opérations ? Écriture du nombre. 52 Pseudo-code schématique Exemple 1 - suite ƒ Lire un nombre et écrire la valeur absolue de ce nombre (suite) Écrire "Entrer un nombre" Décalage pour Lire le nombre démontrer la SI le nombre