Tarification logit dans un réseau

Le problème de tarification qui nous intéresse ici consiste à maximiser le revenu généré par les usagers d'un réseau de transport. Pour se rendre à leurs destinations, les usagers font un choix de route et utilisent des arcs sur lesquels nous imposons des tarifs. Chaque route est caractérisée (aux yeux de l'usager) par sa "désutilité", une mesure de longueur généralisée tenant compte à la fois des tarifs et des autres coûts associés à son utilisation. Ce problème a surtout été abordé sous une modélisation déterministe de la demande selon laquelle seules des routes de désutilité minimale se voient attribuer une mesure positive de flot. Le modèle déterministe se prête bien à une résolution globale, mais pèche par manque de réalisme. Nous considérons ici une extension probabiliste de ce modèle, selon laquelle les usagers d'un réseau sont alloués aux routes d'après un modèle de choix discret logit. Bien que le problème de tarification qui en résulte est non linéaire et non convexe, il conserve néanmoins une forte composante combinatoire que nous exploitons à des fins algorithmiques. Notre contribution se répartit en trois articles. Dans le premier, nous abordons le problème d'un point de vue théorique pour le cas avec une paire origine-destination. Nous développons une analyse de premier ordre qui exploite les propriétés analytiques de l'affectation logit et démontrons la validité de règles de simplification de la topologie du réseau qui permettent de réduire la dimension du problème sans en modifier la solution. Nous établissons ensuite l'unimodalité du problème pour une vaste gamme de topologies et nous généralisons certains de nos résultats au problème de la tarification d'une ligne de produits. Dans le deuxième article, nous abordons le problème d'un point de vue numérique pour le cas avec plusieurs paires origine-destination. Nous développons des algorithmes qui exploitent l'information locale et la parenté des formulations probabilistes et déterministes. Un des résultats de notre analyse est l'obtention de bornes sur l'erreur commise par les modèles combinatoires dans l'approximation du revenu logit. Nos essais numériques montrent qu'une approximation combinatoire rudimentaire permet souvent d'identifier des solutions quasi-optimales. Dans le troisième article, nous considérons l'extension du problème à une demande hétérogène. L'affectation de la demande y est donnée par un modèle de choix discret logit mixte où la sensibilité au prix d'un usager est aléatoire. Sous cette modélisation, l'expression du revenu n'est pas analytique et ne peut être évaluée de façon exacte. Cependant, nous démontrons que l'utilisation d'approximations non linéaires et combinatoires permet d'identifier des solutions quasi-optimales. Finalement, nous en profitons pour illustrer la richesse du modèle, par le biais d'une interprétation économique, et examinons plus particulièrement la contribution au revenu des différents groupes d'usagers.

Analyse de mouvements faciaux à partir d'images vidéo

Lors d'une intervention conversationnelle, le langage est supporté par une communication non-verbale qui joue un rôle central dans le comportement social humain en permettant de la rétroaction et en gérant la synchronisation, appuyant ainsi le contenu et la signification du discours. En effet, 55% du message est véhiculé par les expressions faciales, alors que seulement 7% est dû au message linguistique et 38% au paralangage. L'information concernant l'état émotionnel d'une personne est généralement inférée par les attributs faciaux. Cependant, on ne dispose pas vraiment d'instruments de mesure spécifiquement dédiés à ce type de comportements. En vision par ordinateur, on s'intéresse davantage au développement de systèmes d'analyse automatique des expressions faciales prototypiques pour les applications d'interaction homme-machine, d'analyse de vidéos de réunions, de sécurité, et même pour des applications cliniques. Dans la présente recherche, pour appréhender de tels indicateurs observables, nous essayons d'implanter un système capable de construire une source consistante et relativement exhaustive d'informations visuelles, lequel sera capable de distinguer sur un visage les traits et leurs déformations, permettant ainsi de reconnaître la présence ou absence d'une action faciale particulière. Une réflexion sur les techniques recensées nous a amené à explorer deux différentes approches. La première concerne l'aspect apparence dans lequel on se sert de l'orientation des gradients pour dégager une représentation dense des attributs faciaux. Hormis la représentation faciale, la principale difficulté d'un système, qui se veut être général, est la mise en œuvre d'un modèle générique indépendamment de l'identité de la personne, de la géométrie et de la taille des visages. La démarche qu'on propose repose sur l'élaboration d'un référentiel prototypique à partir d'un recalage par SIFT-flow dont on démontre, dans cette thèse, la supériorité par rapport à un alignement conventionnel utilisant la position des yeux. Dans une deuxième approche, on fait appel à un modèle géométrique à travers lequel les primitives faciales sont représentées par un filtrage de Gabor. Motivé par le fait que les expressions faciales sont non seulement ambigües et incohérentes d'une personne à une autre mais aussi dépendantes du contexte lui-même, à travers cette approche, on présente un système personnalisé de reconnaissance d'expressions faciales, dont la performance globale dépend directement de la performance du suivi d'un ensemble de points caractéristiques du visage. Ce suivi est effectué par une forme modifiée d'une technique d'estimation de disparité faisant intervenir la phase de Gabor. Dans cette thèse, on propose une redéfinition de la mesure de confiance et introduisons une procédure itérative et conditionnelle d'estimation du déplacement qui offrent un suivi plus robuste que les méthodes originales.

