L'évolution des espèces est régie par les modifications stochastiques qui ont eu lieu au niveau du code génétique -l'ADN -composé d'une suite de petites molécules (les nucléotides). Selon l'ampleur de ces évènements, il y a d'abord des modifications à petite échelle, impliquant quelques nucléotides -les insertions, délétions et substitutions. Due à l'impossibilité actuelle de différencier les insertions des délétions, on les appelle communément indels. D'un autre coté, il ya des modifications à grande échelle -impliquant parfois des grandes régions génomiques ou des chromosomes. Les modifications à grande échelle les plus fréquentes sont: les duplications, translocations, inversions et délétions. Au cours de ce projet, nous avons développé une méthode de génomique comparée, capable de relier l'information épidémiologique, comme la carcinogenicité et l'invasivité des souches, aux séquences génomiques. Cette méthode permet de détecter des régions statistiquement significatives à analyser plus en détail par des biologistes, tout en étant capable de discriminer ce seuil à l'aide du calcul des p-values. Nous avons utilisé cette méthode dans l'étude du virus du papillome humain et de la bactérie Neisseria Meningitidis, bactérie responsable de la méningite. Pour le virus du papillome humain, notre méthode a été capable de détecter le domaine PDZ, une région du gène E6, qui est une condition sine qua non de la carcinogenicité du produit de ce gène. Au cours des analyses phylogénétiques de cette famille nous avons trouvé une corrélation statistiquement significative entre les événements à petite échelle et les données épidémiologiques. Par la suite nous avons proposé une séquence de tests pour orienter l'analyse statistique de cette corrélation. Nous avons également remarqué que la carcinogenicité est généralement monophylétique, donc issue d'un ancêtre commun. L'arbre phylogénétique inféré est le premier basé sur les génomes entiers, ce qui a permis d'étudier la variabilité des topologies de gènes par rapport à celle du génome. Pour la bactérie Neisseria Meningitidis nous avons montré qu'il est possible de syntoniser les fonctions de discrimination, pour établir la différence entre les régions responsables du maximum d'invasivité et celles qui ont un rôle structural dans ce processus, détection des structures moléculaires connues (i.e. les anses extra cellulaires, dans notre cas). Les résultats de nos travaux ont permis la mise à la disposition de la communauté internationale de deux bases de données, pour le VPH et le Neisseria, respectivement. Ces bases contiennent des régions candidates à être analysées en laboratoire par des biologistes. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Algorithme pour la détection des régions carcinogènes, Événements évolutionnaires, Analyse de redondance, Arbre phylogénétique, Conception de vaccin, Mutations, Invasivité, Neisseria Meningitidis, Virus du papillome humain.

La littérature fait état des travaux de recherches qui ont été menés pour la résolution des problèmes d'ordonnancement de production. La complexité de ces problèmes rend nécessaire l'emploi de stratégies de recherche de solutions évoluées. Parmi celle-ci figure le formalisme du calcul propositionnel, le plus souvent sous forme normale conjonctive (FNC) associé au problème de satisfiabilité (SAT). Le présent travail de recherche a pour but d'intégrer les formalismes d'approches de résolution des problèmes SAT pour la résolution du problème d'ordonnancement de production, soit le problème d'ordonnancement de véhicules, proposé dans le cadre du challenge ROADEF'2005. Dans un premier temps, les principaux algorithmes pour la résolution de problème SAT sont présentés, particulièrement les algorithmes basés sur le retour en arrière tels que le retour-arrière (Backtracking) et le retour ponctuel (Backjumping) étendus sur les TL-clauses (True-Literal clauses). Ce travail de recherche couvre le développement de trois approches de résolutions du problème SAT appliquées au problème d'ordonnancement de véhicules. Pour chaque approche un encodage en FNC/TL traduisant les contraintes du problème ainsi que l'objectif à optimiser sont effectués. Ces FNC/TL sont générées en format DIMACS à l'aide du logiciel développé par l'auteur. Ensuite, une stratégie de résolution est décrite, en fixant à chaque fois l'objectif à optimiser. Dans la première approche, le problème est traité globalement. Les deux autres approches subdivisent le problème initial en sous-problèmes. Finalement une comparaison des trois approches est décrite. Les instances du problème proposées par le challenge ROADEF'2005 sont utilisées comme base d'évaluation des approches développées. Les résultats obtenus sont comparés aux meilleurs résultats obtenus par le gagnant du challenge ROADEF'2005, à l'aide du logiciel suggéré par le challenge, soit exeCarSeq. Une analyse détaillée des résultats montre que notre stratégie de résolution du problème d'ordonnancement de véhicules est une voie prometteuse. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Forme normale conjonctive, Problème de satisfiabilité, Problème d'ordonnancement de véhicules, TL-clauses, Encodage en FNC/TL.

