Gaignard Alban:
  laboratoire I3S
  Sophia Antipolis (France)

Résumé :

   Cette thèse s'intéresse à la production et au partage cohérent de connaissances distribuées dans le domaine des sciences de la vie. Malgré l'augmentation constante des capacités de stockage et de calcul des infrastructures informatiques, les approches centralisées pour la gestion de grandes masses de données scientifiques multi-sources deviennent inadaptées pour plusieurs raisons: (i) elles ne garantissent pas l'autonomie des fournisseurs de données qui doivent conserver un certain contrôle sur les données hébergées pour des raisons éthiques et/ou juridiques, (ii) elles ne permettent pas d'envisager le passage à l'échelle des plateformes en sciences computationnelles qui sont la source de productions massives de données scientifiques.

Nous nous intéressons, dans le contexte des plateformes collaboratives en sciences de la vie NeuroLOG et VIP, d'une part, aux problématiques de distribution et d'hétérogénéité sous-jacentes au partage de ressources, potentiellement sensibles ; et d'autre part, à la production automatique de connaissances au cours de l'usage de ces plateformes, afin de faciliter l'exploitation de la masse de données produites. Nous nous appuyons sur une approche ontologique pour la modélisation des connaissances et proposons à partir des technologies du web sémantique (i) d'étendre ces plateformes avec des stratégies efficaces, statiques et dynamiques, d'interrogations sémantiques fédérées et (ii) d'étendre leur environnent de traitement de données pour automatiser l'annotation sémantique des résultats d'expérience ``in silico'', à partir de la capture d'informations de provenance à l'exécution et de règles d'inférence spécifiques au domaine.

Les résultats de cette thèse, évalués sur l'infrastructure distribuée et contrôlée Grid'5000, apportent des éléments de réponse à trois enjeux majeurs des plateformes collaboratives en sciences computationnelles : (i) un modèle de collaborations sécurisées et une stratégie de contrôle d'accès distribué pour permettre la mise en place d'études multi-centriques dans un environnement compétitif, (ii) des résumés sémantiques d'expérience qui font sens pour l'utilisateur pour faciliter la navigation dans la masse de données produites lors de campagnes expérimentales, et (iii) des stratégies efficaces d'interrogation et de raisonnement fédérés, via les standards du Web Sémantique, pour partager les connaissances capitalisées dans ces plateformes et les ouvrir potentiellement sur le Web de données.

Mots-clés : Flots de services et de données scientifiques, Services web sémantiques, Provenance, Web de données, Web sémantique, Fédération de bases de connaissances, Intégration de données distribuées, e-Sciences, e-Santé.


Abstract :
This thesis addresses the issues of coherent distributed knowledge production and sharing in the Life-science area. In spite of the continuously increasing computing and storage capabilities of computing infrastructures, the management of massive scientific data through centralized approaches became inappropriate, for several reasons: (i) they do not guarantee the autonomy property of data providers, constrained, for either ethical or legal concerns, to keep the control over the data they host, (ii) they do not scale and adapt to the massive scientific data produced through e-Science platforms.

In the context of the NeuroLOG and VIP Life-science collaborative platforms, we address on one hand, distribution and heterogeneity issues underlying, possibly sensitive, resource sharing ; and on the other hand, automated knowledge production through the usage of these e-Science platforms, to ease the exploitation of the massively produced scientific data. We rely on an ontological approach for knowledge modeling and propose, based on Semantic Web technologies, to (i) extend these platforms with efficient, static and dynamic, transparent federated semantic querying strategies, and (ii) to extend their data processing environment, from both provenance information captured at run-time and domain-specific inference rules, to automate the semantic annotation of ``in silico'' experiment results.

The results of this thesis have been evaluated on the Grid'5000 distributed and controlled infrastructure. They contribute to addressing three of the main challenging issues faced in the area of computational science platforms through (i) a model for secured collaborations and a distributed access control strategy allowing for the setup of multi-centric studies while still considering competitive activities, (ii) semantic experiment summaries, meaningful from the end-user perspective, aimed at easing the navigation into massive scientific data resulting from large-scale experimental campaigns, and (iii) efficient distributed querying and reasoning strategies, relying on Semantic Web standards, aimed at sharing capitalized knowledge and providing connectivity towards the Web of Linked Data.

Keywords: Scientific workflows, Semantic web services, Provenance, Semantic web, Web of Linked Data, Federated knowledge bases, Distributed data integration, e-Science, e-Health.

   Jury :
Andrea Tettamanzi, Professeur, Université Nice Sophia Antipolis (Président du jury)
Oscar Corcho, Associate Professor, Universidad Politécnica de Madrid (Rapporteur)
Ollivier Haemmerlé, Professeur, Université Toulouse le Mirail (Rapporteur)
Olivier Corby, CR INRIA, Laboratoire I3S (Examinateur)
Bernard Gibaud, CR INSERM, Laboratoire LTSI (Examinateur)
Catherine Faron Zucker, Maître de Conférence, Université Nice Sophia Antipolis (Invitée)
Johan Montagnat, DR CNRS, Laboratoire I3S (Directeur de thèse)

Icart Sylvie:
  laboratoire I3S
  Sophia Antipolis (France)

Résumé :

   En télécommunications, l'égalisation aveugle de canal est le problème consistant à retrouver à partir des seules observations, les signaux qui ont été émis en amont d'un canal de transmission. Le canal est supposé linéaire, invariant dans le temps et à réponse impulsionnelle finie. La matrice de transfert qui relie les transformées en z des observations et des sources est alors une matrice polynomiale. Le spectre des observations est également un matrice polynomiale, mais comportant des puissances positives et négatives de z: il s'agit alors d'une matrice polynomiale de Laurent.
Nos travaux portent sur les propriétés de ces matrices ainsi que sur leurs factorisations. Les résultats classiques -tels que décompositions en valeurs propres-vecteurs propres, décomposition en valeurs singulières, décomposition QR- ne s'étendent pas simplement aux matrices polynomiales car l'ensemble considéré n'est pas un espace vectoriel mais un module. Certaines propriétés des matrices polynomiales nous permettront de construire des égaliseurs.

   Le Jury :
- Vladimir KUCERA, professeur à l'Académie des Sciences de Prague, rapporteur
- Eric MOREAU, professeur à l'Institut des Sciences de l'Ingénieur Toulon-Var, rapporteur
- Martine OLIVI, chargée de recherche à INRIA Sophia Antipolis Méditerranée, rapporteur
- Pierre COMON, directeur de recherche, GIPSA-Lab Grenoble, examinateur
- Jean-François LAFAY, professeur à l'Ecole Centrale de Nantes, examinateur

TOKO WOROU Mikaila :
  Laboratoire I3S
  Sophia Antipolis (France)

Résumé :

   L'aspect algorithmique de la détection des communautés dans les grands graphes est le sujet principal abordé dans ce mémoire. Cette problématique est appliquée dans le contexte d'un opérateur de télécommunications dont les graphes proviennent des échanges téléphoniques ou du réseau de télécommunication. Dans ce contexte, la détection des communautés permet la recommandation de contenu, l'analyse des données clients, le classement des recherches Web, la détection des spamming Web, les actions marketing et autres. Cette thèse s'articule autour de deux grandes parties.

Dans un premier temps, nous avons présenté le domaine de la détection des communautés. En effet cette problématique est étudiée sous des angles très variées par des communautés scientifiques différentes. Les principales méthodes et applications sont présentées dans cette première partie descriptive.

Dans un second temps, nous avons présenté notre contribution pour répondre à cette problématique.

Notre contribution se résume en deux principaux points.

Tout d'abord, nous avons présenté une nouvelle fonction de qualité, le facteur d'arbre, plus adaptée à la problématique de détection des communautés dans les réseaux sociaux. Ensuite, nous avons présenté un algorithme rapide et à performance garantie pour approximer le facteur d'arbre optimal et l'identification des communautés.
Ensuite, nous avons étudié la détection des communautés par l'optimisation de la modularité qui est la fonction de qualité la plus utilisée dans la littérature. Nous avons réécrit cette fonction, ce qui nous a permis d'avoir d'autres interprétations et de trouver des liens entre la modularité et d'autres fonctions de coupe du graphe. Enfin, nous avons proposé deux heuristiques pour approximer le problème d'optimisation de la modularité. Le premier est un algorithme basé sur l'analyse spectrale qui approxime la modularité en utilisant le vecteur de Fiedler de la matrice Laplacien du graphe.

Le second algorithme est une heuristique rapide basée sur la représentation de la modularité dans un espace métrique sous forme de forces s'inspirant de la physique. Cette représentation permet de définir un mécanisme d'interaction attraction/répulsion sur les sommets du graphe et d'obtenir des regroupements en communautés. Pour finir, nous construisons un outil de détection des communautés qui allie l'optimisation du facteur d'arbre et de la modularité.

Mots clés : graphes de terrain - algorithmes - réseaux sociaux - Modularité - facteur d'arbre - force du graphe - communautés - densité sous-graphe - analyse spectrale - Web.

Abstract

This thesis concerns the algorithmic aspects of the communities' detection in large graphs. The work can be used by a telecommunications operator whose graphs are associated to telephone calls and SMS or telecommunication networks. In this context, the detection of communities is used for the content recommendation, the analysis of customer data, the classification of Web pages, the detection of Web spamming, marketing activities and others. This thesis is organized around two major parts.

In the first part, we introduce the field of detection of communities. Indeed this problem has been studied with different points of view during the last years. The main methods and applications are presented in this descriptive part.

In the second part, we present our contribution to the problema. Our contribution consists of two main topics.

First, we introduce a new quality function, the fractional arboricity which is more adapted to the problem of detecting communities in social networks. Then, we present a fast and performance guaranteed algorithm to approximate the optimal fractional arboricity and identifies the communities in question.

Second, we study the detection of communities by optimizing the modularity, the most used quality function for communities' detection. We rewrite this function, and then, find new interpretations of the modularity and also links between the modularity and others cut functions. Finally, we propose two heuristics to approximate the optimization of the modularity. The first is an algorithm that approximates the modularity by using the Fiedler vector of the Laplacian matrix of the graph. The second algorithm is a fast heuristic based on the representation of physical interaction of nodes in a metric space. With this representation, we define an attraction/ repulsion mechanism between the vertices and then we obtain clusters in communities. Finally, we combine the optimization of the fractional arboricity and the optimization of the modularity into one communities' detection tool.

Keywords : large complex - networks - algorithms - social networks - scalability - fractional arboricity - graph strength - communities - densest subgraphs - spectral analysis - Web.

   Jury:
M. Jean-Claude BERMOND (Directeur de Recherche Émérite CNRS , Directeur)
M. Éric FLEURY (Professeur LIP ENS Lyon, Examinateur)
M. Jérôme GALTIER (Ingénieur/Chercheur Orange Labs , Co-Directeur)
M. Cyril GAVOILLE ( Professeur LABRI Université Bordeaux, Rapporteur)
M. Renaud LAMBIOTTE (Professeur Department of Mathematics/Naxys University of Namur, Examinateur)
M. Laurent VIENNOT (Directeur de Recherche INRIA LIAFA Paris , Rapporteur)

Provillard Julien:
  Laboratoire I3S
  Sophia Antipolis (France)

Résumé :

   Les automates cellulaires (CA) sont des systèmes dynamiques discrets très utilisés dans des nombreux domaines scientifiques. Leurs principales caractéristiques sont d'agir de manière locale, synchrone et uniforme sur l'ensemble des cellules d'une grille régulière. Ces systèmes produisent une grande variété de dynamiques et ont été largement étudiés dans la littérature.

De nombreuses variantes ont été proposées. Dans ce travail de thèse nous nous intéresserons ici aux automates cellulaires non-uniformes (nu-CA). Il s'agit, essentiellement, d'automates cellulaires dans lesquels la contrainte d'uniformité a été relâchée.

Dans un premier temps, nous considèrerons une famille de nu-CA qui permet de représenter des perturbations dans la structure d'un CA. Il s'agit d'étudier l'influence d'une panne ou d'une erreur ponctuelle dans l'implémentation d'un CA et notamment son influence sur la dynamique. Nous verrons que de nombreuses propriétés ne sont pas stables (à l'exception notable de l'équicontinuité) mais que l'on peut alors établir des liens entre un CA et ses modèles de perturbation.

Dans une seconde partie, nous cherchons à déterminer les propriétés que peut avoir un nu-CA en fonction des comportements locaux que l'on peut observer. On se donne un ensemble de règles locales qui peuvent intervenir dans un nu-CA et nous nous intéressons à la façon d'agencer ces règles pour produire certaines propriétés dans l'automate induit. Nous associons alors, à chacune de ces propriétés, un langage de distributions que nous caractérisons à l'aide de la théorie des langages.

Abstract :

Cellular automata (CA) are discrete dynamical systems widely used in many scientific domains. Their main characteristic is to act locally, synchronously and uniformly on a regular set of elementary components called cells. These systems have a huge variety of dynamical behaviors and have been extensively studied in literature.

Several variants have been proposed. In this work we are interested in non-uniform cellular automata (nu-CA). They are, essentially, CA in which the uniformity constraint has been relaxed.

In the first part, we study a family of nu-CA which allows to easily represent perturbations of the structure of a CA. The idea is to study the impact on the dynamics of a failure or of an error in the physical implementation of a CA by electronic components. Indeed, we will prove that several dynamical properties are not structurally stable (except for the equicontinuity property). However, we will show how to link properties of a CA and its "perturbed" versions.

In the second part, we try to infer the global properties of a nu-CA from the local behaviors we can observe. Given a set of local rules which can appear in a given nu-CA, we study the way of mixing them to obtain given global behaviors. Moreover, we associate global properties with peculiar formal languages and we completely characterize these formal languages. In this way we obtain a natural notion of complexity for properties on nu-CA. A property is as complex as the class of languages from which it is characterized.

   Le jury sera composé de :

- Rapporteurs
Olivier CARTON, Professeur, Université Paris 7
Nicolas OLLINGER, Professeur, Université d'Orléans
Nicolas SCHABANEL, Directeur de recherche CNRS, Université Paris 7

- Examinateurs
Nazim FATES, Chargé de recherche INRIA, Université Nancy 2
Julien CERVELLE, Professeur, Université Paris 12

- Directeur de thèse
Enrico FORMENTI, Professeur, Unversité Nice Sophia Antipolis

Leonardo SAMPAIO ROCHA :
  
  

Résumé :

   Une coloration propre d'un graphe est une fonction qui attribue une couleur à chaque sommet du graphe avec la restriction que 2 sommets voisins ont des couleurs distinctes. Les colorations propres permettent de modéliser des problèmes d'ordonnancement, d'allocation de fréquences ou de registres. Le problème de trouver une coloration propre d'un graphe qui minimise le nombre de couleurs est un problème NP-difficile très connu. Dans cette thèse, nous étudions le nombre de Grundy et le nombre b-chromatique des graphes, deux paramètres qui permettent d'évaluer quelques heuristiques pour le problème de la coloration propre. Nous commençons par dresser un état de l'art des résultats sur ces deux paramètres. Puis, nous montrons que déterminer le nombre de Grundy est NP-difficile sur les graphes bipartis ou cordaux mais polynomial sur le graphes sans P5 bipartis. Ensuite, nous montrons que déterminer le nombre b-chromatique est NP-difficile pour un graphe cordal et distance-héréditaire, et nous donnons des algorithmes polynomiaux pour certaines sous-classes de graphes blocs, complémentaires des graphes bipartis et P4-sparses. Nous considérons également la complexité à paramètre fixé de déterminer le nombre de Grundy (resp. nombre b-chromatique) et en particulier, nous montrons que décider si le nombre de Grundy (ou le nombre b-chromatique) d'un graphe G est au moins |V(G)| - k admet un algorithme FPT lorsque k est le paramètre. Enfin, nous considérons la complexité de nombreux problèmes liés à la comparaison du nombre de Grundy et nombre b-chromatique avec divers autres paramètres d'un graphe.

   

Masmoudi Khaled:
  Laboratoire I3S
  Sophia Antipolis (France)

Résumé :

   

   Jury :
Béatrice Pesquet-Popescu (rapporteur)
Simon Thorpe (rapporteur)
Jean-Marc Chassery (examinateur)
Laurent Perrinet (examinateur)
Marc Antonini(directeur de thèse)
Pierre Kornprobst (directeur de thèse)

Araujo Julio:
  Laboratoire I3S / INRIA
  Sophia-Antipolis / France

Résumé :

   Dans cette thèse, nous étudions plusieurs problèmes de théorie des graphes concernant la coloration et la convexité des graphes. La plupart des résultats figurant ici sont liés à la complexité de calcul de ces problèmes pour certaines classes de graphes.

Dans la première, et principale, partie de cette thèse, nous traitons de coloration des graphes qui est l'un des domaines les plus étudiés de théorie des graphes. Nous considérons d'abord trois problèmes de coloration appelés coloration gloutone, coloration pondérée et coloration pondérée impropre. Ensuite, nous traitons un problème de décision, appelé bon étiquetage de arêtes, dont la définition a été motivée par le problème d'affectation de longueurs d'onde dans les réseaux optiques.

La deuxième partie de cette thèse est consacrée à un paramètre d'optimisation des graphes appelé le nombre enveloppe (géodésique). La définition de ce paramètre est motivée par une extension aux graphes des notions d'ensembles et d'enveloppes convexes dans l'espace Euclidien.

Enfin, nous présentons dans l'annexe d'autres travaux développées au cours de cette thèse, l'un sur les hypergraphes orientés Eulériens et Hamiltoniens et l'autre concernant les systèmes de stockage distribués.

   Rapporteurs :
Ricardo Corrêa - UFC (Fortaleza, Brazil)
Frédéric Maffray - CNRS (Grenoble, France)
Christophe Paul - CNRS (Montpellier, France)

Éxaminateurs :
Jean-Claude Bermond - CNRS (Sophia Antipolis, France)
Frédéric Giroire - CNRS (Sophia Antipolis, France)
Cláudia Linhares Sales - UFC (Fortaleza, Brazil)

Henrio Ludovic:
  Laboratoire I3S / INRIA
  Sophia-Antipolis / France

Résumé :

   Mes travaux de recherche portent sur les modèles de programmation distribuée, principalement par objets et composants. Dans ce domaine, j'ai travaillé à fournir des outils facilitant la programmation d'applications distribuées à large échelle et vérifiant la correction de leur comportement. Pour faciliter la programmation d'applications distribuées je me suis intéressé à la mise au point de langages avec un fort niveau d'abstraction: objets actifs, squelettes algorithmiques, composants. Afin de vérifier la correction du comportement d'une application j'ai collaboré à la mise au point d'outils de spécification et de vérification comportementales d'applications distribuées. Mes travaux ont pour but de fournir un modèle formel des langages de programmations, des bibliothèques, et des environnements d'exécution fournies au programmeur afin de garantir un comportement sûr des applications distribuées.

Ma thèse m'a permis de mettre au point le calcul ASP modélisant le comportement des objets actifs et des futurs. Depuis, nous avons créé une version fonctionnelle de ce calcul que nous avons modélisé en Isabelle/HOL. Aussi j'ai fortement contribué à la définition d'un modèle à composants distribués -- le GCM (Grid Component model)--, à sa formalisation et à son utilisation pour programmer des composants adaptables ou autonomes. Enfin, j'ai contribué à la spécification et la vérification comportementale des programmes utilisant des objets actifs et des composants afin de garantir la sûreté de leur exécution. Actuellement, nous travaillons à la fois à une extension multi-threadée du modèle à objets actifs mieux adaptée aux machines multi-coeurs, et à l'utilisation de méthodes formelles pour mettre au point et prouver la correction d'un algorithme de diffusion pour réseau pair-à-pair de type CAN (Content Adressable Network). Ce manuscrit fournit une vue d'ensemble de tous ces travaux.

Abstract : My research focuses on distributed programming models, more precisely using ob jects and components. In this area, I provided tools easing the programming of large-scale distributed applications and verifying their correct behaviour. To facilitate the programming of distributed applications, I contributed to the design and the development of languages with a high level of abstraction: active ob jects, algorithmic skeletons, components. To verify correction of the behaviour of an application, I have contributed to the creation of tools for specifying and verifying behavioural distributed applications. My work aims to provide a strong model of programming languages, libraries, and runtime environments provided to the developer, and to guarantee the safe behaviour of distributed applications.

During my thesis, I developed the ASP calculus for modelling the behaviour of active ob jects and futures. Since, we created a functional version of this calculus and formalised it in Isabelle/HOL. I also strongly contributed to the definition of a distributed component model - the GCM (Grid Component Model) -, to its formalisation, and to its use for programming adaptive or autonomous components. Finally, I contributed to the specification and behavioural verification of programs based on active ob jects and components, in order to ensure their safe execution. Currently we are working both on a multi-threaded extension of the active ob ject model, better suited for multi-core machine, and on the use of formal methods to design and prove the correction of an algorithm for broadcast on CAN-like peer-to-peer networks (Content Addressable Network). This manuscript provides an overview of all these works.

   
Président du Jury
Pr. Michel Riveill Université de Nice-Sophia-Antipolis - I3S, France

Rapporteurs
Pr. Gordon Blair Lancaster University, United Kingdom
Dr. Pascal Poizat Université d’Evry Val d’Essonne, France
Pr. Davide Sangiorgi University of Bologna, Italy

Examinateurs
Dr. Fabienne Boyer Université Joseph Fourier - LIG, France
Dr. Alan Schmitt INRIA Rennes, France

Invité
Dr. Eric Madelaine INRIA Sophia-Antipolis, France

Bukina Elena:
  Laboratoire I3S
  Sophia-Antipolis / France

Résumé :

   Nous nous intéressons dans ce manuscrit au problème relatif à la minimisation de fonctions quadratiques dont la matrice hessienne est creuse, symétrique et définie positive (ou, de manière équivalente, au problème de résolution de systèmes linéaires de grande taille). Les méthodes classiques itératives fréquemment employées pour résoudre ce problème procèdent en choisissant successivement des pas dont la longueur et la direction dépendent du spectre de la matrice et sont donc adaptés au problème particulier traité. Ce choix adaptatif du pas peut cependant limiter l'efficacité de l'implémentation parallèle d'un algorithme: la présence de nombreux produits scalaires à calculer limite grandement les performances en imposant des étapes de synchronisation ainsi qu'une communication globale coûteuse dans le cas particulier des machines parallèles à mémoire distribuée disposant d'un grand nombre de processeurs.

