Cette HDR concerne l'ordonnancement en présence de divers communications

L'augmentation des cas de surpoids et d'obésité dans les pays développés n'épargne désormais plus les pays émergents qui sont de plus en plus touchés par ce phénomène. J'ai comparé dans cette étude, deux stratégies de prévention de l'obésité en milieu scolaire entre un pays du développé, la France, et un pays émergent, l'Inde. En effet l'Inde qui a amorcé sa transition nutritionnelle, connaît une augmentation des cas de surpoids et d'obésité infantiles. Les nombreuses recherches sur les déterminants de l'obésité mettent aujourd'hui en lumière sa nature multifactorielle. A la piste génétique qui était auparavant privilégiée, s'ajoutent de nombreuses autres hypothèses explicatives mettant en évidence des facteurs psychologiques, sociaux, économiques, épigénétiques, biologiques, alimentaires, liés au rythme de vie (énumération non exhaustive). La pluralité de ces facteurs de risque fait de l'obésité un phénomène qui peut être qualifié de complexe. Pour comprendre cette complexité, je me suis référée à la " méthode " proposée par Edgar Morin (1990) pour conceptualiser et analyser la complexité à travers plusieurs principes directeurs. Ces principes permettent d'orienter le raisonnement entre pensée complexe et pensée simplifiante. Je les ai appliqués à l'analyse des stratégies nutritionnelles en milieu scolaire. Mes résultats révèlent d'une part que le paradigme de complexité permet aux enseignants de développer une stratégie nutritionnelle adaptée à la nature complexe de l'obésité. D'autre part, la stigmatisation de l'obésité, si elle est nécessaire pour déclencher une réelle prise de conscience de l'intérêt de la prévention globale, doit être limitée pour ne pas devenir contre-productive. Ces résultats permettent d'ouvrir de nombreuses perspectives pour améliorer la stratégie nutritionnelle dans chaque contexte étudié (français et indien), tant dans le domaine de la recherche que dans celui de la formation des enseignants.

Soit un réseau comprenant des lignes de communication qui échouent indépendamment, dans lequel tous ou certains sites, appelés terminaux, doivent être capables de communiquer entre eux. Dans le modèle stochastique statique classique le réseau est représenté par un graphe probabiliste dont les arêtes sont présentes selon des probabilités connues. La mesure de fiabilité classique (CLR) est la probabilité que les terminaux appartiennent à la même composante connexe. Dans plusieurs contextes il est utile d'imposer la condition plus forte que la distance entre deux terminaux quelconques soit bornée supérieurement par un paramètre d. La probabilité que ça se produise est connue comme la fiabilité diamètre-bornée (DCR). Il s'agit d'une extension de la CLR. Les deux problèmes appartiennent à la classe NP-difficile de complexité; le calcul exact n'est possible que pour les instances de taille limitée ou topologies spécifiques. Dans cette thèse, nous contribuons des résultats concernant le problème du calcul et l'estimation de la DCR. Nous étudions la complexité de calcul de cas particuliers, paramétré par le nombre de terminaux, nœuds et le paramètre d. Nous passons en revue des méthodes pour le calcul exact et étudions des topologies particulières pour lesquelles le calcul de la DCR a une complexité polynomiale. Nous introduisons des résultats de base sur le comportement asymptotique de la DCR lorsque le réseau se développe comme un graphe aléatoire. Nous discutons sur l'impact de la contrainte de diamètre dans l'utilisation des techniques de Monte Carlo, et adaptons et testons une famille de méthodes basées sur le conditionnement de l'espace d'échantillonnage en utilisant des structures nommées d-pathsets et d-cutsets. Nous définissons une famille de mesures de performabilité qui généralise la DCR, développons une méthode de Monte Carlo pour l'estimer, et présentons des résultats expérimentaux sur la performance de ces techniques Monte Carlo par rapport é l'approche naïve. Finalement, nous proposons une nouvelle technique qui combine la simulation Monte Carlo et l'interpolation polynomiale pour les mesures de fiabilité.

