Nos tutelles

CNRS

Nos partenaires


Accueil > Actualités > Séminaires > Archives Séminaires

Séminaires passés 2015-2016


- Lamia El Badawi (UdA) et David Hill (Limos - UBP) : L’informatique au coeur de la convergence NBIC (Nanotechnologies, Biotechnologies, Informatique et Cognition) – Le transhumanisme : nouvel humanisme ou dangereuse utopie ?
Jeudi 30 juin 2016 - 14 h 00 - Salle du Conseil - Bâtiment ISIMA

Possibilité de visio-conférence

A l’initiative du département de la défense et des recherches avancées des Etats-Unis (DARPA), un rapport public des départements du commerce (DOC) et des finances (DOF) des Etats-Unis, a donné dès 2002, une impulsion notable en faveur d’une recherche des entreprises sur ce que l’on nomme maintenant la « grande convergence » des NBIC (Nanotechnologies, Biologie moléculaire, Informatique et Cognition). Grâce à cette convergence, une philosophie – le transhumanisme – rêve de changer l’homme, de le modifier, de l’augmenter.

Depuis 2012, le directeur de l’ingénierie de Google est un des leaders mondiaux du transhumanisme.

Ce séminaire sera à 2 voix :

- une présentation de l’état des techniques informatiques au coeur de ce que les spécialistes appellent la grande convergence.
(D. Hill - 20 minutes)
- une présentation de l’origine historique et également du cadre juridique lié à ces transformations.
(L. El Badawi - 30 minutes)

- Martin Heusse - LIG - ENSIMAG - Grenoble : La couche physique de LoRa et ses conséquences
Jeudi 23 juin 2016 - 9 h 00 - Salle du Conseil - Bâtiment ISIMA

Possibilité de visio-conférence

L’exposé commencera par une présentation des principes de la modulation LoRa, à base de chirps, une technique destinée initialement aux radars. L’objectif n’est pas la maîtrise de la couche physique mais de faire ressortir les contraintes associées et les bénéfices qui peuvent en être retirés au niveau réseau. Au niveau de l’Internet des objets, on voit ainsi se rejouer une controverse similaire à celle des réseaux cellulaires avec le remplacement d’une technologie à bande étroite (GSM) par le une technologie large bande (UMTS). Qq minutes seront également consacrées à LoRaWAN qui spécifie les échanges entre les objets et les serveurs en cœur de réseau, via les passerelles.

- Paul-Antoine BISGAMBIGLIA - Universita di Corsica Pasquale Paoli : Le doute en Modélisation et Simulation (M&S) : de la représentation et élaboration des connaissances à la validation des résultats, les apports de la logique flou
Jeudi 16 juin 2016 - 14 h 00 - Salle du Conseil - Bâtiment ISIMA

Possibilité de visio-conférence
@IP : 193.55.95.10
Nom du correspondant technique : Nicolas CHAMPEIL
Tél correspondant technique : 04 73 40 50 15 / 06 78 34 55 26
nicolas.champeil@isima.fr
Tél salle de visio : 04 73 40 50 47

La simulation numérique ou informatique s’est aujourd’hui démocratisée, elle est devenue un outil décisionnel indispensable (aéronautique, météorologie, etc.), mais certains utilisateurs ont trop souvent tendance à considérer les résultats de simulation comme des résultats réels, alors que c’est un modèle et non le système lui-même qui est étudié. Afin d’être utilisable, un modèle ne peut être ni trop complexe (proche de système), ni trop simpliste (construit d’hypothèses). Cette phase de conception, voire de simplification, nous oblige à douter de nos modèles, et donc à vérifier et valider nos résultats. Ces étapes de vérification et de validation (V&V) des modèles et des résultats sont pourtant souvent négligées.
Dans cet exposé, nous souhaitons discuter de la notion de doute dans les différentes phases de la M&S : cette notion est ambiguë, car elle amène à s’interroger aussi bien sur la qualité du code de l’outil, sur la qualité des données, que sur l’expertise de l’utilisateur et même sur celle du modélisateur. La qualité de la connaissance, dans sa globalité, et en particulier sur le système étudié a un fort impact sur les résultats obtenus ou attendus. Dans ce contexte, la conception du modèle, sa contextualisation, son utilisation sont dépendantes de connaissances imparfaites (incertaines, imprécises, vagues, ambigües, contradictoires, etc.). Représenter et manipuler ces types de connaissances, ce doute, le quantifier, n’est pas évident. L’impact de la qualité de la connaissance sur la prise de décision est très important.
Des méthodes issues de la logique floue et de la théorie des sous-ensembles flous permettent de manipuler ces connaissances, et de mesurer et d’évaluer le doute. Cette présentation donne une vue d’ensemble de ces méthodes dictée par nos applications.

