La théorie des groupes de tresses s'inscrit au croisement de plusieurs domaines des mathématiques, en particulier, l'algèbre et la géométrie. La recherche actuelle s'étend dans chacune de ces directions, et de riches développements naissent du mariage de ces deux aspects. D'un point de vue géométrique, le groupe des tresses à n brins est vu comme le groupe modulaire d'un disque à n trous, avec composante de bord. On peut représenter une tresse par un diagramme de courbes, c'est-à-dire l'image d'une famille fixée d'arcs sur le disque, par l'élément correspondant du groupe modulaire. Dans cette thèse est présenté l'algorithme de relaxations par la droite, qui permet de retrouver, étant donné un diagramme de courbes, la tresse à partir de laquelle il a été obtenu. Cet algorithme aide à faire le lien entre des propriétés géométriques du diagramme de courbes, et des propriétés algébriques du mot de tresse, en permettant de repérer de grandes puissances d'un générateur sous forme de spirales dans le diagramme de courbes. D'un point de vue algébrique, le groupe de tresses est l'exemple classique de groupe de Garside. L'un des objectifs actuels des recherches en théorie de Garside est d'obtenir un algorithme de résolution en temps polynomial du problème de conjugaison dans les groupes de tresses. À cette fin, on cherche à exploiter les propriétés de certains ensembles finis de conjugués d'une tresse, qui sont des invariants de conjugaison. L'un des résultats de cette thèse concerne la taille d'un de ces invariants, l'ensemble super-sommital : on exhibe une famille de tresses pseudo-anosoviennes dont l'ensemble super-sommital est de taille exponentielle. González-Meneses avait déjà établi le résultat similaire pour une famille de tresses réductibles. La conséquence de ces résultats est qu'on ne peut pas espérer résoudre le problème de conjugaison en temps polynomial au moyen de cet ensemble, et qu'il vaut mieux chercher à exploiter des invariants plus petits. Dans le cas des tresses pseudo-anosoviennes, des espoirs résident actuellement en l'ensemble des circuits glissants. Dans cette thèse, un algorithme en temps polynomial s'appuyant sur ce dernier ensemble résout génériquement le problème de conjugaison, c'est-à-dire qu'il le résout pour une proportion de tresses tendant exponentiellement vite vers 1 lorsque la longueur de la tresse tend vers l'infini. On montre également que, dans une boule du graphe de Cayley avec pour générateurs les tresses simples, une tresse générique est pseudo-anosovienne, ce qui était une conjecture bien connue des spécialistes de la théorie de Garside. / The theory of braid groups is at the intersection of several areas of mathematics, especially algebra and geometry. The current research extends in each of these directions, leading to rich developments. From a geometrical point of view, the braid group on n strands is seen as the mapping class group of a disc with n punctures, with boundary component. A braid can be represented by a curve diagram, that is to say, the image of a family of arcs attached to the disc, by the corresponding mapping class. In this thesis we present the algorithm of relaxations from the right, which, given a curve diagram, determines the braid from which it was obtained. This algorithm helps us to make the link between geometric properties of the curve diagram and algebraic properties of the braid word, allowing us to identify great powers of a generator as spirals in the curve diagram. From an algebraic point of view, the braid group is the classical example of a Garside group. One of the objectives of current research in Garside theory is to obtain a polynomial time algorithm to solve the conjugacy problem in braid groups. For this, a possibility is to exploit the properties of some finite sets of conjugates of a braid, which are invariants of the conjugacy classes. One of the results of this thesis concerns the size of one of these invariants, the super summit set: we construct a family of pseudo-Anosov braids whose super summit set has exponential size. González- Meneses had already established the similar result for a family of reducible braids. These results implies that we cannot hope to solve the conjugacy problem in polynomial time through this set, and it is better to try to use smaller invariants. In the case of pseudo-Anosov braids, one may hope that the so-called sliding circuit set is more useful. In this thesis, we present a polynomial time algorithm based on this last set which generically solves the conjugacy problem, that is to say, it solves it for a proportion of braids that tends exponentially fast to 1 as the length of the braid tends to infinity. We also show that, in a ball of the Cayley graph with generators the simple braids, a braid is generically pseudo-Anosov, which was a well-known conjecture for the specialists in Garside theory.

