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 SMIA, module M5 E2 M. El Marraki 1 31/03/2013 Algorithmique Par P

Algorithmique SMIA, module M5 E2 M. El Marraki 1 31/03/2013 Algorithmique Par Pr. Mohamed El Marraki marraki@fsr.ac.ma 2012/2013 Université Mohammed V-Agdal Faculté des Sciences – Rabat Département d’Informatique Le module M5 E2 : SMIA Algorithmique SMIA, module M5 E2 M. El Marraki 2 31/03/2013 Sommaire 1. Généralités sur l’Algorithmique Introduction L’algorithmique Principe Les caractéristiques d’un Algorithme Analyse descendante L’algorithmique et la programmation Le but de la programmation Langages de programmation Pseudo langage 2. Les variables Déclaration des variables Noms de variables Types de variables 3. Les Primitives Affectation Définition et notation Utilisations Lire et écrire Données et résultats Les objets manipulés par l’algorithme Les tests si .. alors .., si .. alors .. sinon .. Conditions composées Organigramme Tests imbriqués Les Boucles La boucle TantQue La boucle Répéter … jusqu’à … La boucle Pour … jusqu’à … Les boucles imbriquées Une méthodologie pour l'écriture d'une boucle 4. Les structures de données statiques Tableaux à une dimension Introduction Notation et utilisation algorithmique Types pour les tableaux Quelques algorithmes utilisant les tableaux à une dimension Tableaux à deux dimensions Notation et définitions Algorithmes sur les matrices 5. Exercices et Problèmes d’examens Algorithmique SMIA, module M5 E2 M. El Marraki 3 31/03/2013 1. Généralités sur l’Algorithmique 1.1 Introduction L’algorithmique est un terme d’origine arabe, hommage à Al Khawarizmi (780-850) auteur d’un ouvrage décrivant des méthodes de calculs algébriques. Un algorithme est une méthode de résolution de problème énoncée sous la forme d'une série d'opérations à effectuer. La mise en œuvre de l'algorithme consiste en l'écriture de ces opérations dans un langage de programmation et constitue alors la brique de base d'un programme informatique. 1 Une recette de cuisine est un algorithme! 2 Le mode d’emploi d’un magnétoscope est aussi un algorithme! 3 Indiqué un chemin à un touriste égaré ou faire chercher un objet à quelqu’un par téléphone c’est fabriquer - et faire exécuter - des algorithmes. Un algorithme, c’est une suite d’instructions, qui une fois exécutée correctement, conduit à un résultat donné. 1 Si l’algorithme est juste, le résultat est le résultat voulu, et le touriste se retrouve là où il voulait aller. 2 Si l’algorithme est faux, le résultat est, disons, aléatoire, et décidément, ce magnétoscope ne marche pas! Pour fonctionner, un algorithme doit donc contenir uniquement des instructions compréhensibles par celui qui devra l’exécuter (l’ordinateur). L’ADN, qui est en quelque sorte le programme génétique, l’algorithme à la base de construction des êtres vivants, est une chaîne construite à partir de quatre éléments invariables. Ce n’est que le nombre de ces éléments, et l’ordre dans lequel ils sont arrangés, qui vont déterminer si on obtient une puce ou un éléphant. Les ordinateurs eux-mêmes ne sont fondamentalement capables d’exécuter que quatre opérations logiques : 1 l’affectation de variables 2 la lecture / écriture 3 les tests 4 les boucles Un algorithme informatique se ramène donc toujours au bout du compte à la combinaison de ces quatre petites briques de base. Il peut y en avoir quelques unes, quelques dizaines, et jusqu’à plusieurs centaines de milliers dans certains programmes. La taille d’un algorithme ne conditionne pas en soi sa complexité : de longs algorithmes peuvent être finalement assez simples, et de petits algorithmes peuvent être très compliqués. L’informatique est la science du traitement automatique de l’information. Pour cela il faut: 1 modéliser cette information, 2 définir à l’aide d’un formalisme strict les traitements dont elle fera l’objet. 3 et enfin traduire ces traitements dans un langage compréhensible par un ordinateur. Les deux premiers points concernent l’algorithmique, alors que le dernier point relève de ce que l’on nomme la programmation. Algorithmique SMIA, module M5 E2 M. El Marraki 4 31/03/2013 L’écriture d’un programme consiste généralement à implanter une méthode de résolution déjà connue et souvent conçue indépendamment d’une machine pour fonctionner aussi bien sur toutes les machines ou presque. Ainsi, ce n’est pas le programme mais la méthode qu’il faut étudier pour comprendre comment traiter le problème. Le terme algorithme est employé en informatique pour décrire une méthode de résolution de problème programmable sur machine. Les algorithmes sont la « matière » de l’informatique et sont l’un des centres d’intérêt de la plupart, sinon la totalité, des domaines de cette science. 1.2 L’algorithmique Principe Définition : Un algorithme est une séquence bien définie d’opérations (calcul, manipulation de données, etc.) permettant d’accomplir une tache en un nombre fini de pas. En principe un algorithme est indépendant de toute implantation. Cependant dans la pratique de la programmation il s’avère indispensable de tenir compte des capacités du langage de programmation utilisé. La conception d’un algorithme passe par plusieurs étapes : Analyse : définition du problème en terme de séquences d’opérations de calcul de stockage de données, etc. ; Conception : définition précise des données, des traitements et de leur séquencement ; Implantation : traduction et réalisation de l’algorithme dans un langage précis ; Test : Vérification du bon fonctionnement de l’algorithme. Remarque : Les programmes sont souvent sur-optimisés. Il n’est pas toujours indispensable de se donner la peine de trouver l’implantation la plus efficace d’un algorithme, à mois que ce dernier ne soit susceptible d’être utilisé pour une tâche très répétitive. Dans les autres cas, une mise en œuvre simple conviendra souvent : on pourra être sûr que le programme fonctionnera, peut-être cinq ou dix fois moins vite que la version la plus optimisée, ce qui se traduira éventuellement par quelques secondes supplémentaires à l’exécution. En revanche, un mauvais choix d’algorithme peut entraîner une différence d’un facteur cent, mille ou plus, ce qui se traduira en minutes, en heures voir en jours au niveau des temps d’exécution. Les caractéristiques d’un Algorithme Un algorithme est une marche à suivre : 1 dont les opérations sont toutes définies et portent sur des objets appelés informations, 2 dont l’ordre d’exécution des opérations est défini sans ambiguïté, 3 qui est réputée résoudre de manière certaine un problème ou une classe de problèmes, 4 s’exprime dans un langage indépendant des langages de programmation, 1.3 L’algorithmique et la programmation Un programme est la traduction d’un algorithme dans un certain langage de programmation. Il faut savoir qu’à chaque instruction d’un programme correspond une action du processeur. Algorithmique SMIA, module M5 E2 M. El Marraki 5 31/03/2013 1.3.1 Le but de la programmation : • Utiliser l’ordinateur pour traiter des données afin d’obtenir des résultats. • Abstraction par rapport au matériel (indépendance application / plate forme matérielle). • Intermédiaire entre le langage machine (binaire) et le langage humain 1.3.2 Langages de programmation Le langage utilisé par le processeur, est appelé langage machine. Il s'agit d'une suite de 0 et de 1 (du binaire). Toutefois le langage machine est difficilement compréhensible par l'humain. Ainsi il est plus pratique de trouver un langage intermédiaire, compréhensible par l'homme, qui sera ensuite transformé en langage machine pour être exploitable par le processeur. L'assembleur est le premier langage informatique qui ait été utilisé. Celui-ci est encore très proche du langage machine mais il permet déjà d'être plus compréhensible. Toutefois un tel langage est tellement proche du langage machine qu'il dépend étroitement du type de processeur utilisé (chaque type de processeur peut avoir son propre langage machine). Ainsi un programme développé pour une machine ne pourra pas être porté sur un autre type de machine (on désigne par le terme "portable" un programme qui peut être utilisé sur un grand nombre de machines). Pour pouvoir l'utiliser sur une autre machine il faudra alors parfois réécrire entièrement le programme! Il y a trois catégories de langage de programmations : les langages interprétés et les langages intermédiaires et les langages compilés. Langage interprété Un langage de programmation est par définition différent du langage machine. Il faut donc le traduire pour le rendre intelligible du point de vue du processeur. Un programme écrit dans un langage interprété a besoin d'un programme auxiliaire (l'interpréteur) pour traduire au fur et à mesure les instructions du programme. Exemples de langages interprétés : Le langage HTML (les pages web), le langage Maple (calcul mathématique), Prolog (Intelligence artificielle), etc. Langage compilé : Un programme écrit dans un langage dit "compilé" va être traduit une fois pour toutes par un programme annexe (le compilateur) afin de générer un nouveau fichier qui sera autonome, c'est- à-dire qui n'aura plus besoin d'un programme autre que lui pour s'exécuter (on dit d'ailleurs que ce fichier est exécutable). Un programme écrit dans un langage compilé a comme avantage de ne plus avoir besoin, une fois compilé, de programme annexe pour s'exécuter. De plus, la traduction étant faite une fois pour toute, il est plus rapide à l'exécution. Toutefois il est moins souple qu'un programme écrit avec un langage interprété car à chaque modification du fichier source il faudra recompiler le programme pour que les modifications prennent effet. D'autre part, un programme compilé a pour avantage de garantir la sécurité du code source. En effet, un langage interprété, étant directement intelligible (lisible), permet à n'importe qui de connaître les secrets de fabrication d'un programme et donc de copier le code voire de le Algorithmique SMIA, uploads/Industriel/ poly-algo-2013-ch1-4-5-pdf.pdf