Cette thèse, articulée en trois chapitres, a pour objet d'étudier les interdépendances structurelles entre différents marchés financiers. Dans le Chapitre 1, nous étudions l'architecture des interdépendances entre les principaux marchés européens. En modélisant ces interdépendances par des réseaux dynamiques, nous proposons une nouvelle méthodologie permettant de mesurer, en fonction du temps, les liens directs et indirects reliant chaque paire d'élément au sein d'un système donné. Cette mesure topologique permet d'évaluer la hiérarchie d'un système et son niveau d'organisation, constituant ainsi un proxy de complexité. Notre indice s'appuie sur la définition de la complexité de Simon qui lie la complexité d'un système à son niveau d'organisation hiérarchique. Nous validons la pertinence de notre indice en étudiant empiriquement le lien entre complexité et incertitude. Dans le Chapitre 2, nous étudions l'impact de la globalisation sur l'économie, comme un accroissement des interdépendances dans un panel dynamique de 94 pays, de 1970 à 2011. Notre contribution est d'estimer le seuil endogénéisé de globalisation sur un panel dynamique. Enfin, nous étudions le rôle de l'incertitude économique sur le marché de la dette souveraine: le Chapitre 3 expose l'impact de l'incertitude économique sur le niveau des taux souverains au sein de la zone Euro. Ainsi cette thèse étudie le rôle de la complexité et de l'incertitude sur la structure des interdépendances financières. / This PhD dissertation is divided in three chapters, its purpose is to study structural interdependencies between different financial markets. In the Chapter 1, we investigate the architecture of interdependencies between the main European stock markets. Modeling interdependencies as networks, we propose a new methodology allowing to capture the time-varying the role of direct and indirect links between each pair of elements in a given system. This topologic measure asses the hierarchy in a system and its level of organization, constituting so far a proxy of complexity. Our index is based on Simon's definition of complexity: the level of complexity in a given system is related to its level of hierarchical organization. We empirically test our measure of complexity linking its levels with economic uncertainty in Eurozone. In the Chapter 2, we study the impact of globalization on the economy, as an increase of interdependencies in a dynamic panel of 94 countries from 1970 to 2011. our contribution is to estimate an endogeneous threshold of globalization in a dynamic panel. Finally we investigate the role of economic uncertainty on the Eurozone sovereign bond market: the Chapter 3 study the impact of uncertainty on the levels of sovereign yields. To sum up, this PhD dissertation reports our work about the role of complexity and uncertainty on the structure of financial interdependencies.

Une caractéristique contraignante de la complexité de Kolmogorov-Chaitin (dénotée dans ce chapitre par K) est qu'elle n'est pas calculable à cause du problème de l'arrêt, ce qui limite son domaine d'application. Une autre critique concerne la dépendance de K à un langage particulier ou une machine de Turing universelle particulière, surtout pour les suites assez courtes, par exemple, plus courtes que les longueurs typiques des compilateurs des langages de programmation. En pratique, on peut obtenir une approximation de K(s), grâce à des méthodes de compression. Mais les performances de ces méthodes de compression s'écroulent quand il s'agit des suites courtes. Pour les courtes suites, approcher K(s) par des méthodes de compression ne fonctionne pas. On présente dans cet thèse une approche empirique pour surmonter ce problème. Nous proposons une méthode "naturelle" qui permet d'envisager une définition plus stable de la complexité de Kolmogorov-Chaitin K(s) via la mesure de probabilité algorithmique m(s). L'idée est de faire fonctionner une machine universelle en lui donnant un programme au hasard pour calculer expérimentalement la probabilité m(s) (la probabilité de produire s), pour ensuite évaluer numériquement K(s) de manière alternative aux méthodes des algorithmes de compression. La méthode consiste à : (a) faire fonctionner des machines de calcul (machines de Turing, automates cellulaires) de façon systématique pour produire des suites (b) observer quelles sont les distributions de probabilité obtenues et puis (c) obtenir K(s) à partir de m(s) par moyen du théorème de codage de Levin-Chaitin. / In practice, it is a known problem that one cannot compress short strings, shorter, for example, than the length in bits of the compression program which is added to the compressed version of s, making the result (the program producing s) sensitive to the compressor choice and the parameters involved. However, short strings are quite often the kind of data encountered in many practical settings. While compressors' asymptotic behavior guarantees the eventual convergence to K(s) thanks to the invariance theorem, measurements differ considerably in the domain of short strings. We describe a method that combines several theoretical and experimental results to numerically approximate the algorithmic (Kolmogorov-Chaitin) complexity of short bit strings. This is done by an exhaustive execution of abstract machines for which the halting times are known thanks to the Busy Beaver problem. An output frequency distribution is then computed, from which the algorithmic probability is calculated and the algorithmic complexity evaluated by way of the (Levin-Chaitin) coding theorem. The approach we adopt here is different and independent of the machine size (small machines are used only because they allow us to calculate all of them up to a small size) and relies only on the concept of algorithmic probability. The result is a novel approach that we put forward for numerically calculate the complexity of short strings as an alternative to the indirect method using compression algorithms.