Cette thèse revisite les problèmes d'accessibilité et de vivacité pour les au-tomates temporisés.L'accessibilité est couramment résolue par le calcul d'un arbre de recherche abstrait. L'abstraction est paramétrée par des bornes provenant des gardes de l'automate. Nous montrons que l'abstraction a 4LU de Behrmann et al. est la plus grande abstraction saine et complète pour les bornes LU. N' étant pas convexe, elle n'est pas mise en oeuvre dans les outils. Nous introduisons une méthode qui permet son utilisation éfficace. Finalement, nous proposons une optimisation des bornes à la volée exploitant le calcul de l'arbre.Le problème de vivacité requiert de détecter les exécutions Zenon/non-Zenon. Une solution standard ajoute une horloge à l'automate. Nous montrons qu'elle conduit a une explosion combinatoire. Nous proposons une solution qui évite ce problème pour une grande classe d'abstractions. Pour les abstractions LU nous montrons que détecter ces exécutions est un problèmeNP-complet. / We consider the classic model of timed automata introduced by Alurand Dill. Two fundamental properties one would like to check in this modelare reachability and liveness. This thesis revisits these classical problems.The reachability problem for timed automata asks if there exists a run ofthe automaton from the initial state to a given final state. The standard solutionto this problem constructs a search tree whose nodes are abstractionsof zones. For effectiveness, abstractions are parameterized by maximal lowerand upper bounds (LU-bounds) occurring in the guards of the automaton.Such abstractions are also termed as LU-abstractions. The a4LU abstractiondefined by Behrmann et al is the coarsest known LU-abstraction. Althoughit is potentially most productive to use the a4LU abstraction, it has not beenused in implementations as it could lead to non-convex sets. We show howone could use the a4LU abstraction efficiently in implementations. Moreover,we prove that a4LU abstraction is optimal: given only the LU-bound information,it is the coarsest possible abstraction that is sound and completefor reachability. We then concentrate on ways to get better LU-bounds. Inthe standard procedure the LU-bounds are obtained from a static analysisof the automaton. We propose a new method to obtain better LU-boundson-the-fly during exploration of the zone graph. The potential gains of proposedimprovements are validated by experimental results on some standardverification case studies.The liveness problem deals with infinite executions of timed automata.An infinite execution is said to be Zeno if it spans only a finite amountof time. Such runs are considered unrealistic. While considering infiniteexecutions, one has to eliminate Zeno runs or dually, find runs that arenon-Zeno. The B¨uchi non-emptiness problem for timed automata asks ifthere exists a non-Zeno run visiting an accepting state infinitely often. Thestandard solution to this problem adds an extra clock to take care of non-Zenoness. We show that this solution might lead to an exponential blowupin the search space. We propose a method avoiding this blowup for a wideclass of abstractions weaker than LU-abstractions. We show that such amethod does not exist for LU-abstractions unless P=NP. Another questionrelated to infinite executions of timed automata is to decide the existenceof Zeno runs. We provide the first complete solution to this problem. Itworks for a wide class of abstractions weaker than LU. Yet again, we showthe solution could lead to a blowup for LU-abstractions, unless P=NP.

