Cette thèse est une étude de la géométrie de l'interaction dans le facteur hyperfini (GdI5), introduite par Jean-Yves Girard, et de ses liens avec les constructions plus anciennes. Nous commençons par montrer comment obtenir des adjonctions purement géométriques comme une identité entre des ensembles de cycles apparaissant entre des graphes. Il est alors possible, en choisis- sant une fonction qui mesure les cycles, d'obtenir une adjonction numérique. Nous montrons ensuite comment construire, sur la base d'une adjonction numérique, une géométrie de l'interaction pour la logique linéaire multiplicative additive où les preuves sont interprétées par des graphes. Nous expliquons également comment cette construction permet de définir une sémantique dénotationnelle de MALL, et une notion de vérité. Nous étudions finalement une généralisation de ce cadre utilisant des outils de théorie de la mesure afin d'interpréter les exponentielles et le second ordre. Les constructions sur les graphes étant paramétrées par une fonction de mesure des cycles, nous entreprenons ensuite l'étude de deux cas particuliers. Le premier s'avère être une version combinatoire de la GdI5, et nous obtenons donc une interprétation géométrique de l'orthogonalité basée sur le déterminant de Fuglede-Kadison. Le second cas particulier est une version combinatoire des constructions plus anciennes de la géométrie de l'interaction, où l'orthogonalité est basée sur la nilpotence. Ceci permet donc de comprendre le lien entre les différentes versions de la géométrie de l'interaction, et d'en déduire que les deux adjonctions -- qui semblent à première vue si différentes -- sont des conséquences d'une même identité géométrique. Nous étudions ensuite la notion de vérité subjective. Nous commençons par considérer une version légè- rement modifiée de la GdI5 avec une notion de vérité dépendant du choix d'une sous-algèbre maximale commutative (masa). Nous montrons qu'il existe une correspondance entre la classification des masas introduite par Dixmier (regulière, semi-régulière, singulière) et les fragments de la logique linéaire que l'on peut interpréter dans cette géométrie de l'interaction. Nous étudions alors la vérité subjective de la GdI5, qui dépends du choix d'une représentation du facteur hyperfini de type II1, à la lumière de ce résultat. Finalement, nous détaillerons une proposition de Girard pour étudier les classes de complexité et dé- taillons la caractérisation obtenue par ce dernier de la classe de complexité co-NL, en montrant comment coder un problème complet pour cette classe à l'aide d'opérateurs.

L'étude que nous proposons s'inscrit dans le cadre de la complexité implicite des calculs. Selon Daniel Leivant, il s'agit de donner des caractérisations de la complexité sans faire de référence explicite à un modèle de calcul. Nous montrons que les interprétations de programmes sont un bon outil d'analyse dans ce contexte. Les aspects théoriques et pratiques sont abordés.

La complexité de la communication a été introduite en 1979 par Andrew Chi-Chi Yao. Elle est depuis devenue l'un des modèles de calcul les plus étudiés. L'objectif de celle-ci est d'étudier des problèmes dont les entrées sont distribuées entre plusieurs joueurs, en quantifiant la communication que ceux-ci doivent échanger. Nous utilisons d'abord la complexité de Kolmogorov, une caractérisation algorithmique de l'aléatoire, pour prouver des bornes inférieures sur la complexité de la communication. Notre méthode constitue une généralisation de la méthode d'incompressibilité. L'avantage de cette approche est de mettre en valeur la nature combinatoire des preuves. Nous étudions ensuite la simulation des distributions de probabilité causales avec de la communication. Ce modèle généralise la complexité de la communication traditionnelle et comprend en particulier les distributions quantiques. Nous montrons pour ce problème des bornes inférieures et supérieures. Dans le cas des fonctions booléennes, la borne inférieure que nous proposons est équivalente aux normes de factorisation, une puissante méthode introduite par Linial et Shraibman en 2006. Enfin, nous étudions la complexité en boîte non-locale. Cette ressource a été introduite par Popescu et Rohrlich pour étudier la non-localité. Le problème est de quantifier le nombre de boîtes nécessaire et suffisant pour calculer une fonction ou simuler une distributions. Nous donnons encore des bornes inférieures et supérieures pour ces problèmes, ainsi que des applications à l'évaluation sécurisée, un problème cryptographique très important.

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].

