Remerciez-le!

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

division management des systèmes d’information Cours Programmation Edition 2001

division management des systèmes d’information Cours Programmation Edition 2001 Algorithmique et structures de données 1. INTRODUCTION La programmation (but final) a souvent été une activité menée sans méthodes strictes, à grand renfort d'astuces et de recettes personnelles. Cette situation est issue des balbutiements de l'informatique quand les conditions permettaient (ou favorisaient) cet état de choses. Pour tenter de mettre un terme à ce type de situations, un certain nombre de chercheurs (E.W. Dijkstra, N. Wirth, Hoare ...), dès les années 70, se sont efforcés de développer et de propager des méthodes pour discipliner l'analyse, la programmation et l'organisation de projets informatiques. C'est cette méthodologie que l'on désigne sous le terme de programmation structurée. La programmation structurée définit deux types de préoccupations: Disciplines d'analyse et de programmation Définitions d'un nombre restreint de structures dites fondamentales à partir desquelles on peut écrire tout algorithme. Analyse TOP-DOWN : résolution des problèmes par affinages successifs de l'énoncé global jusqu'aux détails. Méthodes systématiques dans l'utilisation des langages traditionnels et de préférence, emploi de langages appropriés. Disciplines d'organisation Définition stricte des rôles des membres d'une équipe de programmation et hiérarchie des équipes. Grand soin apporté à l'écriture et à la mise à jour de la documentation. Modularisation du produit et définitions précises des interfaces. Normes de programmation et normes de présentation des programmes respectées par l'ensemble de l'équipe. Algorithmique et Structures de Données Page 1 /43 2. INTRODUCTION A L’ALGORITHMIQUE L’algorithmique est une science très ancienne. Son nom vient d’un mathématicien arabe du IXème siècle EL KHOWRISMI. Des mathématiciens grecs comme Euclide ou Archimède en ont été les précurseurs (calcul du PGCD de 2 nombres, calcul du nombre π). 2.1. Qu’est-ce qu’un algorithme ? Plusieurs définitions possibles : "spécification d'un schéma de calcul, sous forme d'une suite finie d'opérations élémentaires obéissant à un enchaînement déterminé". "ensemble de règles opératoires dont l'application permet de résoudre un problème donné au moyen d'un nombre fini d'opérations". 2.2. Propriétés d'un algorithme Un algorithme - décrit un traitement sur un nombre fini de données - est la composition d'un nombre fini d'étapes, chaque étape étant formée d'un nombre fini d'opérations dont chacune est définie de façon rigoureuse et non ambiguë, effective, c'est-à-dire pouvant être effectivement réalisée par une machine Quelque soit la donnée sur laquelle il travaille, un algorithme doit toujours se terminer et fournir un résultat. Un algorithme est déterministe; étant donné un algorithme, toute exécution de celui-ci sur les mêmes données donne lieu à la même suite d'opérations et aboutit au même résultat. Il existe une relation étroite entre la notion de programme informatique et celle d'algorithme. Un programme informatique est écrit dans un langage de programmation et s'exécute sur un ordinateur (processeur, mémoire et organes d'Entrées-Sorties). En résumé, un algorithme doit être PRECIS: Il doit indiquer: - l'ordre des étapes qui le constituent - à quel moment il faut cesser une action - à quel moment il faut en commencer une autre - comment choisir entre différentes possibilités DETERMINISTE - Une suite d'exécutions à partir des mêmes données doit produire des résultats identiques. FINI DANS LE TEMPS - c'est-à-dire s'arrêter au bout d'un temps fini. Algorithmique et Structures de Données Page 2 /43 2.3. Place de l'algorithme dans la résolution d'un problème informatique La résolution d'un problème informatique se décompose en quatre phases: - Phase d'étude Inventorier les paramètres connus ou observables et définir les objectifs à réaliser. - Phase de réalisation du modèle Déterminer l'enchaînement des opérations. Cette phase aboutit à l'élaboration d'un schéma de résolution. - Phase de spécification Exprimer le schéma de résolution de manière plus précise en utilisant éventuellement un pseudo-langage. Cette phase débouche sur des algorithmes. - Phase de traduction Mettre en œuvre les algorithmes en les traduisant en un langage de programmation adapté à la machine utilisée. 2.4. Notion de pseudo-langage Aujourd'hui, on dispose d'une grande variété de langages de programmation. Certains langages très connus du grand public sont largement utilisés dans des domaines très divers (PASCAL, C, LISP, ADA, COBOL etc...). On distingue généralement les langages de bas niveau (proches de la machine : Assembleur) et les langages évolués (dits de haut niveau). De tout temps, les chercheurs ont essayé de mettre au point des langages permettant de se détacher le plus possible de la machine sur laquelle les programmes seront exécutés. Certains algorithmes très anciens (Crible d'Erathostène par exemple) ont été décrits en utilisant un langage peu formalisé (proche du langage naturel). D'un autre côté, un algorithme n'a d'intérêt que s'il peut être compris et utilisé par un grand nombre de programmeurs. Il a donc fallu élaborer un langage de description suffisamment formel, pour permettre des implantations dans différents langages de programmation peu fastidieuses, et d'un niveau suffisant pour qu'il soit un outil de communication efficace. Un tel langage s'appelle pseudo-langage. En résumé, l'avantage du pseudo-langage est qu'il permet d'écrire tout algorithme de façon formelle, c'est-à-dire suffisamment précise, tout en restant compréhensible pour l'ensemble des informaticiens. La phase de programmation se trouvera nécessairement allégée, puisqu'elle se résumera à adapter l'ensemble des opérations décrites aux spécificités du langage utilisé. 2.5. Elaboration d'un algorithme. Quatre phases principales: - Analyse du problème - Expression d'une solution en langage courant - Expression d'une solution en pseudo-langage - Tests et Vérification de l'adéquation de la solution Analyse du problème: Algorithmique et Structures de Données Page 3 /43 Bien comprendre l'énoncé du problème: Il est inutile et dangereux de passer à la phase suivante si vous n'avez pas bien discerné le problème. Expression du raisonnement Bien souvent, quelques lignes écrites en langage courant suffisent pour décrire succinctement l'essentiel du problème. L'intérêt de cette étape est qu'elle permet de vérifier rapidement que l'on se trouve sur la bonne voie. De plus, ces quelques lignes seront un support efficace lors de l'écriture de l'algorithme. Expression d'une solution en pseudo-langage Il peut arriver que plusieurs solutions répondent à un problème donné. Il faudra choisir la solution la plus judicieuse et rester cohérent jusqu'au bout. Tests et Vérification de l'adéquation de la solution Vérifier l'exactitude du comportement de l'algorithme, son bon déroulement. Si l'algorithme ne répond pas parfaitement à toutes les requêtes exprimées dans l'énoncé du problème, retournez à la phase n°1. Algorithmique et Structures de Données Page 4 /43 3. OBJETS SIMPLES, TYPES ET ACTIONS ELEMENTAIRES Un algorithme va manipuler des objets au sens informatique. Ces objets pourront être des données qui seront fournies en entrée, des résultats produits par l'algorithme ou des outils nécessaires au bon déroulement de l'algorithme. 3.1. Type d'un objet En mathématiques, lorsque l'on utilise des objets, on précise leur type. Exemples: x R i Z ∈ ∈ x et i appartiennent à des types dont on connaît les propriétés En informatique, les objets manipulés par un algorithme doivent appartenir à un type connu au moment de leur utilisation. Intérêt: documentation vérifications possibles dans les langages de haut niveau lors de certaines opérations Tout objet peut être caractérisé par un type qui indique: les ensembles de valeurs que peut prendre l'objet. les actions autorisées sur cet objet. Les objets simples sont: des nombres (par exemple 3 , 7 , 3.141592 , 1996). des caractères ou des chaînes de caractères (par exemple : 'A' , '45' , 'BONJOUR'). des valeurs booléennes (VRAI , FAUX) On distingue généralement: - les types scalaires qui sont par définition totalement ordonnés - les types structurés qui regroupent sous un même nom une collection d'objets élémentaires qui peuvent être de même type (type homogène) ou de type différents (type hétérogène). Ces types structurés seront vus ultérieurement. En résumé, objet ⇒ donnée ou algorithme algorithme ⇒ procédure ou fonction donnée ⇒ constante ou variable constante ou variable ⇒ type scalaire ou type structuré type structuré ⇒ type homogène ou hétérogène Algorithmique et Structures de Données Page 5 /43 3.2. Les objets. Pour désigner ces différents objets, on utilisera des chaînes de caractères qui seront appelées les identificateurs des objets. Pour différentier un identificateur d'un nombre, un identificateur commence par une lettre et ne comporte pas d'espace. De plus, on essaiera toujours de choisir des noms explicites afin de faciliter la relecture et l'éventuelle maintenance de l'algorithme par un tiers. Un objet peut être : une constante ou une variable s'il s'agit d'une donnée au sens large, une fonction (ou une procédure) s'il s'agit d'un algorithme 3.3. Actions élémentaires Les actions élémentaires sur une donnée dépendent évidemment du type de cette donnée et de sa catégorie (variable ou constante). Type entier: prend ses valeurs dans un sous-ensemble des entiers relatifs. C'est un ensemble fini dans lequel chaque élément possède un successeur et un prédécesseur. Type réel prend ses valeurs dans un sous-ensemble de réels décimaux signés. Dans la plupart des langages, cet ensemble n'est pas un ensemble fini. On ne peut trouver de successeur ou de prédécesseur à un réel donné. Type caractère prend ses valeurs dans l'ensemble des caractères de la table ASCII. Type chaîne de caractère se compose d'une suite de symboles de type caractère Type booléen type logique qui peut prendre les valeurs VRAI ou FAUX. Algorithmique et Structures de uploads/Management/ algo.pdf