L’objectif de cette thèse est de comprendre le design des organisations à la fois innovantes et socialement responsables qui sont capable d’apprendre et évoluer dans l’économie globale basée sur les connaissances. En appliquant l’approche de la science de la complexité au niveau des entreprises (premier essai), nous apportons un éclairage théorique sur les conditions favorables à l’innovation des systèmes organisationnels. Notre analyse suggère que c'est la culture organisationnelle éthique basée sur la liberté individuelle et orientée vers le bien commun qui est la plus favorable à l’innovation radicale et durable. Ce prototype de la culture éthique est opérationnalisé ensuite en mobilisant le cadre théorique de Nahapiet & Ghoshal (1998) sur le lien entre les trois dimensions de capital social et l’innovation (la deuxième étude) et le design holographique (la troisième étude). Nous testons nos deux modèles de recherche sur un échantillon de convenance des répondants organisationnelles en utilisant la méthode PLS-SEM. Les résultats empiriques valident nos deux modèles théoriques qui mettent en évidence le rôle critique du leadership éthique pour développer une culture d’entreprise éthique propice à l’innovation. Ce type de culture organisationnelle qui favorise à la fois l’afflux de nouvelles idées (grâce à la diversité au travail et aux partenariats avec les parties prenantes) et la coopération des employés (grâce au climat éthique ; participation d’employés dans les programmes de la RSE et à l’orientation stratégique de la RSE) est indispensable pour réconcilier la performance économique des entreprises avec le développement durable de la société globale / The aim of this thesis is to understand the design of socially responsible and innovative organizations that are capable of learning and evolving in the global knowledge-based economy. By applying the systemic approach of complexity science to business companies (first essay), we provide a theoretical understanding of the enabling conditions for organizational innovations. Our analysis suggests that ethical learning culture built on individual freedom for creativity and organizational vision for sustainability is the most likely to create a work environment conducive to radical sustainable innovations. To operationalize the prototype of ethical learning culture, we mobilize the theoretical model Nahapiet & Ghoshal (1998) on the link between three dimensions of social capital and innovation (second study) and the cybernetic principles of holographic design (third study). We test the two research models on a convenience sample of organizational respondents by using the PLS-SEM. Empirical findings validate our two theoretical models that highlight the critical role of ethical leadership for developing an ethical learning culture. This type of organizational culture that simultaneously encourages inflows of new ideas (thanks to workforce diversity and partnerships with the firm’s stakeholders) and employees’ cooperation (thanks to ethical climate, employees’ participation in CSR projects and strategic CSR orientation) is essential for the long-term business success and sustainable human development

Les problèmes de la classification ont reçu une attention considérable dans des différents champs d'ingénierie comme traitement des images biomédicales, identification a partir de la voix, reconnaissance d'empreinte digitale etc. Les techniques d'intelligence artificielles, incluant les réseaux de neurones artificiels, permettent de traiter des problèmes de ce type. En particulier, les problèmes rencontrés nécessitent la manipulation de bases de données de tailles très importantes. Des structures de traitement adaptatives et exploitant des ensembles de classificateurs sont utilisées. Dans cette thèse, nous décrivons principalement le développement et des améliorations apportées à un outil de classification désigné par le terme Tree-like Divide to Simplify ou T-DTS. Nos efforts se sont portés sur l'un des modules de cet outil, le module d'estimation de complexité. L'architecture de l'outil T-DTS est très flexible et nécessite le choix d'un nombre important de paramètres. Afin de simplifier l'exploitation de T-DTS, nous avons conçu et développé une procédure automatique d'optimisation d'un de ces plus importants paramètres, le seuil de décision associé à la mesure de complexité. La contribution principale de cette thèse concerne le développement de modules pouvant s'implanté sur une architecture de calcul matérielle parallèle. Ceci permet de se rapprocher d'une implantation purement matérielle de l'outil T-DTS / Classification problems deal with separating group of objects into sets of smaller classes; this set of problems have received considerable attention in diverse engineering fields such as biomedical imaging, speaker identification, fingerprint recognition, etc. Several effective approaches for automated classification were suggested based on artificial intelligence techniques, including neural networks. Still, one of the major challenges faced by these approaches is a large scale of data required for successful classification. In this thesis, we explore a possible solution to this problem based on a module-based Tree-like Divide to Simplify (T-DTS) classification model. We focus on enhancing the key module of this approach - complexity estimation module. Furthermore, we provide an automated procedure for optimizing key complexity estimation parameters of the T-DTS model; this considerably improves usability and allows for a more effective configuration of decomposition reasoning of the approach. Another major contribution of this work employs further development of T-DTS modules that could be implemented using parallel computer architecture, thereby allowing T-DTS to utilize an underlying hardware to the fullest extent