Afin de mieux comprendre le fonctionnement d'un système biologique, il est nécessaire d'étudier les différentes entités qui le composent. Pour cela, on peut modéliser ces interactions biologiques sous la forme de graphes. Pour certains de ces graphes, les sommets sont colorés afin d'apporter une information supplémentaire sur la couleur qui leur est associée. Dans ce cadre, une problématique courante consiste à y rechercher un sous-graphe d'intérêt appelé motif. Dans la première partie de ce manuscrit, on présente un état de l'art d'un point de vue algorithmique sur le problème GRAPH MOTIF, qui consiste à rechercher des motifs dits fonctionnels dans ce type de graphes. La modélisation de systèmes biologiques sous la forme de graphes peut également être appliquée em spectrométrie de masse. Ainsi, on introduit le problème MAXIMUM COLORFUL ARBORESCENCE (MCA) dans le but de déterminer de novo la formule moléculaire de métabolites inconnus. Dans la deuxième partie de ce manuscrit, on réalise une étude algorithmique du problème MCA. Alors que MCA est algorithmiquement difficile à résoudre même dans des classes de graphes très contraintes, notre modélisation nous permet notamment d'obtenir de nouveaux algorithmes d'approximation dans ces mêmes classes, ainsi que de déterminer une nouvelle classe de graphes dans laquelle MCA se résout en temps polynomial. On montre également des résultats de complexité paramétrée pour ce problème, que l'on compare ensuite à ceux de la littérature sur des instances issues de données biologiques. / Ln order to better understand how a biological system works, it is necessary to study the interactions between the different entities that compose it. To this aim, these biological interactions can be modelled in the form of graphs. ln some of these graphs, the vertices are colored in order to provide additional information on the entity which is associated with them. ln this context, a common subproblem consists in searching for a subgraph of interest, called a motif, in these graphs. ln the first part of this manuscript, we present a state of the art from an algorithmical point of view of the GRAPH MOTIF problem, which consists in searching for so-called functional motifs in vertex-colored graphs. The modeling of biological systems in graphs form can also be applied in mass spectrometry. Thus, we introduce the MAXIMUM COLORFUL ARBORESCENCE problem (MCA) in order to de novo determine the molecular formula of unknown metabolites. ln the second part of this manuscript, we carry out an algorithmic study of the MCA problem. While MCA is algorithmically difficult to solve even in very constrained graph classes, our modeling allows us to obtain new approximation algorithms in these same classes, as well as to determine a new graph class in which MCA is solved in polynomial time. Parameterized complexity results for this problem are also shown, which are then compared to those in the literature on instances from biological data.

