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

Thèse effectuée en cotutelle avec l’Université de Montréal et l’Université Paris 1 Panthéon-Sorbonne (IHPST) / L’entropie est généralement considérée comme une propriété émergente, tandis que l’émergence de certaines structures organisées serait le résultat d’une dissipation d’entropie. Ainsi, l’émergence est parfois présentée comme ce qui expliquerait l’entropie alors que l’entropie expliquerait l’émergence. Tels quels, ces deux énoncés ne peuvent être tous deux vrais. Face à la polysémie déconcertante des concepts d’émergence, d’entropie et d’explication, je soutiens que cet apparent paradoxe peut être résolu formellement ainsi : l’émergence (en un sens A) explique (en un sens B) l’entropie (en un sens C) et l’entropie (en un sens D) explique (en un sens E) l’émergence (en un sens F). La solution revient donc à préciser A, B, C, D, E, et F. Pour ce faire, je propose un modèle pluraliste (restreint) de l’explication et un examen critique du concept d’entropie. Dans le cas de l’entropie comme explanandum de l’émergence (A, B et C), ce qui émerge est l’irréversibilité comme propriété essentielle de l’entropie thermodynamique, mais l’émergence ne peut être synonyme de non-explicabilité. Je montre alors trois possibilités où l’émergence peut expliquer l’entropie thermodynamique : selon (i) un sens fort, comme une modalité ontologique, (ii) selon un sens intermédiaire d’après ce que j’appelle l’émergence méthodologique (où il y a possibilité d’explication réductive sans réduction dérivationnelle), et (iii) selon un sens faible, comme sa désignation comme membre d’une classe d’émergents. Dans le cas de l’entropie comme explanans de l’émergence (D, E, et F), il faut distinguer l’approche substantielle de l’approche analogique. Dans le premier cas, l’entropie renvoie à une propriété macroscopique robuste et autonome pouvant être mobilisée au sein d’un explanans de l’émergence de nouvelles structures complexes. Dans le second cas, l’entropie exemplifie la réalisabilité multiple et peut être mobilisée, modulo une justification, au sein d’un explanans de l’émergence de propriétés à des niveaux supérieurs. En définitive, la polysémie de ces concepts peut être fructueuse au sein de ce cadre explicatif de phénomènes divers et complexes, de la physique à la biologie. / Entropy is generally considered as an emergent property, while the emergence of certain organized structures is supposed to be the result of entropy dissipation. Thus, emergence is sometimes seen as explaining entropy, whereas sometimes the explanation is the other way around, as entropy would explain emergence. As such both statements cannot be true. Faced with the daunting polysemy of these concepts of emergence, entropy and explanation, I argue that this apparent paradox can be formally solved as follows: the emergence (in a sense A) explains (in a sense B) entropy (in a sense, C) and entropy (in a sense D) explains (in a sense E) emergence (in a sense F). The solution is therefore to specify A, B, C, D, E, and F. To do this, I suggest a (restricted) pluralistic model of explanation and a critical examination of the concept of entropy. In the case of entropy as explanandum of emergence (A, B and C), what is emerging is irreversibility as an essential property of thermodynamic entropy, but it cannot be emergence of synonymous of non-explicability. I then show three possibilities that can explain the emergence of thermodynamic entropy: (i) in a strong sense, as an ontological modality, (ii) in an intermediate sense, from what I call ‘methodological emergence’ (where there is a possibility of reductive explanation but no derivational reduction), or (iii) in a weak sense, as its designation as a member of an emergence class. In the case of entropy as explanans of emergence (D, E, and F), one must distinguish the substantive approach from the analogical approach. In the first case, entropy refers to a robust and autonomous macroscopic property that can be mobilized in an explanans of the emergence of new complex structures. In the second case, the entropy exemplifies multiple realizability and can be mobilized, with a proper justification, within an explanans of the emergence of properties at higher levels. Ultimately, the polysemy of these concepts can be fruitful in this explanatory framework for various complex phenomena, from physics to biology.

