Les travaux de recherche de ce mémoire portent sur la contribution à l’ordonnancement et à la robustesse d’ateliers de traitement de surface pour une production mono-robot/multi-produits.Une ligne de traitement de surface est constituée d’une succession de cuves dans lesquelles une opération chimique, de durée définie sur un intervalle de temps, appelé fenêtre, doit être réalisée. Ce type de ligne est en particulier contraint par un robot, se déplaçant sur un rail au dessus des cuves et assurant le transport du produit à traiter. Ce problème d’ordonnancement traité, appelé SHMP (Single-Hoist/Multi-Products) est connu pour être NP-difficile, même avec un seul produit et une seule ressource de transport. Basé sur les techniques de satisfaction de contraintes, un algorithme a été développé et mis en œuvre avec succès pour l’atelier de traitement de surfaces étudié. L’utilisation de l’hybridation de ce même algorithme avec d’autres méthodes s’est avérée intéressante et efficace pour déterminer des solutions de meilleure qualité. Nous avons également montré que le recours aux algorithmes génétiques pour l’optimisation du problème job shop mono-robot/multi-produits étudié conduit à des résultats encore plus intéressants et significatifs.La robustesse a aussi été considérée pour l’étude de l’influence des perturbations sur l’ordonnancement. Pour cela, la distinction de divers scénarii a été nécessaire pour l’étude de l’influence d’une perturbation au niveau du chariot. La détermination systématique d’un ordonnancement robuste a été ensuite menée, avec succès, par application d’une méthode d’évaluation multi-critères / In this thesis we study the automated electroplating lines. In these lines, the products are immerged in different tanks. The processing times are bounded. The lower bound represents the minimum time to treat the product while the upper bound depends on the treatment.A classical objective is to find the robot moves which minimize the cycle time, this is called ”hoist scheduling problem” (HSP). In this thesis, we study particularly the single-hoist/multi-products.In this direction, three approaches are presented to solve the single-hoist/multi-products problem with introducing the hoist moves time: constraints satisfaction algorithm based on non standard criteria witch the hoist wait time, hybridization with classical heuristics improving the obtained results, and finally the genetic algorithm to optimize the cycle time. Robustness’ notions are finally exploited in the presence of a disturbance at the critical resource of the workshop which is the hoist.The systematic determination of a robust scheduling has been conducted successfully introducing new performance indicators and by applying a multicriteria evaluation method

