Les travaux présentés dans cette thèse visent à proposer des méthodes permettant de résoudre un problème de Transport à la Demande multicritère. Le premier travail réalisé dans cette thèse est l'étude d'un problème de Dial-a-Ride (DARP) statique multicritère. Trois critères qui peuvent être conflictuels ont été définis : le premier consiste à minimiser le coût de transport, le deuxième critère consiste à minimiser l'insatisfaction des passagers et enfin le troisième critère consiste à minimiser la quantité de CO2 émise par l'ensemble des véhicules. Nous avons développé une méthode évolutionnaire NSGA-II pour chercher un ensemble approximatif d'optimas de Pareto. Le second travail réalisé est l'étude d'un problème d'Optimal Timing dans une tournée. Ce problème consiste à calculer les dates de début de service optimales des points d'arrêts d'une tournée afin de minimiser l'insatisfaction des passagers. Le dernier travail de cette thèse a porté sur l'étude d'un problème de Transport à la Demande dynamique dans lequel de nouvelles requêtes à traiter arrivent en cours de journée. Deux méthodes ont été proposées pour résoudre ce problème : la première est une heuristique d'insertion rapide et la seconde est une méthode arborescente tronquée connue sous le nom de Recovering Beam Search. / The work presented in this thesis aims to propose methods to solve a multicriteria dial-a-ride problem (DARP). Three objective functions that have to be optimized in order to measure the potential efficiency of the DARP solution on different aspects : the cost for the transportation operator, the quality of service for users and the impact on the environment. The first work in this thesis is the study of static DARP for which a NSGA-II algorithm is developped to identify a good approximation of the Pareto optimal set. The second work deals with an optimal timing algorithm which computes pickup and delivery dates when the requests are sequenced on the vehicles, the objective is to minimize the total customer' dissatisfaction. The last problem studied in this thesis aims to solve the dynamic version of DARP for which two methods are proposed. The first one is a fast insertion heuristic based on an attractive index. However, the second methode uses a recovering beam search heuristic which unlike the insertion heuristic allows to modify the structure of the routes previously scheduled in order to schedule the new requests.

La thèse est décomposée en trois parties. Dans la première partie, les modèles de la CUF sont présentés. La CUF permet d’obtenir, dans un formalisme générale, de nombreux modèles qui diffèrent 1) selon l’ordre d’expansion dans l'épaisseur choisie pour les variables primaires; 2) selon le type de modèle: modèles couche équivalente (ESL) ou couche discrète (LW); 3) selon le principe variationnel : “Principle of Virtual Displacements” (raffinée) ou “Reissner’s Mixed Variational Theorem” (avancée). Des géométries cylindrique et à double courbure sont traités. La deuxième partie de la thèse est consacrée à l'obtention des équations fondamentales en utilisant différentes méthodes: la méthode analytique de Navier et deux méthodes numériques approchées; la “Finite Element Method” (FEM) et la “Radial Basis Functions” (RBF). La méthode RBF est une méthode sans maillage “meshless” et peut être considérée comme une méthode alternative à la FEM. La FEM est la plus utilisée dans la littérature et le sujet principal de cette thèse.Dans la dernière partie, différents problèmes sont proposés. Navier est utilisé pour l’analyse thermomécanique de coques FGM, l’analyse de coques piézo-électrique et l’analyse dynamique de nanotubes de carbone. Un élément fini coque, présenté dans cette thèse, est utilisé pour l’analyse de coques composites et FGM. Les résultats obtenus démontrent la supériorité de cet élément par rapport aux éléments finis basés sur les théories classiques pour l’analyse des matériaux avancés. Enfin, la méthode RBF est utilisée pour l’analyse de coques composites, permettant d'illustrer l'avantage des méthodes sans maillage. / The dissertation is organized in three main parts. In the first part, the shell models contained in the CUF are presented. The CUF permits to obtain, in a general and unified manner, several models that can differ by 1) the chosen order of expansion in the thickness direction, 2) the equivalent single layer or layer wise approach and 3) the variational statement used: “Principle of Virtual Displacements” (refined models) or “Reissner’s Mixed Variational Theorem” (advanced models). Both the cylindrical and the double-curvature geometries are considered. The second part is devoted to the derivation of the governing equations by means of different methods: an analytical method, that is the Navier method, and two approximated numerical methods, that are the Finite Element Method (FEM) and the Radial Basis Functions (RBF) method. The RBF method is based on a meshless approach and it can be considered a good alternative to the FEM. The finite element method is the most common method used in literature and it is the main topic of this thesis. In the last part, different problems are analyzed. The thermo-mechanical analysis of FGM shells, the electromechanical analysis of piezoelectric shells and the dynamic analysis of carbon nanotubes are performed by means of the Navier method. Then, the CUF shell finite element, presented in this thesis, is tested and used for the analysis of composite and FGM shells. The superiority of this element in respect to finite elements based on classical theories is shown. Finally, the RBF method is combined with the CUF for the analysis of composite and FGM shells in order to overcome the numerical problems relative to the mesh that usually affect the finite elements.