L'approche proposée dans cette thèse se fonde sur l'utilisation d'une famille de méthodes du gradient pour laquelle l'inverse de la longueur des pas est choisi d'avance. Pour ce type de méthodes, l'utilisation d'une suite de longueurs de pas ayant une distribution arc sinus sur l'intervalle défini par les limites du spectre de la matrice hessienne permet de converger rapidement. De fait, il n'y a aucun besoin d'étudier précisément le détail du spectre dans la mesure où les longueurs de pas ne sont reliées au problème que par les valeurs propres extrêmes de la matrice hessienne. Nous proposons d'estimer celles-ci pendant le déroulement de l'algorithme en utilisant les moments d'une mesure de probabilité associée au spectre matriciel et produite par l'algorithme lui-même. En conséquence de la simplicité du calcul de la longueur des pas, le calcul de produits scalaires à chaque itération de l'algorithme n'est pas nécessaire (ils ne sont utilisés que sur un petit nombre d'itérations prédéfinies dans le but de déterminer les limites spectrales de la matrice) rendant ainsi notre approche particulièrement intéressante dans un contexte de calcul parallèle.

Nous proposons plusieurs méthodes de gradient couplées à différentes suites de longueurs de pas précalculées ainsi qu'à plusieurs estimateurs de valeurs propres. En pratique, les performances de la méthode la plus efficace (en termes de propriété de convergence et de coût calcul) sont testées sur un ensemble de problèmes théoriques et pratiques. La même approche est aussi considérée pour l'optimisation quadratique convexe sous contraintes d'égalité.

Abstract:

In this work we consider the minimization of quadratic functions with sparse and symmetric positive-definite Hessian matrices (or, equivalently, the solution of large linear systems of equations). Classical iterative methods for solving these problems proceed by choosing the step sizes (and search directions) relatively to the spectrum of the matrix, which are thus adapted to the particular problem considered. This type of adaptive choice results in computations that may limit the efficiency of parallel implementations of a given method: the presence of several (separate) inner products to be computed at each iteration creates blocking steps due to the required global communication on some distributed-memory parallel machines with large number of processors.

The approach developed in this thesis is focused on the use of a family of gradient methods where the inverse step sizes are selected beforehand. For this type of methods, the use of sequences of step sizes with the arcsine distribution on the interval defined by the bounds of the matrix spectrum allows to achieve fast rates of convergence. Therefore, there is no need to extensively study the spectrum since the step sizes are connected to the problem through only the extremal eigenvalues of the Hessian matrix. We propose to estimate the extreme eigenvalues during the run of algorithm, using the moments of a probability measure associated with the matrix spectrum and generated by the algorithm itself. Due to the simplicity of the step size generation, the computation of inner products at each iteration is not required (they are needed at just a small number of pre-defined iterations to determine the spectral boundaries), making the approach particularly interesting in a parallel computing context.

Several effective gradient methods are proposed coupled with pre-computed sequences of step sizes and eigenvalue estimators. The practical performance of the most appealing of them (in terms of convergence properties and required computational effort) is tested on a set of theoretical and real-life test problems. The same approach is also considered for convex quadratic optimization subject to equality constraints.

   Jury :
Coralia CARTIS, University of Edinburgh, UK
Pierre COMON, CNRS-I3S, Sophia Antipolis, France
Stephane GAUBERT, INRIA, Ecole Polytechnique, France
Jean-Baptiste HIRIART-URRUTY, Institut de mathématiques de Toulouse, France
Luc PRONZATO, CNRS-I3S, Sophia Antipolis, France
Anatoly ZHIGLJAVSKY, Cardiff University, UK

Ghailen Laouini:
  Laboratoire I3S
  Sophia-Antipolis / France

Résumé :

   Dans ces travaux, nous nous intéressons à la modélisation de la variabilité du rythme cardiaque (HRV) à l'exercice. L'objectif de cette thèse est donc d'étudier la HRV l'exercice en prenant en compte la respiration.
Le modèle IPFM a été utilisé pour expliquer le mécanisme utilisé par le système nerveux autonome pour contrôler le rythme cardiaque. A l'aide des pics générés par ce modèle, nous étudions la relation entre la période cardiaque, qui est la différence entre deux pics RR successifs, et le signal de modulation.
Nous proposons le modèle TVIPFM avec trois approches différentes (A, B, C), comme alternative au modèle IPFM pour estimer la modulation du système nerveux autonome, adaptée à l'exercice. Le modèle TVIPFM, permet alors de corriger la variabilité cardiaque. Cette variabilité sera filtrée dans la bande de la fréquence respiratoire et dans le domaine temps-fréquence, en utilisant différentes méthodes de représentations temps-fréquence. Ceci s'explique par le caractère non stationnaire du signal observé. Nous présentons différentes représentations temps-fréquence linéaires et quadratiques permettant ce filtrage et justifiant leur utilisation. L'EMD est abordée également pour sa propriété de décomposition en signaux monocomposantes. Des simulations nous ayant permis de sélectionner la meilleure correction IPFM et la meilleure représentation temps-fréquence pour le filtrage, une application réelle étendue est proposée. Dans celle-ci, on montre qu'à l'aide de cette chaine de traitement la corrélation avec l'age de la transplantation et la variabilité du rythme cardiaque existe bien.
Mots-Clefs: Électrocardiogramme (ECG), variabilité cardiaque (HRV), système nerveux autonome (ANS), Arythmie sinusale respiratoire (RSA), modèle IPFM, modèle TVIPFM, EMD, représentation temps-fréquence.

Abstract :

In this thesis, we focus on the modeling of heart rate variability (HRV) during exercise. The objective of this thesis is to study HRV during exercise, while taking respiration into account. The IPFM model helps to explain the mechanism used by the autonomic nervous system to control the heartbeat. With peaks generated by this model, we study the relationship between the heart period, which is the difference between two successive RR peaks, and the modulation signal.
We suggest the TVIPFM model with three different approaches (A, B, C), as an alternative to the IPFM model to estimate the modulation of the autonomic nervous system, adapted to the exercise. The TVIPFM model then allows for correction of the heart rate variability. This variability will be filtered around the frequency band of respiration in the time-frequency domain, using different methods of time-frequencyrepresentations.
This is explained by the fact that the signal being observed is not stationary. We present different time-frequency representations for the linear and quadratic filtering and justify their use.
The EMD is also addressed because of its decomposition property in ''monocomponent'' signals. Simulations allowing us to select the best IPFM correction and the best time-frequency representation for filtering, a real application range is proposed. In it, we show that using this process, correlation between age of transplantation and heart rate variability indeed exists.

Keywords : Electrocardiogram (ECG), Heart Rate Variability (HRV), Autonomic Nervous System (ANS), Respiratory Sinus Arrythmia (RSA), IPFM model, TVIPFM model, EMD, time-frequency representation.

   Leif Sornmo, Université de Lund, Suède (Rapporteur)
Guy Carrault, Université de Rennes I (Rapporteur)
Serge Colson, Université de Nice-Sophia Antipolis (Examinateur)
Sofiane Boudaoud, Université Technologique de Compiègne (Examinateur)
Olivier Meste, Université de Nice-Sophia Antipolis (Directeur de thèse)

Thiesse Jean-Marc:
  Laboratoire I3S
  Sophia-Antipolis / France

Résumé :

   Cette thèse est dédiée à l’amélioration des performances de compression vidéo. Deux types d’approches, conventionnelle et en rupture, sont explorées afin de proposer des méthodes efficaces de codage Intra et Inter pour les futurs standards de compression. Deux outils sont étudiés pour la première approche. Tout d’abord, des indices de signalisations sont habilement traités par une technique issue du tatouage permettant de les masquer dans les résiduels de luminance et de chrominance de façon optimale selon le compromis débit-distorsion. La forte redondance dans le mouvement est ensuite exploitée pour améliorer le codage des vecteurs de mouvement. Après observation des précédents vecteurs utilisés, un fin pronostic permet de déterminer les vecteurs résiduels à privilégier lors d’une troisième étape de modification de la distribution des résiduels. 90% des vecteurs codés sont ainsi pronostiqués, ce qui permet une nette réduction de leur coût.
L’approche en rupture vient de la constatation que H.264/AVC et son successeur HEVC sont basés sur un schéma prédictif multipliant les choix de codage, les améliorations passent alors par un meilleur codage de la texture à l’aide d’une compétition accrue. De tels schémas étant bornés par la signalisation engendrée, il est alors nécessaire de transférer des décisions au niveau du décodeur. Une approche basée sur la détermination conjointe au codeur et au décodeur de paramètres de codage à l’aide de partitions causales et ainsi proposée et appliquée aux modes de prédiction Intra et à la théorie émergente de l’échantillonnage compressé. Des performances encourageantes sont reportées et confirment l’intérêt d’une telle solution innovante.


Abstract :

This Ph.D. thesis deals with the improvement of video compression efficiency. Both conventional and breakthrough approaches are investigated in order to propose efficient methods for Intra and Inter coding dedicated to next generations video coding standards.
Two tools are studied for the conventional approach. First, syntax elements are cleverly transmitted using a data hiding based method which allows embedding indices into the luminance and chrominance residuals in an optimal way, rate-distortion wise. Secondly, the large motion redundancies are exploited to improve the motion vectors coding. After a statistical analysis of the previously used vectors, an accurate forecast is performed to favor some vector residuals during a last step which modifies the original residual distribution. 90% of the coded vectors are efficiently forecasted by this method which helps to significantly reduce their coding cost.
The breakthrough approach comes from the observation of the H.264/AVC standard and its successor HEVC which are based on a predictive scheme with multiple coding choices, consequently future improvements shall improve texture by extensively using the competition between many coding modes. However, such schemes are bounded by the cost generated by the signaling flags and therefore it is required to transfer some decisions to the decoder side. A framework based on the determination of encoding parameters at both encoder and decoder side is consequently proposed and applied to Intra prediction modes on the one hand, and to the emerging theory of compressed sensing on the other hand. Promising results are reported and confirm the potential of such an innovative solution.

   Jury :
James FOWLER, Mississipi State University, USA, Rapporteur
Pascal FROSSARD, EPFL, Suisse, Rapporteur
Philippe SALEMBIER, University of Catalonia, Espagne, Rapporteur
Marc ANTONINI, CNRS-Université de Nice-Sophia Antipolis, Directeur de thèse
Joël JUNG, Orange Labs, France, Encadrant de thèse
Frédéric DUFAUX, CNRS-Télécom Paris Tech, France, Examinateur
Pier Luigi DRAGOTTI, Imperial College London, UK, Examinateur
Jérôme VIERON, ATEME, France, Examinateur

Rojas Balderrama Javier :
  Laboratoire I3S
  Sophia Antipolis / France

Résumé :

   L'intérêt va croissant parmi les communautés scientifiques pour le partage de données et d'applications qui facilitent les recherches et l'établissement de collaborations fructueuses. Les domaines interdisciplinaires tels que les neurosciences nécessitent particulièrement de disposer d'une puissance de calcul suffisante pour l'expérimentation à grande échelle. Malgré les progrès réalisés dans la mise en œuvre de telles infrastructures distribuées, de nombreux défis sur l'interopérabilité et le passage à l'échelle ne sont pas complètement résolus. L'évolution permanente des technologies, la complexité intrinsèque des environnements de production et leur faible fiabilité à l'exécution sont autant de facteurs pénalisants.

Ce travail porte sur la modélisation et l'implantation d'un environnement orienté services qui permet l'exécution d'applications scientifiques sur des infrastructures de calcul distribué, exploitant leur capacité de calcul haut débit. Le modèle comprend une spécification de description d'interfaces en ligne de commande; un pont entre les architectures orientées services et le calcul globalisé; ainsi que l'utilisation efficace de ressources locales et distantes pour le passage à l'échelle. Une implantation de référence est réalisée pour démontrer la faisabilité de cette approche. Sa pertinence et illustrée dans le contexte de deux projets de recherche dirigés par des campagnes expérimentales de grande ampleur réalisées sur des ressources distribuées. L'environnement développé se substitue aux systèmes existants dont les préoccupations se concentrent souvent sur la seule exécution. Il permet la gestion de codes patrimoniaux en tant que services, prenant en compte leur cycle de vie entier. De plus, l'approche orientée services aide à la conception de flux de calcul scientifique qui sont utilisés en tant que moyen flexible pour décrire des applications composées de services multiples.

L'approche proposée est évaluée à la fois qualitativement et quantitativement en utilisant des applications réelles en analyse de neuro-images. Les expériences qualitatives sont basées sur l'optimisation de la spécificité et la sensibilité des outils de segmentation du cerveau utilisés pour traiter des Image par Raisonnance Magnétique de patients atteints de sclérose en plaques. Les expériences quantitative traitent de l'accélération et de la latence mesurées pendant l'exécution d'études longitudinales portant sur la mesure d'atrophie cérébrale chez des patients affectés de la maladie d'Alzheimer.


Abstract :

There is an increasing interest among scientific communities for sharing data and applications in order to support research and foster collaborations. Interdiciplinary domains like neurosciences are particularly eager of solutions providing computing power to achieve large--scale experimentation. Despite all progresses made in this regard, several challenges related to interoperability, and scalability of Distributed Computing Infrastructures are not completely resolved though. They face permanent evolution of technologies, complexity associated to the adoption of production environments, and low reliability of these infrastructures at runtime.

This work proposes the modelling and implementation of a service--oriented framework for the execution of scientific applications on Distributed Computing Infrastructures taking advantage of High Throughput Computing facilities. The model includes a specification for description of command-line applications; a bridge to merge service-oriented architectures with Global computing; and the efficient use of local resources and scaling. A reference implementation is proposed to demonstrate the feasibility of the approach. It shows its relevance in the context of two application-driven research projects executing large experiment campaign on distributed resources. The framework is an alternative to existing solutions that are often limited to execution consideration only, as it enables the management of legacy codes as services and takes into account their complete lifecycle. Furthermore, the service-oriented approach helps designing scientific workflows which are used as a flexible and way of describing application composed with multiple services.

The approach proposed is evaluated both qualitatively and quantitatively using concrete applications in the area of neuroimaging analysis. The qualitative experiments are based on the optimization of specificity and sensibility of the brain segmentation tools used in the analysis of Magnetic Resonance Images of patient affected by Multiple Sclerosis. On the other hand, quantitative experiments deal with speedup and latency measured during the execution of longitudinal brain atrophy detection in patients impaired by Alzheimer's disease.

   Le jury sera composé de :

* Bernard Gibaud Inserm, Rennes (Rapporteur)
* Johan Montagnat CNRS, Sophia Antipolis (Directeur)
* Michel Riveill Université Nice Sophia Antipolis (Président)
* Christian Pérez Inria, Lyon (Rapporteur)

Le Tallec Jean-François:
  Laboratoire I3S
  Sophia-Antipolis / France

Résumé :

   La conception des systèmes sur puce s’appuie souvent sur SystemC/C++ qui permet des descriptions architecturales et comportementales à différents niveaux d’abstraction. D’autres approches se tournent vers l’automatisation de l’assemblage de plates-formes dites virtuelles (format IP-Xact). L’utilisation des techniques de l’ingénierie des modèles est une voie plus récente avec des profils UML tels que MARTE. Dans cette thèse, nous étudions les possibilités de modélisation de ces différentes approches et les passe- relles disponibles entre elles. Motivés par la disponibilité de modèles SystemC et par les facilités offertes par MARTE, nous traitons de l’export des modèles SystemC. Au-delà de la simple conversion entre formats, nous décrivons la mise en oeuvre d’une passerelle entre l’implémentation SystemC d’un design et sa version modèle dans le format IP-Xact. La repr´esentation IP-Xact peut ensuite ˆetre de nouveau transformée en modèles MARTE par des outils déjà existants. Nous présentons les travaux connexes avant d’exposer notre vision et sa réalisation au travers de l’outil SCiPX (SystemC to IP-Xact). Dans un second temps, nous présentons plus en détails les possibilités permises par le profil UML-MARTE, son modèle de temps et le langage de spécification de contraintes temporelles CCSL. Nous abordons les pro- blèmes liés à la modélisation de protocoles à différents niveaux d’abstraction et plus spécialement ceux posés par le raffinement entre les niveaux TLM et RTL. Cette étude met en évidence des insuffisances de CCSL concernant la spécification des priorités. Nous proposons un enrichissement de CCSL pour lui permettre de manipuler ce concept de priorité.

Abstract :

The design of System on Chip mostly relies on SystemC/C++. This language allows architectural and behavioural descriptions at different abstraction levels. Others approaches consider automated assem- bly of components into actual or virtual platforms (IP-Xact format). Using Model Driven Engineering techniques is a new trend, which may benefit from UML profiles (especially MARTE). In this thesis, we study the modelling power of these approaches and the possible bridges between them. SystemC provides a great deal of examples while MARTE offers facilities in system modelling at different levels. So, we try to export SystemC designs to MARTE models. Beyond the mere conversion between formats, we propose an abstraction mechanism from SystemC code to models in IP-Xact formats. The IP-Xact description is then transformed into MARTE models with existing tools. We review related works and propose our solution leading to a dedicated tool called SCiPX (standing for SystemC to IP-Xact). In the second part of the thesis we apply the UML profile MARTE, its time model, and the associated language for specification of temporal constraints (CCSL) to specify interactions among components. A special attention is paid to protocol refinement. This study reveals a lack of CCSL for capturing the concept of priority. An improvement in the CCSL constraint solver is proposed to overcome this limitation.

   Jury :

Charles André Université de Nice Sophia-Antipolis
Florence Maraninchi INP Grenoble / ENSIMAG
Christophe Moy Supélec Rennes
Jean-Luc Dekeyser Université de Lille 1
Robert de Simone INRIA Sophia Antipolis Méditerrannée

VU Viet-Hoang:
  Laboratoire I3S
  Sophia-Antipolis / France

Résumé :

   Aujourd'hui, le tourisme devient un secteur économique important. Afin de supporter le développement du marché électronique du tourisme, nous adoptons une méthode de Matchmaking Sémantique basés sur l'ontologie récemment proposées dans la littérature pour traiter le problème de l'hétérogénéité du domaine. L'idée est d'utiliser les Logiques de Descriptions (LDs) pour représenter la sémantique des demandes et des offres disponibles en référence à une ontologie et d'employer des services d'inférence automatique pour classer et proposer les meilleures solutions. De cette manière, la méthode facilite les processus de découverte et de négociation sur le marché. En outre, elle peut aussi être utilisée pour aider à la création des correspondances sémantiques, un processus important qui assure l'interopérabilité entre des systèmes d'information touristique hétérogènes. Pour réaliser le matchmaking, une nouvelle méthode d'inférence, Concept Abduction, a été développée pour la LD ALN. Parce que la représentation des ontologies du tourisme nécessite en général plus de l'expressivité, le premier objectif de cette thèse est d'étendre cette méthode d'inférence pour la LD plus expressive SHIQ. D'ailleurs, il est reconnu que le tourisme est tellement hétérogène qu'une seule ontologie ne peut pas couvrir entièrement le domaine. Pour ce but, multiple ontologies distribués et modulaires doivent être utilisées. Cela conduit au deuxième objectif de la thèse: développer Concept Abduction pour SHIQP, une extension de SHIQ pour les ontologies modulaires distribuées. Enfin, nous proposons une architecture pour réaliser un Sémantique Matchmaker pour les systèmes d'information touristique distribués.


Abstract :

Today, travel and tourism is a sector that plays a more and more important role in the modern economy. To support the development of an electronic marketplace for tourism, we adopt an ontology-based Semantic Matchmaking method proposed so far in the literature to deal with the heterogeneity of the domain. The idea is to use Description Logics (DLs) to represent the semantics of demands and supplies available on the marketplace with reference to an ontology and then employ automated reasoning services to classify and then propose the best potential matches. Using Semantic Matchmaking thereby facilitates the discovery and negotiation process in the marketplace. Besides, the method can also be used to assist in the ontology mapping, an important process for providing the semantic interoperability between heterogeneous tourism systems. To realize the matchmaking process, a new non-standard inference, Concept Abduction, is developed for a quite inexpressive DL ALN. Because the representation of ontologies in the tourism domain requires generally more expressivity, we have to extend this inference method to a more expressive DL SHIQ and that is the first main objective of this thesis. Furthermore, it was acknowledged that travel and tourism is so highly heterogeneous that no one single global ontology can cover the whole domain. Instead, distributed and modular ontologies have to be used. That leads to the second objective of this thesis: developing Concept Abduction for the Package-based DL SHIQP, an extension of SHIQ for distributed and modular ontologies. Finally, we propose an architecture to realize a Semantic Matchmaker for distributed tourism information systems.

   Le jury sera composé de :
- Mme. Parisa GHODOUS (Professeur des universités, Université de Lyon 1, Rapporteur)
- M. Richard CHBEIR (Maitre de Conférences HDR 2010, Université de Bourgogne, Rapporteur)
- M. Olivier HAEMMERLE (Professeur des universités, Université Toulouse le Mirail)
- Mme. Catherine FARON-ZUCKER (Maitre de Conférences, Université de Nice Sophia Antipolis)
- M. Serge MIRANDA (Professeur des universités, Université de Nice Sophia Antipolis)
- M. Nhan LE-THANH (Professeur des universités, Université de Nice Sophia Antipolis, Directeur de thèse)

Tran Vinh Duc:
  Laboratoire I3S
  Sophia-Antipolis / France

Résumé :

    Le sujet de cette thèse est l'étude des langages de mots infinis, en particulier les puissances infinies de langages de mots finis (puissance w). Plus précisément, nous nous intéressons à la question ouverte suivante: étant donné un langage L, existe-t-il un w-code C tel que C^w = L^w ? Cette question est l'analogue de celle pour la concaténation finie: un sous-monoïde d'un monoïde libre est-il engendré par un code ou non ?

Dans un premier temps, nous étudions l'ensemble des relateurs d'un langage L, c'est-à-dire les couples de factorisations différentes d'un même mot de L^* + L^w; nous établissons une condition nécessaire pour que L^w ait un code ou un w-code générateur. Ensuite, nous définissons une nouvelle classe de langages: les langages à un relateur. Leurs ensemble de relateurs est le plus simple possible sans qu'ils soient des codes. Pour cette classe intéressante de langages, on caractérise les langages L tels qu'il existe un w-code ou un code C tels que L^w = C^w. On montre que C ne peut pas être un langage fini. Enfin, une caractérisation des codes concernant les mots infinis nous amène à définir les langages réduits; nous considérons les propriétés de ces langages en tant que générateurs de langages de mots infinis.

   jury composé de :

- Olivier Carton (Université Paris Diderot), rapporteur
- Gabriele Fici (Université de Nice Sophia-Antipolis), examinateur
- Enrico Formenti (Université de Nice - Sophia Antipolis), examinateur
- Sandrine Julia (Université de Nice - Sophia Antipolis), co-directrice
- Igor Litovsky (Université Nice Sophia Antipolis), directeur
- Gwénaël Richomme (Université Paul-Valéry Montpellier 3), rapporteur.

Rivera Marcela:
  Laboratoire I3S
  Sophia-Antipolis / France

Résumé :

   En programmation orientée à composants, mais particulièrement dans des environnements distribués, les composants ont besoin d'être adaptatifs. Une majeure partie de cette adaptation repose sur la reconfiguration dynamique. Dans cette thèse, nous introduisons une nouvelle approche pour la reconfiguration des modèles de composants distribu\'es, avec l'objectif de faciliter le processus de reconfiguration et d'assurer la consistence et la cohérence du système.

Avant d'exécuter une reconfiguration, il est nécessaire que les composants soient dans un état cohérent et stable, afin d'éviter des incohérences dans le processus de reconfiguration. Pour ceci, nous concevons un algorithme pour l'arrêt d'un composant d'une manière sécurisé et atteignant un état stable. Cela a été réalisé en mettant en oeuvre un mécanisme de marquage et d'interception qui permet d'ajouter des informations aux requ\^etes et de manipuler leurs flux, afin de décider lesquelles doivent être servies avant d'arrêter le composant.

Nous avons conçu un ensemble de primitives de reconfiguration de haut niveau qui permettent de réaliser des opérations de reconfiguration plus complexes. Nous fournissons un contrôleur supplémentaire à notre modèle de composant qui implémente ces primitives.

Pour le déclenchement des tâches de reconfiguration, nous avons étendu le langage FScript pour lui permettre d'exécuter des reconfiguration distribuées, en déléguant certaines actions à des composants. Pour ceci, nous avons défini un contrôleur additionnel à l'intérieur de la membrane des composants.

Nous avons testé notre approche sur deux applications basées sur GCM/ProActive: CoCoME et TurnTable.

Abstract :

For component programming, but even more specifically in distributed and Grid environments, components need to be highly adaptative. A great part of adaptativeness relies on dynamic reconfiguration of component systems. We introduce a new approach for reconfiguring distributed components with the main objective to facilitate the reconfiguration process and ensure the consistency and coherence of the system.

First, before executing a reconfiguration it is necessary that the components is a coherent and quiescent state. This is done to avoid inconsistency in the reconfiguration process. To achieve this, we design an algorithm for stopping a component in a safe manner and reach this quiescent state. This was realized by implementing a tagging and interception mechanism that adds informations to the requests and manipulates their flow in order to decide which of them must be served before stopping the component.

Next, we designed a set of high-level reconfiguration primitives to achieve more complex reconfiguration operations. These primitives include: add, remove, duplicate, replace, bind, and unbind. We provide an additional controller to our component model which implements these primitives.

Additionally, for triggering the reconfiguration tasks, we extended the FScript language to give it the capability of executing distributed reconfiguration actions, by delegating some actions to specific components. To achieve this objective, we defined an additional controllers inside the membrane of the components.

We tested our implementation over two GCM/ProActive based applications: the CoCoME example and the TurnTable example.

   Jury:
Françoise Baude, CNRS, France, Président
Florian Kammueller, Middlesex University, London, UK, Rapporteur
Christian Perez, INRIA, Lyon, France, Rapporteur
Ludovic Henrio, Université de Nice-Sophia Antipolis, France, Co-directeur

Peretti Pezzi Guilherme:
  Laboratoire I3S
  Sophia-Antipolis / France

Résumé :

   Simulations hydrauliques d'haute performance dans la Grille avec Java et ProActive

L'optimisation de la distribution de l'eau est un enjeu crucial qui a déjà été ciblé par de nombreux outils de modélisation. Des modèles utiles, implémentés il y a des décennies, ont besoin d'évoluer vers des formalismes et des environnements informatiques plus récents. Cette thèse présente la refonte d'un ancien logiciel de simulation hydraulique (IRMA) écrit en FORTRAN, qui a été utilisé depuis plus de 30 ans par la Société du Canal de Provence, afin de concevoir et maintenir les réseaux de distribution d'eau. IRMA a été développé visant principalement pour le traitement des réseaux d'irrigation - en utilisant le modèle probabiliste d'estimation de la demande de Clément - et il permet aujourd'hui de gérer plus de 6.000 km de réseaux d'eau sous pression. L'augmentation de la complexité et de la taille des réseaux met en évidence le besoin de moderniser IRMA et de le réécrire dans un langage plus actuel (Java).

Cette thèse présente le modèle de simulation implémenté dans IRMA, y compris les équations de perte de charge, les méthodes de linéarisation, les algorithmes d'analyse de la topologie, la modélisation des équipements et la construction du système linéaire. Quelques nouveaux types de simulation sont présentés: la demande en pointe avec une estimation probabiliste de la consommation (débit de Clément), le dimensionnement de pompe (caractéristiques indicées), l'optimisation des diamètres des tuyaux, et la variation de consommation en fonction de la pression. La nouvelle solution adoptée pour résoudre le système linéaire est décrite et une comparaison avec les solveurs existants en Java est présentée.

La validation des résultats est réalisée d'abord avec une comparaison entre les résultats obtenus avec l'ancienne version FORTRAN et la nouvelle solution, pour tous les réseaux maintenus par la Société du Canal de Provence. Une deuxième validation est effectuée en comparant des résultats obtenus à partir d'un outil de simulation standard et bien connu (EPANET). Concernant les performances de la nouvelle solution, des mesures séquentielles de temps sont présentées afin de les comparer avec l'ancienne version FORTRAN. Enfin, deux cas d'utilisation sont présentés afin de démontrer la capacité d'exécuter des simulations distribuées dans une infrastructure de grille, utilisant la solution ProActive. La nouvelle solution a déjà été déployée dans un environnement de production et démontre clairement son efficacité avec une réduction significative du temps de calcul, une amélioration de la qualité des résultats et une intégration facilitée dans le système d'information de la Société du Canal de Provence, notamment la base de données spatiales.


Abstract :

Optimization of water distribution is a crucial issue which has been targeted by many modeling tools. Useful models, implemented several decades ago, need to be updated and implemented in more powerful computing environments. This thesis presents the redesign of a legacy hydraulic simulation software (IRMA) written in FORTRAN that has been used for over 30 years by the Société du Canal de Provence in order to design and to maintain water distribution networks. IRMA was developed aiming mainly the treatment of irrigation networks – by using the Clément demand model and is now used to manage more than 6.000 km of piped networks. The growing complexity and size of networks requested to update IRMA and to rewrite the code by using modern tools and language (Java).

This thesis presents IRMA's simulation model, including its head loss equations, linearization methods, topology analysis algorithms, equipments modeling and the linear system construction. Some new specific simulation features are presented: scenarios with probabilistic demands (Débit de Clément), pump profiling, pipe sizing, and pressure driven analysis. The new adopted solution for solving the linear system is described and a comparison with the available Java solvers is presented.

The validation of results is achieved with a comparison between the previous FORTRAN results of all networks maintained by the Société du Canal de Provence and the values obtained using the new solution. A second validation is performed by comparing the results obtained from a standard and well-known simulation tool (EPANET). Regarding the performance of the new solution, a sequential benchmark comparing with the former FORTRAN version is presented. Finally, two use cases are presented in order to demonstrate the capability of executing distributed simulations in a Grid infrastructure, using the ProActive solution. The new solution has been already deployed in a production environment and demonstrates clearly its efficiency with a significant reduction of the computation time, an improved quality of results and a transparent integration with the company's modern software infrastructure (spatial databases).

   Jury :

Jocelyne ERHEL - INRIA Rennes (rapporteur)
Pierre-Olivier MALATERRE - CEMAGREF Montpellier (rapporteur)
Olivier PILLER - CEMAGREF Bordeaux (co-rapporteur)
Yann VIALA - Société du Canal de Provence (examinateur)
Philippe GOURBESVILLE - Université de Nice (president)
Denis CAROMEL - Université de Nice (directeur)

Legrand Virginie:
  Laboratoire I3S
  Sophia-Antipolis / France

Résumé :

   Cette thèse s’intéresse à l’orchestration de services répartie, résultat (1) d’une approche explicite de découpage d’une orchestration en sous-orchestrations localisées sur des sites physiques distants à des fins de protection de données par exemple, ou (2) d’une approche constructive issue du regroupement d’orchestrations existantes potentiellement hétérogènes, afin de constituer une orchestration globale mais répartie. Les orchestrations de services reflètent des processus métiers, souvent de longue durée, et qui doivent donc pouvoir être adaptables dynamiquement à l’exécution. Cette thèse propose un support d’exécution pour des orchestrations réparties, hétérogènes, dynamiquement reconfigurables, et permettant une administration globale. Une orchestration de services peut être abordée selon ses deux dimensions : temporelle qui reflète l’enchainement des services dans le temps, spatiale qui reflète les services que l’orchestration a besoin d’invoquer afin de s’exécuter. Nous proposons ainsi un nouveau modèle à composants pour les applications orientées services, inspiré en partie de SCA et de SCA/BPEL, mais permettant de représenter ces deux dimensions. Notre approche se fonde sur un modèle de composants logiciels répartis et dynamiquement reconfigurables, et hérite donc des qualités de répartition et de reconfiguration dynamique. Nous décrivons une mise en oeuvre au-dessus de l’implémentation du modèle "Grid Component Model" sur la plateforme de programmation répartie à objets actifs "ProActive". Nous validons notre approche expérimentalement via une application à services d’installation et d’administration d’un parc de passerelles basées sur OSGi.

Abstract :

This thesis focuses on the distributed orchestration of services, resulting (1) from an explicit decomposition of an orchestration into sub-orchestrations, located on physical remote sites to ensure protection of data for example, or (2) from a constructive approach whereby existing and possibly heterogeneous orchestrations are coupled in order to build a global and still distributed orchestration. Service orchestrations reflect business processes, sometimes lasting long, which thus have to be reconfigurable at runtime. This thesis introduces an execution support for distributed, heterogenous, dynamically reconfigurable orchestrations, while enabling a global management. A service orchestration can be considered along its two associated dimensions : temporal reflecting the chain of service invocations during time, spatial which makes it explicit which services are needed to be invoked in order for the orchestration to take place. We thus promote a new model, based upon a software component approach, for service oriented applications, inspired partly from SCA and SCA/BPEL, but allowing to represent and manipulate these two dimensions at once. Our approach grounds upon a model for software components which are distributed and dynamically adaptable, thus inheriting from these qualities of distribution and dynamic reconfiguration. We describe an implementation of our model using the "Grid Component Model" reference implementation on top of the distributed active objects library named "ProActive". We validate experimentally our approach through a service based application for the installation and management of a park of OSGi gateways.

   Jury :

Johann MONTAGNAT CNRS, France Président
Didier DONSEZ Université Joseph Fourier, Grenoble, France Rapporteur
François CHAROY Université Henri Poincaré, Nancy, France Rapporteur
Nicolas SALATGÉ Petals Links, Toulouse, France Examinateur
Françoise BAUDE Université de Nice-Sophia Antipolis, France Directrice
Philippe MERLE LIFL, Lille, France Co-directeur

KAMMOUN Aymen:
  Laboratoire I3S
  Sophia-Antipolis / France

Résumé :

   Les travaux développés dans cette thèse portent sur l'amélioration des performances des codeurs géométriques pour les maillages triangulaires. De nombreux travaux considèrent que la géométrie est la composante la plus importante d'un maillage triangulaire. Les codeurs issus de ces travaux appelés codeurs géométriques, incluent une étape de remaillage et une transformée en ondelettes qui permet une analyse multirésolution efficace. L'objectif de nos travaux est de proposer de nouvelles approches pour le remaillage semi-régulier et des améliorations des transformées en ondelettes existantes. Le but du remaillage semi-régulier est de rendre l'échantillonnage plus régulier et de modéliser l'objet avec une structure multirésolution. Ceci permettra par la suite d'utiliser facilement et efficacement des transformées en ondelettes. Ces transformées en ondelettes offrent une plus grande finesse au niveau de l'analyse du signal et permettent de mieux s'adapter aux propriétés locales des maillages surfaciques. Nous avons alors proposé une nouvelle approche basée Voronoï pour le remaillage semi-régulier des objets statiques. Nous avons aussi proposé une nouvelle approche basée sur des techniques de remaillage statique pour le remaillage des animations 3D. Pour améliorer les transformées en ondelettes existantes, nous avons proposé de modifier les filtres utilisés afin de maximiser la parcimonie des coefficients d'ondelettes tout en respectant certaines propriétés (bi-orthogonalité, moment d'ordre 1 nul). Nous avons aussi proposé une analyse spatio-temporelle pour les animations 3D, ainsi qu'une allocation débit optimale adaptée à cette analyse.