- Sabeur ARIDHI (Aalto University, Finland) : Big data analytics : case of big graphs
Vendredi 27 mai 2016 - 14 h 00 - Salle du conseil - Bâtiment ISIMA

Possibilité de visio-conférence

In the last decade, the field of distributed processing of large-scale graphs has attracted considerable attention. This field has been highly motivated, not only by the increasing size of graph data, but also by its huge number of applications. Such applications include social network analysis, Web graph analysis and spatial network analysis. In this talk, I will present some research works related to big data analytics. The talk will focus on big graph-related research works and will consider graph analysis issues and trends including the problem of distributed k-core decomposition in dynamic graphs and the problem of signal recovery on big graphs.

- Kaïs KHROUF (laboratoire MIR@CL, Université de Sfax, Tunisie) : Analyse OLAP des données complexes
Jeudi 19 mai 2016 - 14 h 00 - Amphi B.Garcia - Bâtiment ISIMA

Les systèmes OLAP (On-Line Analytical Processing) ont été proposés pour améliorer le processus de prise de décision par l’analyse de grandes masses de données. Ces données peuvent être issues des sources opérationnelles des entreprises, ou aussi collectées à partir des sources disséminées et hétérogènes (Internet, Workflow, bibliothèques numériques, réseaux sociaux, etc.). Les décideurs souhaitent disposer d’outils leur permettant d’extraire l’information pertinente, à partir de ces données complexes.
Dans ce contexte, nous proposons un nouveau modèle multidimensionnel dédié à l’OLAP de documents XML (appartenant à une même collection). Ce modèle, dit en diamant, est organisé autour d’une dimension centrale qui traduit la sémantique du contenu textuel. Nous avons défini un ensemble de règles heuristiques en vue de la génération quasi-automatique de modèles en diamant.
La détermination de la dimension sémantique se base sur une approche d’annotation automatique des différents granules d’un document XML permettant ainsi d’inférer une structure sémantique par document. Dans nos travaux, nous considérons que la structure sémantique est une structure superposée à la structure logique d’un document XML et qui décrit la sémantique du contenu (en particulier de ses éléments textuels).
Afin de permettre l’analyse OLAP de documents XML hétérogènes (structure et contenu), nous proposons un autre modèle multidimensionnel intitulé modèle en toile d’araignée. Ce modèle se diffère des autres modèles proposés dans la littérature par les spécificités suivantes : Contrainte d’exclusion entre les dimensions, présence de paramètres réflexives, autorisation de dimension dupliquée et de dimensions corrélées.
Dans le but de profiter des données et informations issues des réseaux sociaux (Twitter), nous proposons un modèle multidimensionnel générique réutilisable (c’est-à-dire non dédié à un besoin analytique spécifique) et adapté au caractère dynamique des données des tweets.

Mots-clés : Analyse OLAP, documents XML, structuration sémantique, réseaux sociaux.

- Prof. Mohammed Mohsen Gammoudi, Laboratoire RIADI-GDL, Université de la Manouba (Tunisie) : Méthode de contrôle de violation de sécurité par Inférence dans les bases de données en utilisant l’analyse formelle des concepts
Mercredi 11 mai 2016 - 10 h 30 - Salle du conseil - Bâtiment ISIMA

