Prédiction structurale de biomolécules à l'aide d'une construction d'automates cellulaires simulant la dynamique moléculaire

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Complexité raffinée du problème d'intersection d'automates

Le problème d'intersection d'automates consiste à vérifier si plusieurs automates finis déterministes acceptent un mot en commun. Celui-ci est connu PSPACE-complet (resp. NL-complet) lorsque le nombre d'automates n'est pas borné (resp. borné par une constante). Dans ce mémoire, nous étudions la complexité du problème d'intersection d'automates pour plusieurs types de langages et d'automates tels les langages unaires, les automates à groupe (abélien), les langages commutatifs et les langages finis. Nous considérons plus particulièrement le cas où chacun des automates possède au plus un ou deux états finaux. Ces restrictions permettent d'établir des liens avec certains problèmes algébriques et d'obtenir une classification intéressante de problèmes d'intersection d'automates à l'intérieur de la classe P. Nous terminons notre étude en considérant brièvement le cas où le nombre d'automates est fixé.

Automates à contraintes semilinéaires = Automata with a semilinear constraint

Cette thèse présente une étude dans divers domaines de l'informatique théorique de modèles de calculs combinant automates finis et contraintes arithmétiques. Nous nous intéressons aux questions de décidabilité, d'expressivité et de clôture, tout en ouvrant l'étude à la complexité, la logique, l'algèbre et aux applications. Cette étude est présentée au travers de quatre articles de recherche. Le premier article, Affine Parikh Automata, poursuit l'étude de Klaedtke et Ruess des automates de Parikh et en définit des généralisations et restrictions. L'automate de Parikh est un point de départ de cette thèse; nous montrons que ce modèle de calcul est équivalent à l'automate contraint que nous définissons comme un automate qui n'accepte un mot que si le nombre de fois que chaque transition est empruntée répond à une contrainte arithmétique. Ce modèle est naturellement étendu à l'automate de Parikh affine qui effectue une opération affine sur un ensemble de registres lors du franchissement d'une transition. Nous étudions aussi l'automate de Parikh sur lettres: un automate qui n'accepte un mot que si le nombre de fois que chaque lettre y apparaît répond à une contrainte arithmétique. Le deuxième article, Bounded Parikh Automata, étudie les langages bornés des automates de Parikh. Un langage est borné s'il existe des mots w_1, w_2, ..., w_k tels que chaque mot du langage peut s'écrire w_1...w_1w_2...w_2...w_k...w_k. Ces langages sont importants dans des domaines applicatifs et présentent usuellement de bonnes propriétés théoriques. Nous montrons que dans le contexte des langages bornés, le déterminisme n'influence pas l'expressivité des automates de Parikh. Le troisième article, Unambiguous Constrained Automata, introduit les automates contraints non ambigus, c'est-à-dire pour lesquels il n'existe qu'un chemin acceptant par mot reconnu par l'automate. Nous montrons qu'il s'agit d'un modèle combinant une meilleure expressivité et de meilleures propriétés de clôture que l'automate contraint déterministe. Le problème de déterminer si le langage d'un automate contraint non ambigu est régulier est montré décidable. Le quatrième article, Algebra and Complexity Meet Contrained Automata, présente une étude des représentations algébriques qu'admettent les automates contraints et les automates de Parikh affines. Nous déduisons de ces caractérisations des résultats d'expressivité et de complexité. Nous montrons aussi que certaines hypothèses classiques en complexité computationelle sont reliées à des résultats de séparation et de non clôture dans les automates de Parikh affines. La thèse est conclue par une ouverture à un possible approfondissement, au travers d'un certain nombre de problèmes ouverts.

Diagnostic des systèmes temps réel modélisés par des automates à entrées sorties temporisées

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

Una aproximación evolucionista para la generación automática de sentencias SQL a partir de ejemplos