Abstract:

The context of this thesis is the improvement of the performance of geometry coders for triangular meshes. Some works consider that geometry is the most important component of triangular meshes. Geometry coders include remeshing technique and wavelet transform providing efficient multiresolution analysis. The goal of our works is to propose new approaches for semi-regular remeshing and to improve existing wavelet transforms. The goal of the semi-regular remeshing is to make the geometry sampling more regular and to model the object with a multiresolution structure. This will allow an easy and efficient use of wavelet transforms. These transforms provide a finer level of analysis of the signal and allow a better adaptability to the local properties of triangular meshes. In our works, we first proposed an original semi-regular remeshing scheme based on Voronoi for static objects. We also proposed an approach for remeshing 3D animations. Furthermore, to improve the existing wavelet transforms, we proposed to modify the classical filters in order to maximize the sparsity of the coefficients, while respecting some specific properties such as bi-orthogonality or vanishing first order moment. We also proposed a spatio-temporal analysis for 3D animations, and an optimal bit-allocation adapted to the proposed analysis.

   Jury de la thèse :
Rapporteurs : M. Titus Zaharia - Professeur - TELECOM SudParis
Mme. Amel Benazza - Professeur - SUP'COM Tunisie
Directeur : M. Marc Antonini - Directeur de recherche - I3S
Co-encadrant : M. Frédéric Payan - Maître de conférence - I3S
Examinateurs : M. Mohamed Daoudi - Professeur - Telecom Lille1
M. Basile Sauvage - Maître de conférence - Université de Strasbourg

Ferry Nicolas:
  Laboratoire I3S
  Sophia-Antipolis (France)

Résumé :

   En informatique ambiante, les applications sont construites en faisant interagir entre eux des objets informatisés et communicants appelés dispositifs. Parce que ces dispositifs peuvent être mobiles ou subir des pannes, cette infrastructure évolue dynamiquement et de manière imprévisible. Aussi, pour s'insérer de manière transparente dans leur environnement et fournir les fonctionnalités attendues par les utilisateurs, bien souvent plus pérennes que l'environnement sur lequel elles reposent, les applications doivent s'adapter dynamiquement à ces évolutions. Ces phénomènes variables poursuivant leur propre dynamique, le défi proposé aux mécanismes d'adaptation est d'être capable de les prendre en compte, avec une dynamique adaptée à chacun d'entre eux.

Dans cette optique, nous proposons un modèle architectural ainsi qu'un mécanisme d'adaptation. Le modèle architectural repose sur quatre niveaux organisés hiérarchiquement en fonction de leur complexité et de la dynamique qu'ils peuvent offrir. Nous lui associons un mécanisme d'adaptation qui, à partir du principe de séparation des préoccupations, permet d'exprimer la variabilité du système. En raison de l'imprévisibilité de l'environnement, les ensembles d'adaptations qui seront déployées par les niveaux supérieurs de l'architecture ne peuvent pas nécessairement être anticipés à la conception. Aussi, grâce à un ensemble de propriétés logiques et temporelles, ces adaptations peuvent être composées de manière non-anticipée dans des temps de réponse adaptés. Le mécanisme d'adaptation proposé, appelé cascade d'aspects, est expérimenté en se basant sur les Aspects d'Assemblages et la plateforme d'exécution WComp.


Abstract

In ubiquitous computing, applications are built as a collaboration of computerized and communicating objects called devices. Because these devices can be mobile or subject to failures, this infrastructure evolves dynamically and unpredictably. Thus, to fit seamlessly into their environment and to provide the functionalities expected by users, which are often more sustainable than the environment, applications must dynamically adapt to these changes. Each of these variable phenomena pursues its own dynamic. The challenge offered to adaptation mechanisms is to be able to consider them, with suitable dynamics.

For this purpose, we propose an architectural model and an adaptation mechanism. The architectural model is based on four levels organized hierarchically according to their complexity and to the dynamics they can offer. We combine to this architectural model an adaptation mechanism. Based on the separation of concerns principle, our mechanism allows us to consider the variability of the system. Due to the unpredictability of the environment, the sets of adaptations that will be deployed by the upper levels of the architecture may not have been anticipated at design time. Also, thanks to some logical and temporal properties, these adaptations can be composed in non-anticipated way and with appropriate response time. The proposed mechanism, called cascaded aspects, is implemented using Aspects of Assembly and the WComp execution platform.

   Composition du jury

Yves DENNEULIN - Professeur, ENSIMAG (rapporteur)
Philippe ROOSE - Docteur H.D.R., IUT de Bayonne (rapporteur)
Pascal ESTRAILLER - Professeur, Université de La Rochelle (président)
Jean-Michel BRUEL - Professeur, Université de Toulouse (examinateur)
Michel RIVEILL - Professeur, Université de Nice (directeur)
Stéphane LAVIROTTE - Docteur, Université de Nice (co-directeur)
Jean-Yves TIGLI - Docteur, Université de Nice (invité)
Eric PASCUAL - Ingénieur, CSTB (invité)

Meftah Anis:
  Laboratoire I3S
  Sophia-Antipolis / France

Résumé :

   Avec les évolutions technologiques, l'industrie de l'imagerie 3D a des besoins de qualité de rendu de plus en plus grandissants, ce qui implique une augmentation des volumes de données à stocker ou à transmettre. Dans ce contexte, cette thèse porte sur le traitement des objets 3D dit "out-of-core" c'est à dire qui ne peuvent pas être chargés totalement en mémoire à cause de leurs grandes tailles. L'enjeu est de proposer de nouvelles techniques pour la manipulation, visualisation et la compression de ce type de données. Nous proposons des méthodes génériques au fil de l'eau permettant un traitement local au fur et à mesure de la lecture ou de l'acquisition de ces objets 3D.
Dans une première partie, cette thèse se concentre sur le traitement multirésolution des maillages surfaciques 3D et plus précisément sur les trois aspects suivants : la compression, la mesure de qualité et la visualisation. Les techniques proposées sont très puissantes et permettent la manipulation des objets "out-of-core" composés de plusieurs milliards de polygones sur des ordinateurs standards avec un minimum de ressources.
Dans une deuxième partie, nous nous focalisons sur le traitement des objets 3D voxéliques. Nous présentons un schéma de compression au fil de l'eau multirésolution traitant des objets de plusieurs téraoctets de données. Ensuite, nous exploitons les spécicités géométriques des objets 3D, comme par exemple les failles et les horizons dans le domaine sismique, pour améliorer les performances du schéma proposé.

Abstract:
With the latest technological progress, the 3D imaging industry needs to increase more and more the rendering quality, which implies an augmentation in the volume of data stored or transmitted. In this context, this thesis focuses on the processing of 3D out-of-core objects which cannot be entirely loaded into memory because of their huge sizes. The challenge is to introduce new techniques for processing, visualization and compression of such data. We then propose generic scan-based methods, enabling the local processing while reading or scanning the 3D objects.
In the first part, this thesis focuses on the processing of multi-resolution 3D surface meshes and specifically on three main areas : compression, quality measurement and visualization. The proposed techniques are very powerful and allow the manipulation of out-of-core meshes composed of billions of polygons on standard computers with a minimum of resources.
In the second part, we focus on the processing of 3D volume objects. We present a scan-based compression scheme dealing with terabytes of data. Furthermore, we exploit the geometry specificities of 3D objects, such as faults and horizons in seismic field, to improve the performances of the presented scheme.

   Jury de la thèse :
Rapporteurs : Benoît Macq - Université catholique de Louvain
Jean-Marie Moureaux - Université Henri Poincaré
Directeur : Marc Antonini - Université de Nice-Sophia Antipolis
co-directeur : Chokri Ben Amar - Université de Sfax
Examinateurs : Attila Baskurt - Université de Lyon
Mohamed Najim - Université de Bordeaux I
Invité : Jean-Marc Krattli - KAPPA Engineering SA

Collet Philippe:
  Laboratoire I3S
  Sophia-Antipolis / France

Résumé :

   Our work stands in the field of software engineering for large scale software intensive systems. We aim at providing techniques and tools to help software architects master the ever-increasing complexity of these systems. Using mainly model-driven engineering approaches, our contribution is organised around three axes.
The first axis concerns the developement of reliable and flexible hierarchical component-based systems with dynamic reconfiguration capabililities. Through the use of novel forms of software contracts, the proposed systems and frameworks support several specification formalisms and maintain up-to-date contracts at runtime.
A second part of our work consists in providing self-adaptive capabilities to these contracting systems, through negotiation mechanisms over contracts and self-adaptive monitoring sub-systems.
A third axis is related to software product lines in which feature models are widely used to model variability. Our contribution consists in providing a set of sound and efficiently implemented composition operators for feature models, as well as a dedicated language for their large scale management.

   Jury composé de :

- Betty H.C. CHENG
Professor, Michigan State University, USA : rapporteur
- Ivica CRNKOVIC
Professor, Mälardalen University, Sweden : rapporteur
- Patrick HEYMANS
Professeur, Université de Namur FUNDP, Belgique : rapporteur
- Jean-Claude BERMOND
Directeur de Recherche, CNRS I3S Sophia Antipolis : examinateur
- Laurence DUCHIEN
Professeur, Université de Lille 1 : examinateur
- Philippe LAHIRE
Professeur, Université Nice - Sophia Antipolis : examinateur
- Jacques MALENFANT
Professeur, Université Pierre et Marie Curie, Paris : examinateur

Madelaine Eric:
  INRIA
  Sophia-Antipolis / France

Résumé :

   Depuis 2001 j’ai développé au sein de l'équipe Oasis des travaux de recherche sur la sémantique des applications à base d'objets distribués, appliquant dans le contexte d'un vrai langage, et d'applications de taille réelle, mes recherches précédentes dans le domaine des algèbres de processus. Les différents aspects de ce travail touchent naturellement à la sémantique comportementale, et à la définition de procédures de génération de modèles prenant en compte les différentes facettes de la programmation d’applications distribuées, mais aussi, en amont, à l'analyse statique de code et aux techniques d'abstraction de modèles, et en aval aux outils de vérification de propriétés comportementales.

Je montre dans ce mémoire la complexité de ces recherches et la grande variété des techniques requises. Nous avons mis en place une méthode cohérente basée sur un modèle sémantique très flexible, le modèle pNets (parameterized Networks of automata), qui nous offre un bon compromis entre décidabilité, complexité, et utilisabilité. Cette approche nous a permis de définir une sémantique comportementale pour différents aspects des applications à base d’objets ou de composants distribués, mais aussi une notion d’abstraction vers des modèles abstraits finis, permettant d’utiliser des outils de vérification de type « model-checking ».

L'ensemble de ces aspects a donné lieu à la réalisation de prototypes, dans la plateforme VerCors, et à des cas d’étude de grande taille.


Abstract :

Since 2001, in the Oasis team, I have developed research on the semantics of applications based on distributed objects, applying in the context of a real language, and applications of realistic size, my previous researches in the field of process algebras. The various aspects of this work naturally include behavioral semantics and the definition of procedures for model generation, taking into account the different concepts of distributed applications, but also upstream, static code analysis and model abstraction techniques, and finally model checking tools.

