Texte remanié de: Diss.--Philosophische Fakultät II--Universität Erlangen-Nürnberg, 1993. / Bibliogr. p. 275-298. Index.

Dans cette thèse nous étudions trois jeux à objectif compétitif sur les graphes. Les jeux à objectif compétitif proposent une approche dynamique des problèmes d'optimisation discrètes. L'idée générale consiste à associer à un problème d'optimisation (coloration, domination, etc.) un jeu combinatoire partisan de la façon suivante. Deux joueurs construisent tour à tour la structure reliée au problème d'optimisation. L'un d'eux cherche à ce que cette structure soit le plus optimale possible, tandis que l'autre essaye de l'en empêcher. Sous l'hypothèse que les deux joueurs jouent optimalement, la taille de la structure obtenue définit un invariant ludique.Nous commençons par étudier une variante 1-impropre du jeu de coloration, qui est le premier et le plus étudié des jeux à objectif compétitif. Dans ce jeu, les joueurs colorient les sommets d'un graphe de sorte que deux sommets adjacents ne partagent jamais la même couleur. Dans la version 1-impropre, un sommet peut avoir au plus un voisin ayant la même couleur que lui. Nous considérons ensuite le jeu de domination, dans lequel les deux joueurs doivent construire un ensemble dominant, c'est-à-dire un ensemble de sommets du graphe tel que tout autre sommet est adjacent à l'un des membres de cet ensemble. Finalement, nous définissons un nouveau jeu à objectif compétitif, relié au problème de coloration distinguante. Dans ce jeu, il s'agit de construire une coloration qui n'est invariante par aucun des automorphismes du graphe. Nous soulevons plusieurs interrogations stimulantes concernant ce nouveau jeu, notamment sur la caractérisation des graphes ayant un invariant ludique infini, par l'existence d'automorphismes d'ordre deux. / In this thesis, we study three competitive optimization graph games. These games allow a dynamic approach to discrete optimization problems, which is an advantageous alternative way to consider these questions. The global idea consists in defining a combinatorial partisan game, associated to the original optimization problem, like coloring, domination, etc. Two players alternatively build the structure related to the optimization problem. One of them tries to obtain a structure as optimal as possible, whereas his opponent wants to prevent him from doing it. Under the hypothesis that both players play optimally, the size of the obtained structure defines a game invariant of the graph.We start by studying a 1-improper variation of the coloring game, which is the first and the most studied competitive optimization graph game. In this game, the players colors the vertices of a graph, such that two adjacent vertices do not share the same color. In the 1-improper version, we allow a vertex to have at most one neighbor with the same color as it. Then, we study the domination game, in which the players have to build a domination set, that is a sub-set of vertices such that any other vertex is adjacent to one of the vertex in this set. Finally, we define a new game, related to the distinguishing coloring problem. This game is about building a vertex-coloring which is preserved by none of the graph automorphisms. We raise some challenging open questions about this new game, especially concerning the characterization of graphs with infinite game invariant, by the existence of order two automorphisms.