Afin de lutter contre la baisse de la natalité et de favoriser la conciliation travail-famille, l’Europe a besoin de services de garde en quantité et qualité suffisantes (Commission Européenne, 2013). Or, la qualité des services auprès du jeune enfant dépend de la qualité de la formation professionnelle (OCDE, 2001). En France, aucun cursus et aucune profession ne sont spécifiquement et exclusivement destinés au travail éducatif en crèche (Odena, Daune-Richard et Petrella, 2009). L’Italie n’a aucun profil de compétences officiel ni au niveau de la formation ni au niveau de la profession (Vandenbroeck, 2011). Notre problème de recherche pointe le paradoxe entre d’un côté, un discours social injonctif à l’égard de la professionnalisation au niveau européen (Commission Européenne, 2011) et d’un autre côté, le peu de connaissances sur les pratiques éducatives dans les crèches européennes pouvant orienter la professionnalisation du personnel. Grâce à des entretiens semi-directifs sur la base de l’entretien compréhensif (Kaufmann, 2008) et une analyse à l’aide des "catégories conceptualisantes" (Paillé et Mucchielli, 2012), notre recherche se propose de comprendre l’activité du travail éducatif des professionnels en crèche. S’inscrivant dans la théorie de la complexité, cette recherche montre que comparer et relier les pratiques éducatives à leurs contextes macro, méso et micro (c'est-à-dire institutionnels, organisationnels et pédagogiques) permet de mieux comprendre la complexité de ces dernières

Dans cette thèse, nous étudions plusieurs problèmes de théorie des graphes concernant la coloration et la convexité des graphes. La plupart des résultats gurant ici sont liés à la complexité de calcul de ces problèmes pour certaines classes de graphes. Dans la première, et principale, partie de cette thèse, nous traitons de coloration des graphes qui est l'un des domaines les plus étudiés de théorie des graphes. Nous considérons d'abord trois problèmes de coloration appelés coloration gloutone, coloration pondérée et coloration pondérée impropre. Ensuite, nous traitons un probl ème de décision, appelé bon étiquetage de arêtes, dont la dé nition a été motivée par le problème d'affectation de longueurs d'onde dans les réseaux optiques. La deuxième partie de cette thèse est consacrée à un paramètre d'optimisation des graphes appelé le nombre enveloppe (géodésique). La dé nition de ce paramètre est motivée par une extension aux graphes des notions d'ensembles et d'enveloppes convexes dans l'espace Euclidien. En n, nous présentons dans l'annexe d'autres travaux développées au cours de cette thèse, l'un sur les hypergraphes orientés Eulériens et Hamiltoniens et l'autre concernant les systèmes de stockage distribués.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

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

La simplification du droit se traduit aujourd’hui par une politique volontariste mise en place par les pouvoirs publics qui se concrétise particulièrement par le biais de lois de simplification du droit. Cette politique cherche donc à réduire la complexité du droit a posteriori car elle vise à réécrire la législation et la réglementation existantes. Toutefois, il est possible, eu égard à la finalité de cette politique – l’amélioration de la qualité du droit –, d’envisager une acception originale de la simplification du droit consistant à prévenir la complexité du droit a priori, au stade de l’écriture du droit.Différents acteurs vont concourir à la réalisation de la simplification du droit. Parmi eux, une seule institution dispose de nombreux moyens pour en être la cheville ouvrière : le Conseil d’État. En effet, eu égard à la spécificité de ses attributions (dualité fonctionnelle, rôle de proposition, etc.) et à la place qu’il occupe au sein des institutions (en tant qu’institution mais aussi par le biais de ses membres qui irriguent les sphères décisionnelles), le Conseil d’État est un acteur de premier plan de la simplification du droit.Lorsque celle-ci est envisagée comme une politique volontariste des pouvoirs publics, le Conseil d’État joue un rôle central. D’une part, bénéficiant de l’expérience qu’il a acquise dans les travaux simplificateurs antérieurs à cette politique et par la place que ses membres occupent dans des structures qui concourent à la réalisation de cette politique, le Conseil d’État prend une part active dans la politique de simplification du droit. D’autre part, le choix initialement retenu de la simplification du droit par voie d’ordonnances lui a offert une place importante car les modalités de l’intervention du Conseil d’État sont nombreuses. En 2008, l’introduction dans la Constitution de la possibilité de solliciter l’avis du Conseil d’État sur les propositions de loi a permis à celui-ci de se replacer au cœur de la politique de simplification du droit. Toutefois, le rôle de l’institution est ambivalent. En effet, alors même qu’il influence le contenu des textes de simplification, le Conseil d’État porte des regards contradictoires sur cette politique publique.A l’égard de la seconde acception de la simplification du droit – la prévention de la complexité du droit –, l’effectivité de l’intervention du Conseil d’État est différente. Dans le cadre de la fonction consultative, alors même qu’il dispose de moyens efficaces pour prévenir la complexité du droit, le Conseil d’État n’est pas en définitive décisionnaire, et la complexité des procédures de décisions limite l’importance de son action. Dans le cadre de la fonction juridictionnelle, les interprétations et les règles jurisprudentielles tendent à accentuer la complexité du droit, ce qui soulève la question de l’amélioration de la qualité de la rédaction des décisions du Conseil d’État. / The simplification of law is expressed today by a voluntarist policy implemented by the public Authorities and it is particularly materialized by means of laws tending to simplify law. This policy thus aims at reducing the intricacy of law a posteriori because it aims at re-writing the existing legislation and regulation. However, it is possible, considering the purpose of this policy – the improvement of the quality of law -, to think of an original meaning of the simplification of law consisting in anticipating the intricacy of law a priori, at the level of the writing of law.Different actors are going to work towards the achievement of the simplification of law. Among them, only one institution has at its disposal many means to be the mainspring of it : the Council of State. Because, considering the specificity of its attributions (functional duality, role of proposal, etc…) and the place it occupies within the institutions (as institution but also by means of its members who irrigate the decision-making spheres) the Council of State is a key actor for the simplification of law.When this latter is considered as a voluntarist policy of the public Authorities, the Council of State plays an essential part. On the one hand, taking advantage of the experience it has acquired in the simplifying works priori to this policy and by the place its members occupy in some structures that work towards the achievement of this policy, the Council of State plays an active part in the policy of simplification of law. On the other hand, the initial choice of the simplification of law by edicts has offered the Council of State a significant place because the modes of the state intervention are numerous. In 2008, the insertion into the constitution of the possibility of asking the opinion of the Council of State about the private bills has entitled the latter to replace itself within the policy of simplification of law. However the role of the institution is ambivalent. Because, even though it influences the content of the texts of simplification, the Council of State has contradictory views on this public policy. Considering the second meaning of the simplification of law, the anticipation of the intricacy of law, the efficiency of the intervention of the Council of State is different. Within the framework of the consultative function, whereas it has efficient means to anticipate the intricacy of law, the Council of State eventually has no decision-making power and the intricacy of the procedures of decisions limits the significance of its action. Within the juridictional frame, the interpretation of the judicial precedents tend to emphasize the intricacy of law, which raises the question of the improvement of the quality of the writing of the Council of State decisions.

Le concept de décloisonnement, est élaboré à partir d'une réflexion sur la complexité des enjeux culturels, notamment, lorsqu'une pluralité de cultures, coexiste et se confronte dans un espace commun. L'étude, le développement et la discussion du décloisonnement sont issus d’une généalogie de la culture et des cultures dans l'histoire des idées, notamment à travers les Sophistes, Las Casas, Montaigne, Rousseau, Volney et Lévi-Strauss et par une analyse historique des concepts de nomos, coutume, et civilisation. Le décloisonnement est bâti autour de trois pôles : décentrement, pluralité et hiérarchie affaiblie ou reconfigurée. La pertinence du concept est testée en regard des rencontres interculturelles et de leurs significations. A partir d'observations historiques, sociologiques et philosophiques, le décloisonnement est rattaché à un cloisonnement initial dans un équilibre sous tension constante et nécessaire. Aux principes absolus du couple ouverture/fermeture est substitué le décloisonnement/cloisonnement. Les dynamiques étudiées sont inévitablement antagonistes et complémentaires. Les tensions, apories et contradictions rencontrées conduisent à l'élaboration d'une triple balance des concepts et aspects trans- inter- et multi- culturels. La triple balance pose la nécessité d'un équilibre entre la pluralité intérieure et la transculturalité dans une perspective de dialogues et de rencontres. La notion conclusive de proximétrie pose la recherche nécessaire d'une mesure des distances culturelles, d'où procède un art délicat du discernement d'un équilibre dans le décloisonnement culturel. / The concept of Dis-closure is based on a reflection on the complexity of cultural confrontations in an intercultural space. The study, development and discussion of the concept of Dis-closure stem from a genealogy of culture in the history of ideas, notably through the Sophists, Las Casas, Montaigne, Rousseau, Volney and Lévi-Strauss and by a historical analysis of the concepts of nomos, custom, and civilization. The Dis-closure is built around three poles: decentralization, plurality and hierarchy weakened or reconfigured. The relevance of the concept is tested in a selection of different cultural fields. On the basis of historical, sociological and philosophical observations, the Dis-closure is related to an initial partitioning in an equilibrium under constant and necessary tension. The absolute principles of Openness / Closeness are substituted with Dis-closure / Closure. The dynamics studied are inevitably antagonistic and complementary. The tensions, aporias and contradictions encountered lead to the development of a triple balance of trans-, Inter- and Multi-cultural poles. The triple balance raises the need for an equilibrum between inner plurality and transculturality in a perspective of dialogues and encounters. The conclusive notion of proximetry poses the necessary search for a measure of cultural distances, their degrees and qualities, from which proceeds a delicate art of discerning a balance in a cultural Dis-closed context.