L'incertitude a été toujours présente dans les problèmes d'optimisation. Dans ce travail, nous nous intéressons aux problèmes d'optimisation multi-niveaux où l'incertitude apparaît très naturellement. Les problèmes d'optimisation multi-niveaux avec incertitude ont suscité un intérêt à la fois théorique et pratique. L'optimisation robuste fait partie des méthodes les plus étudiées pour traiter ces problèmes. En optimisation robuste, nous cherchons une solution qui optimise la fonction objective pour le pire scénario appartenant à un ensemble d'incertitude donné. Les problèmes d'optimisation robuste multi-niveaux sont difficiles à résoudre, même de façon heuristique. Dans cette thèse, nous abordons les problèmes d'optimisation robuste à travers le prisme des méthodes de décomposition. Ces méthodes décomposent le problème en un problème maître (MP) et plusieurs problèmes satellites de séparation (AP). Dans ce contexte, les solutions et les relaxations heuristiques ont une importance particulière. Même pour les problèmes d'optimisation combinatoires, les relaxations sont importantes pour analyser l'écart de l'optimalité des solutions heuristiques. Un autre aspect important est l'utilisation des heuristiques comme integrés dans une méthode exacte. Les principales contributions de ce travail sont les suivantes. Premièrement, nous proposons une nouvelle relaxation pour les problèmes multi-niveaux basée sur l’approche dite d’information parfaite dans le domaine de l’optimisation stochastique. L'idée principale derrière cette méthode est d'éliminer les contraintes de non anticipativité du modèle pour obtenir un problème plus simple. Nous pouvons ensuite fournir des algorithmes combinatoires ad-hoc et des formulations de programmation mixte en nombres entiers compactes pour ce problème. Deuxièmement, nous proposons de nouveaux algorithmes de programmation dynamique pour résoudre les problèmes satellites apparaissant dans une classe spécifique de problèmes robustes pour un ensemble d'incertitude de type budget. Ce type d'incertitude est basé sur le nombre maximum d'écarts autorisés et leur taille. Ces algorithmes peuvent être appliqués à des problèmes de lot-sizing et à des problèmes de tournées de véhicules. Enfin, nous proposons un modèle robuste pour un problème lié à l’installation équitable de capteurs. Ce modèle fait le lien entre l'optimisation robuste et l'optimisation stochastique avec contraintes probabilistes ambigües. / Uncertainty has always been present in optimization problems, and it arises even more severely in multistage optimization problems. Multistage optimization problems underuncertainty have attracted interest from both the theoretical and the practical level.Robust optimization stands among the most established methodologies for dealing with such problems. In robust optimization, we look for a solution that optimizes the objective function for the worst possible scenario, in a given uncertainty set. Robust multi-stage optimization problems are hard to solve even heuristically. In this thesis, we address robust optimization problems through the lens of decompositions methods. These methods are based on the decomposition of the robust problem into a master problem (MP) and several adversarial separation problems (APs). The master problem contains the original robust constraints, however, written only for finite numbers of scenarios. Additional scenarios are generated on the y by solving the APs. In this context, heuristic solutions and relaxations have a particular importance. Similarly to combinatorial optimization problems, relaxations are important to analyze the optimality gap of heuristic solutions. Heuristic solutions represent a substantial gain from the computational viewpoint, especially when used to solve the separation problem. Because the adversarial problems must be solved several times, good heuristic solution may avoid the exact solution of the APs. The main contributions of this work are three-fold. First, we propose a new relaxation for multi-stage problems based on the approach named perfect information in the field of stochastic optimization. The main idea behind this method is to remove nonanticipativity constraints from the model to obtain a simpler problem for which we can provide ad-hoc combinatorial algorithms and compact mixed integer programming formulations. Second, we propose new dynamic programming algorithms to solve the APs for robust problems involving budgeted uncertainty, which are based on the maximum number of deviations allowed and on the size of the deviations. These algorithms can be applied to lot-sizing problems and vehicle routing problems among others. Finally, we study the robust equitable sensor location problem. We make the connection between the robust optimization and the stochastic programming with ambiguous probabilistic constraints. We propose linear models for several variants of the problem together withnumerical results.