Le Théorème des Quatre Couleurs, conjecturé en 1852 et prouvé en 1976, est à l'origine de l'étude des partitions des sommets de graphes peu denses. Il affirme que toute carte plane peut être coloriée avec au plus quatre couleurs différentes, de telle manière que deux régions qui partagent une frontière aient des couleurs différentes. Énoncé en terme de théorie des graphes, cela veut dire que tout graphe planaire, c'est à dire tout graphe qui peut être représenté dans le plan sans que deux arêtes ne se croisent, peut voir son ensemble de sommets partitionné en quatre ensembles tels que chacun de ces ensembles ne contient pas les deux extrémités d'une même arête. Une telle partition est appelée une coloration propre en quatre couleurs. Dans cette thèse, on s'intéresse à l'étude de la structure des graphes peu denses, selon différentes notions de densité. D'une part, on étudie les graphes planaires sans petits cycles, et d'autre part les graphes dont tous les sous-graphes ont un degré moyen peu élevé. Pour ces classes de graphes, on recherche tout d'abord le plus petit nombre de sommets à retirer pour obtenir une forêt, c'est à dire un graphe sans cycles. Cela peut être vu comme une partition des sommets du graphe en un ensemble induisant une forêt et un ensemble de sommets contenant au plus une fraction donnée des sommets du graphe. La motivation première de cette étude est une conjecture d'Albertson et Berman (1976) comme quoi tout graphe planaire admettrait une telle partition où la forêt contient au moins la moitié des sommets du graphe. Dans un second temps, on s'intéresse aux partitions des sommets de ces graphes en deux ensembles, tels que les sous-graphes induits par ces deux ensembles ont des propriétés particulières. Par exemple, ces sous-graphes peuvent être des graphes sans arêtes, des forêts, des graphes de degré borné, ou des graphes dont les composantes connexes ont un nombre borné de sommets. Ces partitions des sommets sont des extensions de la notion de coloration propre de graphe.On montre, pour différentes classes de graphes peu denses, que tous les graphes de ces classes admettent de telles partitions. On s'intéresse également aux aspect algorithmiques de la construction de telles partitions. / The study of vertex partitions of planar graphs was initiated by the Four Colour Theorem, which was conjectured in 1852, and proven in 1976. According to that theorem, one can colour the regions of any planar map by using only four colours, in such a way that any two regions sharing a border have distinct colours. In terms of graph theory, it can be reformulated this way: the vertex set of every planar graph, i.e. every graph that can be represented in the plane such that edges do not cross, can be partitioned into four sets such that no edge has its two endpoints in the same set. Such a partition is called a proper colouring of the graph.In this thesis, we look into the structure of sparse graphs, according to several notions of sparsity. On the one hand, we consider planar graphs with no small cycles, and on the other hand, we consider the graphs where every subgraph has bounded average degree.For these classes of graphs, we first look for the smallest number of vertices that can be removed such that the remaining graph is a forest, that is a graph with no cycles. That can be seen as a partition of the vertices of the graph into a set inducing a forest and a set with a bounded fraction of the vertices of the graph. The main motivation for this study is a the Albertson and Berman Conjecture (1976), which states that every planar graph admits an induced forest containing at least one half of its vertices.We also look into vertex partition of sparse graphs into two sets both inducing a subgraph with some specific prescribed properties. Exemples of such properties can be that they have no edges, or no cycles, that they have bounded degree, or that they have bounded components. These vertex partitions generalise the notion of proper colouring. We show, for different classes of sparse graphs, that every graph in those classes have some specific vertex partition. We also look into algorithmic aspects of these partitions.

