Cet article vous présente une sélection de 5 des meilleurs livres sur l’algorithmique.
1. Algorithmique – Cours avec 957 exercices et 158 problèmes (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest)
Disponible sur Amazon Disponible à la Fnac
Ce livre de cours traduit de l’américain, sans équivalent et d’accès facile, est une introduction complète à l’algorithmique et s’adresse aussi bien aux étudiants qu’aux professionnels en informatique.
L’éventail des algorithmes étudiés va des plus classiques (tris, hachage…) aux plus récents (algorithmes parallèles…) permettant ainsi de passer progressivement des notions élémentaires aux thèmes les plus pointus.
Les algorithmes sont présentés dans un pseudo-code proche des langages Pascal, C et Fortan, ce qui les rend très faciles à comprendre et à implémenter.
Ils sont complétés par des preuves mathématiques et illustrés par de nombreux exemples. Au total, plus de 920 exercices et 140 problèmes sont proposés.
Cette 3ème édition, révisée et mise à jour, comporte deux nouveaux chapitres, l’un sur les arbres de Van Emde Boas et l’autre sur les algorithmes multithreads. Plusieurs nouveaux énoncés d’exercices et de problèmes ont été ajoutés à cette nouvelle édition.
À propos de l’auteur
Diplomé de Princeton. Professeur au Darmouth College (New Hampshire).
2. Conception d’algorithmes – Principes et 150 exercices corrigés (Marc Guyomard, Patrick Bosc, Laurent Miclet)
Disponible sur Amazon Disponible à la Fnac
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. La nouvelle édition de cet ouvrage est entièrement mise à jour.
À propos de l’auteur
Patrick Bosc était professeur d’informatique à l’Enssat, école d’ingénieurs de l’université de Rennes I située à Lannion, où il a enseigné une vingtaine d’années la plupart des méthodes traitées dans cet ouvrage. Son activité de recherche a concerné la prise en compte de la flexibilité dans les systèmes d’information.
Marc Guyomard était professeur d’informatique à l’Enssat. Il s’est plus particulièrement intéressé à la communication homme-machine et aux méthodes formelles du génie logiciel.
Laurent Millet était professeur d’informatique à l’Enssat, où il a en particulier enseigné l’algorithmique. Son domaine de recherche est l’intelligence artificielle et l’apprentissage automatique.
3. Complexité algorithmique (Sylvain Perifel)
Disponible sur Amazon Disponible à la Fnac
Ce livre présente d’abord les notions de base en théorie de la complexité algorithmique avant de traiter de nombreux sujets avancés. Il s’agit du seul ouvrage en français couvrant un si large spectre dans ce domaine central en informatique théorique.
Les notions mathématiques utiles sont rappelées et aucun prérequis, outre une culture mathématique de base, n’est supposé.
Clair et précis, contenant de nombreux exercices, il s’adresse aux étudiants de mathématiques et d’informatique à partir du L3, aux candidats à l’option informatique de l’agrégation de mathématiques, aux enseignants désirant un ouvrage de référence permettant de donner des cours formels sur le sujet (que ce soit un cours introductif ou sur les sujets très techniques des derniers chapitres), et aux chercheurs souhaitant approfondir le domaine.
La description rigoureuse du modèle de calcul (la machine de Turing) permet d’aborder solidement les bases de la complexité en temps et en espace (théorèmes de hiérarchie, accélération, etc.) et d’étudier le problème P = NP : NP-complétude, théorèmes de Ladner, de Mahaney…
Le non-déterminisme est aussi exploré par les oracles et la hiérarchie polynomiale, ainsi que par les protocoles interactifs qui poursuivent l’étude menée sur les algorithmes probabilistes. Un chapitre est consacré aux classes de comptage avec le théorème de Toda et la complétude du permanent.
Enfin, la problématique du calcul par circuits (non-uniformité) est détaillée, de nombreuses bornes inférieures sont montrées ainsi que les liens profonds avec la dérandomisation.
À propos de l’auteur
Sylvain Perifel est maître de conférences à l’université Paris Diderot. Après une thèse en complexité algébrique, il travaille en complexité notamment sur le calcul de polynômes et sur la puissance de l’aléatoire dans les algorithmes.
4. Algorithmes – Notions de base (Thomas H. Cormen)
Disponible sur Amazon Disponible à la Fnac
Connaître les bases du fonctionnement des algorithmes est essentiel pour tout futur « ingénieur ». Savoir par exemple comment un GPS calcule et optimise un itinéraire en quelques secondes, ou comment une transaction en ligne peut-être cryptée et sécurisée.
Certains livres sur les algorithmes sont très abstraits, d’autres au contraire proposent des trucs et astuces pour programmer. Celui-ci est entre les deux : il a parfois recours aux mathématiques pour expliquer certaines notions, mais elles ont été réduites au strict minimum, et aucune expérience de la programmation n’est requise.
Le but de ce livre est d’expliquer comment fonctionnent les algorithmes et comment on peut les évaluer. Il explique également comment modéliser un problème de façon à ce qu’il puisse être résolu par un ordinateur.
À propos de l’auteur
Diplomé de Princeton. Professeur au Darmouth College (New Hampshire).
5. Algorithmique – Entraînez-vous et améliorez votre pratique de la programmation (Laurent Debrauwer)
Disponible sur Amazon Disponible à la Fnac
Ce livre sur l’algorithmique s’adresse à toute personne qui désire améliorer sa maîtrise d’un langage de programmation et en particulier celle du langage Java.
Il propose de nombreux exercices pratiques de difficulté variable pour compléter sa pratique de la programmation (construction d’index, calcul d’intersection de rectangles, calcul de la distance entre deux mots, simulation d’une course automobile, mini-interprétateur d’expression).
La programmation est introduite d’abord avec les concepts de variables, boucles, tests, tableaux et sous-programmes. La programmation par objets est ensuite abordée de façon très progressive (écriture de petites classes, gestion des chaînes de caractères, petite hiérarchie de classes).
Un chapitre particulier est consacré à la récursivité et les structures de données complexes (listes, arbres, piles) font l’objet du dernier chapitre. Une connaissance des principaux concepts du langage Java est un pré-requis à la lecture de ce livre.
À propos de l’auteur
Laurent Debrauwer est docteur en informatique de l’Université de Lille 1. Auteur de logiciels dans le domaine de la linguistique et de la sémantique, il exerce le métier de consultant indépendant en tant que spécialiste de l’approche par objets.
Il enseigne la modélisation en UML à l’université de Lille 1 et la programmation en Java à l’université du Luxembourg.