Les systèmes super intégrables d’ordre trois séparables en coordonnées paraboliques

Ce mémoire est une poursuite de l’étude de la superintégrabilité classique et quantique dans un espace euclidien de dimension deux avec une intégrale du mouvement d’ordre trois. Il est constitué d’un article. Puisque les classifications de tous les Hamiltoniens séparables en coordonnées cartésiennes et polaires sont déjà complétées, nous apportons à ce tableau l’étude de ces systèmes séparables en coordonnées paraboliques. Premièrement, nous dérivons les équations déterminantes d’un système en coordonnées paraboliques et ensuite nous résolvons les équations obtenues afin de trouver les intégrales d’ordre trois pour un potentiel qui permet la séparation en coordonnées paraboliques. Finalement, nous démontrons que toutes les intégrales d’ordre trois pour les potentiels séparables en coordonnées paraboliques dans l’espace euclidien de dimension deux sont réductibles. Dans la conclusion de l’article nous analysons les différences entre les potentiels séparables en coordonnées cartésiennes et polaires d’un côté et en coordonnées paraboliques d’une autre côté. Mots clés: intégrabilité, superintégrabilité, mécanique classique, mécanique quantique, Hamiltonien, séparation de variable, commutation.

Le cinéma omnistéréo ou l'art d'avoir des yeux tout le tour de la tête

Cette thèse s'intéresse à des aspects du tournage, de la projection et de la perception du cinéma stéréo panoramique, appelé aussi cinéma omnistéréo. Elle s'inscrit en grande partie dans le domaine de la vision par ordinateur, mais elle touche aussi aux domaines de l'infographie et de la perception visuelle humaine. Le cinéma omnistéréo projette sur des écrans immersifs des vidéos qui fournissent de l'information sur la profondeur de la scène tout autour des spectateurs. Ce type de cinéma comporte des défis liés notamment au tournage de vidéos omnistéréo de scènes dynamiques, à la projection polarisée sur écrans très réfléchissants rendant difficile l'estimation de leur forme par reconstruction active, aux distorsions introduites par l'omnistéréo pouvant fausser la perception des profondeurs de la scène. Notre thèse a tenté de relever ces défis en apportant trois contributions majeures. Premièrement, nous avons développé la toute première méthode de création de vidéos omnistéréo par assemblage d'images pour des mouvements stochastiques et localisés. Nous avons mis au point une expérience psychophysique qui montre l'efficacité de la méthode pour des scènes sans structure isolée, comme des courants d'eau. Nous proposons aussi une méthode de tournage qui ajoute à ces vidéos des mouvements moins contraints, comme ceux d'acteurs. Deuxièmement, nous avons introduit de nouveaux motifs lumineux qui permettent à une caméra et un projecteur de retrouver la forme d'objets susceptibles de produire des interréflexions. Ces motifs sont assez généraux pour reconstruire non seulement les écrans omnistéréo, mais aussi des objets très complexes qui comportent des discontinuités de profondeur du point de vue de la caméra. Troisièmement, nous avons montré que les distorsions omnistéréo sont négligeables pour un spectateur placé au centre d'un écran cylindrique, puisqu'elles se situent à la périphérie du champ visuel où l'acuité devient moins précise.

Riboswitches : le cas des atténuateurs de la transcription du type terminateur/antiterminateur chez les bactéries

