Remerciez-le!

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

AVANT-PROPOS C’est en forgeant qu’on devient forgeron... Ce vieil adage, dont l

AVANT-PROPOS C’est en forgeant qu’on devient forgeron... Ce vieil adage, dont les hommes ont usé depuis la nuit des temps, est mis dans cet ouvrage au service des étudiants de licence et de première année de master de mathématiques et d’informatique, des élèves-ingénieurs et de toute autre personne souhaitant goûter les joies et maîtriser les diﬃcultés de l’algorithmique. Au cœur de l’informatique, cette science est celle de la conception de méthodes eﬃcaces pour résoudre des problèmes à l’aide d’un ordinateur. Elle déﬁnit des outils généraux permettant de répondre aux questions suivantes : Sur quelle propriété ma- thématique d’un problème peut-on établir une méthode de résolution ? Étant donné un algorithme, résout-il le problème posé ? Lorsque l’on dispose de deux méthodes de résolution diﬀérentes, laquelle est préférable ? L’algorithmique a donné lieu à de nombreux ouvrages remarquables depuis plus de trente ans, sur lesquels se fondent les enseignements dispensés dans les universités et écoles d’ingénieurs, et dont nous donnons une liste non exhaustive à la ﬁn de cet ouvrage. L’expérience des auteurs, enseignants chevronnés dans diﬀérentes universi- tés, les a depuis longtemps confrontés aux diﬃcultés de leurs étudiants face à cette matière. Celles-ci semblent de plusieurs ordres : • il est nécessaire de pouvoir expérimenter les algorithmes sur diﬀérents exemples pour en comprendre intuitivement le fonctionnement ; • apprendre des éléments de cours implique de pouvoir refaire, au besoin, les dé- monstrations qui y ont été présentées, de les rédiger ; • les algorithmes manipulent des entités qui évoluent dans le temps, et cela ajoute une dimension inhabituelle aux raisonnements mathématiques nécessaires pour les prouver et analyser leurs performances ; • l’apprentissage souvent simultané d’un langage de programmation peut parfois ajouter des diﬃcultés de compréhension dues à la syntaxe propre du langage. C’est pour répondre à ces diﬃcultés que les auteurs ont formé le projet de cet ouvrage, à partir d’exercices progressifs conçus lors de leurs années de pratique, et utilisés dans le cadre de travaux dirigés, d’examens, ou pour des devoirs de plus grande envergure. L’ouvrage a pour objectif d’aider l’étudiant dans son apprentissage de la conception et de l’analyse d’algorithmes en insistant sur le raisonnement et sa rédaction, en vue d’écrire dans le langage de son choix des programmes eﬃcaces. Si la plupart des ouvrages de cours d’algorithmique contiennent des énoncés d’exercices, peu sont corrigés. C’est donc l’une des originalités de ce livre que de © Dunod. La photocopie non autorisée est un délit. VII Retrouver ce titre sur Numilog.com Avant-propos proposer une correction entièrement rédigée, rigoureuse et complète de chaque ques- tion. On y trouvera, pour chaque notion, des exercices visant la compréhension du cours, qui permettent d’appliquer un algorithme connu à des données numériques, ou de redémontrer, à partir d’éléments de base dont les déﬁnitions sont explicitées, les pro- priétés de certains algorithmes du cours décomposées en questions progressives. On y trouvera aussi des exercices qui enrichissent des algorithmes classiques de nouvelles fonctionnalités ou qui permettent de les intégrer dans des applications originales. Concernant la programmation, le parti pris de cet ouvrage est d’employer, pour la rédaction des algorithmes, un pseudo-langage impératif, plutôt qu’un véritable lan- gage de programmation, aﬁn de se concentrer sur ce qui ressort de la conception de l’algorithme, et non sur son implémentation. Ce choix devrait toutefois permettre une implémentation aisée des algorithmes dans des langages comme Pascal, C ou C++, avec sans doute un eﬀort supplémentaire en ce qui concerne les langages objets. Nous indiquons plus loin les conventions d’écriture de ce langage, auxquelles le lecteur pourra se référer pour comprendre, mais aussi pour programmer les algorithmes dans le langage de son choix. L’ouvrage aborde un panel assez vaste de domaines d’application de l’algorith- mique, et devrait couvrir la plupart des cours dispensés actuellement en license et master de mathématiques et informatique et en écoles d’ingénieurs. On y développe notamment, après un chapitre méthodologique qui traite de la preuve et de l’analyse de la complexité d’un algorithme, les types de données abstraits pour représenter, gérer et manipuler des ensembles dynamiques, et leur implémenta- tion à l’aide de structures de données linéaires ou arborescentes (piles, ﬁles, listes, arbres binaires de recherche, arbres équilibrés, tas). On aborde ensuite l’étude des algorithmes de tri. Les chapitres suivants sont consacrés à l’étude de l’algorithmique de base des graphes valués et non valués : connexité, accessibilité, parcours, arbres couvrants et chemins de coût minimum, pour ne citer que les principaux problèmes abordés. Ensuite, deux chapitres consacrés l’un aux algorithmes relatifs à la géomé- trie plane et l’autre aux algorithmes relatifs aux automates et aux mots achèvent cet ouvrage. Dans chaque section, les exercices sont présentés dans un ordre de diﬃculté crois- sante, sauf nécessité de regroupement thématique, et souvent les questions d’un exer- cice respectent une certaine progressivité dans la diﬃculté. D’autres algorithmes auraient mérité de ﬁgurer dans ce livre, plus proches de l’al- gorithmique numérique, ou de la recherche opérationnelle. Avec quelques encoura- gements, les auteurs pourraient envisager une suite... VIII Retrouver ce titre sur Numilog.com Avant-propos Prérequis Le livre nécessite les connaissances de mathématiques du niveau des deux premières années de licence, en particulier une bonne maîtrise du raisonnement par récurrence, ainsi que la connaissance de base d’un langage de programmation. Chacun des cha- pitres demande des prérequis, explicités dans les exercices lorsque cela semble né- cessaire. Il est recommandé de traiter les exercices en ayant d’autre part étudié un cours oral ou un livre de référence. Toutefois, de nombreux exercices peuvent être traités en se référant uniquement aux déﬁnitions et résultats de base rappelés en début de sous-chapitre. Cet en-tête de chapitre n’a pas pour objectif d’être un abrégé de cours. Les déﬁnitions présentées sont loin d’être exhaustives, mais sont celles jugées indis- pensables pour traiter les exercices avec le plus d’autonomie possible. Conventions relatives à la présentation des algorithmes Les algorithmes se présentent sous la forme de segments de code, de fonctions ou de procédures. Les types des paramètres, des fonctions et des variables sont toujours explicités. Par défaut, les passages de paramètres se font par valeur. Un texte accom- pagne l’algorithme lorsqu’un paramètre est modiﬁé, et que le passage doit se faire par référence. Comme dans tous les langages de programmation impératifs, les structures de contrôle suivantes sont employées : • si condition alors instruction sinon instruction ﬁnsi ; • tant que condition faire instruction ﬁntantque ; • répéter instruction jusqu’à condition ﬁnrépéter ; • pour variable de valeur initiale à valeur ﬁnale faire instruction ﬁnpour ; • pour tout élément d’un ensemble faire instruction ﬁnpour. Les tableaux sont indexés par des entiers, et un élément d’indice i d’un tableau T s’écrit T[i], de même les éléments d’un tableau M à deux dimensions se notent M[i, j]. La principale spéciﬁcité du pseudo-langage est le traitement des pointeurs. D’abord, nous nous aﬀranchissons des problèmes liés à l’allocation dynamique de mémoire (les objets manipulés sont supposés alloués). Ensuite, pour ne pas alour- dir la présentation des algorithmes, lorsqu’une variable x désigne un pointeur sur un enregistrement à plusieurs champs, par exemple un enregistrement comportant des champs nommés a et b, alors on notera x.a la variable correspondant au champ a de l’enregistrement pointé par x. La même notation sera employée lorsque x représente l’enregistrement lui-même. Un pointeur qui ne pointe sur aucun enregistrement a la valeur nul. © Dunod. La photocopie non autorisée est un délit. IX Retrouver ce titre sur Numilog.com Avant-propos Conventions relatives à l’index Les entrées de l’index font référence à des notions de base traitées dans l’ouvrage. Lorsqu’une notion fait l’objet d’une déﬁnition explicite, ou d’un exercice qui lui est spéciﬁquement consacré, le numéro de page référencé apparaît en gras. Lorsqu’il s’agit d’un algorithme, le numéro de page apparaît en italique. Remerciements Les auteurs se souviennent avec tendresse du vide de leurs premiers regards qu’une explication miraculeuse a un jour allumé d’une petite ﬂamme. Ils saluent leurs maîtres, qui leur ont inculqué une forme de pensée archaïque consistant à chercher en toute circonstance la maîtrise absolue de la situation, par l’intermédiaire d’une preuve au pire longue et laborieuse, au mieux élégante et belle. Ils arrosent d’une larme émue les bancs des facultés, usés par ceux qui ont, depuis vingt ans, à leur insu, participé à la conception de cet ouvrage. Ils remercient chaleureusement les collègues dont ils ont sans vergogne pillé les archives. Troisième édition La troisième édition introduit dans la plupart des chapitres des exercices nouveaux qui se caractérisent par une plus grande originalité, une plus grande diﬃculté et par leur intérêt pédagogique pour appréhender en profondeur les fondements théoriques des concepts algorithmiques présentés dans le chapitre. X Retrouver ce titre sur Numilog.com PREUVE ET COMPLEXITÉ 1 Un algorithme (O, V, S) est formé d’un ensemble ﬁni O d’opérations liées par une structure de contrôle S et dont les opérandes portent sur un ensemble ﬁni V de va- riables. Un algorithme résout le problème P si pour tout énoncé I de P (stocké dans le sous-ensemble des variables d’entrée de V), d’une part la suite des opérations exé- uploads/Litterature/ exer.pdf