La présente thèse décrit des travaux de recherches effectués sur des systèmes tutoriels intelligents (STI) et plus précisément sur les tuteurs par traçage de modèle (MTT). Les travaux de recherche présentés ici s’intéressent à la conception de MTT pour des domaines dans lesquels les étudiants peuvent résoudre la tâche qui leur est assignée de plusieurs façons. Ces domaines comportent parfois des algorithmes avec retour sur trace lorsque l’étudiant ne sait pas forcément quelles sont les alternatives qui feront progresser correctement l’état de la tâche.Cette thèse présente dans un premier temps un système de représentation de connaissances pour les algorithmes avec retour sur trace qui rend les connaissances de cet algorithme exploitables par des agents logiciels. Elle présente dans un second temps un ensemble de processus qui exploitent ces connaissances dans le cadre de MTT pour assurer automatiquement le suivi de l’étudiant et ainsi que la production d’interventions pédagogiques. En premier, ces interventions consistent à fournir à l'étudiant de l’aide pour la prochaine étape qui explique quelles sont les possibilités dont dispose l'étudiant et comment déterminer laquelle est la meilleure. En deuxième, elles fournissent à l'étudiant des rétroactions stratégiques qui lui confirment que son action est valide tout en l’informant de l’existence d’une meilleure alternative le cas échéant. Enfin, elles fournissent à l'étudiant des rétroactions négatives qui lui apprennent dans quelles situations les actions invalides qu’il vient d’effectuer s’appliquent.Une expérimentation a été réalisée avec des étudiants de biologie de l’Université de Sherbrooke pour évaluer les effets de ces interventions sur les choix des étudiants au cours de la résolution de la tâche. Les résultats de cette expérience montrent que les étudiants bénéficiant de ces interventions effectuent plus souvent des choix optimaux, et démontrent ainsi une plus grande maîtrise du domaine.

Les volumes des données générées par les technologies de séquençage haut débit augmentent exponentiellement ce dernier temps. Le stockage, le traitement et le transfertdeviennent des défis de plus en plus sérieux. Pour les affronter, les scientifiques doivent élaborer des approches et des algorithmes de plus en plus efficaces.Dans cette thèse, nous présentons des structures de données efficaces etdes algorithmes pour des problèmes de recherche approchée de chaînes de caractères, d'assemblagedu génome, de compression de séquences d’ADN et de classificationmétagénomique de lectures d’ADN.Le problème de recherche approchée a été bien étudié, avec un grandnombre de travaux publiés. Dans ledomaine de bioinformatique, le problème d’alignement de séquences peut être considéré comme unproblème de recherche approchée de chaînes de caractères. Dans notre travail, nousétudions une stratégie de recherche basée sur une structure d'indexation ditebidirectionnelle. D’abord, nous définissons un formalisme des schémas de recherche pour travailleravec les stratégies de recherche de ce type, ensuite nous fixons une mesure probabiliste del’efficacité de schémas de recherche et démontrons quelques propriétés combinatoires de schémasde recherche efficaces. Finalement, nous présentons des calculs expérimentaux quivalident la supériorité de nos stratégies. L’assemblage du génome est un des problèmes clefs en bioinformatique.Dans cette thèse, nous présentons une structure de données — filtre de Bloom en Cascade— qui améliore le filtre de Bloom standard et peut être utilisé pour larésolution de certains problèmes, y compris pour l’assemblage du génome. Nousdémontrons ensuite des résultats analytiques et expérimentaux sur les propriétés du filtre deBloom en Cascade. Nous présentons également comment le filtre de Bloom en Cascade peut être appliqué au problèmede compression de séquences d’ADN.Un autre problème que nous étudions dans cette thèse est la classificationmétagénomique de lectures d’ADN. Nous présentons une approche basée sur la transforméede Burrows-Wheeler pour la recherche efficace et rapide de k-mers (mots de longueur k).Cette étude est centrée sur les structures des données qui améliorent lavitesse et la consommation de mémoire par rapport à l'index classique de Burrows-Wheeler, dans le cadre de notre application / Amounts of data generated by Next Generation Sequencing technologies increase exponentially in recent years. Storing, processing and transferring this data become more and more challenging tasks. To be able to cope with them, data scientists should develop more and more efficient approaches and techniques.In this thesis we present efficient data structures and algorithmic methods for the problems of approximate string matching, genome assembly, read compression and taxonomy based metagenomic classification.Approximate string matching is an extensively studied problem with countless number of published papers, both theoretical and practical. In bioinformatics, read mapping problem can be regarded as approximate string matching. Here we study string matching strategies based on bidirectional indices. We define a framework, called search schemes, to work with search strategies of this type, then provide a probabilistic measure for the efficiency of search schemes, prove several combinatorial properties of efficient search schemes and provide experimental computations supporting the superiority of our strategies.Genome assembly is one of the basic problems of bioinformatics. Here we present Cascading Bloom filter data structure, that improves standard Bloom filter and can be applied to several problems like genome assembly. We provide theoretical and experimental results proving properties of Cascading Bloom filter. We also show how Cascading Bloom filter can be used for solving another important problem of read compression.Another problem studied in this thesis is metagenomic classification. We present a BWT-based approach that improves the BWT-index for quick and memory-efficient k-mer search. We mainly focus on data structures that improve speed and memory usage of classical BWT-index for our application