Nous détaillons dans cette thèse des algorithmes modérément exponentiels pour l'approximation du problème MAX SAT. Nous discutons d'une méthode générique pour la conception d'algorithmes exponentiels réalisant des schémas d'approximation dans un cadre plus général. Enfin, nous présentons des résultats paramétrés pour des problèmes de coupe à cardinalité contrainte. / We give in this thesis some moderately exponential algorithms for the MAX SAT problem. We discuss a very general method to conceive efficient exponential algorithms that give approximation scheme. In the end, we present some parameterized results for CUT problem with constrained cardinality.

L'objectif de la thèse est de créer et développer de nouvelles méthodes de résolution efficaces des problèmes combinatoires en configuration des lignes de fabrication. Deux problèmes ont été particulièrement étudiés: le problème d'équilibrage et de choix d'équipement pour des lignes dédiées et le problème de minimisation des coûts de changements de séries pour des lignes multi-produits. Une solution du premier problème consiste en une affectation admissible des ressources à un nombre de stations à déterminer de sorte que le coût total soit minimal. Afin de résoudre ce problème, nous l'avons réduit au problème de partition d'ensemble et l'avons résolu par des heuristiques gloutonnes et une méthode exacte de génération de contraintes. Les expérimentations sur différentes instances ont montré que la nouvelle approche de résolution surclasse les approches antérieures de la littérature en termes de qualité de solution et de temps de calcul. Pour le second problème deux critères sont considérés lexicographiquement : la minimisation du nombre de stations et la minimisation du coût de changement de séries. Nous avons examiné successivement les cas d'exécution parallèle et séquentielle des opérations. Des solutions approchées ont été trouvées par des heuristiques gloutonnes. Ensuite, nous avons proposé deux modèles de programmation linéaire en nombres entiers (PLNE) afin de trouver le nombre de stations minimal et ensuite d'obtenir le coût de changement de séries minimal. Les résultats des expérimentations sur ces nouveaux problèmes se sont avérés prometteurs à la fois en termes de qualité de solution et de temps de calcul. / The objective of this thesis is to create and develop new effective solution methods for production line configuration problems. Two problems were studied: the equipment selection and balancing problem for dedicated lines and the setup cost minimization problem for multi-product lines. A solution for the first problem consists in a feasible assignment of the resources to an unknown number of stations so that the total cost is minimized. In order to solve this problem, we reduced it to the set partitioning problem and solved it by greedy heuristics and an exact method of constraint generation. The computer experiments on different problem instances showed that the new solution approach outperforms the previous methods from the literature both in terms of solution quality and computational time. For the second problem two criteria were considered lexicographically: the minimization of the number of stations and the minimization of the total setup cost. We examined successively the cases with parallel and sequential execution of operations. Approximate solutions were found by greedy heuristics. Then, we proposed two integer programming models in order to obtain the minimal number of stations and then the minimal setup cost. The experimental results for this new problem proved to be promising both in terms of solution quality and computational time.

Cette thèse est dédiée à l'étude des pavages : des ensembles de coloriages du plan discret respectant des contraintes locales données par un jeu de tuiles. Nous nous penchons en particulier sur les liens qui unissent les pavages et la calculabilité. Les pavages étant des ensembles effectivement clos particuliers, nous étudions dans un premier temps la structure des ensembles de degrés Turing des pavages, la comparant à celle des ensembles effectivement clos en général : pour tout ensemble effectivement clos il existe un pavage qui a les même degrés Turing à 0 près, le degré des ensembles récursifs. De plus les pavages ne contenant pas de membre récursif ont une structure particulière : ils contiennent toujours un cône de degrés Turing, un degré Turing et tous les degrés qui lui sont supérieurs. Dans un second temps, nous étudions les ensembles de périodes des pavages, pour diverses notions de périodicité, parvenant à des caractérisations à l'aide de classes de complexité ou de calculabilité pour chaque notion étudiée. Enfin nous nous intéressons à la difficulté calculatoire des problèmes de la factorisation et de la conjugaison, des notions de simulation et d'équivalence adaptées aux spécificités des pavages. / This thesis is dedicated to the study of subshifts of finite type (SFTs) : sets of colorings of the discrete plane which respect some local constraints given by a set of forbidden patterns. We study the links between SFTs and computation. SFTs being specific effectively closed classes, we fist study their Turing degree structure, comparing it to the one of effectively closed classes in general: for any effectively closed class, there exist an SFT having the same Turing degrees except maybe 0, the degree of recursive sets. Furthermore, SFTs containing no recursive member have a particular structure: they always contain a cone of Turing degrees, ie. a Turing degree and all degrees above it. We then study the sets of periods of SFTs, for different notions of periodicity, reaching characterizations by means of computational complexity classes or computability classes for each notion introduced. Finally we look at the computable hardness of the factorization and conjugacy problems, the right notions of simulation and equivalence for SFTs.

