Dans cette thèse nous proposons un nouveau modèle statistique pour l'analyse des problèmes de segmentation/classification dont l'objectif <br /> est de partitionner des données en zones homogènes, et de regrouper ces zones en un nombre fini de classes. Les problèmes de segmentation/classification sont traditionnellement étudiés à l'aide <br /> des modèles de chaînes de Markov cachées. Nous proposons un modèle alternatif qui combine un modèle de segmentation et un modèle de mélange.<br /> <br /> Nous construisons notre modèle dans le cas gaussien et nous proposons une généralisation à des variables discrètes dépendantes. Les paramètres de ce modèle sont estimés par maximum de vraisemblance à l'aide d'un algorithme hybride fondé sur la programmation dynamique et sur l'algorithme EM. Nous abordons un nouveau problème de sélection de modèle qui est la sélection simultanée du nombre de groupes et du nombre de segments et proposons une heuristique pour ce choix. <br /> <br /> Notre modèle est appliqué à l'analyse de données issues d'une nouvelle technologie, les microarrays CGH (Comparative Genomic Hybridization). Cette technique permet de compter le nombre de milliers de gènes le long du génome en une seule expérience. L'application de notre méthode à ces données permet de localiser des zones délétées ou amplifiées le long des chromosomes. Nous proposons également une application à l'analyse des séquences d'ADN pour l'identification de régions homogènes en terme de composition en nucléotides.

