Résumé indisponible
Ce livre ne se prête pas à un résumé (il peut s’agir d’un manuel scolaire, d’un cahier d’exercices, d’un livre de cuisine, d’un ouvrage de référence ou d’un recueil). Vous pouvez toutefois consulter la FAQ, les informations sur l’auteur et d’autres métadonnées ci-dessous !
Points clés
1. Les algorithmes : les héros méconnus de l’informatique
Aujourd’hui, avec l’avènement des ordinateurs, les algorithmes sont plus nombreux que jamais et constituent le cœur même de l’informatique.
Les algorithmes sont essentiels. Bien avant l’existence des ordinateurs, les algorithmes formaient déjà la base de la résolution de problèmes. Désormais, avec la multiplication des machines, ils jouent un rôle encore plus crucial, incarnant la logique fondamentale derrière chaque calcul. Ce sont des procédures clairement définies qui transforment des données d’entrée en résultats souhaités, devenant ainsi des outils indispensables pour résoudre des problèmes informatiques.
Des applications omniprésentes. Les algorithmes ne sont pas de simples concepts théoriques ; ils sont profondément ancrés dans notre quotidien. Qu’il s’agisse de l’analyse des données du Projet Génome Humain, des protocoles de routage sur Internet ou des moteurs de recherche, ils sont le moteur de nombreuses technologies. Ils sont également indispensables pour sécuriser le commerce électronique via la cryptographie ou optimiser la gestion des ressources en industrie et logistique.
Au-delà du tri. Si le tri est souvent utilisé pour illustrer les notions algorithmiques, la palette des problèmes que les algorithmes peuvent résoudre est bien plus vaste. Ils peuvent déterminer le chemin le plus court sur une carte, identifier des similitudes entre des séquences d’ADN, planifier des tâches, voire calculer les sommets d’une enveloppe convexe. Les possibilités sont infinies.
2. L’importance de l’efficacité : les algorithmes, une technologie clé
La performance globale d’un système dépend autant du choix d’algorithmes efficaces que de celui d’un matériel rapide.
Le matériel ne fait pas tout. Si des processeurs rapides et une mémoire abondante sont importants, l’efficacité de l’algorithme employé peut avoir un impact bien plus déterminant sur les performances. Un algorithme mal conçu peut annuler les avantages du matériel le plus puissant.
Des écarts considérables. L’écart d’efficacité entre différents algorithmes peut être spectaculaire. Par exemple, le tri par insertion, avec sa complexité en temps de « n² », est largement dépassé par le tri fusion, qui s’exécute en « n log n » sur de grands ensembles de données. Cette différence devient d’autant plus marquée que la taille du problème augmente.
Les algorithmes, une véritable technologie. À l’instar du matériel, les algorithmes doivent être considérés comme une technologie à part entière. Investir dans leur développement et leur sélection est aussi crucial que d’investir dans des processeurs plus rapides ou une mémoire plus grande. Un programmeur compétent sait à quel point la maîtrise des algorithmes est essentielle.
3. Le pseudocode : un langage universel pour les algorithmes
La seule exigence est que la spécification fournisse une description précise de la procédure computationnelle à suivre.
La clarté avant le code. Le pseudocode fait le lien entre la compréhension humaine et l’exécution machine. Il permet d’exprimer les algorithmes de manière claire, concise et sans ambiguïté, sans se perdre dans les détails propres à un langage de programmation particulier.
Une liberté d’expression. Contrairement au code réel, le pseudocode autorise l’usage de phrases en anglais, de notations mathématiques et d’autres moyens expressifs pour transmettre l’essence d’un algorithme. L’objectif est de communiquer la logique de l’algorithme de la façon la plus accessible possible.
Concentration sur la logique. Le pseudocode ne s’attarde généralement pas sur les questions d’ingénierie logicielle telles que l’abstraction des données, la modularité ou la gestion des erreurs. Il se concentre uniquement sur la procédure computationnelle, permettant au lecteur de saisir la logique fondamentale de l’algorithme sans distractions inutiles.
4. Le tri par insertion : simplicité et conception incrémentale
Le tri par insertion fonctionne de la même manière que beaucoup de personnes trient une main de cartes à jouer.
Une approche progressive. Le tri par insertion est un algorithme simple qui construit un tableau trié élément par élément. Il parcourt les données d’entrée en insérant chaque élément à sa place correcte dans la portion déjà triée du tableau.
Les invariants de boucle. Les invariants de boucle sont essentiels pour comprendre et démontrer la correction des algorithmes itératifs. Ils définissent une propriété vraie au début de chaque itération, ce qui permet de raisonner sur le comportement de l’algorithme.
La correction. L’invariant de boucle du tri par insertion affirme qu’au début de chaque itération, la sous-partie à gauche de l’élément courant est toujours triée. En prouvant que cet invariant est maintenu tout au long de l’algorithme, on démontre que le tri par insertion trie correctement l’ensemble du tableau à la fin.
5. Le tri fusion : diviser, conquérir et combiner
Le paradigme diviser pour régner implique trois étapes à chaque niveau de récursion.
Diviser pour régner. Le tri fusion illustre parfaitement ce paradigme, en décomposant le problème de tri en sous-problèmes plus petits, en les triant récursivement, puis en fusionnant les sous-problèmes triés pour obtenir le tableau final trié.
La fusion, un élément clé. Le processus de fusion, qui combine deux sous-tableaux triés en un seul tableau trié, est le cœur du tri fusion. Cette étape s’effectue en temps linéaire, en comparant les éléments des deux sous-tableaux et en les plaçant dans le tableau de sortie dans l’ordre.
Les récurrences. Le temps d’exécution du tri fusion peut être décrit par une équation de récurrence, qui exprime le temps total en fonction du temps nécessaire sur des entrées plus petites. La résolution de cette récurrence montre que le tri fusion a une complexité au pire cas en « n log n ».
6. La notation asymptotique : se concentrer sur la croissance
Ce qui nous intéresse vraiment, c’est le taux de croissance, ou ordre de croissance, du temps d’exécution.
Ignorer les détails. La notation asymptotique simplifie l’analyse des algorithmes en se focalisant sur le taux de croissance de leur temps d’exécution, en négligeant les constantes et les termes de moindre ordre. Cela permet de comparer l’efficacité de différents algorithmes pour de grandes tailles d’entrée.
Theta, Big-O et Omega. Les notations asymptotiques les plus courantes sont :
- La notation Θ : fournit une borne asymptotiquement serrée.
- La notation O : fournit une borne supérieure asymptotique.
- La notation Ω : fournit une borne inférieure asymptotique.
Ordre de croissance. Grâce à ces notations, on peut comparer les algorithmes selon leur ordre de croissance. Un algorithme avec un ordre de croissance plus faible est généralement considéré comme plus efficace pour de grandes entrées, même s’il peut avoir un facteur constant plus élevé pour de petites entrées.
7. Diviser pour régner : un paradigme de conception puissant
De nombreux algorithmes utiles sont récursifs : pour résoudre un problème donné, ils s’appellent eux-mêmes une ou plusieurs fois pour traiter des sous-problèmes étroitement liés.
Résolution récursive de problèmes. Le paradigme diviser pour régner est une technique puissante pour concevoir des algorithmes. Il consiste à décomposer un problème en sous-problèmes plus petits, à les résoudre récursivement, puis à combiner leurs solutions pour résoudre le problème initial.
Trois étapes :
- Diviser : découper le problème en sous-problèmes plus petits.
- Conquérir : résoudre récursivement ces sous-problèmes.
- Combiner : fusionner les solutions des sous-problèmes.
Les récurrences. Les algorithmes diviser pour régner conduisent souvent à des équations de récurrence décrivant leur temps d’exécution. Ces récurrences peuvent être résolues par des méthodes telles que la substitution, les arbres de récursion ou la méthode du maître.
8. Les algorithmes randomisés : accepter l’incertitude
Un algorithme dont le comportement dépend non seulement de son entrée mais aussi des valeurs produites par un générateur de nombres aléatoires est un algorithme randomisé.
Le hasard comme outil. Les algorithmes randomisés utilisent des choix aléatoires durant leur exécution pour améliorer leurs performances ou éviter les pires cas. Ils sont particulièrement utiles lorsque la distribution des entrées est inconnue ou lorsque les algorithmes déterministes sont trop complexes ou inefficaces.
Analyse probabiliste. L’analyse probabiliste permet de déterminer le temps d’exécution attendu d’un algorithme, en prenant l’espérance sur la distribution des choix aléatoires effectués. Cela diffère de l’analyse moyenne, qui porte sur la distribution des entrées.
NP-complétude. Les algorithmes randomisés peuvent imposer une distribution de probabilité sur les entrées, garantissant ainsi qu’aucune entrée particulière ne provoque systématiquement de mauvaises performances, ou encore limiter le taux d’erreur d’algorithmes autorisés à produire des résultats incorrects dans une certaine mesure.
9. Les structures de données : organiser l’information
Une structure de données est une manière de stocker et d’organiser des données afin de faciliter leur accès et leur modification.
Accès efficace. Les structures de données sont fondamentales dans la conception d’algorithmes, offrant des moyens de stocker et d’organiser les données pour permettre un accès et une modification efficaces. Le choix de la structure influence fortement les performances d’un algorithme.
Des compromis. Aucune structure de données n’est idéale pour toutes les situations. Chacune présente des compromis différents entre espace de stockage, temps d’accès et efficacité des opérations.
Exemples. Parmi les structures courantes, on trouve :
- Les piles et files : structures linéaires simples avec des modes d’accès spécifiques.
- Les listes chaînées : structures flexibles permettant des insertions et suppressions efficaces.
- Les tables de hachage : structures offrant un accès rapide en moyenne.
- Les arbres binaires de recherche : structures arborescentes permettant une recherche, insertion et suppression efficaces.
10. La NP-complétude : comprendre l’intractabilité
Si l’on vous demande de produire un algorithme efficace pour un problème NP-complet, vous risquez de passer beaucoup de temps à une recherche vaine.
Des problèmes difficiles. Les problèmes NP-complets forment une classe pour laquelle aucune solution efficace (en temps polynomial) n’est connue. Bien que personne n’ait prouvé qu’une telle solution est impossible, l’absence de résultats malgré des recherches approfondies suggère que ces problèmes sont intrinsèquement complexes.
Réductibilité. La propriété remarquable des problèmes NP-complets est que si un algorithme efficace existe pour l’un d’eux, alors il en existe pour tous. Cette relation rend l’absence de solutions efficaces d’autant plus frustrante.
Approximation. Face à un problème NP-complet, il est souvent plus judicieux de développer un algorithme efficace fournissant une solution satisfaisante, sans forcément être optimale. Ce sont les algorithmes d’approximation.
Dernière mise à jour:
Signaler un problèmeRésumé des avis
Introduction aux algorithmes suscite des avis partagés, bien qu’elle bénéficie d’une appréciation globale élevée. Nombreux sont ceux qui la considèrent comme une référence incontournable en informatique, soulignant la richesse de ses explications et sa rigueur mathématique. Cependant, certains reprochent à cet ouvrage sa complexité, estimant qu’il s’adresse davantage à des lecteurs avancés qu’aux débutants, en insistant trop sur les démonstrations mathématiques au détriment de la mise en pratique. D’autres trouvent le pseudocode difficile à appréhender. Les partisans saluent la profondeur du contenu et la qualité des exercices proposés, tandis que les détracteurs recommandent d’autres ouvrages pour l’apprentissage des algorithmes. Malgré ces critiques, ce livre demeure largement reconnu comme une ressource fondamentale pour les informaticiens et programmeurs désireux d’approfondir leur compréhension des algorithmes et des structures de données.
Les lecteurs ont aussi lu
À propos de l'auteur
Thomas H. Cormen est une figure incontournable dans le domaine de l’enseignement et de la recherche en informatique. Co-auteur du célèbre manuel Introduction to Algorithms, il a largement contribué à l’avancement de la conception et de l’analyse des algorithmes. Professeur titulaire en informatique au Dartmouth College, il a joué un rôle clé dans l’élaboration des programmes d’études et des projets de recherche. Son expertise ne se limite pas aux algorithmes, comme en témoigne sa fonction actuelle de responsable du programme d’écriture du Dartmouth College. Cette responsabilité illustre son engagement à développer les compétences en communication des étudiants, toutes disciplines confondues, conscient de l’importance d’une expression claire tant dans les domaines techniques que non techniques.
Télécharger le PDF
Télécharger l'EPUB
.epub est idéal pour lire des livres numériques sur téléphone, tablette ou liseuse.