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 99 29
Fax: +33 (0)2 38 41 71 37
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é
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.
University of Orléans | INSA Centre Val de Loire