Le roman contemporain apparait comme le lieu d’un double questionnement : le premier est lié à sa forme, tandis que le second renvoie à une longue interrogation sur un monde marqué par de grands bouleversements d’ordre anthropologique, politique, culturel ou sociologique. Chez Glissant et Le Clézio, ce questionnement prend l’allure d’une problématisation du monde et imprègne, d’un bout à l’autre, leur production romanesque. Ainsi, la présente thèse analyse les mécanismes et les enjeux de l’art romanesque à l’épreuve du mouvant. Elle évoque l’idée d’une déconstruction de la forme et la structure romanesques pour arriver à une nouvelle pensée du roman qui permet, en même temps, de penser la complexité du monde. Cette complexité se donne à lire dans le roman à travers l’idée de contrepoint qui permet le mélange de voix narratives, des personnages, des formes, des genres, ou encore des mondes. Parler d’une poétique du mouvant revient, dès lors, à penser la multidimensionnalité de l’être ainsi que les liens qui se tissent entre des individus présentés comme des producteurs et des produits des cultures. La pensée du mouvant prend ainsi une orientation politique du monde. Elle exalte, non pas la dénaturation de le l’individu, la perte de son identité ou encore sa dilution, mais sa propension à penser l’autre dans sa différence, comme un élément d’un tout complexe, avec finalement l’idée de « différence dans l’unité » et d’ « unité dans la différence » qui permet d’aller au-delà de la simple juxtaposition des cultures. Le mouvant devient, dès lors, l’autre nom du métissage, de la complexité et de l’interculturalité. / The usual contemporary novel appears as the place of a double questioning: the first is linked to its form, and the second drives to a long interrogation on a world marked by great anthropological, political, cultural and social upheavals. For Glissant and Le Clézio this interrogation takes the form of an everlasting questioning on the concept of the world and this can be seen along all theirs novels. Thereby, the present thesis investigates the mechanisms and the stakes of the art of the novel compared to the concept of "mouvant". This work treats about the deconstruction of the usual form and the structure of the novel driving to a new approach of the novel allowing, at the same time, to glimpse the complexity of the world. This complexity can be seen in the novel through the mechanisms of the counterpoint which allows the mixing of narrative voices, forms, characters, genres or even worlds. To speak about a poetics of " mouvant" it is necessary to consider the multidimensional aspect of the concept of the living being, as well as the links between individuals presented both as producers of cultures and as themselves a product of cultures. Thus, the concept of "mouvant" takes a political orientation of the world. This concept exalts, neither the denaturation of the individual nor the loss or the dilution of his identity, but the propensity to see the other one in his difference, as a part of a complex whole, and ultimately the idea of “Difference in unity” and “Unity in difference”, which allows us to go beyond the simple juxtaposition of cultures. Therefore, the concept of "mouvant" becomes the other name of the mixing, the complexity of the world and the interculturalism.

