Cette thèse se concentre autour du problème de l'évaluation des requêtes. Étant donné une requête q et une base de données D, l'objectif est de calculer l'ensemble q(D) des uplets résultant de l'évaluation de q sur D. Toutefois, l'ensemble q(D) peut être plus grand que la base de données elle-même car elle peut avoir une taille de la forme n^l où n est la taille de la base de données et l est l'arité de la requête. Calculer entièrement q(D) peut donc nécessiter plus que les ressources disponibles. L'objectif principal de cette thèse est une solution particulière à ce problème: une énumération de q(D) avec un délai constant. Intuitivement, cela signifie qu'il existe un algorithme avec deux phases: une phase de pré-traitement qui fonctionne en temps linéaire dans la taille de la base de données, suivie d'une phase d'énumération produisant un à un tous les éléments de q(D) avec un délai constant (indépendant de la taille de la base de données) entre deux éléments consécutifs. En outre, quatre autres problèmes sont considérés: le model-checking (où la requête q est un booléen), le comptage (où on veut calculer la taille |q(D)|), les tests (où on s'intéresse à un test efficace pour savoir si un uplet donné appartient au résultat de la requête) et la j-ième solution (où on veut accéder directement au j-ième élément de q(D)). Les résultats présentés dans cette thèse portent sur les problèmes ci-dessus concernant: - les requêtes du premier ordre sur les classes de structures de degré borné, - les requêtes du second ordre monadique sur les classes de structures de largeur d'arborescente bornée, - les requêtes du premier ordre sur les classes de structures avec expansion bornée. / This thesis is concentrated around the problem of query evaluation. Given a query q and a database D it is to compute the set q(D) of all tuples in the output of q on D. However, the set q(D) may be larger than the database itself as it can have a size of the form n^l where n is the size of the database and l the arity of the query. It can therefore require too many of the available resources to compute it entirely. The main focus of this thesis is a particular solution to this problem: a scenario where in stead of just computing, we are interested in enumerating q(D) with constant delay. Intuitively, this means that there is a two-phase algorithm working as follows: a preprocessing phase that works in time linear in the size of the database, followed by an enumeration phase outputting one by one all the elements of q(D) with a constant delay (which is independent from the size of the database) between any two consecutive outputs. Additionally, four more problems related to enumeration are also considered in the thesis. These are model-checking (where the query q is boolean), counting (where one wants to compute just the size |q(D)| of the output set), testing (where one is interested in an efficient test for whether a given tuple belongs to the output of the query or not) and j-th solution (where, one wants to be able to directly access the j-th element of q(D)). The results presented in the thesis address the above problems with respect to: - first-order queries over the classes of structures with bounded degree, - monadic second-order queries over the classes of structures with bounded treewidth, - first-order queries over the classes of structures with bounded expansion.

L’exemple paradigmatique d’un processus stochastique multifractionnaire est le mouvement brownien multifractionnaire (mbm). Ce processus gaussien de nature fractale admet des trajectoires continues nulle part dérivables et étend de façon naturelle le célèbre mouvement brownien fractionnaire (mbf). Le mbf a été introduit depuis longtemps par Kolmogorov et il a ensuite été « popularisé » par Mandelbrot ; dans plusieurs travaux remarquables, ce dernier auteur a notamment insisté sur la grande importance de ce modèle dans divers domaines applicatifs. Le mbm, quant à lui, a été introduit, depuis plus de quinze ans, par Benassi, Jaffard, Lévy Véhel, Peltier et Roux. Grossièrement parlant, il est obtenu en remplaçant le paramètre constant de Hurst du mbf, par une fonction H(t) qui dépend de façon régulière du temps t. Ainsi, contrairement au mbf, les accroissements du mbm sont non stationnaires et la rugosité locale de ses trajectoires (mesurée habituellement par l’exposant de Hölder ponctuel) peut évoluer significativement au cours du temps ; en fait, à chaque instant t, l’exposant de Hölder ponctuel du mbm vaut H(t). Notons quecette dernière propriété, rend ce processus plus flexible que le mbf ; grâce à elle, le mbm est maintenant devenu un modèle utile en traitement du signal et de l’image ainsi que dans d’autres domaines tels que la finance. Depuis plus d’une décennie, plusieurs auteurs se sont intéressés à des problèmes d’inférence statistique liés au mbm et à d’autres processus/champs multifractionnaires ; leurs motivations comportent à la fois des aspects applicatifs et théoriques. Parmi les plus importants, figure le problème de l’estimation de H(t), l’exposant de Hölder ponctuel en un instant arbitraire t. Dans ce type de problématique, la méthode des variations quadratiques généralisées, initialement introduite par Istas et Lang dans un cadre de processus à accroissements stationnaires, joue souvent un rôle crucial. Cette méthode permet de construire des estimateurs asymptotiquement normaux à partir de moyennes quadratiques d’accroissements généralisés d’un processus observé sur une grille. A notre connaissance, dans la littérature statistique qui concerne le mbm, jusqu’à présent, il a été supposé que, l’observation sur une grille des valeurs exactes de ce processus est disponible ; cependant une telle hypothèse ne semble pas toujours réaliste. L’objectif principal de la thèse est d’étudierdes problèmes d’inférence statistique liés au mbm, lorsque seulement une version corrompue de ce dernier est observable sur une grille régulière.Cette version corrompue est donnée par une classe de modèles à volatilité stochastique dont la définition s’inspire de certains travaux antérieurs de Gloter et Hoffmann ; signalons enfin que la formule d’Itô permet de ramener ce cadre statistique au cadre classique : « signal+bruit ». / The paradigmatic example of a multifractional stochastic process is multifractional Brownian motion (mBm). This fractal Gaussian process with continuous nowhere differentiable trajectories is a natural extension of the well-known fractional Brownian motion (fBm). FBm was introduced a longtime ago by Kolmogorov and later it has been made « popular» by Mandelbrot; in several outstanding works, the latter author has emphasized the fact that this model is of a great importance in various applied areas. Regarding mBm, it was introduced, more than fifteen years ago, by Benassi, Jaffard, Lévy Véhel, Peltier and Roux. Roughly speaking, it is obtained by replacing the constant Hurst parameter of fBm by a smooth function H(t) which depends on the time variable t. Therefore, in contrast with fBm, theincrements of mBm are non stationary and the local roughness of its trajectories (usually measured through the pointwise Hölder exponent) is allowed to significantly evolve over time; in fact, at each time t, the pointwise Hölder exponent of mBm is equal to H(t). It is worth noticing that the latter property makes this process more flexible than fBm; thanks to it, mBm has now become a useful model in the area of signal and image processing, aswell as in other areas such as finance. Since at least one decade, several authors have been interested in statistical inference problems connected with mBm and other multifractional processes/fields; their motivations have both applied and theoretical aspects. Among those problems, an important one is the estimation of H(t), the pointwise Hölder exponent at an arbitrary time t. In the solutions of such issues, the generalized quadratic variation method, which was first introduced by Istas and Lang in a setting of stationary increments processes, usually plays a crucial role. This method allows to construct asymptotically normal estimators starting from quadratic means of generalized increments of a process observed on a grid. So far, to our knowledge, in the statistical literature concerning mBm, it has been assumed that, the observation of the true values of this process on a grid, is available; yet, such an assumption does not always seem to be realistic. The main goal of the thesis is to study statistical inference problems related to mBm, when only a corrupted version of it, can be observed on a regular grid. This corrupted version is given by a class of stochastic volatility models whose definition is inspired by some Gloter and Hoffmann’s earlier works; last, notice that thanks to Itô formula this statistical setting can be viewed as the classical setting: « signal+noise ».

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

La sécurité des systèmes de transports intelligents est au centre de tous les débats. Afin de s’assurer un fonctionnement sécuritaire, il est nécessaire de pouvoir vérifier le bon fonctionnement des capteurs permettant d’avoir une parfaite connaissance de l’environnement et de l’état du véhicule. Cette thèse présente une nouvelle solution de détection et d’identification de faute pouvant apparaitre sur les capteurs embarqués d’un véhicule intelligent. Cette méthode est basée sur la redondance analytique des données, consistant à estimer une même mesure à l’aide de capteurs de différentes natures. Cette mesure subit alors une transformation non linéaire permettant à la fois d’accroitre la sensibilité aux fautes et d’être plus robuste aux bruits. Cette étude propose plusieurs solutions de transformation et d’estimation qui seront évaluées en simulation avant de proposer une méthode d’optimisation de la prise de décision en fonction de critères choisis par l’utilisateur. La description de l’architecture, des méthodes employées ainsi que des équations permettant l’établissement de celle-ci seront décrites dans le chapitre 3. L’évaluation en simulation des performances de l’architecture sera effectuée dans le chapitre 4 avant une analyse finale des résultats ainsi qu’une comparaison avec une solution existante dans le dernier chapitre, permettant la validation de notre approche.

Les données médicales souffrent de problèmes d'uniformisation ou d'incertitude, ce qui les rend difficilement utilisables directement par des logiciels médicaux, en particulier dans le cas du recrutement pour les essais cliniques. Dans cette thèse, nous proposons une approche permettant de palier la mauvaise qualité de ces données à l'aide de méthodes de classification supervisée. Nous nous intéresserons en particulier à 3 caractéristiques de ces données : asymétrie, incertitude et volumétrie. Nous proposons l'algorithme MOCA-I qui aborde ce problème combinatoire de classification partielle sur données asymétriques sous la forme d'un problème de recherche locale multi-objectif. Après avoir confirmé les apports de la modélisation multiobjectif dans ce contexte, nous calibrons MOCA-I et le comparons aux meilleurs algorithmes de classification de la littérature, sur des jeux de données réels et asymétriques de la littérature. Les ensembles de règles obtenus par MOCA-I sont statistiquement plus performants que ceux de la littérature, et 2 à 6 fois plus compacts. Pour les données ne présentant pas d'asymétrie, nous proposons l'algorithme MOCA, statistiquement équivalent à ceux de la littérature. Nous analysons ensuite l'impact de l'asymétrie sur le comportement de MOCA et MOCA-I, de manière théorique et expérimentale. Puis, nous proposons et évaluons différentes méthodes pour traiter les nombreuses solutions Pareto générées par MOCA-I, afin d'assister l'utilisateur dans le choix de la solution finale et réduire le phénomène de sur-apprentissage. Enfin, nous montrons comment le travail réalisé peut s'intégrer dans une solution logicielle. / Medical data suffer from uncertainty and a lack of uniformisation, making them hard to use in medical software, especially for patient screening in clinical trials. In this PhD work, we propose to deal with these problems using supervised classification methods. We will focus on 3 properties of these data : imbalance, uncertainty and volumetry. We propose the MOCA-I algorithm to cope with this partial classification combinatorial problem, that uses a multi-objective local search algorithm. After having confirmed the benefits of multiobjectivization in this context, we calibrate MOCA-I and compare it to the best algorithms of the literature, on both real data sets and imbalanced data sets from literature. MOCA-I generates rule sets that are statistically better than models obtained by the best algorithmes of the literature. Moreover, the models generated by MOCA-I are between 2 to 6 times shorter. Regarding balanced data, we propose the MOCA algorithm, statistically equivalent to best algorithms of literature. Then, we analyze both theoretically and experimentally the behaviors of MOCA and MOCA-I depending on imbalance. In order to help the decision maker to choose a solution and reduce over-fitting, we propose and evaluate different methods to handle all the Pareto solutions generated by MOCA-I. Finally, we show how this work can be integrated into a software application.

L’objectif de cette thèse CIFRE, réalisée avec la société d’études de marché BVA en collaboration avec le constructeur automobile Renault, est de mesurer l’impact des investissements media pour différents canaux (télévision, affichage, etc.) sur les parts de marché de différentes marques, en prenant en compte la concurrence et les potentiels effets croisés et synergies entre ces marques, ainsi qu’en tenant compte du prix des véhicules, du contexte réglementaire (i.e. prime à la casse), et des effets retard de la publicité.Nous avons puisé dans les littératures marketing et statistique pour développer, comparer et interpréter plusieurs modèles qui respectent la contrainte de somme unitaire des parts de marché. Une application concrète au marché automobile français est présentée, pour laquelle nous montrons que les parts de marché des marques sont plus ou moins sensibles aux investissements publicitaires consentis dans chaque canal, et qu’il existe de synergies entre certaines marques. / The aim of this CIFRE thesis, realized with the market research institute BVA in collaboration with the automobile manufacturer Renault, is to build a model in order to measure the impact of media investments of several channels (television, outdoor, etc.) on the brands’ market shares, taking into account the competition and the potential cross effects and synergies between brands, as well as accounting for the price, the regulatory context (scrapping incentive), and the lagged effects of advertising. We have drawn from marketing and statistical literatures to develop, compare and interpret several models which respect the unit sum constraint of market shares. A practical application to the French automobile market is presented, for which it is shown that brands’ market shares are more or less sensitive to advertising investments made in each channel, and that synergies between brands exist.

Dans un paysage industriel de plus en plus tourné vers le numérique, les opportunités des entreprises ne manquent pas pour innover et répondre à une demande jusqu’alors inaccessible. C’est dans ce cadre que l’internet des objets apparait comme un élan technologique a fort potentiel. Ce levier d’innovation, basé sur la valorisation de flux de données, sont par nature intangible et c’est pourquoi nous les considérons ici comme des services. Cependant, les concepteurs doivent faire face ici à un univers complexe où de nombreux domaines d’expertise et de connaissance sont engagés. C’est pourquoi nous proposons dans cette thèse un modèle méthodologique de conception mettant en scène le service, l’expertise métier et les technologies de découverte de connaissance de manière optimisé pour concevoir à l’internet des objets. Ce modèle de conception a été éprouvé chez e.l.m. leblanc, entreprise du groupe Bosch, dans le développement d’un appareil de chauffage connecté et de ses services / In a more and more numeric oriented industrial landscape, the business opportunities for companies to innovate and answer needs inaccessible yep are increasing. In this framework, the internet of things appears as a high potential technology. This innovation lever, where the value-creation is principally based on the data, is not tangible by nature and this is the reason why we conceder it as a service in this thesis. However, the designer has to face a complex universe where a high number expertise and knowledge are engaged. This is the reason why we propose in this thesis a design methodology model organizing the service, the domain knowledge and the data discovery technologies in an optimized process to design the internet of things. This model has been experienced at e.l.m. leblanc, company of the Bosch group, in the development of a connected boiler and its services.

L’évaluation des formations géologiques consiste en l’analyse et la synthèse de données de différentes sources, de différentes échelles (microscopique à kilométrique) et acquises à des dates très variables. Le processus conventionnel de caractérisation des formations relève alors de l’interprétation physique spécialisée de chacune de ces sources de données et leur mise en cohérence par des processus de synthèse essentiellement d’ordre statistique (corrélation, apprentissage, up-scaling…). Il s’avère cependant qu’une source de données présente un caractère central : les diagraphies. Ces mesures physiques de différentes natures (nucléaires, acoustiques, électromagnétiques…) sont réalisées le long de la paroi d’un puits à l’aide de différentes sondes. Elles sont sensibles aux propriétés in situ des roches, et ce, sur une gamme d’échelle centimétrique à métrique intermédiaire aux carottes et données de test de production. De par leur profondeur d’investigation, les données diagraphiques sont particulièrement sensibles au phénomène d’invasion de boue se produisant lors du forage dans l’abord puits. Traditionnellement, l’invasion est modélisée de façon frustre au moment de l’interprétation diagraphiques par un simple effet piston. Ce modèle simple permet d’honorer le bilan de volume mais ne prend aucunement en compte la physique réelle d’invasion et prive, de fait, les diagraphies de toute portée dynamique. Des essais de modélisation de l’historique d’invasion couplés aux données diagraphiques ont déjà été élaborés par différents laboratoires et une abondante littérature sur le sujet est disponible. Les limitations majeures de ces approches résident dans le caractère sous déterminé des problèmes inverses issus de ces modèles physiques et dans le fait que la donnée diagraphique est réalisée en général sur un intervalle de temps inadaptée au regard du développement de l’invasion. Nous proposons une approche différente qui s’attèle non pas à décrire la physique de l’écoulement mais celle de l’équilibre radial des fluides dans le domaine envahi lorsque les diagraphies sont acquises. Nous montrons qu’en introduisant quelques contraintes pétrophysiques supplémentaires, il est possible d’inverser efficacement la distribution des propriétés dynamiques pour chaque faciès géologique. L’inversion prend en compte le phénomène d’invasion radial dans la zone à eau ainsi que l’équilibre capillaire vertical caractérisant le profil de saturation dans le réservoir pour chaque facies. A chaque profondeur du puits, sont ainsi obtenues perméabilités, pressions capillaires et facteurs de cimentation avec leurs incertitudes ainsi que les lois pétrophysiques propres à chaque faciès. Cette méthode a été appliquée à deux puits réels. En guise de validation, les résultats d’inversion ont été comparés aux mesures laboratoire faites sur carotte. De plus, les perméabilités inversées ont été comparées aux transitoires de pression de mini-tests. La cohérence des résultats montre que, d’une part, les hypothèses de base du modèle sont validées et que, d’autre part, l’approche fournit une estimation fiable de grandeurs dynamiques à toute échelle pour chaque faciès réservoir, et ce, dès l’acquisition des données diagraphiques. L’approche d’inversion proposée a permis de lever une limitation majeure des précédentes tentatives de prédiction des propriétés dynamiques par les diagraphies en reconsidérant la problématique non pas sous l’angle d’une modélisation phénoménologique exacte mais en l’abordant de manière globale à l’échelle d’une chaîne d’étude complète. Cette approche permet de fait une mise en cohérence très précoce des données, d’identifier les faciès d’intérêt et de qualifier les besoins véritables en données. Cet outil s’avère très puissant pour qualifier et caractériser les hétérogénéités pétrophysiques des formations et aider ainsi à résoudre le problème de mise à l’échelle des grandeurs dynamiques / The current geological formation evaluation process is built on a workflow using data from differentsources, different scales (microscopic to kilometric) and acquired at different times. Theconventional process of formation evaluation belongs to the dedicated study of each of thesesource of data and their reconciliation through a synthesis step, often based on statisticalconsideration (correlation, learning, up-scaling …). It turns out that there exists a source of datawhich is of considerable importance: logs. These physical measurements of different nature(nuclear, acoustic, electro-magnetic…) are acquired all across the well thanks to multiple probes.They are sensitive to the in situ properties of the rock on an intermediate scale between core dataand well tests (from centimeters to several meters). Because of their depth of investigation, logsare particularly sensitive to the mud filtrate invasion, a phenomenon which occurs during thedrilling in the near well-bore environment. The invasion is conventionally modeled in a rough waywith a piston effect hypothesis. This simple model allows to ensure the volume balance but doesnot take into account the physical processes of the invasion and thus prevent any estimation ofdynamic properties from log interpretation. Several attempts of simulating the complete history ofinvasion have been made by different laboratories in the past, and a rich literature is available onthis topic. The major pitfalls of these approaches come from the under-determination of theinverse problems derived from such models. Furthermore, logs are generally made in a time lapsewhich does not allow to fully characterize the process of invasion. We propose a differentapproach which does not fully describe the physics of the invasion but considers that a radialequilibrium has been reached between the fluids in the invaded zone when logs are acquired. Weshow that it is possible to efficiently invert the distribution of dynamical properties for eachgeological facies by adding some petrophysical constraints. The inversion takes into account thephenomenon of radial invasion in the water zone and the vertical capillary equilibrium describingthe water saturation profile in the reservoir for each facies. At each depth, permeabilities, capillarypressures and cementation factors are thus obtained, along with their uncertainties and thepetrophysical laws specific to each facies. This method has been applied to two wells. Weobtained good results when comparing inverted parameters to the measurements made on coresamples in laboratory. Furthermore, inverted permeabilities have also been compared topermeabilities derived from mini-tests. The consistency of the results shows that, on the one hand,the hypothesis behind our model are valid and, on the other hand, this approach can provide areliable estimation of dynamical parameters at different scales for each reservoir facies as soon asthe logs are acquired. The proposed approach allows to overcome a major limitation of theprevious attempts of the dynamical properties estimation from log interpretation. It allows areconciliation of different data and a facies recognition at an early stage of interpretation, and canindicate the real contribution of each source of data. The technique can even help in identifying theformation heterogeneities and for the petrophysical upscaling.

Dans cette thèse, nous proposons une nouvelle approche pour la conception d'un processeur tolérant aux fautes. Celle-ci répond à plusieurs objectifs dont celui d'obtenir un niveau de protection élevé contre les erreurs transitoires et un compromis raisonnable entre performances temporelles et coût en surface. Le processeur résultant sera utilisé ultérieurement comme élément constitutif d'un système multiprocesseur sur puce (MPSoC) tolérant aux fautes. Les concepts mis en œuvre pour la tolérance aux fautes reposent sur l'emploi de techniques de détection concurrente d'erreurs et de recouvrement par réexécution. Les éléments centraux de la nouvelle architecture sont, un cœur de processeur à pile de données de type MISC (Minimal Instruction Set Computer) capable d'auto-détection d'erreurs, et un mécanisme matériel de journalisation chargé d'empêcher la propagation d'erreurs vers la mémoire centrale (supposée sûre) et de limiter l'impact du mécanisme de recouvrement sur les performances temporelles. L'approche méthodologique mise en œuvre repose sur la modélisation et la simulation selon différents modes et niveaux d'abstraction, le développement d'outils logiciels dédiées, et le prototypage sur des technologies FPGA. Les résultats, obtenus sans recherche d'optimisation poussée, montrent clairement la pertinence de l'approche proposée, en offrant un bon compromis entre protection et performances. En effet, comme le montrent les multiples campagnes d'injection d'erreurs, le niveau de tolérance au fautes est élevé avec 100% des erreurs simples détectées et recouvrées et environ 60% et 78% des erreurs doubles et triples. Le taux recouvrement reste raisonnable pour des erreurs à multiplicité plus élevée, étant encore de 36% pour des erreurs de multiplicité 8 / In this thesis, we propose a new approach to designing a fault tolerant processor. The methodology is addressing several goals including high level of protection against transient faults along with reasonable performance and area overhead trade-offs. The resulting fault-tolerant processor will be used as a building block in a fault tolerant MPSoC (Multi-Processor System-on-Chip) architecture. The concepts being used to achieve fault tolerance are based on concurrent detection and rollback error recovery techniques. The core elements in this architecture are a stack processor core from the MISC (Minimal Instruction Set Computer) class and a hardware journal in charge of preventing error propagation to the main memory (supposedly dependable) and limiting the impact of the rollback mechanism on time performance. The design methodology relies on modeling at different abstraction levels and simulating modes, developing dedicated software tools, and prototyping on FPGA technology. The results, obtained without seeking a thorough optimization, show clearly the relevance of the proposed approach, offering a good compromise in terms of protection and performance. Indeed, fault tolerance, as revealed by several error injection campaigns, prove to be high with 100% of errors being detected and recovered for single bit error patterns, and about 60% and 78% for double and triple bit error patterns, respectively. Furthermore, recovery rate is still acceptable for larger error patterns, with yet a recovery rate of 36%on 8 bit error patterns

Cette thèse aborde les difficultés de mise au point de codes multicibles - c'est-à-dire de codes dont performances sont portables entre différentes cibles matérielles. Nous avons identifié deux principales difficultés à surmonter : l'unification de l'expression du parallélisme d'une part et la nécessité d'adapter le format de stockage des données d'autre part. Afin de mettre au point une version multicible de la bibliothèque d'algèbre linéaire Legolas++ mise au point à EDF R&D, nous avons conçu MTPS (MultiTarget Parallel Skeleton), une bibliothèque dédiée à la mise au point de codes multicible. MTPS permet d'obtenir une implémentation multicible pour les problèmes appliquant une même fonction aux différents éléments d'une collection. MTPS prend alors en charge l'adaptation du format de stockage des données en fonction de l'architecture ciblée. L'intégration des concepts de MTPS dans Legolas++ a conduit à l'obtention d'un prototype multicible de Legolas++. Ce prototype a permis de mettre au point des solveurs dont les performances sont proches de l'optimal sur différentes architectures matérielles / This thesis addresses the challenges of developing multitarget code - that is to say, codes whose performance is portable across different hardware targets. We identified two key challenges : the unification of the the parallelism expression and the need to adapt the format for storing data according to the target architecture. In order to develop a multitarget version of Legolas++, a linear algebra library developed at EDF R&D, we designed MTPS (Multi-Tatget Parallel Skeleton), a library dedicated to the development of multitarget codes. MTPS allows for multitarget implementations of problems that apply the same function to all the elements of a collection. MTPS then handles the adaptation of the format for storing data according to the targeted architecture. Integrating the concepts of MTPS in Legolas++ has led to the production of a multitarget prototype of Legolas++. This prototype has allowed the development of solvers whose performances near the harware limits on different hardware architectures