Dans cette thèse, nous abordons des problèmes NP-difficiles à l'aide de techniques combinatoires, en se focalisant sur le domaine de la complexité paramétrée. Les principaux problèmes que nous considérons sont les problèmes de Multicoupe et d'Arbre Orienté Couvrant avec Beaucoup de Feuilles. La Multicoupe est une généralisation naturelle du très classique problème de coupe, et consiste à séparer un ensemble donné de paires de sommets en supprimant le moins d'arêtes possible dans un graphe. Le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles consiste à trouver un arbre couvrant avec le plus de feuilles possible dans un graphe dirigé. Les résultats principaux de cette thèse sont les suivants. Nous montrons que le problème de Multicoupe paramétré par la taille de la solution est FPT (soluble à paramètre fixé), c'est-à-dire que l'existence d'une multicoupe de taille $k$ dans un graphe à $n$ sommets peut être décidée en temps $f(k)*poly(n)$. Nous montrons que Multicoupe dans les arbres admet un noyau polynomial, c'est-à-dire est réductible aux instances de taille polynomiale en $k$. Nous donnons un algorithme en temps $O^*(3.72^k)$ pour le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles et le premier algorithme exponentiel exact non trivial (c'est-à-dire meilleur que $2^n$). Nous fournissons aussi un noyau quadratique et une approximation à facteur constant. Ces résultats algorithmiques sont basés sur des résultats combinatoires et des propriétés structurelles qui concernent, entre autres, les décompositions arborescentes, les mineurs, des règles de réduction et les $s-t$ numberings. Nous présentons des résultats combinatoires hors du domaine de la complexité paramétrée: une caractérisation des graphes de cercle Helly comme les graphes de cercle sans diamant induit, et une caractérisation partielle des classes de graphes 2-bel-ordonnées. / This thesis tackles NP-hard problems with combinatorial techniques, focusing on the framework of Fixed-Parameter Tractability. The main problems considered here are Multicut and Maximum Leaf Out-branching. Multicut is a natural generalisation of the cut problem, and consists in simultaneously separating prescribed pairs of vertices by removing as few edges as possible in a graph. Maximum Leaf Out-branching consists in finding a spanning directed tree with as many leaves as possible in a directed graph. The main results of this thesis are the following. We show that Multicut is FPT when parameterized by the solution size, i.e. deciding the existence of a multicut of size $k$ in a graph with $n$ vertices can be done in time $f(k)*poly(n)$. We show that Multicut In Trees admits a polynomial kernel, i.e. can be reduced to instances of size polynomial in $k$. We give an $O^*(3.72^k)$ algorithm for Maximum Leaf Out-branching and the first non-trivial (better than $2^n$) exact algorithm. We also provide a quadratic kernel and a constant factor approximation algorithm. These algorithmic results are based on combinatorial results and structural properties, involving tree decompositions, minors, reduction rules and $s-t$ numberings, among others. We present results obtained with combinatorial techniques outside the scope of parameterized complexity: a characterization of Helly circle graphs as the diamond-free circle graphs, and a partial characterisation of 2-well-quasi-ordered classes of graphs.