La spécification d’une politique globale dans un système d’intégration de données d’une manière traditionnelle n’est pas capable de fournir une solution efficace pour résoudre le problème d’inférence en combinant les résultats de requêtes.

Ceci est principalement dû au fait que les dépendances fonctionnelles de données ne sont pas pris en compte lors de la définition des politiques locales (attachées aux sources locales) des bases de données.

Dans cet exposé, en utilisant l’Analyse Formelle des Concepts, nous proposons une méthodologie, en définissant un ensemble d’algorithmes de détection des violations de la sécurité par inférence. En effet, étant donné un ensemble de politiques locales, un ensemble de dépendances et une politique de données globale initiale, nous proposons une méthode qui permet à l’administrateur de la sécurité de reconnaître un ensemble de requêtes de sorte que lorsque leurs résultats sont combinés, elles pourraient conduire à des violations de la sécurité. Nous détectons également l’ensemble des règles supplémentaires qui seront utilisés pour étendre la politique du médiateur afin de bloquer les failles de sécurité.
Mots-clés : Contrôle d’accès, Intégration de données, Problème d’inférence, Base de données.

- Prof. Sadok Ben Yahia, Laboratoire LIPAH, Université de Tunis-El Manar (Tunisie) :Calcul efficace de la stabilité des concepts formels
Mercredi 11 mai 2016 - 11 h 15 - Salle du conseil - Bâtiment ISIMA

L’extraction d’un nombre submergeant de concepts formels, même à partir de contextes de tailles raisonnable, a été un frein pour leur large utilisation dans l’ère des données massives. La mesure de stabilité est une métrique de qualité des concepts formels. Cependant, le calcul de la stabilité est un problème NP-complet.

Dans ce séminaire, nous présentons nos travaux sur le calcul efficace de la stabilité des concepts formels. Nous nous intéressons aussi à ce calcul lorsque les concepts formels sont organisés sous la forme d’un treillis de Galois.

- Prof. Mohand Boughanem, Laboratoire IRIT, Université de Toulouse : Recherche d’Information Sociale
Mercredi 11 mai 2016 - 12 h 15 - Salle du conseil - Bâtiment ISIMA

Social Web (Web 2.0) technologies has enabled people to express their opinions, to share content (photos, blog posts, videos, bookmarks, etc.) ; to connect with other users, either directly or via common interests often reflected by shared content ; to add free-text tags or keywords to content ; users comment on content items.
All these user-generated contents UGC need not only to be indexed and searched in effective and scalable ways, but they also provide a huge number of meaningful data, metadata that can be used as clues of evidences in a number of tasks related particularly to information retrieval. Indeed, these user-generated contents have several interesting properties, such as diversity, coverage and popularity that can be used as “wisdom of crowds” in search process. This presentation will provide some general properties of these data and then briefly lists some search tasks that leverage these data. We will particularly focus on two specific tasks namely microblog search and exploiting UGC to improve a search.

- Jérémie CHALOPIN, Lif - Aix Marseille Université : Jouer au gendarme et au voleur pour approximer l’hyperbolicité
Jeudi 31 mars 2016 - 14 h 00 - Amphi B.Garcia - Bâtiment ISIMA

Dans cet exposé, on considère une variante du jeu du gendarme et et du voleur où les joueurs ont des vitesses différentes. La différence avec la version classique de ce jeu est qu’à chaque étape, le gendarme peut se déplacer le long d’un chemin de longueur au plus s’ et le voleur le long d’un chemin de longueur au plus s (tout en évitant la position du gendarme). Un graphe est (s,s’)-gagnant si un gendarme avec une vitesse s’ a une stratégie pour capturer n’importe quel voleur se déplaçant à vitesse s.
Les graphes delta-hyperboliques sont des graphes qui ressemblent à des arbres d’un point de vue métrique. On présentera quelques unes des nombreuses définitions de l’hyperbolicité.
On présentera ensuite nos résultats reliant le jeu du gendarme et du voleur et l’hyperbolicité du graphe. On montre que si un graphe est delta-hyperbolique, alors il est (2r,r+2delta)-gagnant pour tout r.
Réciproquement, on montre que si un graphe est (s,s’)-gagnant (avec s > s’), alors il est O(s^2)-hyperbolique.
On présentera ensuite un algorithme quadratique basé sur notre approche pour approximer l’hyperbolicité d’un graphe à partir de sa matrice de distance.