La transmission est un acte social manifestant les échanges entre individus dans le but d’assurer une continuité dans le temps à travers la succession des générations. Par ailleurs, cette même transmission dépend de plusieurs circonstances liées tant aux perceptions des individus qu’à leurs conditions sociohistoriques de vie. Il en résulte que ces transmissions sont souvent imbriquées entre la continuité et le changement, la production et la reproduction, la construction et la co-construction, etc. Certes, elles ne sont que rarement une reproduction à l’identique, ce qui favorise sa diversité et sa richesse aboutissant parfois à la complexité de ce processus. C’est dans le but de détecter les effets de génération traduisant les changements s’opérant entre trois générations masculines marocaines installées en Belgique que nous avions entamé cette étude. Celle-ci par le biais de deux méthodes complémentaires, notamment le récit de vie et l’analyse interprétative phénoménologique, a pu mettre en relation des faits connus. Il s’agit de la mise en lien de pratiques d’engagements familiaux et de transmissions générationnelles favorisant l'extraction d’éclairantes significations. Ainsi, cette étude, en analysant en premier les récits de vie à la façon d’un « roman » familial de ces trois générations ayant des relations collatérales et sociales (relations horizontales), a pu identifier les caractéristiques et profils des sujets relevant de chaque génération. Ces derniers,en vivant des moments sociohistoriques, y participent activement et passivement. En effet, de leur implication à un destin commun et concret, ils forment une unité générationnelle spécifique marquée par un temps historique et une trame événementielle commune.De plus, l’utilisation de la méthode phénoménologique a permis d’identifier ensuite trois registres de transmissions mis en évidence par les générations familiales ayant un lien de filiation patrilinéaire existant entre un grand-père, son fils et son petit-fils (relations verticales). Les différents contenus de leurs registres, non mutuellement exclusifs, dénotent du développement des pratiques de transmission où chaque génération intériorise les valeurs des ainés par modelage ou par l’exemple…, mais s’approprie également de nouvelles valeurs.De surcroit, leurs transmissions véhiculent différents contenus ce qui manifeste que chaque génération reste marquée par ses propres expériences, perceptions, vécues, favorisant la co-construction de nouvelles transmissions et leur circulation. Par conséquent, nos travaux nous amènent à concevoir une articulation très forte entre les transmissions diversifiées selon les contextes et les contenus qui se font entre ces générations patrilinéaires. Celles-ci se sont engagées dans des transmissions générationnelles pour faire face aux différentes pressions socioculturelles et économiques leur imposant de multiples ajustements. Par ailleurs, leurs transmissions s’opérant dans un contexte migratoire, même si elles ambitionnent de garder une continuité avec le patrimoine d’origine, évoquent par ailleurs, le changement social, sans pour autant marquer de rupture prononcée.Finalement, il est à noter que leurs objectifs de par leurs différentes transmissions s’articulent autour de la préservation de l’appartenance et de l’équilibre familial, du respect des habitudes familiales, particulièrement par le développement de leurs liens qui demeurent une puissance affective qui scelle, maintient et développe leurs relations. De plus, toutes ces générations ambitionnent leur adaptation aux nouvelles valeurs et règles de la nouvelle société. Il s’agit là d’un enjeu familial consistant à maintenir une stabilité sociale et culturelle tout en ayant une harmonie avec l’environnement extérieur. / Doctorat en Sciences politiques et sociales / info:eu-repo/semantics/nonPublished

L’objet de cette recherche est de proposer des méthodes et des outils de gestion qui permettent de prévenir la dégradation de la santé mentale et somatique des personnes qui travaillent. Les dirigeants et les managers semblent en effet assez démunis face à l’augmentation des troubles appelés « psychosociaux » et ils ne parviennent que rarement àdépasser le stade de l’évaluation des facteurs psychosociaux de risques. Notre thèse est articulée autour de deux recherches-interventions. L’une s’est déroulée dans une PME de conseils aux entreprises et la seconde au sein d’un groupe multinational et coopératif de l’agroalimentaire. En mobilisant notamment des connaissances et desméthodes de l’ergonomie de l’activité, nous avons pu co-construire avec les acteurs des réponses pratiques à leurs besoins initiaux de prévention. Le management n’est plus centré exclusivement sur la personne qui travaille dont on cherche l’adhésion aux projets managériaux. Les encadrants managent le travail et l’autorité devient synonyme d’autorisation de faire du « bon travail ». Pour ce faire, des espaces de discussion sur le travail ont été organisés et les résultats de ces discussions sont institutionnalisés au sein du dispositif de gestion. Finalement, c’est le développement conjoint de l’entreprise et des personnes qui travaillent que cherchent désormais à atteindre les managers. / This research aims at offering management methods and tools to prevent mental and somatic health diseases in the workforce. Chief executive officers and managers appear to be helpless in the face of rising psychosocial disorders and their response rarely goes beyond the assessment stage of psychosocial risks’ factors. This thesis is built upon two research-intervention projects. One took place in a b-to-b smallscale consultancy venture, whilst the second was set in a multinational and cooperative agrifood firm. Researchers and company staff jointly developed practical actions to address their initial need for prevention by transforming situations in using ergon omics-oriented information. Staff management is no longer centered on seeking the agreement of the workforce with managers’ projects. Instead the company executives organize everyone’s occupation by dealing with the gap between the “real done job” and the prescribed one. Authority istranslated into authorization of doing a “well done job”. To this end, allowance for discussions on the occupational organization and ways to do the job has been made, and results of those discussions are formally integrated in the management device. Overall, managers are now aiming for the joint personal development of staff in addition to the firmdevelopment.

