Nous nous intéressons dans cette thèse aux approches basées sur la restauration de la cohérence à partir de bases de croyances stratifiées ainsi qu'à partir de bases de croyances partiellement préordonnées (BCPP). Dans le premier cas, nous nous attaquons aux problèmes de complexité en proposant trois nouvelles approches de compilation que nous qualifions de flexibles en étant paramétrées par n'importe quel langage cible de compilation. La première concerne l'inférence possibiliste et s'adapte facilement à l'inférence linéaire. La seconde approche se rapporte à l'inférence lexicographique et se base sur la notion de contraintes de cardinalité Booléennes. Nous introduisons aussi une nouvelle compilation pour l'inférence MSP (pour Minimum de Specificity Principle). En ce qui concerne le raisonnement à partir de BCPPs qui offrent plus de flexibilité dans de nombreuses situations, notre première contribution consiste en l'introduction d'une extension de l'inférence lexicographique classique qui revêt un vif intérêt. La seconde contribution dans ce même cadre, est l'étude comparative des différentes relations d'inférence à partir de BCPPs relativement à la complexité, les propriétés logiques et la prudence. Une dernière contribution est l'application du raisonnement en présence d'incohérence dans le cadre de la détection d'intrusions coopérative. En effet, nous proposons une nouvelle approche de corrélation d'alertes. Cette approche se base sur le raisonnement à partir de BCPPs exprimées en logiques de description qui sont bien adaptées à la représentation des informations structurées tout en garantissant la décidabilité du raisonnement. / In this thesis, we are interested in coherence based approaches from both stratified belief bases and partially preordered belief bases (PPBB). In the first case, we tackle the complexity problems by proposing three new compilation approaches. The first one is about the possibilistic inference and applies easily to linear inference. The second approach is relative to lexicographic inference and is based on Boolean cardinality constraints. We also introduce a novel compilation approach for MSP entailment (MSP for Minimum Specificity Principle). As to reasoning from PPBBs which offer much more flexibility in many situations, our first contribution consists in extending the lexicographic inference which has interesting properties. The second contribution is a comparative study of the different inference relations from PPBBs with respect to three key dimensions, namely the complexity, the logical properties and the cautiousness. The last contribution is the application of reasoning under inconsistency in the case of intrusion detection. More precisely, we propose a new correlation approach. This latter is based on reasoning from PPBBs expressed in description logics, which are suitable to represent structured informations by ensuring the decidability of reasoning.

Les résultats de Colson ou de Moschovakis remettent en question que le modèle récursif primitif puisse calculer une valeur par tous les moyens possibles : il y a toutes les fonctions voulues mais il manque des algorithmes. La thèse de Church exprime donc plutôt ce qui peut être calculé que comment le calcul est fait. Nous utilisons la thèse de Gurevich formalisant l'idée intuitive d'algorithme séquentiel par les Abstract States Machines (ASMs).Nous représentons les programmes impératifs par le langage While de Jones, et une variante LoopC du langage de Meyer et Ritchie permettant de sortir d'une boucle lorsqu'une condition est remplie. Nous dirons qu'un langage caractérise une classe algorithmique si les modèles de calcul associés peuvent se simuler mutuellement, en utilisant une dilatation temporelle et un nombre borné de variables temporaires. Nous prouvons que les ASMs peuvent simuler While et LoopC, que si l'espace est primitif récursif alors LoopC est en temps récursif primitif, et que sa restriction LoopC_stat où les bornes des boucles ne peuvent être mises à jour est en temps polynomial. Réciproquement, une étape d'ASM peut être traduite par un programme sans boucle, qu'on peut répéter suffisamment en l'insérant dans un programme qui est dans While si la complexité est quelconque, dans LoopC si elle est récursif primitif, et dans LoopC_stat si elle est polynomiale.Ainsi While caractérise les algorithmes séquentiels en temps quelconque, LoopC ceux en temps et espace récursifs primitifs, et LoopC_stat ceux en temps polynomial / Colson and Moschovakis results cast doubt on the ability of the primitive recursive model to compute a value by any means possible : the model may be complete for functions but there is a lack of algorithms. So the Church thesis express more what can be computed than how the computation is done. We use Gurevich thesis to formalize the intuitive idea of sequential algorithm by the Abstract States Machines (ASMs).We formalize the imperative programs by Jones' While language, and a variation LoopC of Meyer and Ritchie's language allowing to exit a loop if some condition is fulfilled. We say that a language characterizes an algorithmic class if the associated models of computations can simulate each other using a temporal dilatation and a bounded number of temporary variables. We prove that the ASMs can simulate While and LoopC, that if the space is primitive recursive then LoopC is primitive recursive in time, and that its restriction LoopC_stat where the bounds of the loops cannot be updated is in polynomial time. Reciprocally, one step of an ASM can be translated into a program without loop, which can be repeated enough times if we insert it onto a program in While for a general complexity, in LoopC for a primitive recursive complexity, and in LoopC_stat for a polynomial complexity.So While characterizes the sequential algorithms, LoopC the algorithms in primitive recursive space and time, and LoopC_stat the polynomial time algorithms