La navigation avec les systèmes de navigation par satellites (GNSS) est un réel défi dans des environnements contraints (semi-urbain, urbain, feuillage dense) à cause des multitrajets et du masquage du signal. Cette thèse propose un nombre de solutions architecturales et algorithmiques pour le récepteur GNSS afin de pallier ces problèmes. Ces solutions se veulent capables d’exploiter les atouts des poursuites scalaire et vectorielle tout en minimisant leurs défauts et de profiter de l’efficacité de certaines techniques de filtrage Bayésien non linéaire quant à aborder la non-Gaussianité et les non-linéarités associées au problème de navigation et de poursuite vectorielle. Une attention particulière est accordée à certains estimateurs Bayésiens qui essaient d’approximer la loi a posteriori sans linéariser le modèle de filtrage, notamment le filtre de Kalman et les méthodes de filtrage particulaire, mais aussi au filtre de Kalman étendu, dont l’estimation de la loi a posteriori est basée sur la linéarisation du modèle de filtrage. En premier lieu, une brève étude bibliographique présentant les fondamentaux des systèmes et des récepteurs GNSS ainsi que les algorithmes de navigation et de poursuite y associés est faite. Ensuite le fonctionnement d’un récepteur GNSS en milieux contraints est investigué. La thèse propose des modèles pour caractériser les erreurs de poursuite induites par les multitrajets dans une boucle de poursuite vectorielle. Ces modèles permettent d’exprimer les erreurs de poursuite en fonction du délai, de la phase et de la fréquence d’évanouissement des multitrajets. En exploitant le fait que la présence des multitrajets se reflète sur la sortie moins des corrélateurs, de nouveaux détecteurs de multitrajets sont formulés. Un détecteur de masquage du signal direct est aussi proposé. L’attention se tourne ensuite vers la conception d’architectures robustes de poursuite et positionnement pour un récepteur GNSS, incorporant les détecteurs proposés et d’autres indicateurs de qualité. Une boucle de poursuite vectorielle capable de détecter et d’exclure des mesures qui ne sont pas saines du calcul de la solution de navigation en utilisant les indicateurs de qualité est proposée. Deux autres boucles de poursuite, la boucle de poursuite adaptative scalaire-vectorielle et la boucle de poursuite conjointe scalaire-vectorielle, avec la même capacité de détection et exclusion de fautes, sont formulées. Elles bénéficient de la robustesse de la poursuite vectorielle en milieux contraints et de la précision de la poursuite scalaire en milieux dégagés. Des résultats expérimentaux montrent que les solutions conçues offrent une meilleure alternative de poursuite et positionnement par rapport aux boucles usuelles de poursuite scalaire et de poursuite vectorielle. Enfin, la thèse présente des approches de filtrage Bayésien non linéaire pour résoudre le problème de navigation et de poursuite vectorielle. Des stratégies de filtrage itératives et adaptatives appliquées au filtre de Kalman sont étudiées. Une nouvelle approche de filtrage particulaire dénommée filtre particulaire itératif et adaptatif (IAUPF) est formulée. Cette approche exploite les propriétés de convergence des méthodes itératives, l’immunité à la divergence dont jouissent les filtres adaptatifs, et la synergie entre les approches de filtrage particulaire et de Kalman. Des simulations de Monte Carlo avec une borne inférieure de Cramér-Rao a posteriori comme référence ainsi que des résultats expérimentaux montrent que l’approche IAUPF a une meilleure performance comparativement aux autres estimateurs Bayésiens présentés / Navigation with Global Navigation Satellite Systems (GNSS) is a real challenge in harsh environments (suburban, urban, heavy foliage) due to multipath and signal blockage. This thesis proposes a number of GNSS receiver architectural and algorithmic solutions to deal with this challenge. These solutions aim at exploiting the strengths of scalar and vector tracking while minimizing their weaknesses and at utilizing the efficiency of some nonlinear Bayesian filtering techniques in addressing the nonlinearities and non-Gaussianities associated with the navigation and vector tracking problem. Attention is given to some Bayesian estimators that approximate the posterior distribution without linearizing the filtering model, namely the unscented Kalman and particle filtering methods, as well as to the extended Kalman filter, whose posterior estimation is grounded on linearization of the filtering model.First, a brief literature review that presents the fundamentals of GNSS and GNSS receivers together with the applied navigation and tracking algorithms is provided. Then an investigation of the GNSS receiver operation in multipath environments is performed. The thesis proposes models for characterizing multipath induced tracking errors in a vector tracking loop. These models make it possible to express the tracking errors with respect to multipath delay, multipath phase and multipath fading frequency. By exploiting the fact that multipath presence is mirrored on the Early-minus-Late correlator output, novel multipath detectors are devised. A correlator-based non-line-of-sight detector is designed as well. Attention is then directed towards the design of robust tracking and positioning GNSS receiver architectures that incorporate the proposed detectors among other signal quality indicators. A vector tracking scheme capable of detecting and excluding unhealthy measurements from position-velocity-time calculation in the navigator using correlator-based signal quality indicators is suggested. Two other novel tracking schemes, the adaptive scalar-vector tracking loop and the conjoint scalar-vector tracking loop, with the same fault detection and exclusion capability, are formulated. They benefit from vector tracking robustness in harsh environments and scalar tracking positioning accuracy in open sky environments. Experimental results show that the proposed solutions have better tracking and positioning performance than the usual scalar and vector tracking loops. Finally, the thesis presents a number of nonlinear Bayesian filtering approaches to solve the navigation and vector tracking problem. Iterative and adaptive strategies as applied to the unscented Kalman filter are studied. A novel unscented particle filter approach, the iterated adaptive unscented particle filter (IAUPF), is proposed. This approach exploits the convergence properties of iterative methods, the divergence suppression benefits of adaptive filters and the synergy of unscented Kalman and particle filtering approaches. Monte-Carlo simulations conducted with a posterior Cramér-Rao lower bound used as benchmarking reference as well as experimental results demonstrate that the IAUPF outperforms the other Bayesian estimators that are presented

