Lifo - Laboratoire d'Informatique Fondamentale d'orléans INSA Centre Val de Loire Université d'Orléans Université d'Orléans

Lifo > Les séminaires du LIFO

 English Version



Contact

LIFO - Bâtiment IIIA
Rue Léonard de Vinci
B.P. 6759
F-45067 ORLEANS Cedex 2

Email: contact.lifo
Tel: +33 (0)2 38 41 70 11
Fax: +33 (0)2 38 41 71 37



Les séminaires du LIFO


Accès par année : 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017

Sauf exception, les séminaires se déroulent le lundi de 14h à 15h, Salle de réunion 1, bâtiment IIIA (voir plan du campus).


16/12/2013 : Apprentissage incrémental de modèles d'action relationnels
Christophe Rodrigues (Université Paris 13) Résumé
Attention : Débute à 15 h.

13/12/2013 : Soutenance de thèse : Squelettes algorithmiques pour la programmation et l'exécution efficaces de codes parallèles
Joeffrey Legaux (LIFO) Résumé
Attention : Débute à 14 h 30. Lieu : Amphi Herbrand, bâtiment 3IA

25/11/2013 : Votre sécurité informatique
S. Junca (DCRI (Direction Centrale du Renseignement Interieur)) Résumé
Attention : Présentation ouverte aux étudiants / Débute à 13 h 30.

18/11/2013 : Une chaîne d'analyse syntaxique du français utilisant la grammaire FRIGRAM
Guy Perrier (LORIA, Université de Lorraine) Résumé

07/10/2013 : Parallel Functional Programming in Eden
Thomas Horstmeyer and Rita Loogen (Philipps-Universität Marburg) Résumé

07/10/2013 : Formal Semantics for the Parallel Language Eden
Yolanda Ortega-Mallén (Universidad Complutense de Madrid) Résumé
Attention : Débute à 15 h.

27/06/2013 : Soutenance de thèse : Modèle géométrique de calcul : fractales et barrières de complexité
Maxime Senot (LIFO) Résumé
Attention : Lieu : Amphithéâtre Herbrand

24/06/2013 : Deciding Kleene Algebra Terms (In)Equivalence in Coq
Simão Melo de Sousa (Universidade da Beira Interior) Résumé
Attention : Débute à 16 h. Lieu : Salle SR3, bâtiment 3IA

13/05/2013 : Weak Inclusion for Recursive XML Types
Joshua Amavi (LIFO) Résumé

25/03/2013 : Kernelization Using Structural Parameters in Sparse Graph Classes
Somnath Sikdar (RWTH Aachen) Résumé

18/02/2013 : Comparaison de réseaux biologiques : graphe orienté vs graphe non-orienté
Hafedh Mohamed Babou (Université de Nantes) Résumé

11/02/2013 : Packing rectangles in a rectangle
Petru Valicov (LRI - Université Paris Sud) Résumé

04/02/2013 : Stream-processing of large XML documents: selectivity estimation and performance model
Muath Alrammal (LIFO) Résumé


Résumés des séminaires


Apprentissage incrémental de modèles d'action relationnels Christophe Rodrigues, Université Paris 13

Dans ces travaux, nous nous intéressons à l'apprentissage artificiel pour l'action. Nous nous situons à l'intersection de l'apprentissage par renforcement (AR) et de la programmation logique inductive (PLI). Nous étudions plus précisément l'apprentissage de modèles d'actions. Un modèle d'action décrit les conditions et effets des actions possibles dans un environnement. Il permet d'anticiper les conséquences des actions d'un agent et peut aussi être utilisé par un planificateur. Nous nous intéressons en particulier à une représentation relationnelle des environnements. Nous décrivons alors les états et les actions à l'aide d'objets et de relations entre les différents objets qui les composent. Nous présentons la méthode IRALe apprenant de façon incrémentale des modèles d'action relationnels. Nous commençons par supposer que les états sont entièrement observables et que les conséquences des actions sont déterministes. Nous apportons une preuve de convergence pour cette méthode. Ensuite, nous développons une approche d'exploration active qui essaye de focaliser l'expérience de l'agent sur des actions supposées non couvertes par le modèle. Enfin, nous généralisons l'approche en introduisant une perception de l'environnement bruitée afin de rendre plus réaliste notre cadre d'apprentissage. Pour chaque approche, nous illustrons empiriquement son intérêt sur plusieurs problèmes de planification. Les résultats obtenus montrent que le nombre d'interactions nécessaires avec les environnements est très faible comparé à la taille des espaces d'états considérés. De plus, l'apprentissage actif permet d'améliorer significativement ces résultats.