Les données sous forme de chaîne de symboles sont très variées (ADN, texte, EEG quantifié,…) et ne sont pas toujours modélisables. Une description universelle des chaînes de symboles indépendante des probabilités est donc nécessaire. La complexité de Kolmogorov a été introduite en 1960 pour répondre à cette problématique. Le concept est simple : une chaîne de symboles est complexe quand il n'en existe pas une description courte. La complexité de Kolmogorov est le pendant algorithmique de l’entropie de Shannon et permet de définir la théorie algorithmique de l’information. Cependant, la complexité de Kolmogorov n’est pas calculable en un temps fini ce qui la rend inutilisable en pratique.Les premiers à rendre opérationnelle la complexité de Kolmogorov sont Lempel et Ziv en 1976 qui proposent de restreindre les opérations de la description. Une autre approche est d’utiliser la taille de la chaîne compressée par un compresseur sans perte. Cependant ces deux estimateurs sont mal définis pour le cas conditionnel et le cas joint, il est donc difficile d'étendre la complexité de Lempel-Ziv ou les compresseurs à la théorie algorithmique de l’information.Partant de ce constat, nous introduisons une nouvelle mesure d’information universelle basée sur la complexité de Lempel-Ziv appelée SALZA. L’implémentation et la bonne définition de notre mesure permettent un calcul efficace des grandeurs de la théorie algorithmique de l’information.Les compresseurs sans perte usuels ont été utilisés par Cilibrasi et Vitányi pour former un classifieur universel très populaire : la distance de compression normalisée [NCD]. Dans le cadre de cette application, nous proposons notre propre estimateur, la NSD, et montrons qu’il s’agit d’une semi-distance universelle sur les chaînes de symboles. La NSD surclasse la NCD en s’adaptant naturellement à davantage de diversité des données et en définissant le conditionnement adapté grâce à SALZA.En utilisant les qualités de prédiction universelle de la complexité de Lempel-Ziv, nous explorons ensuite les questions d’inférence de causalité. Dans un premier temps, les conditions algorithmiques de Markov sont rendues calculables grâce à SALZA. Puis en définissant pour la première l’information dirigée algorithmique, nous proposons une interprétation algorithmique de la causalité de Granger algorithmique. Nous montrons, sur des données synthétiques et réelles, la pertinence de notre approche. / Data in the form of strings are varied (DNA, text, quantify EEG) and cannot always be modeled. A universal description of strings, independent of probabilities, is thus necessary. The Kolmogorov complexity was introduced in 1960 to address the issue. The principle is simple: a string is complex if a short description of it does not exist. The Kolmogorov complexity is the counterpart of the Shannon entropy and defines the algorithmic information theory. Yet, the Kolmogorov complexity is not computable in finit time making it unusable in practice.The first ones to make operational the Kolmogorov complexity are Lempel and Ziv in 1976 who proposed to restrain the operations of the description. Another approach uses the size of the compressed string by a lossless data compression algorithm. Yet these two estimators are not well-defined regarding the joint and conditional complexity cases. So, compressors and Lempel-Ziv complexity are not valuable to estimate algorithmic information theory.In the light of this observation, we introduce a new universal information measure based on the Lempel-Ziv complexity called SALZA. The implementation and the good definition of our measure allow computing efficiently values of the algorithmic information theory.Usual lossless compressors have been used by Cilibrasi and Vitányi to define a very popular universal classifier: the normalized compression distance [NCD]. As part of this application, we introduce our own estimator, called the NSD, and we show that the NSD is a universal semi-distance between strings. NSD surpasses NCD because it gets used to a large data set and uses the adapted conditioning with SALZA.Using the accurate universal prediction quality of the Lempel-Ziv complexity, we explore the question of causality inference. At first, we compute the algorithmic causal Markov condition thanks to SALZA. Then we define, for the first time, the algorithmic directed information and based on it we introduce the algorithmic Granger causality. The relevance of our approach is demonstrated on real and synthetic data.

