Remerciez-le!

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

Introduction à l’algorithmique SMAHI Zakaria smahi@mail.com Maitre de Conférenc

Introduction à l’algorithmique SMAHI Zakaria smahi@mail.com Maitre de Conférence Dépt de Génie Physique Faculté de Physique USTOMB 1ère année ST1 2019/2020, Semestre 2 SMAHI Zakaria (2020) 1 Un algorithme est une suite finie de règles à appliquer dans un ordre déterminé à un nombre fini de données pour arriver, en un nombre fini d‘étapes, à un certain résultat, et cela indépendamment des données. Introduction à l’algorithmique SMAHI Zakaria (2020) 2 1. Définition d’un Algorithme 1.1. Son origine: Le mot algorithme provient du nom d'un célèbre mathématicien musulman de la première moitié du IXe siècle: Muhammad ibn Musa al Khawarizmi (Khiva (Xiva en ouzbek est une ville d'Ouzbekistan), son ancien nom, Khwarezm ou Khorezm). SMAHI Zakaria (2020) 3 1.2. Son Rôle: Le rôle de l'algorithme est fondamental. En effet, sans algorithme, il n'y aurait pas de programme (qui n'est jamais que sa traduction dans un langage compréhensible par l'ordinateur). De plus, les algorithmes sont fondamentaux en un autre sens: ils sont indépendants à la fois de l'ordinateur et des langages de programmation dans lesquels ils sont énoncés et traduits. SMAHI Zakaria (2020) 4 « Ecrire un algorithme », c’est : Analyser et comprendre le problème : étudier les données fournies et les résultats attendus Résoudre le problème, c’est trouver les structures de données adaptées ainsi que l’enchaînement des actions à réaliser pour passer des données aux résultats Comment exécuter un algorithme sur un ordinateur ? Il faut traduire cet algorithme à l’aide d’un langage de programmation connu par l’ordinateur. SMAHI Zakaria (2020) 5 En Résumé : Un Algorithme consiste à retranscrire un processus logique à l’aide d’un langage naturel. Un Algorithme est la description d’un traitement qui consiste à transformer des données, appelées « entrées » , afin de produire d’autres données appelées « sorties ». Les entrées et les sorties représentent les variables manipulées par l’algorithme. Processus de Principe : Entrées -> Traitement -> Sorties SMAHI Zakaria (2020) 6 2.Représentation d’un algorithme 2.1. Le langage Naturel (Exp : Français). Exemple : comment formuler l’algorithme qui calcule la surface d’un disque ? Réponse : Pour calculer la surface d’un disque, on prend d’abord connaissance de son rayon. La surface est égale au produit de la constante π par le carré du rayon. Historiquement, trois façons pour représenter un algorithme: SMAHI Zakaria (2020) 7 2. 2. L’Organigramme: L’Organigramme: Représentation graphique avec des symboles (carrés, losanges, etc.) Avantage : offre une vue d’ensemble de l’algorithme Inconvénient : représentation quasiment abandonnée aujourd’hui 2. Représentation d’un algorithme SMAHI Zakaria (2020) 8 L’ellipse : indique le début de l’algorithme Le parallélogramme : représente une opération de Lecture ou Ecriture Le rectangle : représente le contenu de chaque étape de traitement, il définit l’opération à exécuter. La flèche : sert à indiquer l’ordre d’exécution des différentes taches. L’Hexagone : sert à indiquer l’initialisation de certains paramètres. Le losange : il représente l’existence d’un choix logique : la proposition logique est indiquée à l’intérieur du losange. Le cercle : indique la poursuite d’une étape précédente. Le triangle renversé : symbolise la fin de l’algorithme. Symboles Signification Représentation graphique d’un Organigramme SMAHI Zakaria (2020) 9 Exemple : Calcul de surface d’un disque Pi=3.141592 Rayon Sur  Pi* Rayon² Sur Sortie: Ecran Entrée: Clavier SMAHI Zakaria (2020) 10 2. 3. Le pseudo-code ou Langage de Description d’Algorithme (LDA): 2. 3. Le pseudo-code ou Langage de Description d’Algorithme (LDA): C’est une représentation textuelle avec une série de conventions ressemblant à un langage de programmation (sans les problèmes de syntaxe) plus pratique pour écrire un algorithme représentation largement utilisée SMAHI Zakaria (2020) 11 Exemple précédent devient: Algorithme surf_Disq ; CONST Pi = 3.141592 : Réel ; VAR Sur, Rayon: Réel ; DEBUT LIRE(Rayon) ; Sur Pi* Rayon**2 ; Ecrire(Sur) ; FIN SMAHI Zakaria (2020) 12 3. Structure générale d’un Algorithme : En générale, l’algorithme comprend les étapes suivantes : 3.1. En tête : Algo Nom de l’algorithme; 3. 2. Déclaration : (Constante, Variable, Structure) 3. 2.1. Type de variable Une variable correspond à un type de variable. Les principaux types sont : Byte (codé sur 1 octet: de 0 à 255) Caractère (codé sur 1 octet: de 0 à 255) Chaîne de caractères (toute suite de caractères ) Entier (codé sur 2 octets: de -32768 à 32767) Réel (codé sur 4 octets: de 0 à 255) Booléen (vraie ou fausse 0 ou 1, codé sur 1 octet SMAHI Zakaria (2020) 13 3. 2.2. Déclaration d’une variable Rappel: toute variable utilisée dans un programme doit avoir fait l’objet d’une déclaration préalable En pseudo-code, on va adopter la forme suivante pour la déclaration de variables Var liste d'identificateurs : type; Var liste d'identificateurs : type; Exemple: Var i, j,k : Entier; x, y : Réel; OK: Booléen; ch1, ch2 : Chaîne; SMAHI Zakaria (2020) 14 3.3. Corps de l’Algo: Début Lecture de données; Initialisation des paramètres; Transformation des données en résultats; Ecriture des résultats; Fin. SMAHI Zakaria (2020) 15 4.1. L’instruction d’affectation Affecter une variable consiste à lui donner une valeur. Cette valeur peut être soit une constante, soit une valeur d’une autre variable, soit le résultat d’un calcul. L’affectation est représentée par une flèche orientée à gauche  Exemple Exemple : Si A,B sont deux variables de type Byte (valeur comprise entre 0 et 255), alors on peut écrire : B  15, A  B+ 4, A  A + 1 1/ Le terme de droite (15) est affecté au terme de gauche (variable A) 2/ " " (valeur de la variable B + 4) affecté au terme gauche (variable A) 3/ " "" (valeur de A (avant instruction) + 1) affecté (variable A. Dans ce dernier cas la nouvelle valeur de A remplace l'ancienne. Si une variable est numérique A  0 Si une variable est chaîne de caractères A  "0", ou A  " Lettres " 4. Les instructions Algorithmiques SMAHI Zakaria (2020) 16 Quelques remarques : Beaucoup de langages de programmation (C, Fortran, pascal, …) utilisent le signe égal = pour l’affectation ←. Attention aux confusions: l'affectation n'est pas commutative : A=B est différente de B=A l'affectation est différente d'une équation mathématique : A=A+1 a un sens en langages de programmation A+1=2 n'est pas possible en langages de programmation et n'est pas équivalente à A=1 4.1. L’instruction d’affectation SMAHI Zakaria (2020) 17 4.2. L’entrée d’information La primitive d’entrée ou saisir (entrée clavier) et lire (lecture en provenant du disque dur). Le but de ces primitives est de permettre à l’ordinateur d’affecter une variable extérieure à une autre variable. Le nom de cette variable symbolise une adresse en mémoire centrale. A cette adresse se trouve la valeur, à un moment donné de la variable. La primitive de sortie : écrire, afficher, imprimer. Le but est de permettre à l’ordinateur de sortir la valeur d’une variable vers les périphériques extérieurs (écran, imprimante, etc…) SMAHI Zakaria (2020) 18 Les instructions de lecture et d'écriture permettent à la machine de communiquer avec l'utilisateur 4.2.1.1. Entrées (Lecture) La lecture permet d'entrer des données à partir du clavier Synthaxe: Lire (A) Lire (A) l la machine met la valeur entrée au clavier dans la zone mémoire nommée A Remarque: Le programme s'arrête lorsqu'il rencontre une instruction Lire et ne se poursuit qu'après la frappe d’une valeur au clavier et de la touche Entrée 4.2.1. Instructions d'entrées-sorties: (Lecture et Ecriture) SMAHI Zakaria (2020) 19 L'écriture permet d'afficher des résultats à l'écran (ou de les écrire dans un fichier) Synthaxe: Ecrire (A) Ecrire (A) la machine affiche le contenu de la zone mémoire A Conseil: Avant de lire une variable, il est fortement conseillé d’écrire des messages à l’écran, afin de prévenir l’utilisateur de ce qu’il doit frapper 4.2.1. Instructions d'entrées-sorties (Lecture et Ecriture) 4.2.2. Sorties (Ecriture) SMAHI Zakaria (2020) 20 4.2.2. Méthode de construction d’un algorithme simple Exemple : Écrire un algorithme qui consiste à calculer l’air S d’un cercle selon la formule S = Pi * R2 Rappel : Pi = 3.14159 et R le rayon du cercle SMAHI Zakaria (2020) 21 Méthodologie à suivre : Constantes : Pi = 3.14159 Variables : Rayon, Surface Types : Rayon, Surface : réel Expressions et affectation : Surface <- Pi * (Rayon)2 Opérations d’entrée-sortie : Lire (Rayon), Écrire (Surface) 4.2.2. Méthode de construction d’un algorithme simple SMAHI Zakaria (2020) 22 Algo Calcul_Aire; Const Pi = 3,14159 : Réels; Var Rayon, Surface : Réels; Début Lire (Rayon); Surface <- Pi * (Rayon)^2; Ecrire (Surface); Fin. 4.2.2. Méthode de construction d’un algorithme simple SMAHI Zakaria (2020) 23 4.3.Instruction de branchement (SAUT): Cette instruction permet de sauter à un endroit précis de l’algorithme repéré par une étiquette. Syntaxe générale : ALLER A <étiquette> SMAHI Zakaria (2020) 24 4.3.Instruction de branchement (SAUT): Exemple: Algo Exemple; Var x : Entier; Début Lire (x); Aller à 1; x <- x + 1; 1: x <- x +2; Ecrire(x); Fin. SMAHI Zakaria (2020) 25 4.4.1. Instruction de CHOIX Rôle : permet d’exécuter une séquence d’instructions plutôt qu’une autre selon les conséquences. On distingue quatre formes de structures de choix (alternative): 4.4.Les structures Conditionnelles uploads/Management/ cours-algo-smahi.pdf