Nous considérons dans cette thèse la complexité algorithmique de problèmes émanant de deux formalismes de raisonnement non-monotone: l'abduction et l'argumentation. Le premier est destiné à formaliser le processus de trouver des explications pour une manifestation observée, le second (et plus récent) offre un cadre théorique pour formaliser le processus de l'argumentation. Nous nous concentrons sur le problème d'existence d'une explication pour l'abduction et sur le problème d'existence d'un argument pour l'argumentation. Dans le cadre de la logique propositionnelle dans son ensemble ces problèmes sont considérés comme étant des tâches algorithmiques difficiles (ils sont souvent situés au deuxième niveau de l'hiérarchie polynomial). Notre but est d'une part de comprendre les sources de difficulté, et d'autre part d'identifier des fragments de la logique propositionnelle dans lequels ces problèmes sont résolubles efficacement. Pour cela nous considérons ces problèmes d'abduction et d'argumentation dans deux cadres bien-établis qui permettent des classifications de complexité : Le cadre de Post et celui de Schaefer. Dans le cadre de Post, des restrictions sont faites sur les connecteurs autorisés dans les formules utilisées. Dans le cadre de Schaefer, on considère les formules en forme normale conjonctive généralisée, les "clauses" sont alors des applications de relations booléennes à des variables et on restreint le type des relations autorisées. / In this thesis we consider the computational complexity of problems from two central formalisms of nonmonotonic reasoning: abduction and argumentation. The first one is designed to formalize the process of finding explanations for some observed manifestation, the second (and more recent) one gives a theoretical framework to formalize the process of argumentation. We focus on the explanation-existence problem for abduction and on the argument-existence problem for argumentation. Considered in full propositional logic these problems are believed to be computationally costly tasks (they are often situated at the second level of the polynomial hierarchy). With the purpose of understanding sources of hardness and of identifying tractable fragments of propositional logic we consider several abduction and argumentation problems in two well-established settings allowing for complexity classifications. In the first one, Post's Framework, restrictions are made on the allowed connectives in the used formulae, whereas in the second one, Schaefer's Framework, one considers formulae in conjunctive normal form, where the clauses are generalized to applications of arbitrary Boolean relations to variables and one restricts the allowed type of relations. We discuss differences and common features between the explanation-existence and the argument-existence problem in function of the two chosen frameworks. Finally, we consider enumeration. In particular we consider the problem of enumerating all solutions (models) of a propositional formula by non-decreasing weight in Schaefer's framework (the weight of a model being the number of variables assigned to true).