La complexité qui traverse l'épidémiologie sociale et la médecine légale du vivant est de celle que l'on cherche à saisir par la variété des observations et par l'intrication de points de vue et d'échelles différentes - l'individu, le groupe, la société. Les méthodes du biomédical sont encore peu adaptées au traitement de la complexité, à sa représentation qui ne soit pas normative, statistique. Il existe un ensemble d'approches non statistiques, " non classiques ", qui puissent traiter simultanément un grand nombre de dimensions et qui permettent de réduire la complexité apparente en dégageant des objets d'étude spécifique. Nous présentons ici les principes et l'utilisation des techniques de reconnaissance de forme dans le cadre de l'épidémiologie sociale, en les appliquant à la recherche d'une typologie de recours aux soins, sur la base des données de la cohorte SIRS. Nous expliquons en quoi ces approches ont leur place, épistémologiquement et techniquement parlant, aux côtés des méthodes expérimentales classiques type essais randomisés contrôlés. Nous exposons également un autre moyen de réduire la complexité des données, tout en en préservant les qualités topologiques. Nous introduisons en médecine légale la notion de dimension intrinsèque, plus petite dimension nécessaire et suffisante à la description des données, et de techniques non linéaires de réduction de la dimension. Nous en appliquons les principes au cas de l'intégration de sources d'information multiples pour l'estimation de l'âge chez les adolescents migrants. Enfin, nous discutons les avantages et limites de ces approches ainsi que les perspectives qu'elles ouvrent à ces deux disciplines complémentaires. / Social epidemiology and clinical legal medicine are hybrid objects that articulate several fields, accounting for social and interpersonal relationships. The complexity that characterizes them both is investigated through different viewpoints, scales and dimensions: the individual scale, the group scale and the society scale. The techniques used in biomedicine are not designed to properly deal with such a complexity, in a non-normative way. A wide range of alternative non-statistical, “non-classical” methods exist that can process simultaneously various dimensions so that we can reduce the apparent complexity of data while discovering scientific objects. Here, we present the principles and the use of clustering techniques, applied to social epidemiology. We applied different clustering techniques on data from the SIRS cohort to build a typology of healthcare utilization in the Paris metropolitan area. From an epistemological and technical viewpoint, we explain why these methods should take place beside other recognized but limited techniques such as randomized controlled trials. We introduce another but complementary kind of complexity reduction technique. The concept of intrinsic dimension is explained – the littlest dimension needed to describe properly data – and nonlinear dimensionality reduction techniques are applied in clinical legal medicine. With these tools, we explore whether the integration of multiple information sources is relevant in age estimation of living migrants. Finally, we discuss the pros and cons of these methods, as well as the opportunities they may create for both fields of social epidemiology and clinical legal medicine.