Le but principal de ce manuscrit est celui de présenter une nouvelle méthode d'interpolation entre des probabilités inspirée du problème de Schrödinger, problème de minimisation entropique ayant des liens très forts avec le transport optimal. À l'aide de solutions au problème de Schrödinger, nous obtenons un schéma d'approximation robuste jusqu'au deuxième ordre et différent de Brenier-McCann qui permet d'établir la formule de dérivation du deuxième ordre le long des géodésiques Wasserstein dans le cadre de espaces RCD* de dimension finie. Cette formule était inconnue même dans le cadre des espaces d'Alexandrov et nous en donnerons quelques applications. La démonstration utilise un ensemble remarquable de nouvelles propriétés pour les solutions au problème de Schrödinger dynamique :- une borne uniforme des densités le long des interpolations entropiques ;- la lipschitzianité uniforme des potentiels de Schrödinger ;- un contrôle L2 uniforme des accélérations. Ces outils sont indispensables pour explorer les informations géométriques encodées par les interpolations entropiques. Les techniques utilisées peuvent aussi être employées pour montrer que la solution visqueuse de l'équation d'Hamilton-Jacobi peut être récupérée à travers une méthode de « vanishing viscosity », comme dans le cas lisse.Dans tout le manuscrit, plusieurs remarques sur l'interprétation physique du problème de Schrödinger seront mises en lumière. Cela pourra aider le lecteur à mieux comprendre les motivations probabilistes et physiques du problème, ainsi qu'à les connecter avec la nature analytique et géométrique de la dissertation. / Main aim of this manuscript is to present a new interpolation technique for probability measures, which is strongly inspired by the Schrödinger problem, an entropy minimization problem deeply related to optimal transport. By means of the solutions to the Schrödinger problem, we build an efficient approximation scheme, robust up to the second order and different from Brenier-McCann's classical one. Such scheme allows us to prove the second order differentiation formula along geodesics in finite-dimensional RCD* spaces. This formula is new even in the context of Alexandrov spaces and we provide some applications.The proof relies on new, even in the smooth setting, estimates concerning entropic interpolations which we believe are interesting on their own. In particular we obtain:- equiboundedness of the densities along the entropic interpolations,- equi-Lipschitz continuity of the Schrödinger potentials,- a uniform weighted L2 control of the Hessian of such potentials. These tools are very useful in the investigation of the geometric information encoded in entropic interpolations. The techniques used in this work can be also used to show that the viscous solution of the Hamilton-Jacobi equation can be obtained via a vanishing viscosity method, in accordance with the smooth case. Throughout the whole manuscript, several remarks on the physical interpretation of the Schrödinger problem are pointed out. Hopefully, this will allow the reader to better understand the physical and probabilistic motivations of the problem as well as to connect them with the analytical and geometric nature of the dissertation.