La modélisation en écologie est aujourd'hui une pratique scientifique de premier plan. Portée par l'avancement technologique, les modèles utilisés en sciences de l'environnement présentent une complexité grandissante. La complexification des modèles est une nécessité pour une variété d'études, mais elle peut être une source d'incompréhension, voire d'erreurs. Savoir gérer son implémentation apparaît donc nécessaire. Fort de ce constat, deux approches complémentaires se sont distinguées et furent étudiées dans ce travail de thèse. D'une part, il est possible de gérer la complexité a priori, en contraignant directement les hypothèses de construction et le formalisme du modèle par l'utilisation d'un cadre théorique. Une illustration de l'utilisation d'un schéma théorique, la théorie des Budgets Dynamiques d'Énergie, présente comment une description précise de l'effet des ultraviolets fut adjointe à un modèle de l'endosymbiose corallienne. Cette étude met en lumière leur possible rôle dans le blanchiment des coraux scléractiniaires. La gestion de la complexité pouvant aussi s'opérer a posteriori, c'est à dire une fois l'étape de construction passée. Ainsi, une méthodologie d'analyse statistique des sorties de modèles ayant pour but de permettre leur simplification fut établie. À titre d'exemple, cette méthode a été appliquée sur un modèle à micro-échelle de l'écosystème mésopélagique. Ne plus avoir la possibilité d'entreprendre une approche analytique de son modèle n'est donc pas une fatalité pour qui veut maitriser son outil, car une multitude d'approches permettent d'obtenir des informations toutes aussi intéressantes. / Ecological modelling is nowadays a leading topic. the models used in environmental science turn to be more and more complex. Driven by technological advancement, the models used in environmental sciences are increasingly complex. The complexity of models is a need for a variety of studies, but it can also be a source of misunderstanding, or even errors. How to manage its implementation is therefore necessary. With this in mind, two complementary approaches have been studied in this thesis. On the one hand, it is possible to manage the complexity textit a priori, by directly constraining the construction assumptions and formalism of the model using a theo- retical framework. An illustration of the use of a theoretical framework, the theory of Dynamic Energy Budgets, shows how an accurate description of the effect of ultraviolet was added to a model of scleractinian corals. This study enlightened their possible role in coral bleaching events. Managing complexity can also be carried out textit a posteriori, ie once the construc- tion phase is done. Thus, a simplification methodology using a statistical analysis of the model outputs was established . As an example, this method was applied on a micro- scale model of the mesopelagic ecosystem. Eventually, not being able of pursuing an analytical approach of the model is not inevitable for those who want to still mastering their model, it exists a multitude of tool who brings equally interesting informations.