La crise énergétique marquée par une flambée des prix du pétrole et les impératifs d'un développement durable font des énergies renouvelables une alternative qui suscitent aujourd'hui l'intérêt de plusieurs équipes de recherches. Le Sénégal, pays subsaharien, non producteur de pétrole n'est pas épargné par cette crise. Celle-ci se traduit par, une faible couverture du pays (en particulier les zones rurales) par le réseau électrique national. Pour faire face à cela, la nouvelle orientation en matière de politique énergétique met l'accent sur l'utilisation des énergies renouvelables notamment, le solaire et l'éolienne. L'objectif principal de cette thèse est de dégager une méthodologie de conception d'un site isolé de production d'énergie électrique à partir des énergies alternatives. Il s'agit à partir des caractéristiques d'un site (ressources d'énergie disponibles, besoins énergétiques) de :- mettre en place une démarche qui permette le choix d'une architecture du réseau et de dimensionner de façon optimale l'ensemble des constituants du réseau (machines, sources et dispositifs de stockage) en tenant compte de toutes les contraintes- concevoir un dispositif de commande des composantes et de gestion des flux d'énergie Cette thèse comprend trois chapitres :- Chapitre 1 : pose la problématique de l'énergie au Sénégal. L'organisation institutionnelle du sous-secteur de l'électricité, les réalisations et les projets en cours sont présentés. Aussi, une étude sur les architectures de micro-réseaux est faite. - Chapitre 2 : traite des outils et logiciels. Une étude comparative des principaux logiciels d'analyse, de conception et simulation des micro-réseaux est réalisée. L'ensemble des composants de notre système ont été modélisées. Les méthodes d'optimisation et des outils de représentation graphique (Bond Graph, GIC et REM) des systèmes ont été présentés. Une enquête menée et une recherche bibliographique nous ont permis d'évaluer le potentiel énergétique du site et les besoins des populations.- Chapitre 3 : il s'agit de l'application de notre outil sur un site isolé identifié au Sénégal (MBoro/Mer). L'optimisation à travers la fonction objectif coût annualisée du système (ACS) nous a permis de dimensionner de façon optimale notre système. Aussi la commande du système avec la Représentation Energétique Macroscopique (REM) a été conçue.Pour la suite du travail, il faudrait envisager une prise en charge des problèmes de disponibilité du système à travers une surveillance et une supervision du dispositif. Le volet socio-économique aussi est à intégrer dans le futur afin de satisfaire l'évolution des besoins et des habitudes des populations.

L'augmentation grandissante du trafic a??rien rend le travail des contr??leurs a??riens de plus en plus ardu, sp??cialement en ce qui a trait aux t??ches de r??solution de conflits et de s??quen??age d'avions en arriv??e. L'automatisation de la r??solution de conflits et du s??quen??age reste toujours un probl??me ouvert aujourd'hui. L'automatisation de ces deux probl??mes permettrait d'une part de mieux mod??liser le comportement des contr??leurs a??riens dans un simulateur de vol, ou d'am??liorer les outils de gestion du trafic a??rien. Les caract??ristiques combinatoires de ces probl??mes conduisent ?? l'utilisation de techniques num??riques stochastiques, plus sp??cifiquement des algorithmes ??volutionnaires. De plus, les nombreux param??tres intervenant dans une situation de gestion de trafic a??rien incitent ?? l'utilisation d'algorithmes multiobjectif. Dans un premier temps, un algorithme g??n??tique multiobjectif (SPEA-MOD) et un algorithme de colonies de particules (PSO-MO) ??galement multiobjectif ont ??t?? d??velopp??s. Ces deux algorithmes ont ??t?? compar??s ?? des probl??mes multiobjectif contraints et non-contraints. Les r??sultats ont montr?? que SPEA-MOD et PSO-MO sont en g??n??ral sup??rieurs ?? ce que l'on rapporte dans la litt??rature. Dans un deuxi??me temps, les deux algorithmes ont r??solu plusieurs situations conflictuelles de la phase de vol en route (r??gime de croisi??re). Les instructions fournies par les algorithmes peuvent ??tre en deux ou en trois dimensions. Les objectifs et les contraintes repr??sentent des param??tres tels que la minimisation d'instructions fournies aux avions et une s??paration minimale entre les avions. De ces solutions num??riques r??alis??es, l'algorithme SPEA-MOD s'est av??r?? particuli??rement efficace ?? des probl??mes fortement contraints. Une mod??lisation novatrice de trajectoires complexes a permis de r??soudre des probl??mes de s??quen??age d'avions dans la phase d'arriv??e. Le s??quen??age d'avions en arriv??e par un algorithme ??volutionnaire fut r??alis?? pour la premi??re fois dans le cadre de cette recherche. Cette mod??lisation a ??galement rendu possible la r??solution de conflits de deux flux d'avions se croisant.

Le vieillissement de la population est un probl??me qui touche de plus en plus le monde occidental et a pour cons??quence de rendre difficile le maintien ?? domicile des personnes ??g??es, ??tant donn?? les co??ts engendr??s et le manque de personnel soignant. D'un autre c??t??, la pr??sence des technologies dans les domiciles devient r??pandue et ce, ?? des prix abordables. On est d??sormais capable de r??cup??rer facilement des informations sur ce qui se passe ?? l'int??rieur de la maison et ainsi agir en cons??quence. Le maintien ?? domicile devient alors possible en offrant une assistance aux personnes ??g??es qui soit port??e par la technologie, afin de les aider ?? r??aliser leurs activit??s de la vie quotidienne. ?? l'aide d'un calendrier ??lectronique dans lequel seront not??es toutes les activit??s ?? r??aliser dans la journ??e, on est en mesure d'utiliser les donn??es fournies par l'appartement pour v??rifier qu'elles ont bien ??t?? r??alis??es, et ainsi offrir des rappels efficaces pour ces activit??s. C'est vers cette probl??matique que se tourne ce m??moire en offrant un outil pouvant utiliser et interpr??ter les informations provenant de l'int??rieur d'un habitat, combin??es ?? celles venant d'un calendrier ??lectronique, dans le but d'aider ?? la r??alisation des t??ches de la vie quotidienne. Cet outil est compos?? de deux programmes principaux: le calendrier ??lectronique et le programme de reconnaissance d'activit??, les deux fonctionnant en collaboration. Ce m??moire pr??sente en premier lieu l'informatique ubiquitaire, les moyens de rappel existants ainsi que les diff??rentes m??thodes pour faire de la reconnaissance d'activit?? dans un appartement intelligent. Suit une description du calendrier ??lectronique permettant aux personnes ??g??es d'entrer correctement leurs activit??s ?? rappeler. Ensuite est d??crit le programme de reconnaissance d'activit??, qui interpr??te les ??v??nements des capteurs pour reconna??tre les activit??s r??alis??es. Le chapitre suivant traite de la collaboration entre le calendrier et le programme de reconnaissance d'activit?? afin qu'ils soient utilisables dans l'appartement. Une exp??rimentation r??alis??e dans l'appartement intelligent du DOMUS cherche ?? fournir une preuve de concept du rappel d'activit?? en fonction de ce qui se passe dans l'appartement.

Thèse diffusée initialement dans le cadre d'un projet pilote des Presses de l'Université de Montréal/Centre d'édition numérique UdeM (1997-2008) avec l'autorisation de l'auteur.

Initialement con¸cu pour d'echarger le CPU des tˆaches de rendu graphique, le GPU estdevenu une architecture massivement parall'ele adapt'ee au traitement de donn'ees volumineuses.Alors qu'il occupe une part de march'e importante dans le Calcul Haute Performance, uned'emarche d'Ad'equation Algorithme Architecture est n'eanmoins requise pour impl'ementerefficacement un algorithme sur GPU.La contribution de cette th'ese est double. Dans un premier temps, nous pr'esentons legain significatif apport'e par l'impl'ementation optimis'ee d'un algorithme de granulom'etrie(l'ordre de grandeur passe de l'heure 'a la minute pour un volume de 10243 voxels). Un mod'eleanalytique permettant d''etablir les variations de performance de l'application de granulom'etriesur GPU a 'egalement 'et'e d'efini et pourrait ˆetre 'etendu 'a d'autres algorithmes r'eguliers.Dans un second temps, un outil facilitant le d'eploiement d'applications de Traitementdu Signal et de l'Image sur cluster multi-GPU a 'et'e d'evelopp'e. Pour cela, le champ d'actiondu programmeur est r'eduit au d'ecoupage du programme en tˆaches et 'a leur mapping sur les'el'ements de calcul (GPP ou GPU). L'am'elioration notable du d'ebit sortant d'une applicationstreaming de calcul de carte de saillence visuelle a d'emontr'e l'efficacit'e de notre outil pourl'impl'ementation d'une solution sur cluster multi-GPU. Afin de permettre un 'equilibrage decharge dynamique, une m'ethode de migration de tˆaches a 'egalement 'et'e incorpor'ee 'a l'outil.

