Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities

ISBN-13: 9783034895538 / Angielski / Miękka / 2012 / 341 str.

Daniele Gardy; Abdelkader Mokkadem

Opis

This book is based on the proceedings of the Colloquium on Mathematics and Computer Science held in the University of Versailles-St-Quentin on September 18- It contains articles on topics that are relevant both to Mathematics and 20, 2000. to Computer Science. These articles have been selected throughout a rigourous process; each of them has been submitted to two referees at least. This selection process, which took place under the supervision of the scientific committee, en- sures the high level and the originality of the contributions. We thank the invited speakers, the authors, the participants to the collo- quium and, of course, the Scientific Committee whose members were D. Aldous, F. Baccelli, P. Cartier, B. Chauvin, P. Flajolet, J.M. Fourneau, D. Gardy, D. Gouyou- Beauchamps, R. Kenyon, J.F. Le Gall, C. Lemarechal, R. Lyons, A. Mokkadem, A. Rouault and C. Roucairol. We also take this opportunity to thank the University of Versailles-St-Quentin, the University of Paris-Sud (Orsay) and the Centre National de la Recherche Sci- entifique (CNRS), whose financial and material support contributed to the success of the Colloquium.

Spis treści

1 Rawa trees.- 2 The height and width of simple trees.- 3 On the node structure of binary search trees.- 4 The saturation level in binary search tree.- 5 Smoothness and decay properties of the limiting quicksort density function.- 6 The number of descendants in simply generated random trees.- 7 An universal predictor based on pattern matching, preliminary results.- 8 A bijective proof of the arborescent form of the multivariable Lagrange’s inversion formula.- 9 Counting paths on the slit plane.- 10 Random generation of words of context-free languages according to the frequencies of letters.- 11 An algebra for generating trees.- 12 A set of well-defined operations on succession rules.- 13 Convergence of a genetic algorithm with finite population.- 14 Complexity issues for a redistribution problem.- 15 On the rate of escape of a mutation-selection algorithm.- 16 Randomized rendezvous.- 17 Computing closed-form stochastic bounds on the stationary distribution of Markov chains.- 18 Effects of reordering and lumping in the analysis of discrete-time SANs.- 19 Large deviations for polling systems.- 20 A nonlinear integral operator encountered in the bandwidth sharing of a star-shaped network.- 21 A new proof of Yaglom’s exponential limit law.- 22 The branching measure, Hausdorff and packing measures on the Galion-Watson tree.- 23 Likelihood ratio processes and asymptotic statistics for systems of interacting diffusions with branching and immigration.- 24 Probabilistic Analysis of a Schröder Walk Generation Algorithm.- 25 Gibbs families.- 26 Generating functions with high-order poles are nearly polynomial.- 27 Ultrahigh Moments for a Brownian Excursion.- 28 A zero-one law for random sentences in description logics.