Soutenance de thèse : Squelettes algorithmiques pour la programmation et l'exécution efficaces de codes parallèles Joeffrey Legaux, LIFO

Résumé : Les architectures parallèles sont désormais présentes dans tous les matériels informatiques, mais les programmeurs ne sont généralement pas formés à leur programmation dans les modèles explicites tels que MPI ou les Pthreads. Il y a un besoin important de modèles plus abstraits tels que les squelettes algorithmiques qui sont une approche structurée. Ceux-ci peuvent être vus comme des fonctions d'ordre supérieur synthétisant le comportement d'algorithmes parallèles récurrents que le développeur peut ensuite combiner pour créer ses programmes. Les développeurs souhaitent obtenir de meilleures performances grâce aux programmes parallèles, mais le temps de développement est également un facteur très important. Les approches par squelettes algorithmiques fournissent des résultats intéressants dans ces deux aspects. La bibliothèque "Orléans Skeleton Library" ou OSL fournit un ensemble de squelettes algorithmiques de parallélisme de données quasi-synchrones dans le langage C++ et utilise des techniques de programmation avancées pour atteindre une bonne efficacité. Nous avons amélioré OSL afin de lui apporter de meilleures performances et une plus grande expressivité. Nous avons voulu analyser le rapport entre les performances des programmes et l'effort de programmation nécessaire sur OSL et d'autres modèles de programmation parallèle. La comparaison rigoureuse entre des programmes parallèles dans OSL et leurs équivalents de bas niveau montre une bien meilleure productivité pour les modèles de haut niveau qui offrent une grande facilité d'utilisation tout en produisant des performances acceptables. Le jury sera composé de : Rapporteurs : Herbert Kuchen, Professeur, Universität Münster Marco Danelutto, Associate Professor, Università di Pisa Examinateurs : Joël Falcou, Maître de conférence, Université Paris-Sud 11 Sylvain Jubertie, Maître de conférence, Université d'Orléans Sébastien Limet, Professeur, Université d'Orléans Stéphane Vialle, Professeur, Supélec Metz Directeur de thèse : Frédéric Loulergue, Professeur, Université d'Orléans Mots clés : Modèles de haut niveau, squelettes algorithmiques, parallélisme quasi-synchrone, effort de programmation, expressivité, exceptions, distribution des données, homomorphismes


Votre sécurité informatique S. Junca, DCRI (Direction Centrale du Renseignement Interieur)

Résumé à venir


Une chaîne d'analyse syntaxique du français utilisant la grammaire FRIGRAM Guy Perrier, LORIA, Université de Lorraine

FRIGRAM est une grammaire du français à large couverture écrite dans le formalisme des grammaires d'interaction. L'originalité du formalisme réside dans l'utilisation d'un système de polarités exprimant l'état de saturation des structures syntaxiques, pour guider la composition syntaxique. La grammaire a été construite sous une forme modulaire à l'aide de l'outil XMG. Elle est liée à un lexique, FRILEX, complètement indépendant du formalisme. Le lien se fait par unification entre les entrées du lexiques et les interfaces associées aux structures grammaticales élémentaires, toutes les deux se présentant sous forme de structures de traits. FRIGRAM et FRILEX sont utilisées dans la chaîne d'analyse syntaxique LEOPAR dont l'originalité est de produire des analyses profondes: elle fournit pour chaque prédicat ses arguments, même lorsqu'ils ne sont pas directement donnés par les dépendances syntaxiques (sujets des infinitifs, anaphores syntaxiques...). La sortie d'analyse est exprimée sous forme d'un graphe de dépendances mais il est possible d'avoir aussi un arbre syntagmatique correspondant. Nous présenterons l'ensemble de la chaîne avec ses différents modules : segmentation de la phrase en mots, étiquetage des mots avec le lexique et la grammaire, filtrage des étiquetages possibles et analyse proprement dite.


Parallel Functional Programming in Eden Thomas Horstmeyer and Rita Loogen, Philipps-Universität Marburg

