 |
Liste des orateurs
Abstracts of the conferences
Conferences for invited speakers last one hour. Accepted
communications should last 30min, questions included.
- Donald E. Knuth (Stanford University)
Five interesting combinatorial objects can unexpectedly be
transformed into each other: Thin BDDs, Dellac permutations,
Genocchi derangements, irreducible Dumont pistols, and paths in a
yet-unnamed simple digraph.
- Philippe Flajolet (INRIA Rocquencourt)
Many applications, from network management to data mining and
data bases, require efficient methods for extracting automatically
quantitative characteristics of large data ensembles. Specifically,
there is interest in determining cardinalities (the number of distinct
elements satisfying various criteria), empirical entropies and more
generally frequency moments, as well as "icebergs", "elephants", and
"mice".
This survey talk will start from a few highly efficient algorithms
that make it possible to attain estimates of good quality (typicallly
accurate within a few percents), based on fine properties of discrete
probabilistic models. The lecture will focus on the intertwinment of
algorithmic design with a collection of general methods of analytic
combinatorics, which have proved especially useful in this context,
namely, generating functions, singularity analysis, Mellin transforms,
and analytic depoissonization.
- Maxime Crochemore (Université Paris-Est et King's College de Londres)
The analysis of periodicities in strings constitutes a fundamental
area of combinatorics on words due to important applications to text
algorithms, data compression, music analysis, and biological sequences
analysis.
Periods are ubiquitous in pattern matching algorithms because
stuttering is likely to slow down any of these algorithms. Dealing
with periods is certainly the hard part of string matching methods to
which D. E. Knuth has made an early famous contribution. The role of
periods is even more important in time-space optimal string-matching
algorithms because the only information on patterns that is
precomputed and stored is related to their global and local periods.
The talk surveys algorithmic methods used to locate repetitive
segments in strings. It discusses the notion of runs that encompasses
various types of periodicities considered by different authors. Their
computation is related in several ways to the Lempel-Ziv factorisation
of a string used in text compression software. The analysis of
related algorithms raises interesting combinatorial questions and
conjectures.Documents : Slides (80.81 ko.)
- Xavier Viennot (CNRS/LaBRI Bordeaux)
From D.Knuth's pre-fascicle 4A: "Trees sprout up just about
everywhere in computer science, as we've seen in Section 2.3 and
in nearly every section of The Art of Computer
Programming". Binary trees are enumerated by the well known
Catalan numbers. This ubiquitous sequence of numbers was introduced
by the universal mathematician Leonhard Euler (1707-1783) in the
last page of a letter he wrote to his good friend Christian
Goldbach on 4th September 1751. In Hydrogeology, Strahler,
following Horton, introduced a certain analysis of river networks,
and in fact defined a certain parameter called the Strahler number
of a binary tree. This talk relates the story of Catalan numbers,
of the Horton-Strahler parameter, and its surprising appearance in
various domains of computer science, mathematics, computer
graphics, physics and molecular biology.
Strahler distribution appears four times in four different classes
of combinatorial objects: binary trees, forest of planar trees,
Dyck paths (nested parentheses) and the so-called Kepler towers
introduced by the speaker during a memorable month spent with
D.Knuth at Mittag-Leffler Institute in winter 2005. Recursive
bijections are known between these four classes of objects. After
Françon's recursive bijection (1984) between binary trees and Dyck
paths preserving the Strahler distribution, combinatorists had to
wait more than 20 years before a "direct" bijection was given. The
inventor of this astonishing bijection is D.Knuth.
- Brigitte Vallée (CNRS/GREYC Caen)
The Euclid Algorithm is, according to Knuth himself, "the
grandfather of all the algorithms". It is of great use, and the
basic "parameters" of the algorithm, namely the number of
iterations, the evolution of remainders, or the total number
of elementary operations are of great interest, since they describe
the precise complexity of the algorithm. Moreover,such a basic
algorithm admits numerous variations, as the binary algorithm, the
version which deals with least significant bits, the fast versions
due to Knuth and Schönhage, etc... There exists very natural
questions about the probabilistic behaviour of all these algorithms
which had not received a precise answer until recently.
All the recent results are obtained by using the same general
method, where an algorithm is viewed as a dynamical system. As
usual in analysis of algorithms, generating functions of the main
parameters are considered, but, now, they are generated themselves
by the transfer operator of the underlying dynamical system, which
plays the rôle of a generating operator. Even if the (various)
Euclid algorithms give rise to very different dynamical systems,
such a general methodology provides a powerful tool for answering
(almost) all the main questions about the analysis of all these
algorithms.Documents : Transparents (290.71 ko.)
- Jean-Michel Muller (CNRS/LIP Lyon)
Floating-point (FP) arithmetic was designed as a mere
approximation to real arithmetic. And yet, since the behaviour of
each operation is fully specified by the IEEE-754 standard for
floating-point arithmetic, FP arithmetic can also be viewed as a
mathematical structure on which it is possible to design algorithms
and proofs. We give some examples (among them, some are due to
D. Knuth) that show the interest of that point of view. Documents : Slides (1.56 Mo.)
Accepted communications
- Luca Castelli Aleardi (LIX (Ecole Polytechnique) / ULB (Bruxelles))
We consider the problem of designing succinct representations of
labeled graphs (we consider vertex labeled planar triangulations,
as well as edge labeled planar graphs and the more general k-page
graphs). The goal is to support various label queries efficiently,
while using an amount of additional space to store the labels which
is essentially the information-theoretic minimum. As far as we
know, our representations are the first succinct representations of
labeled graphs.
First, we define three new traversal orders on the vertices of a
planar triangulation, allowing to design a succinct representation
which supports efficiently labeled based navigation operators.
Second, we design a succinct representation for a k-page graph
when k is large supporting vertex adjacency in sub-linear time
(while previous work uses O(k) time).Documents : Short paper (250.24 ko.)
- Jérémy Barbay (Cheriton School of Computer Science / University of Waterloo)
Succinct data structures replace static instances of pointer based
data structures, improving performance in both time and space in the
word RAM model (a restriction of the RAM model where the size of a
word is restricted). The adaptive analysis of algorithms considers
the complexity in a finer way than merely grouping the instances by
size, yielding more precise lower and upper bound on the complexity
of a problem. We give a quick overview of those two techniques,
some brief examples of how they can be combined on various search
problems to obtain near optimal solutions, and some general
perspective on the development and application of those techniques
to other problems and in undert different models. Documents : Version courte (163.30 ko.)
- Mathilde Bouvel (LIAFA / Université Paris Diderot Paris 7)
In their paper "On the tandem duplication-random loss model of
genome rearrangement" presented at SODA 2006, Chaudhuri, Chen,
Mihaescu and Rao study algorithmic properties of the tandem
duplication-random loss model of genome rearrangement, well-known
in evolutionary biology. In their model, the cost of one step of
duplication-loss of width k is alpha^k for alpha =1 or alpha >=
2. In the work presented here, we study a variant of this model,
where the cost of one step of width k is 1 if k <= K and is
infinite if k > K, for any value of the parameter K in the set {n :
n integer}U{infinity}. We first show that permutations obtained
after p steps of width K define classes of pattern-avoiding
permutations. We also compute the numbers of duplication-loss steps
of width K necessary and sufficient to obtain any permutation of
S_n, in the worst case and on average. In this second part, we may
also consider the case K=K(n), a function of the size n of the
permutation on which the duplication-loss operations are
performed. Documents : Short version (88.50 ko.)
- Nicolas Broutin (INRIA Rocquencourt)
We propose a general model of random trees that covers many
examples of interest in computer science (most trees of
"logarithmic" height we know of). Using a connection with branching
random walks and large deviations techniques, we obtain a law of
large numbers for the height of such trees, i.e., the maximum
length of a path from the root. This approach unifies the results
about heights of random trees that appeared scattered in the
literature. In particular, the well-known results about the heights
of random binary search and random recursive trees are obtained
effortlessly. The main novel applications are the asymptotic
analysis of the height of all polynomial varieties of increasing
trees, and the description of cells in recursive geometric
partitions like k-d trees.
This is joint work with L. Devroye, E. McLeish and M. de la
Salle.Documents : Short version (376.80 ko.)
- Phan-Thuan Do (Le2i / Université de Bourgogne)
ECO-method and its corresponding succession rules allow to
recursively define and construct combinatorial objects. We
introduce here "succession functions" which refine succession
rules. They permit to construct general efficient algorithms for
classes of combinatorial objects and to find some new classes more
easily than previous methods. We apply succession function
technique for a lot of classes of pattern avoiding permutations and
derive general constant amortized time generating algorithms for
them.
This paper is dedicated to Don Knuth who initiated 35 years ago the
field of "pattern avoiding permutations".Documents : Short version (124.61 ko.)
- Jean-Christophe Filliâtre (CNRS / LRI, Univ Paris-Sud / INRIA Futurs))
We introduce a methodology to formally verify MIX programs.
It consists in annotating a MIX program with logical annotations
and then to turn it into a set of purely sequential programs on
which classical techniques can be applied.
Contrary to other approaches of verification of unstructured
programs, we do not impose the location of annotations but only the
existence of at least one invariant on each cycle in the control
flow graph. A prototype has been implemented and used to verify
several programs from The Art of Computer Programming.Documents : Short version (217.48 ko.)
- Arnaud Lefebvre (LITIS / Université de Rouen)
A border u of a string w is a prefix and a suffix of w such that
u ≠ w. The computation of the border array of a string w i.e.
of the borders of each prefix of a string w is strongly related to
the string matching problem: given a string w, find the first or,
more generally, all its occurrences in a longer string y. The
border array of w is better known as the "failure function" of
the Morris-Pratt algorithm. There exist several methods to check if
an integer array f is a border array for some string w. An easy
extension of these methods enables to generate all the distinct
border arrays of some length in linear space and in time
proportional to their number.
In the present work we deal with KMP (Knuth-Morris-Pratt) arrays
instead of border arrays. KMP arrays are used as "failure
function" in the Knuth-Morris-Pratt string matching
algorithms. Given an integer array g, we can decide if g is the KMP
array of some string w on a bounded alphabet of size s. If it is
not, we can compute the longest prefix of g for which there exists
a string w such that the prefix of g is the KMP array of
w. Actually these results are completely independent from w. We are
also capable of generating all the distinct KMP arrays in time and
space proportional to their numbers. Documents : Short version (268.92 ko.)
- Loïck Lhote (GREYC / Université de Caen / Ensicaen)
Gcd computation is omnipresent in rational computations, public key
cryptography or computer algebra but most GCD algorithms perform
successive divisions which leads to a quadratic bit-complexity. Major
improvements in this area are due to Knuth and Schönhage who
designed the first subquadratic algorithm in 1970. They use both
Divide and Conquer techniques and fast multiplications (FFT,
Karatsuba, ...). In this work, we propose a complete average analysis
of variants of the Knuth-Schöonhage algorithm. Due to the close
relations between this algorithm and the Euclid one, the analysis is
based on Dynamical Analysis methods, developed by the Caen group
around Brigitte Vallée. Documents : Short version (113.97 ko.)
- Antonio Vera (GREYC / Université de Caen)
Gauss' algorithm is the fountainhead of polynomial-time lattice
reduction. It can be viewed as a natural generalization of
Euclid's algorithm to complex numbers, and gives rise in a natural
way to a dynamical system. This point of view provides a better
understanding of the algorithm itself, and permits a transfer of
knowledge between the continuous world and the discrete world. This
kind of a transfer has already been operated by Knuth in his
analysis of Euclid's algorithm in "The Art of Computer
Programming". In the present case, we succesfully use the
dynamical analysis machinery introduced by Vallée to reach the
goal.
In this talk, we provide a probabilistic analysis of Gauss'
algorithm in a simple yet realistic model. This allows to see the
transition to Euclid's algorithm. We are particularly interested in
analyzing the bit-complexity and the geometric characteristics of
the output. These results are a main step for our main project,
namely the average-case analysis of the Lenstra, Lenstra and Lovász
lattice reduction algorithm.
This is joint work with Brigitte Vallée.Documents : Short version (154.07 ko.)
|
 |
Soutiens : CNRS
LaBRI
Université Bordeaux I
GDR-IM
|