Description
Cet ouvrage prsente les types d’arbres les plus utiliss en informatique, sous les angles algorithmique et mathmatique. Pour chaque type, nous donnons les algorithmes courants associs et des exemples d’utilisation, directe ou en modlisation, puis nous tudions leurs performances d’un point de vue mathmatique. Nos outils sont les mathmatiques discrtes, les probabilits et la combinatoire analytique, prsents ici simultanment. Le public vis est d’abord celui des tudiants de niveau master scientifique ou en dernire anne d’cole d’ingnieurs avec un cursus pralable en informatique ou en mathmatiques, ou ceux visant une double comptence en mathmatiques et informatique ; ainsi que toute personne dote d’un bagage scientifique minimal et amene utiliser des structures arborescentes lies des algorithmes, qui souhaiterait avoir une meilleure connaissance de ces structures et une ide des performances des algorithmes associs sans se plonger dans les travaux originaux. This book presents a wide range of tree structures, from both a computer science and a mathematical point of view. For each of these structures we give the algorithms that allow us to visit or update the structure, and discuss their potential uses, either directly (for storing data) or in modelling a variety of situations. We present a mathematical approach to their performances; this is done by the systematic and parallel use of tools from discrete mathematics, probability and analytic combinatorics. The book is intended for graduate students in mathematics or computer science (or both) and in engineering schools. It is also suitable for anyone with a basic level of scientific knowledge who may have to use tree structures and related algorithms, and who wishes to get a rigorous knowledge of their performance without going back to the original, often specialized, results. Introduction.- Partie I Modles.- 1.Botanique.- 2.Ala sur les arbres.- 3.Arbres, algorithmes et donnes.- Partie II Analyses.- 4.Approche combinatoire.- 5.Approche probabiliste.- 6.Arbres binaires de recherche.- 7.Arbres digitaux.- 8.Arbres m-aires et quadrants.- 9.Urnes de Plya et applications.- A.Rappels algorithmiques.- B.Rappels mathmatiques : combinatoire.- C.Rappels mathmatiques : probabilits.- D.Un peu d’histoire.- E.Rappel des notations utilises.- References.- Index.- Liste des auteurs.