Cette thèse consiste à améliorer les outils statistiques adaptés à des modèles stochastiques de génétiques des populations et de développer des méthodes statistiques adaptées à des données génétiques de nouvelle génération. Pour un modèle paramétrique basé sur le coalescent, la vraisemblance en un point de l'espace des paramètres s'écrit comme la somme des probabilités de toutes les histoires (généalogies munies de mutations) possibles de l'échantillon observé. À l'heure actuelle, les meilleures méthodes d'inférence des paramètres de ce type de modèles sont les méthodes bayésiennes approchées et l'approximation de la fonction de vraisemblance.L'algorithme d'échantillonnage préférentiel séquentiel (SIS) estime la vraisemblance, en parcourant de manière efficace l'espace latent de ces histoires. Dans ce schéma, la distribution d'importance propose les histoires de l'échantillon observé les plus probables possibles. Cette technique est lourde en temps de calcul mais fournit des estimations par maximum de vraisemblance d'une grande précision.Les modèles que nous souhaitons inférer incluent des variations de la taille de la population. Les méthodes d'IS ne sont pas efficaces pour des modèles en déséquilibre car les distributions d'importance ont été développées pour une population de taille constante au cours du temps. Le temps de calcul augmente fortement pour la même précision de l'estimation de la vraisemblance. La première contribution de cette thèse a consisté à explorer l'algorithme SIS avec ré-échantillonnage (SISR). L'idée est de ré-échantillonner de façon à apprendre quelles sont les histoires proposées par la distribution d'importance qui seront les plus probables avant d'avoir terminé leur simulation et diminuer le temps de calcul. Par ailleurs, nous avons proposé une nouvelle distribution de ré-échantillonnage, tirant profit de l'information contenue dans la vraisemblance composite par paire de l'échantillon.Le développement récent des technologies de séquençage à haut débit a révolutionné la génération de données de polymorphisme chez de nombreux organismes. Les méthodes d'inférence classiques de maximum de vraisemblance ou basées sur le Sites Frequency Spectrum, adaptées à des jeux de données de polymorphisme génétique de quelques loci, supposent l'indépendance des généalogies des loci. Pour tirer parti de données beaucoup plus denses sur le génome, nous considérons la dépendance des généalogies sur des positions voisines du génome et modéliser la recombinaison génétique. Alors, la vraisemblance prend la forme d'une intégrale sur tous les graphes de recombinaison ancestraux possibles pour les séquences échantillonnées, un espace de bien plus grande dimension que l'espace des généalogies. Les méthodes d'inférence basées sur la vraisemblance ne peuvent plus être utilisées sans plus d'approximations. De nombreuses méthodes infèrent les changements historiques de la taille de la population mais ne considèrent pas la complexité du modèle ajusté. Même si certaines proposent un contrôle d'un potentiel sur-ajustement du modèle, à notre connaissance, aucune procédure de choix de modèle entre des modèles démographiques de complexité différente n'a été proposée à partir de longueurs de segments identiques. Nous nous concentrons sur un modèle de taille de population constante et un modèle de population ayant subit un unique changement de taille dans le passé. Puisque ces modèles sont emboîtés, la deuxième contribution de cette thèse a consisté à développer un critère de choix de modèle pénalisé basé sur la comparaison d'homozygotie haplotypique observée et théorique. Notre pénalisation, reposant sur des indices de sensibilité de Sobol, est liée à la complexité du modèle. Ce critère pénalisé de choix de modèle nous a permis de choisir entre un modèle de taille de population constante ou présentant un changement passé de la taille de la population sur des jeux de données simulés et sur un jeux de données de vaches. / This thesis aims to improve statistical methods suitable for stochastic models of population genetics and to develop statistical methods adapted to next generation sequencing data.Sequential importance sampling algorithms have been defined to estimate likelihoods in models of ancestral population processes. However, these algorithms are based on features of the models with constant population size, and become inefficient when the population size varies in time, making likelihood-based inferences difficult in many demographic situations. In the first contribution of this thesis, we modify a previous sequential importance sampling algorithm to improve the efficiency of the likelihood estimation. Our procedure is still based on features of the model with constant size, but uses a resampling technique with a new resampling probability distribution depending on the pairwise composite likelihood. We tested our algorithm, called sequential importance sampling with resampling (SISR) on simulated data sets under different demographic cases. In most cases, we divided the computational cost by two for the same accuracy of inference, in some cases even by one hundred. This work provides the first assessment of the impact of such resampling techniques on parameter inference using sequential importance sampling, and extends the range of situations where likelihood inferences can be easily performed.The recent development of high-throughput sequencing technologies has revolutionized the generation of genetic data for many organisms : genome wide sequence data are now available. Classical inference methods (maximum likelihood methods (MCMC, IS), methods based on the Sites Frequency Spectrum (SFS)) suitable for polymorphism data sets of some loci assume that the genealogies of the loci are independent. To take advantage of genome wide sequence data with known genome, we need to consider the dependency of genealogies of adjacent positions in the genome. Thus, when we model recombination, the likelihood takes the form of an integral over all possible ancestral recombination graph for the sampled sequences. This space is of much larger dimension than the genealogies space, to the extent that we cannot handle likelihood-based inference while modeling recombination without further approximations.Several methods infer the historical changes in the effective population size but do not consider the complexity of the demographic model fitted.Even if some of them propose a control for potential over-fitting, to the best of our knowledge, no model choice procedure between demographic models of different complexity have been proposed based on IBS segment lengths. The aim of the second contribution of this thesis is to overcome this lack by proposing a model choice procedure between demographic models of different complexity. We focus on a simple model of constant population size and a slightly more complex model with a single past change in the population size.Since these models are embedded, we developed a penalized model choice criterion based on the comparison of observed and predicted haplotype homozygosity.Our penalization relies on Sobol's sensitivity indices and is a form of penalty related to the complexity of the model.This penalized model choice criterion allowed us to choose between a population of constant size and a population size with a past change on simulated data sets and also on a cattle data set.