L’objectif de cette thèse, en sciences de l’information et de la communication, est de questionner les enjeux liés à la localisation de la communication de prévention à l’occasion de la politique publique de sécurité routière en France.L’émergence de la communication publique de l’État en France est récente. Elle remonte aux années 1970 avec la politique de création des villes nouvelles et l’introduction de la communication comme facteur de changement de l’administration et de modification du comportement des individus. Ce dernier aspect montre la croyance en un « pouvoir d’influence » de la communication médiatisée de la part des pouvoirs publics et par là-même la tendance qui en résulte d'analyser la communication publique de l’État à travers sa seule dimension « médiatique ». Sans occulter la place des médias dans la communication publique, l’analyse s’intéresse aux différentes dimensions sous-jacentes, qui émergent par la localisation de la communication de prévention sur le thème de la sécurité routière, dont les médias ne semblent refléter qu’une partie.Cette approche par la localisation met en présence des logiques, des stratégies d’acteurs et des représentations qui s’affrontent et montrent que de la question de la sécurité routière émergent d’autres enjeux qui dépassent le cadre initial comme notamment celui de la quête de la visibilité, celui de la légitimation de l’action publique à travers la communication, celui de la normalisation du comportement à travers l’encadrement de la conduite individuelle et celui de la gouvernance des territoires à l'heure où l'État semble perdre de plus en plus de prérogatives au profit des collectivités territoriales.L'approche diachronique de l’ « institutionnalisation » de la communication de l’État sur la question de la sécurité routière et de ses enjeux montre trois périodes clés : les années 1970 avec une approche "technique" de la sécurité routière et la naissance des premières campagnes de prévention (d’abord dans le milieu associatif). Ensuite les années 1980 et les premiers mouvements de décentralisation qui marquent une nouvelle orientation dans le cadre de l’action publique concernant la sécurité routière qui se lit non seulement à travers la structuration interne de l’appareil d’État (restructuration de ses services externes) mais également à travers son déploiement territorial et le transfert de compétences aux pouvoirs locaux. Enfin, les années 2000 voient le renforcement de la dimension « coercitive » et la mise en place d'un ensemble d'outils en ce sens.L’analyse de l’évolution de la communication publique sur la thématique de la sécurité routière et de sa localisation montre qu’elle est intrinsèquement liée à l’évolution même de l’administration d’État (aux niveaux structurel et politique) d’où les tentatives de réorientations successives (et pas nécessairement différentes) de cette politique, l’intervention d'acteurs aux intérêts et logiques différents qui n’apportent pas forcément une redéfinition de la politique de communication (du moins pas dans sa partie la plus visible), l'importance de la mobilisation des outils quantitatifs, réactivée par les lois de finance ainsi que les impératifs au niveau européen. / The objective of this thesis, in information and communication sciences, is to question the issues related to the location of prevention communication during the public policy about road safety in France.In France,the emergence of public communication of the state is recent. It dates back to the 1970s with the policy of creating new towns and the introduction of communication as a factor of change of administration and modification of the behavior of individuals. This last aspect shows the belief in a "power of influence" of the publicized communication on the part of the public authorities and hence the resulting tendency to analyze public communication of the State through its sole dimension “The media ". Without obscuring the role of the media in public communication, the analysis focuses on the various underlying dimensions emerging from the localization of prevention communication on the theme of road safety, the media of which seem to reflect only “a part.This localization approach brings together the logics, the strategies of the actors and the representations that confront each other and show that issues of road safety emerge from other issues that go beyond the initial framework, in particular that of the quest for The visibility, the legitimisation of public action through communication, the normalization of behavior through the management of individual conduct and the governance of territories at a time when the state seems to lose More and more prerogatives for the benefit of local and regional authorities.The diachronic approach of the "institutionalization" of state communication on the issue of road safety and its stakes shows three key periods: the 1970s with a "technical" approach to road safety and the birth of First prevention campaigns (first in the voluntary sector). Then the 1980s and the first decentralization movements marked a new orientation in the framework of public action concerning road safety, which is read not only through the internal structuring of the State apparatus (restructuring of its external services ) But also through its territorial deployment and the transfer of powers to local authorities. Finally, the 2000s saw the strengthening of the "coercive" dimension and the setting up of a set of tools in this sense.The analysis of the evolution of public communication on the issue of road safety and its location shows that it is intrinsically linked to the evolution of state administration (at the structural and political levels) Where attempts at successive (and not necessarily different) reorientations of this policy, the intervention of actors with different interests and logics that do not necessarily bring about a redefinition of the communication policy (at least not in its most visible part ), The importance of the mobilization of quantitative tools, reactivated by the finance laws as well as the imperatives at European level.