L’association de la bière avec les mets apparaît comme une nouvelle tendance en France. Il est donc nécessaire pour les promoteurs de bière et les professionnels de la gastronomie de fournir à leurs clients des conseils de qualité en terme d’accord bière et mets. Au vu de ce contexte, l’objectif de la thèse était d’identifier les principes d’association et de mieux comprendre les mécanismes perceptuels qui les sous-tendent. Les déterminants des accords mets et boissons ont, dans un premier temps, été identifiés à partir du discours d’experts. Les résultats ont montrés que les associations mets et boissons sont régies par des caractéristiques perceptuelles, conceptuelles et affectives, liées à des mécanismes physico-chimiques, perceptuels et cognitifs. Les experts ont souvent mentionné la «similarité aromatique» comme l'un des principaux principes d'association. Ce principe consiste à associer deux produits partageant des arômes similaires. Les mécanismes perceptuels sous-jacents à ce principe ont été investigués. Les résultats ont montrés qu’une similarité aromatique entre un mets et une boisson augmente le niveau d’harmonie et d’homogénéité de leur association et diminue sa complexité. Ces effets peuvent être renforcés en orientant l’attention du dégustateur sur l’arôme partagé. D’un point de vue théorique, cette thèse conclut que l’association bières et mets inclut des dimensions sensorielles avec une recherche d’harmonie, mais aussi des dimensions symboliques et contextuelles. D’un point de vue plus appliqué, cette thèse fournit aux professionnels de la gastronomie, de nouvelles informations concernant les mécanismes perceptifs sous-tendant les principes d’associations. / Pairing between beer and dishes emerges as a new trend in France. Beer promoters or gastronomy professionals need to offer high-quality advices in terms of beer and food pairing to their customers. Within this context, the objective of the research was to identify pairing principles and to better understand the underlying perceptual mechanisms. Determinants of food and beverage pairing were first analysed from experts’ discourses. Results showed that food and beverage pairings are governed by perceptual, conceptual and affective features, related to physio-chemical, perceptual and cognitive processes. Experts often mentioned “Aromatic Similarity” as one of the main pairing principles. This “Aromatic similarity” principle consists in matching two products sharing similar aromas. Underlying perceptual mechanisms were then investigated. Results showed that aromatic similarity in food and beverage generally increases harmony and homogeneity and decreases complexity of the match. These effects can be reinforced by orientating the attentional focus on the shared aroma. From a theoretical point of view, this work concludes that beer and food pairing includes sensory dimensions with the search for harmony, as well as symbolic and contextual dimensions. From an applied point of view, this work provides useful information to gastronomy professionals with recent knowledge on perceptual mechanisms underlying food and beverage pairing principles.

L’industrialisation alimentaire est un véritable progrès pour la société et le consommateur qui recherche la facilité d’achat. Cependant, à la suite de plusieurs crises sanitaires, le consommateur souhaite être mieux informé et maîtriser ses choix de produits. C’est pourquoi, les industriels souhaitent à leur tour améliorer la communication sur leur produit par le biais du packaging grâce aux attributs visuels. Néanmoins, une surabondance des informations, peut rendre le packaging difficilement intelligible. De ce fait, ce travail doctoral s’intéresse à l’impact du niveau de complexité visuelle du packaging sur l’évaluation du produit alimentaire. Cette problématique donne lieu à trois questions de recherche adoptant successivement une approche holistique, puis deux approches analytiques de la complexité du packaging considérant le nombre d’ingrédients et leur degré de similitude selon le niveau de disponibilité des ressources cognitives. L’influence du niveau de complexité du packaging sur l’évaluation du produit est étudiée au moyen de sept études par une approche aux méthodes variées, avec des mesures auto-déclarées, comportementales et implicites. Cette recherche souligne, l’association d’un packaging simple à un produit alimentaire sain, valorisé suivant le bénéfice nutritionnel et suivant la qualité des ingrédients dans la composition du produit. Par ailleurs, elle souligne l’association d’un packaging complexe à un produit meilleur en goût qui facilite la formation de l’imagerie mentale gustative, en fonction du degré de similarité des éléments visuels selon une approche analytique de la complexité du design et selon le niveau de ressources cognitives.Mots clés : complexité, simplicité, design du packaging, ingrédients, salubrité, goût, intention d’achat, charge cognitive / Food industrialization is a real advance for society and the consumer who is looking for ease of purchase. However, with several health crises, the consumer wants to be better informed and to control his product choice. In this way, manufacturers want to improve communication on their product through visual attributes of their packaging. Nevertheless, an information overload can make the packaging difficult to understand. As a result, this doctoral research focuses on the impact of the level of visual complexity of the packaging on the evaluation of the food product. This problem leads to three research questions successively adopting a holistic approach, then two analytical approaches to the packaging complexity considering the number of ingredients and their degree of similarity depending on the level of availability of cognitive resources. The influence of the level of complexity on the evaluation of the product is studied by means of seven studies with a mixed methodological approach, with self-declared, behavioral and implicit measures. This research highlights the combination of a simple packaging with a healthy food product, valued according to the nutritional benefit and the quality ingredients in the product composition. In addition, it emphasizes the combination of a complex packaging with a better taste product that facilitates the formation of mental imagery taste depending on the degree of similarity of visual elements in the analytical approach of the design complexity and the cognitive resources level. Keywords: complexity, simplicity, packaging design, ingredients, healthy food, taste, purchase intent, cognitive load