Dans cette thèse, nous abordons le problème de la génération automatique de contenu graphique avec un haut niveau de détails pour la génération de mondes. Dans cette quête du réalisme, les principaux verrous scientifiques et techniques sont : la gestion des masses de données géométriques nécessaires à la création de variétés d'objets naturels, la prise en compte des interactions en les différents objets et le contrôle utilisateur.Notre approche s'appuie sur un modèle volumique original et unificateur permettant de représenter les différents matériaux d'un terrain. Nous proposons un ensemble d'algorithmes de haut niveau, combinant des étapes de simulation pour assurer la plausibilité physique et le réalisme visuel à des techniques de génération procédurale permettant de gérer efficacement la complexité. Nos algorithmes permettent ainsi de sculpter des terrains complexes avec des grottes ou des surplombs et de générer des routes avec des tunnels et des ponts permettant le franchissement d'obstacles naturels. / In this thesis, we address the problem of automatic generation of graphical content with a high level of detail for the generation of worlds. In this quest for realism, the major scientific and technical challenges include: managing the mass of geometric data needed to create varieties of natural objects, taking into account interactions with the various objects and user control.Our approach is based on an original volumetric model for representing and unifying the different materials of land. We offer a range of high-level algorithms, combining simulation steps to ensure physical plausibility and visual realism, and procedural generation techniques to effectively manage complexity. Our algorithms are used to sculpt and complex terrain with caves and overhangs and generate roads with tunnels and bridges to cross natural barriers.