L'observation directe des exoplanètes est rendue difficile par l'énorme contraste entre la planète et l'étoile autour de laquelle elle gravite, ainsi que la faible séparation angulaire entre ces deux corps. Un tel niveau de contraste aussi proche de l'étoile être atteint en couplant l'imagerie à haute résolution angulaire et la coronographie, qui atténue le flux en provenance de l'étoile ; les performances ultimes d'un instrument d'imagerie à haut contraste sont alors limitées par ses aberrations quasi-statique. Au cours de cette thèse a été conçu un ASO plan focal dédié à la calibration des aberrations quasi-statiques dans les systèmes d'imagerie à haut contraste. Cet ASO, baptisé COFFEE, permet d'estimer les aberrations en amont et en aval du coronographe à partir d'images coronographiques acquises en plan focal différant d'une phase de diversité connue introduite en amont du coronographe. Au cours de cette thèse, COFFEE a été conçu et validé par simulations numérique et démontré expérimentalement sur banc. L'identification de plusieurs facteurs limitant la précision de l'estimation des aberrations a ensuite induit une modification du formalisme sur lequel repose COFFEE pour l'adapter à l'estimation d'aberrations de hautes fréquences spatiales avec une précision nanométrique. Cette version hauts ordres de COFFEE a été utilisée avec succès sur l'instrument SPHERE, où la compensation des aberrations estimées par COFFEE a permis d'optimiser le contraste. Enfin, une nouvelle méthode de compensation a été développée pour permettre d'atteindre de très hauts niveaux de contraste sur le détecteur scientifique. / Performing an exoplanet direct detection means being able to image an object as faint as an extra-solar planet very close to its parent star. After compensation of the turbulence by the XAO loop and most of the star light removed by a coronagraph, the ultimate limitation of high contrast imaging systems lies in its quasi-static aberrations that creates a residual signal which limit the achievable contrast on the scientific detector. To increase the achievable contrast on the detector, these aberrations must be compensated for, ideally using focal plane data recorded from the scientific detector to avoid differential aberrations. The aim of this thesis was to develop a focal-plane wavefront sensor (WFS) dedicated to the estimation of quasi-static aberrations in high contrast imaging systems. This WFS, called COFFEE, estimates the aberrations both upstream and downstream of the coronagraph using coronagraphic focal plane images that differ from a known diversity aberrations introduced upstream of the coronagraph. During this research work, COFFEE has been developed, tested using numerical simulations and demonstrated on an in-house bench. Considering the limitations of the estimation accuracy, COFFEE's formalism has then been modified to allow it to estimate high frequencies aberrations with nanometric precision. This extended version of COFFEE has been successfully used on SPHERE to optimize the contrast on the scientific detector of the instrument using COFFEE in a dedicated compensation process. Lastly, a new compensation method has been developed in order to reach very high contrast levels on the scientific detector.