Cette thèse porte sur la génération aléatoire uniforme des automates finis et l'analyse des algorithmes de minimisation qui s'y appliquent. La génération aléatoire permet de conduire une étude expérimentale sur les propriétésde l'objet engendré et sur les méthodes algorithmiques qui s'y appliquent. Il s'agit également d'un outil de recherche, qui permet de faciliter l'étude théorique du comportement moyen des algorithmes. L'analyse en moyenne des algorithmes s'inscrit dans la suite des travaux précurseurs de Donald Knuth. Le schéma classique en analyse d'algorithmes consiste à étudier le pire des cas, qui n'est souvent pas représentatif du comportement de l'algorithme en pratique. D'un point de vue théorique, on définit ce qui se produit "souvent'' en fixant une loi de probabilitésur les entrées de l'algorithme. L'analyse en moyenne consiste alors à estimer des ressources utiliséespour cette distribution de probabilité. Dans ce cadre, j'ai travaillé sur des algorithmes de génération aléatoire d'automatesdéterministes accessibles (complets ou non). Ces algorithmes sont basés sur de la combinatoirebijective, qui permet d'utiliser un procédé générique : les générateurs de Boltzmann. J'ai ensuite implanté ces méthodes dans deux logiciels : REGAL et PREGA. Je me suis intéressé à l'analyse en moyenne des algorithmes de minimisation d'automateset j'ai obtenu des résultats qui montrent le cas moyen des algorithmes de Moore et Hopcroft est bien meilleur que le pire des cas / This thesis is about the uniform random generation of finite automata and the analysisof their state minimization algorithms. Random generators allow to conduct an experimental study on the properties of the generated objectand on the algorithms that apply to this object. It is also a useful tool for research that facilitates the theoretical study of the average behavior of algorithms. Usually, the analysis of an algorithm focuses on the worst case scenario, which is often not representative of thepractical behavior of the algorithm. From a theoretical point of view, one can define what happens "often" by fixing a probability law on the algorithm's inputs. The average analysis consists in the estimation ofthe requested resources, according to this probability distribution.In this context, I worked on several algorithms for the random generation of deterministic accessibleautomata (complete or not).Those algorithms are based on bijective combinatorics, that allows to use generic tools called the Boltzmann generators. I implemented those methods in two softwares : REGAL and PREGA. I studied the average complexity of state minimization algorithms and obtained results showing that theaverage case of the two algorithms due to Moore and Hopcroft is way better than the worst case

Pendant la construction d'un groupe de réflexion avec des dirigeants de PME, nousavons détecté une grande incertitude par rapport à la continuité future des transactions. La stratégie et la création de valeur des produits et des services prennent une importance considérable si on estime que ce type d'organisation possède une grande quantité de restrictions et dépend principalement des activités marchandes pour survivre, obtenir des profits et croître. Mais, comme nous l'établissons dans la première partie de cette thèse, bien que les approches classiques de la gestion soient convergentes, elles semblent être insuffisantes car basées sur l'ordre et le contrôle en ne considérant que partiellement le dynamisme de ces entreprises, pendant que dans la pratique tout semble être dynamique et pourtant désordonné et complexe. Aussi nous nous posons la question : Comment aider les dirigeants de PME à créer des stratégies dans des situations complexes? La proposition théorique développée dans la deuxième partie, qui est l'originalité de ce travail, étudie les phénomènes dynamiques de l'entreprise en les classifiant comme un système complexe qui est soumis aux émergences et interruptions et qui est lié aux attracteurs et limiteurs de sa dynamique. Finalement, basé sur une épistémologie constructiviste, on a mis en pratique les propositions théoriquesdéveloppées sur le terrain par le biais d'une recherche-intervention en PME qui a permis de concevoir la stratégie de la valeur des produits et des services dans une approche dynamique. / While working with a focus group of SMEs managers, we detected a large uncertainty about future continuity of business transactions. Strategy and value creation of products and services are significantly important if we considered that this kind of organization has a lot of restrictions and depends mainly on their commercial activities to survive, be profitable and grow. But, as we established on the first part of this thesis, although the traditional management approachesconverge they seem to be insufficient because they are based on the principles of order and control by considering only a part of the dynamism of these companies, while in practice everything seems to be dynamic, disordered and complex. So we ask the question: How can we help SMEs to create strategies in complex situations? The theoretical proposition developed in the second part studies the dynamical phenomena by classifying the company as a complex system submitted to interruptions and emergencies and linked to dynamics attractors and restrictors. Finally, based on a constructivist epistemology, we have implemented theoreticalpropositions developed at field-research through an intervention methodology for helping SMEs to design a value creation strategy, of products and services, in a dynamic approach.