Les grappes de PCs constituent des architectures distribuées dont l'adoption se répand à cause de leur faible coût mais aussi de leur extensibilité en termes de noeuds. Notamment, l'augmentation du nombre des noeuds est à l'origine d'un nombre croissant de pannes par arrêt qui mettent en péril l'exécution d'applications distribuées. L'absence de solutions efficaces et portables confine leur utilisation à des applications non critiques ou sans contraintes de temps.MoLOToF est un modèle de tolérance aux pannes de niveau applicatif et fondée sur la réalisation de sauvegardes. Pour faciliter l'ajout de la tolérance aux pannes, il propose une structuration de l'application selon des squelettes tolérants aux pannes, ainsi que des collaborations entre le programmeur et le système de tolérance des pannes pour gagner en efficacité. L'application de MoLOToF à des familles d'algorithmes parallèles SPMD et Maître-Travailleur a mené aux frameworks FT-GReLoSSS et ToMaWork respectivement. Chaque framework fournit des squelettes tolérants aux pannes adaptés aux familles d'algorithmes visées et une mise en oeuvre originale. FT-GReLoSSS est implanté en C++ au-dessus de MPI alors que ToMaWork est implanté en Java au-dessus d'un système de mémoire partagée virtuelle fourni par la technologie JavaSpaces. L'évaluation des frameworks montre un surcoût en temps de développement raisonnable et des surcoûts en temps d'exécution négligeables en l'absence de tolérance aux pannes. Les expériences menées jusqu'à 256 noeuds sur une grappe de PCs bi-coeurs, démontrent une meilleure efficacité de la solution de tolérance aux pannes de FT-GReLoSSS par rapport à des solutions existantes de niveau système (LAM/MPI et DMTCP). / PC clusters are distributed architectures whose adoption spreads as a result of their low cost but also their extensibility in terms of nodes. In particular, the increase in nodes is responsable for the increase of fail-stop failures which jeopardize distributed applications. The absence of efficient and portable solutions limits their use to non critical applications or without time constraints. MoLOToF is a model for application-level fault tolerance based on checkpointing. To ease the addition of fault tolerance, it proposes to structure applications using fault-tolerant skeletons as well as collaborations between the programmer and the fault tolerance system to gain in efficiency. The application of MoLOToF on SPMD and Master-Worker families of parallel algorithms lead to FT-GReLoSSS and ToMaWork frameworks respectively. Each framework provides fault-tolerant skeletons suited to targeted families of algorithms and an original implementation. FT-GReLoSSS uses C++ on top of MPI while ToMaWork uses Java on top of virtual shared memory system provided by JavaSpaces technology. The frameworks' evaluation reveals a reasonable time development overhead and negligible runtime overheads in absence of fault tolerance. Experiments up to $256$ nodes on a dualcore PC cluster, demonstrate a better efficiency of FT-GReLoSSS' fault tolerance solution compared to existing system-level solutions (LAM/MPI and DMTCP)