La th´eorie de la complexit´e permet de classifier les probl`emes en fonction de leur difficult´e. Le cadre classique dans lequel elle s’applique est celui d’un algorithme centralis´e qui dispose de toutes les informations. Avec l’essor des r´eseaux et des architectures d´ecentralis´ees, l’algo- rithmique distribu´ee a ´et´e ´etudi´ee. Dans un grand nombre de probl`emes, en optimisation et en ´economie, les d´ecisions et les calculs sont effectu´es par des agents ind´ependants qui suivent des objectifs diff´erents dont la r´ealisation d´epend des d´ecisions des autres agents. La th´eorie des jeux est un cadre naturel pour analyser les solutions de tels probl`emes. Elle propose des concepts de stabilit´e, le plus classique ´etant l’´equilibre de Nash.Une mani`ere naturelle de calculer de telles solutions est de “ faire r´eagir “ les agents ; si un agent voit quelles sont les d´ecisions des autres joueurs ou plus g´en´eralement un “ ´etat du jeu “, il peut d´ecider de changer sa d´ecision pour atteindre son objectif faisant ainsi ´evoluer l’´etat du jeu. On dit que ces algorithmes sont des “ dynamiques “.On sait que certaines dynamiques convergent vers un concept de solution. On s’int´eresse `a la vitesse de convergence des dynamiques. Certains concepts de solutions sont mˆeme complets pour certaines classes de complexit´e ce qui rend peu vraisemblable l’existence de dynamiques simples qui convergent rapidement vers ces solutions. On a utilis´e alors trois approches pour obtenir une convergence rapide : am´eliorer la dynamique (en utilisant par exemple des bits al´eatoires), restreindre la structure du probl`eme, et rechercher une solution approch´ee.Sur les jeux de congestion, on a ´etendu les r´esultats de convergence rapide vers un ´equilibre de Nash approch´e aux jeux n´egatifs. Cependant, on a montr´e que sur les jeux sans contrainte de signe, calculer un ´equilibre de Nash approch´e est PLS-complet. Sur les jeux d ’appariement, on a ´etudi´e la vitesse de dynamiques concurrentes lorsque les joueurs ont une information partielle param´etr´ee par un r´eseau social. En particulier, on a am´elior´e des dynamiques naturelles afin qu’elles atteignent un ´equilibre enO(log(n)) tours (avec n le nombre de joueurs). / Complexity theory allows to classify problems by their algorithmic hardness. The classical framework in which it applies is the one of a centralized algorithm that knows every informa- tion. With the development of networks and decentralized architectures, distributed dynamics was studied. In many problems, in optimization or economy, actions and computations are made by independant agents that don’t share the same objective whose realization depends on the actions of other agents. Game theory is a natural framework to study solutions of this kind of problem. It provides solution concepts such as the Nash equilibrium.A natural way to compute these solutions is to make the agents “react” ; if an agent sees the actions of the other player, or more generally the state of the game, he can decide to change his decision to reach his objective and updates the state of the game. We call �dynamics� this kind of algorithms.We know some dynamics converges to a stable solution. We are interested by the speed of convergence of these dynamics. Some solution concepts are even complete for some complexity classes which make unrealistic the existence of fast converging dynamics. We used three ways to obtain a fast convergence : improving dynamics (using random bits), finding simple subcases, and finding an approximate solution.We extent fast convergence results to an approximate Nash equilibria in negative congestion games. However, we proved that finding an approximate Nash equilibrium in a congestion games without sign restriction is PLS-complete. On matching game, we studied the speed of concurrent dynamics when players have partial information that depends on a social network. Especially, we improved natural dynamics for them to reach an equilibrium inO(log(n)) rounds (with n is the number of players).

L'augmentation des cas de surpoids et d'obésité dans les pays développés n'épargne désormais plus les pays émergents qui sont de plus en plus touchés par ce phénomène. J'ai comparé dans cette étude, deux stratégies de prévention de l'obésité en milieu scolaire entre un pays du développé, la France, et un pays émergent, l'Inde. En effet l'Inde qui a amorcé sa transition nutritionnelle, connaît une augmentation des cas de surpoids et d'obésité infantiles. Les nombreuses recherches sur les déterminants de l'obésité mettent aujourd'hui en lumière sa nature multifactorielle. A la piste génétique qui était auparavant privilégiée, s'ajoutent de nombreuses autres hypothèses explicatives mettant en évidence des facteurs psychologiques, sociaux, économiques, épigénétiques, biologiques, alimentaires, liés au rythme de vie (énumération non exhaustive). La pluralité de ces facteurs de risque fait de l'obésité un phénomène qui peut être qualifié de complexe. Pour comprendre cette complexité, je me suis référée à la « méthode » proposée par Edgar Morin (1990) pour conceptualiser et analyser la complexité à travers plusieurs principes directeurs. Ces principes permettent d'orienter le raisonnement entre pensée complexe et pensée simplifiante. Je les ai appliqués à l'analyse des stratégies nutritionnelles en milieu scolaire. Mes résultats révèlent d'une part que le paradigme de complexité permet aux enseignants de développer une stratégie nutritionnelle adaptée à la nature complexe de l'obésité. D'autre part, la stigmatisation de l'obésité, si elle est nécessaire pour déclencher une réelle prise de conscience de l'intérêt de la prévention globale, doit être limitée pour ne pas devenir contre-productive. Ces résultats permettent d'ouvrir de nombreuses perspectives pour améliorer la stratégie nutritionnelle dans chaque contexte étudié (français et indien), tant dans le domaine de la recherche que dans celui de la formation des enseignants. / Nowadays, overweight and obesity in developed countries are increasing even in developped countries. In this study, I compared two strategies for obesity prevention in schools between developed countries , France, and a developped country, India. Indeed India which started its nutritional transition, knows an increase in the cases of infantile overweights and obesity. Many researchs on the determinants of obesity clarifies today its multifactorial nature. To the genetic track which was privileged before, many other explanatory assumptions are added highlighting factors psychological, social, economic, epigenetic, biological, food, dependent to the rhythm of life (non exhaustive enumeration). The plurality of these risk factors shows that obesity is a phenomenon which can be qualified of complex. To understand this complexity, I referred to the « method » suggested by Edgar Morin (1990) to conceptualize and analyze complexity through several guiding principles. These principles make it possible to direct the reasoning between complex thought and simplifying thought. I applied them to the analysis of the nutritional strategies in school. My results reveal on the one hand that the paradigm of complexity lead the teachers to develop a nutritional strategy adapted to the complex nature of obesity. In addition, the stigmatization of obesity, which is necessary to start a real awakening of the interest of the total prevention, must be limited not to become against-productive. These results open many prospects to improve the nutritional strategy in each studied context (french and indian), in the field of research and in the field of teacher training.

