Journée MDSC 2018

Programme de la Journée MDSC 31 Mai 2018

  • 09h30 - 10h00

Accueil Café (Salle des Actes Grand Château Valrose)

  • 10h00 - 10h45

Pattern Matching in discrete Models for Ecosystem Ecology

(Cinzia Di Giusto)
We consider models of ecosystems viewed as collections of interacting living (animals, plants, ...) and nonliving entities (air, water, soil, …),they are modeled as sets of rules expressing the conditions of appearance/disappearance of the entities. Realistic models of ecosystem trajectories usually lead to very large state spaces, not allowing to identify specific processes (e.g., predation or competition patterns) using classical graph-theoretic methods. Hence, it seems relevant to identify such invariant patterns at the rule level, as subsets of rules driving the dynamics. Moreover, these patterns can potentially encode different instances in the same ecosystem model. For example, in an alpine ecosystem, sheep-wolf and grass-sheep entities can both be matched with the same predation pattern. I will present a rule-based method allowing to automatically detect patterns (i.e. ecological processes) in ecosystems. The method relies on a measure of similarity and on an optimization algorithm. On the basis of a similarity between ecosystems (or between an ecosystem and patterns), we automatically identify various patterns in different ecosystem models.

(Slides)

  • 10h45 - 11h00

Nicolas Isoart (Présentation pour concours bourse doctorale)

  • 11h00 - 11h15

Pause

  • 11h15 - 11h30

Laetitia Laversa (Présentation pour concours bourse doctorale)

  • 11h30 - 12h15

Absolute : d’un analyseur statique à un solveur de contraintes

(Marie Pelleau)
La programmation par contraintes permet de formaliser et résoudre des problèmes fortement combinatoires, dont le temps de calcul évolue en pratique exponentiellement. Les méthodes développées aujourd’hui résolvent efficacement de nombreux problèmes industriels de grande taille dans des solveurs génériques. Cependant, les solveurs restent dédiés à un seul type de variables (réelles ou entières) et résoudre des problèmes mixtes discrets-continus suppose des transformations ad hoc. Dan sun autre domaine, l'’interprétation abstraite permet de prouver des propriétés sur des programmes en étudiant une abstraction de leur sémantique concrète, constituée des traces des variables au cours d’un exécution. Plusieurs représentations de ces abstractions, appelées domaines abstraits, ont été proposées. En définissant les domaines abstraits en programmation par contraintes, nous pouvons construire une méthode de résolution traitant indifféremment les entiers et les réels, et utiliser des représentation relationnels.

  • 12h15 - 12h30

Samvel Dersakissian (Présentation pour concours bourse doctorale)

  • 12h30 - 14h00

Pause

  • 14h00 - 14h25

Vers un système de contraintes pour l’analyse des erreurs de précision des calculs sur les flottants

(Remy Garcia)
Vers un système de contraintes pour l’analyse des erreurs de précision des calculs sur les flottants Les calculs sur les nombres flottants induisent des erreurs liées aux arrondis nécessaires à la clôture de l’ensemble des flottants. Ces erreurs sont à l’origine de nombreux problèmes, tels que la précision ou la stabilité de ces calculs. Elles font l’objet de nombreux travaux qui s’appuient sur une surestimation des erreurs effectives. Si ces approches permettent une estimation de l’erreur, estimation qui peut être affinée en découpant l’espace de recherche en sous-domaines, elles ne permettent pas, à proprement parler, de raisonner sur ces erreurs et, par exemple, de produire un jeu de valeurs d’entrée capable d’exercer une erreur donnée. Afin de pallier ce manque et d’enrichir les possibilités d’analyses de ces erreurs de précision, nous introduisons dans un solveur de contraintes sur les flottants un domaine dual à celui des valeurs, le domaine des erreurs. Ce domaine est associé à chacune des variables du problème. Nous introduisons aussi les fonctions de projections qui permettent le filtrage de ces domaines ainsi que les mécanismes nécessaires pour produire des jeux d’essais correspondant à une erreur, voir à long terme, à l’erreur maximale.

(Slides)
 

  • 14h25 - 14h55

Solving the Flight Radius Problem

(Arnaud Malapert)
We present the flight radius problem on the condensed flight network. The problem is derived from a decision tool for airline managers to analyze and simulate a new market. It concerns the network design and visualization when allocating a new flight. The flight radius problem consists in finding routes passing through a specific flight that represent business opportunities regarding time and cost criteria. It is formulated as finding a maximal subgraph of nodes belonging to routes accepted by a regret function. The regret is defined as a function of the optimal values of the time and cost criteria. In practice, the condensed flight network is stored in a graph database neo4j. First, we propose a query based on available procedures in the database. Second, we propose a method that uses the regret function to speed up the successive calls to Dijkstra algorithm. Results on a set of real-world instances with different flights (Hub & Spoke) and regret function parameters demonstrate that the algorithm is more efficient than the query and meet real-world response time constraints.

  • 14h45 - 15h10

Pause

  • 15h10 - 15h40

New perspectives in the reconstruction of convex polyominoes from orthogonal projections

(Lama Tarsissi)
The family of (digitally) convex polyominoes, that are the discrete counterpart of Euclidean convex sets, combines the natural constraints of convexity and connectedness. Several years ago, many researchers in this comunity tried to study their reconstruction. In this talk, I use some results by Brlek.al which allow to express digital convexity by the properties of the words encoding the boundary word of the polyomino. I give some examples to show that, in order to maintain the convexity, the addition of one point or two points imposes the inclusion of other points in the neighbor areas. While the addition of points during the reconstruction process does not influence neighborhood areas only under strong geometrical constraints.

(Slides)

Identification de paramètres dynamiques de réseaux de gènes

  • 15h40 - 16h05

(Jonathan Behaegel)
L'étude des réseaux de gènes nous permet de mieux comprendre certains processus biologiques tels que l'adaptation de l'organisme à une perturbation de l'environnement. Dans le cadre d'une modélisation discrète des réseaux de gènes, il a été montré que la logique de Hoare pouvait aider à l'identification des paramètres du modèle afin que ce dernier exhibe les traces biologiques observées. Nous présentons une modélisation hybride des réseaux de gènes mettant l'accent sur le temps passé dans chacun des états et nous introduisons une extension de la logique de Hoare dans ce cas hybride. Le calcul de la plus faible précondition associé à cette logique de Hoare modifiée permet de déterminer les contraintes minimales sur les paramètres dynamiques d'un réseau de gènes à partir d'une trace biologique observée. Ces contraintes forment un CSP continu que nous résolvons à l'aide du solveur continu AbSolute. Les premiers résultats expérimentaux montrent que les solutions exhibées sont en accord avec les spécifications du triplet de Hoare provenant de l'expertise biologique.

(Slides)

  • 16h10 - 18h00

Réunion d'équipe