Réunions

  • Jeudi 16 janvier 2014 au LIPN
    • 10h30 Elie de Panafieu (LIAFA)
      “Transition de phase dans les hypergraphes aléatoires”
    • 11h45  Discussion autour des  modèles combinatoires complexes
      (Non-uniformité, objets combinatoires contraints ou corrélés,
      propriétés structurelles, génération aléatoires)
    • 13h45  Julien Salez (LPMA)
      “La convergence locale faible : un cadre pour l’étude des grands graphes.”
    • 15h Robert Cori (LaBRI)
      “Calcul des rangs de configurations sur le graphe complet”
  • 13 Juin 2013 au LIPN
    • 10H30 : Aline Parreau : Une preuve combinatoire du Lemme local de LovaszLe lemme local de Lovasz est un outil très utilisé permettant de montrer de
      manière simple l’existence d’objets combinatoires avec certaines
      propriétés. Il dit que si des événements ont lieu avec une petite
      probabilité et ne sont pas trop indépendants les uns des autres, la
      probabilité qu’aucun évènement n’arrive est non nulle. Moser a donné en
      2009 une preuve algorithmique de ce lemme, basée sur la compression
      d’entropie. Cette méthode permet en outre, dans certains cas, d’obtenir de
      manière élégante des résultats plus fort que ceux obtenus en utilisant le
      lemme local. J’expliquerai ses idées principales à travers deux exemples :
      la construction de mots sans carrés et le problème $k$-SAT où chaque clause
      a des variables en commun avec un nombre limité de clauses.
    • 11H45 : Yann Ponty : RDOS : Un projet “vitrine” pour des outils de génération aléatoire (non-uniforme) (slides)
      Les prototypes de génération aléatoires, développés au sein de l’ANR ou plus généralement dans la communauté ALEA, restent souvent d’usage assez confiné. Cependant, des besoins concrets pour ceux-ci existent dans des communautés connexes (bioinfo, test logiciel, théorie des automates, workflows …), celles-ci ayant alors souvent recours à des approches ad-hoc potentiellement biaisées, et souvent de complexité sous-optimales par rapport à l’état de l’art.Afin de démontrer les capacités des différents générateurs, en populariser l’utilisation, et mettre en lumière les contributions algorithmiques sous-jacentes, nous développons RDOS (Random Discrete Objects Suite), un serveur web ayant pour vocation de cumuler, au sein d’une interface commune, de nombreux générateurs de principes, objets d’étude et langage d’implémentation différents. Suite à des discussion lors des Journées MAGNUM à Caen, des développements préliminaires ont été initiés. Parmi les choix de conception, nous avons choisi de classer les outils par méthode (Boltzmann, récursive, simulation exacte …), par auteurs et par types d’objets engendrés. L’exécution des générateurs sera effectuée sur des machines éventuellement distinctes selon un modèle de “file d’attente distribuée”, permettant un ajout “à chaud” de nouveaux générateurs et machines. Les objets combinatoires engendrés seront présentés à l’utilisateur dans une page permettant une visualisation basique, ainsi qu’un possible téléchargement des objets. Un accent particulier sera mis sur l’identification des contributeurs (via leurs noms, des liens vers une éventuelle page dédiée, ainsi que la ou les publication(s) relative(s) au générateur).

      Un premier prototype est actuellement partiellement fonctionnel, et devrait être démontré. Nous espérons profiter de cette occasion pour recueillir vos réactions, commentaires et réserves éventuelles sur le projet.

    • 14H00 : Mathieu Raffinot (LIAFA)
      Nouvelles avancées dans la recherche de motifs uniques ou consécutifs dans des permutations
      travail en commun avec D.l Belazzougui (Univ. of Helsinki), A. Pierrot (LIAFA) et S. Vialette (LIGM)Let T be a permutation (that shall play the role of the text) on [n] and a pattern P be a sequence of
      M distinct integer(s) of [n], m order-isomorphic to T[i] .. T[i+m-1], that is, for all 1 P[l] if and only if T[i+k-1]>T[i+l-1].
      Searching for a pattern P in a text T consists in identifying all occurrences of P in T. We first present a forward
      automaton which allows us to search for P in T in O(m^2log log m +n) time. We then introduce a
      Morris-Pratt automaton representation of the forward automaton which allows us to reduce this complexity
      to O(m\log \log m +n) at the price of an additional amortized constant term by integer of the text. Both
      automata occupy O(m) space. We then extend the problem to search for a set of patterns and exhibit a
      specific Aho-Corasick like algorithm. Next we present a sub-linear average case search algorithm running in
      O((mlog m)/(loglog m)+(nlog m)/(mloglog m)) time, that we eventually prove to be optimal on average.
      Joint work with Djamal Belazzougui (Univ. of Helsinki), Adeline Pierrot (LIAFA) and Stéphane Vialette (LIGM).
    • 15H00: 15h15 Axel Bacher (LIPN)
      Génération aléatoire d’arbres en taille exacte et linéaire en temps et en espace
      - version revue, corrigée et clarifiée -L’algorithme de Rémy revisitéL’algorithme de Rémy engendre aléatoirement un arbre binaire de taille n en O(n) opérations arithmétiques. Je présenterai une variante effectuant seulement O(n) opérations élémentaires en moyenne (bit à bit), et utilise en particulier O(n) bits aléatoires en moyenne.

      Je donnerai une adaptation de l’algorithme engendrant des arbres unaires-binaires, avec aussi une complexité bit-à-bit de O(n).

      Travail en commun avec Olivier Bodini et Alice Jacquot.

  • Jeudi 24 Janvier 2013
    à Jussieu, Salle 211 (55-65)

    • 10h30 Xavier Goaoc (Loria)
      “Simplifying inclusion-exclusion formulas”The classical inclusion-exclusion formula expresses the measure of
      the union of a family of $n$ sets using the measures of the
      intersections of subfamilies. The number of terms in this formula is
      exponential in $n$, and a significant amount of research, originating
      in applied areas, has been devoted to constructing simpler formulas
      for particular families (e.g. sets of balls or halfspaces).We provide the apparently first upper bound valid for an arbitrary
      family: we show that every system of $n$ sets with $m$ nonempty fields
      in the Venn diagram admits an inclusion-exclusion formula with
      $m^{O(\log^2n)}$ terms and with $\pm1$ coefficients, and that such a
      formula can be computed in $m^{O(\log^2n)}$ expected time.

      This is joint work with J. Matousek, Pavel Patak, Zuzana Safernova and
      Martin Tancer.

      http://arxiv.org/abs/1207.2591

    • 11h45 Buffet
    • 14h — 18h Discussions et Groupes de travail
  • Réunion du 29 Novembre 2012 – LIPN
    • 10h30 Brigitte Vallée (GREYC)
      Analyse des arbres digitaux de recherche (DST) sous le modèle d’une source générale.
    • 11h45 Discussion
    • 12h30 Buffet — en commun avec l’ANR COMPLICE — salle A201
    • 14h Alice Jacquot (LIPN)
      Génération aléatoire d’arbres de Motzkin en taille exacte et temps linéaire via générateur de Boltzmann et spécification holonome.
    • 15h30 Nick Beaton – post-doc MAGNUM au LIPN
      Three approaches to polymer adsorption
    • 16h30 Discussion (suite et fin)
  • Jeudi 4 Octobre 2012au LIP6, Jussieu,
    • 10h exposé Julien David
    • 11h discussion sur la plate forme logicielle et des journées sage et programme à venir
    • 12h30 buffet
    • 14h30 exposé Anne
    • 15h30 session ouverte de questions et discussions

    —————
    “Une étude en moyenne des hypergraphes et de leur transversaux minimaux”
    J. David (en collaboration avec L. Lhote, A. Mary, F. Rioult)

    Résumé:
    “Dans cet exposé, on s’intéressera à certaines propriétés des hypergraphes
    et à la complexité moyenne d’algorithmes appliqués aux hypergraphes sous
    plusieurs modèles de probabilité.
    Notre approche est à la fois théorique et expérimentale puisque notre objectif
    est d’obtenir un modèle aléatoire capable de capturer la complexité de données
    réelles.

    Partant d’un modèle généralisant celui d’Erdös-Renyi, nous avons obtenus
    des estimations asymptotiques sur le nombres de transversaux, de minimaux
    et de transversaux minimaux d’un hypergraphe aléatoire.
    On utilise ces résultats pour obtenir la complexité moyenne des algorithmes
    de génération des transversaux minimaux d’un hypergraphe.

    Dans un deuxième temps, on complexifie notre modèle aléatoire afin
    de s’approcher de données réelles.
    Les résultats obtenus sont moins précis mais nous avons pu identifier
    des cas où le nombre de transversaux minimaux est au plus polynomial,
    quasi-polynomial ou exponentiel.

    L’exposé se terminera par des réflexions personnelles et encore
    inachevées sur les questions de génération aléatoire et d’analyse
    pour des modèles non-uniformes.”

    ————

    Minimiser les tresses à 4 brins
    Anne Licheli – LIAFA

    Une tresse à n brins correspond à l’idée intuitive que l’on se fait d’une tresse, c’est-à-dire n brins dont les extrémités sont fixes et qui se croisent entre
    eux. Les tresses forment un groupe, noté Bn, engendré par n-1 générateurs vérifiant des relations. Une tresse peut être représentée par un diagramme de
    tresse, c’est-à-dire une suite de croisements entre les brins de la tresse, chaque générateur correspondant à un croisement de deux brins. Ainsi un
    représentant de longueur minimale d’une tresse est un diagramme parmi les diagrammes représentant la tresse, dont le nombre de croisements est minimal. Le
    problème de minimisation d’une tresse consiste à exhiber un tel représentant de la tresse ou au moins à calculer sa longueur. Lorsque les tresses sont
    positives, on connait leur série génératrice qui est rationnelle. Dans B3, il existe des algorithmes polynomiaux pour résoudre le problème de
    minimisation. Mais pour n>3, aucun algorithme polynomial n’est connu à ce jour. On sait par contre que le problème est NP-complet pour n quelconque. Je
    présenterai un algorithme polynomial pour résoudre le problème dans B4 dont la correction est prouvée moyennant une conjecture très simplement énonçable.
    Ce travail a été effectué en collaboration avec Jean Mairesse (LIAFA) et Dominique Poulalhon (LIX).

  • Mercredi 11 juillet 2012au LIP6, Jussieu, salle 101, 25-26
    • 10h30 : Nicolas Schabanel (LIAFA)
      Universality in Stochastic Cellular Automata
    • 12h Buffet
    • 14h00 : Axel Bacher (LIX)
      TBA
    • 15h00 Discussions
  • Réunion du Jeudi 10 Mai 2012
    • 10H 30 : Ana Busic : Autour de la simulation parfaite
    • 14h Jeremie Lumbroso : Autour des machines de Buffon
  • Réunion du Jeudi 15 Mars 2012