Dans ce mémoire de thèse, nous nous intéressons à l'affectation des vols aux avions dans une compagnie aérienne. Notre objectif est de proposer des plannings de vols qui prennent en compte des contraintes de maintenance, en utilisant des algorithmes efficaces. Au cours de nos recherches, nous avons ramené le problème de rotation des avions à des cas particuliers du problème de partitionnement d'un graphe orienté acyclique par des chemins disjoints. Nous avons fait des études de complexité pour différents cas et nous avons proposé des algorithmes de liste, un recuit simulé et une approche heuristique basée sur la génération de colonnes. Nous avons finalement comparé la performance de ces méthodes sur différentes instances.

L'alignement de macromolécules biologiques comme les protéines, l'ADN ou encore l'ARN est une problématique biologique et bio-informatique qui a pour but de révéler une partie des mystères du fonctionnement des cellules, constituants des êtres vivants. Les ARN non-codant sont des macromolécules intervenant dans le métabolisme de tout être vivant et les deux problématiques majeurs les concernant sont: la prédiction de leur structure pour mieux comprendre leur fonctionnement et leur détection dans des bases de données ou des génomes. L'une des approches: l'alignement structure-séquence d'ARN, répond à ces deux problématiques. Le problème d'alignement structure-séquence consiste à aligner une structure connue d'un premier ARN avec la séquence d'un deuxième ARN.La structure est représentée sous la forme d'un graphe ou de façon équivalente sous la forme d'une séquence arc-annotées et la séquence représente la suite des nucléotides de l'ARN.Pour résoudre ce problème, nous cherchons à optimiser l'alignement selon une fonction de coût. C'est donc un problème d'optimisation, qui malheureusement se révèle NP-Difficile.En conséquence différents travaux définissent des classes d'instances réduites pour lesquelles ils proposent des algorithmes spécifiques mais à complexités polynomiales.Les travaux de ma thèse unifient et la généralisent les approches précédentes par la construction d'un algorithme à complexité paramétrée non spécifique à une classe d'instances. En utilisant cet algorithme, il est possible de résoudre le problème d'alignement structure-séquence pour toutes les instances possibles, et aussi efficacement que les précédentes approches sur leur domaine de résolution respectif. Cet algorithme utilise une technique empruntée à la théorie des graphes: la décomposition arborescente, c'est-à-dire qu'il transforme la structure donnée en une décomposition arborescente et c'est ensuite cette décomposition qui est alignée avec la séquence donnée. L'alignement entre une décomposition arborescente et une séquence se fait par programmation dynamique.Sa mise en place a nécessité une reformulation du problème ainsi qu'une modification importante de l'utilisation classique de la programmation dynamique pour les décompositions arborescentes. Au final, cela conduit à un algorithme paramétré dont le paramètre est entièrement lié à la décomposition arborescente. La construction des décompositions arborescentes pour lesquelles l'alignement s'effectuera plus le efficacement possible est malheureusement un problème lui aussi NP-Difficile. Néanmoins, nous avons créé une heuristique de construction de décompositions adaptée aux structures d'ARN.Nous avons alors défini des nouvelles classes de structures pour lesquelles notre algorithme (décomposition et alignement) possède une faible complexité. Ces classes incluent notamment toutes les autres classes précédemment définies et la complexité de notre algorithme est au moins aussi faible que celles des algorithmes spécifiques sur leurs classes de structures respectives. Ces classes de structures représentent la majorité des structures connues et contiennent de nombreux éléments importants jusqu'alors non pris en compte (tel que les motifs tertiaires d'ARN). Le problème de l'alignement structure-séquence tente de répondre aux problématiques de prédictions de structures et de recherche d'ARN. Néanmoins, la qualité des résultats obtenus par sa résolution dépendent de la fonction de coût utilisée. Durant ma thèse j'ai commencé la mise place de la construction par apprentissage d'une nouvelle fonction de coût, adaptée aux nouvelles classes de structures que nous avons défini. Enfin de par la nature de l'algorithme, le travail réalisé permet des améliorations non négligeables, en terme de qualité des résultats et de rapidité de calcul comme la recherche de solution sous-optimales ou l'utilisation de l'algorithme au sein d'heuristiques dérivées d'heuristiques classiques.