Cette recherche, inscrite dans le champ de l’esthétique et de l’histoire de l’art, a pour objectif de rendre compte de la multiplicité et de la polysémie des productions artistiques du XXIe siècle relevant de l’anamorphose et de l’image double. Ces œuvres instables ont la faculté de conjuguer le flux et l’immobilité, tout en permettant de « saisir » la virtualité par le biais de l’entrevision. Constitutives d’ambiguïtés irréductibles, elles réactualisent les détournements de la perspective issus de la Renaissance et produisent des images immatérielles sans nécessairement faire appel aux nouvelles technologies caractérisant l’art numérique. En s’appuyant notamment sur la pensée philosophique de Marcello Vitali Rosati, précisant que le virtuel est la dynamicité de l’interstice, il est posé comme hypothèse de cette investigation que l’analyse de l’ « entre-deux » permettra d’appréhender la virtualité dans la richesse de sa complexité. / This research project in the field of aesthetics aims at accounting for the multiplicity and polysemy of 21st century works of art pertaining to the idea of anamorphosis and double image. These unstable works of art have the power to combine flux and stasis while allowing the spectator to “seize” virtuality through in between-vision. In carrying intractable ambiguities, they revive the Renaissance uses of perspective and illusion and produce immaterial images without necessarily resorting to state- of- the- art digital technology. Drawing on the philosophical works of Marcello Vitali Rosati positing the virtual as being the dynamics of the interstice, the working assumption of this research is that the analysis of “in-betweeness” shall help to get more insight into virtuality in all its richness and complexity.

La complexité implicite (ICC) vise à donner des caractérisations de classes de complexité dans des langages de programmation ou des logiques, sans faire référence à des bornes sur les ressources (temps, espace mémoire). Dans cette thèse, nous étudions l’approche de la logique linéaire à la complexité implicite. L’objectif est de donner des caractérisations de classes de complexité, à travers des variantes du lambda-calcul qui sont typables dans de tels systèmes. En particulier, nous considérons à la fois une perspective monovalente et une perspective polyvalente par rapport à l’ICC. Dans le premier cas, le but est de caractériser une hiérarchie de classes de complexité à travers un lambda-calcul élémentaire typé dans la logique linéaire élémentaire (ELL), où la complexité ne dépend que de l’interface d’un programme, c’est à dire son type. La deuxième approche rend compte à la fois des fonctions calculables en temps polynomial et de la normalisation forte, à travers des termes du lambda-calcul pur qui sont typés dans un système inspiré par la logique linéaire Soft (SLL); en particulier, par rapport à l’approche logique ordinaire, ici nous abandonnons la modalité “!” en faveur de l’emploi des types stratifiés, vus comme un raffinement des types intersection non associatifs, afin d’améliorer la typabilité et, en conséquence, l’expressivité. Enfin, nous explorons l’utilisation des types intersection, privés de certaines de leurs propriétés, vers une direction plus quantitative que l’approche qualitative habituelle, afin d’obtenir une borne sur le calcul de lambda-termes purs, en obtenant en plus une caractérisation de la normalisation forte. / In this thesis we explore the linear logic approach to implicit computational complexity, through the design of type assignment systems based on light linear logic, or heavily inspired by them, with the purpose of giving a characterization of one or more complexity classes, through variants of lambda-calculi which are typable in such systems. In particular, we consider both a monovalent and a polyvalent perspective with respect to ICC. In the first one the aim is to characterize a hierarchy of complexity classes through an elementary lambda-calculus typed in Elementary Linear Logic (ELL), where the complexity depends only on the interface of a term, namely its type. The second approach gives an account of both the functions computable in polynomial time and of strong normalization, through terms of pure lambda-calculus which are typed in a system inspired by Soft Linear Logic (SLL); in particular, with respect to the usual logical take, in the latter we give up the “!” modality in favor of employing stratified types as a refinement of non-associative intersection types, in order to improve typability and, as a consequence, expressivity.Finally we explore the use of intersection types, deprived of some of their usual properties, towards a more quantitative approach rather than the usual qualitative one, namely in order to compute a bound on the computation of pure lambda-terms, obtaining in addition a characterization of strong normalization.