Chevaleret, salle 1D06, LIAFA

10H30 : Guglielmo Paoletti
“Strings and Patches in the Abelian Sandpile Model”
Abstract:

The Abelian Sandpile Model is a simple cellular automaton describing the dynamics of a pile of sand under particle’s addition, which has also been studied under the name of Chip-Firing Game; it presents Self Organized Criticality and seems to display allometry. Here I will show the emergence of 2-dimensional periodic patterns (patches) and 1-dimensional periodic defects (strings). I will present the classification of these objects and the relation between their densities and respective periodicity vector, momentum, reminiscent of a dispersion relation. Strings interact, they can merge and split. In the understanding of the whole structure SL(2,Z) plays a key role, finally bringing to the full determination of particular self-similar Structures.

13H30 : Markus Nebel : Generation Aléatoire Non Uniforme
Abstract:

The random generation of combinatorial objects is useful in many places in
computer science, e.g. in the random testing of programs or for the
estimation of the average case runtime of algorithms that elude a
mathematical analysis. In the Bioinformatics area, random sequences are a
topic of great interest e.g. in genome analysis, since according to a
powerful paradigm, they represent the background noise from which the actual
biological information must differentiate.
However, in many applications the random generation should follow the native
distribution of the objects considered.
In this talk we will show how stochastic context-free grammars can be used
for the random generation of combinatorial objects according to non-uniform
distributions derived from sample data. We will see that both, a fixed size
sampling as well as the more efficient Boltzmann sampling can be performed
on basis of those grammars.

  • Réunion du 17 Novembre 2011, de 10H30 à 17H

