Résumé : Ce mémoire porte sur l’étude de la complexité du problème du décodage des codes stabilisateurs quantiques. Les trois premiers chapitres introduisent les notions nécessaires pour comprendre notre résultat principal. D’abord, nous rappelons les bases de la théorie de la complexité et illustrons les concepts qui s’y rattachent à l’aide d’exemples tirés de la physique. Ensuite, nous expliquons le problème du décodage des codes correcteurs classiques. Nous considérons les codes linéaires sur le canal binaire symétrique et nous discutons du célèbre résultat de McEliece et al. [1]. Dans le troisième chapitre, nous étudions le problème de la communication quantique sur des canaux de Pauli. Dans ce chapitre, nous introduisons le formalisme des codes stabilisateurs pour étudier la correction d’erreur quantique et mettons en évidence le concept de dégénérescence. Le problème de décodage des codes stabilisateurs quantiques négligeant la dégénérescence est appelé «quantum maximum likelihood decoding»(QMLD). Il a été démontré que ce problème est NP-complet par Min Hseiu Heish et al., dans [2]. Nous nous concentrons sur la stratégie optimale de décodage, appelée «degenerate quantum maximum likelihood decoding »(DQMLD), qui prend en compte la présence de la dégénérescence et nous mettons en évidence quelques instances pour lesquelles les performances de ces deux méthodes diffèrent drastiquement. La contribution principale de ce mémoire est de prouver que DQMLD est considérablement plus difficile que ce que les résultats précédents indiquaient. Dans le dernier chapitre, nous présentons notre résultat principal (Thm. 5.1.1), établissant que DQMLD est #P-complet. Pour le prouver, nous démontrons que le problème de l’évaluation de l’énumérateur de poids d’un code linéaire, qui est #P-complet, se réduit au problème DQMLD. Le résultat principal de ce mémoire est présenté sous forme d’article dans [3] et est présentement considéré pour publication dans IEEE Transactions on Information Theory. Nous montrons également que, sous certaines conditions, les résultats de QMLD et DQMLD coïncident. Il s’agit d’une amélioration par rapport aux résultats obtenus dans [4, 5]. // Abstract : This thesis deals with the study of computational complexity of decoding stabilizer codes. The first three chapters contain all the necessary background to understand the main result of this thesis. First, we explain the necessary notions in computational complexity, introducing P, NP, #P classes of problems, along with some examples intended for physicists. Then, we explain the decoding problem in classical error correction, for linear codes on the binary symmetric channel and discuss the celebrated result of Mcleicee et al., in [1]. In the third chapter, we study the problem of quantum communication, over Pauli channels. Here, using the stabilizer formalism, we discuss the concept of degenerate errors. The decoding problem for stabilizer codes, which simply neglects the presence of degenerate errors, is called quantum maximum likelihood decoding (QMLD) and it was shown to be NP-complete, by Min Hseiu Heish et al., in [2]. We focus on the problem of optimal decoding, called degenerate quantum maximum likelihood decoding (DQMLD), which accounts for the presence of degenerate errors. We will highlight some instances of stabilizer codes, where the presence of degenerate errors causes drastic variations between the performances of DQMLD and QMLD. The main contribution of this thesis is to demonstrate that the optimal decoding problem for stabilizer codes is much harder than what the previous results had anticipated. In the last chapter, we present our own result (in Thm. 5.1.1), establishing that the optimal decoding problem for stabilizer codes, is #P-complete. To prove this, we demonstrate that the problem of evaluating the weight enumerator of a binary linear code, which is #P-complete, can be reduced (in polynomial time) to the DQMLD problem, see (Sec. 5.1). Our principal result is also presented as an article in [3], which is currently under review for publication in IEEE Transactions on Information Theory. In addition to the main result, we also show that under certain conditions, the outputs of DQMLD and QMLD always agree. We consider the conditions developed by us to be an improvement over the ones in [4, 5].