Le travail de thèse s'inscrit dans la modélisation numérique de l'écoulement des matériaux cimentaires à l'état frais couplée à un outil d'identification des paramètres. Il traite en particulier l'étape de mise en place de l'identification par analyse inverse. D'abord, une analyse de la littérature fait ressortir l'existence d'outils rhéométriques dédiés aux suspensions cimentaires ; le passage des grandeurs macroscopiques à celles locales est faite, soit par le biais de l'utilisation de géométries conventionnelles, soit au moyen de méthodes de calibration. Néanmoins, ces outils ne permettent pas de trouver une signature rhéologique unique pour une même suspension. De plus, les stratégies d'identification des paramètres relatifs aux matériaux cimentaires frais sont peu nombreuses et limitées aux données locales. Ensuite, une stratégie qui consiste à identifier les paramètres d'une loi supposée, directement à partir des mesures macroscopiques simulées (couples, vitesses de rotation imposées au mobile de cisaillement) a été développée et validée en 2D, en discutant notamment de l'efficacité des algorithmes d'optimisation testés (méthode du simplexe et algorithmes génétiques), en fonction du degré de connaissances que l'utilisateur a du matériau. Enfin, la méthode a été appliquée en 3D sur des fluides modèles supposés homogènes. Elle apparaît efficace en fluide pseudo-plastique, notamment par combinaison des algorithmes d'optimisation. Mais il reste des obstacles à lever en fluide visco-plastique, vraisemblablement liés aux outils expérimentaux plutôt qu'à la procédure d'identification elle-même. / The thesis work is part of the numerical modeling of the flow of cementitious materials in the fresh state coupled with an identification procedure of the parameters. It deals in particular with the step of the development of the identification by inverse analysis. First,the literature review reveals the existence of rheometric tools dedicated to cementitious suspensions; The passage from the macroscopic quantities to the local ones is made either by the use of conventional geometries or by means of calibration methods. Nevertheless, these tools do not make it possible to find the expected single rheological signature for a given suspension. In addition, there are few studies reporting strategies for identifying constitutive parameters in the case of fresh cement-based materials and they are limited to local data. Then, a strategy consisting in identifying the parameters of a supposed law, directly on the basis of the simulated macroscopic measurements (torques, rotational speeds imposed on the shearing tool) was developed and validated in 2D, discussing in particular the efficiency Of the optimization algorithms tested (simplex method and genetic algorithms), according to the degree of knowledge that the user has of the material. Finally, the method has been applied in 3D on model fluids, assuming that they are homogeneous. The method appears effective in the case of pseudo-plastic fluid, in particular by combining both optimization algorithms used. But there remain obstacles to overcome in the case of visco-plastic fluids, probably related to the experimental tools rather than to the procedure of identification itself.

La collecte de données par des réseaux de capteurs autonomes mobiles peut être couplée à l’utilisation de drones qui constituent une solution de backahauling facilement déployable à faible coût. Ces moyens de collecte peuvent servir lors de l’organisation d’évènements temporaires (sportifs ou culturels) ou encore pour mener des opérations dans des terrains difficiles d’accès ou hostiles. L’objectif de cette thèse est de proposer des solutions efficaces pour la communication à la fois entre capteurs mobiles au sol et sur la liaison bord-sol. A ces fins, nous nous intéressons à l’ordonnancement des communications, au routage et au contrôle de l’accès sur la liaison capteurs/drone, le collecteur mobile. Nous proposons une architecture répondant aux contraintes du réseau. Les principales sont l’intermittence des liens et donc le manque de connexité pour lesquelles des solutions adaptées aux réseaux tolérants aux délais sont adoptées. Vu la limitation des opportunités de communication avec le drone et la variation importante du débit physique, nous avons proposés des solutions d’ordonnancement qui tiennent compte à la fois des durées de contact que du débit physique. Le routage opportuniste est également fondé sur ces deux critères à la fois pour la sélection des nœuds relais que pour la gestion des files d’attente. Nous avons souhaité limiter l’overhead et proposer des solutions efficaces et équitables entre capteurs mobiles au sol. Les solutions proposées ont montré leur supériorité par rapport aux solutions d’ordonnancement et de routage classiques. Nous avons enfin, proposé une méthode d’accès combinant un accès aléatoire avec contention ainsi qu’un accès avec réservation tenant compte des critères précédemment cités. Cette solution flexible permet à un réseau de capteurs mobiles denses de se rapprocher des performances obtenues dans un mode oracle. Les solutions proposées peuvent être mises en œuvre et appliquées dans différents contextes applicatifs pour lesquels les nœuds au sol sont mobiles ou aisément adaptées au cas où les nœuds sont statiques. / Data collection by autonomous mobile sensor arrays can be coupled with the use of drones which provide a low-cost, easily deployable backhauling solution. These means of collection can be used to organize temporary events (sporting or cultural) or to carry out operations in difficult or hostile terrain. The aim of this thesis is to propose effective solutions for communication between both mobile sensors on the ground and on the edge-to-ground link. For this purpose, we are interested in scheduling communications, routing and access control on the sensor / drone link, the mobile collector. We propose an architecture that meets the constraints of the network. The main ones are the intermittence of the links and therefore the lack of connectivity for which solutions adapted to the networks tolerant to the deadlines are adopted. Given the limited opportunities for communication with the drone and the significant variation in the physical data rate, we proposed scheduling solutions that take account of both the contact time and the physical flow rate. Opportunistic routing is also based on these two criteria both for the selection of relay nodes and for the management of queues. We wanted to limit the overhead and propose efficient and fair solutions between mobile sensors on the ground. The proposed solutions have proved superior to conventional scheduling and routing solutions. Finally, we proposed a method of access combining a random access with contention as well as an access with reservation taking into account the aforementioned criteria. This flexible solution allows a network of dense mobile sensors to get closer to the performance obtained in an oracle mode. The proposed solutions can be implemented and applied in different application contexts for which the ground nodes are mobile or easily adapted to the case where the nodes are static.