Il est essentiel pour chaque organisme d’avoir la possibilité de réguler ses fonctions afin de permettre sa survie et d’améliorer sa capacité de se reproduire en divers habitats. Avec l’information disponible, il semble que les organismes consacrent une partie assez importante de leur matériel génétique à des fonctions de régulation. On peut envisager que certains mécanismes de régulation ont persisté dans le temps parce qu’ils remplissent bien leurs rôles. Les premières études sur les procaryotes ont indiqué qu’il y avait peu de mécanismes de régulation exerçant le contrôle des gènes, mais il a été démontré par la suite qu’une variété de ces mécanismes est utilisée pour la régulation de gènes et d’opérons. En particulier, les opérons bactériens impliqués dans la biosynthèse des acides aminés, l’ARNt synthétase, la dégradation des acides aminés, les protéines ribosomales et l’ARN ribosomal font l’objet d’un contrôle par l’atténuation de la transcription. Ce mécanisme d’atténuation de la transcription diffère d’autres mécanismes pour la génération de deux structures différentes de l’ARNm, où l’une de ces structures réprime le gène en aval, et l’autre permet de continuer la transcription/traduction. Dans le cadre de cette recherche, nous nous sommes intéressé au mécanisme d’atténuation de la transcription chez les procaryotes où aucune molécule ne semble intervenir comme facteur de régulation, en me concentrant sur la régulation des opérons bactériens. Le but principal de ce travail est de présenter une nouvelle méthode de recherche des riborégulateurs qui combine la recherche traditionnelle des riborégulateurs avec la recherche structurale. En incorporant l’étude du repliement de l’ARNm, nous pouvons mieux identifier les atténuateurs répondant à ce type de mécanisme d’atténuation. Ce mémoire est divisé en quatre chapitres. Le premier chapitre présente une revue de la littérature sur l’ARN et un survol sur les mécanismes de régulation de l’expression génétique chez les procaryotes. Les chapitres 2 et 3 sont consacrés à la méthodologie utilisée dans cette recherche et à l’implémentation du logiciel TA-Search. Enfin, le chapitre 4 expose les conclusions et les applications potentielles de la méthode.

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

Identification et localisation des préoccupations fonctionnelles dans un code légataire Java

Traditionnellement, les applications orientées objets légataires intègrent différents aspects fonctionnels. Ces aspects peuvent être dispersés partout dans le code. Il existe différents types d’aspects : • des aspects qui représentent des fonctionnalités métiers ; • des aspects qui répondent à des exigences non fonctionnelles ou à d’autres considérations de conception comme la robustesse, la distribution, la sécurité, etc. Généralement, le code qui représente ces aspects chevauche plusieurs hiérarchies de classes. Plusieurs chercheurs se sont intéressés à la problématique de la modularisation de ces aspects dans le code : programmation orientée sujets, programmation orientée aspects et programmation orientée vues. Toutes ces méthodes proposent des techniques et des outils pour concevoir des applications orientées objets sous forme de composition de fragments de code qui répondent à différents aspects. La séparation des aspects dans le code a des avantages au niveau de la réutilisation et de la maintenance. Ainsi, il est important d’identifier et de localiser ces aspects dans du code légataire orienté objets. Nous nous intéressons particulièrement aux aspects fonctionnels. En supposant que le code qui répond à un aspect fonctionnel ou fonctionnalité exhibe une certaine cohésion fonctionnelle (dépendances entre les éléments), nous proposons d’identifier de telles fonctionnalités à partir du code. L’idée est d’identifier, en l’absence des paradigmes de la programmation par aspects, les techniques qui permettent l’implémentation des différents aspects fonctionnels dans un code objet. Notre approche consiste à : • identifier les techniques utilisées par les développeurs pour intégrer une fonctionnalité en l’absence des techniques orientées aspects • caractériser l’empreinte de ces techniques sur le code • et développer des outils pour identifier ces empreintes. Ainsi, nous présentons deux approches pour l’identification des fonctionnalités existantes dans du code orienté objets. La première identifie différents patrons de conception qui permettent l’intégration de ces fonctionnalités dans le code. La deuxième utilise l’analyse formelle de concepts pour identifier les fonctionnalités récurrentes dans le code. Nous expérimentons nos deux approches sur des systèmes libres orientés objets pour identifier les différentes fonctionnalités dans le code. Les résultats obtenus montrent l’efficacité de nos approches pour identifier les différentes fonctionnalités dans du code légataire orienté objets et permettent de suggérer des cas de refactorisation.

Images géométriques de genre arbitraire dans le domaine sphérique

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

Système symbolique de création de résumés de mise à jour

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

Le rôle épistémique de certaines simulations informatiques fondamentales en théorie de l'évolution

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

Détection et caractérisation des interactions dans les maladies complexes

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

Étude des mécanismes de capture et de fuite des excitons dans les boîtes quantiques d'InAs/InP

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

Identification d’une architecture à base de composants dans une application orientée objets à l’aide d’une analyse dynamique