English follows La mondialisation et l’interconnectivité ont suscité de nouvelles formes de traduction parmi lesquelles la traduction collaborative en ligne effectuée à des fins activistes. L’étude porte sur les traductions produites par Translating the printemps érable, une initiative de traduction collaborative qui visait à mieux informer la population anglo-canadienne sur le mouvement étudiant québécois de 2012 qualifié de « Printemps érable ». Ce réseau des traductions et des réactions qu’elles ont engendrées chez les internautes présente des modalités formelles et discursives dont la complexité échappe aux modèles de traduction conventionnels. Emprunté à la théorie des réseaux sociaux, le concept de sociogramme (Moreno) a d’abord permis de cartographier les trajectoires des traductions directes et de leurs dérivations (republications intégrales ou modifiées, commentaires) faisant ainsi apparaître deux types de réseaux : primaire et secondaire. Une analyse préliminaire identifie l’auteur, le genre et le sujet des textes source et des textes cible ainsi que les réactions et interactions des internautes. L’étude porte ensuite sur le discours proprement dit. Elle fait apparaître la prise de position des agents dans le passage progressif d’une revendication étudiante à un mouvement de société. Cette évolution se matérialise dans un nouveau vocabulaire. En éclairant le rôle de la connectivité dans l’évolution des pratiques de traduction, l’étude constitue un apport à la théorie des réseaux sociaux, à la théorie de la complexité (en particulier de la reliance selon Edgar Morin) ainsi qu’à l’application traductologique de cette approche. Suivant les principes du mouvement lent l’étude montre aussi que les nouveaux phénomènes de traduction activiste 2.0 peuvent être le vecteur d’une repolitisation à caractère participatif ayant en vue un nouveau modèle de société. Globalization and interconnectivity have given rise to new forms of translation including online activist collaborative translation. This study examines translations produced by Translating the printemps érable, a collaborative translation initiative whose aim was to better inform the Anglo-Canadian population about the Quebec student movement of 2012, dubbed the “Printemps érable” (Maple Spring). This network of translations and the reactions they triggered from Internet users presents formal and discursive modalities whose complexity goes beyond conventional translation models. Borrowed from social network theory, the sociogram concept (Moreno) made it possible to map the trajectories of direct translations and their derivations (unedited or modified republications, and comments), revealing two types of networks, namely, primary, and secondary. A preliminary analysis identifies the author(s), genre, and topic of the source and target texts as well as the reactions and interactions of the readers. The study then addresses the actual discourse. It reveals the positions taken by the agents and the gradual transition from student demands to a social movement. This evolution is materialized in a new vocabulary. By shedding light on the role of connectivity in the evolution of translation practice, the study contributes to social network theory, complexity theory (notably Edgar Morin’s notion of rebinding), as well as to their application to translation studies. In keeping with the principles of Slow Movement, the study also shows that the new activist translation 2.0 phenomenon can be a vehicle for a participatory repoliticisation with a view to a new model of society.

Ce travail a été développé dans le cadre du projet européen FACETS-ITN, dans le domaine des Neurosciences Computationnelles. Son but est d'améliorer la compréhension des réseaux de neurones stochastiques de taille finie, pour des sources corrélées à caractère aléatoire et pour des matrices de connectivité biologiquement réalistes. Ce résultat est obtenu par l'analyse de la matrice de corrélation du réseau et la quantification de la capacité de codage du système en termes de son information de Fisher. Les méthodes comprennent diverses techniques mathématiques, statistiques et numériques, dont certaines ont été importés d'autres domaines scientifiques, comme la physique et la théorie de l'estimation. Ce travail étend de précédents résultats fondées sur des hypothèses simplifiées qui ne sont pas réaliste d'un point de vue biologique et qui peuvent être pertinents pour la compréhension des principes de travail liés cerveau. De plus, ce travail fournit les outils nécessaires à une analyse complète de la capacité de traitement de l'information des réseaux de neurones, qui sont toujours manquante dans la communauté scientifique.