Dans cette thèse, nous étudions le problème inverse du phénomène de couplage des ondes électromagnétiques (EM) et sismiques. Les équations différentielles partielles régissant le phénomène de couplage sont composées d'équations de Maxwell et de Biot. Comme le phénomène de couplage est plutôt faible, nous ne considérons que la transformation des ondes électromagnétiques en ondes sismiques. Nous utilisons le modèle électrosismique pour se référer à cette transformation. Dans le modèle, le champ électrique devient la source des équations de Biot. Un coefficient de couplage est utilisé pour désigner l'efficacité de la transformation.Chapitre 2, nous considérons l'existence et l'unicité du problème vers l'avant dans le domaine fréquentiel et dans le domaine temporel. Dans le domaine fréquentiel, nous proposons l'espace de Sobolev approprié pour considérer le problème électrocinétique. Nous prouvons que la formule faible satisfait l'inégalité de Garding en utilisant la décomposition de Helmohltz. L'alternative de Fredholm peut être appliquée, ce qui montre que l'existence est équivalente à l'unicité. Dans le domaine temporel, la solution faible est définie et l'existence et l'unicité de la solution faible est démontrée.La stabilité du problème inverse est considérée dans le chapitre 3. Nous prouvons d'abord les estimations de Carleman pour les équations de Biot et les équations électrosismiques. Basé sur les estimations de Carleman pour les équations électrosismiques, nous prouvons une stabilité de Holder pour inverser tous les paramètres dans l'équation de Maxwell et le coefficient de couplage. Pour simplifier le problème, nous utilisons des équations électrostatiques pour remplacer les équations de Maxwell. Le problème inverse est décomposé en deux étapes: le problème de source inverse pour les équations de Biot et le problème de paramètre inverse pour l'équation électrostatique. Nous pouvons prouver la stabilité du problème de source inverse pour les équations de Biot sur la base de l'estimation de Carleman pour les équations de Biot. Ensuite, la conductivité et le coefficient de couplage peuvent être reconstitués avec les informations de la première étape.Dans le chapitre 4, nous résolvons les équations électrosismiques numériquement. L'équation électrostatique est résolue par la boîte à outils Matlabe PDE. Les équations de Biot sont résolues avec une méthode de différences finies échelonnées. Pour diminuer la consommation de calcul, nous ne traitons que du problème bidimensionnel. Pour simuler des ondes se propageant dans un domaine non borné, nous utilisons le PML pour absorber les ondes atteignant la limite de coupure.Le chapitre 5 traite du problème de source inverse numérique pour les équations de Biot. La méthode que nous allons utiliser est une variante de la méthode d'inversion temporelle. La première étape de la méthode consiste à transformer le problème source en un problème de valeur initiale sans aucune source. Ensuite, l'application de la méthode d'inversion de temps récupère la valeur initiale. Des exemples numériques démontrent que cette méthode fonctionne bien même pour les équations de Biot avec un petit terme d'amortissement. Mais si le terme d'amortissement est trop grand, le processus inverse n'est pas symétrique avec le processus en avant et les résultats de la reconstruction dégénèrent. / In this thesis, we study the inverse problem of the coupling phenomenon of electromagnetic (EM) and seismic waves. Partial differential equations governing the coupling phenomenon are composed of Maxwell and Biot equations. Since the coupling phenomenon is rather weak, in low frequency we only consider the transformation from EM waves to seismic waves. We use electroseismic model to refer to this transformation. In the model, the electric field becomes the source of Biot equations. A coupling coefficient is used to denote the efficiency of the transformation.Chapter 2, we consider the existence and uniqueness of the forward problem in both frequency domain and time domain. In the frequency domain, we propose the suitable Sobolev space to consider the electrokinetic problem. We prove that the weak formula satisfies a Garding's inequality using Helmohltz decomposition. The Fredholm alternative can be applied, which shows that the existence is equivalent to the uniqueness. In the time domain, the weak solution is defined and the existence and uniqueness of the weak solution is proved.The stability of the inverse problem is considered in Chapter 3. We first prove Carleman estimates for both Biot equations and electroseismic equations. Based on the Carleman estimates for electroseismic equations, we prove a Holder stability to inverse all the parameters in Maxwell equation and the coupling coefficient. To simply the problem, we use electrostatic equations to replace Maxwell equations. The inverse problem is decomposed into two steps: the inverse source problem for Biot equations and the inverse parameter problem for the electrostatic equation. We can prove the stability of the inverse source problem for Biot equations based on the Carleman estimate for Biot equations. Then the conductivity and the coupling coefficient can be reconstructed with the information from the first step.In Chapter 4, we solve the electroseismic equations numerically. The electrostatic equation is solved by the Matlabe PDE toolbox. Biot equations are solved with a staggered finite difference method. To decrease the computation consumption, we only deal with the two dimensional problem. To simulate waves propagating in unbounded domain, we use PML to absorb waves reaching the cut-off boundary.Chapter 5 deals with the numerical inverse source problem for Biot equations. The method we are going to use is a variant of the time reversal method. The first step of the method is to transform the source problem into an initial value problem without any source. Then the application of the time reversal method recovers the initial value. Numerical examples demonstrate that this method works well even for Biot equations with a small damping term. But if the damping term is too large, the inverse process is not symmetric with the forward process and the reconstruction results degenerate.

