Points clés
1. La conception d’algorithmes : un prisme puissant
Le véritable enjeu réside dans le fait que le sujet des algorithmes offre un prisme puissant pour appréhender l’ensemble du domaine de l’informatique.
La tâche essentielle. Concevoir un algorithme, c’est à la fois un art et une science visant à résoudre efficacement des problèmes computationnels. Cette démarche repose sur deux étapes fondamentales : d’abord, extraire des détails complexes d’un problème concret une formulation mathématique claire et précise ; ensuite, identifier les techniques algorithmiques adaptées pour résoudre cette formulation. Ce processus est itératif : la connaissance des techniques disponibles facilite une meilleure formalisation des problèmes.
Des idées omniprésentes. La pensée algorithmique dépasse largement le cadre traditionnel de l’informatique. Qu’il s’agisse des débats sur le routage Internet, de la comparaison de séquences biologiques, de la modélisation financière ou de la gestion du personnel hospitalier, les concepts algorithmiques fournissent un langage pour exprimer les questions sous-jacentes et leurs contraintes. Saisir ces schémas permet d’appliquer des solutions computationnelles à une multitude de défis.
Un processus de conception. Élaborer des algorithmes sophistiqués implique souvent d’explorer plusieurs pistes, y compris des idées initiales qui peuvent échouer. Comprendre pourquoi des méthodes plus simples, comme les heuristiques gloutonnes, ne fonctionnent pas toujours révèle des structures essentielles du problème. Ce processus itératif de formulation, conception, analyse et amélioration est au cœur du domaine.
2. Analyser l’efficacité : la puissance du temps polynomial
La définition mathématique du temps polynomial s’est révélée correspondre de manière étonnamment fidèle, dans la pratique, à ce que nous observons quant à l’efficacité des algorithmes et à la tractabilité des problèmes dans la vie réelle.
Quantifier l’efficacité. Pour dépasser les notions subjectives de « rapidité d’exécution », il est nécessaire de disposer d’une définition concrète et indépendante de la plateforme. Analyser un algorithme revient à comprendre comment ses besoins en ressources, principalement en temps et en mémoire, évoluent lorsque la taille des données d’entrée augmente. Ce comportement d’évolution est décrit par des fonctions mathématiques.
Polynomial versus exponentiel. Une distinction cruciale s’opère entre les temps d’exécution polynomiaux et exponentiels. Un algorithme est dit polynomial si, dans le pire des cas, son temps d’exécution pour une entrée de taille n est borné par c × n^d, où c et d sont des constantes. Les algorithmes exponentiels, dont le temps est borné par r^n avec r > 1, croissent beaucoup plus rapidement. L’écart entre ces deux classes est immense, faisant du temps polynomial un indicateur fort de la faisabilité pratique.
Notation asymptotique. Nous utilisons les notations O(), Ω() et Θ() pour exprimer le taux de croissance des fonctions, en négligeant les constantes et les termes de moindre importance, afin de mieux comparer les comportements à grande échelle.
Résumé des avis
Algorithm Design reçoit des critiques majoritairement positives, salué pour sa clarté, ses explications intuitives et son accent mis sur la compréhension plutôt que la mémorisation. Les lecteurs apprécient sa couverture approfondie des sujets avancés ainsi que ses applications concrètes à la résolution de problèmes réels. Nombre d’entre eux le jugent supérieur à CLRS pour l’apprentissage, bien qu’il soit moins exhaustif en tant qu’ouvrage de référence. L’approche adoptée pour expliquer des concepts complexes, les exercices résolus et la diversité des problèmes proposés, aux niveaux de difficulté variés, sont particulièrement mises en avant. Quelques reproches concernent une notation parfois trop verbeuse et une couverture limitée de certains thèmes, mais dans l’ensemble, ce livre est vivement recommandé pour l’étude des algorithmes au niveau master.