Depuis l’avènement des environnements dits turbulents, une réflexion a vu le jour puis s’est développée autour du type de comportement stratégique et de compétences clés à adopter afin d’en limiter les effets négatifs. Cette réflexion a élevé le débat sur les processus d’adaptation en continu des organisations par rapport aux fluctuations exogènes. Ces perturbations peuvent également provenir de facteurs endogènes qui remodèlent les activités et les trajectoires organisationnelles. Les organisations sont alors contraintes à reconfigurer leurs processus pour mieux intégrer les changements. Mieux appréhender les fluctuations amène les organisations à plus d’anticipation, à plus de rapidité d’exécution, à plus de flexibilité et à plus d’apprentissages pour soutenir leurs projets de développement sur la durée. L’ensemble de ces mutations amènent ainsi les décideurs de tous bords à reconsidérer les hommes, les structures et les capacités organisationnelles dans une visée « agile ». L'agilité organisationnelle, entendue comme l’aptitude à se mouvoir promptement et justement dans des environnements incertains nécessite selon nous une investigation qualitative dans une perspective de meilleure compréhension du concept, car l’incomplétude de la littérature évacue les limites d’une notion qui semble figée. Notre investigation explore ainsi les représentations différenciées de la part des acteurs du concept, son opérabilité –complexe- dans les organisations, et vise enfin à élargir l’existant en apportant de nouveaux éléments de compréhension tels que la proximité, l’entrepreneuriat, la redéfinition de l’articulation du triptyque réactivité-flexibilité-proactivité… / Since the beginning of the so-called turbulent environments, thought has appeared and has developed around the type of strategic behaviour and key skills to be adopted in order to limit their negative effects. This thinking process has lifted up the debate to the ongoing adaptation processes of organisations according to exogenous fluctuations. These disturbances can also stem from endogenous factors that remodel activities and organisational paths. Organisations are therefore compelled to rearrange their processes to better integrate changes. A better approach to fluctuations leads organisations to more anticipation, quicker implementation, more flexibility and more learning that will enable them to sustain their development projects in the long run. All these alterations bring decision makers from all spheres of activity to reconsider men, structures and organisational capacities from an “agile” point of view.Organisational agility understood as the ability to move swiftly and rightly within uncertain environments requires according to this research a qualitative examination leading to a better understanding of the concept since it appears from the review of literature that the theoretical object of agility is described as rigid whereas it has its limits. This research thus explores the differentiated representations that the actors of agility make of the concept, its effectiveness, its (complex) functioning inside organisations. Finally, it also aims at enlarging the state-of-the-art by bringing new elements of understanding as proximity, entrepreneurship, redefinition of the triptych articulation: reactivity-flexibility-pro-activity.