Cette thèse se situe à l'interface entre l'analyse d'images, dont l'objectif est la description automatique du contenu visuel, et la géométrie discrète, qui est l'un des domaines dédiés au traitement des images numériques. Pour être stocké et manipulé sur un ordinateur, un signal observé est régulièrement échantillonné. L'image numérique, qui est le résultat de ce processus d'acquisition, est donc constituée d'un ensemble fini d'éléments distincts. La géométrie discrète se propose d'étudier les propriétés géométriques d'un tel espace dépourvu de continuité. Dans ce cadre, nous avons considéré les régions homogènes et porteuses de sens d'une image, avec l'objectif de représenter leur contour au moyen de modèles géométriques ou de les décrire à l'aide de mesures. L'étendue des applications de ce travail en analyse d'images est vaste, que ce soit au cours du processus de segmentation, ou en vue de la reconnaissance d'un objet. Nous nous sommes concentrés sur trois modèles géométriques discrets définis par la discrétisation de Gauss : la partie convexe ou concave, l'arc de cercle discret et le segment de droite discrète. Nous avons élaboré des algorithmes dynamiques (mise à jour à la volée de la décision et du paramétrage), exacts (calculs en nombres entiers sans erreur d'approximation) et rapides (calculs simplifiés par l'exploitation de propriétés arithmétiques et complexité en temps linéaire) qui détectent ces modèles sur un contour. L'exécution de ces algorithmes le long d'un contour aboutit à des décompositions ou à des polygonalisations réversibles. De plus, nous avons défini des mesures de convexité, linéarité et circularité, qui vérifient un ensemble de propriétés fondamentales : elles sont robustes aux transformations rigides, elles s'appliquent à des parties de contour et leur valeur maximale est atteinte pour le modèle de forme qui sert de comparaison et uniquement sur celui-ci. Ces mesures servent à l'introduction de nouveaux modèles dotés d'un paramètre variant entre 0 et 1. Le paramètre est fixé à 1 quand on est sûr de la position du contour, mais fixé à une valeur inférieure quand le contour est susceptible d'avoir été déplacé par un bruit d'acquisition. Cette approche pragmatique permet de décomposer de manière robuste un contour en segments de droite ou en parties convexes et concaves. / The work presented in this thesis concerns the fields of image analysis and discrete geometry. Image analysis aims at automatically describing the visual content of a digital image and discrete geometry provides tools devoted to digital image processing. A two-dimensional analog signal is regularly sampled in order to be handled on computers. This acquisition process results in a digital image, which is made up of a finite set of discrete elements. The topic of discrete geometry is to study the geometric properties of such kind of discrete spaces. In this work, we consider homogeneous regions of an image having a meaning for a user. The objective is to represent their digital contour by means of geometric patterns and compute measures. The scope of applications is wide in image analysis. For instance, our results would be of great interest for segmentation or object recognition. We focus on three discrete geometric patterns defined by Gauss digitization: the convex or concave part, the digital straight segment and the digital circular arc. We present several algorithms that detect or recognize these patterns on a digital contour. These algorithms are on-line, exact (integer-only computations without any approximation error) and fast (simplified computations thanks to arithmetic properties and linear-time complexity). They provide a way for segmenting a digital contour or for representing a digital contour by a reversible polygon. Moreover, we define a measure of convexity, a measure of straightness and a measure of circularity. These measures fulfil the following important properties: they are robust to rigid transformations, they may be applied on any part of a digital contour, they reach their maximal value for the template with which the data are compared to. From these measures, we introduce new patterns having a parameter that ranges from 0 to 1. The parameter is set to 1 when the localisation of the digital contour is reliable, but is set to a lower value when the digital contour is expected to have been shifted because of some acquisition noise. This measure-based approach provides a way for robustly decomposing a digital contour into convex, concave or straight parts.