(Travail réalisé avec V. Chepoi, P. Papasoglu et T. Pecatte)

- Julien VELCIN (Université Lyon 2) : Modèles de clustering temporel pour la fouille d’opinion dans les médias sociaux
Jeudi 24 mars 2016 - 14 h 00 - Amphi B.Garcia - Bâtiment ISIMA

Les modèles graphiques probabilistes sont devenus très populaires pour traiter les problèmes de classification automatique. Dans cet exposé, je présenterai les travaux réalisés récemment au laboratoire ERIC pour deux problèmes différents de classification non supervisée capables de traiter de données textuelles situés temporellement. Le premier problème que nous avons attaqué s’inspire de modèles probabilistes de topic modeling pour capturer conjointement l’évolution des thématiques et des opinions exprimées dans un corpus de textes. Les résultats obtenus sur des reviews d’Amazon et des articles de presse montrent que notre modèle capture mieux la dynamique globale des opinions. Pour le deuxième problème, nous adaptons un modèle de mélanges au cas temporel afin de trouver un compromis entre la fidélité du modèle au données présentes et un lissage avec les données de la période précédente. Les premiers résultats ont été obtenus dans le cadre du projet ImagiWeb et permettent de suivre l’image exprimée sur Twitter au sujet d’hommes politiques français.

- Eric DUCHENE (LIRIS, UCBL, Lyon) : Jeux combinatoires : théorie générale et illustration sur les graphes
Jeudi 17 mars 2016 - 14 h 00 - Amphi B.Garcia - Bâtiment ISIMA

Les jeux combinatoires sont des jeux à exactement deux joueurs, à information totale, sans hasard ni coalition entre les joueurs. S’ils existent depuis très longtemps, on constate très peu de travaux concernant leur résolution dans la littérature précédent la première moitié du 20ème siècle. La première théorie mathématique permettant de bien les comprendre est apparue dans les années 1970 avec les travaux de Conway. Dès lors, une communauté très active est née, et aujourd’hui, les problèmes les plus difficiles concernent les jeux à score (type Othello ou Dots and Boxes) ou encore les jeux en version misère (càd celui qui joue le dernier coup gagne).

Par ailleurs, ces jeux présentent l’intérêt d’être un domaine d’application pour de nombreux autres, comme la théorie des graphes, la théorie des nombre, la combinatoire des mots ou encore l’intelligence artificielle. Dans cet exposé, j’aborderai dans un premier temps la jolie théorie de Conway en l’illustrant sur le jeu Domineering. Puis je m’attarderai sur les différentes variantes du jeu de Nim dans les graphes pondérés (règle simple : on enlève du poids et on se déplace sur un sommet voisin), en présentant les principaux résultats de complexité connus sur le sujet.

- Arnaud Sangnier Liafa (Univ. Paris Diderot) : Parameterized verification of Networks with (selective) broadcast
Mardi 15 mars 2016 - 14 h00 - Salle du Conseil - Bâtiment ISIMA

Possibilité de visio-conférence

We study decision problems for parameterized verification of a formal model of networks with broadcast communication in which the number of participants as the communication topoloby are paramters. The configuration of such a model can be represented thanks to graphs where nodes are labelled with states of individual processes. Adjacent nodes represent single-hop neighbors. Processes are finite state automata that communicate via broadcast messages. Reception of a broadcast is restricted to single-hop neighbors. We show that for such a model simple reachability questions are undecidable, but that decidability can be regained by either restricting the set of topologies or by allowing some processes not to receive the emitted messages. Finally, we consider verification problem under local strategies, where we assume that each process in the network behaves the same according to its past.