En la actualidad, el uso de las tecnologías ha sido primordial para el avance de las sociedades, estas han permitido que personas sin conocimientos informáticos o usuarios llamados “no expertos” se interesen en su uso, razón por la cual los investigadores científicos se han visto en la necesidad de producir estudios que permitan la adaptación de sistemas, a la problemática existente dentro del ámbito informático. Una necesidad recurrente de todo usuario de un sistema es la gestión de la información, la cual se puede administrar por medio de una base de datos y lenguaje específico, como lo es el SQL (Structured Query Language), pero esto obliga al usuario sin conocimientos a acudir a un especialista para su diseño y construcción, lo cual se ve reflejado en costos y métodos complejos, entonces se plantea una pregunta ¿qué hacer cuando los proyectos son pequeñas y los recursos y procesos son limitados? Teniendo como base la investigación realizada por la universidad de Washington[39], donde sintetizan sentencias SQL a partir de ejemplos de entrada y salida, se pretende con esta memoria automatizar el proceso y aplicar una técnica diferente de aprendizaje, para lo cual utiliza una aproximación evolucionista, donde la aplicación de un algoritmo genético adaptado origina sentencias SQL válidas que responden a las condiciones establecidas por los ejemplos de entrada y salida dados por el usuario. Se obtuvo como resultado de la aproximación, una herramienta denominada EvoSQL que fue validada en este estudio. Sobre los 28 ejercicios empleados por la investigación [39], 23 de los cuales se obtuvieron resultados perfectos y 5 ejercicios sin éxito, esto representa un 82.1% de efectividad. Esta efectividad es superior en un 10.7% al establecido por la herramienta desarrollada en [39] SQLSynthesizer y 75% más alto que la herramienta siguiente más próxima Query by Output QBO[31]. El promedio obtenido en la ejecución de cada ejercicio fue de 3 minutos y 11 segundos, este tiempo es superior al establecido por SQLSynthesizer; sin embargo, en la medida un algoritmo genético supone la existencia de fases que amplían los rangos de tiempos, por lo cual el tiempo obtenido es aceptable con relación a las aplicaciones de este tipo. En conclusión y según lo anteriormente expuesto, se obtuvo una herramienta automática con una aproximación evolucionista, con buenos resultados y un proceso simple para el usuario “no experto”.

Contraintes vécues, idéal normatif et actions déployées en vue de transformer l’exercice de la profession infirmière en centre hospitalier : une étude exploratoire auprès d’infirmières québécoises politiquement engagées

Les changements socioéconomiques des dernières décennies ont profondément transformé le rapport qu’entretient le Québec avec ses professionnels de la santé. En ouvrant le champ à l’accumulation privée du capital dans les années 1990, se met en place au sein de la fonction publique une philosophie politique issue du monde des affaires. Dès lors, le paradigme de la gouvernance investit les hôpitaux, où exerce 65 % de l’effectif infirmier québécois. Des chercheurs ont investigué les contraintes et torts subis par les infirmières consécutivement à la restructuration du système de santé, cependant, peu d’entre eux ont tenu compte des rapports de force et des structures de pouvoir dans lesquels s’enracine le vécu des infirmières. La présente étude a pour but d’explorer les expériences vécues d’infirmières soignantes politiquement engagées qui exercent en centre hospitalier (CH), de rendre compte de l’ordre social existant au sein de cette institution, de décrire la façon dont elles aimeraient idéalement exercer et de répertorier les idées qu’elles ont et les actions qu’elles mettent en place individuellement ou collectivement de façon à favoriser la transformation de l’ordre social et de l’exercice infirmier en CH. Épistémologiquement, notre étude qualitative s’inscrit dans cette idée que la réalité est complexe, mouvante et dépendante de la perception des personnes, proposant une orientation compréhensive et contextualisée de l’action humaine et du politique; c’est ainsi que le point de vue politique des infirmières participantes est pris en compte. L’articulation des expériences vécues, de l’idéal normatif et de l’action politique des participantes est explorée suivant une perspective postmoderniste, praxéologique et dialectique issue de la théorie critique qui réfléchit non seulement sur ce qui est, mais également sur ce qui est souhaitable; une réflexion qui sous certaines conditions s’ouvre sur l’action transformatrice. Les notions de pouvoir, de rapport de force, de résistance et d’émancipation influencent notre analyse. Au terme de cette étude, les résultats indiquent la présence d’une déprofessionnalisation graduelle en faveur d’une technicisation du soin infirmier et d’une dérive autoritaire grandissante au sein des CH s’arrimant au registre sémantique de l’économie de marché à partir des notions d’efficacité, de performance et d’optimisation. Les infirmières soignantes perçues comme des « automates performants » se voient exclues des processus décisionnels, ce qui les prive de leurs libertés de s’exprimer et de se faire critiques devant ce qui a été convenu par ceux qui occupent les hautes hiérarchies du pouvoir hospitalier et qui déterminent à leur place la façon dont s’articule l’exercice infirmier. Le pouvoir disciplinaire hospitalier, par l’entremise de technologies politiques comme la surveillance continue, les représailles et la peur, la technicisation du soin et le temps supplémentaire obligatoire, concourt à la subjectivation des infirmières soignantes, en minimisant l’importance de leur jugement clinique, en affaiblissant la solidarité collective et en mettant au pas l’organisation syndicale, ce qui détournent ces infirmières de la revendication de leurs droits et idéaux d’émancipation les ramenant à une position subalterne. Nos résultats indiquent que les actions politiques que les participantes souhaitent déployer au sein des CH visent l’humanisation des soins et l’autodétermination professionnelle. Toutefois, nombre des actions répertoriées avaient pour finalité fonctionnelle la protection et la survie des infirmières au sein d’un dispositif hospitalier déshumanisant. Certaines infirmières soignantes s’objectent en conscience, déploient des actions de non-coopération individuelles et collectives, font preuve d’actes de désobéissance civile ou souhaitent agir en ce sens pour établir un rapport de force nécessaire à la prise en compte de leurs revendications par une gouvernance hospitalière qui autrement ferait la sourde oreille. Le pouvoir exercé de façon hostile par la gouvernance hospitalière doit à notre avis être contrecarré par une force infirmière collective égale ou supérieure, sans quoi les politiques qui lui sont associées continueront de leur être imposées. Le renouvellement radical de la démocratie hospitalière apparaît comme la finalité centrale vers laquelle doivent s’articuler les actions infirmières collectives qui permettront l’établissement d’un nouveau rapport de force puisque c’est à partir de celle-ci que les infirmières soignantes pourront débattre de l’orientation que doit prendre l’exercice infirmier.