Cette étude des pratiques RH dans les moyennes entreprises met en évidence l'influence significative des facteurs organisationnels et institutionnels. Dans le cadre de cette recherche, nous nous intéressons à ces pratiques à travers une approche intégratrice des théories mobilisées et montrons des particularismes en termes : 1/ de différenciation et d'hybridité structurelle, 2/ de légitimité institutionnelle et 3/ de complexité relationnelle.Reposant sur une méthodologie de recherche qualitative, l'étude empirique comprend 40 entretiens dont 13 menés dans le cadre de deux études de cas. Ces entretiens réalisés auprès de plusieurs acteurs RH permettent des comparaisons entre des moyennes entreprises de différentes tailles.À la lumière des spécificités des moyennes entreprises, nos résultats mettent en évidence une diversité des pratiques de RH. Notre recherche confirme l'intérêt d'une approche « non consensuelle » des pratiques de RH, celle-ci étant due au recul de la hiérarchie face à l'arrivée des managers. Nos résultats montrent aussi que dans les moyennes entreprises, les pratiques de RH sont personnelles, conformistes, pseudo-conformistes, pseudo-innovantes et innovantes. / This study of HR practices in medium-sized enterprises emphasizes on the significative influence of organizational and institutional factors. In this research, we examine these HR practices through an approach which integrates mobilized theories. We also point-out the specificities of these HRpractices in terms of: 1/ differentiation and structural hybridity, 2/ institutional legitimacy and 3/ relational complexity.Based on a methodology of qualitative research, this empirical study includes 40 interviews, 13 of which were part of two case studies. These interviews with different HR actors allow to make comparisons between medium-sized enterprises of different sizes.In light of the specificities of the medium-sized enterprises, our results highlight a variety of HR practices. Our research confirms that beyond the leader, there is a strong interest for a « nonconsensual » approach of HR practices, given that the hierarchy was forced to play a lesser role after the arrival of the managers. Our results show that in medium-sized enterprises, HR practicesare personal, conformist, pseudo-conformist, pseudo-innovative and innovative.

Pour mieux saisir les liens complexes entre génotype et phénotype, une méthode utilisée consiste à étudier les relations entre différents éléments biologiques (entre les protéines, entre les métabolites...). Celles-ci forment ce qui est appelé un réseau biologique, que l'on représente algorithmiquement par un graphe. Nous nous intéressons principalement dans cette thèse au problème de la recherche d'un motif (multi-ensemble de couleurs) dans un graphe coloré, représentant un réseau biologique. De tels motifs correspondent généralement à un ensemble d'éléments conservés au cours de l'évolution et participant à une même fonction biologique. Nous continuons l'étude algorithmique de ce problème et de ses variantes (qui admettent plus de souplesse biologique), en distinguant les instances difficiles algorithmiquement et en étudiant différentes possibilités pour contourner cette difficulté (complexité paramétrée, réduction d'instance, approximation...). Nous proposons également un greffon intégré au logiciel Cytoscape pour résoudre efficacement ce problème, que nous testons sur des données réelles.Nous nous intéressons également à différents problèmes de génomique comparative. La démarche scientifique adoptée reste la même: depuis une formalisation d'un problème biologique, déterminer ses instances difficiles algorithmiquement et proposer des solutions pour contourner cette difficulté (ou prouver que de telles solutions sont impossibles à trouver sous des hypothèses fortes) / To investigate the complex links between genotype and phenotype, one can study the relations between different biological entities. It forms a biological network, represented by a graph. In this thesis, we are interested in the occurrence of a motif (a multi-set of colors) in a vertex-colored graph, representing a biological network. Such motifs usually correspond to a set of elements realizing a same function, and which may have been evolutionarily preserved. We follow the algorithmic study of this problem, by establishing hard instances and studying possibilities to cope with the hardness (parameterized complexity, preprocessing, approximation...). We also develop a plugin for Cytoscape, in order to solve efficiently this problem and to test it on real data.We are also interested in different problems related to comparative genomics. The scientific method is the same: studying problems arising from biology, specifying the hard instances and giving solutions to cope with the hardness (or proving such solutions are unlikely)