L’une des grandes applications de la statistique est la validation et la comparaison de modèles probabilistes au vu des données. Cette branche des statistiques a été développée depuis la formalisation de la fin du 19ième siècle par des pionniers comme Gosset, Pearson et Fisher. Dans le cas particulier de l’approche bayésienne, la solution à la comparaison de modèles est le facteur de Bayes, rapport des vraisemblances marginales, quelque soit le modèle évalué. Cette solution est obtenue par un raisonnement mathématique fondé sur une fonction de coût.Ce facteur de Bayes pose cependant problème et ce pour deux raisons. D’une part, le facteur de Bayes est très peu utilisé du fait d’une forte dépendance à la loi a priori (ou de manière équivalente du fait d’une absence de calibration absolue). Néanmoins la sélection d’une loi a priori a un rôle vital dans la statistique bayésienne et par conséquent l’une des difficultés avec la version traditionnelle de l’approche bayésienne est la discontinuité de l’utilisation des lois a priori impropres car ils ne sont pas justifiées dans la plupart des situations de test. La première partie de cette thèse traite d’un examen général sur les lois a priori non informatives, de leurs caractéristiques et montre la stabilité globale des distributions a posteriori en réévaluant les exemples de [Seaman III 2012]. Le second problème, indépendant, est que le facteur de Bayes est difficile à calculer à l’exception des cas les plus simples (lois conjuguées). Une branche des statistiques computationnelles s’est donc attachée à résoudre ce problème, avec des solutions empruntant à la physique statistique comme la méthode du path sampling de [Gelman 1998] et à la théorie du signal. Les solutions existantes ne sont cependant pas universelles et une réévaluation de ces méthodes suivie du développement de méthodes alternatives constitue une partie de la thèse. Nous considérons donc un nouveau paradigme pour les tests bayésiens d’hypothèses et la comparaison de modèles bayésiens en définissant une alternative à la construction traditionnelle de probabilités a posteriori qu’une hypothèse est vraie ou que les données proviennent d’un modèle spécifique. Cette méthode se fonde sur l’examen des modèles en compétition en tant que composants d’un modèle de mélange. En remplaçant le problème de test original avec une estimation qui se concentre sur le poids de probabilité d’un modèle donné dans un modèle de mélange, nous analysons la sensibilité sur la distribution a posteriori conséquente des poids pour divers modélisation préalables sur les poids et soulignons qu’un intérêt important de l’utilisation de cette perspective est que les lois a priori impropres génériques sont acceptables, tout en ne mettant pas en péril la convergence. Pour cela, les méthodes MCMC comme l’algorithme de Metropolis-Hastings et l’échantillonneur de Gibbs et des approximations de la probabilité par des méthodes empiriques sont utilisées. Une autre caractéristique de cette variante facilement mise en œuvre est que les vitesses de convergence de la partie postérieure de la moyenne du poids et de probabilité a posteriori correspondant sont assez similaires à la solution bayésienne classique / One of the major applications of statistics is the validation and comparing probabilistic models given the data. This branch statistics has been developed since the formalization of the late 19th century by pioneers like Gosset, Pearson and Fisher. In the special case of the Bayesian approach, the comparison solution of models is the Bayes factor, ratio of marginal likelihoods, whatever the estimated model. This solution is obtained by a mathematical reasoning based on a loss function. Despite a frequent use of Bayes factor and its equivalent, the posterior probability of models, by the Bayesian community, it is however problematic in some cases. First, this rule is highly dependent on the prior modeling even with large datasets and as the selection of a prior density has a vital role in Bayesian statistics, one of difficulties with the traditional handling of Bayesian tests is a discontinuity in the use of improper priors since they are not justified in most testing situations. The first part of this thesis deals with a general review on non-informative priors, their features and demonstrating the overall stability of posterior distributions by reassessing examples of [Seaman III 2012].Beside that, Bayes factors are difficult to calculate except in the simplest cases (conjugate distributions). A branch of computational statistics has therefore emerged to resolve this problem with solutions borrowing from statistical physics as the path sampling method of [Gelman 1998] and from signal processing. The existing solutions are not, however, universal and a reassessment of the methods followed by alternative methods is a part of the thesis. We therefore consider a novel paradigm for Bayesian testing of hypotheses and Bayesian model comparison. The idea is to define an alternative to the traditional construction of posterior probabilities that a given hypothesis is true or that the data originates from a specific model which is based on considering the models under comparison as components of a mixture model. By replacing the original testing problem with an estimation version that focus on the probability weight of a given model within a mixture model, we analyze the sensitivity on the resulting posterior distribution of the weights for various prior modelings on the weights and stress that a major appeal in using this novel perspective is that generic improper priors are acceptable, while not putting convergence in jeopardy. MCMC methods like Metropolis-Hastings algorithm and the Gibbs sampler are used. From a computational viewpoint, another feature of this easily implemented alternative to the classical Bayesian solution is that the speeds of convergence of the posterior mean of the weight and of the corresponding posterior probability are quite similar.In the last part of the thesis we construct a reference Bayesian analysis of mixtures of Gaussian distributions by creating a new parameterization centered on the mean and variance of those models itself. This enables us to develop a genuine non-informative prior for Gaussian mixtures with an arbitrary number of components. We demonstrate that the posterior distribution associated with this prior is almost surely proper and provide MCMC implementations that exhibit the expected component exchangeability. The analyses are based on MCMC methods as the Metropolis-within-Gibbs algorithm, adaptive MCMC and the Parallel tempering algorithm. This part of the thesis is followed by the description of R package named Ultimixt which implements a generic reference Bayesian analysis of unidimensional mixtures of Gaussian distributions obtained by a location-scale parameterization of the model. This package can be applied to produce a Bayesian analysis of Gaussian mixtures with an arbitrary number of components, with no need to specify the prior distribution.