Au cours de cette thèse on développera l'hypothèse que l'individu biologique soit une unité fonctionnelle hiérarchiquement organisée : une définition qui correspond à l'ontologie des systèmes biologiques et influence la pratique de la biologie. Le but de cette thèse est de démontrer que l'organisation des entités en niveaux n'est pas une question purement méthodologique : le fait d'avoir des Individus à plusieurs niveaux fait partie de l'ontologie des systèmes biologiques. Le point de départ de la thèse c'est le constat qu'il y a des individus biologiques à plusieurs niveaux : c'est-à-dire des entités spatio ­temporellement limitées et uniques. Même s'il y a plusieurs types de niveaux d'entités biologiques (évolutionnaires, physiologiques, moléculaires, etc. ) c'est certainement les niveaux de sélection qui occupent une grosse partie du débat. A quel niveau agit-elle la sélection et si elle est la force la plus Importante de l'histoire, est une question majeure. Ce qui caractérise la biologie est donc une complexité dynamique. Les caractéristiques de chaque entité sont influencées par celles des entités è côté. Pour cette raison, se demander quelle est l'unité de sélection n'est pas une question pertinente pour comprendre l'ontologie de systèmes biologiques. Tout d'abord, Il n'y a pas que les niveaux de sélection: réduire l'émergence des niveaux supérieurs à l'action de la sélection naturelle est une vision simpliste. Notamment, l'exemple du cancer nous conduit à considérer les niveaux fonctionnels comme importants pour la compréhension de l'ontologie des vivants. Les transitions évolutionnaires, par exemples, nous montrent que les nouvelles formes d'organisation sont caractérisées par des nouvelles fonctions. La naissance d'une organisation complexe permet de réaliser plus de fonctions. En conclusion, on peut montrer comment une définition de l'individu biologique comme unité fonctionnelle permet de réconcilier la métaphysique des sciences avec une notion de sens commun et, en même temps, d'être utile pour la pratique de la science. / One of the main problems related to the definition of individuality in biology is how to account for the hierarchical structure of nature, which has been prominently emphasized in evolutionary theory (Dobzhansky 1937; Eldredge 1985; Mayr 1963; Liebermann, Vrba 1995). Nowadays, works in several areas validate a hierarchical approach to the study of biological individuality: the debate on the units of selection, for example, springs from the idea that hierarchy is the product of evolution by natural selection. Moreover, studies on major evolutionary transitions inquiry why selection at lower levels does not disrupt integration at higher levels (Maynard Smith, Szathmary 1995). Finally, the hierarchy theory (Gould, Vrba 1986) proposes a new formulation of the Darwinian theory, ln order to overcome reductionism. Moreover, nowadays cancer, thanks to its analysis from a multi-level perspective, is increasingly considered as a pathology linked to the tissue organization more then to the cell regulation (Sonnenschein, Soto 1999). ln effect, cancer was originally considered to be a deregulation of the normal growing program of the cell. Exploring the notion of hierarchy and levels of individuals in biology has epistemological and ontological consequences. First of all, from an epistemological point of view we have to understand whether complexity is the necessary outcome of natural selection. Another problem is to understand why selection at lower levels does not disrupt integration at higher levels (Maynard Smith, Szathmary 1995, Calcott Sterelny 2011 ). A paradigmatic case in which integration between lower and higher levels is lost is cancer, in which selection acting on cells destroys tissue and organism organisation (Nowell 1976, Okasha 2006). This pathological case seems to show that biological individuals have a hierarchical organization ln which the identity of parts depends both on their interactions and on higher-level effects. Therefore, relations among levels are crucial: we need a relational ontology of levers· (Bertolaso 2013, 2016), which will allow understanding how each level ls the result of relations among underlying parts. Then, from an ontological point of view, the problem we face today in defining the most fundamental level in biological hierarchy is the same of the old metaphysical problem of defining parts and wholes. This is an ontological concern: asking what makes of an aggregate a real individual The aim of this dissertation ls to show that a definition of individual as functional unit gives reason of the hierarchical organization of living beings: it allows a contextual analysis of the individual (Goodnight). Through such a definition, we can overcome reductionism without supporting a naif pluralism.

