2014


Retour à la vue des calendrier
Mardi 1 Juillet
Heure: 12:00 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Branch-and-Price for the relaxed clique Partitioning and Covering Problems
Description: Roberto Wolfler Calvo Relationships between objects can be modeled with graphs, where nodes
represent the different objects and edges express the relationship.
Social network analysis is an example where clusters, e.g., formed by
members of a community, are studied using cliques and clique
relaxations. A clique is a subgraph with pairwise directly connected
nodes, i.e., a subgraph with diameter one. Several relaxations have been
defined either in terms of distance (k-clique), degree (k-plex, k-core),
diameter (k-club), or density. The majority of the literature deals with
identifying such subgraphs of maximum cardinality or weight. In this
presentation, we consider the generic problem of covering or
partitioning a graph with a set of relaxed cliques. We present an exact
solution fromework for solving the relaxed clique partitioning and
covering problems based on branch-and-price. Herein, the subproblem
consists of finding a relaxed clique of maximum weight. We present
heuristics and a new combinatorial branch-and-bound algorithm for its
resolution.

This is a join work with Fabio Furini and Stefan Irnic.
Mercredi 2 Juillet
Heure: 10:45 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Marcel-Paul Schützenberger et les monoïdes
Description: Gérard Duchamp Marcel-Paul Schützenberger était un fan du monoïde plaxique et aussides monoïdes de commutation : souvenirs et réminiscences.
Heure: 10:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: journée 'combinatoire et théorie des langages' à Paris 13 (et clôture de cette année de séminaires CALIN !)
Heure: 11:00 - 14:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Quelques résultats de 'combinatoire-théorie des langages' récents ou anciens ou futurs !
Description: CALIN
Heure: 11:30 - 14:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Systèmes sofiques-Dyck et fonctions zêtas
Description: Marie-Pierre Béal Les systèmes dynamiques symboliques sont des suites bi-infinies de symbolesdont les facteurs finis évitent un ensemble de mots finis donné. Nousprésentons les systèmes appelés sofiques-Dyck. Ces systèmes sont unegénéralisation des systèmes Markov-Dyck introduits par Krieger etMatsumoto. Nous montrons que ces systèmes de séquences sont exactement lessystèmes dont le langage des facteurs finis est un langage de motsimbriqués (nested words). Nous calculons la fonction zêta, qui compte lesséquences périodiques du système, pour un système sofic-Dyck.(Travaux avec Michel Blockelet et Catalin Dima)
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Machines de Lukasiewicz
Description: Julien David Dans cette présentation, on s'intéressera à deux sujets a priori distincts.
Le premier concerne la génération aléatoire d'arbres planaires dans
lequel on maîtrise le nombre d'occurrences d'un motif d'arbre.
Le but est, partant d'un motif donné, de produire automatiquement
une grammaire d'arbre dans laquelle les occurrences du motif sont marqués.
Cette grammaire permet directement d'obtenir un générateur aléatoire
en utilisant la méthode récursive, mais permet également d'obtenir
une série génératrice bivariée.

Le second est une présentation d'une famille de grammaires d'arbres
et des automates qui y sont associés, appelés machines de Lukasiewicz.
Cette famille fut utilisé pour résoudre le premier problème.
Il s'agit d'une généralisation des grammaires d'arbre régulières.
Si ces grammaires et les machines associés ont des propriétés de clôtures décevantes,
on a pu décrire un algorithme de minimisation pour les machines déterministes.
Heure: 14:45 - 17:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Génération aléatoire via les langages temporisés
Description: Nicolas Basset A chaque langage régulier, on associe la classe (appelée régulière) de permutations ayant un motif d'ascentes/descentes (a/d) dans ce langage régulier de {a,d}*. Par exemple, on peut définir ainsi les permutations alternantes, lespermutations n'ayant pas deux descentes consécutives, les permutations ayant un nombre pair dedescentes... J'expliquerai un algorithme qui étant donné un automate renvoie une formule closepour la série génératrice exponentielle de la classe régulière de permutations associée. J'expliqueraiensuite un algorithme qui permet de générer des permutations aléatoirement et de façon uniformeles permutations de même longueur de la classe régulière de permutations considérée. Les deuxalgorithmes sont basés sur une correspondance entre comptage de permutations et volumes delangages temporisés qui s'explique en terme de polytopes d'ordre et polytopes de chaîne de Stanley.Les deux algorithmes évoqués ci-dessus sont ainsi obtenus à partir d'algorithmes de calculde fonction génératrice des volumes et de génération aléatoire de mots temporisé associés à unautomate temporisé.
Mardi 16 Septembre
Heure: 12:00 - 13:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Lexicographical polytopes
Description: Michele Barbato Within a fixed integer box of R^n, the lexicographical polytopes are the convex hulls of the integer points that are lexicographically between two given integer points. We prove that, together with the bounds, the linear inequalities that arise naturally when characterizing those points suffice to describe these polytopes. As a consequence, this family of integer polytopes is closed by intersection.
Beside, we prove that lexicographical polytopes are precisely the superincreasing knapsacks described by Gupte. Our contribution is to provide significantly simpler and shorter proofs.
This is a joint work with Roland Grappe, Mathieu Lacroix and Clément Pira.
Mardi 23 Septembre
Heure: 12:00 - 13:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Vérification distribuée par exploration d'un espace de paramètres
Description: Camille Coti Dans cet exposé, je présenterai un travail effectué avec Étienne André et Sami Evangelista portant sur la parallélisation d'un algorithme de vérification par exploration d'un espace de paramètres dans le but d'établir un ensemble de contraintes.

Ces contraintes forment un pavage de cet espace de paramètres par des polyèdres irréguliers. La parallélisation de cette exploration ne peut alors pas s'effectuer en utilisant une décomposition de domaine classique, du fait du caractère irrégulier des polyèdres obtenus. Nous avons implémenté et évalué deux heuristiques de décomposition du calcul entre les processus parallèles et examiné leurs performances.

Ce travail a été présenté à la conférence EuroMPI/Asia 2014.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: soutenance de thèse
Description: Nguyen Nghia Hoang
Lundi 29 Septembre
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Peuplement d'ontologies par des techniques de TAL
Description: Frédérik Bilhaut La société NOOPSIS, éditeur de logiciels de "text-mining" et "knowledge management" issu du laboratoire GREYC en 2008, vient présenter des expérimentations réalisées dans le domaine du "Knowledge Base Population" (KBP). Le cadre général de ces travaux est l'utilisation de modèles linguistiques et sémantiques permettant d'instancier automatiquement des bases de connaissances au format RDF du W3C. Nous nous intéresserons principalement au sujet de l'instanciation de ressources et de prédicats par la reconnaissance d'entités et la "tripletisation" de procès linguistiques. Les techniques de TAL employés impliquent la reconnaissance d'entités et surtout une analyse syntaxico-sémantique de différents phénomènes prédicatifs. Nous évoquerons également des problématiques connexes comme l'identification automatique de classes, ou encore des questions liées à la représentation des procès dans le modèle RDF. L'objectif de la rencontre est d'exposer des applications pratiques de ces méthodes et leurs modalités d'implémentation, d'identifier des pistes potentielles de collaboration, et si possible de discuter les pistes à suivre.
Mardi 30 Septembre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Polynomials invariants on stranded graphs
Description: Joseph Ben Geloun Tutte polynomial is a 2-variable polynomial defined on a graph whichsatisfies a contraction/deletion recurrence relation. This polynomialgeneralizes into the so-called Bollobas-Riordan (4-variable) polynomial forribbon graphs which also satisfies a similar recurrence rule. In the recentPhysics literature, there exists a growing interest for a new category ofgraphs called rank d stranded graphs. Such graphs encompass simple andribbon graph structures and represent simplicial complexes in any dimensiond. I will introduce a genuine 7-variable polynomial on these graphstructures when restricted in rank 3 and when provided with a specificcoloring. The polynomial satisfies a new contraction/cut rule. The procedurecan be certainly extended in any rank.