À la lumière de nombreux travaux récents, la conception, dans le champ des sciences sociales, de la mondialisation économique et culturelle comme une force d’uniformisation semble perdre de sa prégnance. L’objectif de cette thèse de doctorat est donc de se saisir de l’exemple de l’industrie de la grande distribution, en tant qu’éminente représentante de ce phénomène, pour vérifier, à travers le prisme particulier des pratiques et des représentations alimentaires, si l’on peutencore se contenter de comprendre le processus de mondialisation uniquement comme un vecteur d’éradication des différences culturelles. Procédant selon une méthodologie inductive et une approche comparative, nous avons voulu décrire cette industrie et ses implications sur les modalités du choix alimentaire, en prolongeant au Maroc nos analyses basées sur l’étude des cas français et américain. Suivant les préceptes méthodologiques de la socio-anthropologie et la stratégie de la mosaïque d’études de cas, nous avons, selon le modèle itératif prôné notamment par la grounded theory, sans cesse cherché à mettre nos hypothèses à l’épreuve du terrain à travers une constante extension des cas et une variation des objets étudiés. Cela nous a autorisé à viser une plus grande généralisation de nos théories et ainsi arguer en faveur d’une conception moins simplificatrice des processus de mondialisation en ancrant empiriquement notre plaidoyer pour une perspective complexe des phénomènes culturels et sociaux qui en sont issus. / In the light of the most recent work in social sciences, the understanding of globalization as a force of uniformization seems to be less and less acurate. The goal of this PhD dissertation is, therefore, to use the example of retail store industry, as a media of this globalization process, to verify, through the particular case of food practices and representations, if it is still possible to describe globalization as a destructive phenomenon in terms of cultural differences. Following an inductivist methodology, we studied this industry, its development modalities and their consequences within the various environment which have seen its appearance, its growth and spread to new cultural spaces in order to developp a more general theory of globalization. Adopting the principles of socio-anthropological research and the « case studies mosaic » strategy, and as it is encouraged by the iterative model of the grounded theory, we have constantly sought to submit our theoretical analysis at the test of our empirical field through a continious extension of cases and variation of objects. Thus, gaining in generalization, we have argued for a less simplist understanding of the globalization process, therefore founding our plead for a complex perspective of social and cultural phenomena.

Dans cette thèse nous nous intéressons au développement d'une méthode de prise de décision pour un équipement de réception de Radio Intelligente qui s’adapte dynamiquement à son environnement. L'approche que nous adoptons est basée sur la modélisation statistique de l'environnement radio. En caractérisant statistiquement les observations fournies par les capteurs de l'environnement, nous mettons en place des règles de décisions statistiques qui prennent en considération les erreurs d'observation des métriques radio, ce qui contribue à minimiser les taux des décisions erronées. Nous visons aussi à travers cette thèse à utiliser les capacités intelligentes de prise de décision pour contribuer à la réduction de la complexité de calcul au niveau de l'équipement de réception. En effet, nous identifions des scénarios de prise de décision de reconfiguration qui limitent la présence de certains composants ou fonctions de la chaîne de réception. En particulier, nous traitons, deux scénarios de décision qui adaptent respectivement la présence des fonctions d’égalisation et du beamforming en réception. La limitation de ces deux opérations contribue à la réduction de la complexité de calcul au niveau de la chaîne de réception sans dégrader ses performances. Enfin, nous intégrons notre méthode de décision par modélisation statistique ainsi que les deux scénarios de décision traités dans une architecture de gestion d'une radio intelligente, afin de mettre en valeur le contrôle de l'intelligence et de la reconfiguration dans un équipement radio. / In this thesis we focus on the development of a decision making method for the cognitive radio receiver that dynamically adapts to its environment. The approach that we use is based on the statistical modeling of the radio environment. By statistically characterizing the observations provided by the radio sensor, we set up statistical decision rules that take into account the observations’ errors. This helps to minimize the rate of bad decisions. Also, we aim to use the intelligent capacities to reduce the computational complexity in the receiver chain. Indeed, we identify decision scenarios that limit some operators. In particular, we address two decision scenarios that adapt the presence of the equalization and of the beamforming to the environment. The limitation of these two operations helps to reduce the computational complexity in reception. Finally, we integrate our decision method and the two decision scenarios in a management architecture of reconfiguration and intelligence.