Orientador: Messias Modesto dos Passos / Resumo: O conceito de geossistema é constantemente mencionado no debate geográfico relacionado aos estudos paisagísticos e ambientais, fato que remonta ao seu protagonismo teórico-metodológico na constituição da interface entre geografia e abordagem sistêmica. Mesmo diante da importância do conceito para a ciência geográfica, não tem havido atenção especial ao entendimento dos diferentes legados científicos estrangeiros que suportam a pesquisa nacional sobre o tema. Também não há, em território nacional, um debate de fôlego que demonstre como o geossistema tem sido operacionalizado nos estudos articuladores sociedade ↔ natureza. Nesse âmbito, objetivou-se, de modo geral, analisar o uso do conceito de geossistema pela pós-graduação em geografia no Brasil entre 1971 e 2015, considerando as suas trajetórias e tendências junto aos estudos dedicados à relação sociedade ↔ natureza. Para o alcance de tal objetivo, discutiram-se as perspectivas históricas e os legados internacionais sobre o tema; a produção geográfica nacional sobre geossistema e suas relações com a paisagem e o ambiente; a importância da correlação entre conceitos particulares e complementares ao debate do ordenamento – paisagístico e ambiental – dos territórios; e, por fim, realizou-se um debate visando à ressignificação conceitual e à prática analítica sobre o tema. Para isso, a partir de uma metodologia articuladora pautada no pensamento da complexidade e em análise histórica, documental e comparativa, realizou-se a recu... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: The concept of geosystems is constantly addressed in the geographical debate related to landscape and environmental studies, a fact that resumes the concept's theoretical and methodological role in constituting the interface between geography and the systemic approach. Even despite the importance of the concept for geographical science, no special attention has been given to understanding the different foreign scientific legacies underlying the national research on the subject; nor is there a national debate that demonstrates how geosystems have been operationalized in studies articulating society and nature. In this vein, the primary objective of this study was to analyze how the concept of geosystems has been used by graduate programs in geography in Brazil between 1971 and 2015, considering the concept’s trajectories and trends in studies addressing the society-nature relationship. To this end, the study discussed historical perspectives and international legacies on the subject; national publications on geosystem and its relationship with landscape and the environment; the importance of correlating concepts that are specific and complementary to the debate of (landscape and environmental) territorial planning; and, finally, argued in favor of a conceptual reframing and analytical practices on the subject. Therefore, based on an articulating methodology encompassing complex thought and historical, documentary and comparative analysis, the study recovered the national and i... (Complete abstract click electronic access below) / Résumé: Le concept de géosystème est constamment abordé dans le débat géographique lié aux études paysagères et environnementales, ce qui remonte au rôle théorique et méthodologique dans la constitution de l’interface entre la géographie et l’approche systémique. Malgré l'importance du concept pour la science géographique, aucune attention particulière n'a été accordée à la compréhension des différents héritages scientifiques étrangers qui soutiennent la recherche nationale sur le sujet. Il n'y a pas non plus de débat national qui montre comment le géosystème a été opérationnalisé dans les études sur la société et la nature. Dans cette optique, l’objectif principal de cette étude était d’analyser la manière dont le concept de géosystème a été utilisé par les programmes de troisième cycle en géographie au Brésil entre 1971 et 2015, en prenant en compte les trajectoires et les tendances de ce concept dans les études traitant de la relation société-nature. À cette fin, l’étude a examiné les perspectives historiques et l’héritage internationale sur le sujet; les publications nationales sur le géosystème et sa relation avec le paysage et l'environnement; l'importance de corréler des concepts spécifiques et complémentaires au débat sur l'aménagement (paysager et environnemental) du territoire; et, enfin, a préconisé un recadrage conceptuel et des pratiques analytiques sur le sujet. Pour cela, reposant sur une méthodologie articulée englobant pensée complexe et analyse historique, documenta... (Résumé complet accès életronique ci-dessous) / Doutor