Cette thèse se situe à l'interface de trois grands domaines : la combinatoire des mots, la théorie des automates et la théorie des nombres. Plus précisément, nous montrons comment des outils provenant de la combinatoire des mots et de la théorie des automates interviennent dans l'étude de problèmes arithmétiques concernant les séries formelles à coefficients dans un corps fini.Le point de départ de cette thèse est un célèbre théorème de Christol qui caractérise les séries de Laurent algébriques sur le corps F_q(T), l'entier q désignant une puissance d'un nombre premier p, en termes d'automates finis et dont l'énoncé est : « Une série de Laurent à coefficients dans le corps fini F_q est algébrique si et seulement si la suite de ses coefficients est engendrée par un p-automate fini ». Ce résultat, qui révèle dans un certain sens la simplicité de ces séries de Laurent, a donné naissance à des travaux importants parmi lesquels de nombreuses applications et généralisations.L'objet principal de cette thèse est, dans un premier temps, d'exploiter la simplicité de séries de Laurent algébriques à coefficients dans un corps fini afin d'obtenir des résultats diophantiens, puis d'essayer d'étendre cette étude à des fonctions transcendantes arithmétiquement intéressantes. Nous nous concentrons tout d'abord sur une classe de séries de Laurent algébriques particulières qui généralisent la fameuse cubique de Baum et Sweet. Le résultat principal obtenu pour ces dernières est une description explicite de leur développement en fraction continue, généralisant ainsi certains travaux de Mills et Robbins. Rappelons que le développement en fraction continue permet généralement d'obtenir des informations très précises sur l'approximation rationnelle ; les meilleures approximations étant obtenues directement à partir de la suite des quotients partiels. Malheureusement, il est souvent très difficile d'obtenir le développement en fraction continue d'une série de Laurent algébrique, que celle-ci soit donné par une équation algébrique ou par son développement en série de Laurent. La deuxième étude que nous présentons dans cette thèse fournit une information diophantienne à priori moins précise que la description du développement en fraction continue, mais qui a le mérite de concerner toutes les séries de Laurent algébriques (à coefficients dans un corps fini). L'idée principale est d'utiliser l'automaticité de la suite des coefficients de ces séries de Laurent afin d'obtenir une borne générale pour leur exposant d'irrationalité. Malgré la généralité de ce résultat, la borne obtenue n'est pas toujours satisfaisante. Dans certains cas, elle peut s'avérer plus mauvaise que celle provenant de l'inégalité de Mahler. Cependant, dans de nombreuses situations, il est possible d'utiliser notre approche pour fournir, au mieux, la valeur exacte de l'exposant d'irrationalité, sinon des encadrements très précis de ce dernier.Dans un dernier travail nous nous plaçons dans un cadre plus général que celui des séries de Laurent algébriques, à savoir celui des séries de Laurent dont la suite des coefficients a une « basse complexité ». Nous montrons que cet ensemble englobe quelques fonctions remarquables, comme les séries algébriques et l'inverse de l'analogue du nombre \pi dans le module de Carlitz. Il possède, par ailleurs, des propriétés de stabilité intéressantes : entre autres, il s'agit d'un espace vectoriel sur le corps des fractions rationnelles à coefficients dans un corps fini (ce qui, d'un point de vue arithmétique, fournit un critère d'indépendance linéaire), il est de plus laissé invariant par diverses opérations classiques comme le produit de Hadamard / This thesis looks at the interplay of three important domains: combinatorics on words, theory of finite-state automata and number theory. More precisely, we show how tools coming from combinatorics on words and theory of finite-state automata intervene in the study of arithmetical problems concerning the Laurent series with coefficients in a finite field.The starting point of this thesis is a famous theorem of Christol which characterizes algebraic Laurent series over the field F_q(T), q being a power of the prime number p, in terms of finite-state automata and whose statement is the following : “A Laurent series with coefficients in a finite field F_q is algebraic over F_q(T) if and only if the sequence of its coefficients is p-automatic”.This result, which reveals, somehow, the simplicity of these Laurent series, has given rise to important works including numerous applications and generalizations. The theory of finite-state automata and the combinatorics on words naturally occur in number theory and, sometimes, prove themselves to be indispensable in establishing certain important results in this domain.The main purpose of this thesis is, foremost, to exploit the simplicity of the algebraic Laurent series with coefficients in a finite field in order to obtain some Diophantine results, then to try to extend this study to some interesting transcendental functions. First, we focus on a particular set of algebraic Laurent series that generalize the famous cubic introduced by Baum and Sweet. The main result we obtain concerning these Laurent series gives the explicit description of its continued fraction expansion, generalizing therefore some articles of Mills and Robbins.Unfortunately, it is often very difficult to find the continued fraction representation of a Laurent series, whether it is given by an algebraic equation or by its Laurent series expansion. The second study that we present in this thesis provides a Diophantine information which, although a priori less complete than the continued fraction expansion, has the advantage to characterize any algebraic Laurent series. The main idea is to use some the automaticity of the sequence of coefficients of these Laurent series in order to obtain a general bound for their irrationality exponent. In the last part of this thesis we focus on a more general class of Laurent series, namely the one of Laurent series of “low” complexity. We prove that this set includes some interesting functions, as for example the algebraic series or the inverse of the analogue of the real number \pi. We also show that this set satisfy some nice closure properties : in particular, it is a vector space over the field over F_q(T).