Cette thèse de doctorat en littérature et arts de la scène et de l’écran examine les écritures scéniques de la catastrophe humaine dans le théâtre contemporain. Elle explore les dynamiques qui sous-tendent la représentation de la barbarie au sein de formes spectaculaires marquées par une forte dimension visuelle. Divisé en deux volets – un premier, critique et un second, pratique –, le travail s’articule d’abord autour d’un corpus composé de trois spectacles : Kamp du collectif Hotel Modern, Rwanda 94 du Groupov et Rouge décanté signé par Guy Cassiers. En observant les oeuvres à la lumière de la complexité et en les abordant à l’aide d’une approche systémique,l’étude tente de révéler les mouvements – esthétiques, perceptifs et thématiques – qui animent ces écritures hétérogènes. La seconde partie de la thèse rend compte d’un processus d’expérimentation mené dans l’espace scénique. Ce dernier, consacré à esquisser une création artistique originale, questionne les mémoires occidentales du génocide des Tutsi du Rwanda.L’expérience pratique fait écho à plusieurs des problématiques soulevées par l’investigation critique et propose une autre forme de réflexion, menée directement sur le plateau. / This doctoral thesis in performing arts looks into scenic writings of human disasters incontemporary theatre. It examines dynamics underlying the representation of barbarism withinspectacular forms imprinted with a visual dimension. Split into two parts – a first one, critical anda second one, practical -, the work is firstly structured around a corpus composed of three shows :Kamp of the Hotel Modern group, Rwanda 94 of Groupov and Rouge décanté by Guy Cassiers.Through the observation of the works in the light of the complexity and by analysing it with asystemic approach, the study attempts to reveal the moves – aesthetic, perceptive and thematic –that drive these heterogeneous writings. The second part of the thesis deals with a process ofexperimentation led in the scenic space. The latter, dedicated to outline an original artisticcreation, questions occidental memories on the Tutsi genocide in Rwanda. The practicalexperience echoes back to several issues raised by the critical investigation and proposes anotherform of reflection, directly led on the stage.

Un fasciagraphe de taille n et de fibre F est constitué de n copies consécutives du graphe F, chaque copie étant reliée à la suivante selon le même schéma. Les rotagraphes sont définis similairement, mais selon une structure circulaire. Dans cette thèse nous caractérisons un ensemble de problèmes combinatoires qui peuvent être résolus de façon efficace dans la classe des fasciagraphes et rotagraphes. Dans ce contexte, nous définissons les (d,q,w)-propriétés closes et stables, et présentons pour de telles propriétés un algorithme pour calculer une solution optimale en temps constant pour l'ensemble des fasciagraphes ou rotagraphes de fibre fixée. Nous montrons que plusieurs problèmes communément étudiés dans la théorie des graphes et NP-complets dans le cas général sont caractérisés par des (d,q,w)-propriétés closes ou stables. Dans une seconde partie de la thèse, nous adaptons cet algorithme générique à trois problèmes spécifiques caractérisés par des (d,q,w)-propriétés stables : le problème du code identifiant minimum, et deux problèmes proches, celui de dominant-localisateur minimum et celui du dominant-total-localisateur minimum. Nous présentons alors une implémentation de l'algorithme qui nous a permis de répondre à des questions ouvertes dans certains rotagraphes particuliers : les bandes circulaires de hauteur bornée. Nous en déduisons d'autres résultats sur les bandes infinies de hauteur bornée. Enfin, nous explorons le problème du code identifiant dans une autre classe de graphes à structure répétitive : les graphes fractals de cycle. / A fasciagraph of length n and of fiber F, is constituted of n consecutive copies of a graph F, each copy being linked to the next one according to a same scheme. Rotagraphs are defines similarily, but along a circular structure. In this thesis, we caracterize a set of combinatorial problems that can be efficiently solved when applied on the class of rotagraphs and fasciagraphs. In this context, we define closed and stable (d,q,w)-properties, and we present, for such properties, an algorithm to compute an optimal solution, in constant time, for the set of fasciagraphs or rotagraphs of fixed fiber. We show that several problems, largely studied in graph theory, are caracterized by closed or stable (d,q,w)-properties. In a second part of the thesis, we adapt the generic algorithm to three problems caracterized by stable (d,q,w)-properties : the problem of minimum indentifying code, and two other, close to this one, the problem of minimum locating-dominating set et the one of minimum locating-total-dominating set. We present an implementation of our algorithm which has let us respond to open questions in a certain sub-class of rotagraphs : the circular strips of bounded height. We deduce from there other results on infinite strips of bounded height. Finaly we explore the problem of minimum identifying code in another class of graphs with repetitive structure : the fractal graphs.