Petits, isolés, vulnérables, les territoires insulaires apparaissent comme les symboles des interrogations sur la soutenabilité des systèmes économiques. Cette coïncidence n’a rien de fortuite. Les expériences insulaires et coloniales occupent une place centrale dans la formation de l’économie politique, qui s’intéresse initialement tant à l’accroissement des richesses qu’à la pérennité de cette dynamique, notamment en raison des contraintes écologiques. Réciproquement, l’économie politique nourrit la formation d’un nouvel art de gouverner qui influence en profondeur les trajectoires insulaires et produit des rapports de pouvoir, qui persistent encore. Notamment à travers la notion de développement (durable) qui naturalise une lecture utilitariste de la soutenabilité. En rapprochant le paradigme de la complexité, l’économie écologique et les approches poststructuralistes, cette thèse propose d’explorer la construction de ce concept puis de le repenser dans un cadre institutionnaliste qui intègre pleinement les facteurs écologiques, symboliques et sociaux et la pluralité des formes d’organisation des économies. Elle étudie ensuite la construction et les ressorts de l’économie de plantation, à La Réunion et dans les Caraïbes, en interrogeant le paradoxe de l’ « insoutenabilité durable » : comment une économie fondée sur la destruction et incapable de satisfaire les finalités assignées en raison de ses contradictions, peut-elle se maintenir dans la longue durée ? Une troisième partie questionne la soutenabilité du projet départemental : décréter le développement, métamorphoser une colonie ruinée en une économie moderne, équilibrée, tirée par une croissance auto-entretenue. / Small, isolated and vulnerable, islands have become symbols in current debates on the sustainability of economic systems. This is no coincidence. For colonial and insular experiences have played a key role in the emergence of political economy, which, initially focused on the creation of wealth as much as on its durability. Conversely, political economy nurtured the development of a new “art of government” which has deeply influenced islands trajectories and engendered new relations of power that persist today. In particular through the concept of (sustainable) development that naturalizes a contingent, utilitarian, view of sustainability. By bringing together the paradigm of complexity, ecological economics and poststructuralist works, this thesis aims to deconstruct this concept and reframe it through an institutionalist and interdisciplinary approach that fully integrates ecological, symbolic and social factors as well as the multiplicity of economies. It then studies the formation and evolution of plantation economies, both in Reunion Island and the Caribbean, to question the paradox of “durable unsustainability”: why and how can an economy grounded on destruction and unable to satisfy the ends it was designed for, maintain itself on the long term? A third part queries the sustainability of the “departementalisation” project, i.e. decreeing development: turning a ruined colony in a modern economy, able to reach European standards through self-sustained growth. It thus emphasizes the retroactions that wiped this utopia out to give birth to an original, yet fragile, model of resilient dependence.

Cette thèse est une modélisation diasystémique de la flexion verbale de cinq langues sames (famille finno-ougrienne), qui s'inscrit dans le cadre théorique des systèmes complexes. Elle se pose à l'intersection entre la complexité flexionnelle, avec pour but de démêler et modéliser les phénomènes intriqués d'allomorphie paradigmatique, et la complexité dialectale, en comparant cinq systèmes flexionnels de langues formant un réseau dialectal pour déterminer les mécanismes de différentiation et les flux interactifs qui entrent en jeu au sein du diasystème. L'analyse morphologique fait usage du modèle Paradigm Function Morphology, une approche réalisationnelle de la complexité paradigmatique développée par G. Stump, qui permet de modéliser le grand nombre d'alternances thématiques qui font la réputation d'extrême complexité de la flexion same. L'analyse des paradigmes débouche sur une taxinomie des verbes sames, sous la forme de classes flexionnelles, dans chacune des langues étudiées (sames du Sud, de Lule, du Nord, d'Inari et same Skolt), et sur un inventaire détaillé des mécanismes de flexion. À partir de ces modélisations comparables, je développe ensuite une analyse diasystémique de la morphologie verbale same en en interprétant les processus d'intrication, d'auto-organisation et d'émergence au sein du système. La configuration qui en ressort, renforcée par une étude dialectométrique, est celle d'un système dialectal à deux pôles décisionnels majeurs, ouest et est, et au centre une zone de transition et de compromis où se produisent des phénomènes de complexification phonologique et morphologique. / This thesis analyzes the verbal inflection of five Saami languages (Finno-Ugric family) in a diasystemic modelization, working within the framework of Complex Systems Theory. It deals with both inflectional complexity, aiming to untangle and model the intricacy of paradigmatic allomorphy in Saami, and dialectal complexity, by comparing the inflectional systems of five languages organized in a dialect continuum, in order to highlight the mechanisms of differentiation and interactive flows within the diasystem.The morphological analysis uses Paradigm Function Morphology, a realizational approach to paradigmatic complexity developed by G. Stump. This framework gives me the tools needed to model the great number of stem alternations that makes Saami inflection renowned for its extreme complexity. From the paradigm analysis, I work to build a taxonomy of Saami verbs, in the form of inflectional classes, in each of the studied languages (South, Lule, North, Inari and Skolt Saami), and a detailed inventory of inflection mechanisms. Based on these comparable models, I then develop a diasystemic analysis of Saami verbal morphology by modeling the processes of intrication, self-organization and emergence happening in the system. The resulting configuration, reinforced by a dialectometric study, is that of a system with two major decision centers, western and eastern, and in the center a transitional zone of compromise where phonological and morphological complexification phenomena arise.