Les modèles géométriques de calcul permettent d’effectuer des calculs à l’aide de primitives géométriques. Parmi eux, le modèle des machines à signaux se distingue par sa simplicité, ainsi que par sa puissance à réaliser efficacement de nombreux calculs. Nous nous proposons ici d’illustrer et de démontrer cette aptitude, en particulier dans le cas de processus massivement parallèles. Nous montrons d’abord à travers l’étude de fractales que les machines à signaux sont capables d’une utilisation massive et parallèle de l’espace. Une méthode de programmation géométrique modulaire est ensuite proposée pour construire des machines à partir de composants géométriques de base les modules munis de certaines fonctionnalités. Cette méthode est particulièrement adaptée pour la conception de calculs géométriques parallèles. Enfin, l’application de cette méthode et l’utilisation de certaines des structures fractales résultent en une résolution géométrique de problèmes difficiles comme les problèmes de satisfaisabilité booléenne SAT et Q-SAT. Ceux-ci, ainsi que plusieurs de leurs variantes, sont résolus par machines à signaux avec une complexité en temps intrinsèque au modèle, appelée profondeur de collisions, qui est polynomiale, illustrant ainsi l’efficacité et le pouvoir de calcul parallèle des machines a signaux. / Geometrical models of computation allow to compute by using geometrical elementary operations. Among them, the signal machines model distinguishes itself by its simplicity, along with its power to realize efficiently various computations. We propose here an illustration and a study of this ability, especially in the case of massively parallel processes. We show first, through a study of fractals, that signal machines are able to make a massive and parallel use of space. Then, a framework of geometrical modular programmation is proposed for designing machines from basic geometrical components —called modules— supplied with given functionnalities. This method fits particulary with the conception of geometrical parallel computations. Finally, the joint use of this method and of fractal structures provides a geometrical resolution of difficult problems such as the boolean satisfiability problems SAT and Q-SAT. These ones, as well as several variants, are solved by signal machines with a model-specific time complexity, called collisions depth, which is polynomial, illustrating thus the efficiency and the parallel computational abilities of signal machines.

