L'informatique met en jeu des programmes et des
systèmes
chaque jour plus complexes. Cependant, de tels systèmes ne
s'appuient que sur la résolution d'un petit nombre de "
grands "
algorithmes dont le rôle est souvent critique.
L'analyse d'algorithmes se donne pour objectif de se
caractériser précisément les performances de ces
algorithmes fondamentaux.
Ce livre présente une étude approfondie des techniques
fondamentales utilisées en analyse mathématique
d'algorithmes. Les sujets abordés par les auteurs gravitent
auteur de thèmes mathématiques, notamment les mathématiques
discrètes, l'analyse réelle élémentaire, et la
combinatoire, mais également autour de thèmes proprement
informatiques, en particulier les algorithmes et les
structures de données. Ils se sont attachés principalement
à l'analyse " en moyenne " et à l'analyse " probabilistique
", tout en introduisant les outils nécessaires à l'analyse
" dans le pire des cas " ou à l'analyse de " complexité
".
Sommaire
L'analyse d'algorithmes
Relations de récurrence
Séries génératrices
Approximations asymptotiques
Arbres
Permutations
Chaînes et arbres digitaux
Mots et mappes