Quels sont les modes de réponses les plus adaptés au traitement de l’inattendu et sous contrainte de temps pour maintenir ou renforcer la fiabilité organisationnelle ? Les travaux du courant HRO (High Reliability Organization) et du courant actionniste convergent sur le fait que l’individu constitue une source de fiabilité. Ils divergent néanmoins sur l’importance donnée au respect des règles face aux évènements imprévus. Afin d’analyser les comportements d’adaptation d’individus au sein d’un groupe restreint face à des situations à risques et inattendues sous contrainte de temps, l’attention est portée sur l’étude de situations nautiques vécues par des bâtiments de surface de la Marine nationale. Une première approche qualitative menée auprès d’experts du terrain étudié complétée par une approche quantitative réalisée à partir de 237 situations nautiques font ressortir les configurations à risques à l’origine d’accidents nautiques. Ces informations nous permettent de soumettre des équipes de quart passerelle à des situations à risques, dans le cadre d’une expérimentation, au moyen du simulateur de navigation de l’Ecole navale, école de formation des officiers de la Marine nationale. Les comportements de 96 équipes de quart passerelle, en formation initiale, sur le simulateur de navigation permettent de tester, selon les différentes situations, les réponses associées : improvisation de procédure, recours aux règles avec ou non l’usage de méta règles. Les résultats de l’expérimentation soulignent l’intérêt des méta règles dans le traitement des situations à haut niveau de complexité et nécessitant d’agir rapidement mais aussi les risques d’une improvisation non cadrée. / What are the best types of answers given by a 4-member team of the French Navy without expertise in unexpected situations under time pressure in order to maintain or to increase organizational reliability ? HRO researchers agree with Interactionists on the fact that human beings can be considered as a reliability factor. Nevertheless, they disagree on one point: the need to respect the rules or not in unexpected events. A first qualitative study completed by a quantitative one (based on 237 nautical situations), emphasize different types of risk situations, responsible for accidents. Thanks to this data, an experiment based on the behavioral observations of 96 bridge-teams is set up on the simulator of the French Naval Academy, which trains all future officers of the French Navy. The aim of this work is to test different proposals of variables using either improvisation or rules, with or without meta rules. Results show that firstly, thanks to meta rules, the level of reliability is higher in high level complex situations under time pressure and secondly, results underline the risk of an improvised action without guidelines

Malgré une littérature abondante sur les conséquences des technologies de l'information et de la communication (TIC), cette littérature n'aborde que trop peu les conséquences sociétales, qu'elles soient positives ou négatives, intentionnelles ou non. Parce que les interactions se propagent au-delà de l'espace en ligne et de ces conséquences paradoxales, les défis sociétaux sont un problème complexe. C'est pour ces raisons que nous avons besoin d'une meilleure compréhension des problèmes sociaux complexes. Pour ce faire, nous avons adopté le modèle de la thèse sur travaux. Les trois études de ce travail de doctorat adoptent une approche qualitative et un positionnement réaliste critique. Nous examinons un premier cas : celui du Printemps Arabe et l'utilisation de Facebook. Etudier ces types d'événements contemporains ne vient pas sans difficultés analytiques. Par conséquent, nous utilisons un outil d'analyse sémiotique pour faire face à la complexité représentationnelle des données recueillies. Enfin, les communautés en ligne peuvent également générer des coûts sociaux en fournissant un espace se faisant l'écho à des comportements socialement indésirables. / Despite the wide literature on the consequences of Information and Communication Technologies (ICTs) use, the literature still lacks understanding about the societal consequences, positive or negative, intended or unintended. Consequences of technology usages on society are paradoxical. The paradoxical outcomes can be threat to the sustainability of society. Because interactions spread beyond the online space and its outcomes are paradoxical, societal challenges are complex problem. To harvest society, we need a better understanding of social complex problems. To do so, we adopted a multi-study dissertation model. The three studies of this doctoral work adopt a qualitative approach and a critical realist philosophy.We look at a first case: The Arab Spring and aim at understanding how an online community that started on Facebook materialized in urban space, changing the political landscape. Addressing these contemporaneous events does not come without analytical challenges. Therefore, we use and extend a semiotic analytical tool to face the representational complexity: Finally, online communities can also have social costs by providing an echo chamber to socially undesirable behaviors.