Évolution à fine échelle des sites d'épissage des introns dans les gènes des oomycètes

Les introns sont des portions de gènes transcrites dans l’ARN messager, mais retirées pendant l’épissage avant la synthèse des produits du gène. Chez les eucaryotes, on rencontre les introns splicéosomaux, qui sont retirés de l’ARN messager par des splicéosomes. Les introns permettent plusieurs processus importants, tels que l'épissage alternatif, la dégradation des ARNs messagers non-sens, et l'encodage d'ARNs fonctionnels. Leurs rôles nous interrogent sur l'influence de la sélection naturelle sur leur évolution. Nous nous intéressons aux mutations qui peuvent modifier les produits d'un gène en changeant les sites d'épissage des introns. Ces mutations peuvent influencer le fonctionnement d'un organisme, et constituent donc un sujet d'étude intéressant, mais il n'existe actuellement pas de logiciels permettant de les étudier convenablement. Le but de notre projet était donc de concevoir une méthode pour détecter et analyser les changements des sites d'épissage des introns splicéosomaux. Nous avons finalement développé une méthode qui repère les évènements évolutifs qui affectent les introns splicéosomaux dans un jeu d'espèces données. La méthode a été exécutée sur un ensemble d'espèces d'oomycètes. Plusieurs évènements détectés ont changé les sites d’épissage et les protéines, mais de nombreux évènements trouvés ont modifié les introns sans affecter les produits des gènes. Il manque à notre méthode une étape finale d'analyse approfondie des données récoltées. Cependant, la méthode actuelle est facilement reproductible et automatise l'analyse des génomes pour la détection des évènements. Les fichiers produits peuvent ensuite être analysés dans chaque étude pour répondre à des questions spécifiques.

Modélisation de répartition d’espèces aviaires et de feux en forêt boréale du Québec dans un contexte de changement climatique

Les changements climatiques prennent une importance grandissante dans l’étude des phénomènes spatiaux à grande échelle. Plusieurs experts affirment que les changements climatiques seront un des principaux moteurs de changement écologique dans les prochaines décennies et que leurs conséquences seront inévitables. Ces changements se manifesteront sur le milieu physique par la fonte des calottes glaciaires, le dégel du pergélisol, l’instabilité des versants montagneux en zone de pergélisol, l’augmentation de l’intensité, de la sévérité et de la fréquence des événements climatiques extrêmes tels les feux de forêt. Les changements climatiques se manifesteront aussi sur le milieu biologique, tel la modification de la durée de la saison végétative, l’augmentation des espèces exotiques invasives et les changements dans la distribution en espèces vivantes. Deux aspects sont couverts par cette étude : 1) les changements dans la répartition spatiale de 39 espèces d’oiseaux et 2) les modifications dans les patrons spatiaux des feux, en forêt boréale québécoise, tous deux dans l’horizon climatique de 2100. Une approche de modélisation statistique démontre que la répartition spatiale des oiseaux de la forêt boréale est fortement liée à des variables bioclimatiques (R2adj = 0.53). Ces résultats permettent d’effectuer des modélisations bioclimatiques pour le gros-bec errant et la mésange à tête noire quivoient une augmentation de la limite nordique de distribution de l’espèce suivant l’intensité du réchauffement climatique. Finalement, une modélisation spatialement explicite par automate cellulaire permet de démontrer comment les changements climatiques induiront une augmentation dans la fréquence de feux de forêt et dans la superficie brûlée en forêt boréale du Québec.