- Radu CIUCANU (Oxford University) : Learning Path Queries on Graph Databases
Jeudi 10 mars 2016 - 14 h 00 - Salle du Conseil - Bâtiment ISIMA

We investigate the problem of learning graph queries by exploiting user examples. The input consists of a graph database in which the user has labeled a few nodes as positive or negative examples, depending on whether or not she would like the nodes as part of the query result. Our goal is to handle such examples to find a query whose output is what the user expects. This kind of scenario is pivotal in several application settings where unfamiliar users need to be assisted to specify their queries. In this paper, we focus on path queries defined by regular expressions, we identify fundamental difficulties of our problem setting, we formalize what it means to be learnable, and we prove that the class of queries under study enjoys this property. We additionally investigate an interactive scenario where we start with an empty set of examples and we identify the informative nodes i.e., those that contribute to the learning process.
Then, we ask the user to label these nodes and iterate the learning process until she is satisfied with the learned query. Finally, we present an experimental study on both real and synthetic datasets devoted to gauging the effectiveness of our learning algorithm and the improvement of the interactive approach. Joint work with Angela Bonifati and Aurélien Lemay.
==========================
Bio :
Radu Ciucanu is a postdoc in the database group of the University of Oxford, UK. Previously, he was a PhD student at the University of Lille 1 and INRIA, and a visiting student at the University of Toronto, Canada. He worked on complexity problems related to learning queries and schemas, on data integration, and he is currently working on factorized databases. His research led to publications in conferences like VLDB and EDBT, as well as in the journals ACM Transactions on Database Systems and Theory of Computing Systems. More details at http://www.cs.ox.ac.uk/people/radu.ciucanu/

Jean-Pierre DUSSAULT (Professeur à l’Université de Sherbrooke, Canada) : Présentation unifiée d’algorithmes de région de confiance et d’une nouvelle variante de ARC nommée ARCq
Jeudi 18 février 2016 - 14 h 00 - Salle du Conseil - Bâtiment ISIMA

Le récent algorithme ARC possède une propriété remarquable, une complexité en pire cas optimale. Après une mise en contexte sur les notions de vitesse de convergence et de complexité en pire cas, nous présentons un point de vue unifié des méthodes de région de confiance et de régularisation cubique adaptative (ARC). Bien que les liens entre ces deux familles aient été mentionnés dans l’article qui introduit ARC, nous poussons plus loin l’analogie et en déduisons une démonstration de convergence globale plus simple et unifiée. Nous soulignons également les faits importants de la complexité en pire cas qui s’avère optimale pour notre nouvelle variante ARCq, mais pas pour les algorithmes de région de confiance. ARCq, se prête bien à des implémentations efficaces et nous en présentons deux, une matricielle de type Cholesky et une itérative basée sur des algorithmes de type Krylov ; cette dernière variante peut résoudre des problèmes de très grande taille. Quelques illustrations numériques seront également présentées.

- Vincent DESPRES (Laboratoire GIPSA, Grenoble) : Calcul du nombre geometrique d’intersections des courbes.
Jeudi 11 février 2016 - 14 h 00 - Salle du Conseil - Bâtiment ISIMA

Le nombre geometrique d’intersections d’une courbe C est le nombre minimum d’auto-intersections parmi toutes les courbes qui peuvent être obtenues par homotopie (déformations continues) à partir de celle ci. Le problème a été largement étudié dans la communauté mathématique et plusieurs de ces travaux sont de nature algorithmique. Malheureusement, leur utilisation n’est pas toujours possible directement et, pour la plupart, ils ne s’appliquent que dans un cadre particulier. Nous décrivons des algorithmes simples et généraux qui nous permettent de résoudre le problème en temps O(n+l^2) où l est la longueur de C et n est la complexité de S.

- Nicolas NISSE (INRIA Sophia-Antipolis, Laboratoire I3S) : Recovery of disrupted airline operations using k-Maximum Matching in Graphs
Jeudi 28 janvier 2016 - 14 h 00 - Salle du Conseil - Bâtiment ISIMA