Nous étudions des problèmes NP-difficiles portant sur les graphes contenant des blocages.Nous traitons les problèmes de coupes du point de vue de la complexité paramétrée. La taille p de la coupe est le paramètre. Étant donné un ensemble de sources {s1,...,sk} et une cible t, nous proposons un algorithme qui construit une coupe de taille au plus p séparant au moins r sources de t. Nous nommons ce problème NP-complet Partial One-Target Cut. Notre algorithme est FPT. Nous prouvons également que la variante de Partial One-Target Cut, où la coupe est composée de noeuds, est W[1]-difficile. Notre seconde contribution est la construction d'un algorithme qui compte les coupes minimums entre deux ensembles S et T en temps $2^{O(plog p)}n^{O(1)}$.Nous présentons ensuite plusieurs résultats sur le ratio de compétitivité des stratégies déterministes et randomisées pour le problème du voyageur canadien.Nous prouvons que les stratégies randomisées n'utilisant pas de mémoire ne peuvent pas améliorer le ratio 2k+1. Nous apportons également des éléments concernant les bornes inférieures de compétitivité de l'ensemble des stratégies randomisées. Puis, nous étudions la compétitivité en distance d'un groupe de voyageurs avec et sans communication. Enfin, nous nous penchons sur la compétitivité des stratégies déterministes pour certaines familles de graphes. Deux stratégies, avec un ratio inférieur à 2k+1 sont proposées: une pour les graphes cordaux avec poids uniformes et l'autre pour les graphes où la taille de la plus grande coupe minimale séparant s et t est au plus k. / We study NP-hard problems on graphs with blockages seen as models of networks which are exposed to risk of failures.We treat cut problems via the parameterized complexity framework. The cutset size p is taken as a parameter. Given a set of sources {s1,...,sk} and a target $t, we propose an algorithm which builds a small edge cut of size p separating at least r sources from t. This NP-complete problem is called Partial One-Target Cut. It belongs to the family of multiterminal cut problems. Our algorithm is fixed-parameter tractable (FPT) as its execution takes $2^{O(p^2)}n^{O(1)}$. We prove that the vertex version of this problem, which imposes cuts to contain vertices instead of edges, is W[1]-hard. Then, we design an FPT algorithm which counts the minimum vertex (S,T)-cuts of an undirected graph in time $2^{O(plog p)}n^{O(1)}$.We provide numerous results on the competitive ratio of both deterministic and randomized strategies for the Canadian Traveller Problem. The optimal ratio obtained for the deterministic strategies on general graphs is 2k+1, where k is a given upper bound on the number of blockages. We show that randomized strategies which do not use memory cannot improve the bound 2k+1. In addition, we discuss the tightness of lower bounds on the competitiveness of randomized strategies. The distance competitive ratio for a group of travellers possibly equipped with telecommunication devices is studied. Eventually, a strategy dedicated to equal-weight chordal graphs is proposed while another one is built for graphs with small maximum (s,t)-cuts. Both strategies outperform the ratio 2k+1.

