9h10 -   9h50 

Jonas Lefèvre
         Algorithmes autostabilisants pour le problème du couplage.

    À partir d'un algorithme préexistant, nous avons construit un algorithme probabiliste autostabilisant qui calcule un couplage maximal dans un réseau distribué anonyme. Il se stabilise en O(n ³) pas de calcul avec probabilité très proche de 1. Nous nous sommes intéressés à un autre algorithme qui calcule une 2/3-approximation d'un couplage maximum. En exhibant une exécution de taille 2 ^{√ n}, nous avons prouvé une borne inférieure sur la complexité de cet algorithme.

  9h50 – 10h10

Pause café

10h10 – 11h00

Mohammed Rezgui
         Parallélisme en programmation par contraintes.

    Nous étudions la parallélisation de la procédure de recherche de solution d'un problème en Programmation Par Contraintes (PPC). Après une étude de l'état de l'art, nous présentons une nouvelle méthode, nommée Embarrassingly Parallel Search (EPS). Cette méthode est basée sur la décomposition d'un problème en un très grand nombre de sous-problèmes disjoints qui sont ensuite résolus en parallèle par des unités de calcul avec très peu, voire aucune communication. Le principe d'EPS est d'arriver statistiquement à un équilibrage des temps de résolution de chaque unité de calcul afin d'obtenir une bonne répartition de la charge de travail. EPS s'appuie sur la propriété suivante : la somme des temps de résolution de chacun des sous-problèmes est comparable au temps de résolution du problème en entier.
    Cette propriété est vérifiée en PPC, ce qui nous permet de disposer d'une méthode simple et efficace en pratique. Dans nos expérimentations, nous nous intéressons à la recherche de toutes les solutions d'un problème en PPC, à prouver qu'un problème n'a pas de solution et à la recherche d'une solution optimale d'un problème d'optimisation. Les résultats montrent que la décomposition doit générer au moins 30 sous-problèmes par unité de calcul pour obtenir des charges de travail par unité de calcul équivalentes.
    Nous évaluons notre approche sur différentes architectures (machine multi-cœurs, centre de calcul et cloud computing) et montrons qu'elle obtient un gain pratiquement linéaire en fonction du nombre d'unités de calcul. Une comparaison avec les méthodes actuelles telles que le work stealing ou le portfolio montre qu'EPS obtient de meilleurs résultats.

11h00 - 12h00

Réunion d'équipe.

12h00 - 14h00

Déjeuner au restaurant l' Union.

14h00 - 14h40

Cinzia Di Giusto
         Activity Networks with Delays: an application into toxicity analysis.

    I will present ANDy, Activity Networks with Delays. It is a discrete time framework aimed to the qualitative modelling of time-dependent activities. Activities involve entities playing the role of activators, inhibitors or products of biochemical network operation. Activities may have given duration, i.e., the time required to obtain results. An entity may represent an object (e.g., an agent, a biochemical species or a family of thereof) with a local attribute, a state denoting its level (e.g., concentration, strength). Entities levels may change as a result of an activity or may decrease gradually as time passes by. The semantics of ANDy is formally given via high-level Petri nets ensuring this way some modularity. The concise and modular syntax of ANDy makes it suitable for an easy and natural modelling of time-dependent (biological) systems. I will conclude with an application of ANDy to the study of toxic behaviours in biological systems. In particular I will present a classification of toxicity properties and give some hints on how they can be verified with existing tools on ANDy systems.

14h40 - 15h20

Bruno Guillon
         Caractérisation algébrique des relations acceptées par transducteurs bidirectionnels unaires.

    Les transducteurs sont des extensions d'automates finis qui sont capable d'écrire des mots sur un ruban de sortie en écriture seule durant leur calcul. Ils reconnaissent donc des relations sur les mots. Les transducteurs unidirectionnels unaires acceptent exactement la classe des relations rationnelles. Cependant, les transducteurs bidirectionnels étendent strictement la puissance calculatoire des transducteurs unidirectionnel, même dans le cas d'alphabets (d'entrée et de sortie) unaires (c'est à dire ne contenant qu'une seule lettre).
    Après avoir introduit le modèle par des exemples simples, je présenterai les grandes lignes d'une construction, basée sur les _crossing sequences_, qui permet d'obtenir une caractérisation des relations acceptées par des transducteurs bidirectionnels dans le cas particulier d'alphabets d'entrée et de sortie unaires. Je discuterai ensuite des extensions et des conséquences de ce résultat.
    ollaboration avec Christian Choffrut.

15h20 - 15h40

Pause café

15h40 - 16h10

Guillaume Perez
         Relations entre MDDs et Tuples et Modifications dynamique de contraintes MDDs.

    Nous étudions les relations entre Multi-Valued Decision Diagrams (MDD) et les tuples (i.e. les éléments du produit cartésien du domaine des variables). D'abord nous améliorons les méthodes existantes pour transformer un ensemble de tuples, des Global Cut Seeds et des séquences de tuples en MDDs. Puis nous présentons plusieurs algorithmes sur place pour ajouter et supprimer des tuples d'un MDD. Ensuite nous considérons une contrainte MDD qui est modifiée durant la recherche en supprimant plusieurs tuples. Nous donnons un algorithme qui adapte MDD-4R à ces modifications dynamiques et persistantes. Plusieurs expérimentations montrent que les contraintes MDD sont compétitives avec les contraintes de table.

16h10 - 16h50

Benjamin Miraglio
         Un langage dédié et une logique pour l'évaluation toxicologique.

    Dans le cadre de la toxicologie réglementaire, l'établissement du seuil de toxicité d'une molécule peut s'avérer très délicat. L'existence même de ce seuil est parfois difficile à prouver alors qu'elle est nécessaire à la commercialisation de la molécule.
    Durant cet exposé, je vous présenterai une ébauche d'un langage à base de règles et d'une sémantique qualitative discrète permettant de modéliser un système biologique. Par ailleurs, une logique dédiée permettra d'exprimer des propriétés d'intérêt toxicologique. Ce langage et cette logique définiront un cadre de travail pour tester si l'introduction de la molécule d'intérêt dans le système mène obligatoirement à un état pathologique ou si cette molécule possède un seuil de toxicité.