Remerciez-le!

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

Algorithmique et Structures de Données - L’algorithmique est un terme d’origine

Algorithmique et Structures de Données - L’algorithmique est un terme d’origine arabe. L’algorithmique L’algorithmique - Le mot « algorithme » vient du nom du grand mathématicien persan Al Khawarizmi, qui introduisit en Occident la numération décimale.  Qu’est – ce qu’un algorithme  Algorithmes et programmation  Formaliser un algorithme  Langages de programmation (langage C) L’algorithmique L’algorithmique  Complexité des algorithmes Un algorithme est un ensemble de règles logiques et chronologiques qu‟on doit suivre pour aboutir à la résolution d‟un problème particulier. Ces règles sont constituées d‟un nombre fini d’opérations élémentaires. Les algorithmes Les algorithmes o Les opérations élémentaires (+, -, *, /, \) et (AND, OR, NON). Ces opérations seront exécutées dans un ordre bien déterminé. Un algorithme peut être assimilé à un raisonnement que l‟on peut traduire avec un langage que toute personne peut comprendre : o LDA : Langage de Description d‟Algorithme Les algorithmes Le LDA n‟est pas un langage informatique. Le programme informatique est à la traduction du LDA à un autre langage compréhensible pour la machine (Pascal, Visual Basic, C, C++, C#, Java…) L’algorithmique et la programmation LDA …… …… …… Langage traduisant la pensée de manière compréhensible pour toute personne : Algorithme Langage traduisant le LDA de manière compréhensible pour l‟ordinateur : Programme Raisonnement logique et chronologique Programme C, C++,… Qu’est – ce qu’un algorithme ? Une suite d’instructions, qui une fois exécutée correctement, conduit à un résultat donné ► Ouvrir un livre de recettes de cuisine, ► Indiquer un chemin à un touriste égaré. ► chercher un mot dans le dictionnaire… ► Résoudre une équation de second degré Qu’est – ce qu’un algorithme ? Pour fonctionner, un algorithme doit donc contenir uniquement des instructions compréhensibles par celui qui devra l’exécuter. En informatique les choses auxquelles ont doit donner des instructions sont les ordinateurs et donc on utilise les langages informatiques (Pascal, Visual basic, C, C++, ….etc) pour leur décrire ces instructions. Pour quoi apprendre l’algorithmique ? Par ce que l’algorithmique exprime les instructions résolvant un problème donné indépendamment des particularités de tel ou tel langage. Apprendre l’algorithmique, c’est apprendre à manier la structure logique d’un programme informatique. Exemple 1. résoudre une équation de 1er degré Résoudre l’équation ax+b = 0 Ecrire un plan d’un algorithme permettant le calcul de la valeur de x. Retenir (saisir, lire) la valeur de a. Retenir (saisir, lire) la valeur de b. Si a est égal à zéro il y aura pas de solution. Sinon la valeur de x est obtenue en divisant -b par a. Afficher la valeur de x Fin algorithme Début algorithme Entrées Traitement Sortie Exemple 1. résoudre une équation de 1er degré Exemple 1. résoudre une équation de 1er degré Exemple 3: Plan de l’algorithme Recherche d'un mot dans un dictionnaire Méthode 1 : Recherche séquentielle a. Début algorithme. b. Retenir (saisir, lire) le mot à rechercher. c. Ouvrir le dictionnaire à la première page. d. Tant que le mot ne se trouve pas sur la page courante et la page courante n'est pas la dernière exécuter l'étape e) sinon passer à l'étape f). e. Passer à la page suivante. f. Si le mot s'y trouve lire la définition sinon ce mot ne se trouve pas dans le dictionnaire. g. Fin de l'algorithme. Exemple 1. Recherche d’un mot dans un dictionnaire Exemple 1. Recherche d’un mot dans un dictionnaire Exemple 3: Plan de l’algorithme Recherche d'un mot dans un dictionnaire Exercice : la méthode de recherche séquentielle est-elle optimale ? Donner un plan d‟algorithme d‟une autre méthode de recherche plus rapide Exemple 1. Recherche d’un mot dans un dictionnaire Exemple 1. Recherche d’un mot dans un dictionnaire Exemple 3: Plan de l’algorithme Recherche d'un mot dans un dictionnaire a. Début algorithme. b. Retenir (saisir, lire) le mot à rechercher. c. Ouvrir le dictionnaire à la page du milieu. d. Tant que le mot ne se trouve pas sur la page courante et la page courante n'est pas la dernière exécuter l'étape e) et f) sinon passer à l'étape g). e. Si le mot se trouve dans la partie droite ouvre la page du milieu de cette partie f. Sinon ouvre la page du milieu de la partie gauche g. Si le mot s'y trouve lire la définition sinon ce mot ne se trouve pas dans le dictionnaire. h. Fin de l'algorithme. Exemple 1. Recherche d’un mot dans un dictionnaire Exemple 1. Recherche d’un mot dans un dictionnaire Exemples • Conclusion –Plusieurs algorithme peuvent donner le même résultats –Evaluation des algorithmes en fonction du temps d’exécution et de la mémoire utilisée Formaliser un algorithme Deux types de utilisés pour représenter des algorithmes: Représentation graphique = organigramme ► Pseudo - code ► Organigramme – Pseudo - code Lire X; si X>=0 alors Y<-- X sinon Y<-- -X fin si; Afficher Y; *Structure d’un Algorithme algorithme nom de l‟algorithme const liste des constantes var liste des variables struct liste des structures début algorithme action 1 // commentaire 1 action 2 // commentaire 2 . . . action n // commentaire n fin algorithme Déclaration du nom de l‟algorithme Déclaration des constantes, des variables et des structures Le corps de l‟algorithme Nom de l’algorithme : o Il permet tout simplement d‟identifier un algorithme parmi d‟autres. Les déclarations : o C‟est une liste exhaustive de variables utilisées et manipulées dans le corps de l‟algorithme. Le corps de l’algorithme : o Dans cette partie de l‟algorithme, sont placées les tâches à exécuter (instructions, opérations, …). Les commentaires : o Pour permettre une lecture plus aisée et plus compréhensive de l‟algorithme *Structure d’un Algorithme *Structure d’un Algorithme *Les Déclarations Les Constantes : o Elles représentent des chiffres, des nombres, des caractères, des chaînes de caractères, … dont la valeur ne peut pas être modifiée au cours de l‟exécution de l‟algorithme. Les Variables : o Elles peuvent stocker des chiffres des nombres, des caractères, des chaînes de caractères,… dont la valeur peut être modifiée au cours de l‟exécution de l‟algorithme. Les Structures : o Elles permettent de rassembler plusieurs variables ou constantes sous un même identificateur, on parle également d‟entités ou d‟objets. *Les Déclarations des variables et des constantes Les constantes et les variables sont définies dans la partie déclarative par deux caractéristiques essentielles, à savoir : L’ identificateur : o Il représente le nom de la variable, de la constante ou de la structure. Il est composé généralement de lettres mais peut également contenir et de chiffres. Il ne doit pas commencer par des chiffres Il ne doit pas contenir d‟espaces, de caractères de ponctuation ou de caractères accentués. Le type : o Il représente la nature de la variable ou de la constante (entier, réel, booléen, chaîne de caractères…) Exemples : o var age : réel o var adresse, ville : chaine o var nbr_enfants , etage : entier *Les Déclarations des variables et des constantes *Les Déclarations des variables et des constantes De façon générale, pour toute variable censé contenir une ou plusieurs informations devant êtres traitées par le processeur, l‟ordinateur doit lui réserver de la mémoire volatile (RAM). La taille mémoire nécessaire pour stocker cet objet dépend de la nature de l’information en question. Exemple d’informations de base : Les nombres entiers : 0, -1, 45, 36, -10 en décimal 45H, 0FBH, 64H en hexadécimal 10101111, 1011 en binaire Le caractère : ‘a’ , ‘A’ , ’*’ , ’7’ , ’z’ , ’!’ , …. Les nombres réels : -3.67, 4.2569, –564.0, 18.36 10e-6 La chaîne de caractères "électronique", "cd ROM de 80mn" , … Le booléen : Il ne peut prendre que deux états possibles : VRAI ou FAUX (True ou False) *Les types de variables *Les types de variables *Les types de variables en langage C Type de donnée Signification Taille (en octets) Plage de valeurs acceptée char Caractère 1 -128 à 127 unsigned char Caractère non signé 1 0 à 255 short int Entier court 2 -32 768 à 32 767 unsigned short int Entier court non signé 2 0 à 65 535 int Entier 2 (sur processeur 16 bits) 4 (sur processeur 32 bits) -32 768 à 32 767 -2 147 483 648 à 2 147 483 647 unsigned int Entier non signé 2 (sur processeur 16 bits) 4 (sur processeur 32 bits) 0 à 65 535 0 à 4 294 967 295 long int Entier long 4 -2 147 483 648 à 2 147 483 647 unsigned long int Entier long non signé 4 0 à 4 294 967 295 float Flottant (réel) 4 3.4*10-38 à 3.4*1038 double Flottant double 8 1.7*10-308 à 1.7*10308 long double Flottant double long 10 3.4*10-4932 à 3.4*104932 *Déclarations des variables Algorithme (LDA) Langage C Var x, y : entiers int x, y ; Var a, b : réels Float a, b ; Var z1, z2, z3 : caractères Char z1, z2, z3 ; Arithmétique Opérateur Algo C Addition + + Soustraction - - Multiplication * * Division / / Modulo MOD % Division entière \ Puissance ^ Pow() *Les Opérateurs *Les Opérateurs Comparaison Opérateur Algo C uploads/Philosophie/ chap-3-algorithmique 1 .pdf