Links' Seminars and Public Events | ![]() ![]() |
Fri, March 9, 2018 10:00 am 11:00 am | Benjamin Bergougnoux : Counting minimal transversals of hypergraphs A transversal of a hypergraph H is a subset of vertices that intersects all the hyper-edges H. The enumeration and the counting of the minimal transversals have a lot of applications in many domains (graph theory, AI, datamining, etc). Counting problems are generally harder than theirs associated decision problems. For example, finding a minimal transversal is doable in polynomial time but counting them is #P-complet (the equivalent of NP-complet for counting problems). We have proved that we can count the minimal transversals of any beta-acyclique hypergraph in polynomial time. Our result is based on a recursive decomposition of the beta-acyclique hypergraph founded by Florent Capelli and by the introduction of a new notion that generalize the minimal transversals. A lot of exciting open questions live in the neighborhood of our result. In particular, our algorithm is able to count the minimum dominating set of a strong-chordal graph. But counting the minimum dominating set is #P-complete on split graphs. Is it the beginning of a complete characterization of the complexity of counting minimal dominating sets in dense graphs ? Salle B21 |
Fri, February 16, 2018 10:30 am 11:30 am | Victor Marsault : Formal semantics of the query-language Cypher Cypher is a query-language for property-graphs. It was originally designed and implemented as part of the Neo4j graph database, and it is currently used by several commercial database products and researchers. The semantics of Cypher queries is currently described using natural language and, as a result, it is often not well defined. This work is part of a project to define a full denotational semantics of Cypher queries. The talk will first present the main features of Cypher through examples, including the core mecanism: graph pattern-matching, and then will describe the formal semantics in its current state. Salle B21 - INRIA Institut National Recherche Informatique Automatique; 40 Avenue Halley, 59650 Villeneuve d'Ascq, France |
Wed, January 31, 2018 5:30 pm 7:00 pm | Bien avant l'avènement des ordinateurs personnels, de l'internet et des smartphones , l'Interaction Homme-Machine (IHM) était déjà une préoccupation au cœur de certaines des visions qui ont contribué à forger l'informatique moderne, qu'elle soit personnelle ou professionnelle. Pour autant, la conception et l'étude des interactions est encore souvent considérée comme secondaire dans la conception des systèmes, la priorité étant souvent mise sur le développement des fonctionnalités plutôt que sur les moyens pour les utiliser. Cette situation s'est progressivement améliorée, avec notamment l'avènement des dispositifs tactiles (smartphones et tablettes) ou de divertissement (consoles de jeux) pour lesquels l'argument de simplicité d'utilisation a détrôné celui de la puissance intrinsèque. Cela a bien évidemment permis de populariser et démocratiser l'accès à la technologie. Mais une conséquence est, selon nous, un relatif appauvrissement des possibilités offertes par ces technologies paradoxalement plus puissantes que jamais. En masquant la complexité plutôt qu'en aidant à la maîtriser, en entretenant le mythe qu'avec ces dispositifs il est aisé pour chacun de faire beaucoup sans efforts, la tendance est à sacrifier le potentiel de l'outil informatique et la performance des utilisateurs pour la rapidité de prise en main, sans permettre un usage plus avancé, plus performant, et peut-être plus gratifiant pour l'utilisateur. Cet équilibre entre simplicité d'usage et puissance de l'outil est un compromis difficile à trouver, et c'est selon nous un des défis et une difficulté majeure de l'IHM : observer et comprendre les phénomènes sensorimoteurs et psychomoteurs, cognitifs, sociaux et technologiques mis en œuvre lors de l'interaction entre des personnes et des systèmes afin d'améliorer cette interaction et d'en guider la conception pour encapaciter les utilisateurs. Le but étant finalement de leur permettre de réaliser ce qu'il leur serait impossible de faire sans cet outil, même si cela requiert de leur part des efforts certains d'apprentissage. Dans ce séminaire, nous commencerons par présenter ce qu'est l'Interaction Homme-Machine en tant que domaine de recherche avec ses objectifs, ses méthodes et ses pratiques. Ensuite, au travers d'une brève histoire de l'informatique sous le prisme de l'interaction, nous évoquerons quelques innovations d'aujourd'hui qui découlent des visions de pionniers du domaine, en considérant notamment ce compromis simplicité / puissance de l'outil. Nous verrons aussi avec des exemples et contre-exemples issus de nos environnements numériques actuels, ainsi qu'avec des travaux de recherche récents, que ces visions portent encore de nombreux défis présents et futurs de l'IHM. En particulier, nous conclurons en discutant de la nécessité d'adopter une approche centrée utilisateur et interaction à l'heure des grands défis scientifiques, technologiques et sociétaux du numérique tels que la conception des systèmes autonomes ou le traitement et l'exploitation automatique des données. Mots-clés : Machines et langages Algorithme Interaction Homme machine (IHM). Liliad |
Wed, January 31, 2018 4:00 pm 5:30 pm | Cours extérieur de Gérard Berry du Collège de France Le centre Inria Lille - Nord Europe reçoit Gérard Berry, du Collège de France pour son cours sur la photographie numérique. Ce cours se prolongera par un séminaire de Stéphane Huot, responsable de l'équipe Mjolnir. Cette manifestation sera suivie d'un cocktail au cours duquel Isabelle Herlin, directrice du centre de recherche Inria Lille - Nord Europe présentera ses voeux. Date : 31/01/2018 Lieu : Lilliad, Campus Université Lille - sciences et technologies - 2 avenue Jean Perrin, Villeneuve d'Ascq Programme 15h30 : Accueil 15h45 : Introduction par Isabelle Herlin 16h - 17h30 : Cours de Gérard Berry, "La photographie numérique, un parfait exemple de la puissance de l'informatique" 17h30 - 18h30 : Séminaire de Stéphane Huot, "Interaction humain-machine : passé composé et futur simple... ou l'inverse" 18h30 - 18h45 : Questions aux deux orateurs 19h - 20h30 : Cocktail Cours de Gérard Berry Bio express : Gérard Berry est informaticien, professeur au Collège de France où il est titulaire de la chaire d'Algorithmes, machines et langages. Résumé L’appareil photo numérique est un excellent exemple de l’évolution actuelle des systèmes cyberphysiques, c’est-à-dire des systèmes couplant intimement mécanique, physique, électronique et logiciel. C’est aussi un exemple merveilleux et accessible à tous de la puissance des méthodes de l’informatique par rapport à celles de la physique et de la mécanique seules. Le cours présentera la panoplie des algorithmes embarqués dans les appareils photos modernes et dans les logiciels de postproduction, puis discutera l’impact majeur qu’ils ont sur la conception des appareils et des objectifs, totalement bouleversée en ce moment, et celui qu’ils ont sur les photographes professionnels ou amateurs. La photographie argentique, fort ancienne, n’a que lentement progressé au cours du XXe siècle : amélioration lente des pellicules et papiers, introduction de l’exposition automatique calculée analogiquement à partir de cellules photo-électriques, visée télémétrique ou reflex, tout cela a demandé des dizaines d’années. Au contraire, à partir de la commercialisation du premier appareil numérique en 1990, la photographie numérique a évolué extrêmement vite. En 2003, on trouvait déjà des appareils semi-professionnels corrects et, dès 2009, des appareils reflex de haute qualité à un prix abordable. Maintenant, il existe toute une panoplie d’appareils de tailles variées, tous capables de fournir des images de grande qualité. Même les téléphones sont devenus de très bons appareils photos et caméras vidéo, principalement grâce aux algorithmes qu’ils mettent en œuvre. Comme ils savent faire bien d’autres choses, par exemple envoyer immédiatement les images sur Internet, ils sont en train de remplacer les anciens petits appareils compacts et de servir d’équipement unique pour les photographes occasionnels et pour tous dans les pays où la photo argentique était d’un coût inabordable pour les habitants. La logique de la photo numérique est ainsi devenue très différente de celle de l’argentique, ce qui n’empêche cependant pas que cette dernière garde toujours les faveurs de certains artistes. Qu’est-ce qui a permis cette révolution et pourquoi est-elle allée aussi vite ? Il y a trois raisons principales : la conception par les physiciens et la fabrication industrielle en grand volume de capteurs de haute qualité ; l’augmentation considérable de la puissance et la diminution de la dépense énergétique des ordinateurs embarqués, grâce à la fameuse loi de Moore ; enfin, et surtout, l’amélioration continue des algorithmes de la photographie, qui jouent en fait un rôle plus important que celui des capteurs. Dans les quinze dernières années, nous avons gagné au moins 4 degrés de sensibilité, dont les trois quarts grâce aux algorithmes. Même des appareils aux capteurs relativement petits savent faire des photos de très haute qualité à 3200 ISO, ce qui était complètement impossible avec l’argentique. Le cours détaillera d’abord la suite des transformations algorithmiques subtiles qui permettent le développement des images des données numériques du capteur, aboutissant à l’image finale en gérant au mieux la lumière, la netteté et le bruit. Ensuite, il étudiera les algorithmes dédiés à la correction automatique des divers défauts optiques des objectifs ; il montrera que la puissance de ces algorithmes fait que ces objectifs ne seront plus conçus comme auparavant : leur conception intègre désormais totalement physique et algorithmique, fournissant des optiques de meilleure qualité, moins encombrantes, plus légères et moins chères. Il insistera sur l’importance que prennent les nouveaux traitements fondés sur la fusion de prises de vue successives pour l’amélioration de la qualité selon divers objectifs (lumière, bruit, profondeur de champ, etc.), en particulier pour les téléphones. Il montrera pourquoi fonder les nouveaux appareils directement sur les algorithmes modifie de plus en plus le cœur de leur conception, ce qui fait que bien d’autres nouveautés surprenantes pourront apparaître. Des évolutions similaires bouleversent d’ailleurs tout autant les imageries médicale et astronomique. Enfin, le cours soulignera l’importance des nouveaux algorithmes destinés à l’amélioration de l’ergonomie de la prise de vue, qui rendent la vie technique du photographe bien plus facile sur quasiment tous les aspects : interaction humain-machine bien conçue, stabilisation du capteur et de l’objectif pour supprimer le flou de bougé, gestion sophistiquée de la lumière et de la mise au point, nombreuses aides à la prise de vue dans le viseur devenant électronique, liaison directe avec les ordinateurs et téléphones. Séminaire de Stéphane Huot Résumé Bien avant l'avènement des ordinateurs personnels, de l'internet et des smartphones , l'Interaction Homme-Machine (IHM) était déjà une préoccupation au cœur de certaines des visions qui ont contribué à forger l'informatique moderne, qu'elle soit personnelle ou professionnelle. Pour autant, la conception et l'étude des interactions est encore souvent considérée comme secondaire dans la conception des systèmes, la priorité étant souvent mise sur le développement des fonctionnalités plutôt que sur les moyens pour les utiliser. Cette situation s'est progressivement améliorée, avec notamment l'avènement des dispositifs tactiles (smartphones et tablettes) ou de divertissement (consoles de jeux) pour lesquels l'argument de simplicité d'utilisation a détrôné celui de la puissance intrinsèque. Cela a bien évidemment permis de populariser et démocratiser l'accès à la technologie. Mais une conséquence est, selon nous, un relatif appauvrissement des possibilités offertes par ces technologies paradoxalement plus puissantes que jamais. En masquant la complexité plutôt qu'en aidant à la maîtriser, en entretenant le mythe qu'avec ces dispositifs il est aisé pour chacun de faire beaucoup sans efforts, la tendance est à sacrifier le potentiel de l'outil informatique et la performance des utilisateurs pour la rapidité de prise en main, sans permettre un usage plus avancé, plus performant, et peut-être plus gratifiant pour l'utilisateur. Cet équilibre entre simplicité d'usage et puissance de l'outil est un compromis difficile à trouver, et c'est selon nous un des défis et une difficulté majeure de l'IHM : observer et comprendre les phénomènes sensorimoteurs et psychomoteurs, cognitifs, sociaux et technologiques mis en œuvre lors de l'interaction entre des personnes et des systèmes afin d'améliorer cette interaction et d'en guider la conception pour encapaciter les utilisateurs. Le but étant finalement de leur permettre de réaliser ce qu'il leur serait impossible de faire sans cet outil, même si cela requiert de leur part des efforts certains d'apprentissage. Dans ce séminaire, nous commencerons par présenter ce qu'est l'Interaction Homme-Machine en tant que domaine de recherche avec ses objectifs, ses méthodes et ses pratiques. Ensuite, au travers d'une brève histoire de l'informatique sous le prisme de l'interaction, nous évoquerons quelques innovations d'aujourd'hui qui découlent des visions de pionniers du domaine, en considérant notamment ce compromis simplicité / puissance de l'outil. Nous verrons aussi avec des exemples et contre-exemples issus de nos environnements numériques actuels, ainsi qu'avec des travaux de recherche récents, que ces visions portent encore de nombreux défis présents et futurs de l'IHM. En particulier, nous conclurons en discutant de la nécessité d'adopter une approche centrée utilisateur et interaction à l'heure des grands défis scientifiques, technologiques et sociétaux du numérique tels que la conception des systèmes autonomes ou le traitement et l'exploitation automatique des données. Mots-clés : Machines et langages Algorithme Interaction Homme machine (IHM). Lililad |
Wed, January 31, 2018 3:30 pm 8:30 pm | Le centre Inria Lille - Nord Europe reçoit Gérard Berry, du Collège de France pour son cours sur la photographie numérique. Ce cours se prolongera par un séminaire de Stéphane Huot, responsable de l'équipe Mjolnir. Cette manifestation sera suivie d'un cocktail au cours duquel Isabelle Herlin, directrice du centre de recherche Inria Lille - Nord Europe présentera ses voeux. Programme 15h30 : Accueil 15h45 : Introduction par Isabelle Herlin 16h - 17h30 : Cours de Gérard Berry, "La photographie numérique, un parfait exemple de la puissance de l'informatique" 17h30 - 18h30 : Séminaire de Stéphane Huot, "Interaction humain-machine : passé composé et futur simple... ou l'inverse" 18h30 - 18h45 : Questions aux deux orateurs 19h - 20h30 : Cocktail Liliad |
Fri, January 19, 2018 10:00 am 12:00 pm | Sylvain Salvati: "On magic set rewriting for Datalog" Cet exposé se veut une introduction à la transformation de programmes datalog. En particulier, je présenterai la transformation appelée "supplementary magic set rewriting" qui permet d'obtenir des programmes datalog dont l'évaluation semi-naïve se comporte de façon similaire à l'évaluation des programmes originaux par résolution SLD. Je montrerai l'algorithme et des exécutions de programmes sur des exemples issus de problèmes d'analyses grammaticales. Lille B21 |