Cette thèse porte sur des minorants pour des mesures de complexité liées à des sous-classes de la classe P de langages pouvant être décidés en temps polynomial par des machines de Turing. Nous considérons des modèles de calcul non uniformes tels que les programmes sur monoïdes et les programmes de branchement. Notre première contribution est un traitement abstrait de la méthode de Nečiporuk pour prouver des minorants, indépendamment de toute mesure de complexité spécifique. Cette méthode donne toujours les meilleurs minorants connus pour des mesures telles que la taille des programmes de branchements déterministes et non déterministes ou des formules avec des opérateurs booléens binaires arbitraires ; nous donnons une formulation abstraite de la méthode et utilisons ce cadre pour démontrer des limites au meilleur minorant obtenable en utilisant cette méthode pour plusieurs mesures de complexité. Par là, nous confirmons, dans ce cadre légèrement plus général, des résultats de limitation précédemment connus et exhibons de nouveaux résultats de limitation pour des mesures de complexité auxquelles la méthode de Nečiporuk n'avait jamais été appliquée. Notre seconde contribution est une meilleure compréhension de la puissance calculatoire des programmes sur monoïdes issus de petites variétés de monoïdes finis. Les programmes sur monoïdes furent introduits à la fin des années 1980 par Barrington et Thérien pour généraliser la reconnaissance par morphismes et ainsi obtenir une caractérisation en termes de semi-groupes finis de NC^1 et de ses sous-classes. Étant donné une variété V de monoïdes finis, on considère la classe P(V) de langages reconnus par une suite de programmes de longueur polynomiale sur un monoïde de V : lorsque l'on fait varier V parmi toutes les variétés de monoïdes finis, on obtient différentes sous-classes de NC^1, par exemple AC^0, ACC^0 et NC^1 quand V est respectivement la variété de tous les monoïdes apériodiques finis, résolubles finis et finis. Nous introduisons une nouvelle notion de docilité pour les variétés de monoïdes finis, renforçant une notion de Péladeau. L'intérêt principal de cette notion est que quand une variété V de monoïdes finis est docile, nous avons que P(V) contient seulement des langages réguliers qui sont quasi reconnus par morphisme par des monoïdes de V. De nombreuses questions ouvertes à propos de la structure interne de NC^1 seraient réglées en montrant qu'une variété de monoïdes finis appropriée est docile, et, dans cette thèse, nous débutons modestement une étude exhaustive de quelles variétés de monoïdes finis sont dociles. Plus précisément, nous portons notre attention sur deux petites variétés de monoïdes apériodiques finis bien connues : DA et J. D'une part, nous montrons que DA est docile en utilisant des arguments de théorie des semi-groupes finis. Cela nous permet de dériver une caractérisation algébrique exacte de la classe des langages réguliers dans P(DA). D'autre part, nous montrons que J n'est pas docile. Pour faire cela, nous présentons une astuce par laquelle des programmes sur monoïdes de J peuvent reconnaître beaucoup plus de langages réguliers que seulement ceux qui sont quasi reconnus par morphisme par des monoïdes de J. Cela nous amène à conjecturer une caractérisation algébrique exacte de la classe de langages réguliers dans P(J), et nous exposons quelques résultats partiels appuyant cette conjecture. Pour chacune des variétés DA et J, nous exhibons également une hiérarchie basée sur la longueur des programmes à l'intérieur de la classe des langages reconnus par programmes sur monoïdes de la variété, améliorant par là les résultats de Tesson et Thérien sur la propriété de longueur polynomiale pour les monoïdes de ces variétés. / This thesis deals with lower bounds for complexity measures related to subclasses of the class P of languages that can be decided by Turing machines in polynomial time. We consider non-uniform computational models like programs over monoids and branching programs.Our first contribution is an abstract, measure-independent treatment of Nečiporuk's method for proving lower bounds. This method still gives the best lower bounds known on measures such as the size of deterministic and non-deterministic branching programs or formulae{} with arbitrary binary Boolean operators; we give an abstract formulation of the method and use this framework to prove limits on the best lower bounds obtainable using this method for several complexity measures. We thereby confirm previously known limitation results in this slightly more general framework and showcase new limitation results for complexity measures to which Nečiporuk's method had never been applied.Our second contribution is a better understanding of the computational power of programs over monoids taken from small varieties of finite monoids. Programs over monoids were introduced in the late 1980s by Barrington and Thérien as a way to generalise recognition by morphisms so as to obtain a finite-semigroup-theoretic characterisation of NC^1 and its subclasses. Given a variety V of finite monoids, one considers the class P(V) of languages recognised by a sequence of polynomial-length programs over a monoid from V: as V ranges over all varieties of finite monoids, one obtains different subclasses of NC^1, for instance AC^0, ACC^0 and NC^1 when V respectively is the variety of all finite aperiodic, finite solvable and finite monoids. We introduce a new notion of tameness for varieties of finite monoids, strengthening a notion of Péladeau. The main interest of this notion is that when a variety V of finite monoids is tame, we have that P(V) does only contain regular languages that are quasi morphism-recognised by monoids from V. Many open questions about the internal structure of NC^1 would be settled by showing that some appropriate variety of finite monoids is tame, and, in this thesis, we modestly start an exhaustive study of which varieties of finite monoids are tame. More precisely, we focus on two well-known small varieties of finite aperiodic monoids: DA and J. On the one hand, we show that DA is tame using finite-semigroup-theoretic arguments. This allows us to derive an exact algebraic characterisation of the class of regular languages in P(DA). On the other hand, we show that J is not tame. To do this, we present a trick by which programs over monoids from J can recognise much more regular languages than only those that are quasi morphism-recognised by monoids from J. This brings us to conjecture an exact algebraic characterisation of the class of regular languages in P(J), and we lay out some partial results that support this conjecture. For each of the varieties DA and J, we also exhibit a program-length-based hierarchy within the class of languages recognised by programs over monoids from the variety, refining Tesson and Thérien's results on the polynomial-length property for monoids from those varieties.