Nous avons développé et mis à l’épreuve des activités utilisant un registre basé sur des diagrammes lors de l’enseignement de la théorie de la relativité restreinte avec des élèves de terminale S. L’approche graphique est source de difficultés didactiques mais les potentialités didactiques peuvent être plus avantageuses. Une étude épistémologique sur les diagrammes utilisables en relativité restreinte permet de voir les liens importants entre les mathématiques et la genèse de la théorie. C’est le cas du diagramme de Minkowski. Nous avons également étudié les diagrammes de Brehme et de Loedel, créés beaucoup plus tard pour des raisons didactiques. Après les séances pilotes, nous avons développé un nouveau cadre théorique, permettant d’analyser plus finement les interactions développées par les élèves résolvant un problème utilisant des diagrammes en relativité restreinte. Nous avons modifié les espaces de travail mathématique (ETM) en rajoutant le cadre de rationalité de la physique à celui des mathématiques. Le cadre des ETM étendu nous a permis de concevoir plusieurs versions de séquences et de réaliser une analyse a priori de leur niveau de difficulté et a posteriori en étudiant des travaux d’élèves. L’analyse du travail de groupes d’élèves a été effectuée lors d’une séquence utilisant le diagramme de Minkowski avec GeoGebra, un logiciel de simulation graphique. Le degré de maitrise du diagramme de Minkowski a été évalué pour chaque élève du point de vue des mathématiques et de la physique. Les résultats sont prometteurs, ils montrent une appropriation réelle des concepts de la théorie de la relativité restreinte via une approche utilisant des diagrammes. / We tried to develop and test several activities using a register based on diagrams for teaching the special theory of relativity to S class of twelfth graders. The graphic approach may result it complications in learning. However, its educational potential can turn out to be more beneficial. An epistemological study on diagrams used in special relativity allowed us to report important links between mathematics and the genesis of the special theory of relativity. This is the case of the Minkowski diagram. We were also interested in two other diagrams, Brehme and Loedel, which were developed much more later for teaching purposes. Following experimental sessions, we developed a new theoretical frame to comprehensively analyse the interactions developed by students to solve a problem using diagrams in special relativity. We modified the mathematical working spaces (MWS) by adding a new frame of rationality to the existing mathematic workspace to physics. The extended frame of the MWS allowed us to plan several versions of sequences proposed to the students and realize a priori analysis of their difficulty level and a posteriori study by analysing pupils' works. We have considered several works of student groups during a sequence using the Minkowski diagram with GeoGebra, a graphic simulation software. It allowed us to estimate the degree of control of the Minkowski diagram for every student, both from the frame of rationality of the mathematics and the physical sciences’ point of view. The results are promising and they tend to show a real appropriation of the concepts of the special theory of relativity with an approach using diagrams.

