MULTIYEAR PROGRAM
RESEARCH SCHOOL - ÉCOLE DE RECHERCHE
Organizing Committee
Comité d’organisation
Frédérique Bassino (Université Sorbonne Paris Nord)
Christina Goldschmidt (University of Oxford)
Bénédicte Haas (Université Sorbonne Paris Nord)
Florent Koechlin (Université Sorbonne Paris Nord)
Meltem Ünel (Université Sorbonne Paris Nord)
IMPORTANT WARNING: Scam / Phishing / SMiShing ! Note that ill-intentioned people may be trying to contact some of participants by email or phone to get money and personal details, by pretending to be part of the staff of our conference center (CIRM). CIRM and the organizers will NEVER contact you by phone on this issue and will NEVER ask you to pay for accommodation/ board / possible registration fee in advance. Any due payment will be taken onsite at CIRM during your stay.
The annual meeting Aléa is dedicated to the study of random discrete structures arising in various scientific domains, mainly in theoretical computer science, combinatorics and probability theory, but also in statistical physics, bioinformatics or in other branches of mathematics.
These structures are, for example, trees, words, permutations, lattice walks, more geometrical objects like planar maps, or other objects related to discrete dynamics like cellular automata. Aims and methods are diverse, ranging from enumeration, asymptotic properties and analytic combinatorics, probability, random generation…
The Aléa meeting is closely related to the community of the Working Group Aléa of the “Groupement de recherche CNRS” gdr-im, which was created in the 90’s under the impulse of Philippe Flajolet to promote interactions between combinatorics and probability around the analysis of algorithms. In the last ten years it has been the birth place to many fruitful interdisciplinary collaborations (e.g. on planar maps, walks in quarter plane, algebraic urns…) and it has grown into one of the most active interface between computer scientists and mathematicians in France. The program of the conference aims both at broadening the common knowledge of the participants via mini-courses and invited long talks, and at reflecting the variety and dynamism of the community via short talks that are selected through an open call.
Les journées Aléa sont consacrées à l’étude de l’aléa discret, i.e. l’étude des structures aléatoires discrètes telles qu’elles apparaissent dans diverses disciplines, principalement l’informatique théorique, la combinatoire et la théorie des probabilités, mais aussi la physique statistique, la bio-informatique ou d’autres branches des mathématiques.
Les objets d’études sont par exemple les arbres, les mots, les permutations, les chemins, ou des objets plus géométriques comme les cartes, ou encore liés à une dynamique discrète comme les automates cellulaires. Les objectifs et les méthodes utilisées sont divers : l’énumération, les propriétés asymptotiques et la combinatoire analytique, les propriétés probabilistes, la génération aléatoire…
Les journées Aléa sont étroitement liées à la communauté du groupe de travail Aléa du gdr-im, créé à l’initiative de Philippe Flajolet vers la fin des années 90 pour favoriser les interactions entre combinatoristes et probabilistes autour de l’analyse d’algorithmes. Au cours de ces dix dernières années, elles ont été le creuset de nombreuses et fécondes collaborations interdisciplinaires (e.g. autour des cartes planaires, des marches dans le quart-de plan, des urnes algébriques…) et elles sont devenues lieu d’expression de l’une des interfaces math/info les plus actives en France. Le programme répond au double objectif d’assurer une forme de formation continue de la communauté au travers de cours invités et d’exposés longs, et de refléter sa diversité et son dynamisme au travers d’exposés courts sélectionnés via appel à propositions.
MINI-COURSES
Durée: for a total 2.5 hours + exercise session of 1 hour, each
LONG TALKS
Une triangulation est un modèle de surface discrète consistant à recoller un nombre fini de triangles le long de leurs côtés de manière à obtenir une surface. Dans le cas planaire (i.e. quand la surface doit avoir la topologie de la sphère), l’étude de triangulations aléatoires repose sur des résultats de comptage exacts obtenus par Tutte dans les années 60.
En revanche, pour des surfaces plus générales, de tels résultats exacts ne sont plus disponibles. Le but de l’exposé sera de donner une idée des techniques développées pour étudier des triangulations aléatoires de grand genre malgré le manque de résultats combinatoires précis. On verra en particulier que parfois, les résultats probabilistes permettent même
d’obtenir en retour des estimées combinatoires. Travaux en commun avec Baptiste Louf et Guillaume Chapuy.
Les séries génératrices comptant des marches dans le quadrant, les distributions stationnaires de marches aléatoires ou encore les transformées de Laplace de mouvements browniens réfléchis satisfont le même type d’équations fonctionnelles en deux variables catalytiques. Dans cet exposé, je présenterais des méthodes issues de la théorie de Galois classique ou différentielle pour déterminer le comportement algébrique de solutions de telles équations voire d’expliciter ces solutions en terme de fonctions spéciales.
Balanced binary search trees are a common data structure for implementing ordered sets, with three kinds of queries: checking whether a given value belongs to the set, inserting a value, and deleting a value. The two latter queries require updating the data structure.
Some implementations, like red-black trees or weak AVL trees, allow efficient update procedures, which run in a top-down way and require an amortized constant number of write operations per update query. Yet, AVL trees still require bottom-up updating procedures, which may require a logarithmic number of write operations per query. We will present new algorithms for updating AVL trees, directly inspired from algorithms for weak AVL trees, that bridge this gap: they run in a top-down way and/or require only an amortized constant number of write operations per update query. Most of the presentation will be devoted to the latter aspect.
SPONSORS
Projet ANR GrR (Reconfiguration de graphes)
Projet ANR DIMERS
