Remerciez-le!

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

Ce livre sur l’algorithmique est destiné à toute personne qui s’intéresse au dé

Ce livre sur l’algorithmique est destiné à toute personne qui s’intéresse au développement d’applications informatiques et qui souhaite s’initier ou retrouver les bases fondamentales de la programmation. Il ne s’agit pas ici de programmer avec un langage ou un autre, mais bien de raisonner sur un problème pour concevoir une solution abstraite. Ce travail de réflexion et de conception prépare le stade ultime de l’implémentation et du cycle de vie du programme concret. Le lecteur ne trouvera pas dans ce livre un recueil d’algorithmes qu’il devra ensuite adapter pour résoudre des problèmes mais au contraire une introduction originale et efficace à l’algorithmique pour apprendre à analyser un problème. Le livre est divisé en deux parties. Dans la première partie sont détaillées les notions d’algorithmique de base et la méthode de construction raisonnée d’un algorithme impératif : l’auteur y précise notamment la distinction entre la spécification et la réalisation d’un algorithme et montre que l’algorithmique proprement dite s’arrête là où commence la programmation. Dans la deuxième partie l’auteur propose cette fois des solutions à des problèmes plus élaborés dans divers domaines du calcul automatique, comme la simulation de phénomènes aléatoires ou le cryptage des données. Toutes les activités proposées restent élémentaires avec le souci constant de privilégier le raisonnement qui conduit à l’élaboration des algorithmes. Ce livre numérique a été conçu et est diffusé dans le respect des droits d’auteur. Toutes les marques citées ont été déposées par leur éditeur respectif. La loi du 11 Mars 1957 n’autorisant aux termes des alinéas 2 et 3 de l’article 41, d’une part, que les “copies ou reproductions strictement réservées à l’usage privé du copiste et non destinées à une utilisation collective”, et, d’autre part, que les analyses et les courtes citations dans un but d’exemple et d’illustration, “toute représentation ou reproduction intégrale, ou partielle, faite sans le consentement de l’auteur ou de ses ayants droit ou ayant cause, est illicite” (alinéa 1er de l’article 40). Cette représentation ou reproduction, par quelque procédé que ce soit, constituerait donc une contrefaçon sanctionnée par les articles 425 et suivants du Code Pénal. Copyright Editions ENI Algorithmique Raisonner pour concevoir Christophe HARO Résumé L'auteur Ingénieur et docteur en informatique, Christophe Haro a enseigné l'informatique à l'université et en école d'ingénieurs pendant 22 ans. Depuis près de 10 ans il enseigne le génie logiciel, le développement d'applications informatiques et les architectures logicielles en BTS Informatique de Gestion. C'est toute cette expérience pédagogique qui donne à ce livre son efficacité pour aborder l'algorithmique. - 1 - © ENI Editions - All rigths reserved Qu’estce que l’algorithmique ? On s’intéresse à l’activité de programmation d’un ordinateur qui permet de résoudre des problèmes d’une façon automatique. On se place à un niveau conceptuel dans lequel un problème quelconque, informatique ou non, est caractérisé par un ensemble de données d’entrée et des résultats attendus. On peut donc représenter ce niveau d’analyse par le schéma de la figure cidessous. Exemple On donne les ingrédients suivants : Thym laurier persil ail huile vinaigre sel poivre citron et un brochet de trois livres. Préparer une marinade de brochet. Dans cet exemple, le problème est représenté par les données : le thym, le laurier, ..., le brochet dont on connaît le poids et par le résultat attendu qui est un plat cuisiné : une marinade de brochet. Ce n’est pas (pas encore) un problème qui se pose habituellement en informatique, mais il se pose dans les mêmes termes. Exemple On demande de calculer, pour une année dont on donne le millésime, le jour de la semaine où tombe le premier mai. Ici, les données sont constituées d’un millésime, comme 2005 par exemple. Le résultat attendu est un jour de la semaine, comme dimanche par exemple. Dans ces exemples, le problème est constitué d’un jeu de données. Le résultat attendu doit être obtenu par des transformations à faire subir aux données ; c’est ce que représente la figure cidessus. Les problèmes auxquels on s’intéresse dans ce livre sont résolus à l’aide d’un ordinateur. Un ordinateur est constitué d’une machine matérielle complétée d’un ensemble de composants périphériques, comme un clavier, une souris, une table traçante... La machine matérielle est constituée, en première approximation, d’une unité centrale, chargée d’effectuer les calculs, complétée d’une mémoire, permettant d’enregistrer les données, les résultats des calculs intermédiaires et les résultats attendus. Pour résoudre un problème avec l’aide d’un ordinateur, il faut enregistrer dans sa mémoire, d’une part les données du problème, qu’il devra transformer pour obtenir le résultat attendu et, d’autre part, la suite des instructions que l’unité centrale du calculateur devra exécuter pour effectuer les transformations des données. Le résultat étant obtenu, il sera d’abord enregistré, comme les données, dans la mémoire. La figure suivante représente ces éléments. - 1 - © ENI Editions - All rigths reserved Un périphérique d’entrée permet de communiquer au programme les données à transformer. Un programme, constitué d’instructions en langage machine exécutées par l’unité centrale, les transforme et produit des résultats qui sont envoyés au périphérique de sortie. Un premier élément, remarquable ici, est l’architecture mise en œuvre. Les instructions machine exécutées par l’unité centrale et les données sur lesquelles elles agissent sont rangées et cohabitent dans la même mémoire centrale. Une telle architecture est celle des ordinateurs depuis leur tout début, dans la première moitié du vingtième siècle. Elle a été inventée et théorisée par John VON NEUMANN et Alan THÜRING. Dans cette architecture, l’unité centrale n’exécute qu’une seule instruction à la fois et ces instructions sont exécutées séquentiellement, l’une après l’autre, dans un ordre préétabli et définitivement fixé. On dit qu’il s’agit d’une machine séquentielle pour caractériser un tel comportement. Il existe d’autres types de machines qui ne nous intéressent pas dans ce livre. Une deuxième propriété importante de telles machines est que les mêmes données, communiquées au même programme, produisent les mêmes résultats, indépendamment de l’environnement et du moment de l’exécution des instructions. On dit alors que ce type de machine est déterministe. Là encore, ce n’est pas la seule architecture matérielle possible, mais ce livre se restreint à ce cas. Pour obtenir un programme et les instructions qui le composent, on le prépare en utilisant un langage de programmation à l’aide duquel on écrit les instructions qui transforment les données. Il existe de nombreux langages de programmation de haut niveau, certains dédiés à des tâches spécifiques, comme les tableurs par exemple, d’autres destinés à écrire des programmes plus généraux, comme JAVA, PHP, C... La figure cidessous représente les relations entre un programme de haut niveau et le calculateur auquel il est destiné. - 2 - © ENI Editions - All rigths reserved Pour passer des données d’un problème aux résultats attendus, on considère une machine fictive caractérisée par un comportement qui lui permet de réaliser les opérations. Cette machine fictive, comme son modèle, l’ordinateur de VON NEUMANN, n’effectue qu’une seule opération à la fois pour réaliser un traitement précisément défini. Les opérations s’organisent en une suite ordonnées d’instructions qui opèrent sur de l’information symbolique, c’estàdire sur une suite de signes alphabétiques, numériques, lexicaux. Cette machine fictive est donc une machine séquentielle, comme son modèle. On appelle calcul une suite de traitements réalisés par cette machine, machine abstraite le calculateur fictif et programme abstrait la suite d’instructions préparées pour une telle machine. Cependant, alors que les programmes écrits dans un langage de programmation et destinés à un calculateur concret doivent respecter une syntaxe précise et rigide, les programmes abstraits ne sont contraints par aucune règle de « grammaire », aucune syntaxe imposée. En ce sens, un programme abstrait n’est pas un programme et n’utilise pas un langage différent du langage naturel. On appelle algorithme un programme écrit pour la machine abstraite. La figure cidessous représente les relations entre la machine abstraite et son modèle, le calculateur concret. - 3 - © ENI Editions - All rigths reserved Tout ordinateur et son langage sont donc la réalisation particulière d’une machine abstraite. Cependant, alors que le programme concret, destiné à un calculateur concret, appartient à l’espace de la solution du problème que nous voulons résoudre, la machine abstraite et son langage, l’algorithme, appartiennent à l’espace du problème à résoudre. La figure cidessus montre les différents espaces d’intervention. L’algorithme est le « langage » de la machine fictive. On y reconnaît deux domaines indépendants et bien distincts : G la spécification du problème qui le définit entièrement et d’une façon non ambiguë. C’est le domaine des Mathématiques et de la logique. G Les instructions de la machine fictive est un domaine qui assure la transition vers les instructions en langage de haut niveau destinées à la machine effective. Dans l’espace de la solution, le langage de haut niveau et le langage machine réalisent les instructions de la machine effective. Pour être plus précis, il faudrait considérer que le langage de haut niveau introduit une machine fictive intermédiaire, mais cela ne sera pas fait ici pour simplifier. - 4 - © ENI Editions - All rigths reserved Structure du uploads/Industriel/ algorithmique-raisonner-pour-concevoir.pdf