Dans ce mémoire, j'examine différents aspects d'un objet simple mais omniprésent en informatique: la séquence de symboles (appelée selon le contexte mot ou chaîne de caractères). La notion de mot est au carrefour de domaines comme la théorie de l'information et la théorie des langages. S'il est simple, il reste fondamental: nous n'avons, au plus bas niveau, que cela à disposition puisqu'il arrive toujours un moment où une donnée doit être encodée en symboles stockables en mémoire. La quantité d'information croissante de données mise à disposition et qu'on peut stocker, par exemple des génomes d'individus ou des documents numérisés, justifie que les algorithmes et les structures de données qui les manipulent soient optimisés. En conséquence, les besoins d'analyse se font sentir pour guider le choix et la conception des programmes qui manipulent ces données. L'analyse en moyenne est ici particulièrement adaptée puisque les données atteignent une variété et des volumes tellement importants que c'est le cas typique qui traduit le mieux la complexité et non pas le cas le pire. Cela évidemment pose le problème de la modélisation de données qui reste encore très épineux. En effet on souhaite deux choses contradictoires: un modèle au plus près des données, qui traduise vraiment leurs spécificités, mais aussi un modèle permettant de donner des résultats, c'est-à-dire de prédire les performances (et on comprend vite que le modèle doit donc rester relativement simple pour qu'il subsiste un espoir de le traiter!). Les méthodes sont le plus souvent celles de la combinatoire analytique et font appel à un objet mathématique, les séries génératrices, pour mener les analyses à bien.

L'analyse de données sismiques pour l'étude du sous-sol est un travail long et difficile qui demande beaucoup de connaissances a priori au géophysicien qui l'effectue. L'outil informatique permet d'accélérer ce travail par une mise en valeur des zones d'intérêt, formées de continuités (horizons) et discontinuites (failles, domes de sel ...). L'analyse par ondelettes est particulièrement adaptée à l'étude des continuités et discontinuités et permet, à l'aide d'ondelettes directionnelles, de détecter des fractures, problème extrêmement difficile. Nous présentons dans ce travail un exposé succint de la théorie des ondelettes suivi des différents algorithmes de la transformée en ondelettes ainsi que les problèmes de représentation d'une telle transformée. Nous introduisons la notion d'ondelette directionnelle, sensible aux discontinuités dans une direction donnée et étudions quelques-unes de ses propriétés. Divers applications aux images sismiques sont exposées. Une méthode de filtrage basée sur l'algorithme à trous pour l'amélioration du pointe d'horizons est présentée. L'utilisation de la transformée en ondelettes directionnelles aboutit, entre autres, à la détection de failles. Ceci peut être améliorer par l'utilisation d'un filtrage préalable adapté et la représentation angle-espace-échelle.