Cours d'Algorithmique - 2023/2024 - Université Ibn Zohr PDF

PARTIE1: L’ALGORITHMIQUE - Introduction - Organigramme - Instructions de contrôle - Instructions répétitives 1 Département Informatique Faculté de Sciences – Université Ibn Zohr Année Universitair...

PARTIE1: L’ALGORITHMIQUE - Introduction - Organigramme - Instructions de contrôle - Instructions répétitives 1 Département Informatique Faculté de Sciences – Université Ibn Zohr Année Universitaire 2023/2024 C’EST QUOI UN ALGORITHME ? (1/2) Définition 01  Un algorithme représente une séquence d’instructions (Actions), logiquement ordonnées, qui permet de résoudre un problème donné. Problème à Algorithme Résoudre Résoudre  d’actions (instruction) Remarques  Pas d’Algorithme sans Problème. Un algorithme est lié à un problème bien précis.  Un Algorithme sera traduit à un programme qui sera exécuté par un ordinateur. 2 Année Universitaire : 2023/2024 C’EST QUOI UN ALGORITHME ? (2/2) Définition 02  Un algorithme représente une séquence d’actions (Instructions), logiquement ordonnées, qui transforment des données en entrées (inputs) vers des données en sortie (outputs). Ces dernières (outputs) représentent la solution d’un problème donné. Modélise Problème Extraire (Déduire) Données Algorithme  de Données +  d’instruction 3 Année Universitaire : 2023/2024 ANALYSE ET RÉSOLUTION D’UN PROBLÈME Problème Analyser et Etudier le problème à Résoudre Spécifier le modèle de Résolution : données et les Modèle formules mathématiques Algorithme Écrire l’algorithme Traduire l’algorithme à un programme Programme Exécuter le programme par un ordinateur afin Résultats d’obtenir des résultats 4 Année Universitaire : 2023/2024  DÉFINITION ET OBJECTIF D’UN ALGORITHME Un algorithme est la description de la solution d’un problème sous la forme d’une suite finie d’opérations à effectuer sur les données du problème. Pour fonctionner, un algorithme doit contenir uniquement les instructions compréhensibles par celui qui devra l’exécuter. Son fonctionnement nécessite un certain nombre d’objets, cet ensemble s’appelle : environnement de l’algorithme. 5 Année Universitaire : 2023/2024 STRUCTURE D’UN ALGORITHME (1/3) Entête Permet d’identifier l’algorithme avec un nom unique (Identificateur) Algorithme  de Données +  d’instruction Déclarations On déclare toutes les données (Variables et Constantes) Corps (Instructions) La partie des instructions (Entrées, Traitement et Sorties) Modèle d’écriture d’un Algorithme Algorithme Début 6 Fin Année Universitaire : 2023/2024 STRUCTURE D’UN ALGORITHME (2/3) Exemples – Entête d’un Algorithme Algorithme exo1 Algorithme Equation1D Algorithme PGCD_PPCM Algorithme Nombre_Premier Etc. Exemples – Déclarations Constantes PI 3.14 HAUTEUR 15.78 nom Université Zohr F TRUE Variables : 7 Année Universitaire : 2023/2024 STRUCTURE D’UN ALGORITHME (3/3) Types de Données  Il y a cinq types de base : Entier, Réel, Caractère, Chaîne de Caractère et Booléen.  Un type Représente un ensemble de valeurs (fini ou infini)  Les Nombres naturels sont inclus dans le type Entier. Exemples – Déclarations Variables : a : entier b : réel x:entier y:entier z:entier → x, y, z : entiers , , …, : 8 Année Universitaire : 2023/2024 INSTRUCTIONS ÉLÉMENTAIRES EN ALGORITHMIQUE Le langage algorithmique offre trois instructions élémentaires de base :  l’affectation.  entrée de données.  sortie de données. 9 Année Universitaire : 2023/2024 DONNÉES : VARIABLES & CONSTANTES Définition  Une Donnée représente une information liée à un élément du problème traité par l’algorithme. Variable C’est un objet contenant une valeur pouvant être modifiée. Dans un programme, ça représente Données une zone mémoire dans la RAM. Constante C’est un objet contenant une valeur fixe (ne peut jamais être modifiée). 10 Année Universitaire : 2023/2024 DONNÉES : IDENTIFICATEUR (1/2) Concept d’Identificateur  Chaque donnée (Variable ou constante) manipulée par un algorithme est désignée par un nom unique : IDENTIFICATEUR.  Identificateur : c’est une chaîne de caractères alphanumérique (contenant uniquement des caractères alphabétiques [a-z, A-Z] et numériques [0-9]) en plus du caractère « _ » (Trait souligné) et qui ne commence pas par un caractère numérique. Remarques  Même l’algorithme lui-même possède un nom unique. Donc, il doit avoir un identificateur pour l’algorithme.  Un identificateur est affecté à un seul objet. On ne peut jamais utiliser le même identificateur pour deux variables ou constantes différentes. 11 Année Universitaire : 2023/2024 DONNÉES : IDENTIFICATEUR (2/2) Exemple  Parmi les identificateurs suivants, indiquer ceux qui sont valides et ceux qui ne le sont pas ? 12x ; Prix Unitaire ; Hauteur-Mur ; a1 ; a?b ; Réponse 12x : n’est valide, puisqu’il commence par un caractère numérique. Doit être : x12 Prix Unitaire : n’est pas valide, puisqu’il contient un espace. Doit être : PrixUnitaire ou Prix_Unitaire. Hauteur-Mur : n’est pas valide, puisque il contient le signe « - »(moins). Doit être : Hauteur_Mur. a1 : est valide a?b : n’est pas valide, puisqu’il contient le caractère « ? ». Doit être : ab. 12 Année Universitaire : 2023/2024 DONNÉES : TYPES DES VARIABLES Le type d’une variable permet de :  Définir l’ensemble de valeurs que peut prendre la variable  Fixer la taille, en cases mémoires (octets), de la variable  Définir la nature des opérations autorisées sur la variable Les types utilisés en langage algorithmique sont :  Entierpour représenter les entiers positifs ou négatifs  Réel pour représenter les nombres à virgule  Caractère pour représenter des caractères  Chaîne pour représenter des phrases  Booléen pour représenter les valeurs de vérité de la 13 logique Année Universitaire : 2023/2024 INSTRUCTION ÉLÉMENTAIRE : AFFECTATION L’affectation permet d’assigner une valeur à un objet. Elle est représentée en algorithmique par le symbole Syntaxe : Identificateur valeur Le membre droit d’une affectation (valeur) peut être soit :  Une variable de même type que identificateur  Une constante de même type que identificateur  Une expression dont l’évaluation produit un résultat final de même type que identificateur 14 Année Universitaire : 2023/2024 INSTRUCTION ÉLÉMENTAIRE : AFFECTATION Les affectations suivantes sont incorrectes : 16 valeur X*Y 15 Le membre gauche d’une affectation (lvalue) doit être une variable déclarée. Il doit correspondre à une case mémoire qui peut recevoir une valeur. De même la partie droite d’une affectation doit être une quantité bien définie, c à d une structure ayant une évaluation qui fournit une valeur résultat. 15 Année Universitaire : 2023/2024 INSTRUCTION ÉLÉMENTAIRE : AFFECTATION Les types de deux parties de l’affectation doivent être les mêmes Exemple d’affectation Soit deux variables X et Y de type entier, Supposons que la variable X contient la valeur 16 et que la variable Y contient 25. Que valent les valeurs de X et Y après les instructions d’affectation suivantes ? X X + Y Instruction 1 Y X - Y Instruction 2 X X - Y Instruction 3 16 Année Universitaire : 2023/2024 INSTRUCTION ÉLÉMENTAIRE : AFFECTATION Schématisons un peu ! X contient 16 et Y contient 25, veut dire que les cases mémoire nommées respectivement X , Y et qui sont situées en mémoire aux adresses adr1200 et adr1204 (par exemple) contiennent respectivement les valeurs 16 et 25. 25 16 Y X adr1204 adr1200 17 Année Universitaire : 2023/2024 INSTRUCTION ÉLÉMENTAIRE : AFFECTATION X X + Y Instruction 1 Y X - Y Instruction 2 X X - Y Instruction 3 L’instruction 1 peut être expliciter comme ceci : 1. Évaluation de l’expression X + Y Addition des valeurs de X et Y 2. Affectation du résultat de l’expression X + Y à X + 16 25 41 X Y adr1200 adr1204 18 Année Universitaire : 2023/2024 INSTRUCTION ÉLÉMENTAIRE : AFFECTATION 16 41 25 X 41 Y adr1200 adr1204 Après l’instruction 1, X contient 41 et la variable Y n’a pas été modifiée. Après l’instruction 2, X vaut 41 (elle n’a pas été modifiée) la variable Y contient 16. Après l’instruction 3, X contient 25 et Y 16. 19 Année Universitaire : 2023/2024 INSTRUCTION ÉLÉMENTAIRE : AFFECTATION Remarques :  L’ensemble des instructions 1, 2 et 3 permet de permuter les valeurs de deux variables.  L’opérateur d’affectation détruit complètement et définitivement le contenu d’une variable 20 Année Universitaire : 2023/2024 INSTRUCTION ÉLÉMENTAIRE : AFFECTATION Algorithme Affectation1 Algorithme Affectation2 Variables Variables X, Y : entiers X, Y : entiers Début Début X 15 X 15 Y 25 Y 25 X Y Y X Y X X Y Fin Fin Dans les deux algorithmes ci-dessus, les instructions sont exécutées dans l'ordre, séquentiellement : l'une après l'autre. Du fait de cet ordre séquentiel, les deux séquences ci-dessus ont des effets très différents. Les valeurs de sorties pour les variables X et Y sont : 25 pour l’algorithme 1 et 15 pour l’algorithme 2. 21 Année Universitaire : 2023/2024  DONNÉES : ENTRÉES ET SORTIES Données Données Données d’Entrée Intermédiaires (Inputs) Données utilisées par Les données que Données de Sortie l’algorithme pour le (Outputs) l’utilisateur doit traitement lié au fournir à Les données que problème l’algorithme. l’algorithme doit montrer à l’utilisateur. C’est les résultats de l’algorithme (Solution du Problème) 22 Année Universitaire : 2023/2024 INSTRUCTION D’ENTÉE Elle permet d’introduire une valeur d’une variable. L’entrée de données peut être effectuée soit par clavier ou directement par lecture des données stockées sur le disque. En langage algorithmique la fonction utilisée pour lire des données est : Lire(maVar) cette instruction permet d’affecter à la variable maVar, la valeur lue sur le périphérique d’entrée. 23 Année Universitaire : 2023/2024 INSTRUCTION DE SORTIE La sortie, qui constitue le résultat, peut être affichée à l’écran, imprimée sur papier ou stockée dans une mémoire magnétique. La fonction de sortie utilisée en algorithmique est la fonction Écrire : Écrire(monRésultat) cette instruction permet de transférer la valeur monRésultat vers le périphérique de sortie. 24 Année Universitaire : 2023/2024 EXERCICE Proposer une analyse pour calculer le périmètre d’un cercle ( 2*π*leRayon) Analyse du problème PI 3.14 lePerimetre leRayon 25 Année Universitaire : 2023/2024 EXERCICE Algorithme A1 Algorithme perimetreCercle constante PI 3.14 Variables lePerimetre, leRayon : réels Début Lire(leRayon) lePerimetre 2*PI*leRayon Ecrire(lePerimetre) Fin 26 Année Universitaire : 2023/2024 RÉSUMÉ  Un algorithme permet de résoudre un problème à travers une séquence d’instructions ordonnées logiquement. Ces instructions transforment des données en entrée en données en sortie.  Chaque donnée utilisée dans un algorithme est soit variable ou constante.  Un algorithme doit être traduit à un programme exécutable par l’ordinateur pour avoir des résultats.  Pour écrire des algorithmes, il faut respecter une certaine structure ou modèle d’écriture. 27 Année Universitaire : 2023/2024  ORGANIGRAMMES (1) Un organigramme est une représentation schématique d’un algorithme mettant en valeur sa structure. Il permet de mieux présenter les différents modules de traitement et d’expliquer la succession des opérations d’un travail. Les symboles utilisés dans un organigramme sont : Début Début : démarrage d’un traitement Séquence : marque le passage d’une action à une autre Test et décision : marque un choix Non Oui condition conditionnel d’une action à exécuter suivant que la condition est vérifiée ou non. 28 Année Universitaire : 2023/2024  ORGANIGRAMMES (2) Variante de l’alternative : selon la valeur selon(var) de la variable var, il y aura branchement vers l’exécution de l’instruction correspondante. S S + T Opération : calcul modifie une variable par l’affectation d’une nouvelle valeur. Instruction d’entrée/sortie : entrée de données standard à partir du clavier ou sortie de données standard vers l’écran. Fin Fin : Arrêt d’un traitement 29 Année Universitaire : 2023/2024  EXEMPLE TRADUCTION DE L’ALGORITHME A1 Début Algorithme perimetreCercle const PI 3.14 Variables Lire(leRayon) lePerimetre, leRayon : réels Début Lire(leRayon) lePerimetre 2*PI*leRayon lePerimetre 2*PI*leRayon Écrire(lePerimetre) Fin Écrire(lePerimetre) Fin 30 Année Universitaire : 2023/2024 INSTRUCTIONS COMPOSÉES Les algorithmes précédents présentent un enchaînement d’exécution linéaire et séquentiel, dans la pratique, il peut y avoir des cas où l’on exige une exécution par morceau, c à d des sauts ou des répétitions d’un même bloc d’instructions. Ceci peut se faire à l’aide des primitives de base structurées. Il existe deux types d’instructions composées :  Les primitives de choix  Les primitives d’itérations 31 Année Universitaire : 2023/2024 INSTRUCTIONS CONDITIONNELLES (1/8) Syntaxe de l’instruction conditionnelle simple  L’instruction conditionnelle permet de décider si on exécute une suite d’instructions (bloc d’instructions) ou non. Cette décision est basée sur une condition : Expression booléenne. Si la condition est vrai, on exécute alors ce bloc d’instructions. Sinon, on l’exécute pas.  La syntaxe de l’instruction conditionnelle est : Si Alors …….. FinSi Bloc du Si 32 Année Universitaire : 2023/2024 INSTRUCTIONS CONDITIONNELLES (2/8) Sémantique de l’instruction conditionnelle simple  Soit l’exemple suivant (Algorithmique) ⚫ Si (x > 0) Alors Ecrire (" X est positif") FinSi  Ça veut dire quoi cette instruction ?  Le sens de cette instruction est comme suit : Si la valeur de x est supérieure à 0 alors on affiche la chaîne ‘X est positif’. Si la condition est fausse, on exécute automatiquement l’instruction qui vient après FinSi. 33 Année Universitaire : 2023/2024 INSTRUCTIONS CONDITIONNELLES (3/8) Utilisation de l’instruction conditionnelle simple  Quant-est-ce que nous utiliserons l’instruction conditionnelle simple ?  Dans l’algorithmique, et dans plusieurs situations, des instructions ne sont pas toujours exécutées. Ces instructions sont exécutées uniquement si une ou plusieurs conditions doivent être vérifiées. Ces conditions sont formulées sous forme d’expression booléennes : ⚫ Si l’expression booléenne vaut TRUE (Vrai), alors ces instructions seront exécutées. ⚫ Si l’expression vaut FALSE (Faux), alors ces instructions ne sont pas exécutées.  Dans ce type de cas, on est amené à utiliser l’instruction conditionnelle simple. 34 Année Universitaire : 2023/2024 INSTRUCTIONS CONDITIONNELLES (4/8) Exemple  Ecrire un algorithme qui affiche la valeur absolue d’un nombre réel. Début Algorithme ValAbs Variables Lire(X) X : réel Oui Début X0) Alors xx–1 Sinon xx+2 FinSi  L’instruction précédente signifie que si la valeur de x est supérieure à 0 alors on décrémente la valeur de x (x  x-1), sinon (c-a-d x ≤0) on incrémente la variable x de 2 (x  x+2).  Si on prend l’exemple x=-5, donc on exécute le bloc Sinon, puisque la condition x>0 n’est pas vérifiée. Ainsi, la nouvelle valeur de x est : -3.  Si on prend x = 8, donc on exécute le bloc Si, (la condition x>0 est vérifiée). La nouvelle valeur de x sera : 7. 37 Année Universitaire : 2023/2024  INSTRUCTIONS CONDITIONNELLES (7/8) Utilisation de l’instruction conditionnelle simple  Quant-est-ce que l’instruction conditionnelle est simple ?  Dans plusieurs problèmes, on est amené à choisir entre deux séquences d’instructions à exécuter. Le choix, bien évidemment est effectué selon une condition (expression booléenne).  Dans certain cas, il faut choisir entre au moins trois blocs d’instructions (plus que deux). La solution est d’utiliser les structures imbriquées : on aura par exemple une instruction conditionnelle simple à l’intérieur du bloc Si (ou du bloc Sinon) d’une autre instruction conditionnelle simple. 38 Année Universitaire : 2023/2024  INSTRUCTIONS CONDITIONNELLES (8/8) Exemple  Exemple valeur absolue d’un nombre réel : Algorithme ValAbs Début Variables X, Y : réels LIRE(X) Début Lire(X) Si(X < 0) Alors Non Oui Y -X xB) alors Max ← A Sinon Max ← B Fin Si Retourner Max Fin L’APPEL D’UNE FONCTION : Pour exécuter une fonction, il suffit de faire appel à elle en écrivant son nom suivi des paramètres dans le programme principal. Le résultat d'une fonction étant une valeur, devra être affecté à une variable où être utilisé dans une expression, calcul, affichage, test, …etc. Exemple //Algorithme principal Variable max : Entier Début Ecrire("saisir une valeur de A ") Lire(A) Ecrire("saisir une valeur de B ") Lire(B) 8 Université IBN ZOHR - Faculté des Sciences d’Agadir Année Universitaire 2023-2024 //Appel de la fonction maximum() max←maximum(A, B) Ecrire("Le maximum est: ",max) Fin III. Les procédures : SYNTAXE : Procedure nom_Procedure (parm1 : Type, parm2 : Type, …) Début Instruction 1 Instruction 2...... Instruction n Fin APPEL DE LA PROCEDURE : Pour déclencher l'exécution d'une procédure dans un algorithme, il suffit de l'appeler. L'appel de procédure s'écrit en mettant le nom de la procédure, puis la liste des paramètres, séparés par des virgules. A l'appel d'une procédure, l'algorithme interrompt son déroulement normal, exécute les instructions de la procédure, puis retourne au programme appelant et exécute l'instruction suivante. SYNTAXE : nom_Procedure (Pram1, Param2, …) EXEMPLE : Appel de la procédure Addition qui prend en paramètres deux nombres A et B de type entier puis affiche le résultat de l’addition. Algorithme Addition //Déclaration de la procédure Addition() Procédure Addition (A : entier, B : entier) Début Ecrire("Le résultat de l’addition et :", A+B) Fin //Algorithme principal Début Ecrire("saisir une valeur de A ") Lire(A) 9 Université IBN ZOHR - Faculté des Sciences d’Agadir Année Universitaire 2023-2024 Ecrire("saisir une valeur de B ") Lire(B) //Appel de la procédure Addition() Addition(A, B) Fin REMARQUES : Contrairement à l'appel d'une fonction, on ne peut pas affecter la procédure appelée ou l'utiliser dans une expression. L'appel d'une procédure est une instruction autonome. IV. Le passage par valeur et par adresse : Il y a deux méthodes pour passer des variables en paramètre dans une fonction : le passage par valeur et le passage par variable. Passage par valeur : La valeur de l’expression passée en paramètre est copiée dans une variable locale. C’est cette variable qui est utilisée pour faire les calculs dans la fonction appelée. Si l’expression passée en paramètre est une variable, son contenu est copié dans la variable locale. Aucune modification de la variable locale dans la fonction appelée ne modifie la variable passée en paramètre, parce que ces modifications ne s’appliquent qu’à une copie de cette dernière. Passage par adresse : La deuxième technique consiste à passer non plus la valeur des variables comme paramètre, mais à passer les variables elles-mêmes. Il n’y a donc plus de copie, plus de variable locale. Toute modification du paramètre dans la fonction appelée entraîne la modification de la variable passée en paramètre. 10 Université IBN ZOHR - Faculté des Sciences d’Agadir Année Universitaire 2023-2024 Exemple : V. Portées des variables : On peut manipuler deux types de variables dans un module (procédure ou fonction) : des variables locales et des variables globales. Elles se distinguent par ce qu'on appelle leur portée (leur "champ de définition", leur "durée de vie") Les variables locales : Une variable déclarée à l'intérieur d'une procédure/fonction est dite locale. Elle n'est accessible qu'à la procédure/fonction au sein de laquelle elle est définie, les autres procédures/fonctions n'y ont pas accès. La durée de vie d'une variable locale est limitée à la durée d'exécution de la procédure/fonction. Les variables globales : Une variable déclarée dans la partie déclaration de l'algorithme principale est appelée variable globale. Elle est accessible de n'importe où dans l'algorithme, même depuis les procédures et les fonctions. Elle existe pendant toute la durée de vie d'algorithme. 11