Préface
Nous proposons dans ce livre une introduction complète à l’étude contemporaine des algorithmes informatiques. De nombreux algorithmes y sont présentés et étudiés en détail, de façon à rendre leur conception et leur analyse accessibles à tous les niveaux de lecture. Nous avons essayé de maintenir la simplicité des explications, sans sacrifier ni la profondeur de l’étude, ni la rigueur mathématique.
Chaque chapitre présente un algorithme, une technique de conception, un domaine d’application, ou un sujet s’y rapportant. Les algorithmes sont décrits en français et dans un « pseudo-code » conçu pour être lisible par quiconque ayant déjà un peu programmé. Le livre contient plus de 230 figures qui illustrent le fonctionnement des algorithmes. Comme nous mettons l’accent sur l’efficacité comme critère de conception, les temps d’exécution de tous nos algorithmes sont soigneusement analysés.
Ce texte est en premier lieu un support du cours d’algorithmique ou de structures de données de deuxième ou troisième cycle universitaire. Il est également bien adapté à la formation personnelle des techniciens professionnels, puisqu’il s’intéresse aux problèmes d’ingénierie ayant trait à la conception d’algorithmes, ainsi qu’à leurs aspects mathématiques.
Dans cette édition, qui est la seconde, nous avons modifié l’ensemble du livre. Les changements vont de la simple refonte de phrases individuelles jusqu’à l’ajout de nouveaux chapitres.
a) Pour l’enseignant
Ce livre se veut à la fois complet et polyvalent. Il se révélera utile pour toute sorte de cours, depuis un cours de structures de données en deuxième cycle jusqu’à un cours d’algorithmique en troisième cycle. Un cours trimestriel étant beaucoup trop court pour aborder tous les sujets étudiés ici, on peut voir ce livre comme un « buffet garni »
où vous pourrez choisir le matériel le mieux adapté aux cours que vous souhaitez enseigner.
Vous trouverez commode d’organiser votre cours autour des chapitres dont vous avez vraiment besoin. Nous avons fait en sorte que les chapitres soient relativement indépendants, de manière à éviter toute subordination inattendue ou superflue d’un chapitre à l’autre. Chaque chapitre commence en présentant des notions simples et se poursuit avec les notions plus difficiles, le découpage en sections créant des points de passage naturels. Dans un cours de deuxième cycle, on pourra ne faire appel qu’aux premières sections d’un chapitre donné ; en troisième cycle, on pourra considérer le chapitre entier.
Nous avons inclus plus de 920 exercices et plus de 140 problèmes. Chaque section se termine par des exercices et chaque chapitre se termine par des problèmes. Les exercices sont généralement des questions courtes de contrôle des connaissances.
Certains servent surtout à tester la compréhension du sujet ; d’autres, plus substantiels, sont plutôt du genre devoir à la maison. Les problèmes sont des études de cas plus élaborées qui introduisent souvent de nouvelles notions ; ils sont composés le plus souvent de plusieurs questions qui guident l’étudiant à travers les étapes nécessaires pour parvenir à une solution.
Les sections et exercices munis d’une astérisque (*) recouvrent des thèmes destinés plutôt aux étudiants de troisième cycle. Un passage étoilé n’est pas forcément plus ardu qu’un passage non étoilé, mais il risque d’exiger des connaissances mathématiques plus pointues. De même, un exercice étoilé risque de demander un niveau théorique plus important ou d’incorporer des subtilités au-dessus de la moyenne.
b) Pour l’étudiant
Nous espérons que ce livre vous fournira une introduction agréable à l’algorithmique.
Nous avons essayé de rendre chaque algorithme accessible et intéressant. Pour vous aider lorsque vous rencontrez des algorithmes peu familiers ou difficiles, nous les avons tous décrits étape par étape. Nous expliquons aussi avec soin les notions mathématiques nécessaires pour comprendre l’analyse des algorithmes. Si vous êtes déjà familiarisé avec un sujet, vous constaterez que l’organisation des chapitres vous permet de sauter les sections d’introduction et d’aller rapidement aux concepts plus avancés...............