The intended goal of this manuscript is to build bridges between two definitions of complexity. One of them, called the algorithmic complexity is well-known to any computer scientist as the difficulty of performing some task such as sorting or optimizing the outcome of some system. The other one, etymologically closer from the word "complexity" is about what happens when many parts of a system are interacting together. Just as cells in a living body, producers and consumers in some non-planned economies or mathematicians exchanging ideas to prove theorems. On the algorithmic side, the main objects that we are going to use are two models of computations, one called communication protocols, and the other one circuits. Communication protocols are found everywhere in our world, they are the basic stone of almost any human collaboration and achievement. The definition we are going to use of communication reflects exactly this idea of collaboration. Our other model, circuits, are basically combinations of logical gates put together with electrical wires carrying binary values, They are ubiquitous in our everyday life, they are how computers compute, how cell phones make calls, yet the most basic questions about them remain widely open, how to build the most efficient circuits computing a given function, How to prove that some function does not have a circuit of a given size, For all but the most basic computations, the question of whether they can be computed by a very small circuit is still open. On the other hand, our main object of study, cellular automata, is a prototype of our second definition of complexity. What "does" a cellular automaton is exactly this definition, making simple agents evolve with interaction with a small neighborhood. The theory of cellular automata is related to other fields of mathematics�� such as dynamical systems, symbolic dynamics, and topology. Several uses of cellular automata have been suggested, ranging from the simple application of them as a model of other biological or physical phenomena, to the more general study in the theory of computation. / The intended goal of this manuscript is to build bridges between two definitions of complexity. One of them, called the algorithmic complexity is well-known to any computer scientist as the difficulty of performing some task such as sorting or optimizing the outcome of some system. The other one, etymologically closer from the word "complexity" is about what happens when many parts of a system are interacting together. Just as cells in a living body, producers and consumers in some non-planned economies or mathematicians exchanging ideas to prove theorems. On the algorithmic side, the main objects that we are going to use are two models of computations, one called communication protocols, and the other one circuits. Communication protocols are found everywhere in our world, they are the basic stone of almost any human collaboration and achievement. The definition we are going to use of communication reflects exactly this idea of collaboration. Our other model, circuits, are basically combinations of logical gates put together with electrical wires carrying binary values, They are ubiquitous in our everyday life, they are how computers compute, how cell phones make calls, yet the most basic questions about them remain widely open, how to build the most efficient circuits computing a given function, How to prove that some function does not have a circuit of a given size, For all but the most basic computations, the question of whether they can be computed by a very small circuit is still open. On the other hand, our main object of study, cellular automata, is a prototype of our second definition of complexity. What "does" a cellular automaton is exactly this definition, making simple agents evolve with interaction with a small neighborhood. The theory of cellular automata is related to other fields of mathematics, such as dynamical systems, symbolic dynamics, and topology. Several uses of cellular automata have been suggested, ranging from the simple application of them as a model of other biological or physical phenomena, to the more general study in the theory of computation.

Si l'Ingénieur s'efforce de coordonner sur les territoires les deux facettes de son activité : d'un côté la gestion des fonctions urbaines, de l'autre celle des risques, il hésite à se démarquer de celles-ci comme il le devrait, pour affronter la complexité spatiale. Or notre pratique des espaces urbanisés comme notre engagement dans la prévention des risques montrent que la complexité se manifeste à lui, tant dans la réalisation des projets que dans la survenue des catastrophes. En proposant un outil d'analyse spatiale : le territoire-étagé, en le dotant d'une fonction - le monitorage - nous proposons une voie qui permette à l'ingénierie d'anticiper du plus possible le développement de processus dommageables. En permettant une plus grande compréhension des mécanismes à l'œuvre au sein des espaces métapolitains [Ascher, 1995], l'ingénierie du territoire-étagé offre la possibilité d'agir en retour sur les pratiques de gestion pour espérer réduire, par la résilience, les perturbations ou leurs effets de différentes natures et intensités. / If the Engineer tries to coordonnate the two facets of its activities : on one hand the management of urban functions, on the other hand the management of the risk, he hesitates to escape of these to tackle with complexity as he should do. Meanwhile, our experiment of urban areas as well as our action in the management of prevention show complexity appear in the carrying out of projects and in disasters. By proposing a tool to analyse urban areas : the « territoire-étagé », by using it as monitoring tool, we open a way to allow engineers to anticipate as soon as possible the development of damaging processes. By allowing a better understanding mechanisms into metapolitan areas [Ascher, 1995], the engineering of « territoire-étagé » gives the possibility feed-back on management practices to expect reduce, by resilience, the perturbations or the effects of various nature and intensity.