With the high development of Chinese economy, the number of automobiles rises sharply. In order to let more vehicles pass the limited roads successfully, The Aerawide Real-Time Traffic Control CARTC) System cornes up. Although ARTC has been studied for many years in foreign countries, its study is still in the embryonic stage in China. After investigating, we discovered that system just recently. Only some simple Intelligent transport control has been realized in quite a few cities However, in many large and middle cities, Intelligent transport control is still in a research period. We had been thinking about this research from juniors. We spent one year doing large quantity of social examination, investigating some roads personally and inquiring a lot of material from Internet and library. On the basis of this, we made the road sate model. Several typical states are represented on this model, so it is definitely representative. We chose the comparatively simple and easily operated green wave control. One computer controls six PLC. Long-range control is realized by dialing online the modulator-demodulator. We adopted some basic vague control thought, meanwhile, combined with actual circumstances, and designed a set of practical control algorithm. We mainly used VB6.0 and PLC programmed software from OMRON Company. In the end, we completed the control program of both the upper and lower bit machine. Of course, there are many immature and imperfect aspects in our design, I hope to get guidance and help from all people. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : ARTC (Aerawide Real-Time Traffic Control), PLC (Programmable Logic Contrllor), ITS (Intelligent Traffic System)

À chaque semestre, la direction du Département d'informatique de l'UQAM doit convenablement affecter les divers groupes-cours disponibles à ses professeurs, en se basant sur leurs préférences et certaines règles adoptées par l'assemblée départementale. Le but de notre travail est développer un algorithme qui trouve une solution de bonne qualité à ce problème, et ce dans un temps raisonnable. Dans ce mémoire, nous appliquons deux approches différentes pour résoudre le problème d'affectation des groupes-cours. La première est basée sur un algorithme branch-and-bound, qui est un algorithme de recherche exhaustif et complet. La deuxième est basée sur un processus heuristique de recherche local amélioré. Plus particulièrement, nous nous concentrons sur l'algorithme de recherche local. Des algorithmes de recherche locale divers sont présentés, entre autres, la recherche locale guidée et le recuit simulé. Ce que nous faisons n'est pas simplement d'appliquer ces algorithmes et les combiner ensemble. Nous essayons aussi de nous inspirer de ces algorithmes pour mettre au point quelques nouvelles idées appropriées pour notre propre problème. Finalement, nous utilisons les résultats expérimentaux obtenus par l'algorithme branch-and-bound comme point de référence en ce qui concerne la qualité de la solution et le temps d'exécution pour évaluer les autres approches. Les résultats que nous avons obtenus de données réelles et des données générées aléatoirement montrent que notre algorithme effectue un bon travail tant en termes de qualité de solution que de temps d'exécution. Les résultats montrent aussi que notre algorithme peut trouver une bonne solution à de grands problèmes en un temps raisonnable. ______________________________________________________________________________

Dans ce document, nous proposons un algorithme heuristique efficace pour résoudre le problème de partage spectral dynamique dans les réseaux de radios cognitives. Cet algorithme fonctionne selon les principes du paradigme de transmissions cognitives simultanées (en anglais underlay) où des utilisateurs primaires et des utilisateurs secondaires transmettent simultanément sur la même bande spectrale. L'algorithme proposé est basé sur un modèle théorique de graphe. Premièrement., le réseau de radios cognitives est modélisé en un graphe dont les sommets possèdent des poids. Le problème de partage spectral se réduit à colorier les sommets du graphe. Les décisions de partage spectral sont prises au niveau d'un serveur spectral qui coordonne les transmissions secondaires afin de trouver les paires (transmission secondaire/bande spectrale) qui maximisent le débit global du système. Le serveur spectral est aussi responsable de protéger les transmissions des utilisateurs primaires de l'interférence causée par les transmissions des utilisateurs secondaires. La réussite de cette tâche se base sur une allocation appropriée des puissances de transmission pour les utilisateurs secondaires. Grâce à des simulations bien élaborées, nous démontrons que les performances de l'algorithme proposé en terme de débit global sont proches de celles de l'algorithme optimal. Les performances de notre algorithme illustrent le gain en performances dû à une augmentation de la diversité de sélection de bande passante et à une diversité de sélection d'utilisateurs secondaires. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : algorithme de partage spectral, réseau de radios cognitives, théorie des graphes, systèmes de communication sans fil, simulation des réseaux.