When an aircraft is approaching an airport, it gets a short time interval (called slot) that it can use to land. If the landing of the aircraft is delayed (because of bad weather, or if it arrives late, or if other aircrafts have to land first), it looses its slot and Air traffic controllers have to assign it a new slot. However, slots for landing are a scare resource of the airports and, to avoid that an aircraft waits too much time, Air traffic controllers have to regularly modify the assignment of the slots of the aircrafts. Unfortunately, for legal and economical reasons, Air traffic controllers can modify the slot-assignment only using two kind of operations : either assign to aircraft A a slot that was free, or give to A the slot of another aircraft B and assign to B a free slot. The problem is then the following. Let k >= 1 be an odd integer and let G be a graph and M be a matching (set of pairwise disjoint edges) of G . What is the maximum size of a matching that
can be obtained from M by using only augmenting paths of length at most k ? Moreover, how to compute such a maximum matching ? This problem has already been studied in the context of wireless networks, mainly because it provides a simple approximation for the classical matching problem. We prove that this problem can be solved in polynomial-time when k <=> =4 the problem is NP-complete in planar bipartite graphs with maximum degree at most 3 .

- Jerry Lonlac (LIMOS) Résolution du problème de la Satisfiabilité en logique propositionnelle (SAT)
Mardi 12 janvier 2016 - 14 h 00 - Amphi B.Garcia - Bâtiment ISIMA

Le problème SAT (une formule propositionnelle donnée sous forme normale conjonctive admet-elle une valuation qui la rende vraie ?) est un problème fondamental en théorie de la complexité. Il est aujourd’hui utilisé dans de nombreux domaines comme la bio-informatique, la cryptanalyse, la planification, la vérification de matériels et de logiciels. En dépit d’énormes progrès observés ces dernières années dans la résolution pratique de SAT grâce à la puissance des démonstrateurs SAT, la preuve de la satisfiabilité ou de l’insatisfiabilité de plusieurs problèmes reste un défi intéressant. En effet, de nombreux problèmes industriels restent hors de portée de tous les démonstrateurs SAT contemporains. Ainsi, il existe encore une forte demande d’algorithmes efficaces pouvant permettre de résoudre ces problèmes difficiles.
Dans la première partie de cet exposé, nous présentons une méthode de résolution basée sur une technique de substitution dynamique de fonctions booléennes (dépendances fonctionnelles entre variables) détectées lors d’une phase de pré-traitement. Cette approche permet de mimer de façon élégante la résolution étendue un des plus puissants systèmes de preuve par résolution. Les dépendances fonctionnelles exploitées correspondent à celles introduites lors de la phase d’encodage CNF grâce à l’application du principe de Tseitin.
Dans la deuxième partie, nous nous intéressons à un autre composant des démonstrateurs SAT modernes, à savoir la stratégie d’élimination des contraintes (clauses) apprises déduites par résolution à chaque conflit. En effet, Le nombre des ces clauses croît de manière exponentielle rendant nécessaire d’éliminer régulièrement certaines, jugées non pertinentes. Dans ce cadre, nous revisitons quelques stratégies efficaces de gestion des clauses apprises. Nous proposons également de nouvelles stratégies originales combinant de manière astucieuse la longueur des clauses et la randomisation afin d’éliminer les clauses non pertinentes au cours de la résolution. Ces différentes stratégies sont conçues en considérant qu’une clause est pertinente pour la suite de la recherche si elle est courte et implique des variables affectées en haut de l’arbre de recherche.

- M. Sang Il Oum (KAIST, Corée) Variants of Hadwiger’s conjecture
Mardi 15 décembre 2015 - 13h30. Amphi B.Garcia - Bâtiment ISIMA

Hadwiger conjectured that every graph with no K_t minor is (t-1)-colorable ; in other words, every graph with no K_t minor admits a partition of its vertex set into t-1 independent sets. This conjecture is still widely open and if true, it implies the four color theorem.
Gerards and Seymour made a stronger conjecture claiming that every graph with no K_t odd minor is (t-1)-colorable, commonly called the odd Hadwiger’s conjecture.

We prove variants of Hadwiger’s conjecture. First, we prove that every graph with no K_t minor admits a partition of its vertex set into t-1 sets, each inducing a subgraph of bounded maximum degree. Secondly, we prove that every graph with no K_t minor admits a partition of its vertex set into 3(t-1) sets, each inducing a subgraph having no large components.
We also prove variants of the odd Hadwiger’s conjecture as follows : Every graph with no odd K_t minor admits a partition of its vertex set into 7t-10 sets, each inducing a subgraph of bounded maximum degree.
As a corollary, we prove that every graph with no odd K_t minor admits a partition of its vertex set into 28t-40 sets, each inducing a subgraph with no large components. The last result improves the result of Kawarabayashi, who showed it with 496t sets.
This talk is a combination of three works ; first with K. Edwards, D. Kang, J. Kim, and P. Seymour, second with C. Liu, and third with D. Kang.

- Catherine AARON (Laboratoire de mathématiques - UBP) : quelques problèmes d’inférence géométrique.
Jeudi 26 novembre 2015 - 14 h 00 - Amphi Bruno GARCIA - Bâtiment ISIMA

L’inférence géométrique consiste, a partir de l’observation de $n$ points tirés aléatoirement sur un "ensemble", a estimer cet ensemble ou tester des hypothèses sur cet ensemble.
Dans cet exposé on donnera une réponse a la question suivante : peut on considérer que l’ensemble est convexe ?
On montrera ensuite qu’on peut estimer l’ensemble comme une union de "petites" enveloppes convexes.
Puis on présentera une méthode permettant d’identifier les points proches du "bord" de l’ensemble.
Enfin, si il reste du temps on montrera comment répondre a de telles questions a partir d’une sous triangulation de la triangulation de Delaunay.

-  Alexandre AUSSEM (LIRIS - Univ. Lyon 1) : Réseaux bayésiens & Inférence causale
Jeudi 19 novembre 2015 - 14 h 00 - Amphi B. Garcia - Bâtiment ISIMA

Au cours de cet exposé, je présenterai les applications des modèles graphiques probabilistes à la prédiction, à l’inférence causale, à la correction des biais de confusion et de sélection, à l’élucidation de certains paradoxes (et controverses) sur lesquels les statisticiens et les chercheurs en sciences sociales ont buté au 20e siècle. J’évoquerai également comment l’inférence causale a permis de faire la lumière sur des litiges juridiques portant sur la discrimination sexuelle à l’embauche et au recrutement.

-  Alexandre BAZIN (post-doc LIMOS) : Calculer la base canonique d’implications - influence de l’ordre.
Jeudi 22 octobre 2015 - 14 h 00 - Salle du conseil - Bâtiment ISIMA

Les implications de la forme A->B présentes dans un ensemble de données objet-attributs étant trop nombreuses, on cherche à en isoler un sous-ensemble sans perte d’information appelé base. La plus petite de ces bases, la base canonique, peut être calculée en énumérant les ensembles d’attributs dits pseudo-fermés. Ce problème, bien que beaucoup étudié, présente toujours des zones d’ombre, notamment au sujet de l’influence de l’ordre sur la complexité de l’énumération. Nous expliquerons en quoi l’ordre est important et présenterons des résultats concernant deux catégories d’ordres importantes.

- Imed KACEM (Université Paul Verlaine - Metz (UPVM) : Approximation algorithms for maximizing the weighted number of early jobs on a single machine with non-availability intervals.
Jeudi 8 octobre 2015 - 14 h 00 - Salle du conseil - Bâtiment ISIMA

Possibilité de visio-conférence

@IP : 193.55.95.10
Nom du correspondant technique : Nicolas CHAMPEIL
Tél correspondant technique : 04 73 40 50 15 / 06 78 34 55 26
nicolas.champeil@isima.fr
Tél salle de visio : 04 73 40 50 47

In this talk we consider the maximization of the weighted number of early jobs on a single machine with non-availability constraints. We deal with the resumable and the non-resumable cases. We show that the resumable version of this problem has a fully polynomial time approximation scheme (FPTAS) even if the number of the non-availability intervals is variable and a subset of jobs has deadlines instead of due dates. For the non-resumable version we remark that the problem cannot admit an FPTAS even if all due dates are equal and only one non-availability interval occurs. Nevertheless, we show in this case that it admits a polynomial time approximation scheme (PTAS) for a constant number of non-availability intervals and arbitrary due dates.

REFERENCE : Imed KACEM, Hans KELLERER, Yann LANUEL. Journal of Combinatorial Optimization, October 2015, Volume 30, Issue 3, pp.403-412.

- Jean-Florent RAYMOND (LIRMM, Université Montpellier II et Faculty of Mathematics, Informatics and Mechanics, Université de Varsovie) : The Erdős-Pósa property : from combinatorics to algorithms.
Jeudi 24 septembre 2015 - 14 h 00 - Salle A104 - Bâtiment ISIMA

Pas de visio-conférence

A class of graphs F has the Erdős-Pósa property if the cardinalities of a covering and a packing of F satisfy a loose min-max relation in
any graph. A simple example is the Erdős-Pósa theorem, which state that the class of cycles has this property : every graph contains k
vertex-disjoint cycles, or has O(k log k) vertices covering every cycle, for every positive integer k. There are two variants of the
Erdős-Pósa property : one where packings must be vertex-disjoint and where a cover is a set of vertices, and the edge-version defined similarly
by replacing every occurrence of "vertex" by "edge".

In this talk, I will show how this purely combinatorial property can be used in the design of approximation algorithms. More precisely,
I will consider the class of graphs which contract to the multiedge ofmultiplicity r, and show that the problems of maximum packing and
minimum covering of graphs from this class admit a O(log OPT)-approximation algorithm. This result holds for both the vertex and edge version
and improves the previous O(log n)-approximation of Joret et al., 2011 for the vertex version. The proof relies on a protrusion-based reduction
and on a combinatorial lemma stating that a reduced graph contains a large packing.

This is joint work with Dimitris Chatzidimitriou (University of Athens), Ignasi Sau (LIRMM CNRS) and Dimitrios Thilikos (LIRMM CNRS and
University of Athens).

-  Guilherme D. DA FONSECA - MC LIMOS : Linear-Time Approximation Algorithms for Geometric Intersection Graphs.
Jeudi 17 septembre 2015 - 14 h 00 - Amphi B. Garcia - Bâtiment ISIMA

Pas de visio-conférence

Joint work with Vinícius G. Pereira de Sá and Celina M. H. de Figueiredo. Submitted for journal publication with conference version at WAOA 2014.

Numerous approximation algorithms for problems on geometric intersection graphs have been proposed in the literature, exhibiting a sharp trade-off between running times and approximation ratios. We introduce a method to obtain linear-time constant-factor approximation algorithms for such problems. To illustrate its applicability, we obtain results for three well-known optimization problems on two classes of geometric intersection graphs. Among such results, our method yields linear-time (4+ε)-approximations for the maximum-weight independent set and the minimum dominating set of unit disk graphs, thus bringing dramatic performance improvements when compared to previous algorithms that achieve the same approximation ratios.

-  Dr. Frederic ANDRES (National Institute of Informatics, Tokyo, Japan) : Challenges and Opportunities with Big Data Visualization.
Jeudi 8 octobre 2015 - 11 h 00 - Salle du Conseil - Bâtiment ISIMA

In this talk, I will review the challenges and opportunities in big data visualization and point out some current approaches and visualization tools. In this big data era, huge amount data are continuously acquired for a variety of purposes. Advanced computing, imaging, and sensing technologies enable scientists to study natural and physical phenomena at unprecedented precision, resulting in an explosive growth of data. It is a huge challenge to visualize this growing data in static or in dynamic form. Most traditional data visualization approaches and tools can’t support at “big” scale.