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”.

Conception des réseaux maillés sans fil à multiples-radios multiples-canaux

Généralement, les problèmes de conception de réseaux consistent à sélectionner les arcs et les sommets d’un graphe G de sorte que la fonction coût est optimisée et l’ensemble de contraintes impliquant les liens et les sommets dans G sont respectées. Une modification dans le critère d’optimisation et/ou dans l’ensemble de contraintes mène à une nouvelle représentation d’un problème différent. Dans cette thèse, nous nous intéressons au problème de conception d’infrastructure de réseaux maillés sans fil (WMN- Wireless Mesh Network en Anglais) où nous montrons que la conception de tels réseaux se transforme d’un problème d’optimisation standard (la fonction coût est optimisée) à un problème d’optimisation à plusieurs objectifs, pour tenir en compte de nombreux aspects, souvent contradictoires, mais néanmoins incontournables dans la réalité. Cette thèse, composée de trois volets, propose de nouveaux modèles et algorithmes pour la conception de WMNs où rien n’est connu à l’ avance. Le premiervolet est consacré à l’optimisation simultanée de deux objectifs équitablement importants : le coût et la performance du réseau en termes de débit. Trois modèles bi-objectifs qui se différent principalement par l’approche utilisée pour maximiser la performance du réseau sont proposés, résolus et comparés. Le deuxième volet traite le problème de placement de passerelles vu son impact sur la performance et l’extensibilité du réseau. La notion de contraintes de sauts (hop constraints) est introduite dans la conception du réseau pour limiter le délai de transmission. Un nouvel algorithme basé sur une approche de groupage est proposé afin de trouver les positions stratégiques des passerelles qui favorisent l’extensibilité du réseau et augmentent sa performance sans augmenter considérablement le coût total de son installation. Le dernier volet adresse le problème de fiabilité du réseau dans la présence de pannes simples. Prévoir l’installation des composants redondants lors de la phase de conception peut garantir des communications fiables, mais au détriment du coût et de la performance du réseau. Un nouvel algorithme, basé sur l’approche théorique de décomposition en oreilles afin d’installer le minimum nombre de routeurs additionnels pour tolérer les pannes simples, est développé. Afin de résoudre les modèles proposés pour des réseaux de taille réelle, un algorithme évolutionnaire (méta-heuristique), inspiré de la nature, est développé. Finalement, les méthodes et modèles proposés on été évalués par des simulations empiriques et d’événements discrets.

La génomique évolutive mitochondriale révèle des échanges génétiques et la ségrégation chez les Gloméromycètes

Les champignons mycorhiziens à arbuscules (CMA) sont des organismes microscopiques du sol qui jouent un rôle crucial dans les écosystèmes naturels et que l’on retrouve dans tous les habitats de la planète. Ils vivent en relation symbiotique avec la vaste majorité des plantes terrestres. Ils sont des biotrophes obligatoires, c'est-à-dire qu'ils ne peuvent croître qu'en présence d'une plante hôte. Cette symbiose permet entre autres à la plante d'acquérir des nutriments supplémentaires, en particulier du phosphore et du nitrate. Malgré le fait que cette symbiose apporte des services importants aux écosystèmes, la richesse des espèces, la structure des communautés, ainsi que la diversité fonctionnelle des CMA sont mal connues et l'approfondissement des connaissances dans ces domaines dépend d’outils de diagnostic moléculaire. Cependant, la présence de polymorphisme nucléaire intra-isolat combiné à un manque de données génomiques dans différents groupes phylogénétique de ces champignons complique le développement de marqueurs moléculaires et la détermination de l'affiliation évolutive à hauts niveaux de résolution (c.a.d. entre espèces génétiquement similaires et/ou isolats de la même espèce). . Pour ces raisons, il semble une bonne alternative d’utiliser un système génétique différent en ciblant le génome mitochondrial, qui a été démontré homogène au sein d'un même isolat de CMA. Cependant, étant donné le mode de vie particulier de ces organismes, une meilleure compréhension des processus évolutifs mitochondriaux est nécessaire afin de valoriser l'utilisation de tels marqueurs dans des études de diversité et en génétique des populations. En ce sens, mon projet de doctorat consistait à investiguerétudier: i) les vecteurs de divergences inter-isolats et -espèces génétiquement rapprochéesphylogénétiquement apparentées, ii) la plasticité des génomes mitochondriaux, iii) l'héritabilité mitochondriale et les mécanismes potentiels de ségrégation, ainsi que iv) la diversité mitochondriale intra-isolat in situ. À l'aide de la génomique mitochondriale comparative, en utilisant le séquençage nouvelle génération, on a démontré la présence de variation génétique substantielle inter-isolats et -espèces, engendrées par l'invasion d'éléments mobiles dans les génomes mitochondriaux des CMA, donnant lieu à une évolution moléculaire rapide des régions intergéniques. Cette variation permettait de développer des marqueurs spécifiques à des isolats de la même espèce. Ensuite, à l'aide d'une approche analytique par réseaux de gènes sur des éléments mobiles, on a été en mesure de démontrer des évènements de recombinaisons homologues entre des haplotypes mitochondriaux distincts, menant à des réarrangements génomiques. Cela a permis d'ouvrir les perspectives sur la dynamique mitochondriale et l'hétéroplasmie dans un même isolatsuggère une coexistence de différents haplotypes mitochondriaux dans les populations naturelles et que les cultures monosporales pourraient induirent une sous-estimation de la diversité allélique mitochondriale. Cette apparente contradiction avec l'homogénéité mitochondriale intra-isolat généralement observée, a amené à investiguer étudier les échanges génétiques à l'aide de croisements d'isolats génétiquement distincts. Malgré l'observation de quelques spores filles hétéroplasmiques, l'homoplasmie était le statut par défaut dans toutes les cultures monosporales, avec un biais en faveur de l'un des haplotypes parentaux. Ces résultats suggèrent que la ségrégation opère durant la formation de la spore et/ou le développement de la coloniedu mycélium. De plus, ils supportent la présence d'une machinerie protéique de ségrégation mitochondriale chez les CMAAMF, où l'ensemble des gènes impliqués dans ce mécanisme ont été retrouvé et sont orthologues aux autres champignons. Finalement, on est revenue aux sources avecon a étudié le polymorphisme mitochondrial intra-isolat à l'aide d'une approche conventionnelle de PCR en utilisant une Taq polymérase de haute fidélité, suivie de clonage et de séquençage Sanger, sur deux isolats de R. irregularis. Cela a permis l'observation d'hétéroplasmie in situ, ainsi que la co-expression de variantes de variantes de protéines'ARNm dans une souche in vitro. Les résultats suggèrent que d'autres études basées sur le séquençage nouvelle génération aurait potentiellement ignorée cette variation, offrant ainsi plusieurs nouveaux arguments permettant de considérer les CMA comme des organismes possédant une population de génomes mitochondriaux et nucléaires distincts.

Approches générales de résolution pour les problèmes multi-attributs de tournées de véhicules et confection d'horaires

Thèse réalisée en cotutelle entre l'Université de Montréal et l'Université de Technologie de Troyes