Cette thèse vise à développer des stratégies permettant d'augmenter la puissance du calcul séquentiel et des systèmes distribués, elle traite en particulier, la décomposition séquentielle des opérations ainsi que des systèmes d'édition collaboratifs décentralisés. Nous introduisons, une méthode d'indexage avec précision contrôlée. Celle-ci permet la génération d'identifiants uniques utilisés dans l'indexage des communications dans les systèmes distribués, plus particulièrement dans les systèmes d'édition collaboratifs décentralisés. Ces identifiants sont des nombres réels avec un motif de précision contrôlé. Un ensemble fini d'identifiants est conservé pour permettre le calcul de cardinalités locales et globales. Cette propriété joue un rôle prépondérant dans la gestion des communications indexées. De plus, d'autres propriétés incluant la préservation de l'ordre sont observées. La méthode d'indexage a été testée et vérifiée avec succès. Ceci a permis la conception d'un système d'édition collaboratif décentralisé. Aussi, nous explorons les stratégies existantes, relatives a la décomposition séquentielle d'opérations, que nous étendons à de nouvelles stratégies. Ces stratégies mènent à une optimisation (processeur, compilateur, mémoire, code). Ces styles de décomposition portent un intérêt majeur à la communauté scientifique. Des recherches et des implémentations de plus en plus rapides résultent de la conception d'unité arithmétique. / This thesis aims at developing strategies to enhance the power of sequential computation and distributed systems, particularly, it deals with sequential break down of operations and decentralized collaborative editing systems. In this thesis, we introduced precision control indexing method that generates unique identifiers which are used for indexed communication in distributed systems, particularly, in decentralized collaborative editing systems. These identifiers are still real numbers with a specific controlled pattern of precision. Set of identifiers is kept finite that makes it possible to compute local as well as global cardinality. This property plays important role in dealing with indexed communication. Besides this, some other properties including order preservation are observed. The indexing method is tested and verified by experimentation successfully and it leads to design decentralized collaborative editing system. Dealing with sequential break down of operations, we explore limitations of the existing strategies, extended the idea by introducing new strategies. These strategies lead towards optimization (processor, compiler, memory, code). This style of decomposition attracts research communities for further investigation and practical implementation that could lead towards designing an arithmetic unit.

Dans cette thèse, nous nous intéressons à des problèmes à la croisée de deux domaines, les bases de données et les bases de connaissances. Nous considérons deux problèmes équivalents concernant les requêtes conjonctives avec négation : l'inclusion de requêtes et l'évaluation d'une requête booléenne sous l'hypothèse du monde ouvert. Nous reformulons ces problèmes sous la forme d'un problème de déduction dans un fragment de la logique du premier ordre. Puis nous raffinons des schémas d'algorithmes déjà existants et proposons de nouveaux algorithmes. Pour les étudier et les comparer expérimentalement, nous proposons un générateur aléatoire et analysons l'influence des différents paramètres sur la difficulté des instances du problème étudié. Finalement, à l'aide de cette méthodologie expérimentale, nous comparons les apports des différents raffinements et les algorithmes entre eux. / In this thesis, we consider problems at the intersection of two areas: databases and knowledge bases. We focus on two equivalent problems on conjunctive queries with negation : query containment and query answering with boolean queries while making the open-world assumption. We reformulate these problems as a problem of deduction in a first order logic fragment. Then we refine existing algorithm schemes and propose new algorithms. To study and compare them experimentally, we propose a random generator and we analyze the influence of parameters on problem instances difficulty. Finally, we analyse the contributions of the different refinements and we compare experimentally the algorithms.

