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.

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.

Contrairement aux robots conventionnels, les robots continuums ne possèdent ni de liaisons discrètes, ni de corps rigides. Leur courbure est continue, similaire à celle des trompes ou des tentacules animales. Le développement de ce type de robots pour les applications médicales soulève plusieurs problèmes : optimisation de la conception, modélisation cinématique, choix des capteurs et commande en temps réel. Les techniques actuelles pour la modélisation des robots continuums ne tiennent pas compte les incertitudes inhérentes au système. La prise en compte de ces incertitudes est d'une importance cruciale pour la certification de tels robots utilisés pour les gestes chirurgicaux. Dans cette thèse, nous considérons un micro robot continuum à 3 actionneurs. Ce robot a été développé au laboratoire LISSI pour le traitement des anévrismes de l'aorte abdominale par chirurgie mini-invasive. Dans ce type de chirurgie, il est important de disposer d'un modèle cinématique garanti du robot continuum prenant en compte différents types d'incertitudes. Pour traiter ce problème, nous utilisons les techniques d'analyse par intervalles. Ces techniques permettent de résoudre des problèmes d'optimisation globale sous contraintes tout en prenant en compte des incertitudes aussi bien aléatoires que systématiques. La contribution de cette thèse porte sur la proposition d'un modèle cinématique d'un robot continuum prenant en compte des incertitudes liées à différents facteurs comme les erreurs d'arrondis, les erreurs paramétriques et les erreurs dues aux hypothèses de modélisation. Tout d'abord, nous développons les modèles géométriques direct et inverse du robot continuum sous forme de solutions de formes fermées. Ces solutions sont utilisées pour caractériser les différentes propriétés du robot comme la manipulabilité. Pour calculer la cinématique inverse garantie et optimale, nous appliquons une version améliorée de l'algorithme par séparation et évaluation (Branch and Bound). En considérant l'orientation du robot, la cinématique inverse est ramenée à la formulation et à la résolution par intervalles d'un problème d'optimisation sous contraintes. Les approches proposées sont validées par des simulations. Les résultats de cette thèse constituent un cadre général pour la modélisation garantie de la classe des robots continuums dont la forme est décrite par des actionneurs en flexion continue / Unlike conventional robots, continuum robots do not contain any rigid link or any rotational joint but present a continuous bending in the structure through smooth motion. Development of this class of robot for their medical application presents a common set of problems : optimization of design, kinematic modeling, sensing choice, and their control in real time. Existing techniques for the modeling of continuum robots do not take system uncertainties into account. A proper handling of these uncertainties becomes of crucial importance for the certification of such robots used as medical devices. For our research, we consider a continuum robot that has been developed for the treatment of aortic aneurysm by Minimal Invasive Surgery (MIS), in LISSI Lab. In the context of MIS, it is very important to develop a guaranteed kinematic model of robot taking into account the different types of un-certainties. To handle this problem, we use the techniques of interval analysis. These techniques are capable of performing the global optimization and solving CSPs while taking into account the different uncertainties ; no matter, whether these uncertainties are random or systematic. Contribution of this thesis is proposal of a continuum robot's kinematic model that can take system uncertainties due to different factors such as rounding errors, parametric errors, and errors due to modeling assumptions. Initially, we develop the forward and inverse kinematics of the continuum robot in closed-form formulas. These derived formulas are used for the characterization of different properties of the robot such as manipulability. To find optimized guaranteed kinematics, we retained and applied an enhanced version of branch and bound algorithm. The inverse kinematics was formulated and resolved as a constrained optimization problem for robot's orientation. The proposed approaches are validated through simulations. The results of this thesis give rise to a general framework that is valid to handle the system uncertainties for the entire class of continuum robot that are shaped by continuously bending actuators

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 pa ! r 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 œuvre 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 œuvre 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é. / In this thesis, a new approach to estimation problems under the presence of bounded uncertain parameters and statistical noise has been presented. The objective is to use the uncertainty model which appears as the most appropriate for every kind of uncertainty. This leads to the need to consider uncertain stochastic systems and to study how the two types of uncertainty combine : statistical noise is modeled as the centered gaussian variable and the unknown but bounded parameters are approximated by intervals. This results in an estimation problem that demands the development of mixed filters and a set-theoretic strategy. The attention is drawn on set inversion problems and constraint satisfaction problems. The former is the foundation of a method for solving interval equations, and the latter can significantly improve the speed of interval based arithmetic and algorithms. An important contribution of this work consists in proposing an interval matrix inversion method which couples the algorithm SIVIA with the construction of a list of constraint propagation problems. The system model is formalized as an uncertain stochastic system. Starting with the interval Kalman filtering algorithm proposed in [Chen 1997] and that we name the IKF, an improved interval Kalman filtering algorithm (iIKF) is proposed. This algorithm is based on interval conditional expectation for interval linear systems. The iIKF has the same structure as the conventional Kalman filter while achieving guaranteed statistical optimality. The recursive computational scheme is developed in the set-membership context. Our improvements achieve guaranteed interval inversion whereas the original version IKF [Chen 1997] uses an instance (the upper bound) of the interval matrix to avoid the possible singularity problems. This point of view leads to a sub-optimal solution that does not preserve guaranteed results, some solutions being lost. On the contrary, in the presence of unknown-but-bounded parameters and measurement statistical errors, our estimation approach in the form of the iIKF provides guaranteed estimates, while maintaining a computational burden comparable to that of classic statistical approaches. Several constraint based techniques have also been implemented to limit the overestimation effect due to interval propagation within the interval Kalman filter recursive structure. The results have shown that the iIKF out puts bounded estimates that enclose all the solutions consistent with bounded errors and achieves good overestimation control. iIKF is used to propose a fault detection algorithm which makes use of a Semi-Closed Loop strategy which does not correct the state estimate with the measure as soon as a fault is detected. Two methods for generating fault indicators are proposed : they use the a priori state estimate and a threshold based on the a posteriori and a priori covariance matrix, respectively, and check the consistency against the measured output. Through different examples, the advantages of the iIKF with respect to previous versions are exhibited and the efficiency of the iIKF based Semi-Closed Loop fault detection algorithm is clearly demonstrated.