Les technologies microélectroniques ainsi que les outils de CAO actuels permettent la conception de plus en plus rapide de circuits et systèmes intégrés très complexes. L'un des plus importants problèmes rencontrés est de gérer la complexité en terme de nombre de transistors présents dans le système à manipuler ainsi qu'en terme de diversité des composants, dans la mesure où les systèmes actuels intègrent, sur un même support de type SiP ou bien SoC, de plus en plus de blocs fonctionnels hétérogènes. Le but de cette thèse est la recherche de nouvelles techniques de test qui mettent à contribution les ressources embarquées pour le test et le contrôle des modules AMS et RF. L'idée principale est de mettre en oeuvre pour ces composantes des méthodes de test et de contrôle suffisamment simples pour que les ressources numériques embarquées puissent permettre leur implémentation à faible coût. Les techniques proposées utilisent des modèles de représentation auto-régressifs qui prennent en comptes les non linéarités spécifiques à ce type de modules. Les paramètres du modèle comportemental du système sont utilisés pour la prédiction des performances du système qui sont nécessaire pour l'élaboration de la signature de test et le contrôle de la consommation du circuit. Deux démonstrateurs ont été mis en place pour valider la technique proposée : une chaine RF conçue au sein du groupe RMS et un accéléromètre de type MMA7361L. / Analogue-mixed-signal (AMS) and Radio frequency (RF) devices are required in many applications such as communications, multimedia, and signal processing. These applications are often subject to severe area constraints. The complexity of AMS and RF cores, together with shrinking device dimensions limit accessibility to the internal nodes of the circuit. This makes the test and the control of this circuit very difficult. Ensuring high test/control quality at low cost for these AMS and RF designs has become an important challenge for test engineers. RF and AMS cores are generally incorporated in a chip including large digital components as microprocessors and memories. The main idea of this work is to develop for these components simple test and control methods which can be implemented in the embedded resources of the system at low cost. The proposed techniques use autoregressive models for the devices under test/control. These models take into account the specific nonlinearities to such devices. Only the behavioural model parameters of the system are used to predict the system performances which are necessary to develop the test signature and/or control the consumption of the circuit. This method is implemented on a dsPiC30f for testing and controlling two demonstrators: a front-end RF card, designed in RMS group of TIMA laboratory, and a MMA7361L 3 axis accelerometer.