Les travaux de recherche présentés dans cette thèse se situent dans une problématique d’aide à la conception d’enveloppes isolantes pour la rénovation thermique de bâtiments résidentiels collectifs. Ces enveloppes isolantes sont composées de panneaux multifonctionnels rectangulaires, configurables et préfabriqués en usine. Leur conception repose sur les cinq caractéristiques suivantes. Premièrement, le nombre de panneaux nécessaires pour concevoir une enveloppe ainsi que leur taille respective ne sont pas
 connus au début de la rénovation (mais leur taille est cependant bornée). Deuxièmement, en raison des contraintes de fabrication, chaque fenêtre et chaque porte présentes sur la façade à rénover doivent être insérées dans un et un seul panneau. Troisièmement, les panneaux sont fixés à des endroits spécifiques de la façade, assez résistants pour supporter leur poids, nommés zones d’accroche. Quatrièmement, ni trous (zone non couverte), ni chevauchements entre panneaux ne sont autorisés. Cinquièmement, afin de garantir une isolation thermique performante tout en minimisant son coût, les enveloppes doivent être
 composées d’un nombre minimal de panneaux. Aux vues de la complexité de ce problème, nous restreignons nos travaux de recherche aux façades rectangulaires portant des menuiseries et des zones d’accroche rectangulaires. Compte tenu des cinq caractéristiques énoncées et de l’hypothèse de forme rectangulaire des éléments traités (panneaux, façades, menuiseries, zones d’accroche), la conception des enveloppes est à la fois un problème de découpe et de conditionnement à deux dimensions et un problème de configuration. Ce problème est formalisé et traité comme un problème de satisfaction de contraintes et a pour but d’aider la conception dédites enveloppes isolantes. En tant que tel, les travaux de cette thèse présentent deux contributions majeures. En raison des caractéristiques originales du problème de calepinage de façades, sa description et sa formalisation comme un problème de satisfaction de contraintes constituent la première contribution de ces travaux de thèse. Deuxièmement, les solutions algorithmiques basées sur les contraintes constituent notre seconde contribution. En particulier, ces travaux de thèse présentent deux solutions manuelles et trois automatiques pour le problème de conception d’enveloppes isolantes. / The research presented in this thesis falls within the problem of supporting the design of thermal insulating envelopes for the renovation of collective residential buildings. These insulating envelopes are composed of rectangular multi-functional panels, configurable and prefabricated in the factory. Their design is based on the following five characteristics. First, the number of panels needed to design an envelope and their size are not known at the beginning of the renovation (but their size is however bounded). Second, because of manufacturing constraints, every window and every door present on the facade to be renovated must be inserted into one and only one panel. Third, panels are attached to specific areas of the facade strong enough to support their weight, called supporting areas. Fourth, neither holes (uncovered area) or overlapping between panels are allowed. Fifth, to ensure efficient thermal insulation while minimizing cost, envelopes should be composed of a minimum number of panels. In view of the complexity of this problem, we restrict our research to rectangular facades with rectangular joinery and supporting areas. Given the five stated characteristics and the assumption of rectangular elements (panels, facades, 
joinery, supporting areas), the envelopes design is both a two-dimensional Cutting & Packing problem as well as a configuration one. This problem is formalized and treated as a constraint satisfaction problem and aims to support the design of such insulating structures. As such, the thesis presents two major contributions. Given the original features of the building renovation problem, its description and its formalization as a constraint satisfaction problem are the first contribution of the work. Second, constraint-based algorithmic solution’s are our second contribution. In particular, the thesis presents two manual and three automatic solutions for the design problem of insulating envelopes.