Modèles de développement, capitalisme et industrialisme sont de grandes dynamiques du risque par leur capacité à transformer le social. Au niveau des firmes, l’innovation continue et la concurrence obligent à l’ajustement permanent. Soumises aux propriétaires, les firmes se focalisent sur le risque financier. Les autres risques lui sont subordonnés. Les dynamiques internes du risque évoluent au rythme d’impératifs externes. La compétition justifie réductions de coûts et réorganisations déstabilisantes. La sécurité a pour objectif la limitation des conditions de réalisation des risques. Construction sociale complexe, la sécurité voit localement la fusion d’hommes, d’outils dans une organisation. Globalement, l’enjeu de la sécurité est la maîtrise du niveau de risque et son coût. Comme pour l’armateur du navire, la direction de l’unité possède les clés de la sécurité. Elle arbitre entre les budgets et joue la concurrence entre les territoires. En assurant l’impunité, l’équivalence et la non-discrimination, le droit international garantit une mise en concurrence de tous les États. Avec la Mondialisation, nous entrons dans l’ère de la sécurité de marché. La sécurité est vue comme un facteur de production. Dans la concurrence, les dirigeants l’intègrent dans leurs stratégies, notamment lors des choix d’implantation géographique et des répartitions budgétaires. En sélectionnant les participants, la direction produit une représentation univoque de la sécurité en phase avec ses paradigmes. La rénovation de la sécurité dans les unités productives se joue localement mais aussi globalement en découvrant les complexités des dynamiques du risque et de la construction de la sécurité. / Models of development, capitalism and industrialism are also big dynamics of risk by their ability altering social world. At the level of firms, innovation and competition requires ongoing adjustment. Subject to their owners, companies focus on financial risk. Other risks are subordinate to the primary target. The dynamics of risk are changing the firm at the rate of external demands. The competition justifies harmful cost reductions and destabilizing re-engineering. The aim of safety is to reduce the uprising conditions of risk. Safety is a complex social building. Locally, safety seems a melt of man and tools within an organization. Overall, control of the safety is a challenge between risk and cost in the unit. Between cost and efficiency, management makes its own choice. As the shipowner and his vessel, the factory management has the keys to safety. It arbitrates between budgets and plays competition between territories. Ensuring impunity, equivalence and non-discrimination, international law guarantees competition between all States and flags. With globalization, we entered the era of the safety market. Safety is one of the production factors in global competition. Business leaders incorporate it into their overall strategies. With this factor in mind they choose their factories geographical location but also the allocation of budgets inside the firm. In selecting safety participants, the Executive create a unique picture of what safety is that corresponds to their paradigms. The rebuilding of safety in production units is played locally but also globally and by discovering the complexities of the dynamics of risk and the way of building safety.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Complexity theory helps us predict and control resources, usually time and space, consumed by programs. Static analysis on specific syntactic criterion allows us to categorize some programs. A common approach is to observe the program’s data’s behavior. For instance, the detection of non-size-increasing programs is based on a simple principle : counting memory allocation and deallocation, particularly in loops. This way, we can detect programs which compute within a constant amount of space. This method can easily be expressed as property on control flow graphs. Because analyses on data’s behaviour are syntactic, they can be done at compile time. Because they are only static, those analyses are not always computable or easily computable and approximations are needed. “Size-Change Principle” from C. S. Lee, N. D. Jones et A. M. Ben-Amram presented a method to predict termination by observing resources evolution and a lot of research came from this theory. Until now, these implicit complexity theories were essentially applied on more or less toy languages. This thesis applies implicit computational complexity methods into “real life” programs by manipulating intermediate representation languages in compilers. This give an accurate idea of the actual expressivity of these analyses and show that implicit computational complexity and compilers communities can fuel each other fruitfully. As we show in this thesis, the methods developed are quite generals and open the way to several new applications. / La théorie de la complexité´e s’intéresse à la gestion des ressources, temps ou espace, consommés par un programmel ors de son exécution. L’analyse statique nous permet de rechercher certains critères syntaxiques afin de catégoriser des familles de programmes. L’une des approches les plus fructueuses dans le domaine consiste à observer le comportement potentiel des données manipulées. Par exemple, la détection de programmes “non size increasing” se base sur le principe très simple de compter le nombre d’allocations et de dé-allocations de mémoire, en particulier au cours de boucles et on arrive ainsi à détecter les programmes calculant en espace constant. Cette méthode s’exprime très bien comme propriété sur les graphes de flot de contrôle. Comme les méthodes de complexité implicite fonctionnent à l’aide de critères purement syntaxiques, ces analyses peuvent être faites au moment de la compilation. Parce qu’elles ne sont ici que statiques, ces analyses ne sont pas toujours calculables ou facilement calculables, des compromis doivent être faits en s’autorisant des approximations. Dans le sillon du “Size-Change Principle” de C. S. Lee, N. D. Jones et A. M. Ben-Amram, beaucoup de recherches reprennent cette méthode de prédiction de terminaison par observation de l’évolution des ressources. Pour le moment, ces méthodes venant des théories de la complexité implicite ont surtout été appliquées sur des langages plus ou moins jouets. Cette thèse tend à porter ces méthodes sur de “vrais” langages de programmation en s’appliquant au niveau des représentations intermédiaires dans des compilateurs largement utilises. Elle fournit à la communauté un outil permettant de traiter une grande quantité d’exemples et d’avoir une idée plus précise de l’expressivité réelle de ces analyses. De plus cette thèse crée un pont entre deux communautés, celle de la complexité implicite et celle de la compilation, montrant ainsi que chacune peut apporter à l’autre.