La profession de masseur-kinésithérapeute est située à un tournant de son histoire. Les réformes en cours conduisent à questionner les savoirs enseignés et les compétences des masseurs-kinésithérapeutes pour garantir la sécurité du patient et la qualité des soins. Il a été cherché à connaître l'origine des savoirs en masso-kinésithérapie et à évaluer les dispositifs d'enseignements et d'appropriation de ces savoirs par les étudiants et par les professionnels de santé. Les résultats des études montrent que les écarts aux compétences attendues sont liés aux modalités d'enseignement et d'évaluation utilisées par les formateurs en formation initiale et en formation continue. Il apparait que les modalités pédagogiques utilisées par les formateurs sont souvent basées sur un socle théorique behavioriste, un modèle d'évaluation contrôle et des pratiques dogmatiques qui empêchent l'accès à la pensée et à la pratique « complexe » du soin. La formation n'optimise pas le développement des compétences de réflexivité, d'esprit critique et d'innovation nécessaires à la relation humaine de soin et à la sécurité idéale du patient. Cette thèse montre l'intérêt majeur de réaliser les enseignements en masso-kinésithérapie par des enseignants-chercheurs qui pensent, écrivent, discourent, agissent différemment des formateurs en formation initiale et en formation continue. Il est donc indispensable pour la sécurité du patient et pour la qualité des soins que la formation initiale et la formation continue en masso-kinésithérapie soient réalisées dans le cadre d'une discipline en masso-kinésithérapie sous la responsabilité d'enseignants-chercheurs en masso-kinésithérapie. / The profession of physiotherapist is located at a crossroads. Ongoing reforms lead to questioning the knowledge and skills taught physiotherapists to ensure patient safety and quality of care. It was sought to know the origin of knowledge in physiotherapy devices and evaluate teaching and ownership of such knowledge by students and health professionals. The study results show that the differences are expected to skills related to teaching methods and assessment used by teachers in initial training and continuing education. It appears that the teaching methods used by teachers are often based on a theoretical foundation behaviorist model evaluation and control practices that prevent access dogmatic thinking and practice "complex" care. Training of physiotherapists does not optimize the skills development of reflexivity, critical thinking and innovation needed in the human relationship of care and patient safety ideal. This thesis shows the major interest to carry out physiotherapy lessons by teachers and researchers who think, write, discoursing, act differently trainers in initial training and continuing education. It is therefore essential for patient safety and quality of care that initial training and continuing education in physiotherapy are carried out within the framework of a discipline physiotherapy under the responsibility of teachers researchers in physiotherapy.

Les grands projets urbains sont devenus des éléments indispensables des stratégies de développement local, dans un contexte de compétition entre les territoires. Leur pilotage nécessite souvent une remise en question des formes organisationnelles convenues de l'action publique. Ainsi, le programme Constellation, opération toulousaine réunissant une zone industrielle et deux éco-quartiers, a été l’occasion de ré-instruire les connaissances et les pratiques urbaines locales. Ce processus se matérialise dans des instruments d’action délibérément mobilisés pour domestiquer l’incertitude générée par la mise à distance du fonctionnement traditionnel du système de fabrication de la ville. Ces instruments, qui peuvent être des chartes, des équipes-projets, des procédures de désignation d’urbanistes ou d’architectes, des normes qualité ou des bases-vie de chantier, mobilisent de nouveaux acteurs et de nouvelles formes managériales. Les usagers leur attribuent une capacité à transformer la culture du projet urbain. Cette thèse vise à comprendre comment les acteurs instrumentent leur action en situation d’incertitude. Elle montre que l’action instrumentée active quatre types de médiation, pragmatique, épistémique, interactive et symbolique, dont les combinaisons produisent quatre mécanismes de confinement des problèmes : la socialisation et la communalisation, la sélection et la socialisation. L’ensemble rend compte d’une politisation de l’action, dans la mesure où les instruments transforment la nature des échanges, passant d’échanges économiques à des échanges politiques. / Large urban projects have come to play an indispensible part in local development strategies, in the context of competition between areas. Their successful conduct often requires calling into question conventional ways of organizing public action. The Constellation project in Toulouse, including an industrial zone and two eco-neighborhoods, provides an occasion to re-examine local urban knowledge and practices. This process is seen in the tools used deliberately to calm the incertitude caused by departures from traditional ways of building cities. They can include charters, team projects, procedural designations of urbanists and architects, drawing up of quality standards and managing on-site locales. They mobilize new participants and new forms of management. Users of the site accredit them with an ability to transform an urban project’s culture. This doctoral thesis intends to provide an understanding of how participants use these tools in a situation of uncertainty. It shows how action involves four types of mediation: pragmatic, epistemic, interactive, and symbolic. Combinations of these produce four mechanisms for delimiting problems: association and community building, selection and socialization. The whole gives an account of the politicization of action insofar as the tools transform the nature of exchanges, from economic to political ones.

