Brigitte Chauvin - Böcker

This is the second volume in a series of innovative proceedings entirely devoted to the connections between mathematics and computer science. Here mathematics and computer science are directly confronted and joined to tackle intricate problems in computer science with deep and innovative mathematical approaches. The book serves as an outstanding tool and a main information source for a large public in applied mathematics, discrete mathematics and computer science, including researchers, teachers, graduate students and engineers. It provides an overview of the current questions in computer science and the related modern and powerful mathematical methods. The range of applications is very wide and reaches beyond computer science.

This volume contains the proceedings of the vVorkshop on Trees held in Versailles on 14-16 June 1995. Why: a workshop on trees? Two main reasons motivated this workshop. First, the current plethora of tree representations in branching processes which has be­ come obvious by the Minneapolis IMA Congress Classica] and Modern Branching Processes in 1994. But this would not have been sufficient to organize an "n-th" congress on branching processes. Secondly, regular discussions with researchers in algebra and computing sciences at the University of Versailles and at INRIA (lnstitut National de Recherche en Informatique et Automatique) convinced us it would be fruitful to offer the workers in these different fields the opportunity to exchange their points of view on the subject. The organizers being probabilists, a large part of the meeting (two sessions) was devoted t~ probability theor:y (not only branching processes). Nevertheless, the other three sessions focused on algorithms, on ultrametric and combinatorial aspects of trees and on disordered systems. Most papers in this volume are both of high level and of pedagogical interest. They are intended for a large public, including graduate students looking for an initiation to tree structures. The papers have been grouped into four sections: - disordered systems, - probability and trees, - large deviations, - ultrametric and algebraic aspects of trees. Some of the speakers are, unfortunately, not represented in this volume.

Cet ouvrage présente les types d'arbres les plus utilisés en informatique, sous les angles algorithmique et mathématique. Pour chaque type, nous donnons les algorithmes courants associés et des exemples d'utilisation, directe ou en modélisation, puis nous étudions leurs performances d'un point de vue mathématique. Nos outils sont les mathématiques discrètes, les probabilités et la combinatoire analytique, présentés ici simultanément.Le public visé est d'abord celui des étudiants de niveau master scientifique ou en dernière année d’école d’ingénieurs avec un cursus préalable en informatique ou en mathématiques, ou ceux visant une double compétence en mathématiques et informatique ; ainsi que toute personne dotée d’un bagage scientifique « minimal » et amenée à utiliser des structures arborescentes liées à des algorithmes, qui souhaiterait avoir une meilleure connaissance de ces structures et une idée des performances des algorithmes associés 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.