Cette thèse étudie les mécanismes qui entrent en action dans le développement du pouvoir d’agir des individus en situation de vulnérabilité. À cette fin, nous nous appuyons d’une part sur des travaux en sociologie, philosophie, linguistique, et d’autre part sur notre expérience professionnelle dans le domaine du socio-éducatif (expérience retransmise et analysée ici via un récit d’investigation professionnelle), qui nous a permis de recueillir le témoignage de praticiens et de patients. L’auteure a ainsi procédé à douze échanges conversationnels avec des personnes en situation de handicap et de précarité. Ces entretiens sont retranscrits en annexe dans le tome II de cette thèse, tandis que le tome I procède à leur analyse avec les outils de la recherche biographique (socianalyse issue de l’analyse institutionnelle, étude via les catégories de Walter R. Heinz : des grilles d’analyses adaptées par Christine Delory-Momberger). Nous montrons aussi comment un tiers-lieu, un groupe d’échanges de pratiques, a été utilisé pour « déplier la complexité », au sens d’Edgar Morin, de l’approche biographique et de la question de l’implication du chercheur. Les intrications entre pouvoir d’agir et reconnaissance se retrouvent incarnées,au sein de cette recherche, par l’ensemble des personnes dont nous analysons les entretiens. À cette occasion, nous revisitons notamment les réflexions de Blaise Pascal,Hegel, Hannah Arendt, et les travaux de Paul Ricoeur, d’Axel Honneth et d’Emmanuel Renault. Cette démarche théorique s’est doublée de deux interactions concrètes avec la caisse primaire d’assurance maladie et avec un foyer d’accueil de personnes handicapées : nous illustrons comment, via la jonction de nos considérations universitaires et de notre sensibilité de praticienne dans le social, nous avons pu amener ces deux institutions à modifier leur approche, leur regard. / This PhD thesis studies the mechanisms which play a role in the development of the empowerment of people in a vulnerable situation. To this end, we base our approach on previous works in sociology, philosophy, linguistics, and also on our professional experiences in the socio-educative area which allowed us to collect testimonies of social workers and their patients.The author thus proceeded to twelve conversational exchanges with people with disabilities or in situations of precariousness. These exchanges are transcribed into an annex, which constitutes the second volume of this thesis, while the first volume provides their analysis via biographical research tools (socianalysis stemming from institutional analysis, analysis via Walter R. Heinz's categories : an analysis framework adapted by Christine Delory-Momberger). What is more, our experience is summarized and analyzed here via a professional investigation narrative account. We also show how a « Third Place » (a group of exchanges of practices) was used in order to, to quote Edgar Morin, « unfold the complexity » of the biographical approach and of the issue of the researcher’s implication.The entanglements between empowerment and social recognition are here embodied, in this research, by each person we interviewed. On this occasion, we revisit in particular some thoughts by Blaise Pascal, Hegel, Hannah Arendt, and the works of Paul Ricoeur, Axel Honneth, and Emmanuel Renault. This theoretical approach is accompanied by two concrete interactions with the CPAM (the main institution of the French Health System) and a group home for people with disabilities : We illustrate how, via the junction of our university point of view and our sensibility as a social worker, we have been able to convince these two institutions to adapt their approach and their perspectives.

Dans la pratique, énormément de problèmes concrets peuvent être modélisés par un graphe. Par exemple, une carte géographique est typiquement un graphe dans lequel on serait amener à chercher des chemins courts entre les villes, ou à passer par toutes les routes ou toutes les villes.... Cela explique pourquoi la théorie des graphes est certainement le domaine le plus populaire des mathématiques discrètes malgré son jeune âge....

Cette recherche en Sciences de l'Education est placée sur le champ de la conception et de l'ingénierie des formations d'ingénieurs scientifiques et techniques afin de comprendre en quoi les pratiques pédagogiques peuvent être liées au mode de pilotage d'une école. Cette relation entre deux actions, direction et enseignement, appartient à une vision qualifiée de complexe, c'est-à-dire visant à observer les interactions entre les phénoménes et à les modéliser. La problématique de cette recherche a ainsi voulu explorer en quoi les actions mises en place pour l'organisation d'une école d'ingénieurs (niveau méso) étaient reliées aux actions développées au niveau micro (c'est-à-dire les dynamiques pédagogiques portées par les enseignants comme les étudiants) ? La combinaison de plusieurs méthodologies, attachées à la fois à une observation participante, une écoute active dans le cadre d'entretiens et une démarche d'action-recherche, nous a permis de construire une stratégie de recherche. / This research in education sciences is focused on the conception and design of scientific and technique engineering programme training. The main objective is to understand in which way the pedagogical practices can be connected with the school management. The relation between the top management and teaching activities is complex. We envisage watching these interactions and modeling it. The objective of this research is thus oriented to the study of the interactions between school management (meso level) and the actions developed at a micro level (meaning pedagogic dynamics). The research strategy is made of several methodologies such as participative observation, active Iistening during interviews and an action - research approach.

Cette thèse étudie des formalismes logiques exprimant des propriétés sur des programmes. L'intention originale de ces logiques est de vérifier formellement la correction de programmes manipulant des pointeurs. Dans l'ensemble, il ne sera pas proposé de méthode de vérification applicable dans cette thèse- nous donnons plutôt un éclairage nouveau sur la logique de séparation, une logique pour triplets de Hoare. Pour certains fragments essentiels de cette logique, la complexité et la décidabilité du problème de la satisfiabilité n'étaient pas connus avant ce travail. Aussi, sa combinaison avec certaines autres méthodes de vérification était peu étudiée. D'une part, dans ce travail nous isolons l'opérateur de la logique de séparation qui la rend indécidable. Nous décrivons le pouvoir expressif de cette logique, en la comparant à des logiques du second ordre. D'autre part, nous essayons d'étendre des fragments décidables de la logique de séparation avec la une logique temporelle et avec l'aptitude à décrire les données. Cela nous permet de donner des limites à l'utilisation de la logique de séparation. En particulier, nous donnons des limites à la création de logiques décidables utilisant ce formalisme combiné à une logique temporelle ou à l'aptitude à décrire les données. / This thesis studies logics which express properties on programs. These logics were originally intended for the formal verification of programs with pointers. Overall, no automated verification method will be proved tractable here- rather, we give a new insight on separation logic. The complexity and decidability of some essential fragments of this logic for Hoare triples were not known before this work. Also, its combination with some other verification methods was little studied. Firstly, in this work we isolate the operator of separation logic which makes it undecidable. We describe the expressive power of this logic, comparing it to second-order logics. Secondly, we try to extend decidable subsets of separation logic with a temporal logic, and with the ability to describe data. This allows us to give boundaries to the use of separation logic. In particular, we give boundaries to the creation of decidable logics using this logic combined with a temporal logic or with the ability to describe data.