Eden extends Haskell with constructs for the definition and instantiation of parallel processes. Processes evaluate function applications remotely in parallel. The programmer has control over process granularity, data distribution, communication topology, and evaluation site, but need not manage synchronisation and data exchange between processes. The latter are performed by the parallel runtime system through implicit communication channels, transparent to the programmer. Common and sophisticated parallel communication patterns and topologies, so-called algorithmic skeletons, are provided as higher-order functions in a user-extensible skeleton library written in Eden. Eden is geared toward distributed settings, i.e.\ processes do not share any data, but can equally well be used on multicore systems. In the talk, we give an introduction into Eden's language constructs and its skeleton-based programming methodology.


Formal Semantics for the Parallel Language Eden Yolanda Ortega-Mallén, Universidad Complutense de Madrid

We present two formal semantics for the kernel of the parallel language Eden. First we describe an operational semantics expressed as a two-level transition system. Next we present a denotational semantics based on continuations, suitable for dealing with side-effects and parallelism. We end by comparing both approaches.


Soutenance de thèse : Modèle géométrique de calcul : fractales et barrières de complexité Maxime Senot, LIFO

Descriptif : Les modèles géométriques de calcul permettent d'effectuer des calculs à l'aide de primitives géométriques. Parmi eux, le modèle des machines à signaux se distingue par sa simplicité, ainsi que par sa puissance à réaliser efficacement de nombreux calculs. Nous nous proposons ici d'illustrer et de démontrer cette aptitude, en particulier dans le cas de processus massivement parallèles. Nous montrons d'abord à travers l'étude de fractales (et plus généralement de structures appelées accumulations) que les machines à signaux sont capables d'une utilisation massive et parallèle de l'espace. Une méthode de programmation géométrique modulaire est ensuite proposée pour construire des machines à partir de composants géométriques de base – les modules – munis de certaines fonctionnalités. Cette méthode est particulièrement adaptée pour la conception de calculs géométriques parallèles. Enfin, l'application de cette méthode et l'utilisation de certaines des structures fractales résultent en une résolution géométrique de problèmes difficiles comme les problèmes de satisfaisabilité booléenne SAT et Q-SAT. Ceux-ci, ainsi que plusieurs de leurs variantes, sont résolus par machines à signaux avec une complexité en temps intrinsèque au modèle, appélée profondeur de collisions, qui est polynomiale, illustrant ainsi l'efficacité et le pouvoir de calcul parallèle des machines à signaux. Jury : Denys Duchier - Professeur des Universités, Université d'Orléans Jérôme Durand-Lose - Professeur des Universités, Université d'Orléans - Directeur de thèse Géraud Sénizergues - Professeur des Universités, Université de Bordeaux 1 Véronique Terrier - Maître de Conférence HDR, Université de Caen - Rapporteur Jean-Baptiste Yunès - Maître de Conférence HDR, Université de Paris 7 - Rapporteur


Deciding Kleene Algebra Terms (In)Equivalence in Coq Simão Melo de Sousa, Universidade da Beira Interior

This talk presents a mechanically verified implementation of an algorithm for deciding the (in)equivalence of Kleene algebra terms. The algorithm decides the (in)equivalence of two given terms through an iterated process of testing the equivalence of their partial derivatives and does not require the construction of the corresponding automata. Recent theoretical and experimental research provide evidence that this method is, on average, more efficient than the classical methods based in automata. We present some performance tests, comparisons with similar approaches, and also introduce a generalization of the algorithm to decide the equivalence of terms of Kleene algebra with tests. The motivation for the presented work is that of using the developed libraries as trusted frameworks for carrying out certified program verification.


Weak Inclusion for Recursive XML Types Joshua Amavi, LIFO