10H30 : Yann Ponty (LIX) Un point de vue combinatoire sur la conception et l’unification d’algorithmes pour l’étude du repliement et de l’évolution des ARN [Slides Partie 1] [Slides Partie 2]

Les ARN sont des molécules simple-brin pouvant être assimilés à des séquences sur un alphabet A, C, G et U. Alors que la biologie moléculaire se détache progressivement d’une vision protéo-centrique des mécanismes cellulaires, de nouvelles classes d’ARN fonctionnels sont découverts quasi-quotidiennement grâce à l’émergence de nouvelles technologies de séquençage. Un premier pas vers une compréhension de ces nouveaux ARN consiste à prédire leur repliement, c’est à dire quelle conformation ils adoptent. A cette fin, des modèles d’énergies simplifiés, couplés à des approches algorithmiques efficaces, ont été proposés au cours des trois dernières décennies, construisant sur des abstractions discrètes de l’espace des conformations. Parmi ces représentations simplifiés, la structure secondaire considère uniquement les paires de bases non-croisantes, et est donc analogue à un objet arborescent, ce qui permet la mise en œuvre d’algorithmes efficaces par programmation dynamique. Ces algorithmes permettent ainsi de déterminer en temps polynomial la conformation la plus stable (Minimisation de l’énergie libre, cf Zuker/Stiegler MFold), ou postulent un équilibre thermodynamique, résultant en une distribution de Boltzmann (cf McCaskill) sur l’ensemble des conformations, ce qui permet alors d’extraire des quantités moyennes dans cette ensemble (ex: probabilité d’une paire de base).