Il a été observé que l'exécution des heuristiques de recherche aléatoire dépend d'un ou de plusieurs paramètres. Un certain nombre de résultats montrent un avantage des paramètres dynamiques, c'est-à-dire que les paramètres de l'algorithme sont modifiés au cours de son exécution. Dans ce travail, nous montrons que la complexité de la boîte noire sans biais de la classe de fonction de référence OneMax est $n ln(n) - cn pm o(n)$ pour une constante $c$ comprise entre $0.2539$ et $0.2665$. L'exécution peut être réalisé avec un algorithme simple de type-(1+1) utilisant une puissance de mutation fitness dépendant. Une fois traduite dans le cas du budget fixe, notre algorithme trouve des solutions plus proches de l'optimum de 13% que celles des meilleurs algorithmes connus.Basé sur la puissance de mutation optimale analysée pour OneMaX, nous montrons qu'un choix auto-ajusté du nombre de bits à retourner atteint le même temps d'exécution (excepté $o(n)$ termes inférieurs) et le même (asymptotique) 13% amélioration de la fitness-distance par rapport au RLS. Le mécanisme d'ajustement doit apprendre de manière adaptative la puissance de mutation actuellement optimale des itérations précédentes. Cela vise à la fois à exploiter le fait que des problèmes généralement différents peuvent nécessiter des puissances de mutation différentes et que, pour un problème fixe, différentes puissances peuvent devenir optimales à différentes étapes du processus d'optimisation.Nous étendons ensuite notre stratégie d'auto-ajustement aux algorithmes évolutifs basés sur la population dans des espaces discrets de recherche. Grosso modo, il consiste à créer la moitié de la descendance avec un taux de mutation qui est deux fois plus élevé que le taux de mutation actuel et l'autre moitié avec la moitié du taux actuel. Le taux de mutation est ensuite mis à jour au taux utilisé dans cette sous-population qui contient la meilleure descendance. Nous analysons comment l'algorithme d'évolution $(1+lambda)$ avec ce taux de mutation auto-ajustable optimise la fonction de test OneMax. Nous montrons que cette version dynamique de $(1+lambda)$~EA trouve l'optimum dans un temps d'optimisation attendu (nombre d'évaluations de la fitness) de $O(nlambda/loglambda+nlog n)$. Le temps est asymptotiquement plus petit que le temps d'optimisation de l'EA classique $(1+lambda)$. Des travaux antérieurs montrent que cette performance est la meilleure possible parmi tous les algorithmes de boîtes noires sans biais unaire basés sur des mutations $lambda$-parallèles.Nous proposons et analysons également une version auto-réglage de l'algorithme évolutionnaire $(1,lambda)$ dans lequel le taux de mutation actuel fait partie de l'individu et donc également sujet à mutation. Une analyse d'exécution rigoureuse sur la fonction de référence OneMax révèle qu'un simple schéma de mutation pour le taux conduit à un temps d'optimisation attendu du meilleur $O(nlambda/loglambda+nlog n)$. Notre résultat montre que l'auto-réglage dans le calcul évolutif peut trouver automatiquement des paramètres optimaux complexes. En même temps, cela prouve qu'un schéma d'auto-ajustement relativement compliqué pour le taux de mutation peut être remplacé par notre schéma endogène simple. / It has been observed that the runtime of randomized search heuristics depend on one or more parameters. A number of results show an advantage of dynamic parameter settings, that is, the parameters of the algorithm are changed during its execution. In this work, we prove that the unary unbiased black-box complexity of the OneMax benchmark function class is $n ln(n) - cn pm o(n)$ for a constant $c$ which is between $0.2539$ and $0.2665$. This runtime can be achieved with a simple (1+1)-type algorithm using a fitness-dependent mutation strength. When translated into the fixed-budget perspective, our algorithm finds solutions which are roughly 13% closer to the optimum than those of the best previously known algorithms.Based on the analyzed optimal mutation strength for OneMax, we show that a self-adjusting choice of the number of bits to be flipped attains the same runtime (apart from $o(n)$ lower-order terms) and the same (asymptotic) 13% fitness-distance improvement over RLS. The adjusting mechanism is to adaptively learn the currently optimal mutation strength from previous iterations. This aims both at exploiting that generally different problems may need different mutation strengths and that for a fixed problem different strengths may become optimal in different stages of the optimization process.We then extend our self-adjusting strategy to population-based evolutionary algorithms in discrete search spaces. Roughly speaking, it consists of creating half the offspring with a mutation rate that is twice the current mutation rate and the other half with half the current rate. The mutation rate is then updated to the rate used in that subpopulation which contains the best offspring. We analyze how the $(1+lambda)$ evolutionary algorithm with this self-adjusting mutation rate optimizes the OneMax test function. We prove that this dynamic version of the $(1+lambda)$~EA finds the optimum in an expected optimization time (number of fitness evaluations) of $O(nlambda/loglambda+nlog n)$. This time is asymptotically smaller than the optimization time of the classic $(1+lambda)$ EA. Previous work shows that this performance is best-possible among all $lambda$-parallel mutation-based unbiased black-box algorithms.We also propose and analyze a self-adaptive version of the $(1,lambda)$ evolutionary algorithm in which the current mutation rate is part of the individual and thus also subject to mutation. A rigorous runtime analysis on the OneMax benchmark function reveals that a simple local mutation scheme for the rate leads to an expected optimization time of the best possible $O(nlambda/loglambda+nlog n)$. Our result shows that self-adaptation in evolutionary computation can find complex optimal parameter settings on the fly. At the same time, it proves that a relatively complicated self-adjusting scheme for the mutation rate can be replaced by our simple endogenous scheme.

No description available.

Ce travail a été développé dans le cadre du projet européen FACETS-ITN, dans le domaine des Neurosciences Computationnelles. Son but est d’améliorer la compréhension des réseaux de neurones stochastiques de taille finie, pour des sources corrélées à caractère aléatoire et pour des matrices de connectivité biologiquement réalistes. Ce résultat est obtenu par l’analyse de la matrice de corrélation du réseau et la quantification de la capacité de codage du système en termes de son information de Fisher. Les méthodes comprennent diverses techniques mathématiques, statistiques et numériques, dont certaines ont été importés d’autres domaines scientifiques, comme la physique et la théorie de l’estimation. Ce travail étend de précédents résultats fondées sur des hypothèses simplifiées qui ne sont pas réaliste d’un point de vue biologique et qui peuvent être pertinents pour la compréhension des principes de travail liés cerveau. De plus, ce travail fournit les outils nécessaires à une analyse complète de la capacité de traitement de l’information des réseaux de neurones, qui sont toujours manquante dans la communauté scientifique. / The brain is the most complex system in the known universe. Its nested structure with small-world properties determines its function and behavior. The analysis of its structure requires sophisticated mathematical and statistical techniques. In this thesis we shed new light on neural networks, attacking the problem from different points of view, in the spirit of the Theory of Complexity and in terms of their information processing capabilities. In particular, we quantify the Fisher information of the system, which is a measure of its encoding capability. The first technique developed in this work is the mean-field theory of rate and FitzHugh-Nagumo networks without correlations in the thermodynamic limit, through both mathematical and numerical analysis. The second technique, the Mayer’s cluster expansion, is taken from the physics of plasma, and allows us to determine numerically the finite size effects of rate neurons, as well as the relationship of the Fisher information to the size of the network for independent Brownian motions. The third technique is a perturbative expansion, which allows us to determine the correlation structure of the rate network for a variety of different types of connectivity matrices and for different values of the correlation between the sources of randomness in the system. With this method we can also quantify numerically the Fisher information not only as a function of the network size, but also for different correlation structures of the system. The fourth technique is a slightly different type of perturbative expansion, with which we can study the behavior of completely generic connectivity matrices with random topologies. Moreover this method provides an analytic formula for the Fisher information, which is in qualitative agreement with the other results in this thesis. Finally, the fifth technique is purely numerical, and uses an Expectation-Maximization algorithm and Monte Carlo integration in order to evaluate the Fisher information of the FitzHugh-Nagumo network. In summary, this thesis provides an analysis of the dynamics and the correlation structure of the neural networks, confirms this through numerical simulation and makes two key counterintuitive predictions. The first is the formation of a perfect correlation between the neurons for particular values of the parameters of the system, a phenomenon that we term stochastic synchronization. The second, which is somewhat contrary to received opinion, is the explosion of the Fisher information and therefore of the encoding capability of the network for highly correlated neurons. The techniques developed in this thesis can be used also for a complete quantification of the information processing capabilities of the network in terms of information storage, transmission and modification, but this would need to be performed in the future.

No description available.

Dans cette thèse, nous explorons la complexité algorithmique de plusieurs problèmes issus de la génomique comparative, et nous apportons des solutions à certains de ces problèmes sous la forme d'algorithmes d'approximation ou paramétrés. Le dénominateur commun aux problèmes soulevés est la mise en commun d'informations génomiques provenant de plusieurs espèces dans le but de tirer des conclusions pertinentes pour l'étude de ces espèces. Les problèmes de tri par transpositions et de tri par inversions pré xes permettent de retrouver l'histoire évolutive des deux espèces. Les problèmes de distance exemplaire et de plus petite partition commune ont pour but de comparer deux génomes dans les cas algorithmiquement di ciles où chaque gène apparait avec plusieurs copies indistinguables dans le génome. En n, les problèmes d'extraction de bandes et de linéarisation visent à préciser ou corriger l'information génomique a n qu'elle soit plus pertinente pour des traitements ultérieurs. Les résultats principaux que nous présentons sont la NP-di culté des problèmes de tri (par transpositions et par inversions pré xes) dont la complexité est restée longtemps une question ouverte; une étude complète de la complexité du calcul des distances exemplaires; un algorithme paramétré pour le calcul de plus petite partition commune (avec un unique paramètre étant la taille de la partition); une étude à la fois large et approfondie des problèmes d'extraction de bandes et en n une nouvelle structure de données permettant de résoudre plus e cacement le problème de linéarisation.

Pour les opérateurs, les réseaux FTTH représentent à la fois la solution de référence pour répondre à la demande croissante de trafic fixe, et un investissement considérable dû à leur mise en place. Le but de ces travaux est d'assurer le déploiement de réseaux de qualité à moindre coût. Nous commençons à présenter les différents aspects de la planification de ces réseaux qui en font un problème complexe. La littérature concernée est abordée afin d'exhiber les nouveaux défis que nous relevons. Puis nous élaborons des stratégies permettant de trouver la meilleure solution dans différents contextes. Plusieurs politiques de maintenance ou d'utilisation du génie civil sont ainsi explorées. Les problèmes rencontrés sont analysés à la lumière de divers outils d'optimisation (programmation entière, inégalités valides, programmation dynamique, approximations, complexités, inapproximabilité...) que nous utilisons et développons selon nos besoins. Les solutions proposées ont été testées et validées sur des instances réelles, et ont pour but d'être utilisées par Orange / For operators, FTTH networks are the most widespread solution to the increasing traffic demand. Their layout requires a huge investment. The aim of this work is to ensure a cost effective deployment of quality networks. We start by presenting aspects of this network design problem which make it a complex problem. The related literature is reviewed to highlight the novel issues that we solve. Then, we elaborate strategies to find the best solution in different contexts. Several policies regarding maintenance or civil engineering use will be investigated. The problems encountered are tackled using several combinatorial optimization tools (integer programming, valid inequalities, dynamic programming, approximations, complexity theory, inapproximability…) which will be developed according to our needs. The proposed solutions were tested and validated on real-life instances, and are meant to be implemented in a network planning tool from Orange

Les systèmes de santé des pays en développement font face à de nombreux enjeux organisationnels pour améliorer l’état de santé de leur population. Au nombre de ces enjeux, il est fréquemment mentionné la présence d’organisations internationales ayant des objectifs et caractéristiques peu convergents et qui interviennent de façon non nécessairement coordonnée. Cette thèse explore la thématique de l’introduction du changement dans ces systèmes de santé en mettant un accent spécifique sur l’enjeu lié à la présence de ces organisations internationales. La méthodologie utilisée est une analyse de concept. Cette approche méthodologique consiste à effectuer des revues critiques de la littérature sur des concepts, à mobiliser de nouvelles approches théoriques pour clarifier ces concepts et à réaliser des études de cas pour leur mise à l’épreuve empirique. En nous appuyant sur la théorie de l’action sociale de Parsons, la théorie de la complexité ainsi que les expériences d’introduction du changement dans différents systèmes de santé, nous avons développé un cadre théorique d’analyse de l’introduction du changement dans les systèmes de santé des pays en développement (1er concept). Ce cadre théorique, qui suggère de concevoir le processus d’introduction du changement comme un système d’action sociale complexe et émergent, a été appliqué à l’analyse de l’introduction d’un système de surveillance épidémiologique en Haïti. Plus précisément, nous avons analysé une étape ainsi que certains aspects du mécanisme sous-jacent au processus d’introduction du changement. Ce faisant, nous avons analysé, dans les deux premiers articles de la thèse, l’étape d’adoption du système de surveillance épidémiologique (2ème concept) ainsi que les déterminants de la collaboration entre les organisations impliquées dans le processus d’introduction du changement (3ème concept). Les résultats de ces analyses nous ont permis d’objectiver de faibles niveaux d’adoption, ainsi qu’une faible articulation des déterminants de la collaboration entre les différentes organisations impliquées dans le processus d’introduction du changement. Partant de ces constats, nous avons pu mettre en évidence, dans le troisième article, une phase de « chaos » dans le fonctionnement du système de santé d’Haïti. Cette phase de « chaos », qui pourrait expliquer les difficultés liées à l’introduction du changement dans les systèmes de santé des pays en développement en général et plus particulièrement en Haïti, était caractérisée par la présence d’un ordre sous-jacent au désordre apparent dans le fonctionnement de certaines composantes du système de santé d’Haïti, l’existence d’une instabilité, d’une imprédictibilité ainsi que d’une invariance structurelle aux différents niveaux de gouvernance. Par ailleurs, cette recherche a également permis de démontrer que les caractéristiques du « chaos » sont entretenues par la présence de trois groupes de systèmes d’action sociale bien articulés et bien cohérents à tous les échelons de la pyramide sanitaire en Haïti. Il s’agissait des systèmes d’action liés aux agences de coopération bilatérale, ceux liés aux initiatives ou fondations internationales de lutte contre le sida et finalement ceux associés aux organisations onusiennes. Ces systèmes d’action sociale sont en outre associés à d’autres systèmes d’action plus complexes qui sont situés à l’extérieur du système de santé d’Haïti. Au regard de ces résultats, nous avons proposé une nouvelle approche permettant de mieux appréhender l’introduction du changement dans les systèmes de santé des pays en développement et qui s’inscrit dans une logique permettant de favoriser une plus grande variété et une plus grande diversification. Cette variété et cette diversification étant soutenue par la création et la mise en place de plusieurs interconnections entre tous les systèmes d’action en présence dans les systèmes de santé qu’ils soient d’appartenance nationale, internationale ou qu’ils agissent au niveau central, départemental ou local. La finalité de ce processus étant l’émergence de propriétés systémiques issues non seulement des propriétés des groupes de systèmes d’action individuels qui interviennent dans la constitution du système émergent, mais aussi d’autres propriétés résultant de leur mise en commun. / In an attempt to improve the health status of their population, health care systems in developing countries face several organizational issues. These issues include the presence of international organizations with different goals and characteristics, as well as little convergence and poor coordination. While focussing on this specific issue, the objective of this dissertation is to deeply explore the issues related to the process of introducing change in health care systems of developing countries. The research method for this study is a concept analysis that requires a literature review, the use of new theories to clarify these concepts as well as the use of case studies to empirically validate these concepts. Using Parsons’s social action theory and the complexity theory, a new theory of change (1st concept) was developed and applied to the process of introduction of an epidemiological surveillance system in Haiti. More specifically, in the first two articles, we have analysed the process of adopting the epidemiological surveillance system (2nd concept) and the determinants of collaboration among the different organizations involved in the change process (3rd concept). The results from these two articles enabled us to highlights the low level of adoption as well as the weak articulation of the determinants of collaborations between the various organizations involved in the change process. From these analyses, we were able to highlights the dynamics of chaos operating in Haiti’s health care system in the third article. This chaos stage which could enable us to show the difficulties associated with the introduction of change in health systems in developing countries in general, and Haiti in particular, was characterized by a hidden order underlying an apparent disorder in the operation of certain components of the Haitian’s health system, the existence of instability, unpredictability as well as structural invariance at various levels of governance. Moreover, this research also enabled us to show that these characteristics are maintained by the presence of three well articulated and coherent social action systems at all levels of the health pyramid. They are those related to bilateral cooperation agencies, those related to international foundations and global initiatives fighting against AIDS, and finally those associated with the United Nations Organizations. These social action systems are also associated with other more complex systems outside the Haiti’s health system. On the basis of these results, we proposed a new approach to understand the process of introducing change in health care systems of developing countries that would fit into the logic that supports the setting up a larger interconnections and diversification among various organizations involved.