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

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.

---

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.
Content:
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
Front Matter....Pages 75-85
A bijective proof for the arborescent form of the multivariable Lagrange inversion formula....Pages 87-87
Counting paths on the slit plane....Pages 89-100
Random generation of words of context-free languages according to the frequencies of letters....Pages 101-112
An Algebra for Proper Generating Trees....Pages 113-125
A set of well-defined operations on succession rules....Pages 127-139
Front Matter....Pages 141-152
Convergence of a Genetic Algorithm with finite population....Pages 153-153
Complexity issues for a redistribution problem....Pages 155-163
On the rate of escape of a mutation-selection algorithm....Pages 165-176
Randomized Rendezvous....Pages 177-182
Front Matter....Pages 183-194
Computing Closed-Form Stochastic Bounds on the Stationary Distribution of Markov Chains....Pages 195-195
Effects of Reordering and Lumping in the Analysis of Discrete-Time SANs....Pages 197-208
Large deviations for polling systems....Pages 209-220
A nonlinear integral operator encountered in the bandwidth sharing of a star-shaped network....Pages 221-229
Front Matter....Pages 231-242
A new proof of Yaglom’s exponential limit law....Pages 243-243
The branching measure, Hausdorff and packing measures on the Galton-Watson tree....Pages 245-249
Likelihood ratio processes and asymptotic statistics for systems of interacting diffusions with branching and immigration....Pages 251-263
Probabilistic Analysis of a Schr?der Walk Generation Algorithm....Pages 265-274
Gibbs Families....Pages 275-294
Generating functions with high-order poles are nearly polynomial....Pages 295-304
Ultrahigh Moments for a Brownian Excursion....Pages 305-321
A zero-one law for random sentences in description logics....Pages 323-328
Back Matter....Pages 329-340
....Pages 341-341