L'objectif de cette thèse est d'appliquer les méthodes d'approximations stochastiques à l'estimation de la densité et de la régression. Dans le premier chapitre, nous construisons un algorithme stochastique à pas simple qui définit toute une famille d'estimateurs récursifs à noyau d'une densité de probabilité. Nous étudions les différentes propriétés de cet algorithme. En particulier, nous identifions deux classes d'estimateurs; la première correspond à un choix de pas qui permet d'obtenir un risque minimal, la seconde une variance minimale. Dans le deuxième chapitre, nous nous intéressons à l'estimateur proposé par Révész (1973, 1977) pour estimer une fonction de régression r:x-> E[Y|X=x]. Son estimateur r_n, construit à l'aide d'un algorithme stochastique à pas simple, a un gros inconvénient: les hypothèses sur la densité marginale de X nécessaires pour établir la vitesse de convergence de r_n sont beaucoup plus fortes que celles habituellement requises pour étudier le comportement asymptotique d'un estimateur d'une fonction de régression. Nous montrons comment l'application du principe de moyennisation des algorithmes stochastiques permet, tout d'abord en généralisant la définition de l'estimateur de Révész, puis en moyennisant cet estimateur généralisé, de construire un estimateur récursif br_n qui possède de bonnes propriétés asymptotiques. Dans le troisième chapitre, nous appliquons à nouveau les méthodes d'approximation stochastique à l'estimation d'une fonction de régression. Mais cette fois, plutôt que d'utiliser des algorithmes stochastiques à pas simple, nous montrons comment les algorithmes stochastiques à pas doubles permettent de construire toute une classe d'estimateurs récursifs d'une fonction de régression, et nous étudions les propriétés asymptotiques de ces estimateurs. Cette approche est beaucoup plus simple que celle du deuxième chapitre: les estimateurs construits à l'aide des algorithmes à pas doubles n'ont pas besoin d'être moyennisés pour avoir les bonnes propriétés asymptotiques.

Texte remanié de : PhD : George Mason University : 2002.

Les polyominos sont souvent représentés par des mots de quatre lettres ou des mots de changements de direction décrivant leur contour. La combinatoire des mots classique y joue donc un rôle descriptif important, particulièrement dans le choix d'un représentant canonique. Les mots de Lyndon fournissent, de façon naturelle, un tel représentant. Une approche systématique pour le calcul de propriétés des polyominos, basée sur une version originale d'une discrétisation du théorème de Green classique en calcul bivarié, est élaborée. Ceci nous a naturellement amené à analyser les propriétés géométriques d'ensembles du réseau discret de rondeur maximale. Pour une taille donnée, ces ensembles minimisent le moment d'inertie par rapport à un axe passant par leur centre de gravité. Nous introduisons la notion de quasi-disque et montrons entre autres que ces ensembles minimaux sont des poIyominos fortement-convexes. Nous développons également un algorithme permettant de les engendrer systématiquement. Un autre aspect concerne des propriétés sur les contours d'ensembles discrets donnant lieu à une nouvelle démonstration d'un résultat de Daurat et Nivat sur les points dits saillants et rentrants d'un polyomino. Nous présentons également une généralisation de ce résultat aux réseaux hexagonaux et montrons que le résultat est faux pour les autres réseaux semi-réguliers. Nous poursuivons par l'introduction d'opérations de mélange spéciaux sur des mots décrivant des chemins discrets selon la suite de leurs changements de direction. Ces opérations de mélange permettent d'engendrer des courbes fractales du type courbe de dragon et d'analyser certains de leurs invariants. Finalement, une généralisation aux dimensions supérieures des algorithmes précédents basés sur le théorème de Green discret, est présentée. Plus particulièrement, nous développons une version discrète du théorème de Stokes basée sur des familles de poids sur les hypercubes de dimension k dans l'espace discret Zn, k ≤ n. Quelques applications sont également décrites. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Géométrie discrète, Combinatoire des mots, Ensembles discrets, Polyominos, Quasi-disques, Chemins polygonaux, Courbes de dragon, Théorème de Green discret, Théorème de Stokes discret, Algorithmes.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal