Conception d'algorithmes. Principes et 150 exercices corrigés, 2e édition

Résumé : La conception des algorithmes : une science ! L'algorithmique est l'art et la science de concevoir des algorithmes corrects et efficaces. Pour beaucoup d'informaticiens, c'est l'aspect artistique qui prédomine : on cherche l'idée lumineuse, la structure cachée, la réponse astucieuse. Mais la conception des algorithmes est d'abord une science dont il faut posséder les bases et les techniques avant d'exprimer sa créativité. Ce livre invite le lecteur à une approche rigoureuse de la construction d'algorithmes. Il explique comment la même idée peut se retrouver dans plusieurs algorithmes correspondant à des problèmes différents. Il donne les outils pour analyser rationnellement un problème, le classer dans une famille de méthodes et produire une solution exacte. Un manuel de référence sur la construction raisonnée des algorithmes Dans chaque chapitre de ce livre, les bases théoriques et techniques sont rappelées et illustrées par des exemples. On y trouve ensuite un grand nombre d'exercices, accompagnés d'une correction minutieuse et complète. De la sorte, on y voit comment une démarche rationnelle permet d'atteindre une solution, exacte par construction, à travers une grande variété de cas. Après des rappels sur le raisonnement, les structures de données et la complexité, le livre parcourt les grandes méthodes de construction d'algorithmes : invariants, récursivité, essais successifs, méthodes PSEP, algorithmes gloutons, diviser pour régner, programmation dynamique. Au total, près de 150 exemples d'algorithmes sont ainsi analysés et construits rigoureusement. A qui s'adresse ce livre ? Aux étudiants et enseignants en science informatique Aux ingénieurs, enseignants-chercheurs, informaticiens et industriels.

Les bases de données classiques stockent un grand nombre d'informations précises permettant de traiter des requêtes de type booléen. Ces systèmes trouvent leurs limites lorsqu'il s'agit de prendre en compte des préférences dans les requêtes ou quand certaines données stockées sont imparfaitement connues. Pour traiter ces deux problèmes et définir des systèmes autorisant des requêtes graduelles ou permettant de manipuler des données imprécises, les auteurs de l'ouvrage s'appuient sur la théorie des ensembles flous. Le livre débute par des rappels sur les bases de données relationnelles et les bases orientées objets, suivis d'une présentation des ensembles flous. Sur ces bases est alors développée la thématique de l'interrogation flexible dans le cadre des bases relationnelles, puis dans celui des bases à objet. Puis est présentée la théorie des possibilités, pour représenter divers types de données imprécises. Enfin est traitée l'interrogation de bases de données dont certaines valeurs sont mal connues. Des exercices corrigés complètent l'exposé et permettent au lecteur de l'approfondir. Biographie de l'auteur Patrick Bosc, Professeur d'informatique à l'ENSSAT (Ecole nationale supérieure de sciences appliquées et de technologie) à Lannion, dirige le projet de recherche Badins de l'IRISA (Institut de recherches en informatique et systèmes aléatoires). Ludovic Liétard, Maître de conférences à l'IUT de Lannion, Olivier Pivert et Daniel Rocacher, Maîtres de conférences à l'ENSSAT, sont tous trois membres de ce projet.

La conception des algorithmes : une science ! L'algorithmique est l'art et la science de concevoir des algorithmes corrects et efficaces. Pour beaucoup d'informaticiens, c'est l'aspect artistique qui prédomine : on cherche l'idée lumineuse, la structure cachée, la réponse astucieuse. Mais la conception des algorithmes est d'abord une science dont il faut posséder les bases et les techniques avant d'exprimer sa créativité. Ce livre invite le lecteur à une approche rigoureuse de la construction d'algorithmes. Il explique comment la même idée peut se retrouver dans plusieurs algorithmes correspondant à des problèmes différents. Il donne les outils pour analyser rationnellement un problème, le classer dans une famille de méthodes et produire une solution exacte. Un manuel de référence sur la construction raisonnée des algorithmes Dans chaque chapitre de ce livre, les bases théoriques et techniques sont rappelées et illustrées par des exemples. On y trouve ensuite un grand nombre d'exercices, accompagnés d'une correction minutieuse et complète. De la sorte, on y voit comment une démarche rationnelle permet d'atteindre une solution, exacte par construction, à travers une grande variété de cas. Après des rappels sur le raisonnement, les structures de données et la complexité, le livre parcourt les grandes méthodes de construction d'algorithmes : invariants, récursivité, essais successifs, méthodes PSEP, algorithmes gloutons, diviser pour régner, programmation dynamique. Au total, près de 150 exemples d'algorithmes sont ainsi analysés et construits rigoureusement. Cet ouvrage, pour sa troisième édition, a été entièrement revu et corrigé. Nombre d'exercices ont été remaniés, certains assez largement, en visant une meilleure gradation des difficultés et une argumentation plus complète. La 1re édition de Conception d'algorithmes a été finaliste du prix Roberval 2017. A qui s'adresse ce livre ? - Aux étudiants et enseignants en science informatique - Aux ingénieurs, enseignants-chercheurs, informaticiens et industriels