La complexité implicite est la caractérisation de classes de complexité par des restrictions syntaxiques sur des modèles de calcul. Plusieurs sous-systèmes de la logique linéaire caractérisant le temps polynomial ont été définis: ces systèmes sont corrects (les termes normalisent en temps polynomial) et complets (il est possible de simuler une machine de Turing pendant un nombre polynomial d'étapes). Un des buts sur le long terme est de donner statiquement des bornes de complexité. C’est pourquoi nous cherchons les caractérisations du temps polynomial les plus expressives possible. Notre principal outil est la sémantique des contextes: des jetons voyagent à travers le réseau selon certaines règles. Les chemins définis par ces jetons représentent la réduction du réseau. Contrairement aux travaux précédents, nous ne définissons pas directement des sous-systèmes de la logique linéaire. Nous définissons d'abord des relations -> sur les sous-termes des réseaux de preuves tel que: B -> C ssi ”le nombre de copies de B dépend du nombre de copies de C”. L’acyclicité de -> borne le nombre de copies de chaque sous-terme, donc la complexité du terme. Ensuite nous définissons des sous-systèmes de la logique linéaire assurant l’acyclicité de ->. Nous étudions aussi des caractérisations du temps élémentaire et primitif récursif. Dans le but d’adapter nos sous-systèmes de la logique linéaire à des langages plus riches, nous adaptons la sémantique des contextes aux réseaux d’interaction, utilisés comme langage cible pour de petits langage de programmation. Nous utilisons cette sémantique des contexte pour définir une sémantique dénotationnelle sur les réseaux d’interactions. / Implicit computational complexity is the characterization of complexity classes by syntactic restrictions on computation models. Several subsystems of linear logic characterizing polynomial time have been defined : these systems are sound (terms normalize in polynomial time) and complete (it is possible to simulate a Turing machine during a polynomial number of steps). One of the long term goals is to statically prove complexity bounds. This is why we are looking for the most expressive characterizations possible. Our main tool is context semantics : tokens travel across proof-nets (programs of linear logic) according to some rules. The paths defined by these tokens represent the reduction of the proof-net.Contrary to previous works, we do not directly define subsystems of linear logic. We first define relations -> on subterms of proof-nets such that: B -> C means \the number of copies of B depends on the number of copies of C". The acyclicity of -> allows us to bound the number of copies of any subterm, this bounds the complexity of the term. Then, we define subsystems of linear logic guaranteeing the acyclicity of ->. We also study characterizations of elementary time and primitive recursive time. In orderto adapt our linear logic subsystems to richer languages, we adapt the context semantics to interaction nets, used as a target language for small programming languages. We use this context semantics to define a denotational semantics on interaction nets.

Cette thèse propose une méthodologie de pilotage d'organisations complexes, ens'intéressant à de nouvelles méthodes de planification collaborative et d'optimisation d'interventions en environnements soumis à des rayonnements ionisants. En nous basant sur l'étude d'installations scientifiques et technologiques complexes tels que celles du CERN à Genève (Suisse) et de la GSI à Darmstadt (Allemagne), nous y analysons les besoins et contraintes de planification imposés par les environnements à risques en général, et par lesrayonnements ionisants en particulier. Les implications liées à la collaboration sont ensuite détaillées, et un modèle ontologique d'intervention est proposé afin de sélectionner les méthodes les plus adaptées au problème étudié. La méthode proposée dans cette thèse repose sur des techniques éprouvées en planification de projets ainsi qu'en conception de produits comme la Design Structure Matrix (DSM). Elle introduit en revanche dans ces domaines des méthodes habituellement rencontrées en intelligence artificielle : les algèbres temporelles qualitatives et la propagation des contraintes temporelles, ainsi que la recherche de compromis en cas de conflit. Cette « DSM Collaborative » a été implémentée dans une application prototype testée sur des cas pratiques au CERN et à la GSI, dont le premier est décrit dans l'ultime chapitre de cette thèse. C'est une approche qui place la ressource(essentiellement humaine) et les contraintes temporelles au coeur du processus de planification. Elle met l'accent sur la collaboration entre les différents participants, ainsi que sur la simulation et la comparaison multicritère de multiples scenarii plutôt que sur la recherche d'un unique optimum souvent irréalisable sur le plan pratique. / This work proposes a methodology to handle complexity in organizations byfocusing on innovative and collaborative planning and scheduling methods dedicated to the optimization of interventions in environments emitting ionizing radiations. By taking as work environment highly complex and technological scientific facilities such as the ones of CERN in Geneva (Switzerland) and GSI in Darmstadt (Germany), we analyze the needs and requirements induced in intervention planning and scheduling by hazardous environments in general, and then more specifically by ionizing radiations. The implications of collaborative work are then scrutinized, and an ontological model for interventions is designed in order to select the methods best suited to our problem. The framework we present in this work relies on methods sucessfully used in project planning and scheduling and innovative product design like the Design Structure Matrix (DSM). It also introduces in these fields methods borrowed to artificial intelligence planning and scheduling such as the temporal qualitative algebras, constraint propagation, and the search of compromises in case of conflicts. This so called “Collaborative DSM” has been implemented in a prototype software application tested at CERN and GSI on practical applications. The very first one and its results are presented in the final chapter of this thesis. This framework aims at placing resources (mostly human resources) and temporal constraints at the heart of the planning and scheduling process. It focuses on collaboration between the different actors involved, from coordinators to technicians, and on simulation and multiple-criteria comparison of several scenarios, rather than searching for a unique optimum, which often tends to be non-practical, should one even be found.

Le théorème de Carathéodory coloré, prouvé en 1982 par Bárány, énonce le résultat suivant. Etant donnés d Å1 ensembles de points S1,SdÅ1 dans Rd , si chaque Si contient 0 dans son enveloppe convexe, alors il existe un sous-ensemble arc-en-ciel T µ SdÅ1 iÆ1 Si contenant 0 dans son enveloppe convexe, i.e. un sous-ensemble T tel que jT \Si j • 1 pour tout i et tel que 0 2 conv(T ). Ce théorème a donné naissance à de nombreuses questions, certaines algorithmiques et d’autres plus combinatoires. Dans ce manuscrit, nous nous intéressons à ces deux aspects. En 1997, Bárány et Onn ont défini la programmation linéaire colorée comme l’ensemble des questions algorithmiques liées au théorème de Carathéodory coloré. Parmi ces questions, deux ont particulièrement retenu notre attention. La première concerne la complexité du calcul d’un sous-ensemble arc-en-ciel comme dans l’énoncé du théorème. La seconde, en un sens plus générale, concerne la complexité du problème de décision suivant. Etant donnés des ensembles de points dans Rd , correspondant aux couleurs, il s’agit de décider s’il existe un sous-ensemble arc-en-ciel contenant 0 dans son enveloppe convexe, et ce en dehors des conditions du théorème de Carathéodory coloré. L’objectif de cette thèse est de mieux délimiter les cas polynomiaux et les cas “difficiles” de la programmation linéaire colorée. Nous présentons de nouveaux résultats de complexités permettant effectivement de réduire l’ensemble des cas encore incertains. En particulier, des versions combinatoires du théorème de Carathéodory coloré sont présentées d’un point de vue algorithmique. D’autre part, nous montrons que le problème de calcul d’un équilibre de Nash dans un jeu bimatriciel peut être réduit polynomialement à la programmation linéaire coloré. En prouvant ce dernier résultat, nous montrons aussi comment l’appartenance des problèmes de complémentarité à la classe PPAD peut être obtenue à l’aide du lemme de Sperner. Enfin, nous proposons une variante de l’algorithme de Bárány et Onn, calculant un sous ensemble arc-en-ciel contenant 0 dans son enveloppe convexe sous les conditions du théorème de Carathéodory coloré. Notre algorithme est clairement relié à l’algorithme du simplexe. Après une légère modification, il coïncide également avec l’algorithme de Lemke, calculant un équilibre de Nash dans un jeu bimatriciel. La question combinatoire posée par le théorème de Carathéodory coloré concerne le nombre de sous-ensemble arc-en-ciel contenant 0 dans leurs enveloppes convexes. Deza, Huang, Stephen et Terlaky (Colourful simplicial depth, Discrete Comput. Geom., 35, 597–604 (2006)) ont formulé la conjecture suivante. Si jSi j Æ d Å1 pour tout i 2 {1, . . . ,d Å1}, alors il y a au moins d2Å1 sous-ensemble arc-en-ciel contenant 0 dans leurs enveloppes convexes. Nous prouvons cette conjecture à l’aide d’objets combinatoires, connus sous le nom de systèmes octaédriques, dont nous présentons une étude plus approfondie / The colorful Carathéodory theorem, proved by Bárány in 1982, states the following. Given d Å1 sets of points S1, . . . ,SdÅ1 µ Rd , each of them containing 0 in its convex hull, there exists a colorful set T containing 0 in its convex hull, i.e. a set T µ SdÅ1 iÆ1 Si such that jT \Si j • 1 for all i and such that 0 2 conv(T ). This result gave birth to several questions, some algorithmic and some more combinatorial. This thesis provides answers on both aspects. The algorithmic questions raised by the colorful Carathéodory theorem concern, among other things, the complexity of finding a colorful set under the condition of the theorem, and more generally of deciding whether there exists such a colorful set when the condition is not satisfied. In 1997, Bárány and Onn defined colorful linear programming as algorithmic questions related to the colorful Carathéodory theorem. The two questions we just mentioned come under colorful linear programming. This thesis aims at determining which are the polynomial cases of colorful linear programming and which are the harder ones. New complexity results are obtained, refining the sets of undetermined cases. In particular, we discuss some combinatorial versions of the colorful Carathéodory theorem from an algorithmic point of view. Furthermore, we show that computing a Nash equilibrium in a bimatrix game is polynomially reducible to a colorful linear programming problem. On our track, we found a new way to prove that a complementarity problem belongs to the PPAD class with the help of Sperner’s lemma. Finally, we present a variant of the “Bárány-Onn” algorithm, which is an algorithmcomputing a colorful set T containing 0 in its convex hull whose existence is ensured by the colorful Carathéodory theorem. Our algorithm makes a clear connection with the simplex algorithm. After a slight modification, it also coincides with the Lemke method, which computes a Nash equilibriumin a bimatrix game. The combinatorial question raised by the colorful Carathéodory theorem concerns the number of positively dependent colorful sets. Deza, Huang, Stephen, and Terlaky (Colourful simplicial depth, Discrete Comput. Geom., 35, 597–604 (2006)) conjectured that, when jSi j Æ d Å1 for all i 2 {1, . . . ,d Å1}, there are always at least d2Å1 colourful sets containing 0 in their convex hulls. We prove this conjecture with the help of combinatorial objects, known as the octahedral systems. Moreover, we provide a thorough study of these objects

En raison des changements climatiques actuels, il est primordial de comprendre comment les écosystèmes vont réagir et tout particulièrement comment les chaînes trophiques vont être impactées. Pour cela, le comportement des oiseaux marins peut être utilisé comme des indicateurs des changements se déroulant au sein de l’écosystème. Cependant, un des défis actuels dans l’étude du comportement animal est d’identifier comment la structure temporelle du comportement est dépendante des conditions intrinsèques et extrinsèques et comment la complexité de cette organisation comportementale évolue sur un gradient allant de la stochasticité au déterminisme en fonction des changements environnementaux. Ma thèse a donc pour objectif d’étudier si un comportement complexe est adapté pour faire face à une perturbation du système chez les oiseaux marins et plus particulièrement chez deux espèces de manchots étant exposées à des changements environnementaux. / Due to ongoing climate change, it is necessary to understand how ecosystems will react and more particularly, how species may cope with the challenges of living in unstable systems. Seabirds’ behavior provides a way to monitor changes occurring in the marine environment, but identifying how the temporal structure and complexity of behavior depend on intrinsic and extrinsic parameters are underexplored topics in the field of animal behavior. My thesis aims to investigate if behavioral organization, through a gradient of stochasticity-determinism complexity, allows little and adélie penguins to buffer changes in the environment under a fractal analysis approach.