The International Colloquium on Mathematics and Computer Science is a biennial event that first took place at the University of Versailles-St-Quentin in 2000 and was acknowledged a success. The second colloquium was held in September 16-19, 2002, again in Versailles; its proceedings are gathered in this book. The importance of these regular meetings between researchers from mathematics and from computer science is now unanimously recognized by the two communities. The colloquium offers the opportunity to establish the state of the art and to present new trends, new ideas and new results in the common areas such as analysis of algorithms, trees, combinatorics, optimization, performance evaluation and probabilities.
This series of proceedings is the first one 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.
Author(s): Didier Arquès, Anne Micheli (auth.), Brigitte Chauvin, Philippe Flajolet, Danièle Gardy, Abdelkader Mokkadem (eds.)
Series: Trends in Mathematics
Edition: 1
Publisher: Birkhäuser Basel
Year: 2002
Language: English
Pages: 543
Tags: Data Structures, Cryptology and Information Theory; Coding and Information Theory; Discrete Mathematics in Computer Science; Probability and Statistics in Computer Science; Systems Theory, Control; Algorithms
Front Matter....Pages i-xiii
Front Matter....Pages 15-15
n-Colored Maps and Multilabel n-Colored Trees....Pages 17-31
Limit Laws for Basic Parameters of Lattice Paths with Unbounded Jumps....Pages 33-47
Counting Walks in the Quarter Plane....Pages 49-67
Bijective Construction of Equivalent Eco-systems....Pages 69-81
Random Boundary of a Planar Map....Pages 83-93
Enumération des 2-arbres k -gonaux....Pages 95-109
Front Matter....Pages 111-111
Breadth First Search, Triangle-Free Graphs and Brownian Motion....Pages 113-125
Random Planar Lattices and Integrated SuperBrownian Excursion....Pages 127-145
The Diameter of a Long-Range Percolation Graph....Pages 147-159
Giant Components for Two Expanding Graph Processes....Pages 161-173
Coloring Random Graphs — an Algorithmic Perspective....Pages 175-195
A Sharp Threshold for a Non-monotone Digraph Property....Pages 197-211
Approximability of Paths Coloring Problem in Mesh and Torus Networks....Pages 213-222
Minimal Spanning Trees for Graphs with Random Edge Lengths....Pages 223-245
Front Matter....Pages 247-247
Generalized Pattern Matching Statistics....Pages 249-265
A Note on Random Suffix Search Trees....Pages 267-278
On the Profile of Random Forests....Pages 279-293
On the Number of Heaps and the Cost of Heap Construction....Pages 295-310
A Combinatorial Problem Arising in Information Theory: Precise Minimax Redundancy for Markov Sources....Pages 311-328
Analysis of Quickfind with Small Subfiles....Pages 329-340
Front Matter....Pages 247-247
Distribution of the Size of Simplified or Reduced Trees....Pages 341-354
Digits and Beyond....Pages 355-377
Front Matter....Pages 379-379
Growth Rate and Ergodicity Conditions for a Class of Random Trees....Pages 381-391
Ideals in a Forest, One-Way Infinite Binary Trees and the Contraction Method....Pages 393-414
On Random Walks in Random Environment on Trees and Their Relationship with Multiplicative Chaos....Pages 415-422
Note on Exact and Asymptotic Distributions of the Parameters of the Loop-Erased Random Walk on the Complete Graph....Pages 423-440
Convergence Rate for Stable Weighted Branching Processes....Pages 441-453
Reduced Branching Processes in Random Environment....Pages 455-467
Front Matter....Pages 469-469
A Cooperative Approach to Rényi’s Parking Problem on the Circle....Pages 471-479
On the Noise Sensitivity of Monotone Functions....Pages 481-495
Apprentissage de Séquences Non-Indépendantes d’Exemples....Pages 497-511
Entropy Reduction Strategies on Tree Structured Retrieval Spaces....Pages 513-525
Zero-One Law Characterizations of ε 0 ....Pages 527-539
Further Applications of Chebyshev Polynomials in the Derivation of Spanning Tree Formulas for Circulant Graphs....Pages 541-553
Back Matter....Pages 555-557