Ce travail porte sur la synthèse et la caractérisation de nouveaux matériaux multiferroïques basés sur le concept très récent de la Ferroélectricité Hybride Impropre.Deux classes de matériaux ont été envisagées : les oxydes de type Ruddlesden-Popper NaRMO4 (R=Y, La; M= Mn, Cr) et les doubles pérovskites ordonnées NaLnCoWO6 (Ln= Y, La, Pr, Nd, Sm, Eu, Gd, Tb, Dy, Ho, Er, and Yb). Les essais de synthèse sur la première classe n’ont pas permis d’obtenir les composés visés. Pour la seconde classe, l’ensemble des composés ont pu être obtenus par synthèse par voie solide à haute température. Les composés NaLnCoWO6 (Ln=La, Pr, Nd) ont été synthétisés à pression ambiante. L’usage des techniques de Hautes Pressions – Hautes Températures (HP-HT) a permis de stabiliser les composés contenant des terres rares plus petites et d’obtenir ainsi neuf nouveaux composés aux propriétés inédites.L’utilisation combinée de la diffraction sur poudre des rayons X au synchrotron et des neutrons a permis une étude structurale fine de la famille des doubles pérovskites ordonnées NaLnCoWO6. Les groupes d’espace ont été déterminés grâce aux affinements Rietveld des diffractogrammes de Rayons X sur poudre haute résolution. Les composés NaLnCoWO6 (Ln=La, Pr, Nd) cristallisent dans le groupe d’espace centrosymétrique C2/m tandis que les 9 nouveaux composés (Ln= Y, Sm, Eu, Gd, Tb, Dy, Ho, Er, and Yb) cristallisent dans le groupe d’espace polaire P21. Des mesures de génération de seconde harmonique confirment la structure non-centrosymétrique des nouveaux composés. L’analyse adaptée des modes de symétrie des composés cristallisant dans la structure polaire montre que l’amplitude du mode polaire induit augmente avec la diminution de la taille du cation Ln3+. La polarisation estimée à partir des affinements de la structure pourrait atteindre jusqu’à ~20µC/cm2.Une transition de phase présentant une très large hystérésis en température (~150K) a été observée par diffraction des neutrons pour le composé NaLaCoWO6. De plus, les images obtenues en Microscopie Electronique en Transmission révèlent la présence de bandes dans la phase haute température. Cette superstructure présente une périodicité de 12ap selon la direction [100]p ou [010]p . On a pu montrer à l’aide d’observations en STEM (microscopie à balayage en transmission) combinées avec des mesures en EELS (spectroscopie de pertes d’énergie des électrons) que ce contraste de bandes n’est pas lié à une variation de composition mais bien à une variation structurale. Différents modèles de rotations des octaèdres d’oxygènes ont été élaborés pour valider les données expérimentales obtenues par diffraction des rayons X et de neutrons. Le schéma de rotation qui décrit au mieux les données est a-a-c0. Concernant la phase basse température le groupe d’espace attribué est le groupe polaire P21.Les caractérisations magnétiques ont été réalisées pour toutes ces phases. Tous les composés NaLnCoWO6 s’ordonnent dans une configuration antiferromagnétique. Les températures de Néel varient entre 4 et 13K en fonction de la nature de la terre-rare. Les moments effectifs déterminés par la loi de Curie-Weiss sont en accord avec les moments théoriques attendus. Toutes les températures de Weiss sont négatives traduisant le fait que les interactions antiferromagnétiques sont prépondérantes dans ces systèmes. Les structures magnétiques ont été déterminées pour les composés Ln= Y, La, Tb, and Ho. Pour ces mêmes composés, des mesures diélectriques en fonction de la température et du champ magnétique ont permis de mettre en évidence un couplage magnéto-diélectrique conséquent pour Ln=Y and Ho. Les mesures de courant pyroélectrique autour de la transition magnétique montrent qu’il existe une polarisation induite par l’ordre magnétique dans le composé NaYCoWO6.. C’est la première mise en évidence expérimentale d’un couplage magnéto-électrique dans la famille des doubles pérovskites ordonnées AA’BB’O6. / In this study, new magneto-electric materials were synthesized on the basis of the very recently recognized ferroelectric inducing mechanism, hybrid improper ferroelectricity, and structural and physical properties characterizations were carried out on these new phases.Two classes of materials were focused on: the Ruddlesden-Popper oxides NaRMO4 (R=Y, La; M= Mn, Cr) and the doubly ordered perovskites NaLnCoWO6 (Ln= Y, La, Pr, Nd, Sm, Eu, Gd, Tb, Dy, Ho, Er, and Yb). Attempts to synthesize the former class failed to give the target phases. All compounds in the latter class were prepared successfully by solid-state reactions at high temperature, among which the compounds NaLnCoWO6 (Ln=La, Pr, Nd) were prepared at ambient pressure while the other nine compounds were synthesized at high pressure.The structural study of the doubly ordered perovskite family NaLnCoWO6 was performed by synchrotron X-ray powder diffraction (SXRPD) and neutron powder diffraction (NPD). Based on the Rietveld refinement of the SXRPD patterns, the space groups were assigned. NaLnCoWO6 (Ln=La, Pr, Nd) compounds crystallize in the centrosymmetric C2/m symmetry, whereas the other nine new compounds crystallize in the polar space group P21. Second harmonic generation measurements on powder confirmed the non-centrosymmetric structure of the new compounds. Symmetry mode analysis demonstrates that the amplitude of the induced polar mode increases with a decreasing Ln cation size. The amplitude of the polarization was estimated from the refined structures, and can be as large as ~20µC/cm2.A structural phase transition was observed by NPD in NaLaCoWO6 with a large temperature hysteresis of ~150K. In addition, stripes were observed on the high-resolution transmission electron microscopy (TEM) images in the high temperature phase. The periodicity of this superstructure is 12ap along either the [100]p or [010]p direction. Further investigations by scanning TEM and electron energy loss spectroscopy revealed that the contrast of the stripes is due to a structural modulation rather than a compositional variation. Octahedral tilt twinning models were built with different tilting schemes to fit the observed SXRPD and NPD patterns. The tilting scheme a-a-c0 describes successfully the data. The low temperature phase was unambiguously determined to possess the polar space group P21.Magnetic and electric properties were experimentally characterized. All NaLnCoWO6 compounds order antiferromagnetically below TN which is between 4 and 13K. Curie-Weill fits were performed for all compounds, yielding reasonable effective magnetic moments compared to the theoretical ones. Weiss temperatures were all determined to be negative further indicating that antiferromagnetic interactions are dominant in these systems. Magnetic structures were determined for four NaLnCoWO6 (Ln= Y, La, Tb, and Ho) compounds, of which two have non-magnetic Ln cations (Y and La) and two have magnetic ones (Tb and Ho). Magneto-dielectric coupling was experimentally observed in compounds NaLnCoWO6 (Ln=Y, Tb, Ho) by dielectric measurements as a function of temperature and magnetic field. Polarization was derived for the Y and Ho compounds from pyroelectric current measurement, however, only the NaYCoWO6 compound demonstrates a polar behavior which cannot be switched. This is the first evidence that electric polarization can be induced by the magnetic ordering in the AA’BB’O6 class materials.