Les problèmes de domination (dominant, dominant indépendant, ...) et de couverture (vertex-cover, arbre de Steiner, ...) sont NP-complets. Pour autant, pour la plupart de ces problèmes, il existe toujours une solution constructible en temps polynomial (potentiellement de valeur objective très mauvaise), ou au moins, il est possible de déterminer facilement (en temps polynomial) l'existence ou non d'une solution. Ces problèmes, initialement issus de situations réelles, sont des modélisations simplistes de ces situations. Nous ajoutons donc des contraintes additionnelles modélisant des contraintes pratiques plausibles : les conflits, des paires d'éléments ne pouvant faire simultanément partie d'une solution (modélisant des incompatibilités diverses), la connexité dans un second graphe (les éléments doivent pouvoir communiquer, et le graphe correspondant à ces liens de communication n'est pas forcément le même) et les obligations, des sous-ensembles d'éléments interdépendants devant être ajoutés simultanément à une solution. Notre but ici n'est pas de modéliser un problème réel précis, mais d'étudier la manière dont ces contraintes modifient la complexité des problèmes étudiés. Nous verrons que dans un grand nombre de cas, déterminer l'existence même d'une solution devient difficile, même sans se préoccuper de leur optimisation. Le problème du firefighter modélise des pompiers tentant de contenir un feu se propageant au tour par tour dans un graphe (potentiellement infini). Nous avons étudié ce problème en ajoutant des contraintes sur le déplacement des pompiers (une vitesse de déplacement limitée entre deux tours). Nous verrons que ces contraintes augmentent en général le nombre de pompiers nécessaires mais ne provoquent pas de changements aussi importants que dans les problèmes précédents. / Domination problems (dominating set, independant dominating set, ...) as well as covering problems (vertex-cover, Steiner tree, ...) are NP-complete. However, for most of these problems, it is always possible to construct a (eventually bad) solution in polynomial time, or at least it is possible to determine whether a solution exists. Those problems originally came from industry, but are simplified modelizations of the real life problems. We add additional constraints modeling plausible practical constraints : conflicts which are pairs of elements that cannot apear simultaneously in a solution (to modelize various incompatibilities), connexity in a second graph (elements of the solution must be able to communicate, and the communication links are a second graph), and obligations which are subsets of interdependant vertices which must be added simultaneously in a solution.We don't aim to model a specific real-world problem, but to study how these plausible constraints affect the complexity of the studied problems. We will see that, in many cases, even determining the existence of a solution (regardless of its size) become hard. The firefighter problem models firefighters aiming to contain a fire spreading turn by turn in a (eventually infinite) graph. We studied this problem with the addition of deplacement constraints for the firefighters (a limited moving speed between turns). We will see that, most of the time, this constraint increase the number of firefighters necessary to contain the fire, but does not trigger such major change as constraints studied in the others problems.

La mise en réseau des Centres de Formation Professionnels et de Promotion Agricole en Rhône-Alpes, portés par leur EPLEFPA, rencontre de fortes difficultés : relations, mutualisations, harmonisations des pratiques, productions, etc. Ceci a été révélé par une étude interne en 2011. Par ailleurs, les contraintes des marchés publics poussent les centres à adopter des fonctionnements peu propices à des activités pédagogiques et ingénieriques adéquats. Les défaillances se multiplient à tous les niveaux. A partir des théories de la complexité, cette recherche propose un nouveau modèle hypercomplexe organisationnel et productif, aux différents niveaux (réseau, centre, dispositif pédagogique, et situation d’apprentissage). Loin de vouloir normaliser, cette modélisation souhaite reconstruire les bases de nouvelles interactions saines, efficaces, efficientes et harmonisantes, favorables aux différentes pratiques pédagogiques. Parce que tous ces niveaux sont interconnectés, ils doivent pouvoir se caler facilement les uns avec les autres, dans une logique récursive, fractale, et dialogique, et ainsi intégrer les mêmes repères fondamentaux. / There are a lot of difficulties in a networking of the CFPPA in Rhône-Alpes region, supported by their own EPLEFPA: agreement, mutualization, harmonization of practices, productions… It has been highlighted in an internal study in 2011. Besides, public markets’ constraints urge the formation centers to adopt few convenient functional for the deployment of appropriates pedagogical and engineerical activities. Failures are increased in all level. From complexity theories, this research suggests a new organizational and productive hypercomplex model at different levels (network, center, pedagogical device, and learning situation). Without wanting to normalize, this modeling wants to rebuild healthy, effective, efficient and harmonizate, new interactions, conducive to different pedagogical practices. Because all these levels are interconnected, they must could easily prop up some with the others, in a recursive, fractal, and dialogical logic, and by the way integrate the same fundamental references.