In database area, an important problem is schema evolution, particularly when considering XML types. XML is also used for exchanging data on the web. In this setting, we want to compare XML types in a loose way. To do it, we address the more general problem of approximative comparison of unranked-tree languages defined by regular grammars. Considering that the unranked tree languages L(G) and L(G') are those defined by given possibly-recursive XML types G and G', in this seminar we propose a method to verify whether L(G) is ''approximatively'' included in L(G'). The approximation consists in weakening the father-children relationships. Experimental results are discussed, showing the efficiency of our method in many situations.


Kernelization Using Structural Parameters in Sparse Graph Classes Somnath Sikdar, RWTH Aachen

Meta-theorems for polynomial (linear) kernels have been the subject of intensive research in parameterized complexity. Heretofore, there were meta-theorems for linear kernels on graphs of bounded genus, H-minor-free graphs, and H-topological-minor-free graphs. To the best of our knowledge, there are no known meta-theorems for kernels for any of the larger sparse graph classes: graphs of bounded expansion, locally bounded expansion, and nowhere dense graphs. In this paper we prove meta-theorems for these three graph classes. More specifically, we show that graph problems that have finite integer index (FII) have linear kernels on graphs of bounded expansion when parameterized by the size of a modulator to constant-treedepth graphs. For graphs of locally bounded expansion, our result yields a quadratic kernel and for nowhere dense graphs, a polynomial kernel. While our parameter may seem rather strong, we show that a linear kernel result on graphs of bounded expansion with a weaker parameter will necessarily fail to include some of the problems included in our framework. Moreover, we only require problems to have FII on graphs of constant treedepth. This allows us to prove linear kernels for problems such as Longest Path/Cycle, Exact s,t-Path, Treewidth and Pathwidth which do not have FII in general graphs.


Comparaison de réseaux biologiques : graphe orienté vs graphe non-orienté Hafedh Mohamed Babou, Université de Nantes

La comparaison de réseaux biologiques est actuellement l'une des approches les plus prometteuses pour aider à la compréhension du fonctionnement des organismes vivants. Elle apparaît comme la suite attendue de la comparaison de séquences biologiques dont l'étude ne représente en réalité que l'aspect génomique des informations manipulées par les biologistes. Dans ce travail, nous proposons une approche innovante permettant de comparer deux réseaux biologiques modélisés respectivement par un graphe orienté D et un graphe non-orienté G, et dotés d'une fonction f établissant la correspondance entre les sommets des deux graphes. L'approche consiste à extraire automatiquement une structure dans D, biologiquement significative, dont les sommets induisent dans G, par f, une structure qui soit aussi biologiquement significative. Nous réalisons une étude algorithmique du problème issu de notre approche en commençant par sa version dans laquelle D est acyclique (DAG). Nous proposons des algorithmes polynomiaux pour certains cas, et nous montrons que d'autres cas sont algorithmiquement difficiles (NP-complets). Pour résoudre les instances difficiles, nous proposons une bonne heuristique et un algorithme exact basé sur la méthode branch-and-bound. Enfin, pour montrer l'efficacité de notre heuristique, nous l'appliquerons sur des données simulées et sur des données biologiques réelles. Mots clés : Réseaux hétérogènes, Biologie computationnelle, NP-difficulté, APX-difficulté, Complexité paramétrée, Heuristiques, Branch-and-Bound.


Packing rectangles in a rectangle Petru Valicov , LRI - Université Paris Sud

We address the problem of packing rectangles into a bigger ectangle, also called the two-dimensional Orthogonal Packing Problem (OPP-2). The goal is to decide whether a set of rectangles can be packed in a rectangular container C without overlapping and without exceeding the borders of C. In the classical version the rotation of items is not allowed. This problem is NP-complete in the strict sense and can be seen as a sub-problem of the two-dimensional Orthogonal Knapsack Problem which is the optimization version : each item has an associated profit and the goal is to choose a subset of items maximizing the total profit. Till late 90's the algorithms for solving the problem were mainly based on mathematical programming tools. In 1997 Fekete and Schepers characterized the set of solutions for a given instance by using interval graphs. Using this characterization they designed an efficient algorithm to solve OPP by enumerating interval graphs with a certain number of constraints. In this talk I will present the general idea of their work and show how their model can be improved in order to avoid symmetry issues by using more compact data structures. I will finish the talk by showing the comparison of our approach with other algorithms from the literature using standard benchmarks. This is a joint work with C. Joncour and A. Pêcher.


Stream-processing of large XML documents: selectivity estimation and performance model Muath Alrammal, LIFO

XML is a key standard for manipulating data on the Internet. However, querying large volume of XML data represents a bottleneck for several computationally intensive applications. Many modern applications require processing of massive streams of XML data, creating difficult technical challenges. Among these is the optimization of XPath query processing and accurate cost estimation for these queries. In this seminar, we present a novel performance prediction model which a priori estimates the cost of any Forward XPath structural in terms of space used and time spent. The model consists of (1) a lazy stream-querying algorithm LQ (2) a mathematical performance model (linear regression functions), and (3) a new selectivity estimation technique. Extensive experiments on both real and synthetic data sets show that our model achieves accuracy better than existing approaches. The resulting prototype supports the a priori design of efficient queries, as well as automatic query optimizations.