Dans cette thèse, nous étudions divers problèmes dont l'objectif est de gérer la croissance d'internet plus efficacement. En effet celle-ci est très vive : 41% pour le pic en 2012. Afin de répondre aux défis posés par cette évolution aux divers acteurs du réseau, des protocoles de gestion et de communication plus intelligents sont nécessaires. Les protocoles de l'Internet furent conçus comme des protocoles point à point. Or, la part de la diffusion de média dans le trafic est prépondérante et en nette hausse, et des projections indiquent qu'en 2016 80-90% du trafic sera engendré par de la diffusion vidéo. Cette divergence entraîne des inefficacités, car des multiples copies d'un message transitent par un lien. Dans cette thèse, nous étudions comment remediér á cette inefficacité. Nos contributions sont organisées selon les couches et les phases de déploiement du réseau. Nous étudions le placement de caches lors de la conception du réseau. Ensuite, pour la gestion d'un réseau, nous regardons quand placer des appareils en veille, en utilisant un mécanisme de cache et en coopération avec des réseaux de distribution. Puis, au niveau de la couche application, nous étudions un problème de maintenance d'arbres équilibrés pour la diffusion de média. Enfin, nous analysons la probabilité de survie des données dans un système de sauvegarde distribuée. Notre travail se fonde à la fois sur des méthodes théoriques (Chaînes de Markov, Programmation Linéaire), mais aussi sur des outils empiriques tels que la simulation et l'expérimentation.