Ma thèse s'inscrit dans le domaine de l'ingénierie de l'interaction homme-machine. Elle traite de la conception d'interfaces hommes machine (IHM). La créativité n'y est souvent considérée que de manière marginale. Pourtant l'effervescence technologique et la diversité résultante des contextes d'usage appellent à de plus en plus de créativité. Ma thèse soutient le principe que l'innovation passe par l'application de processus créatifs. Dès lors, le défi est de savoir explorer largement et efficacement l'espace de conception dès les phases amont du processus. Il convient donc d'intégrer et d'enseigner la créativité dans les processus de conception d'IHM, en particulier pour les concepteurs débutants.Ce positionnement sur le sujet provient d'une double approche : d'une part théorique, avec un état de l'art explorant les dimensions de la créativité et les outils informatiques de support à la créativité ; d'autre part empirique, avec quatre mises en pratique de la créativité dans des domaines de conception différents comme l'architecture, la conception de produit et la conception de systèmes interactifs. Je construis ma contribution sur les principes suivants : (1) la créativité n'est pas réservée à une élite, mais peut être travaillée et renforcée par des outils informatiques ; (2) ces outils doivent soutenir la motivation, la recherche d'inspiration, l'exploration en largeur, et les connaissances relatives au domaine et aux processus de conception. Selon une démarche réflexive, j'applique ces mêmes principes dans ma thèse. Je propose une exploration en largeur du support à la créativité via cinq contributions logicielles complémentaires : Maestro et Bank pour la capitalisation des connaissances ; WebGallery, BrianStorming et Magellan pour l'inspiration et l'exploration de l'espace de conception. Plus précisément, Maestro traite de la capitalisation des processus de conception tandis que BANK assure la structuration et la capitalisation des connaissances en IHM via un graphe de modèles. WebGallery est une galerie de sites web pour inspirer les concepteurs : je conduis une expérimentation sur la perception humaine du style d'un site web. BrianStorming est un assistant au brainstorming : il fournit des suggestions pendant une séance de brainstorming électronique. Magellan est un environnement interactif à base d'algorithmes génétiques qui génèrent et transforment automatiquement des IHM pour un problème de conception donné. Par ce positionnement et ces contributions logicielles, l'ordinateur change de statut : de simple outil, il devient un concepteur assistant, partenaire du processus de créativité. / My PhD thesis contributes to the engineering of Human Computer Interaction (HCI). It deals with the design of User Interfaces (UI). I claim that creative processes should be better considered, and supported by tools especially for novice designers. The challenge is to speed up the exploration of the design space at the early stages of the process. This claim is grounded in both a theoretical state of the art in creativity and creativity support tools, and in practice of the topic with four hands-on experiences of creativity in different areas of design such as architecture, product design and UI design. I build my contribution on the following principles: (1) creativity is not reserved for the elite, but can be tailored and fostered by software tools; (2) the tools must leverage motivation, inspiration, wide exploration, and knowledge in UI and design processes. Through a reflective process, I apply these principles to my thesis. I explore a wide range of creativity support tools through five complementary software contributions: Maestro and Bank for supporting knowledge capitalization; WebGallery, BrianStorming and Magellan for fostering inspiration and exploration of the design space. Maestro addresses the capitalization of design processes whilst BANK gathers knowledge in HCI as a graph of models. WebGallery is a gallery of websites to inspire designers: I report an experiment on human perception of websites styles. BrianStorming is a brainstorming assistant: it provides suggestions in a electronic brainstorming session. Magellan is an interactive environment based on genetic algorithms that automatically generate and transform UIs for a given design problem. This changes the role of the computer: from a simple tool, it becomes a designer's partner in the creative process.

Cette thèse cherche à résoudre en pratique le problème de couverture dans les réseaux de Petri et les systèmes de canaux à pertes (LCS). Ces systèmes sont intéressants à étudier car ils permettent de modéliser facilement les systèmes concurrents et les systèmes distribués. Le problème de couverture dans un système de transitions consiste à savoir si on peut, à partir d’un état initial arriver à un état plus grand qu’un état cible. La résolution de ce problème dans les systèmes de transitions bien structurés (WSTS) sera le sujet d’études de la première partie. Les réseaux de Petri et les LCS sont des WSTS. On donnera dans la première partie une méthode générale pour le résoudre rapidement en pratique. Cette méthode utilise des invariants de couverture, qui sont des sur-approximations de l’ensemble des états couvrables. La seconde partie sera consacrée aux réseaux de Petri. Elle présentera diverses comparaisons théoriques et pratiques de différents invariants de couverture. Nous nous intéresserons notamment à la combinaison de l’invariant classique de l’inéquation d’état avec une analyse de signe simple. Les LCS seront le sujet d’études de la troisième partie. On présentera une variante de l’inéquation d’état adaptée aux LCS ainsi que deux invariants qui retiennent des propriétés sur l’ordre dans lequel les messages sont envoyés. La thèse a mené à la création de deux outils, ICover et BML, pour résoudre le problème de couverture respectivement dans les réseaux de Petri et dans les LCS. / The goal of this thesis is to solve in practice the coverability problem in Petri nets and lossy channel systems (LCS). These systems are interesting to study because they can be used to model concurrent and distributed systems. The coverability problem in a transition system is to decide whether it is possible, from an initial state, to reach a greater state than a target state. In the first part, we discuss how to solve this problem for well-structured transition systems (WSTS). Petri nets and LCS are WSTS. In the first part, we present a general method to solve this problem quickly in practice. This method uses coverability invariants, which are over-approximations of the set of coverable states. The second part studies Petri nets.We present comparisons of coverability invariants, both in theory and in practice. A particular attention will be paid on the combination of the classical state inequation and a simple sign analysis. LCS are the focus of the third part. We present a variant of the state inequation for LCS and two invariants that compute properties for the order in which messages are sent. Two tools, ICover and BML, were developed to solve the coverability problem in Petri nets and LCS respectively.