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 99 29
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 2018 2019 2020 2021 2022 2023 2024

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).


10/12/2007 : Hybridation de méthodes complètes et incomplètes pour la résolution de CSP
Tony Lambert (LIFO orleans) Résumé

03/12/2007 : Consistency and Minimality of UML class specifications
Gernot Salzer (Technische Universität Wien (vienne - autriche)) Résumé
Attention : ATTENTION 15H

03/12/2007 : Représentation distribuée de distances
Arnaud Labourel (LABRI Université Bordeaux 1) Résumé

26/11/2007 : Représentations dynamiques de graphes
Christophe Crespelle (Université Paris Diderot - Paris 7) Résumé

12/11/2007 : Méthodes de Décomposition pour la Résolution Paralléle du Problème SAT
Daniel Singer (Laboratoire d'Informatique Théorique et Appliquée de l'Université de Metz (LITA)) Résumé

05/11/2007 : Graphes dirigés et circuits
Guillaume Malod (Equipe de logique mathématiques Paris 7) Résumé

10/09/2007 : On the computational capabilities of several models
Olivier Bournez (INRIA Lorraine) Résumé

09/07/2007 : Clustering spectral et biclustering pour les données structurées.
Farida Zehraoui (Evry) Résumé

18/06/2007 : Mots, morphismes et répétitions : quelques résultats et questions
Gwenael Richomme (Université de Picardie Jules Verne) Résumé

18/04/2007 : Randomized Clustering Forests for Image Classification
Frédéric Jurie () Résumé

13/04/2007 : Sur quelques problèmes de graphes
Pascal Berthomé (LRI) Résumé
Attention : 10h SR1

10/04/2007 : Décomposition bi-joint et généralisations
Michael Rao (Jussieu) Résumé

10/04/2007 : Colorations orientées de graphes
Alexandre Pinlou (LABRI) Résumé
Attention : 16h

02/04/2007 : Pour une représentation décentralisée de l'information syntaxique
Philippe Blache () Résumé

02/04/2007 : Formules booléennes quantifiées et problèmes d'abduction
Florian Letombe (CRIL) Résumé
Attention : A 16h SR1

26/03/2007 : Ordres chaîne dominés
Jimmy Leblet (LIFO) Résumé

26/03/2007 : Strasheela: Design and Usage of a Generic Music Constraint System
Torsten Anders (Cologne) Résumé
Attention : à 16h !

23/03/2007 : Extraction de concepts à l'aide de techniques d'apprentissage non supervisé
Julien Velcin (LIP6) Résumé
Attention : Vendredi 10h