Les robots mobiles à roues orientables gagnent de la mobilité en employant des roues conventionnelles entièrement orientables, comportant deux joints actifs, un pour la direction et un autre pour la conduite. En dépit d'avoir seulement un degré de mobilité (DOM) (défini ici comme degrés de liberté instantanément autorisés DOF), correspondant à la rotation autour du centre de rotation instantané (ICR), ces robots peuvent effectuer des trajectoires planaires complexes de $ 2D $. Ils sont moins chers et ont une capacité de charge plus élevée que les roues non conventionnelles (par exemple, Sweedish ou Omni-directional) et, en tant que telles, préférées aux applications industrielles. Cependant, ce type de structure de robot mobile présente des problèmes de contrôle textit {basic} difficiles de la coordination de la direction pour éviter les combats d'actionneur, en évitant les singularités cinématiques (ICR à l'axe de la direction) et les singularités de représentation (du modèle mathématique). En plus de résoudre les problèmes de contrôle textit {basic}, cette thèse attire également l'attention et présente des solutions aux problèmes de textit {niveau d'application}. Plus précisément, nous traitons deux problèmes: la première est la nécessité de reconfigurer "de manière discontinue" les articulations de direction, une fois que la discontinuité dans la trajectoire du robot se produit. Une telle situation - la discontinuité dans le mouvement du robot - est plus susceptible de se produire de nos jours, dans le domaine émergent de la collaboration homme-robot. Les robots mobiles qui fonctionnent à proximité des travailleurs humains en mouvement rapide rencontrent généralement une discontinuité dans la trajectoire calculée en ligne. Le second apparaît dans les applications nécessitant que l'angle de l'angle soit maintenu, certains objets ou fonctionnalités restent dans le champ de vision (p. Ex., Pour les tâches basées sur la vision) ou les changements de traduction. Ensuite, le point ICR est nécessaire pour déplacer de longues distances d'un extrême de l'espace de travail à l'autre, généralement en passant par le centre géométrique du robot, où la vitesse du robot est limitée. Dans ces scénarios d'application, les contrôleurs basés sur l'ICR à l'état de l'art conduiront à des comportements / résultats insatisfaisants. Dans cette thèse, nous résolvons les problèmes de niveau d'application susmentionnés; à savoir la discontinuité dans les commandes de vitesse du robot et une planification meilleure / efficace pour le contrôle du mouvement du point ICR tout en respectant les limites maximales de performance des articulations de direction et en évitant les singularités cinématiques et représentatives. Nos résultats ont été validés expérimentalement sur une base mobile industrielle. / Steerable wheeled mobile robots gain mobility by employing fully steerable conventional wheels, having two active joints, one for steering, and another for driving. Despite having only one degree of mobility (DOM) (defined here as the instantaneously accessible degrees of freedom DOF), corresponding to the rotation about the instantaneous center of rotation (ICR), such robots can perform complex $2D$ planar trajectories. They are cheaper and have higher load carrying capacity than non-conventional wheels (e.g., Sweedish or Omni-directional), and as such preferred for industrial applications. However, this type of mobile robot structure presents challenging textit{basic} control issues of steering coordination to avoid actuator fighting, avoiding kinematic (ICR at the steering joint axis) and representation (from the mathematical model) singularities. In addition to solving the textit{basic} control problems, this thesis also focuses attention and presents solutions to textit{application level} problems. Specifically we deal with two problems: the first is the necessity to "discontinuously" reconfigure the steer joints, once discontinuity in the robot trajectory occurs. Such situation - discontinuity in robot motion - is more likely to happen nowadays, in the emerging field of human-robot collaboration. Mobile robots working in the vicinity of fast moving human workers, will usually encounter discontinuity in the online computed trajectory. The second appears in applications requiring that some heading angle is to be maintained, some object or feature stays in the field of view (e.g., for vision-based tasks), or the translation verse changes. Then, the ICR point is required to move long distances from one extreme of the workspace to the other, usually passing by the robot geometric center, where the feasible robot velocity is limited. In these application scenarios, the state-of-art ICR based controllers will lead to unsatisfactory behavior/results. In this thesis, we solve the aforementioned application level problems; namely discontinuity in robot velocity commands, and better/efficient planning for ICR point motion control while respecting the maximum steer joint performance limits, and avoiding kinematic and representational singularities. Our findings has been validated experimentally on an industrial mobile base.

À l'origine de cette thèse, nous nous sommes intéressés à l'algorithme de tri TimSort qui est apparu en 2002, alors que la littérature sur le problème du tri était déjà bien dense. Bien qu'il soit utilisé dans de nombreux langages de programmation, les performances de cet algorithme n'avaient jamais été formellement analysées avant nos travaux. L'étude fine de TimSort nous a conduits à enrichir nos modèles théoriques, en y incorporant des caractéristiques modernes de l'architecture des ordinateurs. Nous avons, en particulier, étudié le mécanisme de prédiction de branchement. Grâce à cette analyse théorique, nous avons pu proposer des modifications de certains algorithmes élémentaires (comme l'exponentiation rapide ou la dichotomie) qui utilisent ce principe à leur avantage, améliorant significativement leurs performances lorsqu'ils sont exécutés sur des machines récentes. Enfin, même s'il est courant dans le cadre de l'analyse en moyenne de considérer que les entrées sont uniformément distribuées, cela ne semble pas toujours refléter les distributions auxquelles nous sommes confrontés dans la réalité. Ainsi, une des raisons du choix d'implanter TimSort dans des bibliothèques standard de Java et Python est probablement sa capacité à s'adapter à des entrées partiellement triées. Nous proposons, pour conclure cette thèse, un modèle mathématique de distribution non-uniforme sur les permutations qui favorise l'apparition d'entrées partiellement triées, et nous en donnons une analyse probabiliste détaillée / At first, we were interested in TimSort, a sorting algorithm which was designed in 2002, at a time where it was hard to imagine new results on sorting. Although it is used in many programming languages, the efficiency of this algorithm has not been studied formally before our work. The fine-grain study of TimSort leads us to take into account, in our theoretical models, some modern features of computer architecture. In particular, we propose a study of the mechanisms of branch prediction. This theoretical analysis allows us to design variants of some elementary algorithms (like binary search or exponentiation by squaring) that rely on this feature to achieve better performance on recent computers. Even if uniform distributions are usually considered for the average case analysis of algorithms, it may not be the best framework for studying sorting algorithms. The choice of using TimSort in many programming languages as Java and Python is probably driven by its efficiency on almost-sorted input. To conclude this dissertation, we propose a mathematical model of non-uniform distribution on permutations, for which permutations that are almost sorted are more likely, and provide a detailed probabilistic analysis

Dans une première partie théorique, nous nous penchons sur une analyse rigoureuse des performances de l'algorithme Sequential Monte Carlo (SMC) conduisant à des résultats de type bornes L^p et inégalités de concentration. Nous abordons notamment le cas particulier des SMC associés à des schémas de température, et analysons sur ce sujet un processus à schéma adaptatif.Dans une seconde partie appliquée, nous illustrons son utilisation par la résolution de problèmes inverses concrets en électromagnétisme. Le plus important d'entre eux consiste à estimer les propriétés radioélectriques de matériaux recouvrant un objet de géométrie connue, et cela à partir de mesures de champs rétrodiffusés. Nous montrons comment l'algorithme SMC, couplé à des calculs analytiques, permet une inversion bayésienne, et fournit des estimées robustes enrichies d'estimations des incertitudes. / Sequential and Quantum Monte Carlo methods, as well as genetic type search algorithms, can be interpreted as a mean field and interacting particle approximation of Feynman-Kac models in distribution spaces. The performance of these population Monte Carlo algorithms is strongly related to the stability properties of nonlinear Feynman-Kac semigroups. In a first theoretical part, we analyze these models in terms of Dobrushin ergodic coefficients of the reference Markov transitions and the oscillations of the potential functions. Sufficient conditions for uniform concentration inequalities w.r.t. time are expressed explicitly in terms of these two quantities. We provide an original perturbation analysis that applies to annealed and adaptive FK models, yielding what seems to be the first results of this kind for these type of models. Special attention is devoted to the particular case of Boltzmann-Gibbs measures' sampling. In this context, we design an explicit way of tuning the number of Markov Chain Monte Carlo iterations with temperature schedule. We also propose and analyze an alternative interacting particle method based on an adaptive strategy to define the temperature increments. In a second, applied part, we illustrate the use of these SMC algorithms in the field of inverse problems. Mainly, the following electromagnetism (EM) inverse problem is addressed. It consists in estimating local radioelectric properties of materials recovering an object from global EM scattering measurements, at various incidences and wave frequencies. This large scale ill-posed inverse problem is explored by an intensive exploitation of an efficient 2D Maxwell solver, distributed on high performance computing machines. Applied to a large training data set, a statistical analysis reduces the problem to a simpler probabilistic metamodel, on which Bayesian inference can be performed. Considering the radioelectric properties as a hidden dynamic stochastic process, that evolves in function of the frequency, it is shown how the Sequential Monte Carlo methods can take benefit of the structure and provide local EM property estimates.