Cette thèse étudie le problème de la localisation et cartographie simultanées des robots sous-marins, et ses méthodes de résolution utilisant le calcul par intervalles. Le principe du SLAM (Simultaneous Localization And Mapping, ou cartographie et localisation simultanées) est le suivant: un robot sous-marin connait en général sa position initiale (lorsqu'il est à la surface grâce à un GPS), son modèle de déplacement (très approximativement) et possède quelques capteurs l'aidant à estimer sa position (capteur de pression pour mesurer sa profondeur, loch Doppler pour mesurer sa vitesse et sa distance au fond, centrale inertielle pour mesurer son orientation) et voir ce qui l'entoure (sonar). Pourtant, malgré tous ces capteurs, plus il avance, plus ses erreurs d'estimation de position s'accumulent: le robot se perd. En passant et repassant devant plusieurs objets (ou éléments remarquables quelconques de son environnement), il va pouvoir évaluer leur position (plus ou moins précisément) une première fois à partir de la sienne (cartographie grâce à sa localisation), puis recalculer sa trajectoire en les prenant comme repère les fois suivantes quand il est perdu (localisation grâce à sa cartographie). Les mesures de capteurs ou variables utilisées pour décrire les robots étant souvent entachées d'erreurs, elles peuvent être représentées de différentes façons: distributions probabilistes, nuages de points, ensembles continus... En général, les données constructeur des capteurs ou actionneurs du robot nous indiquent des bornes (liées à la précision...). On peut donc représenter ces valeurs sous forme d'intervalles. Les méthodes ensemblistes telles que l'analyse par intervalles permettent d'obtenir des résultats à partir d'équations sur des intervalles. L'avantage de ces méthodes est qu'on est sûr de ne perdre aucune solution (compte tenu des hypothèses faites), contrairement à celles utilisant l'approche probabiliste, où on n'obtient parfois que les solutions les plus probables. Dans cette thèse, l'utilisation du calcul par intervalles dans le cadre du SLAM appliqué aux robots sous-marins et une comparaison entre plusieurs méthodes existantes seront étudiées. De plus, une nouvelle méthode permettant de mieux gérer le problème des données fugaces (données seulement significatives à des instants bien précis et inconnus), rencontré notamment avec des données provenant de sonars, sera proposée. Les applications de ces travaux concernent par exemple le développement de robots sous-marins autonomes (souvent appelés AUVs pour Autonomous Underwater Vehicles ou UUVs pour Unmanned Underwater Vehicles). En effet, contrairement aux robots téléguidés par des humains, ceux-ci doivent eux-mêmes être capables de se repérer dans leur environnement pour effectuer leur travail. Ces robots peuvent avoir des missions variées: relevé de données hydrographiques, localisation d'épaves (bateau, avion...) ou objets dangereux (mines...), surveillance (détection de pollution, vérification de l'état de pipelines...)... Actuellement, ces tâches sont principalement réalisées par des humains, directement avec des plongeurs, ou indirectement avec des sous-marins téléopérés pour les travaux les plus dangereux ou difficiles d'accès.

Cette thèse traite deux types de problèmes algorithmiques : des problèmes de triangularisation de matrices booléennes par permutation des lignes et des colonnes et des problèmes de découverte de structures secondaires d'ARN. Nous étudions des problèmes de triangularisation de matrices booléennes par permutation des lignes et des colonnes. Ce problème apparaît, par exemple, lorsque l'on souhaite calculer "en place" un système d'équations. Une façon naturelle d'aborder ce problème est de se placer dans le cadre général de la théorie des graphes et des graphes bipartis en particulier. Nous présentons de nombreux résultats de complexité - essentiellement de NP-complétude - liés à ce problème et introduisons quelques extensions dont nous précisons toujours la complexité. Certaines familles d'ARN sont très précisément définies par des motifs de séquence, et des contraintes structurelles secondaires et tertiaires. La plupart des outils ne sont pas adaptés puisqu'ils n'intègrent pas toutes les connaissances sur la molécule lors de l'exploration des banques de séquences. D'où l'intérêt d'algorithmes de recherche assurant une recherche en séquence et structure par le biais d'un descripteur défini par l'utilisateur intégrant l'ensemble des connaissances caractérisant l'ARN à détecter. Une nouvelle façon d'aborder ce problème consiste en l'étude de problèmes algorithmiques sur les graphes d'intersection d'un ensemble de 2-intervalles. Cette notion de 2-intervalles se trouve dans la lignée des études actuelles en matière d'algorithmique de graphes où l'on étudie de plus en plus les structures des graphes issues de modèles géométriques. Nous présentons plusieurs résultats de complexité et montrons en particulier que la recherche de motifs dans un ensemble de 2-intervalles est un problème NP-complet. Nous nous intéressons, plus particulièrement, à appliquer ces travaux pour la prédiction de motifs biologiques structurés. Plus spécifiquement, nous avons mis au point l'algorithme ORANGE pour la prédiction des introns auto-catalytiques de groupe 1 dans de grandes séquences génomiques. Cet algorithme est une amélioration de l'algorithme CITRON mis au point par F. Lisacek et F. Michel du point de vue de la rapidité d'exécution. De plus, une mise-en-œuvre de l'algorithme ORANGE est accessible en ligne sur Internet.

La modélisation des systèmes dynamiques requiert la prise en compte d'incertitudes liées à l'existence inévitable de bruits (bruits de mesure, bruits sur la dynamique), à la méconnaissance de certains phénomènes perturbateurs mais également aux incertitudes sur la valeur des paramètres (spécification de tolérances, phénomène de vieillissement). Alors que certaines de ces incertitudes se prêtent bien à une modélisation de type statistique comme par exemple les bruits de mesure, d'autres se caractérisent mieux par des bornes, sans autre attribut. Dans ce travail de thèse, motivés par les observations ci-dessus, nous traitons le problème de l'intégration d'incertitudes statistiques et à erreurs bornées pour les systèmes linéaires à temps discret. Partant du filtre de Kalman Intervalle (noté IKF) développé dans [Chen 1997], nous proposons des améliorations significatives basées sur des techniques récentes de propagation de contraintes et d'inversion ensembliste qui, contrairement aux mécanismes mis en jeu par l'IKF, permettent d'obtenir un résultat garanti tout en contrôlant le pessimisme de l'analyse par intervalles. Cet algorithme est noté iIKF. Le filtre iIKF a la même structure récursive que le filtre de Kalman classique et délivre un encadrement de tous les estimés optimaux et des matrices de covariance possibles. L'algorithme IKF précédent évite quant à lui le problème de l'inversion des matrices intervalles, ce qui lui vaut de perdre des solutions possibles. Pour l'iIKF, nous proposons une méthode originale garantie pour l'inversion des matrices intervalle qui couple l'algorithme SIVIA (Set Inversion via Interval Analysis) et un ensemble de problèmes de propagation de contraintes. Par ailleurs, plusieurs mécanismes basés sur la propagation de contraintes sont également mis en oeuvre pour limiter l'effet de surestimation due à la propagation d'intervalles dans la structure récursive du filtre. Un algorithme de détection de défauts basé sur iIKF est proposé en mettant en oeuvre une stratégie de boucle semi-fermée qui permet de ne pas réalimenter le filtre avec des mesures corrompues par le défaut dès que celui-ci est détecté. A travers différents exemples, les avantages du filtre iIKF sont exposés et l'efficacité de l'algorithme de détection de défauts est démontré.

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

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

Cette étude se classe dans le domaine de la psychologie de la perception du temps et cherche à documenter comment celle-ci fonctionne chez les autistes. En particulier, elle s’intéresse à l’influence du contexte global sur la perception d’intervalles locaux. Dans cet objectif, un groupe de participants autistes (n = 11) et un groupe contrôle (n = 11) ont effectué une tâche de comparaison d’intervalles allant de 200 à 800 ms. Chaque comparaison d’intervalles sonores est précédée d’une séquence au rythme régulier, l’ensemble étant intégré dans une session aux rythmes multiples. L’expérience comprend quatre sessions dont les propriétés distributionnelles diffèrent. Cette étude mesure l’influence de la modification du rythme moyen d’une session expérimentale (un son à chaque 400 vs 600 ms) ainsi que de son hétérogénéité (différence de 200 vs 400 ms entre le plus court et le plus long intervalle) sur l’erreur constante (EC), l’EC exprimée en valeur absolue et la fraction de Weber. Conformément à ce qu’ont obtenu Jones et McAuley (2005) auprès de non-autistes, les résultats indiquent que chez les deux groupes, la perception temporelle est sujette aux effets du contexte global. De plus, les résultats confirment que la plus grande autonomie de la perception par rapport aux fonctions de haut niveau, caractéristique centrale du fonctionnement cognitif des autistes, influence leur perception du temps. En diminuant l’influence du contexte, cette particularité favorise tant la perception que la discrimination. Finalement, l’analyse de tous les intervalles compris dans l’expérience indique, en moyenne, de moins grands écarts d’estimation ainsi qu’une meilleure discrimination temporelle chez les autistes. Pris dans leur ensemble, les résultats appuient le modèle du surfonctionnement perceptif de Mottron et al. (2006), qui soutient que chez les autistes, une plus grande implication des aires cérébrales dédiées à la perception est liée à un traitement de l’information plus efficace. / The current study belongs to the field of time perception psychology and attempts to better explain it’s functioning in autistic people. In particular, this work investigates global context effects on local time judgments. Therefore, a group of autistic subjects (n = 11) and a control group (n = 11) performed an auditive interval comparison task. The intervals comprised in the study were ranged between 200 and 800 ms. Every interval comparison followed a regular rhythmic sequence delaminated by brief tones, and the whole was integrated into a multirhythmic session. There were four sessions in the experiment, and each of them had a unique set of distributional properties. This study investigated the impact of modifying a session’s average pace (one sound at every 400 vs 600 ms) and heterogeneity (200 vs 400 ms difference between the shortest and the largest interval) on constant error (CE), CE absolute value and Weber ratio. In addition to confirm what Jones and McAuley (2005) obtained in their original experience with non-autistic subjects, the results indicate that among the two groups, time perception can be influenced by global context. Next, they confirm that time perception and discrimination sensitivity of autistic people are more autonomous toward high level functions, which is a central characteristic of autistics cognitive functioning. By reducing context effect on perception and discrimination, this characteristic helps perception and discrimination. Then, for the average of all durations comprised in this study, time perception and discrimination of autistic people were better than those of non-autistics. Taken into a whole, results support the enhanced perceptual functioning model (EPF) of Mottron and al. (2006), which sustains that among autistics, a greater implication of perceptual brain areas is related to a more effective information processing

La théorie des systèmes dynamiques étudie les phénomènes qui évoluent au cours du temps. Plus précisément, un système dynamique est donné par : un espace de phase dont les points correspondent à des états possibles du système étudié et une loi d'évolution décrivant l'infinitésimal (pour le cas continu) pas à pas (pour le cas discret) les changements des états du système. Le but de la théorie est de comprendre l'évolution dans le long terme. Dans ce travail, nous présentons une nouvelle méthode pour la résolution des systèmes linéaires avec preuve assistée par ordinateur dans le cadre de modèles linéaires réalistes. Après une introduction de quelques propriétés de la théorie des équations différentielles ordinaires, on introduit une méthode de calcul rigoureux pour trouver la solution périodique de la conjecture de Galaktionov-Svirshchevskii. On reformule le problème comme un problème à valeur initiale, puis on calcule la solution périodique dans le domaine positif et on déduit l'autre solution par symétrie. Notre résultat énonce une partie de la conjecture 3:2 dans le livre de Victor A. Galaktionov & Sergey R. Svirshchevskii : Exact Solutions and Invariant Subspaces of Nonlinear Partial Differential Equations in Mechanics and Physics, [Chapman & Hall/CRC, applied mathematics and nonlinear science series, (2007)]. Mots clés. Conjecture de Galaktionov-Svirshchevskii, Analyse d'intervalle, Théorème de contraction de Banach, Polynômes de rayons. / The theory of dynamical systems studies phenomena which are evolving in time. More precisely, a dynamical system is given by the following data: a phase space whose points correspond to the possible states of the system under consideration and an evolution law describing the infinitesimal (for continuous time) or one-step (for discrete time) change in the state of the system. The goal of the theory is to understand the long term evolution of the system. In this work, we introduce a new method for solving piecewise linear systems with computer assisted proofs in the context of realistic linear models. After introducing some properties of the theory of ordinary differential equations, we provide a rigorous computational method for finding the periodic solution of Galaktionov-Svirshchevskii's conjecture. We reformulate the problem as an initial value problem, compute periodic solution in the positive domain and deduce the other solution by symmetry. Our result settles one part of the Conjecture 3:2 by Victor A. Galaktionov & Sergey R. Svirshchevskii: Exact Solutions and Invariant Subspaces of Nonlinear Partial Differential Equations in Mechanics and Physics, [Chapman & Hall/CRC, applied mathematics and nonlinear science series, (2007)]. Key words. Galaktionov-Svirshchevskii's conjecture, Interval analysis, Contraction mapping theorem, Radii polynomials.

Dans ces travaux, nous nous intéressons à l'estimation et l'étude des intervalles cardiaques. L'objectif principal de cette thèse est donc de développer de nouveaux outils d'estimation de ces intervalles. Plus précisément, nous souhaitons concevoir de nouvelles techniques de traitement du signal pour extraire des ECG les intervalles P-R, qui sont très peu étudiés dans la littérature de part la difficulté d'extraire les ondes P, et dans un second temps les intervalles Q-T. Inspirés de la méthode itérative de Woody (1967) basée sur une technique de corrélation de chaque observation avec une moyenne des signaux réalignés, nous proposons tout d'abord un perfectionnement de cette méthode. En effet, à partir du même modèle d'observations, nous développons le critère de maximum de vraisemblance et nous obtenons une amélioration de la méthode de Woody au sens de l'optimalité. Le modèle d'observations de cette méthode est ensuite enrichi par une onde potentiellement parasite additionnée au bruit, et une généralisation de la méthode de Woody est proposée. En prenant l'exemple de l'onde T de l'ECG qui se superpose à l'onde P du battement suivant lorsque la fréquence cardiaque est élevée, différents modèles de l'onde T sont proposés. Grâce à ces deux méthodes proposées, les objectifs d'estimer et d'analyser les intervalles cardiaques, tels que les intervalles R-R, Q-T et P-R, sont atteints. Plus précisément, grâce à la généralisation de Woody, l'estimation des intervalles P-R à l'exercice est réalisable. L'application de ces méthodes aux enregistrements réels de différents types d'ECG (repos, exercice, fibrillation auriculaire,...), nous a révélé de nouveaux résultats concernant l'évolution des intervalles cardiaques, comme par exemple : l'existence d'un phénomène d'hystérésis en sens horaire dans la relation P-R/R-R, et une caractérisation possible des sujets en fonction de leur niveau d'entraînement à l'aide de la pente des intervalles P-R au début de la phase de récupération. Une modélisation de la réponse du Q-T à un changement de la période cardiaque a également été proposée s'inspirant du comportement électrique cellulaire.

L'émergence des expériences dites à haut débit permet l'acquisition rapide de données concernant un système biologique. Les biologistes disposent ainsi, aujourd'hui, d'un nombre important de données de natures hétérogènes qu'ils cherchent à structurer et analyser. Les méthodes dites intégratives proposent de répondre à cette demande, mais la création d'une méthode générale et satisfaisant les requêtes précises des biologistes constitue une tâche ardue. Ce mémoire s'inscrit dans cette problématique. Nous y abordons diverses méthodes d'intégration des aspects omiques (métaboliques, génomiques, transcriptomiques...) d'un système bactérien et nous proposons la nôtre, nommée SIPPER, qui est une méthode générique et flexible. SIPPER permet de retrouver de l'information biologique cohérente entre les différents aspects étudiés grâce à la construction d'un modèle intégratif et l'utilisation d'une distance reposant sur des propriétés ou hypothèses biologiques choisies. Nous avons appliqué SIPPER deux fois sur les données métaboliques et génomiques d'E. coli. La première application teste l'hypothèse "les chaînes de réactions successives du réseau métabolique sont catalysées à l'aide d'enzymes produites par des gènes proches sur le génome", et la seconde teste l'hypothèse "les chaînes de réactions successives sont catalysées par des gènes dont l'expression est similaire". Nous avons découvert, par ces expériences, des mesures caractérisant certaines entités biologiques comme la densité génomique qui permet l'identification d'opérons métaboliques. L'apport de l'intégration de données supplémentaires aux approches n'utilisant traditionnellement qu'un seul type d'information a également été illustré au travers de la génomique comparative. Nous avons ainsi élaboré M&W-IISCS_M, une méthode qui calcule des intervalles communs maximaux ayant un fort intérêt omique.

L’interdiction des quintes parallèles fait figure de loi immuable dans les études d’harmonie et de contrepoint, souvent imputée au fait qu’elles créent de l’ambiguïté tonale. Cependant, les cas de transgression de cette règle dans la musique de piano en France sont nombreux entre 1880 et 1940, période de foisonnement de styles et d’évolution tonale. Ce mémoire s’intéresse à l’utilisation de cet élément dans la musique pour piano à cette époque. Après une brève définition et un bref historique de la problématique, il expose les différents aspects de la règle telle qu’elle est énoncée dans plusieurs traités et dresse un portrait de la musique de piano et de l’évolution de la tonalité en France entre 1880 et 1940. Il propose ensuite un classement des types de quintes parallèles, puis l’applique au répertoire étudié. En conclusion, le mémoire aborde le rôle et l’impact des quintes parallèles sur le langage pianistique. / The prohibition of parallel fifths seems to be an unassailable law in the study of harmony and counterpoint, often attributed to the fact that they create tonal ambiguity. However, there are many instances of this rule being transgressed in piano music in France between 1880 and 1940, a period marked by the proliferation of styles and tonal evolution. This dissertation focusses on the use of this element in the piano music at the time. Following a brief status quaestionis and historical survey, it presents the different aspects of the rule as stated in several treatises and draws a picture of piano music and the evolution of tonality in France between 1880 and 1940. It then proposes a typology of parallel fifths and applies it to the repertoire in question. In conclusion, the role of parallel fifths and their impact on the pianistic language are discussed.