19/03/2007 : Résolution de contraintes du premier ordre par réécriture : Théorie et Pratique
Khalil Djelloul (Université d'Ulm (Allemagne)) Résumé

19/03/2007 : Extraction, sélection et exploitation de séquences dans un contexte applicatif textuel
Antoine Doucet (IRISA) Résumé
Attention : 2eme séminaire à 16h

12/03/2007 : Bidirectional XQuery: Updating XML through Materialized View
Zhenjiang Hu (University of Tokyo) Résumé

05/03/2007 : Automatic Inversion Generates Divide-and-Conquer Parallel Programs
Zhenjiang Hu (University of Tokyo) Résumé

19/02/2007 : Apprentissage de séquences
Lorenza Saitta (Université du Piémont Oriental) Résumé

12/02/2007 : GPAC, Analyse récursive, fonctions R-récursives : trois modèles de calcul sur les réels qui calculent les mêmes fonctions.
Emmanuel Hainry (LORIA) Résumé

05/02/2007 : Apprentissage d'ensemble de classifieurs
Lorenza Saitta (Université du Piémont Oriental) Résumé

15/01/2007 : Outils de développement paralléle pour la Vision artificielle
Joël Falcou (LASMEA Clermont-Ferrand) Résumé


Résumés des séminaires


Hybridation de méthodes complètes et incomplètes pour la résolution de CSP Tony Lambert, LIFO orleans

L'hybridation des mécanismes de méthodes incomplètes et des techniques de programmation par contraintes est souvent basée sur des combinaisons de type maître-esclave, dédiées à la résolution de classes de problèmes spécifiques. Nous nous intéressons à la définition d'un modèle théorique uniforme, basé sur les itérations chaotiques de K.R. Apt qui définissent un cadre mathématique pour l'itération d'un ensemble fini de fonctions sur des domaines abstraits munis d'un ordre partiel. Ce cadre permet de prendre en compte une hybridation entre les méthodes incomplètes et les méthodes complètes. Notre cadre générique permet alors d'envisager des stratégies de combinaisons et d'hybridation de manière plus fine et d'étudier leurs propriétés.


Consistency and Minimality of UML class specifications Gernot Salzer, Technische Universität Wien (vienne - autriche)

The Unified Modeling Language (UML) has become a universal tool for the formal object-oriented specification of hard- and software. In particular, UML class diagrams and so-called multiplicities, which restrict the number of links between objects, are essential when using UML for applications like the specification of admissible configurations of components. UML class diagrams are not only useful for software engineers, but they also pose problems interesting from a theoretical point of view. In this talk we show that the consistency of such specifications can be checked in polynomial time, and give an algorithm for computing minimal configurations (models). The core of our approach is a translation of the diagrams to Diophantine inequations.


Représentation distribuée de distances Arnaud Labourel, LABRI Université Bordeaux 1

La représentation distribuée d'un graphe consiste à stocker sur chaque sommet du graphe une information utile permettant la résolution de requête de manière locale, c'est-à-dire en examinant seulement l'information stockée par les sommets concernés par la requête. On s'intéresse ici au cas de la requête de distance bornée, c'est-à-dire déterminer la distance entre deux sommets si celle-ci est inférieure à un paramètre k fixé. Notre principale contribution est une représentation de distance bornée pour les arbres de n sommets utilisant log n +O(k log(k log n)) bits par sommets. La représentation obtenue permet en fait des requêtes plus complexes que de simples tests de distance et a des applications pour les recherches dans les fichiers XML.


Représentations dynamiques de graphes Christophe Crespelle, Université Paris Diderot - Paris 7

L'exposé abordera la question de l'entretien dynamique de représentations géométriques de graphes. Nous montrerons des connexions fortes entre trois types de représentation de graphes : les décompositions de graphes, les modèles géométriques et les représentations arborescentes à degrés de liberté (PQ-arbres, PC-arbres et autres structures du même type). De nouvelles relations entre ces objets seront mises en évidence et d'autres déjà connues seront approfondies. Notamment, il sera établi une équivalence mathématique et algorithmique entre la décomposition modulaire des graphes d'intervalles et le PQ-arbre de leurs cliques maximales. Nous montrerons comment exploiter les connexions entre les trois types de représentation précités pour la conception d'algorithmes de reconnaissance entièrement dynamiques pour les graphes de permutation et les graphes d'intervalles. Ces deux algorithmes ont la même complexité : les modifications d'arête et de sommet sont traitées en temps O(n), où n est le nombre de sommets du graphe. L'approche mise en oeuvre est assez générale pour laisser entrevoir les mêmes possibilités algorithmiques pour d'autres classes de graphes définies géométriquement.


Méthodes de Décomposition pour la Résolution Paralléle du Problème SAT Daniel Singer, Laboratoire d'Informatique Théorique et Appliquée de l'Université de Metz (LITA)

Le problème SAT consiste à décider si une formule de la Logique Propositionnelle est satisfaisable ou non. Il est actuellemnt l'un des problèmes les plus étudiés en Informatique, d'une part, parce qu'il occupe une place centrale en Informatique Théorique en tant que premier problème à avoir été démontré NP-complet (Cook 1971), d'autre part, grâce à l'efficacité atteinte aujourd'hui par les solveurs (séquentiels) basés sur l'algorithme DPLL, il permet la résolution en pratique de nombreux problèmes réels dans différents domaines d'activité (Planification, Model Checking, etc.). L'un des challenges actuels du domaine est l'utilisation des différentes architectures paralléles multicores, clusters, grilles pour pouvoir résoudre des problèmes de trés grande taille (milliers de variables, voire plus). Notre exposé présentera les différentes méthodes de décomposition pour la résolution en paralléle. Tout d'abord, nous ferons un bref état de l'art des propositions qui ont consisté généralement à décomposer l'espace de recherche. Puis nous introduirons notre nouveau schéma de résolution de SAT, intutitulé JaCk-SAT basé sur une décomposition structurelle de l'instance considérée. L'idée est d'utiliser la structure de graphe sous-jacente au problème (sa sémantique) pour définir une heuristique de décomposition qui ne fasse pas appel à la recherche de séparateurs minimaux (problème lui même NP-complet!). Nous présenterons les tout premiers résultats expérimentaux obtenus par cette méthode ainsi que les nombreuses perspectives qu'elle ouvre.


Graphes dirigés et circuits Guillaume Malod, Equipe de logique mathématiques Paris 7

Si on définit des classes de complexité de polynômes en utilisant des circuits arithmétiques, une des premières classes intéressantes est la classe VP obtenue via les circuits de taille et degré polynomialement bornés. Cette classe se caractérise par des circuits avec une restriction sur les multiplications. Une autre restriction sur les multiplications, plus forte et peut-être moins naturelle, produit la classe VPws. Curieusement, nous connaissons bien plus de propriétés pour cette classe que pour la classe plus naturelle VP. La plupart des propriétés de VPws s'obtiennent grâce à une caractérisation par des graphes dirigés, dont je donnerai des exemples. Ceci soulève alors le problème de trouver une telle caractérisation pour la classe VP.


On the computational capabilities of several models Olivier Bournez, INRIA Lorraine

We review some results about the computational power of several computational models. Considered models have in common to be related to continuous dynamical systems.


Clustering spectral et biclustering pour les données structurées. Farida Zehraoui, Evry

Le clustering peut être vu comme une minimisation de la coupe normalisée d'un graphe de similarités, graphe composé d'un ensemble de noeuds représentant les données et d'un ensemble d'arêtes pondérées représentant la similarité entre les données. Le problème de minimisation de la coupe de graphe normalisée est NP-difficile. Une approche possible pour résoudre ce problème est basée sur la théorie spectrale de graphes. Elle transforme le problème de coupe de graphe en un problème de recherche de valeurs et de vecteurs propres. Cette approche s?appelle le clustering spectral. Le biclustering, qui est une extension du clustering, regroupe les données suivant un sous-ensemble de d?attributs. Je vais présenter dans cet exposé le principe du clustering spectral, les différents types d?algorithmes de biclustering et particulièrement le biclustering spectral et son extension pour traiter des données structurées (séries temporelles, graphes, ?).


Mots, morphismes et répétitions : quelques résultats et questions Gwenael Richomme, Université de Picardie Jules Verne

La résolution de nombreux problèmes nécessite une bonne compréhension de phénomènes de répétitions dans les mots. Nous présentons plusieurs résultats et questions autour de ce sujet. Notamment nous nous intéresserons à un problème ouvert dans les années 1980 : est-il possible de décider si un morphisme préserve les mots sans puissance k ? Egalement, nous parlerons des mots quasipériodiques, les mots qui peuvent s'obtenir par concaténations et chevauchements d'un autre mot.


Randomized Clustering Forests for Image Classification Frédéric Jurie,

This talk will be focused on 3 recent contributions to the problems of image classification and image search. Some of the most effective recent methods for content-based image classification work by extracting image descriptors, quantizing them according to a coding rule such as k-means vector quantization, accumulating histograms of the resulting visual word codes over the image, and classifying these with a conventional classifier such as an SVM. Large numbers of descriptors and large codebooks are required for good results and this becomes slow using k-means. First, a new paradigm for representing images will be presented. We will introduce Extremely Randomized Clustering Forests -- ensembles of randomly created clustering trees -- and show that they provide more accurate results, much faster training and testing and good resistance to background clutter. Second, an efficient image classification method will be described. It combines ERC-Forests and saliency maps very closely with the extraction of image information. It will be shown that this method, which requires to extract 20 times less information from images than the standard bag-of-word algorithm also provides more accurate results. in several state-of-the-art image classification tasks. Finally, we will show that the proposed ERC-Forests can also be used very successfully for learning distance between images. The similarity measure has been evaluated on four very different datasets and always outperforms the state-of-the-art competitive approaches. References # E. Nowak and F. Jurie, Learning Visual Similarity Measures for Comparing Never Seen Objects, IEEE Conference on Computer Vision and Pattern Recognition, 2007 # F.Moosmann, B. Triggs, F. Jurie, Randomized Clustering Forests for Building Fast and Discriminative Visual Vocabularies, NIPS'06, 2006. # Frank Moosmann, Diane Larlus, Frederic Jurie, Learning Saliency Maps for Object Categorization ECCV IWRUPKV - 2006


Sur quelques problèmes de graphes Pascal Berthomé, LRI

Dans cet exposé, j'ai choisi de vous présenter deux aspects de mes recherches. Le premier point porte sur une variation autour du problème des flots maximum: il s'agit de flots multi-terminaux paramétrés: il s'agit de déterminer efficacement un flot maximum quand ni la source, ni la destination, ni la capacité de certaines arêtes ne sont déterminées a priori. Le deuxième point porte sur une nouvelle représentation des graphes basée sur l'une de ses triangulations. Cette représentation est pertinente pour des calculs exacts sur un graphe comme le calcul du polynôme chromatique de ce graphe. Pour ces deux problèmes, nous considérerons la problématique générale, les résultats que nous avons obtenus et les diverses perspectives de recherche qu'ils engendrent.


Décomposition bi-joint et généralisations Michael Rao, Jussieu

Les modules et la décomposition modulaire sont des éléments récurrents en théorie et algorithmique de graphes. Après quelques rappels, on s'intéressera à la décomposition bi-joint qui en est une généralisation. On montra une relation entre les décompositions bi-joint et modulaire au travers du ``Seidel switch''. Ceci nous donnera des caractérisations des graphes entièrement décomposables, et un algorithme linéaire de décomposition. On présentera également une relation entre cette décomposition et la ``clique-width''. Dans la seconde partie, on présentera une famille de décompositions de 2-structures généralisant la décomposition modulaire. La décomposition bi-joint en fait partie, ainsi que deux différentes généralisations aux graphes orientés. Enfin on verra que toutes ces décompositions peuvent être calculées en temps $O(n3)$.


Colorations orientées de graphes Alexandre Pinlou, LABRI

Un homomorphisme d'un graphe orienté G vers un graphe orienté H est une application f de l'ensemble des sommets de G vers l'ensemble des sommets de H telle que pour tout arc (u,v) de G, (f(u),f(v)) est un arc de H. Une k-sommet-coloration orientée d'un graphe orienté G est définie comme un homomorphisme de G vers un graphe orienté H à k sommets. Cette notion de sommet-coloration orientée fut introduite en 1994, et durant les dix dernières années, elle a été largement étudiée par la communauté internationale et le nombre chromatique orienté d'un grand nombre de familles de graphes a été borné. Après un rapide état de l'art, je vous exposerai les récents résultats que nous avons obtenu, notamment pour les graphes planaires, les graphes série-parallèles ou encore les graphes planaires extérieurs. J'introduirai ensuite la notion d'arc-coloration orientée, notion naturellement définie à partir de la notion de sommet-coloration orientée. Je vous montrerai que nous sommes capables d'obtenir des bornes en fonction de paramètres connus (e.g. nombre chromatique, nombre chromatique orienté, nombre chromatique acyclique). Je vous présenterai également les résultats obtenus sur certaines classes de graphes.


Pour une représentation décentralisée de l'information syntaxique Philippe Blache,

Les théories génératives ont profondément et durablement marqué la représentation de l'information syntaxique. Il est ainsi aujourd'hui d'usage d'utiliser le domaine des arbres pour construire des structures syntaxiques. Or une telle conception est étroitement dépendante de la relation que la grammaire générative introduit entre grammaire et langage, ce dernier étant énuméré par le truchement de la grammaire. Plusieurs approches récentes ont montré l'intérêt de se dégager d'une telle vision, par exemple en se situant dans la perspective de la théorie des modèles. Il y a donc incompatibilité entre ces approches et une représentation strictement hiérarchisée de l'information syntaxique. Nous présenterons dans cet exposé une approche basée sur une représentation décentralisée de l'information syntaxique qui, en mettant les contraintes au coeur du processus d'analyse et de représentation, permet de dépasser ces limites.


Formules booléennes quantifiées et problèmes d'abduction Florian Letombe, CRIL

La validité des formules booléennes quantifiées (QBFs) et l'abduction sont intimement liés. En effet, en tant que problème PSPACE-complet canonique, de nombreux problèmes d'IA peuvent être réduits de manière polynomiale à la validité des QBFs (parmi lesquels l'abduction ...). Dans un premier temps, je présenterai les résultats de complexité obtenus sur des restrictions du problème de la validité des QBFs. Ensuite, j'introduirai zlas (http://users.info.unicaen.fr/~zanutti/zlas), un prouveur dédié à la résolution de problèmes d'abduction. Je montrerai en quoi les études réalisées tendent à montrer qu'une modélisation sous forme de QBF n'est pas nécessairement une méthode optimale.


Ordres chaîne dominés Jimmy Leblet, LIFO

M'intéressant à l'étude morphologique des ensembles ordonnés finis au travers des sous-structures orthogonales que sont les chaînes et les antichaînes, je vais être amené à introduire la classe des ordres chaîne dominés. Ces ordres sont des ordres admettant une famille partitive de ses éléments en deux ensembles. L'un de ces ensembles induit un chemin dans son digraphe de couverture et l'autre induit un sous-digraphe sans arc. Après avoir rappelé les définitions de base nécessaires à l'exposé, je montrerai que cette classe d'ordre est l'intersection de deux classes connues que sont les ordres d'intervalles et les treillis tronqués. Puis, en utilisant la notion de couplage maximum dans les graphes, je montrerai que le calcul du nombre de sauts des ordres chaîne dominés est alors polynomial. Enfin, je montrerai que tout ordre d'intervalles peut se plonger dans un ordre de cette classe et que leurs dimensions ne diffèrent pas de plus deux.


Strasheela: Design and Usage of a Generic Music Constraint System Torsten Anders, Cologne

Strasheela is an expressive constraint-based music composition system. Users declaratively state a music theory and the computer generates music which complies with this theory. A theory is formulated as a constraint satisfaction problem (CSP) by a set of rules (constraints) applied to a music representation in which some aspects are unknown (variables). After briefly introducing the field which studies musical applications of constraint programming in general, I will motivate and outline the design of Strasheela as a generic music constraint system. I will discuss models of musical aspects (e.g. harmony and motifs) defined on top of Strasheela, and present musical CSP examples.


Extraction de concepts à l'aide de techniques d'apprentissage non supervisé Julien Velcin, LIP6

Le "regroupement conceptuel" (conceptual clustering) est une branche de l'apprentissage non supervisé qui permet d'extraire des concepts à l'aide de techniques de classification automatique. Il s'avère particulièrement utile lorsque la quantité d'information devient très conséquente et qu'il est nécessaire d'en extraire une représentation synthétique. En cela, le cas des articles de presse est tout à fait caractéristique et sert de cas d'application pratique à nos travaux. L'objectif est alors d'extraire des descriptions résumant les différents sujets abordés dans l'ensemble des articles. Pour répondre à cette problèmatique, un premier modèle a été développé durant ma thèse au LIP6 dans l'équipe de Jean-Gabriel Ganascia. Ce modèle général était basé sur la structure de treillis et utilisait le concept de stéréotype. Le programme qui a été implémenté, PRESS, nous a permis d'obtenir des résultats très intéressants aussi bien sur des jeux de données artificiels que sur une base d'articles réels tirés de la presse du XIXe siècle. Ce modèle posait cependant le problème de devoir traduire préalablement les articles dans un formalisme logique. C'est pourquoi une nouvelle approche appelée AGAPE, adaptée aux données binaires décrites dans de grandes dimensions (dictionnaire de plusieurs dizaines de milliers de mots), est actuellementà l'étude. L'approche consiste à reformuler le problème de clustering en un problème d'optimisation et d'utiliser une méta-heuristique de recherche taboue afin de proposer les meilleures solutions possibles au problème. Les premiers résultats obtenus, notamment sur une base de dépêches AFP récente, ont été comparés à d'autres algorithmes de text clustering et sont très encourageants. Enfin, ce type de techniques peut difficilement être utilisé sans prendre en compte la problématique essentielle et complémentaire d'évaluation des résultats. C'est pourquoi la présentation se terminera par quelques réflexions d'ordre théoriques mais également pratiques sur les résultats pouvant être obtenus en apprentissage non supervisé.


Résolution de contraintes du premier ordre par réécriture : Théorie et Pratique Khalil Djelloul, Université d'Ulm (Allemagne)

Les contraintes du premier ordre (toute quantification et tout symbole logique) offrent une expressivité hors du commun qui permet de modéliser d'une manière très naturelle des problèmes complexes de différents domaines de l'intelligence artificielle (IA). Cependant, la plupart des langages de programmation logique utilisés en IA, tels Prolog ou CHR (Constraint Handling Rules), n'offrent aucun outil pour la résolution de telles contraintes. Nous présentons dans cet exposé une extensions au premier ordre des solveurs de ces langages afin que ces derniers puissent résoudre toute contrainte du premier ordre dans une théorie hybride contenant entre autres des arbres finis ou infinis et des réels additifs ordonnées (R,+,-,<). Une des difficulté majeure dans ce travail réside dans le fait que cette théorie n'admet pas d'élimination complète de quantificateur. Deux approche par réécriture seront alors présentées ainsi que des testes de performances effectués par des implémentations de deux solveurs en CHR et C++. Les résultats obtenus confirmerons le fait que CHR est un langage de programmation logique qui permet d'implémenter d'une manière concise et efficace des solveurs très complexes. Nous terminerons cet exposé par quelque résultats nouveaux autour de la sémantique de CHR et des contraintes logiques.


Extraction, sélection et exploitation de séquences dans un contexte applicatif textuel Antoine Doucet, IRISA

Dans cet exposé, je vous présenterai en détails mes travaux visant à exploiter la nature séquentielle de la donnée textuelle. Ils sont généralisables à tout type de donnée séquentielle. Ces informations sont souvent entièrement ignorées par l'utilisation de modèles vectoriels (dits "sacs de mots"). Mes travaux se sont jusqu'ici concentrés sur les problèmes d'extraction, de sélection et d'utilisation d'unités multi-mots dans un contexte généraliste et multilingue. Les techniques proposées reposent 1) sur la fouille de données séquentielles (généralisation d'une technique d'extraction de séquences d'items à des corpus de n'importe quelle taille), 2) sur la statistique et l'algèbre linéaire (développement d'une méthode de calcul en temps linéaire de la probabilité d'occurrence discontinue d'une séquence d'items). Dans toutes ces techniques, aucune donnée linguistique n'est utilisée, ce qui favorise le passage à l'échelle et permet de généraliser les techniques développées. Des expériences sur des corpus en anglais, coréen, chinois et japonais ont permis de confirmer ces ambitions généralistes. Je présenterai certains prolongements en cours de ces travaux, en collaboration avec le groupe HULTIG de l'université deBeira Interior (Portugal) dirigé par Gaël Dias: - meilleure détection des frontières des unités multi-mots, - résumé de texte basée sur une méthode d'alignement de paraphrases, également en collaboration avec le projet INRIA SYMBIOSE (bioinformatique) et l'université d'Helsinki. Un autre prolongement en cours est l'application des techniques d'extraction de séquences au problème du séquençage vidéo.


Bidirectional XQuery: Updating XML through Materialized View Zhenjiang Hu, University of Tokyo

XQuery is a powerful functional language to query XML data. This paper gives a bidirectional interpretation of XQuery to address the problem of updating XML data through materialized XQuery views. We first design an expressive bidirectional transformation language, and then translate XQuery expressions into the code of this language. As a result, an XQuery expression can execute in two directions: in the forward direction, it generates a materialized view from the source XML data; while in the backward direction, it updates the source data by putting back the updates on the view. As a practical application, we show how a new web page updating system can be constructed based on this technique. This is a joint work with D. Liu, K. Nakano, Y. Hayashi and M. Takeichi.


Automatic Inversion Generates Divide-and-Conquer Parallel Programs Zhenjiang Hu, University of Tokyo

Divide-and-conquer algorithms are suitable for modern parallel machines, tending to have large amounts of inherent parallelism and working well with caches and deep memory hierarchies. Among others, list homomorphisms are a class of recursive functions on lists, which match very well with the divide-and-conquer paradigm. However, direct programming with list homomorphisms is a challenge for many programmers. In this paper, we propose and implement a novel system that can automatically derive cost-optimal list homomorphisms from a pair of sequential programs, based on the third homomorphism theorem. Our idea is to reduce extraction of list homomorphisms to derivation of weak right inverse. We show that weak right inverse always exists and can be automatically generated from a wide class of sequential functions. We demonstrate our system with several nontrivial examples, including the maximum prefix sum problem, the prefix sum computation, maximum segment sum problem, and the line-of-sight problem. The experimental results show practical efficiency of our automatic parallelization algorithm and good speedups of the generated parallel programs. This is a joint work with K. Morita, A. Morihata, K. Matsuzaki and M. Takeichi.


Apprentissage de séquences Lorenza Saitta, Université du Piémont Oriental

à venir


GPAC, Analyse récursive, fonctions R-récursives : trois modèles de calcul sur les réels qui calculent les mêmes fonctions. Emmanuel Hainry, LORIA

Il existe de nombreux modèles de calcul sur les réels. Ces différents modèles calculent diverses fonctions, certains sont plus puissants que d'autres, certains sont deux à deux incomparables. Le calcul sur les réels est donc de ce point de vue bien différent du calcul sur les entiers qui est unifié par la thèse de Church-Turing qui affirme que tous les modèles raisonnables calculent les mêmes fonctions. Nous allons présenter trois modèles de calcul sur les réels : le GPAC, l'analyse récursive et les fonctions récursives puis montrer qu'en utilisant une bonne définition de ce qui est calculable, ces modèles sont équivalents. Ces résultats constituent donc une avancée vers une éventuelle unification des modèles de calcul sur les réels.


Apprentissage d'ensemble de classifieurs Lorenza Saitta, Université du Piémont Oriental

à venir


Outils de développement paralléle pour la Vision artificielle Joël Falcou, LASMEA Clermont-Ferrand

Les travaux présentés ici se proposent d'apporter une solution logicielle permettant de paralléliser des applications de vision artificielle complexes afin de les exécuter à une fréquence compatible avec le temps-réel vidéo. Ces outils se doivent de répondre à deux contraintes fortes : d'une part, permettre à des développeurs issus de la communauté Vision pour qui ces problématiques de parallélisation ne sont pas triviales de mener à bien la parallèlisation de leurs applications, et d'autre part de garantir que ces outils ne dégradent pas outre mesure les performances de ces applications. La difficulté est donc de conserver un niveau de performance élevé malgré des modèles de programmation et des interfaces de haut-niveau exprimés dans un langage largement diffusé dans la communauté Vision -- le C++ -- mais dont les fonctionnalités et le modèle de compilation jouent en notre défaveur. Pour résoudre ces difficultés, nous proposons une approche basée sur un mécanisme d'évaluation partielle qui va précalculer à la compilation les parties statiques de ces applications. Grâce à des techniques d'implantations à base de méta-programmation template, nous réinjectons directement au sein de nos bibliothèques ces étapes de pré-optimisation, créant ainsi des bibliothèques actives capable de s'auto-optimiser en fonction du contexte et pallier aux défauts de l'approche objet classique. Nous proposons donc deux bibliothèques basées sur ce principes : * EVE, qui propose une interface proche de celle de MATLAB et qui prend en charge la gestion du parallélisme SIMD; * QUAFF, qui se base sur un modèle de programmation à base de squelettes algorithmiques afin de faciliter le développement sur des machines MIMD. Plusieurs applications de vision artificielle de complexité réalistes sont ensuite implantées grace à ces outils et permettent de valider leur apport en terme de performance et de faciliter d'utilisation.