De nombreux problèmes de la vie réelle sont NP-Difficiles et ne peuvent pas être résolus en temps polynomial. Deux paradigmes notables pour les résoudre quand même sont: l'approximation et la complexité paramétrée. Dans cette thèse, on présente une nouvelle technique appelée "gloutonnerie-Pour-La-Paramétrisation". On l'utilise pour établir ou améliorer la complexité paramétrée de nombreux problèmes et également pour obtenir des algorithmes paramétrés pour des problèmes à cardinalité contrainte sur les graphes bipartis. En vue d'établir des résultats négatifs sur l'approximabilité en temps sous-Exponentiel et en temps paramétré, on introduit différentes méthodes de sparsification d'instances préservant l'approximation. On combine ces "sparsifieurs" à des réductions nouvelles ou déjà connues pour parvenir à nos fins. En guise de digestif, on présente des résultats de complexité de jeux comme le Bridge et Havannah. / Several real-Life problems are NP-Hard and cannot be solved in polynomial time.The two main options to overcome this issue are: approximation and parameterized complexity. In this thesis, we present a new technique called greediness-For-Parameterization and we use it to improve the parameterized complexity of many problems. We also use this notion to obtain parameterized algorithms for some problems in bipartite graphs. Aiming at establishing negative results on the approximability in subexponential time and in parameterized time, we introduce new methods of sparsification that preserves approximation. We combine those "sparsifiers" with known or new reductions to achieve our goal. Finally, we present some hardness results of games such as Bridge and Havannah.

Cette thèse porte sur un certain nombre de problèmes algorithmiques motivés par la planification temporelle automatisée et la vérification formelle des systèmes réactifs et finis. Nous nous sommes concentrés sur les méthodes théoriques des jeux pour obtenir de nouvelles connaissances, des limites de complexité améliorées et des algorithmes plus rapides pour les modèles suivants: réseaux temporels hyper, réseaux conditionnels Simples / Hyper temporels, jeux de mise à jour, jeux Muller McNaughton et jeux Mean Payoff / This dissertation deals with a number of algorithmic problems motivated by automated temporal planning and formal verification of reactive and finite state systems. We focused on game theoretical methods to obtain novel insights, improved complexity bounds, and faster algorithms for the following models: Hyper Temporal Networks, Conditional Simple/Hyper Temporal Networks, Update Games, Muller McNaughton Games, and Mean Payoff Games

Nous considérons un problème d'ordonnancement à une machine avec dates de fin impératives et nous cherchons caractériser l'ensemble des solutions optimales, sans les énumérer. Nous supposons que les travaux sont numérotés selon la règle EDD et que cette séquence est réalisable. La méthode consiste à utiliser le treillis des permutations et d'associer à la permutation maximale du treillis la séquence EDD. Afin de caractériser beaucoup de solutions, nous cherchons une séquence réalisable aussi loin que possible de cette séquence. La distance utilisée est le niveau de la séquence dans le treillis, qui doit être minimum (le plus bas possible). Cette nouvelle fonction objectif est étudiée. Quelques cas particuliers polynomiaux sont identifiés, mais la complexité du problème général reste ouverte. Quelques méthodes de résolution, polynomiales et exponentielles, sont proposées et évaluées. Le niveau de la séquence étant en rapport avec la position des travaux dans la séquence, de nouvelles fonctions objectifs en rapport avec les positions des travaux sont identifiées et étudiées. Le problème de la minimisation de la somme pondérée des positions des travaux est prouvé fortement NP-difficile. Quelques cas particuliers sont étudiés et des méthodes de résolution proposées et évaluées. / We consider a single machine scheduling problem with deadlines and we want to characterise the set of optimal solutions, without enumerating them. We assume that jobs are numbered in EDD order and that this sequence is feasible. The key idea is to use the lattice of permutations and to associate to the supremum permutation the EDD sequence. In order to characterize a lot of solutions, we search for a feasible sequence, as far as possible to the supremum. The distance is the level of the sequence in the lattice, which has to be minimum. This new objective function is investigated. Some polynomially particular cases are identified, but the complexity of the general case problem remains open. Some resolution methods, polynomial and exponential, are proposed and evaluated. The level of the sequence being related to the positions of jobs in the sequence, new objective functions related to the jobs positions are identified and studied. The problem of minimizing the total weighted positions of jobs is proved to be strongly NP-hard. Some particular cases are investigated, resolution methods are also proposed and evaluated.