In this thesis I show the complexity of this research and the wide variety of techniques involved. We have established a consistent semantic model based on a very flexible model called pNets (parameterized Networks of automata), which offers a good compromise between decidability, complexity, and usability. This approach allowed us to define semantics for behavioral aspects of object-based or component-based distributed applications, but also a notion of finite abstraction of the behavioral models, opening the use of model-checking tools. All these elements led to the realization of prototypes, in the Vercors platform, and case studies of large size.

   

Acher Mathieu:
  Laboratoire I3S
  Sophia Antipolis (France)

Résumé :

   L'ingénierie des lignes de produits logiciels (LdPs) est un paradigme pour la modélisation et le développement de familles de systèmes logiciels plutôt que de systèmes logiciels individuels. Son objectif porte sur les moyens de produire et maintenir efficacement des produits logiciels similaires en exploitant ce qu'ils ont en commun et en gérant ce qui varie entre eux. Par analogie, la pratique dans l'industrie automobile est de construire une ligne de production dans laquelle des variations personnalisées mais tout de même similaires de modèles de voitures sont produits.
Les feature models (FMs) sont une représentation fondamentale pour spécifier et raisonner sur la commonalité et la variabilité des LdPs en termes de features (caractéristiques). Les FMs deviennent de plus en plus complexes, manipulés par plusieurs développeurs ou organisations, utilisés pour décrire des features à divers niveaux d'abstraction et qui sont mises en relation de différentes façons. Maintenir un seul gros FM n'est ni réaliste ni souhaitable. Au contraire une tendance forte est de considérer de multiples FMs. Dans cette thèse, nous développons les fondations théoriques et un support pratique pour gérer de multiples FMs.
Nous concevons et développons un ensemble d'opérateurs de composition et de décomposition (aggregate, merge, slice) pour supporter la séparation des préoccupations. Les opérateurs sont formellement définis et implémentés avec un algorithme qui garantie des propriétés sémantiques.
Nous montrons comment les opérateurs de composition et de décomposition peuvent être combinés ensemble ou avec d'autres opérateurs d'édition ou de raisonnement pour réaliser des tâches complexes.
Nous proposons un language textuel, FAMILIAR (pour FeAture Model scrIpt Language for manIpulation and Automatic Reasoning), qui fournit une solution opérationnelle à la gestion de multiples FMs à large échelle. Un utilisateur des FMs peut combiner les différents opérateurs et manipuler un ensemble restreint de concepts (FMs, features, configurations, etc.) en utilisant une notation concise et des facilités linguistiques. FAMILIAR cache les détails d'implémentations (e.g., solveurs) et est supporté par un environnement de développement complet.
Nous décrivons plusieurs applications de ces opérateurs et utilisations de FAMILIAR dans différents domaines (imagerie médicale, vidéo protection) et pour différents objectifs (conception de workflows scientifiques, modélisation de la variabilité des exigences à l'exécution, rétro ingénierie), démontrant l'applicabilité à la fois des opérateurs et du langage de support. Sans les nouvelles capacités fournies par les opérateurs et FAMILIAR, certaines opérations d'analyse et de raisonnement n'auraient pas été possibles dans les différents cas d'études.
Pour conclure, nous discutons les différentes perspectives de recherche à moyen terme (opérateurs, langage, éléments de validation) et à long terme (e.g., relations entre les FMs et les autres modèles).

Abstract :

Software Product Line (SPL) engineering is a paradigm shift towards modeling and developing software system families rather than individual systems.
It focuses on the means of efficiently producing and maintaining multiple similar software products, exploiting what they have in common and managing what varies among them. This is analogous to what is practiced in the automotive industry, where the focus is on creating a single production line, out of which many customized but similar variations of a car model are produced.
Feature models (FMs) are a fundamental formalism for specifying and reasoning about commonality and variability of SPLs.
FMs are becoming increasingly complex, handled by several stakeholders or organizations, used to describe features at various levels of abstraction and related in a variety of ways. In different contexts and application domains, maintaining a single large FM is neither feasible nor desirable. Instead, multiple FMs are now used.
In this thesis, we develop theoretical foundations and practical support for managing multiple FMs. We design and develop a set of composition and decomposition operators (aggregate, merge, slice) for supporting separation of concerns. The operators are formally defined, implemented with a fully automated algorithm and guarantee properties in terms of sets of configurations. We show how the composition and decomposition operators can be combined together or with other reasoning and editing operators to realize complex tasks.
We propose a textual language, FAMILIAR (for FeAture Model scrIpt Language for manIpulation and Automatic Reasoning), which provides a practical solution for managing FMs on a large scale. An SPL practitioner can combine the different operators and manipulate a restricted set of concepts (FMs, features, configurations, etc.) using a concise notation and language facilities. FAMILIAR hides implementation details (e.g., solvers) and comes with a development environment.
We report various applications of the operators and usages of FAMILIAR in different domains (medical imaging, video surveillance) and for different purposes (scientific workflow design, variability modeling from requirements to runtime, reverse engineering), showing the applicability of both the operators and the supporting language. Without the new capabilities brought by the operators and FAMILIAR, some analysis and reasoning operations would not be made possible in the different case studies.
To conclude, we discuss different research perspectives in the medium term (regarding the operators, the language and validation elements) and in the long term (e.g., relationships between FMs and other models).

   Jury :
* Krzysztof Czarnecki, Professeur, University of Waterloo (Canada),rapporteur
* Jean-Marc Jézéquel, Professeur, Université de Rennes 1 (France),rapporteur
* Robert De Simone, Directeur de Recherche, INRIA Sophia Antipolis(France), examinateur
* Patrick Heymans, Professeur, University of Namur (Belgium), examinateur
* Robert B. France, Professeur, Colorado State University (USA), examinateur
* Philippe Lahire, Professeur, Université Nice Sophia Antipolis,co-directeur
* Philippe Collet, Maître de Conférences, Université Nice Sophia Antipolis, co-directeur

Angelino Cesasrio Vincenzo:
  Laboratoire I3S
  Sophia Antipolis / France

Résumé :

   Cette thèse aborde la formulation par la théorie de l?information des problèmes de traitement d?image. Cette formulation exprime la solution au travers de la minimisation d?une énergie. Ces énergies appartiennent à la classe non paramétrique au sens où elles ne font aucune hypothèse paramétrique sur la distribution des données. Les ´energies sont exprimées directement en fonction des données considérées comme des variables aléatoires. Toutefois, l?estimation non paramétrique classique repose sur des noyaux de taille fixe moins fiables lorsqu?il s?agit de données de grande dimension. En particulier, des méthodes récentes dans le traitement de l?image dépendent des données de type ?patch? correspondant à des vecteurs de description de modèles locaux des images naturelles, par exemple, les voisinages de pixels. Le cadre des k-plus proches voisins résout ces difficultés en s?adaptant localement à la distribution des données dans ces espaces de grande dimension. Sur la base de ces prémisses, nous développons de nouveaux algorithmes qui s?attaquent principalement à deux problèmes du traitement de l?image : la déconvolution et le débruitage. Le problème de la restauration est d´evelopp´e dans les hypoth`eses d?un bruit blanc gaussien additive puis successivement adaptés à domaines tels que la photographie numérique et le débruitage d?image radar (SAR). Le schéma du débruitage est également modifié pour définir un algorithme d?inpainting.


Résumé en Anglais :

This thesis addresses informational formulation of image processing problems. This formulation expresses the solution through a minimization of an information-based energy. These energies belong to the nonparametric class in that they do not make any parametric assumption on the underlying data distribution. Energies are expressed directly as a function of the data considered as random variables. However, classical nonparametric estimation relies on fixed-size kernels which becomes less reliable when dealing with high dimensional data. Actually, recent trends in image processing rely on patch-based approaches which deal with vectors describing local patterns of natural images, e. g., local pixel neighborhoods. The k-Nearest Neighbors framework solves these difficulties by locally adapting the data distribution in such high dimensional spaces. Based on these premises, we develop new algorithms tackling mainly two problems of image processing: deconvolution and denoising. The problem of denoising is developed in the additive white Gaussian noise (AWGN) hypothesis and successively adapted to no AWGN realm such as digital photography and SAR despeckling. The denoising scheme is also modified to propose an inpainting algorithm.

   Jury de la thèse :

Prof. Philippe Salembier (Rapporteur)
Prof. Luigi Paura (Rapporteur)
Prof. Giovanni Poggi (Examinateur)
Prof. Michel Barlaud (Directeur de thèse)
Dr. Eric Debreuve (Co-Directeur de thèse)

Filali Imen:
  Laboratoire I3S
  Sophia Antipolis (France)

Résumé :

   Le modèle de communication pair-à-pair a beaucoup attiré l’attention dans les dernières années car il est considéré comme un paradigme puissant pour déployer et exécuter des applications distribuées à grande échelle. Dans ce contexte, le problème de découverte de ressources, c’est-à-dire la recherche d’une ressource donnée répondant aux besoins de l’application constitue un aspect critique dans les systèmes pair-à-pair. Cette thèse se concentre sur la recherche de ressources dans les systèmes pair-à-pair non structurés ainsi que structurés. Dans la première partie de cette thèse, nous proposons un algorithme de découverte de ressources dans un environnent non structuré qui ajuste l’horizon de la requête dynamiquement dans le but de retrouver les ressources demandées d’une manière efficace. La deuxième partie porte sur la conception et l’implémentation d’une architecture pair-à-pair hiérarchique ayant pour but le stockage et la recherche de ressources sémantiques à grande échelle. Cette infrastructure combine le modèle pair-à-pair au niveau de l’architecture elle même et le modèle RDF au niveau de la représentation des données.

Abstract

The Peer-to-Peer (P2P) communication model has drawn much attention in the last few years and has been emerged as a powerful paradigm to build large scale distributed applications. Resource discovery constitutes a critical aspect of P2P systems; it involves the matching of the user’s application requirements to available resources. The thesis focuses on the resource discovery in P2P systems encompassing unstructured and structured P2P overlays. In the first part of this work, we have concentrated on resource discovery in unstructured P2P systems. We have proposed and evaluated a novel algorithm for resource location in unstructured P2P networks that dynamically adjust the query horizon in order to efficiently locate the required resources. The second part of the thesis deals with the design and the implementation of a hierarchical P2P semantic space infrastructure aiming at the distributed storage and retrieval of the semantic data at large scale. This infrastructure combines the strengths of both P2P paradigm at the architectural level and the Resource Description Framework (RDF) data model at the knowledge representation level. While the P2P communication model addresses the system complexity by allowing flexible and decentralized resource storage and processing, the semantic web technologies, on the other hand, address the problem of information complexity by providing advanced support for data presentation and querying.

   Jury

Guillaume Urvoy-Keller, I3S (président du Jury)
Abdelkader Hameurlain, IRIT- Université de Paul Sabatier (rapporteur)
Pierre Kuonen, University of Applied Sciences of Western Switzerland, Fribourg (rapporteur)
Françoise Baude, Université de Nice-Sophia Antipolis (directrice de thèse)
Fabrice Huet, Université de Nice-Sophia Antipolis (Co-directeur de thèse)

MAHESHWARI Ketan:
  Laboratoire I3S
  Sophia-Antipolis (France)

Résumé :

   Le portage d'applications manipulant de grandes masses de données sur des infrastructures de calcul distribué à grande échelle est un probl\`{e}me difficile. Combler l'écart entre l'application et sa description sous forme de workflow soul\`{e}ve des défis à différents niveaux. Le défi au niveau de l'utilisateur final est le besoin d'exprimer la logique de l'application et des dépendances de flots de données dans un domaine non-technique. Au niveau de l'infrastructure, il s'agit d'un défi pour le portage de l'application sur infrastructures à grande échelle en optimisant l'exploitation des ressources distribuées.

Les workflows permettent le déploiement d'applications distribuées gr\^{a}ce à la représentation formelle de composants les constituant, de leurs interactions et des flots de données véhiculés. Cependant, la description de workflows et leurs gestionnaires d'exécution nécessitent des améliorations pour relever les défis mentionnés. Faciliter la description du parallélisme sous une forme concise, la combinaison des données et des structures de données de haut niveau de mani\`{e}re cohérente est nécessaire. Cette th\`{e}se vise à satisfaire ces exigences.
Partant du cas d'utilisation de traitement d'images médicales, plusieurs stratégies sont développées afin d'exprimer le parallélisme et l'exécution asynchrone de workflows complexes en fournissant une expression concise et un gestionnaire d'exécution interfacé avec des infrastructures à grande échelle.

Les contributions principales de cette th\`{e}se sont: a) Un langage riche de workflows disposant de deux représentations. L'exécution des applications de traitement d'images médicales décrites avec ce langage sur la grille de calcul européenne (EGI) donne des résultats expérimentaux fructueux. b) Une extension d'un environnement d'exécution existant de flots applicatifs (Taverna) pour permettre l'exécution de l'application sur les infrastructures à grande échelle.


Résumé en Anglais:

Porting data-intensive applications on large scale distributed computing infrastructures is not trivial.

Bridging the gap between application and its workflow expression poses challenges at different levels. The challenge at the end-user level is a need to express the application's logic and data flow requirements from a non-technical domain. At the infrastructure level, it is a challenge to port the application such that a maximum exploitation of the underlying resources can takes place.

Workflows enable distributed application deployment by recognizing the application component's inter-connections and the flow among them.

However, workflow expressions and engines need enhancements to meet the challenges outlined. Facilitation of a concise expression of parallelism, data combinations and higher level data structures in a coherent fashion is required. This work targets to fulfill these requirements. It is driven by the use-cases in the field of medical image processing domain. Various strategies are developed to efficiently express asynchronous and maximum parallel execution of complex flows by providing concise expression and enactments interfaced with large scale distributed computing infrastructures.

The main contributions of this research are: a) A rich workflow language with two-way expression and fruitful results from the experiments carried out on enactment of medical image processing applications workflows on the European Grid Computing Infrastructure; and b) Extension of an existing workflow environment (Taverna) to interface with the Grid Computing Infrastructures.

   Jury de la thèse:

M. Frédéric DESPREZ --rapporteur
Mme. Françoise BAUDE --examinateur
M. Hugues BENOIT-CATTIN --rapporteur
M. Tristan GLATARD --examinateur
M. Johan MONTAGNAT --directeur

RIBAULT Judicael:
  laboratoire I3S
  Sophia-Antipolis (France)

Résumé :

   L'étude d'un système à l'aide de simulations informatiques à événements discrets implique plusieurs activités: spécification du modèle conceptuel, description de l'architecture logicielle du modèle, développement du logiciels, scénarisation de la simulation, instrumentation, planification d'expérimentation, configuration des ressources de calcul, exécution, post-traitement et analyse, validation et de vérification (V&V). De nombreux éléments logiciels sont requis pour remplir toutes ces activités. Toutefois, il est fréquent de créer un nouveau simulateur à partir de rien quand on commence une étude à l'aide de simulation. Dans ce cas il est nécessaire de développer de multiples outils prenant en charge les activités de la simulation.
Cette thèse aborde le défi de la création de nouveaux simulateurs tout en réutilisant des modèles et des outils provenant d'autres simulateurs. En effet, la réutilisation de logiciel augmente la fiabilité, est moins sujette aux erreurs, permet une meilleure utilisation des expertises complémentaires, améliore la conformité aux normes, et accélère le développement. La réutilisation de logiciels peut être appliquée à toutes les activités de la simulation. Plusieurs problèmes doivent être résolus pour tirer pleinement profit de la réutilisation. Dans cette thèse, nous abordons trois questions principales: Tout d'abord, nous étudions les solutions pratiques de réutilisation permettant de combiner un ensemble choisi d'éléments logiciels utiles pour la modélisation et la simulation, en incluant aussi bien les modèles, les moteurs de simulation, les algorithmes et les outils; Deuxièmement, nous nous concentrons sur les questions liées à l'instrumentation; Troisièmement, nous étudions le problème de l'intégration d'élément logiciels provenant d'autres simulateurs dans un nouveau simulateur. Pour atteindre ces objectifs, nous étudions des techniques de pointe en génie logiciel comme le génie logiciel à base de composants (CBSE), la modélisation par couches et la programmation orientée aspect.

Abstract:

Studying a system using discrete-event computer simulations implies several activities: conceptual model specification, software model architecture description, software development, simulation scenario, instrumentation, experimentation planning, computationnal, resources configuration, execution, post-processing and analysis, validation and verification (V&V). Many software are required to complete all these activities. However, it is common to create a simulator from scratch when we start a simulation study. It is therefore necessary to redevelop a whole suite of tools to ensure support for all simulation activities.
This thesis addresses the challenge of developing new simulators while reusing existing models and simulator parts. Indeed, reusing software increases dependability, is less error prone, makes better use of complementary expertises, improves standards compliance, and accelerates development. Reusing software can be applied to all simulation activities. Several problems have to be solved to derive full benefit of reuse. In this thesis, we adress three major issues: Firstly, we investigate practical means of reusing and combining valuable pieces of modeling and simulation software at large, including models, simulation engines and algorithms, and supporting tools for the modeling and simulation methodology; Secondly, we focus on issues related to instrumentation; Thirdly, we focus on problems of integration of existing simulation tools. To achieve these objectives, we investigate advanced software engineering techniques such as component-based software engineering (CBSE), layered patterns and aspect-oriented programming.

   Le Jury :

Mr Michel Riveill, Professeur des universités - Université Nice Sophia Antipolis - Président
Mme Adelinde Uhrmacher, Professor - University of Rostock, Germany - Rapporteur
Mr Gabriel Wainer, Associate Professor - Carleton University, Canada - Rapporteur
Mr Lionel Seinturier, Professeur des universités - Université Lille 1 - Rapporteur
Mr David Hill, Professeur des universités - Université Blaise Pascal - Examinateur
Mr Denis Conan, Maître de conférences - Institut Télécom, Télécom SudParis - Examinateur
Mr Jean-Claude Bermond, Directeur de Recherche CNRS - I3S, UMR6070, UNS CNRS - Directeur de thèse
Mr Olivier Dalle, Maître de conférences - Université Nice Sophia Antipolis - Co-Directeur de thèse

MAUREIRA Juan-Carlos :
  laboratoire I3S
  Sophia-Antipolis (France)

Résumé :

   Cette thèse propose une nouvelle méthode pour fournir une connexion réseau à des véhicules au cours de trajets prédéterminés (trains, métros, autobus urbains, etc...). La communication entre le véhicule et l'infrastructure réseau est basée uniquement sur la technologie WiFi. Les contributions de ce travail sont d'une part la conception d'une méthode pour réaliser le handover horizontal (entre bornes WiFi), et d'autre part la modélisation et l'analyse de topologies pour le réseau d'infrastructure (réseau backbone plus réseau d’accès WiFi) déployé sur la trajectoire du véhicule. Dans une première partie, nous proposons une méthode, appelée Spiderman Handover, pour réaliser le handover horizontal d'un réseau en mouvement (embarqué dans le véhicule) et une procédure de mise à jour des informations de routage (couche 2 OSI) lors du handover. Nous évaluons notre proposition par simulation et validons nos résultats par des mesures expérimentales. Dans une deuxième partie, nous étudions théoriquement les paramètres de plusieurs familles de topologies du type Chordal pour le réseau backbone construit sur un réseau d'accès linéaire. À partir de la comparaison de ces paramètres, nous proposons une topologie backbone issue de la combinaison de deux topologies Chordal. Cette topologie fournit un bon compromis entre coût du déploiement, nombre de sauts nécessaires pour atteindre la passerelle du réseau et résilience raisonnable. Enfin, nous évaluons l'intégration de la topologie proposée pour le réseau d'infrastructure avec le système handover par des simulations. Les résultats présentés suggèrent que l'algorithme de handover proposé fonctionne correctement sur le réseau d'infrastructure proposé. Cela permet la garantie d'une connexion continue aux passagers à bord des trains, métros ou autobus urbains.


Abstract

This thesis proposes a new method for providing network connectivity to vehicles over a predefined trajectory (trains, metros, urban buses, etc...). The communication between the vehicle and the infrastructure network is based only on WiFi technology. The contributions of this work are two-fold: 1) the horizontal handover (between WiFi access points) and 2) the design and analysis of a infrastructure network (backbone network plus WiFi access network) deployed along the trajectory of the vehicle.

In the first contribution, we propose a handover scheme, called Spiderman Handover, which performs the horizontal handover for an in-motion network (on-board the vehicle) considering a procedure to update the routing information of a bridged infrastructure network (OSI layer 2) when performing the handover. We evaluate our proposal by means of simulation and we validate our results by experimental measurements.

In the second contribution, we study theoretically the parameters of several chordal like topologies in order to build a backbone network for a linear access network. By comparing these parameters, we propose a backbone network composed by a combination of two chordal topologies. This backbone network provides a good balance between their deployment cost, number of hops to the gateway of the network and a reasonable resilience.

Finally, We evaluate the integration of this infrastructure network and the handover scheme by means of simulations. Results showed the proposed handover scheme works properly on the proposed infrastructure network, allowing the provision of a continuous network connectivity to passengers on-board trains, metros or urban buses.

   Le jury:

- Marion BERBINEAU, Directrice de Recherche - IFFSTTAR-LEOST (rapporteur)
- Bertrand DUCOURTHIAL, Professeur - Université de Technologie de Compiègne ( (rapporteur)
- Felipe PERRONE, Associate Professor - Bucknell University (rapporteur, absent pour la soutenance)
- Jean-Claude BERMOND, Directeur de Recherche - CNRS, MASCOTTE (directeur de thèse)
- Olivier DALLE, Maître de Conférences - U. Nice Sophia, Mascotte (directeur de thèse)
- Gabriel WAINER, Associate Professor - Carleton University.
- Jorge AMAYA, Associate Researcher - Universidad de Chile (CMM). (directeur de thèse)
- Frédéric GIROIRE, Chargé de Recherche - CNRS, Mascotte

PIRO Paolo:
  laboratoire I3S
  Sophia-Antipolis (France)

Résumé :

   


Abstract :

In this PhD thesis we address automatic indexing and classification of images.
First of all, we describe our original SMP image descriptor, which represents the texture information at different resolution levels sparsely.
Then, we address the problem of how to efficiently perform the k-nearest neighbor search with respect to the broad class of Bregman divergences (symmetrized or not).
The core part of the thesis is devoted to improve instance-based classification methods like the k-NN rule in a boosting framework. We first describe our UNN one-versus-all learning method, which brings the boosting principle into prototype-based classification, by defining prototypes as weak classifiers to be induced via the minimization of a risk functional.
Then, we describe our inherently multiclass MLNN algorithm, that relies on generic density estimation kernels for better classification precision. The main practical advantage of our method is to considerably reduce the size of the prototype set to be used at classification time, by rejecting "noisy" prototypes, thus enabling better precision at a reduced computational cost.
We validated our novel approach on some well-known real-world image datasets, which contain from 8 to 15 challenging categories. Experiments show that the proposed method improves over the state-of-the-art prototype-based classification significantly, while comparing favourably with the best performing methods in terms of computational complexity. We also applied our method to the challenging problem of medical image classification, particularly focusing on the body part recognition in radiographic images.

   Jury :

M. Luigi Cordella, Professeur à l'Université "Federico II" de Naples (Rapporteur)
M. Patrick Pérez, Directeur de recherche INRIA (Rapporteur)
M.me Cordelia Schmid, Directeur de recherche INRIA (Examinateur)
M. Francesco Tortorella, Professeur à l'Université de Cassino (Examinateur)
M. Giulio Iannello, Professeur à l'Université Campus Bio-Medico de Rome (Directeur en co-tutelle)
M. Michel Barlaud, Professeur à l'Université de Nice-Sophia Antipolis (Directeur de thèse)

MEJDOUB Mahmoud :
  laboratoire I3S
  Sophia-Antipolis (France)

Résumé :

   Face au rythme de croissance des volumes des contenus numériques, le développement des méthodes pour l'indexation et la recherche de ces contenus devient une nécessité. Dans cette thèse, nous nous intéressons aux approches de quantification vectorielle produisant des représentations et des structurations automatiques du contenu visuel des images. Pour commencer, nous nous penchons sur le problème de la description visuelle du contenu afin de fournir une représentation efficace des images. Pour cela, nous utilisons une représentation par sacs de mots visuels basée sur un algorithme de quantification vectorielle flou. Cette représentation permet de décrire localement les images et d'obtenir une représentation plus fine des descripteurs de bas niveau. Les zones locales sélectionnées dans l'image sont aussi bien les zones de variation représentées par les points d'intérêts que les zones homogènes. Le grand nombre de descripteurs locaux qu'on peut obtenir, requiert des outils efficaces pour qu'ils soient exploitables convenablement. Pour cela, nous proposons une nouvelle structure d'indexation: "l'arbre de lattices emboîtés", basée sur la quantification vectorielle par réseau régulier de points. Celui-ci est utilisé aussi bien pour l'accélération de la recherche des k plus proches voisins que pour l'amélioration de la qualité de la classification sémantique des images.


Abstract :

With the growth of digital content volumes, the development of methods for indexing and searching this content becomes a necessity. In this thesis, we are focused on lattice vector quantization approach since its ability to provide an effective automatic structuring of image visual feature vectors. The features extraction step is based on local descriptors obtained by the bag of words technique. Local areas selected in the image correspond to both salient points and homogeneous patches. The large number of local descriptors that can be obtained requires effective tools to organize them. In this sense, we propose a new indexing structure: the "embedded lattices tree" based on lattice vector quantization. The proposed approach is used both to accelerate the k nearest neighbours search and to improve the quality of semantic image classification.

   Le jury est composé de :

*Mr Michel BARLAUD, Professeur, Polytech'Nice, Université de Nice-Sophia Antipolis (président)
*Mme Nozha BOUJEMAA, Professeur, INRIA PARIS ROCQUENCOURT (rapporteur)
*Mme Amel BENAZZA-BENYAHIA, Professeur, SUP'COM Tunis (rapporteur)
*Mr Adel Mohamed ALIMI, Professeur, Ecole Nationale des ingénieurs de Sfax (examinateur)
*Mr Marc ANTONINI, Directeur de Recherche, CNRS, UNSA, (directeur de thèse)
*Mr Chokri BEN AMAR, Professeur, Ecole Nationale des ingénieurs de Sfax (directeur de thèse)

BOULFANI-CUISINAUD Yasmine:
  laboratoire I3S
  Sophia-Antipolis (France)

Résumé :

   De nos jours, les maillages 3D dynamiques sont de plus en plus exploités dans de nombreux domaines, comme la médecine, les jeux vidéo, le cinéma, etc. Ces contenus 3D requièrent un espace mémoire important, la compression reste donc une technique indispensable pour traiter ces données 3D. Nous proposons dans cette thèse deux approches de compression géométrique de maillages 3D dynamiques au fil de l’eau par analyse multirésolution. Comme première approche de compression, le codeur TWC (Temporal Wavelet Coding) est proposé, incluant une transformée en ondelettes temporelle mise en oeuvre au moyen d’un schéma lifting, où plusieurs schémas lifting ont été testés. Les sous-bandes de la transformées en ondelettes sont codées avec une technique basée sur une allocation binaire, proposée dans les travaux de l’équipe, permettant d’obtenir les pas de quantification optimaux, selon un critère débit/distorsion.
En deuxième approche de compression, le codeur appelé MCTWC (Motion Compensated Temporal Wavelet Coding) est proposé, s’appuyant sur la transformée en ondelettes incluant une compensation du mouvement, un codage arithmétiques des matrices de mouvement et des partitions des maillages animés, et un codage des sous-bandes par le codeur basé sur l’allocation binaire.
Une technique de segmentation automatique au sens du mouvement est proposée, consistant à regrouper dans des parties (clusters) les sommets qui suivent le même mouvement affine, sous la contrainte de la minimisation de l’erreur de compensation de mouvement. Une estimation/compensation du mouvement est appliqué ensuite sur chaque cluster de la partition afin d’obtenir une séquence compensée en mouvement par parties, sur laquelle est appliqué une transformée en ondelettes basée sur le schéma lifting. Expérimentalement, le codeur MCTWC incluant la compensation de mouvement a prouvé son efficacité par rapport au codeur TWC qui n’inclue pas cette fonctionnalité. Mais aussi par rapport à certaines techniques de l’état de l’art, tout en offrant l’avantage de ne pas dépendre des caractéristiques géométriques de la séquence, une analyse multirésolution à faible complexité de calcul, la scalabilité temporelle et le codage au fil de l’eau.


Résumé en Anglais :

Today, 3D dynamic meshes are increasingly exploited in many fields such as medicine, video games, movies, etc. These 3D contents require huge memory resources, making compression an essential tool.
We propose in this thesis two approaches for geometric compression of 3D dynamic meshes computing on the fly multiresolution analysis.
As a first compression approach, the encoder TWC (Temporal Wavelet Coding) is proposed, including a temporal wavelet transform implemented by several lifting schemes. The subbands of the wavelet transforms are encoded thanks to a bit allocation giving the optimal quantization steps, by optimizing the rate-distortion trade-off.
A second compression approach is proposed, called MCTWC (Motion Compensated Temporal Wavelet Coding). It is based on the motion compensated wavelet transform.
An automatic motion-based segmentation technique is proposed using a region growing approach: the vertices that follow the same affine motion belong to a same cluster. A motion estimation /compensation is then applied to each cluster of the partition to obtain a cluster-based motion compensated sequence. Then, a wavelet-based lifting scheme is applied.
Experimentally, the encoder MCTWC including motion compensation improves significantly the compression performances compared to the encoder TWC which does not include this feature. Also, compared to some state of the art encoders, the proposed coders do not depend on the geometric characteristics of the mesh sequences, permit a low computational complexity multiresolution analysis, and offer features like temporal scalability and streaming.

   Jury de thèse :

Chokri Ben Amar Professeur à l’ENIS, Tunisie (Rapporteur)
Rémy Prost Professeur des Universités à l’INSA de Lyon (Rapporteur)
Marc Antonini Directeur de Recherche CNRS (Directeur de thèse)
Amel Benazza Professeur à SUP’COM, Tunisie (Examinateur)
Florent Dupont Professeur des Universités à l’LIRIS de Lyon (Examinateur)
Marius Preda Maitre de conférence à l'INT de Paris (Examinateur)

BERCACHI Maroun :
  laboratoire I3S
  Sophia-Antipolis (France)

Résumé :

   Les Algorithmes Évolutionnaires (AEs) sont des méthodes de recherche inspirées par la théorie darwinienne de l'évolution, travaillant sur une population de solutions potentielles, par itération de phases de sélections et de variations aléatoires. La sélection d'une représentation, la définition des paramètres ou l'attribution de leurs propres valeurs ont une influence cruciale sur les performances de l'algorithme. Un choix qui ne s'accorde pas à la fonction de fitness peut rendre le problème plus difficile à résoudre. Trouver une configuration appropriée pour un AE est donc depuis longtemps un grand défi. Bien que les AEs soient reconnus comme des méthodes compétitives sur des problèmes de grande taille, ils sont sujets à un certain nombre de critiques tel celui du réglage/contrôle des paramètres. Par réglage, nous entendons l'approche qui consiste à trouver des valeurs satisfaisantes pour les paramètres avant l'exécution de l'algorithme. Dans cette thèse, nous fournissons des arguments qu'un jeu de paramètres constants durant l'exécution semble être inadéquat. Notre contribution au vaste domaine de l'optimisation concerne le réglage automatique des paramètres selon le problème traité. Dans la première partie, nous exposons la problématique du réglage/contrôle des paramètres ainsi que les principales heuristiques existantes. Dans la deuxième, nous proposons deux méthodes pour le contrôle dynamique des paramètres associés à la représentation des solutions. Dans la troisième, nous proposons l'algorithme évolutionnaire à états (SEA), une variante parallèle des AEs; cette nouvelle approche gère simultanément plusieurs AEs afin de contrôler dynamiquement les paramètres au cours du processus d'optimisation. Dans la dernière partie, nous présentons une instanciation du SEA qui intègre différents taux de mutation afin d'adapter le meilleur taux à la recherche. Cette nouvelle instance est testée sur le problème du sac à dos multidimensionnel. Des résultats comparables ont été obtenus, ce qui prouve que le SEA est capable de contrôler dynamiquement le compromis exploration/exploitation.


Résumé en Anglais :

Evolutionary Algorithms (EAs) are search methods inspired by the darwinian theory of evolution, working iteratively on a population of potential solutions that are randomly selected and modified. The selection of a representation, the definition of parameters or the attribution of their proper values have a crucial influence on the algorithm performances. A choice that does not match to the fitness function can make the problem more difficult to resolve. Finding suitable parameter settings is therefore a big challenge. Although EAs are recognized as competitive methods on large problems, they are subjects to certain critics such as parameters adjustment/control. By parameter settings, we mean the approach which consists in finding reasonable parameter values before the algorithm execution. In this thesis, we provide arguments that a set of constant parameters during the run seems to be inadequate. Our contribution to the broad area of optimization concerns the automatic adjustment of parameters according to the test problem. In the first part, we expose the problematic of parameters adjustment/control as well as the principal exisitng heuristics. In the second, we introduce two methods for dynamic control of parameters associated with the representation of solutions. In the third, we propose the States based Evolutionary Algorithm (SEA), a parallel variant of AEs; this new approach manages simultaneously several EAs in order to control dynamically the parameters during optimization process. In the last part, we present an instantiation of the SEA which integrates different mutation rates in order to adapt the best rate to the search. This new instance was tested on the multidimensional knapsack problem. Comparable results were obtained, which proves that the SEA is capable of dynamically controlling the compromise exploration/exploitation.

   Jury de la thèse :

Pierre Bernhard (Président)
Manuel Clergue (Examinateur)
Philippe Collard (Directeur de thèse)
Yves Duthen (Rapporteur)
El-Ghazali Talbi (Rapporteur)
Sébastien Verel (Examinateur)

NEPOMUCENO Napoleão:
  laboratoire I3S
  Sophia-Antipolis (France)

Résumé :

   Avec les progrès des technologies d'accès, le goulot d'étranglement des réseaux cellulaires se déplace progressivement de l'interface radio vers le backhaul. La possibilité de déployer rapidement des liens radio micro-ondes efficaces est essentielle pour apporter des solutions crédibles au problème de l'engorgement des réseaux backhaul. Toutefois, les solutions de backhaul disponibles avec cette technologie ont reçu peu d'attention de la communauté scientifique. En effet, contrairement aux réseaux filaires, la capacité d'un lien radio micro-ondes est sujette à variation, soit due à des facteurs extérieurs (météo), soit par l'action de l'opérateur. Cette différence soulève une variété de nouvelles questions qui doivent être abordées de façon appropriée. Dans cette thèse, nous étudions les problèmes d'optimisation de réseaux liés à la conception et la configuration des liaisons terrestres sans fil à micro-ondes. Nous nous intéressons en particulier à la classe des problèmes de multiflot de coût minimum avec des fonctions de coût en escalier sur les liens du réseau. Ces problèmes sont parmi les problèmes d'optimisation combinatoire les plus importants et les plus difficiles dans l'optimisation des réseaux, et il n'est généralement possible de les résoudre que de façon approchée. Nous introduisons des modèles mathématiques pour certains de ces problèmes et présentons des approches de solution basées essentiellement sur la programmation entière mixte, la programmation sous contraintes probabilistes, des techniques de relaxation, des méthodes de coupe, ainsi que des méta-heuristiques hybrides.


Abstract :

With the advances in access technologies, the capacity bottleneck of cellular networks is gradually moving from the radio interface towards the backhaul. The ability for microwave to be rapidly and cost-effectively deployed is being a crucial point for successfully tackling the backhaul bottleneck problem. However, backhaul solutions available with this technology have received little attention from the scientific community. In fact, unlike wired networks, the capacity of a microwave radio link is prone to variations, either due to external factors (e.g., weather) or by the action of the network operator. This fundamental difference raises a variety of new issues to be addressed appropriately. In this thesis, we investigate network optimization problems related to the design and configuration of wireless microwave backhaul. We are concerned with a general class of problems expressed in terms of minimum cost multicommodity flows with discontinuous step increasing cost functions on the links of the network. These problems are among the most important and challenging problems in network optimization. Generally, they are computationally very difficult and, in practice, can only be solved approximately. We introduce mathematical models for some of these problems and present solution approaches essentially based on general mixed integer programming, chance-constrained programming, relaxation techniques, cutting plane methods, as well as hybrid metaheuristics.

   Le jury est composé de :

*Jean-Claude BERMOND, Directeur de Recherche, CNRS, (directeur de thèse)
*Simon BRYDEN, Engineer, SME 3Roam (examinateur)
*Manoel CAMPÊLO, Professeur, Universidade Federal do Ceará (co-directeur de thèse)
*Ricardo CORRÊA, Professeur, Universidade Federal do Ceará (rapporteur)
*David COUDERT, Researcher, INRIA (co-directeur de thèse)
*Arie KOSTER, Professeur, RWTH Aachen University (examinateur)
*Fabrice VALOIS, Professeur, INSA Lyon (rapporteur)

NICOLAS Lionel:
  laboratoire I3S
  Sophia-Antipolis (France)

Résumé :

   L'efficacité de la grande majorité des outils utilisés pour le Traitement Automatisé des Langues Naturelles (TALN) dépend directement ou indirectement de la qualité des ressources linguistiques informatisées sur lesquels ils reposent.

Pour des langues internationalement employées telles que le français ou l'espagnol, bien des ressources de référence sont encore dans un état précaire de développement. Pour d'autres langues ayant une communauté moins importante, ces ressources sont souvent inexistantes. Cette situation est la conséquence directe des ambiguïtés et des irrégularités des langues naturelles. Ces dernières rendent leur formalisation complexe, leur description manuelle fastidieuse et leur acquisition automatisée difficile.

De nos jours, pour les aspects linguistiques ayant des formalismes de description consensuels, la principale limitation à la création de ressources linguistiques est le coût humain prohibitif induit par leur création et amélioration manuelle. Comme le formalise la loi de Zipf, améliorer la qualité et la couverture d'une ressource linguistique devient toujours plus laborieux lorsque l'on compare les efforts investis aux améliorations obtenues. La difficulté est donc moins de savoir comment décrire l'aspect linguistique d'une langue que d'en réaliser une description dont la couverture et la qualité répondent aux besoins d'applications performantes.

Construire de telles ressources requiert donc des années d'efforts constants débouchant trop souvent sur des résultats d'une qualité relative et d'une visibilité limitée. L'acquisition et la correction rapides et efficaces de ressources linguistiques sont donc des problèmes peu résolus et d'une importance capitale pour les développements dans le domaine du TALN.

Dans ce contexte, mes recherches ont pour but premier de faciliter la production de ressources linguistiques symboliques ayant trait à l'analyse syntaxique. Elles s'inscrivent dans un projet, appelé Victoria, dont l'objectif est de développer un ensemble de techniques, d'outils et de stratégies pour l'acquisition et la correction de règles morphologiques, de lexiques morpho-syntaxiques et de grammaires lexicalisées. L'application pratique de ces développements nous a permis de créer et/ou d'améliorer des ressources linguistiques pour le français, l'espagnol et le galicien.

Plus particulièrement, mes efforts se sont concentrés sur :
-> des stratégies pratiques pour minimiser les efforts nécessaires à la création et l'amélioration de ressources linguistiques,
-> l'acquisition automatique des règles morphologiques d'une langue à morphologie concaténative,
-> la correction semi-automatique de lexiques morpho-syntaxiques à large couverture.

Abstract

The efficiency and linguistic relevance of most tools dedicated to Natural Language Processing (NLP) depend directly or indirectly on the quality and coverage of the numeric linguistic resources they rely on. Even for major languages such as Spanish and French, many well known and widely used linguistic resources are still in a precarious state of development. For languages with a smaller speech community, they barely exist.

Such situation is a direct consequence of the ambiguity and irregularities of natural languages which make their formalization complex, their manual description labor-intensive and their automatized acquisition difficult. Nowadays, for linguistic aspects that have consensual frameworks to describe them, one can consider the efforts required to develop linguistic resources as the main limitation. As formalized by Zipf's law, increasing the quality of a linguistic resource becomes more and more difficult with time since the efforts are always more demanding when compared with the resulting improvements. In other words, the difficulty for some linguistic levels lies less in how to describe them than in actually achieving a description that has both the coverage and precision required by complex NLP tasks.

Owing to these issues, building linguistic resources can take years of constant effort which might fail to achieve visible or useful results. Therefore, quick and efficient acquisition and correction of linguistic resources is an unsolved problem of considerable interest for the NLP community.

In this context, my PhD has focused on enhancing the production capacities of symbolic linguistic resources for parsing. It is part of a project, named Victoria, that aims at developing techniques, tools and guidelines to produce or improve morphological rules, morpho-syntactic wide-coverage lexicons and lexicalized grammars. The practical use of these developments has enabled us to create and/or improve linguistic resources for French, Spanish and Galician.

More speciffically, my efforts has focused on:
-> practical guidelines for saving as much efforts as possible when creating or improving linguistic resources,
-> the automatic acquisition of the morphological rules of languages with a concatenative morphology,
-> the semi-automatic correction of morpho-syntactic wide-coverage lexicons.

   Le jury sera composé de :
* Pr. Jacques Farré - Univ. Nice-Sophia + CNRS (directeur)
* Dr. Carlos Gómez - Univ. A Coruña (rapporteur)
* Pr. Jean Charles Régin - Univ. Nice-Sophia + CNRS (examinateur)
* Dr. Benoît Sagot - Univ. Paris7 + INRIA (examinateur)
* Pr. Alexis Nasr - Univ. Aix-Marseille (rapporteur)
* Pr. Gertjan Van Noord - Univ. Groningen (rapporteur)

NEMO Clémentine :
  laboratoire I3S
  Sophia-Antipolis (France)

Résumé :

   Les Systèmes d'Information d'Entreprise (SIE) visent à mettre à disposition des développeurs, un ensemble d'éléments hétérogènes (politiques, composants sur étagère, patrons de conception, ...) communs à tous les projets de l'entreprise. Le développement des logiciels se fait ainsi par l'alternance d'intégrations des briques logicielles et de modifications manuelles des codes.
Lorsque les briques logicielles correspondent à l’introduction de politiques, telle que le contrôle d'accès, les assemblages de composants résultants respectent les contraintes imposées par la politique. Or, l’intégration d’autres politiques et les modifications de l’utilisateur peuvent violer ces contraintes et introduire des incohérences dans le modèle. Assurer et éventuellement rétablir la cohérence des assemblages construits par introductions de politiques est la problématique abordée par ce travail de thèse.
Dans cette thèse nous appréhendons une politique comme une transformation de modèle à modèle où son application, par des propriétés d'idempotence, modifie uniquement les éléments de modélisation nécessaires. Ainsi l'application garantit que le modèle résultant respecte les contraintes associées à la politique. La ré-application des transformations idempotentes est alors notre seul outil pour réparer les incohérences introduites dans un modèle. Si la ré-application de la transformation ne modifie pas le modèle, le modèle valide les contraintes associées à la politiques.
Nous proposons alors une spécification des transformations afin de définir par construction des transformations idempotentes que nous nommons ITC. Cette formalisation consiste (i) à spécifier la sémantique des actions élémentaires composant l'expression d'une ITC et (ii) à spécifier le processus d'application d'une ITC. Les applications d'ITCs deviennent alors la base pour construire, valider et réparer un modèle. Nous définissons alors un algorithme de rejeu d'un ensemble d'applications d'ITCs afin de construire un modèle validant un ensemble de contraintes liées à un ensemble de politiques.
L'écriture de l'expression des ITCs à partir d'actions élémentaires, l'application des ITCs et l'algorithme de rejeu sont mise en oeuvre dans un moteur d'applications implémenté en Prolog. Nous illustrons cette contribution à travers une étude de cas où nous mettons en avant la nécessité de permettre les introductions séquentielles et ensemblistes des politiques.

   Le jury sera composé de :

* Mireille Blay-Fornarino - Professeur des Universités ( co-directrice)
* Eric Cariou - Maître de Conférence (examinateur)
* Bernard Coulette - Professeur des Universités (rapporteur)
* Marie-Pierre Gervais - Professeur des Universités (rapportrice)
* Philippe Lahire - Professeur des Universités (examinateur)
* Michel Riveill - Professeur des universités (co-directeur)

Truong Huu Tram :
  laboratoire I3S
  Sophia-Antipolis (France)

Résumé :

   Les infrastructures virtuelles de cloud sont de plus en plus exploitées pour relever les défis de calcul intensif en sciences comme dans l’industrie. Elles fournissent des ressources de calcul, de communication et de stockage à la demande pour satisfaire les besoins des applications à grande échelle. Pour s'adapter à la diversité de ces infrastructures, de nouveaux outils et modèles sont nécessaires. L’estimation de la quantité de ressources consommées par chaque application est un problème particulièrement difficile, tant pour les utilisateurs qui visent à minimiser leurs coûts que pour les fournisseurs d'infrastructure qui visent à contrôler l’allocation des ressources. Même si une quantité quasi illimitée de ressources peut être allouée, un compromis doit être trouvé entre (i) le coût de l’infrastructure allouée, (ii) la performance attendue et (iii) la performance optimale atteignable qui dépend du niveau de parallélisme inhérent à l’application. Partant du cas d’utilisation de l’analyse d’images médicales, un domaine scientifique représentatif d’un grand nombre d’applications à grande échelle, cette thèse propose un modèle de coût à grain fin qui s’appuie sur l’expertise extraite de l’application formalisée comme un flot. Quatre stratégies d'allocation des ressources basées sur ce modèle de coût sont introduites. En tenant compte à la fois des ressources de calcul et de communication, ces stratégies permettent aux utilisateurs de déterminer la quantité de ressources de calcul et de bande passante à réserver afin de composer leur environnement d'exécution. De plus, l'optimisation du transfert de données et la faible fiabilité des systèmes à grande échelle, qui sont des problèmes bien connus ayant un impact sur la performance de l’application et donc sur le coût d'utilisation des infrastructures, sont également prises en considération.

Les expériences exposées dans cette thèse ont été effectuées sur la plateforme Aladdin/Grid'5000, en utilisant l’intergiciel HIPerNet. Ce gestionnaire de plateforme virtuelle permet la virtualisation de ressources de calcul et de communication. Une application réelle d’analyse d’images médicales a été utilisée pour toutes les validations expérimentales. Les résultats expérimentaux montrent la validité de l'approche en termes de contrôle du coût de l'infrastructure et de la performance des applications. Nos contributions facilitent à la fois l'exploitation des infrastructures de cloud, offrant une meilleure qualité de services aux utilisateurs, et la planification de la mise à disposition des ressources virtualisées.


Title and abstract:

Title :
Workflow-based applications performance and execution cost optimization on cloud infrastructures

Abstract:
Cloud computing is increasingly exploited to tackle the computing challenges raised both in science and industry. Clouds provide computing, network and storage resources on demand to satisfy the needs of large-scale distributed applications. To adapt to the diversity of cloud infrastructures and usage, new tools and models are needed. Estimating the amount of resources consumed by each application in particular is a difficult problem, both for end users who aim at minimizing their cost and infrastructure providers who aim at controlling their resources allocation. Although a quasi-unlimited amount of resources may be allocated, a trade-off has to be found between (i) the allocated infrastructure cost, (ii) the expected performance and (iii) the optimal performance achievable that depends on the level of parallelization of the application. Focusing on medical image analysis, a scientific domain representative of the large class of data intensive distributed applications, this thesis proposes a fine-grained cost function model relying on the expertise captured from the application. Based on this cost function model, four resources allocation strategies are proposed. Taking into account both computing and network resources, these strategies help users to determine the amount of resources to reserve and compose their execution environment. In addition, the data transfer overhead and the low reliability level, which are well-known problems of large-scale distributed systems impacting application performance and infrastructure usage cost, are also considered.

The experiments reported in this thesis were carried out on the Aladdin/Grid’5000 infrastructure, using the HIPerNet virtualization middleware. This virtual platform manager enables the joint virtualization of computing and network resources. A real medical image analysis application was considered for all experimental validations. The experimental results assess the validity of the approach in terms of infrastructure cost and application performance control. Our contributions both facilitate the exploitation of cloud infrastructures, delivering a higher quality of services to end users, and help the planning of cloud resources delivery.

   Le jury sera composé de :

* Tristan Glatard - Chargé de recherche CNRS (examinateur)
* Emmanuel Jeannot - Chargé de recherche INRIA (rapporteur)
* Johan Montagnat - Directeur de recherche CNRS (Directeur de thèse)
* Michel Riveill - Professeur des Universités (Examinateur)
* Pascale Vicat-Blanc Primet - Directrice de recherche INRIA (Rapportrice)

Mathias Elton:
  laboratoire I3S
  Sophia-Antipolis (France)

Résumé :

   Dans cette thèse, nous présentons un intergiciel modulaire pour le calcul distribué dans les plates-formes multi-domaine Grid/Cloud, qui permet le traitement de ces questions d'une façon extérieure aux applications. L'idée principale derrière cet intergiciel c'est d'offrir une infrastructure modulaire qui peut être composé hiérarchiquement selon la topologie des ressources et dynamiquement en fonction des ressources disponibles. Cet intergiciel fonctionne comme une colle entre les processus des applications en cours d'exécution dans des différents domaines administratifs, à travers les mécanismes tels que la communication point à point et collective en prenant en compte de la topologie des réseaux. Cet intergiciel est basé sur GCM (Grid Component Model) et l'intergiciel ProActive, que nous avons amélioré avec des fonctionnalités, telles que: des sémantiques de communication gathercast (Mx1) et multicast (Mx1) génériques, des interfaces gather-multicast (MxN) avec le support à la création des raccourcis pour la communication MxN directe entre les composants, le déploiement automatisé et le tunneling et redirectionnement des communications. Tout au long de cette thèse, nous motivons notre travail en mettant en perspective deux plateformes multi-domaine hautement communiquantes, qui nous présentons comme des cas d'utilisation de notre intergiciel: (1) une plateforme HPC, qui permet le couplage des applications basées sur la méthode de décomposition de domaine et une approche de programmation SPMD similaire à MPI, dans des environnements hétérogènes (Runtime DiscoGrid) et (2) une fédération des Enterprise Service Buses (ESB) à l'échelle de l'Internet (fDSB SOA4All), qui permet à des ESBs indépendants d'être (hiérarchiquement) fédérées selon les relations de partenariat entre les fournisseurs/consommateurs de services. Les résultats expérimentaux obtenus dans le cadre des deux cas d'utilisation (le Runtime DiscoGrid et le fDSB) montrent que l'approche proposée est prometteuse, non seulement en termes d'approche de programmation, mais aussi en termes de performance.

Abstract :

In this thesis, we introduce a modular middleware for multi-domain Grid and Cloud computing that allows the treatment of issues related to deployment, resources access and communication in heterogeneous networks externally to applications. The main idea behind this middleware is to offer a modular infrastructure that can be composed hierarchically, according to resources topology, and dynamically, according to the availablility resources. This middleware works as a glue between application processes running in different domains, featuring mechanisms like topology-aware point-to-point and collective communication. Our middleware grounds from the GCM (the Grid Component Model) and the ProActive Grid middleware, that we improved with features, such as: generic gathercast (Mx1) and multicast (Mx1) communication semantics, gather-multicast (MxN) component interfaces, MxN shortcuts, automated deployment and communication tunneling and forwarding. All along this thesis, we motivate our work by putting in perspective two highly communicating multi-domain frameworks, which we present as use-cases of our middleware: (1) an HPC runtime, which allows the coupling of domain-decomposition applications in heterogeneous environments through an MPI-like SPMD programming (the DiscoGrid Runtime) and (2) an Internet wide federation of Distributed Enterprise Service Buses (the SOA4All fDSB), which allows independent distributed service buses (DSBs) to be (hierarchically) federated according to partnership relations among service providers. Experimental results obtained in the context of both use-cases show that the proposed approach is promising, not only in terms of programming approach but also in terms of performance.

   Le jury

Stéphane LANTERI, INRIA Sophia-Antipolis Mediterranée (Président du Jury)
Frederic DESPREZ, Ecole Normale Supérieure Lyon (Rapporteur)
Thilo KIELMANN, Vrije Universiteit Amsterdam (Rapporteur)
Jean-Pierre LORRÉ, Petals Link (Examinateur)
Françoise BAUDE, Université de Nice - Sophia Antipolis (Directrice de Thèse)

Amedro Brian:
  laboratoire I3S
  Sophia-Antipolis (France)

Résumé :

   Les processeurs modernes tendent à devenir massivement multi-coeurs, tandis que les clusters s’ouvrent vers l’Internet pour devenir des "Clouds". Ainsi, d’ici à quelques années, nous par- lerons peut-être de Cloud Haute Performance. Cette ouverture rend les plateformes de calcul plus accessibles et induit un intérêt croissant pour les langages de programmation adaptés à ces architectures hybrides où l’on rencontre aussi bien des espaces mémoire partagé que distribués. Cette thèse de doctorat s’inscrit dans ce contexte et présente ainsi la conception, l’implémentation et l’évaluation de différentes solutions ayant pour but commun d’optimiser l’exécution d’applications numériques haute performance sur ces environnements.
Nous proposons un ensembles d’extensions pour le modèle à objets actifs asynchrones com- municants ASP (Asynchronous Sequential Process), avec des constructions améliorant le développement et l’exécution d’applications. En particulier, ce travail explore le domaine des communications asynchrones entre activités, en étudiant les différentes propriétés de con- fluence et de déterminisme qui peuvent être assurées. Ainsi nous proposons plusieurs construc- tions de langage et approches plus générales au niveau de l’intergiciel (middleware), s’appuyant sur le comportement de l’application pour en optimiser les communications.
Une autre contribution de ce manuscrit consiste en une étude avancée des performances de Java ainsi que de l’intergiciel ProActive, l’implémentation du modèle ASP. Tout en se concentrant sur les applications dites "hautes performance", notre analyse montre comment utiliser les plateformes Java et ProActive pour rendre un programme plus efficace, en s’appuyant sur différentes architectures, comme le suggère le sous-titre de cette thèse: "Des processeurs multi- coeurs aux architectures multi-clouds.

Abstract

Modern processors become massively multi-cores, and clusters become clouds. Within a few years, we may even speak about HPC as High Performance Clouds. This openness makes com- puting platforms more accessible and induces a increasing interest in programming languages adapted to these hybrid shared/distributed memory architectures. This PhD Thesis presents the design, implementation and evaluation of several solutions to optimize the execution of HPC numerical applications in such situation.
We propose some extensions to the asynchronous communicating Active Objects model ASP (Asynchronous Sequential Process), with constructs that improve the execution of applica- tions. In particular, this work explores the era of asynchronous communications between activities, by studying the different properties that can be ensured. Thus, we proposes various language constructs or rather general middleware approaches based on the behavior of the program to optimize communications. Another contribution of this thesis consists in an advanced analysis of the performance of a middleware-based ASP model for high performance applications. This work is based on ProActive, a Java implementation of the model, which has been evaluated in a heterogeneous context characterized by the subtitle of this thesis "from multi-cores to multi-clouds.

   Le jury

Stéphane Descombes, Université de Nice - Sophia Antipolis (Président du Jury)
François Bodin, Directeur de l'IRISA (Rapporteur)
Thierry Priol, Directeur scientifique adjoint, INRIA Rennes (Rapporteur)
Jean-Paul Smets, Nexedi (Examinateur)
Denis Caromel, Université de Nice - Sophia Antipolis (Directeur de thèse)

Coadou Anthony:
  I3S
  Sophia-Antipolis (France)

Résumé :

   Cette thèse définit un nouveau modèle de calcul et de communication, dénommé graphe à routage k-périodique (KRG). Ce modèle, de la famille des réseaux de processus flots de données, admet des aiguillages réguliers des données, explicités par des séquences binaires k-périodiques.

Nous étudions les propriétés mathématiques intrinsèques au modèle. Le routage explicite et l'absence de conflit nous permettent d'exprimer algébriquement les dépendances de données, de même que des transformations topologiques préservant le comportement du graphe. Nous montrons ensuite comment ordonnancer le KRG, en associant aux nœuds des horloges k-périodiques.

Nous positionnons ensuite notre modèle au sein d'un flot de conception dédié aux applications de traitement intensif de données. Nous montrons en particulier la capacité des KRG à représenter explicitement le parallélisme d'instruction extrait du modèle polyédrique. Nous pouvons alors appliquer un ensemble d'optimisations de bas niveau, sortant du cadre affine du modèle polyédrique. Nous présentons enfin une méthodologie pour l'implantation des KRG, basée sur la conception insensible aux latences.

   Jury :

Pierre BOULET - Professeur, Université de Lille I (rapporteur)
Albert COHEN - Directeur de recherche, INRIA Saclay (examinateur)
Robert DE SIMONE - Directeur de recherche, INRIA Sophia (directeur)
Nicolas HALBWACHS - Directeur de recherche, Verimag (examinateur)
Marc POUZET - Professeur, École Normale Supérieure (rapporteur)

Monteiro Julian:
  INRIA, I3S(CNRS-Univ. Nice Sophia)
  Sophia-Antipolis (France)

Résumé :

   Les systèmes pair-à-pair à grande échelle ont été proposés comme un moyen fiable d’assurer un stockage de données à faible coût. Cette thèse vise à fournir des outils permettant d’analyser et de prédire la performance de ces systèmes de stockage de données à grande échelle. Nous avons utilisé ces outils pour analyser l’impact de différents choix de conception du système sur différentes mesures de performance. Par exemple, la consommation de bande passante, l’espace de stockage et la probabilité de perdre des données doivent être aussi faibles que possible. Tout d’abord, nous décrivons un modèle simple par chaîne de Markov et nous établissons des formules mathématiques closes. Ces formules nous permettent de comprendre les interactions entre les paramètres du système. Nous confirmons en comparant à des simulations que ces modèles donnent des approximations correctes du comportement moyen du système. En effet, un mécanisme de réparation paresseux est étudié et nous décrivons comment régler les paramètres du système pour obtenir une utilisation efficace de la bande passante. Nous proposons ensuite un nouveau modèle stochastique basé sur une approximation fluide pour saisir les écarts par rapport au comportement moyen. De plus, nous étudions plusieurs autres aspects d’un système de stockage distribué : nous utilisons un modèle de files d’attente pour calculer le temps de réparation pour un système avec bande passante limitée ; nous étudions un système de codage hybride : en mixant les codes d’effacement avec la simple réplication des données ; enfin, nous étudions l’impact des différentes façons de distribuer des fragments de données entre les pairs.


Abstract Large scale peer-to-peer systems are foreseen as a way to provide highly reliable data storage at low cost. This thesis aims at providing tools to analyze and predict the performance of general peer-to-peer storage systems. We use these tools to analyze the impact of different choices of system design on different performance metrics. For instance, the bandwidth consumption, the storage space overhead, and the probability of data loss should be as small as possible. Different techniques are studied and applied. First, we describe a simple Markov chain model that harnesses the dynamics of a storage system under the effects of peer failures and of data repair. Then we provide closed-form formulas that give good approximations of the model. These formulas allow us to understand the interactions between the system parameters. Indeed, a lazy repair mechanism is studied and we describe how to tune the system parameters to obtain an efficient utilization of bandwidth. We confirm by comparing to simulations that this model gives correct approximations of the system average behavior, but it does not capture its variations over time. We then propose a new stochastic model based on a fluid approximation that indeed captures the deviations around the mean behavior. These variations are most of the time neglected by previous works, despite being very important to correctly allocate the system resources. We additionally study several other aspects of a distributed storage system: we propose queuing models to calculate the repair time distribution under limited bandwidth scenarios; we discuss the trade-offs of a Hybrid coding (mixing erasure codes and replication); and finally we study the impact of different ways to distribute data fragments among peers, i.e., placement strategies.

   Le jury :
- Virgílio ALMEIDA, Professeur - U. Federal de Minas Gerais, Brésil (rapporteur)
- Olivier DALLE, Maître de Conférences - U. Nice Sophia, Mascotte (directeur de thèse)
- Frédéric GIROIRE, Chargé de Recherche - CNRS, Mascotte
- Alfredo GOLDMAN, Professeur - U. de São Paulo, Brésil
- Alain JEAN-MARIE, Directeur de Recherche INRIA, Maestro/LIRMM
- Fabien MATHIEU, Ingénieur - Orange Labs (rapporteur)
- Stéphane PÉRENNES, Directeur de Recherche - CNRS, Mascotte (directeur de thèse)
- Pierre SENS, Professeur - U. Pierre et Marie Curie, LIP6 (rapporteur, absent pour la soutenance)

Mosser Sébastien:
  Laboratoire I3S
  Sophia-Antipolis / France

Résumé :

   Les Architectures Orientées Services permettent la définition d’applications complexes par assemblage de service existants, par exemple sous la forme d’«orchestrations» implémentant des processus métiers. La complexité de ces assemblages impose l’utilisation de techniques telle que la Séparation des Préoccupations pour en maitriser la difficulté. Dans cette thèse, nous présentons ADORE, un métamodèle d’activité permettant l’évolution des orchestrations. Il permet d’exprimer dans le même formalisme des “orchestrations” et des “fragments d’orchestrations”. Nous proposons alors différents algorithmes de compositions permettant l’intégration automatique de ces fragments dans des processus existants. Ces algorithmes définissent des propriétés de compositions (e.g., préservation des relations d’ordre), et assurent leur respect dans les processus composés. Ils assurent que les résultats de composition obtenus ne dépendent pas de l’ordre d’application. ADORE permet la définition de règles de détection d’interférences, sous la forme de prédicats. Le logiciel développé propose ainsi un support, en identifiant les interférences apparaissant lors des compositions. Nous illustrons cette contribution au travers de 2 études de cas: (i) JSEDUITE, une application de diffusion d’information utilisée en production et (ii) CCCMS, une application de gestion de crise implémentée dans le cadre d’une réponse à une étude de cas commune. Pour conclure, nous mettons en perspectives de récentes collaborations visant l’intégration d’ADORE au sein d’un processus de développement logiciel complet, allant des l’ingénierie des besoins à la visualisation efficace des processus composés.

Abstract :

The Service Oriented Architecture (SOA) paradigm supports the assembly of atomic services to create applications that implement complex business processes. Since the design of a complete process can be very complex, composition mechanisms inspired by the Separation of Concerns paradigm (e.g., features, aspects) are needed to support the definition of large systems by composing smaller artifacts into a complex one. In this thesis, we propose ADORE, “an Activity meta– moDel supOrting oRchestration Evolution” to address this issue in the SOA context. The ADORE meta-model allows process designers to express in the same formalism business processes and fragment of processes. Such fragments define additional activities that aim to be integrated into others process. They can be composed into several processes and at different location through the use of algorithms which tame the complexity of large process design. Using these algorithms ensure properties in the final processes such as guard and activity order preservation. The underlying logical foundations of ADORE allow to define interference detection rules as logical predicate, such as consistency properties on ADORE models. Consequently, the ADORE framework supports process designers while designing large process, managing the detection of interference among fragments and ensuring that the composed processes are consistent and do not depend on the order of the composition. This work is illustrated in this document according to two case study: (i) JSEDUITE, an information broadcasting system daily used in several academic institutions and (ii) the CCCMS, a common case study to compare Aspect Oriented Modeling approaches. Ac- cording to several collaboration with others research teams in various domain (i.e., requirement engineering, visualization and real–time systems), we expose as perspectives the integration of ADORE into a complete software development tool chain.

   Jury :

- Don Batory, Université du Texas à Austin, (rapporteur)
- Xavier Blanc, Université Bordeaux 1, LABRI, (rapporteur)
- Mireille Blay-Fornarino, Université Nice - Sophia Antipolis, I3S, (co-directrice)
- Pierre-Alain Muller, Université de Haute Alsace, IRISA (examinateur)
- Lionel Seinturier, Université de Lille 1, LIFL (examinateur),
- Michel Riveill, Université Nice - Sophia Antipolis, I3S, (co-directeur).

Bonizzi Pietro:
  Laboratoire I3S
  Sophia-Antipolis / France

Résumé :

   La fibrillation auriculaire (FA) est l'arythmie la plus fréquente dans le domaine clinique. Les mécanismes de génération de la FA sont encore plutôt inconnus. Differents stratégies pour traiter la FA sont sélectionnées par rapport à la durée des épisodes de FA, dont l'efficacité depend du degré d’organisation de l'activité auriculaire (AA), qui dépend à son tour du niveau de chronicité de la FA. Par conséquent, des outils de traitement du signal appropriés s'avèrent nécessaires pour éclaircir les origines electrophysiologique de la FA et son influence sur le systeme cardiaque. En particulier, l'intérêt du traitement du signal repose sur l'extration de plus d'informations possibles des enregistrements non invasifs. Dans ce sense, la connaissance du degré d'organisation de l’AA peut être important pour aider la décision clinique. Dans ces traveaux de thèse, nous exploitons la diversité spatiale offerte par des enregistrements ECG à plusieures dérivations et pour améliorer la qualité de l'extraction du signal de AA des enregistrements ECG, nécessaire pour des analyses détaillées de la FA, et pour quantifier d'une maniére non invasive le degré de l'organisation spatio-temporel des activations auriculaires pendant FA. Les résultats de notre étude confirment l'intérêt d’exploiter l'information spatiale dans l'ECG pour génerér differentes sous-espaces qui décrivent de façon appropriée les composants ventriculaire et auriculaire de l'ECG, qui se révèlent utiles et pour définir des contraintes supplémentaires pour l'extraction de l'AA et pour analyser directement l'organisation de la FA, soutenant la justesse des approches qui exploitent la diversité spatiale dans l'analyse de la FA.

Abstract :

Atrial fibrillation (AF) is the most common cardiac arrhythmia encountered in clinical practice.The mechanisms of initiation and maintenance of AF are still quite unknown. Different strategies for AF treatment are selected with respect to the duration of AF episodes, and their efficacy may also be influenced by the degree of organization in the atrial activity (AA), in turn depending on the chronification of AF. Thus, proper signal processing tools are required in order to shed some light on the lectrophysiological origins of AF and on its impairing influence on the cardiac system. Particularly, the signal processing interest relies in extracting as much information as possible from noninvasive recordings. In this sense, a certain knowledge of the degree of organization in the AA may be potentially relevant in clinical decision making.
In this doctoral thesis, we exploit the spatial diversity offered by multi-lead ECG recordings both to enhance the quality of an AA signal extracted from ECG recordings, necessary for further detailed analysis of AF, and to noninvasively quantify the degree of spatio-temporal organization of the atrial activations during AF. The results of our study confirm the interest of using the spatial information in the ECG in order to generate different subspaces suitably describing the ventricular and atrial components of the ECG, which reveal to be useful both to define additional constraints for the AA signal extraction and to directly analyze the AF organization in surface recordings, supporting the appropriateness of signal processing approaches exploiting spatial diversity in AF analysis.

   Le Jury sera composé de :

M. Christopher James - Professeur à l'Université de Warwick (Royaume-Uni) - Rapporteur
M. Peter MacFarlane - Professeur à l'Université de Glasgow (Royaume-Uni) - Rapporteur
M. Luca Mainardi - Professeur associé à l'Université de Milano (Italie) - Rapporteur
Mme. Laure Blanc-Féraud - Directrice de recherche au CNRS - Examinateur
M. Nadir Saoudi - Professeur, Chef du Service de cardiologie au Centre Hospitalier Princesse Grace (Monaco) - Examinateur
M. Olivier Meste - Professeur à l'Université de Nice-Sophia Antipolis - Directeur de thèse
M. Vicente Zarzoso - Professeur à l'Université de Nice-Sophia Antipolis - Directeur de thèse

Vincent Hourdin:
  I3S - GLC - Rainbow team (EPU)
  

Résumé :

   En informatique ambiante, le contexte joue un rôle capital. Les applications informatiques étendent leurs interactions avec l'environnement: de nouvelles entrées et sorties sont utilisées, telles que des capteurs et d'autres dispositifs mobiles d'interaction avec l'environnement réel et physique. Les intergiciels, créés pour masquer la complexité des couches inférieures en informatique distribuée, se voient alors chargés de nouvelles préoccupations, comme la prise en compte du contexte, l'adaptation des applications ou la sécurité.

Une représentation en couches intergicielles de ces préoccupations ne permet pas d'exprimer toutes leurs interdépendances. En informatique ambiante, la distribution est nécessaire pour obtenir les informations contextuelles, mais il est aussi nécessaire de prendre en compte le contexte dans la distribution, par exemple pour limiter les interactions aux entités d'un contexte défini. De plus, les interactions asynchrones utilisées dans les nouveaux environnements informatiques nécessitent une attention particulière lors de la prise en compte du contexte. De même, la sécurité intervient à la fois dans les couches intergicielles de distribution et de prise en compte du contexte.

Dans cette thèse nous présentons un modèle de prise en compte du contexte dans la sécurité et la distribution. Le contrôle d'accès doit évoluer pour intégrer une autorisation dynamique et réactive, basée sur des informations liées à l'environnement et plus simplement sur l'authentification des entités. Les informations contextuelles évoluent suivant une dynamique indépendante des applications. Il est aussi nécessaire de détecter les changements de contexte pour réévaluer l'autorisation.

Nous expérimentons cette prise en compte du contexte dans le contrôle des interactions avec la plate-forme expérimentale WComp, issue du modèle SLCA/AA (Service Lightweight Component Architecture / Aspects of Assembly). SLCA permet de concevoir des intergiciels et des applications dynamiques dont le découpage fonctionnel n'est pas traduit en couches, mais par un entrelacement de fonctionnalités. Les aspects d'assemblage sont un mécanisme d'adaptation compositionnelle d'assemblages de composants. Nous les utilisons pour exprimer nos préoccupations non-fonctionnelles et pour les composer avec les applications existantes de façon déterministe et réactive. Nous introduisons pour cela des règles de contrôle d'interactions contextualisées. L'intergiciel permet ainsi d'adapter en fonction du contexte nos préoccupations non-fonctionnelles et le comportement de l'application.

---

Abstract

In ubiquitous computing, context is key. Computer applications are extending their interactions with the environment: new inputs and outputs are used, such as sensors and other mobile devices interacting with the physical environment. Middlewares, created in distributed computing to hide the complexity of lower layers, are then loaded with new concerns, such as taking into account the context, adaptation of applications or security.

A middleware layer representation of these concerns cannot express all their interdependencies. In pervasive computing, distribution is required to obtain contextual information, but it is also necessary to take into account the context in distribution, for example to restrict interactions between entities in a defined context. In addition, asynchronous interactions used in those new environments require special attention when taking into account the context. Similarly, security is involved both in the middleware layers of distribution and context-sensitivity.

In this thesis we present a model taking into account the context both in security and distribution. Access control must evolve to incorporate a dynamic and reactive authorization, based on information related to environment or simply on the authentication information of entities. Contextual information evolve with their own dynamic, independent of applications. It is also necessary to detect context changes to reenforce the authorization.

We are experimenting this context-awareness targetting interaction control with the experimental framework WComp, derived from the SLCA/AA (Service Lightweight Component Architecture / Aspects of Assembly) model. SLCA allows to create dynamic middlewares and applications for which functional cutting is not translated into layers but into an interleaving of functionalities. Aspects of assembly are a mechanism for compositional adaptation of assemblies of components. We use them to express our non-functional concerns and to compose them with existing applications in a deterministic and reactive manner. For this purpose, we introduce context-aware interaction control rules. The middleware thus allows to adapt, according to context, our non-functional concerns and the behavior of the application.

   

Naoumenko Paul:
  Laboratoire I3S, INRIA
  Sophia-Antipolis(France)

Résumé :

   Concevoir des aspects non-fonctionnels à l’aide de composants Dans cette thèse nous considérons des modèles de programmation pour des applications à grande échelle, distribuées et déployées dans des contextes en constant changement, comme la grille de calcul. Pour maintenir leur fonctionnalité tout en minimisant les interventions humaines, ces applications doivent être équipées de capacités auto-adaptatives. Notre recherche a pour base le paradigme de l'"Autonomic Computing", qui conçoit les applications auto-adaptables comme des compositions d'éléments autonomes. Ce sont des entités logicielles qui sont constituées de deux parties: une partie métier (ou fonctionnelle), et une partie contrôle, composée d'entités de contrôle (ou "managers") qui supervisent la partie métier et maintiennent sa fonctionnalité en réagissant aux changements de l'environnement. Les managers peuvent implémenter des stratégies de contrôle complexes: en plus de contrôler la partie métier, ils peuvent communiquer avec des managers d'autres éléments autonomes de l'application et collaborer afin d'élaborer les stratégies adéquates. Les stratégies des managers peuvent être mises à jour dynamiquement.
Nous proposons de concevoir des applications autonomes distribuées en utilisant un modèle à composants: GCM (pour Grid Component Model). Les composants GCM sont distribués par nature et le modèle inclut dans sa spécification la séparation des aspects (les composants GCM ont une partie métier et une partie de contrôle), une structure hiérarchique et la reconfiguration dynamique. Notre contribution peut être résumée en deux points. Premièrement, nous étendons la partie de contrôle (également appelée la membrane) des composants GCM, en donnant la possibilité d'y inclure des managers qui correspondent à la vision de l'Autonomic Computing. Grâce à l'introduction de nouveaux éléments architecturaux, les managers ont la capacité de superviser la partie métier des composants GCM. Ils peuvent également entrer en contact avec des managers d'autres composants faisant partie de la même application . Un composant GCM devrait être facile à produire: nous proposons un processus de développement qui permet de concevoir et développer la partie non-fonctionnelle séparément de la partie métier, puis d'intégrer ces deux parties dans une entité logicielle unifiée. On apporte des modifications au langage de description architectural (ADL), utilisé pour décrire un assemblage GCM statique. Deuxièmement, nous avons inclus les extensions introduites précédemment dans l'implémentation de référence du GCM.

---

English version:

In this thesis we are considering programming models for large-scale and distributed applications that are deployed in dynamic ever-changing environments, like the Grid. To maintain their function with minimal involvement of human operators, those applications have to be instrumented with self-adaptive capabilities. We ground our research on the autonomic computing paradigm, which proposes to design applications as compositions of autonomic elements. Those are software entities exposing two parts: a business part, and a management part, with managers in charge of supervising the business part by reacting to environmental changes. Managers have the possibility to implement complex management strategies: additionnaly to the supervision of the business part, they can contact managers from other autonomic elements involved in the application, and collaborate with them in order to elaborate adequate reactions. Strategies of managers can be dynamically updated. We propose to design distributed autonomic applications using a component-oriented model: the GCM (Grid Component Model). GCM components are distributed by essence and the model features as a part of its specification separation of concerns (GCM components have a business part and a management part), hierarchical structure, and dynamic reconfiguration. Our contribution is twofold. First, we extend the management part (called the membrane) of GCM components, giving the possibility to include managers that correspond to the vision of autonomic computing. Thanks to newly introduced architectural elements, the managers are able to supervise the business part of GCM components. They can also contact managers of other components of the application and collaborate with them. A GCM component with self-adaptive capabilities should be easy to produce: we suggest a development process that allows to design and implement the management part separately from the business part, and then integrate both parts inside one unified software entity. We modify the ADL (architecture description language) used to statically describeGCMcomponent assemblies according to the new development process. Second, we include the previously presnted extensions in the reference implementation of the GCM.

   

Galluccio Laurent:
  Laboratoire I3S
  

Résumé :

   Cette thèse présente de nouvelles méthodes de segmentation et classification non supervisées de données appliquées dans un contexte astrophysique. Les informations a priori telles que le nombre de classes ou la distribution sous-jacente des données ne sont pas toujours connues. Beaucoup de méthodes de classification existantes en astrophysique sont basées sur des connaissances a priori ou sur des observations déjà réalisées sur les données. Les classifications obtenues dépendront donc de ces informations et seront limitées par les connaissances des experts. L'intérêt de développer des algorithmes de classification non supervisées est de s'affranchir de ces limitations afin de détecter potentiellement de nouvelles classes.

L'approche principale adoptée dans cette thèse est l'utilisation d'un graphe construit sur les données : l'arbre de recouvrement minimal (ARM). En connectant les points par des segments on construit une structure qui capture les relations existantes entre chaque paire de points. Nous proposons d'estimer le nombre et la position des classes présentes dans les données en explorant les connexions de l'ARM construit. Ces informations servent d'initialisation à des algorithmes de classification. Une nouvelle classe d'ARMs multi-enracinés est présentée. De leur construction, des mesures de distances permettant la prise en compte du voisinage local et global des points sont dérivées. Une méthode de classification non supervisée qui combine les résultats de multiples partitionnements effectués sur les ARMs multi-enracinées est également proposée.
Les méthodes proposées sont validées sur des benchmark et appliquées à des données astrophysiques.

---

Abstract:

This thesis presents new data segmentation and data clustering methods applied to astrophysical data. A priori information such as the number of classes or the underlying data distribution is not necessarily known. Many classification methods in astophysics community are based on a priori knowledges or on observations already realized on data. Classifications obtained will depend on these information and will be limited by the experts knowledge. The goal of developping clustering algorithms is to get rid of these limitations, to be able to potentially detect new classes.

The main approach chosen in this thesis is the use of a graph built on the data: the minimal spanning tree (MST). By connecting the points by segments we build a structure which encapsulates the being relations between each pair of points. We propose a method to estimate both the number and the position of clusters by exploring the connections of the MST built. A data partition is obtained by using this information to initialize some clustering algorithms.
A new class of multi-rooted MSTs is introduced. From their construction, new distance measures are derived allowing to take into account both the local and global data neighborhood. A clustering method which combines results of multiple partitionments realized on the multi-rooted trees is also exposed.
The methods proposed are validated on benchmarks and applied to astrophysical datasets.

   Le jury sera composé de :

M. Andre FERRARI, Professeur des universités - Nice Sophia Antipolis - Examinateur
M. Pierre BORGNAT, Chargé de recherche CNRS - ENS Lyon - Examinateur
M. Stéphane CANU, Professeur des universités - INSA Rouen - Rapporteur
M. Jocelyn CHANUSSOT, Professeur des universités - INP Grenoble - Rapporteur
M. Pierre COMON, Directeur de Recherche CNRS - Nice - Directeur de thèse
M. Olivier MICHEL, Professeur des universités, INP Grenoble - Directeur de thèse

Mikael Sorensen:
  Laboratoire I3S
  Sophia-Antipolis(France)

Résumé :

   Nombre de problèmes issus du traitement de signal peuvent être modélisés par des équations/problèmes tensoriels. La spécificité des problèmes de traitement de signal est qu’ils donnent lieu à des décompositions tensorielles structurées.
L’objectif principal de cette thèse est, d’une part, le développement de méthodes numériques appliquées aux problèmes de décompositions de tenseurs structurés et, d’autre part, leur application en traitement de signal.

Dans un premier temps, nous proposons des méthodes pour le calcul de la décomposition CANDECOMP/PARAFAC (CP) avec un facteur matriciel semi-unitaire. De plus, nous développons des méthodes pour résoudre des problèmes d’analyse en composantes indépendantes (ICA) pouvant être modélisés par une décomposition CP structurée, en les considérant comme des problèmes de décompositions CP sous contrainte de semi-unitarité.

Ensuite, pour le calcul de décompositions CP avec symétries hermitiennes partielles, nous proposons des méthodes de décompositions simultanées de Schur généralisées. D’un point de vue numérique, nous développons le calcul de décompositions CP réelles par une méthode de Jacobi.

En troisième lieu, nous nous attaquons à la décomposition de tenseurs ayant des facteurs matriciels bande ou Hankel/Toeplitz, conjointement (ou non) à des symétries hermitiennes partielles. Ces méthodes sont appliquées à la résolution de problèmes d’identification aveugle basés sur des cumulants.

Enfin, nous proposons une méthode (plus) efficace pour l’égalisation aveugle de canaux paraunitaires basée sur les itérations de Jacobi. Dans le même esprit, nous dérivons une solution algébrique à la méthode de Jacobi pour effectuer la diagonalisation conjointe de matrices réelles définies positives.


Abstract:

Several problems in signal processing can be put in a tensorial framework. In many cases, these problems lead to compute structured tensor decompositions. The main purpose of this thesis is the development of computational methods for structured tensor decomposition problems with application in signal processing.

First, we propose methods for the computation of the CANDECOMP/ PARAFAC (CP) decomposition with a semi-unitary matrix factor. Moreover, we develop methods to solve CP structured independent component analysis problems by addressing them as semi-unitary constrained CP decompositions problems.

Second, we propose simultaneous (generalized) Schur decomposition methods to compute CP decompositions possibly with partial (Hermitian) symmetries. Moreover, a Jacobi-type sweeping procedure for the computation of a real CP decomposition will be considered.

Third, we propose methods to compute tensor decompositions with banded or Hankel/Toeplitz matrix factors and possibly also with partial (Hermitian) symmetries. The methods will be applied to solve some cumulant based blind identification problems.

Fourth, we propose a more efficient Jacobi method for blind equalization of paraunitary channels. Furthermore, we also derive an algebraic solution for the Jacobi method for likelihood based joint diagonalization of real positive definite matrices.

   Le Jury sera composé de:
M. Pierre COMON - Directeur de Recherche, CNRS, Nice - Examinateur
M. Lieven DE LATHAUWER - Associate Professor, K. U. Leuven - Examinateur
M. Gerard FAVIER - Directeur de Recherche, CNRS, Nice - Président
Mme. Sylvie ICART - Maitre de Conférences, Université de Nice - Examinateur
M. Eric MOREAU - Professeur, Université du Sud Toulon-Var - Rapporteur
M. Jean-Christophe PESQUET - Professeur, Université de Marne-la-Vallée - Président
M. Nicholas D. SIDIROPOULOS - Professor, Technical University of Crete - Rapporteur

Hesse Matthias:
  Laboratoire I3S
  sophia-antipolis(France)

Résumé :

   Les codes spatio-temporels orthogonaux par blocs (OSTBC) sont devenus populaires en ce qu'ils permettent de construire des systèmes de communications sans-fil à diversité maximale et à décodage simplifié par maximum de vraisemblance découplé. Cependant, ces codes reposent en général sur une orthogonalité ponctuelle, ce qui entraîne une dégradation bien connue du débit de transmission pour les systèmes à plus de deux antennes d'émission.

Nous introduisons dans cette thèse le concept d'orthogonalité L2 pour les codes spatio-temporel (STC). Cette approche permet de généraliser naturellement la propriété d'orthogonalité ponctuelle pour des systèmes à codages spatio-temporels non-linéaires. Il devient alors possible de construire de nouveaux systèmes multi-antennes (MIMO) à faible complexité de décodage et gain de diversité maximal. De plus, contrairement aux systèmes reposant sur des codes linéaires orthogonaux, ces nouveaux systèmes ne présentent plus de limitation du débit de transmission pour plus de deux antennes. Nous détaillons la construction générale de diverses familles de codes spatio-temporels L2 à débit maximal reposant sur des modulations de phase continue (CPM) et ceci pour n'importe quel nombre d'antennes d'émission. L'orthogonalité L2 des systèmes construits est obtenue par un banc de fonctions de correction de phase qui induit la diversité par décalage en fréquence tout en maintenant la continuité de la phase pour chaque antenne. L'étude de ces codes permet de démontrer que les systèmes MIMO à décodage simplifié ainsi obtenus sont à diversité maximale et débit optimal. Enfin, notons que la construction de ces codes n'introduit aucune contrainte supplémentaire sur les paramètres des modulations de phase continue utilisées.


Abstract:

Orthogonal Space-Time block codes (STBC) have been a popular way to implement wireless communications systems with full diversity and simple decoupled maximum-likelihood decoding. However, all these codes rely on pointwise orthogonality which leads to a well-known degradation of data rate for more than two antennas.

In this thesis, we introduce the concept of L2-orthogonality for non-linear Space-Time codes (STC). Our approach generalizes code design based on pointwise orthogonality. Hence, we are able to derive new codes with the same advantages as pointwise orthogonal STBC, i.e. low decoding complexity and diversity gain. At the same time, we are no longer limited by the restrictions of pointwise orthogonal codes, namely the reduction in data rate. Actually, we show how to construct full rate codes for any arbitrary number of transmit antennas. More precisely, a family of codes for continuous phase modulation (CPM) is detailed. The L2-orthogonality of these codes is ensured by a bank of phase correction functions which maintains the phase continuity but also introduces frequency offsets. We prove that these codes achieve full diversity and have full rate. Moreover, these codes do not put any restriction on the CPM parameters.

   Le Jury sera composé de:

M. Gerard FAVIER - Directeur de Recherche, CNRS, Nice - Président
M. Mérouane DEBBAH - Professeur, SUPELEC, Paris - Rapporteur
M. Luc VANDENDORPE - Professeur, UCL - ELEC, Louvain - Rapporteur
M. Raymond KNOPP - Professeur, EURECOM, Nice - Examinateur

Viet Dung Doan:
  Laboratoire I3S
  Sophia-Antipolis(France)

Résumé :

   Dans cette thèse, nous proposons un environnement de programmation sur grille, nommé PicsouGrid, qui cible tout particulièrement le pricing de contrats dérivés optionnels dans le domaine de la finance. Nous nous focalisons sur le problème de la valorisation d'options de grande dimension (c.a.d. dont le sous-jacent est un grand panier d'actifs). Cet environnement inclut des mécanismes de tolérance aux fautes, de répartition de charge, de partage dynamique de taches, de déploiement, et ainsi, cible des environnements de calcul hétérogènes tels les grilles de calcul.

Nous nous intéressons également à la parallélisation d'un algorithme nommé Classification Monte Carlo (CMC), défini à l'origine par Picazo (2002), pour calculer le prix d'options de type Américain en grande dimension, et qui passe à l'échelle. Nous décrivons les résultats d'expériences obtenus avec cet algorithme parallèle implémenté dans PicsouGrid avec jusqu'à 100 opportunités d'exercice et jusqu'à 40 actifs sous-jacents (pour faire référence à l'indice CAC40). Nous comparons et analysons la précision numérique des prix des ces options calculés avec cet algorithme CMC, et ce en utilisant différents algorithmes de classification, comme AdaBoost, Gradient Boost et les "Support Vector Machines".

Finalement, nous définissons une suite de tests de performance, dans le domaine de la finance, pour l'évaluation et l'analyse d'intergiciels de grilles de calcul. La suite de tests de performance a ete utilisee avec succes durant le "2008 SuperQuant Monte Carlo challenge - the Fifth Grid Plugtest and Contest". Dans le cadre de ce challenge, nous avons également développé une API pour faciliter la mise en oeuvre d'applications ProActive nécessitant des simulations Monte Carlo.

Mots clés : Grille de calcul, evaluation des options Américaines en grande dimension, méthode de Monte Carlo, techniques de classification, suite de benchmark, middleware de grille.


Abstract:

In this thesis, we provide a grid programming framework, named PicsouGrid, which especially targets financial derivative pricing applications. We are interested in the evaluation of high dimensional option contracts (based on a basket of underlying assets) Such a framework includes fault tolerance, load balancing, dynamic task distribution and deployment mechanisms, and as such targets heterogeneous computing environments like computing grids.

We also propose a parallelisation of the Classification Monte Carlo (CMC) algorithm, originally devised by Picazo (2002), for high dimensional American option pricing, which scales in a grid environment. We describe experimental results obtained running this parallel algorithm using PicsouGrid. We are able to run this algorithm for pricing American options requiring important computation times, because of a large number of opportunity dates (e.g. up to 100 such dates), and because of large dimension (e.g. up to 40 underlying assets). We also compare and analyse the option price accuracy obtained with this CMC algorithm when using different classification algorithms such as AdaBoost, Gradient Boost and Support Vector Machines.

Additionally, we define a financial benchmark suite for performance evaluation and analysis of grid computing middlewares. Such benchmark suite is conceptually simple and easy to understand for both the grid computing and financial communities. The benchmark suite was successfully used in the 2008 SuperQuant Monte Carlo challenge - the Fifth Grid Plugtest and Contest. Within the context of this challenge, we developed the ProActive Monte Carlo API (MC API).

Key works : Grid computing, high dimensional American option pricing, Monte Carlo methods, classification techniques, benchmark suite, grid middleware.

   Jury:
Johan Montagnat (Directeur de Recherche I3S CNRS) -- Président
David Hill (Professeur Université de Clermont Ferrand) -- Rapporteur
Bernard Lapeyre (Professeur École des Pont ParisTech) -- Rapporteur
Frédéric Abergel (Professeur École Centrale de Paris) -- Examinateur
Françoise Baude (Maître de Conférences HdR, Université de Nice Sophia-Antipolis) --Directrice de thèse
Mireille Bossy (Chargée de Recherche, INRIA Sophia Antipolis Mediterranée) -- Co-Directrice de thèse

Khan Aamir Mehmood :
  Laboratoire I3S/INRIA
  Sophia-Antipolis ( France )

Résumé :

   Les Systèmes sur puce (SoC) sont de plus en plus complexes. Leur conception repose largement sur la réutilisation des blocs, appelés IP (Intellectual Property). Ces IP sont construites par des concepteurs différents travaillant avec des outils différents. Aussi existe-t-il une demande pressante concernant l'interopérabilité des IP, c'est-à-dire d'assurer la compatibilité des formats et l'unicité d'interprétation de leurs descriptions. IP-Xact constitue un standard de facto défini dans le cadre de la conception de systèmes électroniques pour fournir des représentations portables de composants (électroniques) et d'IP. IP-Xact a réussi à assurer la compatibilité syntaxique, mais il a négligé les aspects comportementaux. UML est un langage de modélisation classique pour le génie logiciel. Il fournit des éléments de modèle propres à couvrir tous les aspects structurels et comportementaux d'une conception. Nous prônons une utilisation conjointe d'UML et d'IP-Xact pour réaliser la nécessaire interopérabilité. Plus précisément, nous réutilisons le profil UML pour MARTE pour étendre UML avec des caractéristiques temps réel et embarquées. Le paquetage Modélisation Générique de Ressources de MARTE est étendu pour prendre en compte des spécificités structurelles d'IP-Xact. Le Modèle de temps de marte étend le modèle atemporel d'UML avec le concept de temps logique bien adapté à la modélisation au niveau système électronique.

La première contribution de cette thèse est la définition d'un modèle de domaine pour IP-Xact. Ce modèle de domaine est utilisé pour construire un profil UML pour IP-Xact qui réutilise autant que possible les stéréotypes de MARTE et en définit de nouveaux uniquement en cas de besoin. Une transformation de modèle a été mise en oeuvre dans ATL permettant d'utiliser des éditeurs graphiques UML comme front-end pour la spécification d'IP et la génération des spécifications IP-Xact correspondantes. Inversement, des fichiers IP-Xact peuvent être importés dans un outil UML par une autre transformation de modèles.

La deuxième contribution porte sur la modélisation de propriétés et de contraintes temporelles portant sur des IP. Les diagrammes comportementaux d'UML sont enrichis avec des horloges logiques et des contraintes d'horloge exprimées dans le langage de spécification de contraintes d'horloge (CCSL) de MARTE. La spécification CCSL peut alors servir de « modèle de référence » pour le comportement temporel attendu et la vérification des implémentations à différents niveaux d'abstraction (RTL ou TLM). Les propriétés temporelles sont vérifiées en utilisant une bibliothèque spécialisée d'observateurs.

Abstract: On-chip systems (also known as System-on-chip or SoC) are more and more complex. SoC design heavily relies on reuse of building blocks, called IPs (Intellectual Property). These IPs are built by different designers working with different tools. So, there is an urgent demand for interoperable IPs, that is, ensuring format compatibility and unique interpretation of the descriptions. IP-Xact is a de facto standard defined in the context of electronic system design to provide portable representations of (electronic) components and IPs. It succeeds in syntactic compatibility but neglects the behavioral aspects. UML is a classical modeling language for software engineering. It provides several model elements to cover all aspects of a design (structural and behavioral). We advocate a conjoint use of UML and IP-Xact to achieve the required interoperability. More specifically, we reuse the UML Profile for MARTE to extend UML elements with real-time embedded specific features. MARTE General Resource Modeling package is extended to add IP-Xact structural features. MARTE Time Model extends the untimed UML with an abstract concept of time adequate to model at the Electronic System Level.

The first contribution of this thesis is the definition of an IP-Xact domain model. This domain model is used to build a UML Profile for IP-Xact that reuses as much as possible MARTE stereotypes and defines new ones only when required. A model transformation has been implemented in ATL to use UML graphical editors as front-ends for the specification of IPs and to generate IP-Xact specifications. Conversely, IP-Xact files can be imported within a UML tool through another model transformation.

The second contribution addresses the modeling of the IPs time properties and constraints. UML behavioral diagrams are enriched with logical clocks and clock constraints using the MARTE Clock Constraint Specification Language (CCSL). The CCSL specification can serve as a "golden model" for the expected time behavior and the verification of candidate implementations at different abstraction levels (RTL or TLM). Time properties are verified through the use of a dedicated library of observers.

   Le Jury sera composé de:

M. Jean-Luc DEKEYSER, Professeur Université des Sciences et Technologies de Lille, en qualité de rapporteur.
M. François TERRIER, Directeur de Recherche - CEA LIST/DTSI/SOL/LLSP, en qualité de rapporteur.
M. Pierre BRICAUD, Directeur R&D - SYNOPSYS, en qualité de invité.
M. Charles ANDRÉ, Professeur Université de Nice Sophia Antipolis, en qualité de directeur de thèse.
M. Frédéric MALLET, Maître de conférences Université de Nice Sophia Antipolis, en qualité de directeur de thèse.

De Cesare Cédric:
  Laboratoire I3S
  Sophia-Antipolis / France

Résumé :

   Durant les dernières années, l’imagerie visuelle est de plus en plus utilisée dans le milieu sous-marin, aussi bien comme une aide à la navigation que comme un outil de cartographie permettant l’étude et la surveillance des fonds sous-marins. Ces opérations de surveillance consistent principalement en l’établissement de cartes des fonds sur de larges zones (plusieurs km2). Les contraintes du milieu (grandes profondeurs, faible absorption de la lumière, etc…) imposent comme systématique l’utilisation de robots autonomes (AUVs), et ce à une altitude proche du fond. La carte est alors réalisée en mettant en correspondance les images enregistrées et en les fusionnant : on parle de mosaïques d’images. Les méthodes actuelles de construction de larges mosaïques ne garantissent pas le recouvrement de celles-ci, permettant ainsi l’existence possible de trous. Pourtant, cet enjeu est primordial afin de permettre une observation complète de la zone de mission. C’est dans ce contexte que s’inscrit notre sujet : «Acquisition de mosaïques d’images complètes à l’aide d’un engin sous-marin autonome».

Nous développons une stratégie adaptative qui assure le recouvrement de la mosaïque. Nous nous basons sur des trajectoires de type lawnmower et déterminons, à la fin de chaque segment observé, la distance avec le prochain segment. Cette distance dépend de l’incertitude de positionnement du robot. Celui-ci dérivant au cours du temps, il doit régulièrement se repositionner pour ne pas se perdre. En ce sens, les caractéristiques morphologiques de la zone observée vont définir des événements possibles de recalage, au cours desquels le robot va faire une mise à zéro de son erreur. Plus la région observée est texturée, plus le nombre d’événements est élevé, et plus le véhicule est mieux à même de se repositionner. La distance inter-segment sera alors grande. Au contraire, plus la région sera lisse, plus la distance de recouvrement sera faible. Dans notre souci d’optimisation de la distance inter-segment, nous risquons d’être confrontés à des situations de mises en correspondance d’images présentant un faible recouvrement. Les méthodes classiques échouent dans de telles situations car elles forcent les associations entre les localités des images (templates). Nous avons établit une méthode, basée sur la Théorie de l’Information, qui pallie ce problème et prend en compte ces ambiguïtés.


Abstract:

During the last years, visual imagery has been more and more used in the underwater environment, as well as an help for navigation than as a tool for cartography allowing the study and survey of seafloors. These operations of survey consist principally in the establishment of maps of the seafloor on large zones (several km2). The constraints of the environment (depth, low absorption of light, etc…) impose as systematic the use of autonomous underwater vehicles (AUV), and this at an altitude close to the ground. The map (image mosaic) is then obtained by matching and fusing the recorded images. The current construction methods of large mosaics do not guarantee the overlap of these ones, leading to the possible existence of holes in the mosaics. However, this stake is high in order to allow the complete observation of the mission zone. It is in this context that we have developed our subject of research : “Acquisition of complete image mosaics with an autonomous underwater vehicle”.

We develop an adaptive strategy that ensures the mosaic overlapping. We base our study on lawnmower trajectories and determine, at the end of each observed segment, the distance with the next segment. This distance depends on the robot relative positioning incertitude. This incertitude increasing with the time, the vehicle must recalculate its position frequently in order to not lose itself. The relief characteristics of the observed zone will define possible registration events, for which the vehicle will reset his positioning error. The more the textured region is, the higher the number of events is, and thus the vehicle can better position itself. The inter-track distance is then high. On the contrary, the less the region is informative, the lower the distance is. In our aim of inter-track distance optimisation, we risk to be confronted to low overlap image matching situations. The classical methods fail in such situations because they force the association between image localities (templates). We have established a method, based on Information Theory, that palliates this problem and take into account these ambiguities.

   Jury:

Joël Le Roux (Professeur des Universités - ESSI), Examinateur
Olivier Meste (Professeur des Universités – I3S), Examinateur
Simon Lacroix (Directeur de recherche – LAAS), Rapporteur
Olivier Strauss (Maître de conférences - LIRMM), Rapporteur
Michel Perrier (Ingénieur – Ifremer), Examinateur
Maria-João Rendas (Chargée de recherche – I3S), Co-directrice de thèse
Fabien Napolitano (Ingénieur – Ixsea), Invité
Stéphane Nicolas (Ingénieur – Prolexia), Invité

Pankajakshan Praveen:
  Laboratoire I3S
  Sophia-Antipolis / France

Résumé :

   Abstract:
Three dimensional (3D) fluorescence microscopy through optical sectioning is a very powerful technique for visualizing biological specimens. The microscope objective is focused at different depths in order to image the biological sample that one wishes to study. Yet, the observation process is never perfect and there are always uncertainties in measurements occurring as blur, aberration and noise. Often, the 3D observed images are never an ideal representation of the true object, and restoration approaches assume that the underlying degradation process is known. However, in fluorescence microscopy, often the degradation varies with imaging conditions and is also sometimes specimen dependent. Blind restoration approaches, tackle this much more realistic but difficult situation of restoration from a single observation of the sample. As the degradation is characterized by the system's point-spread function (PSF), the focus of this thesis is on estimating it along with the fluorescence distribution of the specimen. These problems are ill-posed, under-determined, and so we treat restoration as a Bayesian inferencing problem.
In the first part, we recall briefly how the diffraction-limited nature of an optical microscope's objective, and the intrinsic noise can affect an observed image's resolution. We use statistical approaches for restoration as the physics underlying the production of the images could be considered statistical in nature. The state of the art algorithms related to this subject are reviewed and also the modeling of the imaging process with the optical system is examined. As the imaging involves a photon counting process, the model chosen for the observation is based on the theoretically correct Poisson distribution. An alternative minimization (AM) approach, in the Bayesian framework, restores the lost frequencies beyond the diffraction limit by using a regularization on the object and a constraint on the PSF. Furthermore, new methods are proposed to learn the free-parameters, like the regularization parameter, which conventionally is chosen manually.
When imaging into deeper sections of the specimen, the approximation of an aberration-free imaging, as assumed previously, is not realistic anymore. This is because the refractive index mismatch between the specimen and the immersion medium of the objective lens becomes significant with depth under the cover slip. An additional difference in the path is introduced in the emerging wavefront of the light due to this difference in the index, and the phase aberrations of the wavefront becomes significant. The spherical aberrated (SA) PSF in this case becomes dependent on the axially varying depth. In the second part, we show that an object's location and its original intensity distribution can be recovered by retrieving this phase from the observed intensities. However, due to the incoherent nature of the acquisition system, phase retrieval from the observed intensities will be possible only if the phase restoration is constrained. We use geometrical optics to model the refracted wavefront phase, and modify the AM algorithm to retrieve the PSF from some simulated images. Finally, we propose an extension of this method to restore specimens affected by SA. In this case, as the PSF is depth varying, the linear space invariant model is not suitable. The observation process is defined by a quasi-stationary model, and the PSF approximated so that, excluding the object, there is only one free parameter to be estimated.

Keywords: confocal laser scanning microscopy, point-spread function, blind deconvolution, spherical aberration, Bayes' theorem, maximum likelihood, expectation maximization, maximum a posteriori, alternate minimization

   The jury consists of
Laure Blanc-Féraud, CNRS, France
Philippe Ciuciu, CEA/I2BM, Neurospin center, France
Alain Dieterlen, IUT de Mulhouse, France
Gilbert Engler, INRA Sophia-Antipolis, France
Zvi KAM, Weizmann Institute, Israel
Jean-Christophe Olivo-Marin, Pasteur Institute, France
James B. Pawley, University of Wisconsin Madison, USA
Josiane Zerubia, INRIA Sophia-Antipolis, France

The defense presentation and the discussion will be in English.

Amate Laure:
  Laboratoire I3S
  Sophia-Antipolis / France

Résumé :

   Il est souvent important de trouver une représentation compacte des propriétés morphologiques d'un ensemble d'objets. C'est le cas lors du déplacement de robots autonomes dans des environnements naturels, qui doivent utiliser les objets dispersés dans la région de travail pour naviguer. Cette thèse est une contribution à la définition de formalismes et méthodes pour l'identication de tels modèles. Les formes que nous voulons caractériser sont des courbes fermées correspondant aux contours des objets détectés dans l'environnement, et notre caractérisation de leurs propriétés sera probabiliste.
Nous formalisons la notion de forme en tant que classes d'équivalence par rapport à des groupes d'opérateurs géométriques basiques, introduisant deux approches : discrète et continue. La théorie discrète repose sur l'existence d'un ensemble de points remarquables et est sensible à leur sélection. L'approche continue, qui représente une forme par des objets de dimension infinie, correspond mieux à la notion intuitive de forme mais n'est pas parcimonieuse.
Nous combinons les avantages des deux approches en représentant les formes à l'aide de splines : fonctions continues, flexibles, définies par un ensemble de noeuds et de points de contrôle. Nous étudions d'abord l'ajustement d'un modèle spline à une courbe, comme la recherche d'un compromis entre la parcimonie de la représentation et sa fidélité aux données, approche classique dans le cadre de familles imbriquées de dimension croissante. Nous passons en revue les méthodes utilisées dans la littérature, et nous retenons une approche en deux étapes, qui satisfait nos pré-requis : détermination de la complexité du modèle (par une chaîne de Markov à sauts réversibles), suivie de l'estimation des paramètres (par un algorithme de recuit simulé). Nous discutons finalement le lien entre l'espace de formes discrètes et les représentations splines lorsque l'on prend comme points remarquables les points de contrôle.
Nous étudions ensuite le problème de modélisation d'un ensemble de courbes, comme l'identification de la distribution des paramètres de leur représentation par des splines où les points de contrôles et les noeuds sont des variables latentes du modèle. Nous estimons ces paramètres par un critère de vraisemblance marginale. Afin de pouvoir traiter séquentiellement un grand nombre de données nous adaptons une variante de l'algorithme EM proposée récemment. Le besoin de recourir à des approximations numériques (méthodes de Monte-Carlo) pour certains calculs requis par la méthode EM, nous conduit à une nouvelle variante de cet algorithme, proposée ici pour la première fois.


Abstract:

In many contexts it is important to be able to find compact representations of the collective morphological properties of a set of objects. This is the case of autonomous robotic platforms operating in natural environments that must use the perceptual properties of the objects present in their workspace to execute their mission. This thesis is a contribution to the definition of formalisms and methods for automatic identication of such models. The shapes we want to characterize are closed curves corresponding to contours of objects detected in the scene.
We begin with the formal definition of the notion of shape as classes of equivalence with respect to groups of basic geometric operators, introducing two distinct approaches that have been used in the literature: discrete and continuous. The discrete theory, admitting the existence of a finite number of recognizable landmarks, provides in an obvious manner a compact representation but is sensible to their selection. The continuous theory of shapes provides a more fundamental approach, but leads to shape spaces of infinite dimension, lacking the parsimony of the discrete representation. We thus combine in our work the advantages of both approaches representing shapes of curves with splines: piece-wise continuous polynomials defined by sets of knots and control points.
We first study the problem of fitting free-knots splines of varying complexity to a single observed curve. The trade-of between the parsimony of the representation and its fidelity to the observations is a well known characteristic of model identication using nested families of increasing dimension. After presenting an overview of methods previously proposed in the literature, we single out a two-step approach which is formally sound and matches our specic requirements. It splits the identification, simulating a reversible jump Markov chain to select the complexity of the model followed by a simulated annealing algorithm to estimate its parameters. We investigate the link between Kendall's shape space and spline representations when we take the spline control points as landmarks.
We consider now the more complex problem of modeling a set of objects with similar morphological characteristics. We equate the problem to finding the statistical distribution of the parameters of the spline representation, modeling the knots and control points as unobserved variables. The identified distribution is the maximizer of a marginal likelihood criterion, and we propose a new Expectation-Maximization algorithm to optimize it. Because we may want to treat a large number of curves observed sequentially, we adapt an iterative (on-line) version of the EM algorithm recently proposed in the literature. For the choice of statistical distributions that we consider, both the expectation and the maximization steps must resort to numerical approximations, leading to a stochastic/on-line variant of the EM algorithm that, as far as we know, is implemented here for the first time.

   Jury:
Mr. Mario Figueiredo (Prof. IST Lisbonne), rapporteur
Mr. René Garello (Prof.Telecom Bretagne), rapporteur
Mr. Ian Jermyn (CR INRIA Sophia), membre du jury
Mr. Jacques Blanc-Talon (DGA/MRIS), membre du jury
Mr. Ciprian Girucaneanu (Researcher Univ. Tampere), membre invité
Mr Tarek Hamel (Prof. UNS), directeur de thèse
Mme Maria Joao Rendas (CR Laboratoire I3S), co-encadrante de thèse

COLLAVIZZA Hélène:
  Laboratoire I3S
  Sophia-Antipolis / France

Résumé :

   Ce mémoire d'Habilitation à Diriger des Recherches présente mes contributions à la vérification formelle des processeurs et des programmes, ainsi qu'à la programmation par contraintes. La vérification formelle, tant de matériel que de logiciel, est cruciale pour la sécurité des systèmes critiques, est un enjeu économique important et reste un défi pour la recherche.

Les méthodes de vérification formelle retenues, aussi bien pour la vérification des processeurs que des programmes sont des méthodes entièrement automatiques qui reposent sur l'utilisation de procédures de décision.
Pour la vérification de programmes, la résolution de contraintes sur domaines finis fournit une procédure de décision sur les entiers bornés (codables en machine). L'explosion combinatoire est retardée par la combinaison de solveurs spécifiques (booléen, linéaires, domaines finis), ce qui a permis d'obtenir des résultats expérimentaux qui surpassent dans certains cas les outils de "bounded model checking" basés sur l'utilisation de solveurs SAT.

Dans un second temps, la vérification formelle des programmes est également abordée sous l'angle du développement conjoint d'une vérification complète et d'une exploration par model checking, basés sur la sémantique formelle du langage définie dans l'assistant de preuves HOL4.

Enfin, ce mémoire présente mes contributions sur les contraintes en domaines continus (i.e. où les variables sont des nombres réels). Ces contraintes ont de nombreuses applications pratiques, par exemple en mécanique ou avionique, et leurs mécanismes de résolution peuvent servir de base à la vérification de programmes en présence de nombres flottants.


Summary :

This habilitation thesis presents my contributions to the formal verification of processors and programs, and to constraint programming. Formal verification of hardware and software is crucial for the safety of critical systems, is an important economic issue and remains a challenge for research.

The formal methods we explored for the verification of processors and programs are entirely automatic and based on decision procedures.
For the formal verification of programs, the resolution of constraints on finite domains provides a decision procedure on bounded integers (i.e. machine-codable). The combinatorial explosion is delayed by the combination of specific solvers (Boolean, linear, finite domains). This has made possible to obtain experimental results outperforming in some cases state of the art bounded model checkers based on SAT solvers.

In a second step, the formal verification of programs is also approached under the angle of the joint development of a complete proof and an exploration by model checking. Both complete proof and model checking are based on the formal semantics of the language defined in the proof assistant HOL4.

Lastly, this habilitation thesis presents my contributions on numerical constraints (i.e where variables are real numbers). These constraints have many practical applications, for example in mechanics or avionics. Furthermore, their resolution mechanisms can be a basis for the formal verification of programs with floating point numbers.

   Le jury sera constitué de :

Dominique Borrione, Professeur à l'Université de Grenoble
Mike Gordon, Professeur, Cambridge University
Thierry Jéron (rapporteur), Directeur de Recherches à l'IRISA, Rennes
Michel Rueher, Professeur à l'Université de Nice Sophia-Antipolis
Michaël Rusinowitch (rapporteur), Directeur de Recherches au LORIA Nancy
Lakhdar Saïs, Professeur à l'Université de Lens

Pascal Van Hentenryck, professeur à Brown University, est également rapporteur mais il ne participera pas au jury.

Vicente ZARZOSO:
  Laboratoire I3S
  Sophia-Antipolis/France

Résumé :

   Cet exposé portera sur la séparation de sources dans des mélanges linéaires. En réduisant le nombre d'hypothèses, l'approche dite aveugle s'est avérée adaptable à une grande variété de domaines d'application. Cependant, les performances peuvent être améliorées en exploitant des propriétés spécifiques du problème à traiter, comme on discutera pendant l’exposé. Quelques contributions récentes de ce type seront présentées, y compris une nouvelle technique robuste pour la séparation aveugle de sources dans des scénarios génériques et un nouveau critère pour l'estimation du signal atrial dans des enregistrements de surface de fibrillation auriculaire.

Abstract:

This talk will focus on the separation of source signals in linear mixtures. By making as few assumptions as possible, the blind approach has shown its adaptability to a wide variety of application domains. However, performance can be improved by exploiting specific features of the problem under analysis, as will be discussed throughout the talk. Some recent contributions of this kind will be presented, including a new robust technique for blind source separation in generic scenarios and a novel criterion for atrial signal estimation in atrial fibrillation surface recordings.

   Jury:

- John McWhirter (Cardiff University, Royaume-Uni)
- Sergio Cerutti (Politecnico di Milano, Italie)
- Jean-Marc Vesin (EPFL, Suisse)
- Christian Jutten (GIPSA-Lab, INP Grenoble)
- Éric Moreau (Université Sud Toulon Var)
- Pierre Comon (I3S, CNRS)

Bettinger Régis:
  Laboratoire I3S
  Sophia-Antipolis / France

Résumé :

   
Ce travail concerne la modélisation du processus de synthèse (construction) de supports de catalyseurs obtenus par réaction silice-alumine. Ce phénomène est caractérisé par 5 variables d'entrée et 2 variables de sortie (la surface spécifique et le volume mésoporeux du support de catalyseur). Chaque combinaison des valeurs de sortie ayant une application potentielle, on voudrait savoir en synthétiser le plus grand nombre, c'est-à-dire connaître les variables d'entrée permettant de construire un catalyseur ayant des caractéristiques données (surface, volume) a priori quelconques. Les limites atteignables des deux sorties du système sont inconnues.

Ne disposant pas de suffisamment d'essais pour pouvoir espérer construire un modèle fiable sur l'ensemble du domaine de variation des variables d'entrée, nous choisissons une approche par plans d'expérience séquentiels avec modélisation par krigeage permettant d'éviter une trop grande dispersion des variables d'entrée tout en assurant une exploration du domaine accessible pour les variables de sortie. Les essais sont choisis séquentiellement en se servant de l'information apportée par les essais précédents et traitée par le modèle de krigeage. Cette façon de procéder est a priori plus efficace que celle consistant à utiliser un plan d'expériences fixé au départ et comprenant la totalité des essais disponibles.

Des critères d'ajout séquentiel de points d'expérimentation (définissant les valeurs des variables d'entrée) sont proposés, qui favorisent une forte dispersion des sorties correspondantes et prennent en compte les incertitudes associées aux prédictions par krigeage. Enfin, les critères retenus, l'un à base de distance et l'autre à base d'entropie, sont testés sur des données simulées afin de vérifier la bonne répartition finale des valeurs des réponses.

Des rappels sur la modélisation par processus gaussien, la régression/interpolation par krigeage et ses liens avec les méthodes de type splines et SVM, ainsi que la planification d'expériences sont présentés en essayant de concilier rigueur et clarté.

Mots-clés : planification d'expériences, krigeage, entropie de Tsallis.


Abstract

This work deals with the modeling of the synthesis process for catalyst supports obtained by a chemical reaction involving silica and alumina. The process is characterized by 5 inputs and 2 outputs (specific surface and mesoporous volume of the support). Each pair of output values has a potential application and the ultimate objective is to be able to find input values associated with the synthesis of a catalyst with any given output characteristics (surface, volume). The ranges of the two outputs are unknown.

The number of runs available is too small to build a satisfactory model over the whole input domain. We thus combine design of experiments and kriging modeling in a way that ensures both a limited dispersion of the input factors and a good exploration of the reachable output domain. The runs are designed sequentially, using the information provided by former runs through their associated kriging model. This sequential construction seems more efficient than the design of a non-sequential experiment containing the total amount of available runs.

Several criteria are proposed for sequential design which favor a high dispersion of the corresponding outputs and take the uncertainties associated with the kriging model into account. The two most appealing are tested on simulated data in order to check the dispersion of outputs; one is based on minimax distance and the other on entropy.

Basic properties of Gaussian processes, regression/interpolation by kriging and links with other methods such as splines and SVMs are reminded, together with standard methods for designing experiments, with the objective of combining rigor and clarity.

Keywords : design of experiments, kriging, Tsallis entropy.