Un système, décrit avec un grand nombre d'éléments fortement interdépendants, est complexe, difficile à comprendre et à maintenir. Ainsi, une application orientée objet est souvent complexe, car elle contient des centaines de classes avec de nombreuses dépendances plus ou moins explicites. Une même application, utilisant le paradigme composant, contiendrait un plus petit nombre d'éléments, faiblement couplés entre eux et avec des interdépendances clairement définies. Ceci est dû au fait que le paradigme composant fournit une bonne représentation de haut niveau des systèmes complexes. Ainsi, ce paradigme peut être utilisé comme "espace de projection" des systèmes orientés objets. Une telle projection peut faciliter l'étape de compréhension d'un système, un pré-requis nécessaire avant toute activité de maintenance et/ou d'évolution. De plus, il est possible d'utiliser cette représentation, comme un modèle pour effectuer une restructuration complète d'une application orientée objets opérationnelle vers une application équivalente à base de composants tout aussi opérationnelle. Ainsi, La nouvelle application bénéficiant ainsi, de toutes les bonnes propriétés associées au paradigme composants. L'objectif de ma thèse est de proposer une méthode semi-automatique pour identifier une architecture à base de composants dans une application orientée objets. Cette architecture doit, non seulement aider à la compréhension de l'application originale, mais aussi simplifier la projection de cette dernière dans un modèle concret de composant. L'identification d'une architecture à base de composants est réalisée en trois grandes étapes: i) obtention des données nécessaires au processus d'identification. Elles correspondent aux dépendances entre les classes et sont obtenues avec une analyse dynamique de l'application cible. ii) identification des composants. Trois méthodes ont été explorées. La première utilise un treillis de Galois, la seconde deux méta-heuristiques et la dernière une méta-heuristique multi-objective. iii) identification de l'architecture à base de composants de l'application cible. Cela est fait en identifiant les interfaces requises et fournis pour chaque composant. Afin de valider ce processus d'identification, ainsi que les différents choix faits durant son développement, j'ai réalisé différentes études de cas. Enfin, je montre la faisabilité de la projection de l'architecture à base de composants identifiée vers un modèle concret de composants.

Études des fuites excitoniques dans des familles de boîtes quantiques d'InAs/InP par PLRT par addition de fréquences

Ce mémoire porte sur les mécanismes de relaxation et de fuite des excitons dans des systèmes de boîtes quantiques(BQs) d’InAs/InP. Les systèmes sont composés d’un sub- strat volumique d’InP, appelé matrice (M), d’un puits quantique d’InAs, nommé couche de mouillage (CM), et des familles de BQs d’InAs. La distinction entre les familles est faite par le nombre de monocouche d’épaisseur des boîtes qui sont beaucoup plus larges que hautes. Une revue de littérature retrace les principaux mécanismes de relaxation et de fuite des excitons dans les systèmes. Ensuite, différents modèles portant sur la fuite thermique des excitons des BQs sont comparés. Les types de caractérisations déjà produites et les spécifications des croissances des échantillons sont présentés. L’approche adoptée pour ce mémoire a été de caractériser temporellement la dynamique des BQs avec des mesures d’absorbtion transitoire et de photoluminescence résolue en temps (PLRT) par addition de fréquences. L’expérience d’absorption transitoire n’a pas fait ressortir de résultats très probants, mais elle est expliquée en détails. Les mesures de PLRT ont permis de suivre en température le temps de vie effectif des excitons dans des familles de BQs. Ensuite, avec un modèle de bilan détaillé, qui a été bien explicité, il a été possible d’identifier le rôle de la M et de la CM dans la relaxation et la fuite des excitons dans les BQs. Les ajustements montrent plus précisément que la fuite de porteurs dans les BQs se fait sous la forme de paires d’électrons-trous corrélées.

L’extraction de phrases en relation de traduction dans Wikipédia

Afin d'enrichir les données de corpus bilingues parallèles, il peut être judicieux de travailler avec des corpus dits comparables. En effet dans ce type de corpus, même si les documents dans la langue cible ne sont pas l'exacte traduction de ceux dans la langue source, on peut y retrouver des mots ou des phrases en relation de traduction. L'encyclopédie libre Wikipédia constitue un corpus comparable multilingue de plusieurs millions de documents. Notre travail consiste à trouver une méthode générale et endogène permettant d'extraire un maximum de phrases parallèles. Nous travaillons avec le couple de langues français-anglais mais notre méthode, qui n'utilise aucune ressource bilingue extérieure, peut s'appliquer à tout autre couple de langues. Elle se décompose en deux étapes. La première consiste à détecter les paires d’articles qui ont le plus de chance de contenir des traductions. Nous utilisons pour cela un réseau de neurones entraîné sur un petit ensemble de données constitué d'articles alignés au niveau des phrases. La deuxième étape effectue la sélection des paires de phrases grâce à un autre réseau de neurones dont les sorties sont alors réinterprétées par un algorithme d'optimisation combinatoire et une heuristique d'extension. L'ajout des quelques 560~000 paires de phrases extraites de Wikipédia au corpus d'entraînement d'un système de traduction automatique statistique de référence permet d'améliorer la qualité des traductions produites. Nous mettons les données alignées et le corpus extrait à la disposition de la communauté scientifique.