Nous étudions dans ce mémoire les propriétés des ensembles de pavages engendrés par des jeux de tuiles de Wang exhibant une ou plusieurs directions de déterminisme local, en accordant une importance toute particulière aux jeux déterministes dans les quatre directions diagonales simultanément, dits 4-way déterministes. Après avoir proposé une construction alternative d’un jeu de tuiles apériodique 4-way déterministe, nous étudions plusieurs problèmes de décision sur ces objets et complétons en particulier le résultat d’indécidabilité du problème du pavage dans le cadre 4-way déterministe établi par Lukkarila en montrant l’indécidabilité du problème du pavage périodique 4-way déterministe. Nous montrons également que des familles complexes de coloriages du plan telles que celles engendrées par les substitutions restent sofiques dans un cadre 4-way déterministe. Nous proposons une bi-déterminisation des constructions de jeux de tuiles point-fixe de Durand, Romashchenko et Shen et en tirons quelques premières applications. Enfin, nous considérons l’opportunité d’élargir le rayon de la règle locale de déterminisme afin de limiter les directions d’expansivité et ainsi de permettre la construction localement déterministe de systèmes de particules et collisions non triviaux. Nous introduisons un nouveau modèle syntaxique commode afin de travailler à rayon deux et revisitons des problématiques de Lukkarila dans ce cadre. / In this thesis, we study some properties of the sets of tilings generated by Wang tilesets that exhibit one or more directions of local determinism, focusing in particular on tilesets that are simultaneously deterministic in the four diagonal directions, referred to as 4-way deterministic. After having exposed an alternative construction of a 4-way deterministic aperiodic tileset, we study several decision problems on these objects and complete in particular Lukkarila’s result of undecidability of the Domino Problem in the 4-way deterministic setting proving the undecidability of the 4-way deterministic periodic Domino Problem. We also prove that some complex families of colorings of the plane such that those generated by substitutions remain sofic in the 4-way deterministic setting. We propose a bi-determinization of the constructions by Durand, Romashchenko and Shen of fixed-point tilesets and give some first applications. Finally, we investigate the idea of extending the radius of the local rule of determinism in order to reduce the set of directions of expansiveness and thus allow the local realization of non-trivial particles and collisions systems. We introduce a new and convenient syntactic model to deal with radius two and revisit some of Lukkarila’s problems in this setting.

Le cadre général de cette thèse est l'étude des polynômes comme objets de modèles de calcul. Cette approche permet de définir de manière précise la complexité d'évaluation d'un polynôme, puis de classifier des familles de polynômes en fonction de leur difficulté dans ce modèle. Dans cette thèse, nous nous intéressons en particulier au modèle AffPow des sommes de puissance de forme linéaire, i.e. les polynômes qui s'écrivent $f = \sum_{i = 1}^s \alpha_i \ell_i^{e_i}$, avec $\deg \ell_i = 1$. Ce modèle semble assez naturel car il étend à la fois le modèle de Waring $f = \sum \alpha_i \ell_i^d$ et le modèle du décalage creux $f = \sum \alpha_i \ell^{e_i}$, mais peu de résultats sont connus pour cette généralisation.Nous avons pu prouver des résultats structurels pour la version univarié de ce modèle, qui nous ont ensuite permis d'obtenir des bornes inférieures et des algorithmes de reconstruction, qui répondent au problème suivant : étant donné $f = \sum \alpha_i (x-a_i)^{e_i}$ par la liste de ses coefficients, retrouver les $\alpha_i, a_i, e_i$ qui apparaissent dans la décomposition optimale de $f$.Nous avons aussi étudié plus en détails la version multivarié du modèle, qui avait été laissé ouverte par nos précédents algorithmes de reconstruction, et avons obtenu plusieurs résultats lorsque le nombre de termes dans une expression optimale est relativement petit devant le nombre de variables ou devant le degré du polynôme. / The general framework of this thesis is the study of polynomials as objects of models of computation. This approach allows to define precisely the evaluation complexity of a polynomial, and then to classify families of polynomials depending on their complexity. In this thesis, we focus on the study of the model of sums of affine powers, that is polynomials that can be written as $f = \sum_{i = 1}^s \alpha_i \ell_i^{e_i}$, with $\deg \ell_i = 1$.This model is quite natural, as it extends both the Waring model $f = \sum \alpha_i \ell_i^d$ , and the sparsest shift model $f = \sum \alpha_i \ell^{e_i}$, but it is still not well known.In this work, we obtained structural results for the univariate variant of this model, which allow us to obtain lower bounds and reconstruction algorithms, that solve the following problem : given $f = \sum \alpha_i (x-a_i)^{e_i}$ as a list of its coefficient, find the values of the $\alpha_i$’s, $e_i$’s and $a_i$’s in the optimal decomposition of $f$.We also studied the multivariate case and obtained several reconstruction algorithms that work whenever the number of terms in the optimal expression is small in terms of the number of variable or the degree of the polynomial.

