Introduction à l’Algorithmique

Préface à l’édition française
Vous savez compter. Un ordinateur aussi ! Mais connaissez-vous les mécanismes utilisés
? Etes-vous vraiment sûr que le résultat affiché soit juste ? Combien de temps
devrez-vous attendre la fin du calcul ? N’y a-t-il pas un moyen de l’obtenir plus vite ?
Que vous soyez ingénieur, mathématicien, physicien, statisticien et surtout informaticien,
toutes ces questions vous vous les posez. Si vous êtes étudiant, elles surgiront
très rapidement.
Étudier l’algorithmique, c’est apporter des réponses à vos questions.
Cette science est le coeur de l’informatique. Pour tout ceux qui doivent ou devront
faire travailler un ordinateur, il est essentiel de comprendre ses principes fondamentaux
et de connaître ses éléments de base. Une formule 1 ne se conduit pas comme
une voiture à pédales. De même un ordinateur se s’utilise pas comme un boulier.
L’algorithmique est le permis de conduire de l’informatique. Sans elle, il n’est pas
concevable d’exploiter sans risque un ordinateur.
Cette introduction remarquable à l’algorithmique donne au lecteur d’une part les
bases théoriques indispensables et lui fournit d’autre part les moyens de concevoir rigoureusement
des programmes efficaces permettant de résoudre des problèmes variés
issus de différentes applications.
L’éventail des algorithmes présentés va des plus classiques, comme les algorithmes
de tri et les fonctions de hachage, aux plus récents comme ceux de la cryptographie.
On trouve ici rassemblés des algorithmes numériques, par exemple pour l’inversion
de matrices ou la transformée de Fourier et des algorithmes combinatoires comme
les algorithmes de graphes ou la recherche de motif.
Une très large place est faite aux structures de données, des plus simples comme
les listes, aux plus sophistiquées comme les tas de Fibonacci. Notons au passage
l’importance accordée aux différentes mesures de complexité (pire des cas, amortissement,
en moyenne) qui permettent d’approfondir entre autres l’étude de l’efficacité
des algorithmes de tri et des structures de données.