Il existe de nombreuses approches développées par la communauté Implicit Computational Complexity (ICC) permettant d'analyser les ressources nécessaires à la bonne exécution des algorithmes. Dans cette thèse, nous nous intéressons plus particulièrement au contrôle des ressources à l'aide d'interprétations sémantiques. Après avoir rappelé brièvement la notion de quasi-interprétation ainsi que les différentes propriétés et caractérisations qui en découlent, nous présentons les différentes avancées obtenues dans l'étude de cet outil : nous étudions le problème de la synthèse qui consiste à trouver une quasi-interprétation pour un programme donné, puis, nous abordons la question de la modularité des quasi-interprétations. La modularité permet de diminuer la complexité de la procédure de synthèse et de capturer un plus grand nombre d'algorithmes. Après avoir mentionné différentes extensions des quasi-interprétations à des langages de programmation réactifs, bytecode ou d'ordre supérieur, nous introduisons la sup-interprétation. Cette notion généralise la quasi-interprétation et est utilisée dans des critères de contrôle des ressources afin d'étudier la complexité d'un plus grand nombre d'algorithmes dont des algorithmes sur des données infinies ou des algorithmes de type diviser pour régner. Nous combinons cette notion à différents critères de terminaison comme les ordres RPO, les paires de dépendance ou le size-change principle et nous la comparons à la notion de quasi-interprétation. En outre, après avoir caractérisé des petites classes de complexité parallèles, nous donnons quelques heuristiques permettant de synthétiser des sup-interprétations sans la propriété sous-terme, c'est à dire des sup-interprétations qui ne sont pas des quasi-interprétations. Enfin, dans un dernier chapitre, nous adaptons les sup-interprétations à des langages orientés-objet, obtenant ainsi différents critères pour contrôler les ressources d'un programme objet et de ses méthodes / There are several approaches developed by the Implicit Computational Complexity (ICC) community which try to analyze and control program resources. In this document, we focus our study on the resource control with the help of semantics interpretations. After introducing the notion of quasi-interpretation together with its distinct properties and characterizations, we show the results obtained in the study of such a tool: We study the synthesis problem which consists in finding a quasi-interpretation for a given program and we tackle the issue of quasi-interpretation modularity. Modularity allows to decrease the complexity of the synthesis procedure and to capture more algorithms. We present several extensions of quasi-interpretations to reactive programming, bytecode verification or higher-order programming. Afterwards, we introduce the notion of sup-interpretation. This notion strictly generalizes the one of quasi-interpretation and is used in distinct criteria in order to control the resources of more algorithms, including algorithms over infinite data and algorithms using a divide and conquer strategy. We combine sup-interpretations with distinct termination criteria, such as RPO orderings, dependency pairs or size-change principle, and we compare them to the notion of quasi-interpretation. Using the notion of sup-interpretation, we characterize small parallel complexity classes. We provide some heuristics for the sup-interpretation synthesis: we manage to synthesize sup-interpretations without the subterm property, that is, sup-interpretations which are not quasi-interpretations. Finally, we extend sup-interpretations to object-oriented programs, thus obtaining distinct criteria for resource control of object-oriented programs and their methods