Cette présentation synthétisera deux contributions algorithmiques, récemment présentées au conférences WABI’11 and RECOMB’11, qui unifient et étendent ces approches “ensemblistes”, en regardant les problèmes à travers le prisme “analyse d’algorithme dans des distributions pondérées”. Dans une première contribution (travail commun avec C. Saule, LRI), nous considérons des espaces de conformations étendus, contenant certains types restreints de croisements (pseudonoeuds), mais autorisant néanmoins des approches algorithmiques par programmation dynamique pour la minimisation d’énergie. Nous proposons une unification des espaces de conformation précédemment proposés dans la littérature, reposant sur des hypergraphes pondérés. Nous proposons une famille d’algorithmes, de formulation extrêmement simple un fois exprimés dans le formalisme des hypergraphes, et ayant des complexités compétitives avec les propositions antérieures. Nous introduisons une technique de preuve basée sur les séries génératrice pour prouver la validité des décompositions sous-jacentes à ces algorithmes. Enfin nous proposons un algorithme générique pour le calcul des moments généraux (y compris des corrélations) de paramètres additifs dans la distribution de Boltzmann.

Dans une deuxième contribution, nous revisitons, en collaboration avec J. Waldispühl (McGill, Montréal), un modèle d’évolution pour l’ARN, où chaque séquence voisine (à une distance de Hamming donnée) d’une séquence de référence se voit associer une probabilité proportionnelle à sa fonction de partition (Comptage pondéré sur l’ensemble des conformations). Cependant, ce modèle induit une surreprésentation des base G et C (aka contenu en GC) en comparaison avec des séquences d’ARN naturelles, où des contraintes d’environnement interdisent une stabilité trop forte. Pour explorer efficacement des régions de contenu GC prédéterminé, nous avons proposé une stratégie d’échantillonnage adaptatif “à la Boltzmann”. Cette approche a permit un gain algorithmique conséquent, tant théoriquement, comme le prouve une analyse en moyenne dans un modèle “relâché”, qu’empiriquement, par comparaison avec un rejet naïf ou un algorithme de programmation dynamique. De façon plus générale, ces deux contributions soulignent un besoin réel, en bioinformatique en général, d’analyses en moyenne et de la génération aléatoire, dans un contexte où les “bioalgorithmiciens” s’intéressent de plus en plus à la stabilité des prédictions obtenues par des approches d’optimisation (dont la fonction objectif est, par essence, incertaine et entachée d’erreurs). [Slides Partie 1] [Slides Partie 2]

14h00 : Cyril Nicaud (IGM) Quelques exemples d’analyse en modèles non uniformes.

  • Réunion du Jeudi 13 Octobre, de 14H30 à 18H30 à Jussieu, salle 101 tour 25-26

14h30 -15h30 Lucas Gérin : “Introduction aux calculs de temps de mélange”
16h-17h Andrea Sportiello : “Enumeration des automates minimaux et conséquences”
17h15-18h30 discussion

  • Réunion du Jeudi 3 Mars 2011 (10H – 18H)

10h00-11h00 : Modèles combinatoires  (Vlady Ravelomanana – LIAFA)
11h15-12h00 : Organisation : site web, logo, listes de diffusion …  (Frédérique Bassino, Dominique Rossin, Michèle Soria)

14h00-15h00 : Analyse d’algorithmes réalistes (Brigitte Vallée – GREYC)
15h00-15h30 : pause-café
15h30-16h00 : Développement de Logiciels (Yann Ponty – LIX)
16h00-18h00 : Discussions

  • Réunion du Jeudi 4 Novembre 2010 de 14H à 18H.

Cette première réunion comporte la présentation scientifique de deux axes (axes 2 et 3) du projet Magnum. Le programme de cette journée est le suivant:

14H-15H : Génération aléatoire des structures combinatoires complexes par Michèle Soria.

15H-16H : Simulation de système dynamiques discrets aléatoires par Jean Mairesse.

16H-17H : Intervention de Nadia Nadah de l’ANR pour nous présenter le fonctionnement du suivi des projets par l’agence pour la recherche.

  • Réunion Kickoff du Lundi 12 Juillet 2010 à 14H.

Cette réunion a pour objectif de présenter Magnum à l’ensemble des membres et de commencer à mettre en œuvre les différents axes de recherches proposés dans le sujet. Il s’agira en outre de parler de points d’organisation et du périmètre du projet qui vient d’être labellisé par le pôle de compétitivité SYSTEM@TIC.

Leave a Reply