This is the first book where mathematics and computer science are directly confronted and joined to tackle intricate problems in computer science with deep mathematical approaches. It contains a collection of refereed papers presented at the Colloquium on Mathematics and Computer Science held at the University of Versailles-St-Quentin on September 18-20, 2000. The colloquium was a meeting place for researchers in mathematics and computer science and thus an important opportunity to exchange ideas and points of view, and to present new approaches and new results in the common areas such as algorithms analysis, trees, combinatorics, optimization, performance evaluation and probabilities. The book is intended 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 related modern mathematical methods. The range of applications is very wide and reaches beyond computer science.
Author(s): Andras Antos, Luc Devroye (auth.), Danièle Gardy, Abdelkader Mokkadem (eds.)
Series: Trends in Mathematics
Edition: 1
Publisher: Birkhäuser Basel
Year: 2000
Language: English
Pages: 341
Tags: Mathematics, general
Front Matter....Pages N2-xi
Front Matter....Pages 1-1
Rawa Trees....Pages 3-15
The height and width of simple trees....Pages 17-30
On the node structure of binary search trees....Pages 31-40
The Saturation Level in Binary Search Tree....Pages 41-51
Smoothness and Decay Properties of the Limiting Quicksort Density Function....Pages 53-64
The Number of Descendants in Simply Generated Random Trees....Pages 65-73
An Universal Predictor Based on Pattern Matching: Preliminary results 1 ....Pages 75-85
Front Matter....Pages 87-87
A bijective proof for the arborescent form of the multivariable Lagrange inversion formula....Pages 89-100
Counting paths on the slit plane....Pages 101-112
Random generation of words of context-free languages according to the frequencies of letters....Pages 113-125
An Algebra for Proper Generating Trees....Pages 127-139
A set of well-defined operations on succession rules....Pages 141-152
Front Matter....Pages 153-153
Convergence of a Genetic Algorithm with finite population....Pages 155-163
Complexity issues for a redistribution problem....Pages 165-176
On the rate of escape of a mutation-selection algorithm....Pages 177-182
Randomized Rendezvous....Pages 183-194
Front Matter....Pages 195-195
Computing Closed-Form Stochastic Bounds on the Stationary Distribution of Markov Chains....Pages 197-208
Effects of Reordering and Lumping in the Analysis of Discrete-Time SANs....Pages 209-220
Large deviations for polling systems....Pages 221-229
A nonlinear integral operator encountered in the bandwidth sharing of a star-shaped network....Pages 231-242
Front Matter....Pages 243-243
A new proof of Yaglom’s exponential limit law....Pages 245-249
The branching measure, Hausdorff and packing measures on the Galton-Watson tree....Pages 251-263
Likelihood ratio processes and asymptotic statistics for systems of interacting diffusions with branching and immigration....Pages 265-274
Probabilistic Analysis of a Schröder Walk Generation Algorithm....Pages 275-294
Gibbs Families....Pages 295-304
Generating functions with high-order poles are nearly polynomial....Pages 305-321
Ultrahigh Moments for a Brownian Excursion....Pages 323-328
A zero-one law for random sentences in description logics....Pages 329-340
Back Matter....Pages 341-341