Une donnée peut avoir diverses formes et peut provenir d'un large panel d'applications. Habituellement, une donnée possède beaucoup de bruit et peut être soumise aux effets du hasard. Les récents progrès en apprentissage automatique ont relancé les recherches théoriques sur les limites des différentes méthodes probabilistes de traitement du signal. Dans cette thèse, nous nous intéressons aux questions suivantes : quelle est la meilleure performance possible atteignable ? Et comment peut-elle être atteinte, i.e., quelle est la stratégie algorithmique optimale ?La réponse dépend de la forme des données. Les sujets traités dans cette thèse peuvent tous être représentés par des modèles graphiques. Les propriétés des données déterminent la structure intrinsèque du modèle graphique correspondant. Les structures considérées ici sont soit éparses, soit denses. Les questions précédentes peuvent être étudiées dans un cadre probabiliste, qui permet d'apporter des réponses typiques. Un tel cadre est naturel en physique statistique et crée une analogie formelle avec la physique des systèmes désordonnés. En retour, cela permet l'utilisation d'outils spécifiques à ce domaine et de résoudre des problèmes de satisfaction de contraintes et d'inférence statistique. La problématique de performance optimale est directement reliée à la structure des extrema de la fonction d'énergie libre macroscopique, tandis que les aspects algorithmiques proviennent eux de la minimisation de la fonction d'énergie libre microscopique (c'est-à-dire, dans la forme de Bethe).Cette thèse est divisée en quatre parties. Premièrement, nous aborderons par une approche de physique statistique le problème de la coloration de graphes aléatoires et mettrons en évidence un certain nombre de caractéristiques. Dans un second temps, nous calculerons une nouvelle limite supérieure de la taille de l'ensemble contagieux. Troisièmement, nous calculerons le diagramme de phase du modèle de Dawid et Skene dans la région dense en modélisant le problème par une factorisation matricielle de petit rang. Enfin, nous calculerons l'erreur optimale de Bayes pour une classe restreinte de l'estimation matricielle de rang élevé. / Datasets come in a variety of forms and from a broad range of different applications. Typically, the observed data is noisy or in some other way subject to randomness. The recent developments in machine learning have revived the need for exact theoretical limits of probabilistic methods that recover information from noisy data. In this thesis we are concerned with the following two questions: what is the asymptotically best achievable performance? And how can this performance be achieved, i.e., what is the optimal algorithmic strategy? The answer depends on the properties of the data. The problems in this thesis can all be represented as probabilistic graphical models. The generative process of the data determines the structure of the underlying graphical model. The structures considered here are either sparse random graphs or dense (fully connected) models. The above questions can be studied in a probabilistic framework, which leads to an average (or typical) case answer. Such a probabilistic formulation is natural to statistical physics and leads to a formal analogy with problems in disordered systems. In turn, this permits to harvest the methods developed in the study of disordered systems, to attack constraint satisfaction and statistical inference problems. The formal analogy can be exploited as follows. The optimal performance analysis is directly related to the structure of the extrema of the macroscopic free energy. The algorithmic aspects follow from the minimization of the microscopic free energy (that is, the Bethe free energy in this work) which is closely related to message passing algorithms. This thesis is divided into four contributions. First, a statistical physics investigation of the circular coloring problem is carried out that reveals several distinct features. Second, new rigorous upper bounds on the size of minimal contagious sets in random graphs, with bounded maximum degree, are obtained. Third, the phase diagram of the dense Dawid-Skene model is derived by mapping the problem onto low-rank matrix factorization. The associated approximate message passing algorithm is evaluated on real-world data. Finally, the Bayes optimal denoising mean square error is derived for a restricted class of extensive rank matrix estimation problems.