Search

Au cours des dernières décennies, plusieurs générations de réseaux cellulaires se sont succédé pour répondre au mieux aux exigences des applications mobiles émergentes et aux défis de la rareté du spectre radio. Différentes technologies telles que la communication à ondes millimétriques (mm- Wave), le déploiement des réseaux hétérogènes et des réseaux à bandes multiples sont des solutions prometteuses pour les futurs réseaux cellulaires. Dans cette thèse, nous proposons des algorithmes efficaces d’allocation de ressources et d’association des utilisateurs aux stations de base pour les réseaux cellulaires à bandes multiples de prochaines générations. Dans le premier chapitre, nous introduisons de manière générale le projet de thèse en abordant les motivations, les problématiques, les contributions ainsi que la méthodologie adoptée. Dans le deuxième chapitre, nous étudions le problème conjoint d’association des utilisateurs et d’allocation des créneaux temporels. Chaque utilisateur ne peut être associé qu’à une seule station de base utilisant des fréquences inférieures à 6 GHz (sub-6 GHz) ou des fréquences millimétriques (mmWave), et chaque station de base ne peut associer qu’un nombre limité d’utilisateurs. L’objectif est de maximiser le nombre d’utilisateurs associés tout en garantissant un débit de données requis par utilisateur. Nous commençons par la formulation mathématique du problème comme un programme linéaire en nombres entiers, puis nous prouvons son appartenance à la classe des problèmes NP-difficile. Nous proposons un algorithme glouton centralisé et un autre distribué évolutif basé sur l’apprentissage automatique par renforcement. Dans le troisième chapitre, nous étudions le problème conjoint d’association des utilisateurs aux stations de base, d’allocation de puissance, d’affectation des sous-canaux et de la technique d’accès multiple. Nous considérons un réseau cellulaire utilisant la bande de fréquences sub-6 GHz et la bande de fréquences mmWave. Ainsi, les deux techniques d’accès multiple orthogonal et non orthogonal sont utilisées. La fonction objectif est d’optimiser le débit de données tout en respectant les exigences d’un débit minimum par utilisateur et les contraintes de puissance. Nous prouvons que le problème est NP-difficile par restriction et nous proposons des solutions algorithmiques. Tout d’abord, un algorithme glouton ainsi qu’une métaheuristique sont détaillés. Puis, nous proposons deux autres algorithmes basés sur la technique d’apprentissage automatique par renforcement profond. Ces algorithmes sont ensuite évalués et comparés. Dans le quatrième chapitre, nous considérons un réseau cellulaire utilisant trois bandes de fréquences sub-6 GHz, mmWave et térahertz et nous étudions le problème d’optimisation conjointe d’allocation de ressources et d’association des utilisateurs aux stations de base. Une nouvelle mesure d’efficacité énergétique qui quantifie le nombre d’utilisateurs satisfaits par unité de puissance est considérée. L’objectif est de maximiser l’efficacité énergétique du système tout en respectant les contraintes du système et de qualité de service. Le problème conjoint d’association des utilisateurs aux stations de base, d’allocation des canaux et de puissance est formulé comme un programme non linéaire partiellement en nombres entiers. Nous montrons que le problème appartient à la classe des problèmes NP-difficile et nous proposons des solutions algorithmiques peu complexes et évolutives. La première solution consiste à diviser le problème en deux sous-problèmes pour le résoudre de manière itérative. Tout d’abord, nous résolvons le sous-problème d’association des utilisateurs aux stations de base et d’attribution des canaux. Ensuite, nous résolvons le sous-problème d’allocation de puissance. Nous proposons aussi une solution multiagent basée sur l’apprentissage par renforcement profond. Chaque utilisateur est un agent qui apprend la meilleure association indépendamment des autres utilisateurs en maximisant son score. Nous présentons des résultats de simulation Monte-Carlo de chaque problème étudié afin d’illustrer les performances des solutions proposées. _____________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : réseaux cellulaires à bandes multiples, ondes millimétriques, fréquences térahertz, allocation de ressources, association des utilisateurs aux stations de base, techniques d’accès multiples, NOMA, efficacité énergétique, solutions algorithmiques, apprentissage par renforcement profond, NP-difficulté, algorithmes gloutons

La présente recherche s’inscrit dans le cadre du traitement automatique du langage naturel. Dans ce travail, nous nous intéresserons aux résumés automatiques de textes en portant une attention particulière à la famille de méthodes de résumé automatique par compréhension. L’objectif principal de cette recherche était de concevoir et d'implémenter deux approches de résumé automatique par extraction et par abstraction ainsi qu’un protocole d’évaluation de résumés automatiques de texte par compréhension. Le volet informatique de notre recherche présente de manière détaillée les approches proposées pour le résumé automatique de texte. En ce qui concerne le volet cognitif, nous accordons une attention particulière aux théories de compréhension de textes issues de la psychologie cognitive. L’hypothèse générale qui sous-tend notre recherche est qu’un modèle informatique de résumé automatique de textes ou d’évaluation de résumé automatique doit être inspiré de l’activité résumante chez le sujet humain. _____________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Résumés automatiques de textes par compréhension, Résumés automatiques par extraction et abstraction, Méthodes d’évaluation des résumés automatiques. Modèles issus de la psychologie cognitive pour la compréhension de textes.

Les réseaux cellulaires ont connu durant les dernières décennies des avancées technologiques considérables. Plusieurs générations de ces réseaux se sont succédé, et chacune offrait une gamme de plus en plus large d'applications de haute performance aux utilisateurs. La première et la deuxième générations, plus connues sous les sigles 1G et 2G, étaient spécialement conçues pour le transport de la voix. Les générations récentes sont dotées de la capacité de transporter des données; permettant ainsi un accès continu à Internet. Les exigences de la prochaine génération portent encore la barre plus haut avec un débit de transmission plus élevé (allant jusqu'à des dizaine de gigabits par seconde), un délai de latence plus réduit (moins d'une milliseconde) ainsi qu'une couverture et une disponibilité quasi-complète. Afin d'atteindre ces exigences, la prochaine génération adoptera plusieurs nouvelles technologies, telles que les antennes multiples à large échelle, la communication millimétrique, et les réseaux cellulaires denses hétérogènes (appelés Dense Cellular Networks ou simplement DCNs). Les réseaux DCNs se caractérisent par le déploiement de plusieurs stations de base de différentes caractéristiques (tailles, puissance, prix, etc.) avec des distances réduites entre elles. Dans cette thèse, nous proposons des algorithmes d'allocation de ressources dans les réseaux DCNs de la prochaine génération. Spécifiquement, nous étudions le problème d’ordonnancement et d'association des utilisateurs aux différentes stations de base ainsi que l'allocation des fréquences. Nous nous intéressons à (i) étudier la complexité computationnelle de ce problème en caractérisant sa NP-difficulté et (ii) proposer des algorithmes d'allocation de ressources avec des performances théoriques dans le pire cas (comme des algorithmes d'approximations ou des algorithmes compétitifs). Dans la première partie de cette thèse, nous étudions le problème d'association des utilisateurs aux stations de base sous les contraintes d'interférence et de qualité de service avec l'objectif de maximiser le nombre d'utilisateurs associés. Ce problème, à nos connaissances, n'a pas été étudié par d'autres chercheurs. Nous montrons la NP-difficulté du problème et nous proposons un algorithme d'approximation permettant de le résoudre efficacement. Ensuite, nous modélisons ce problème en utilisant la théorie des jeux. Ainsi, nous proposons un algorithme d'apprentissage totalement distribué. En second lieu, nous étudions le problème conjoint d'association des utilisateurs avec activation et désactivation des stations de base. L’objectif est de minimiser la consommation énergétique sous les contraintes de qualité de service des utilisateurs. Nous étudions la faisabilité de ce problème et nous montrons qu'il s'agit d'un problème NP-difficile. Nous proposons ensuite différentes solutions algorithmiques pour différents cas de qualité de service exigée. Dans la troisième partie de cette thèse, nous étudions le problème conjoint d'ordonnancement, d'association des utilisateurs et d'allocation de fréquences avec ou sans la récolte d'énergie. L’objectif est de maximiser le nombre d'utilisateurs satisfaits. Ce problème est résolu sous les contraintes de qualité de service et de délai contraignant. Dans le cas sans récolte d'énergie, nous étudions un cas spécial de ce problème et nous proposons un algorithme optimal pour le résoudre. Après, nous démontrons la NP-difficulté du problème dans le cas général et nous proposons un algorithme d'approximation avec un facteur d'approximation constant. Dans le cas avec récolte d'énergie, nous étudions la NP-difficulté du problème dans différents cas. Lorsque le problème appartient à la classe P, nous proposons un algorithme optimal pour le résoudre. Lorsque le problème est NP-difficile, nous proposons des algorithmes d'approximation ainsi que des algorithmes heuristiques. Ensuite, nous résolvons ce problème dans un scénario online. Nous proposons des algorithmes online compétitifs ainsi qu'un algorithme d'apprentissage incrémental et nous démontrons que son regret est sous-linéaire. Pour chaque problème étudié dans ce projet, nous présentons des résultats de simulations Monte Carlo afin d'illustrer les performances de nos solutions proposées. La dernière partie de cette thèse conclut le travail et présente différentes pistes de recherche pour le futur. _____________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Réseaux cellulaires denses hétérogènes, allocation de ressources, ordonnancement, association des utilisateurs, allocation de fréquences, récolte d'énergie, activation et désactivation des stations de base, interférence, capacité, délai, dates limites, complexité asymptotique, NP-difficulté, algorithmes optimaux, algorithmes gloutons, algorithmes compétitifs, algorithmes d'approximation, algorithmes d'apprentissage.

Les arbres phylogénétiques (c.-à-d., arbres additifs ou X-arbres) contiennent des informations importantes caractérisant l'évolution spécifique des familles de gènes étudiées. Cependant, un arbre consensus d'espèces fiable ne peut pas être inféré à partir d'un alignement de séquences multiples d'une famille de gènes unique ou de la concaténation des alignements correspondant à des familles de gènes ayant des histoires évolutives différentes. Ces histoires évolutives peuvent différer, par exemple, à cause des transferts horizontaux subis par certains gènes ou à cause de l'ancienne duplication génique qui provoque l'émergence de paralogues dans un génome. De nombreuses méthodes ont été proposées pour déduire un arbre consensus unique pour un ensemble d'arbres phylogénétiques donné. L'application de ces méthodes classiques peut donc conduire à la perte d'information sur les histoires évolutives spécifiques qui caractérisent certaines familles de gènes ou certains groupes de familles de gènes. Ainsi, la problématique d'inférence des arbres consensus multiples devient pertinente. Dans cette thèse de doctorat, nous présentons de nouveaux algorithmes permettant de raffiner le processus d'inférence d'arbres consensus et de super-arbres obtenus par regroupement d'arbres phylogénétiques. L'avantage de notre approche par rapport aux approches classiques, qui retournent comme solution un arbre consensus ou un super-arbre unique, est qu'elle permet de déterminer un ou plusieurs arbres consensus ou super-arbres représentant au mieux le groupe d'arbres phylogénétiques fournis en entrée. Nous montrons comment les algorithmes de regroupement classiques, les k-moyennes et les k-médoïdes, peuvent être modifiés pour partitionner des arbres phylogénétiques définis sur un même ensemble de feuilles (problématique de l'arbre consensus) ou sur des ensembles de feuilles différents, mais mutuellement chevauchants (problématique de super-arbre). Dans notre étude, la distance topologique de Robinson et Foulds (classique et normalisée) sera utilisée pour comparer des arbres phylogénétiques. Les trois nouveautés majeures de cette thèse sont les suivantes : 1) le développement des algorithmes rapides de construction d'arbres consensus et de super-arbres multiples; 2) l'adaptation des indices de validité des clusters populaires (c.-à-d., l'indice de Calinski-Harabasz, l'indice Silhouette et la statistique Gap) pour leur utilisation dans les algorithmes de regroupement d'arbres phylogénétiques; 3) l'application des algorithmes proposés aux données réelles montrant comment ils peuvent être utilisés pour détecter des transferts horizontaux de gènes ou des événements d'hybridation. _____________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : arbre phylogénétique, arbre consensus, super-arbre, distance de Robinson et Foulds, algorithme des k-moyennes, algorithme des k-médoïdes, partitionnement d'arbres

La théorie de l'évolution de Darwin, puis la découverte de l'ADN (acide désoxyribonucléique) dans les années 1950 ont donné naissance à la phylogénie moléculaire, dont le but principal est de construire des arbres d'espèces à partir de données moléculaires (essentiellement de l'ADN ou des protéines). De nombreux algorithmes ont été développés dans ce contexte. Les méthodes de distances sont les plus rapides, tandis que les méthodes basées sur les caractères donnent généralement de meilleurs résultats mais nécessitent des temps de calcul beaucoup plus importants. Par ailleurs, plusieurs phénomènes évolutifs fondamentaux, comme l'hybridation, ne peuvent pas être représentés par un arbre phylogénétique. Il faut alors considérer des réseaux phylogénétiques. Plusieurs méthodes d'inférence de tels réseaux ont été introduites depuis une vingtaine d'années. La plupart d'entre elles produisent des réseaux implicites, qui peuvent s'avérer très difficiles à interpréter. Notre premier projet a ainsi consisté à développer un algorithme pour inférer un réseau d'hybridation explicite à partir d'une matrice de distances entre un certain nombre d'espèces. Des simulations et des tests sur des données réelles nous ont permis de mettre en lumière l'efficacité de notre nouvel algorithme. Notre programme est disponible en ligne pour l'ensemble de la communauté scientifique. Dans un deuxième temps, nous avons appliqué notre nouvelle méthodologie dans le cadre de la biolinguistique. L'évolution des langues peut en effet être représentée sous la forme d'un arbre ou d'un réseau, et plusieurs études ont démontré la pertinence d'appliquer des méthodes d'inférence phylogénétique à des données linguistiques. Nous avons ainsi reconstruit un réseau d'hybridation explicite représentant l'histoire de 84 langues indo-européennes, et nous avons comparé ce réseau à ceux obtenus à partir d'autres méthodes. Enfin, dans notre troisième projet, nous avons développé une méthode d'inférence de réseaux phylogénétiques basée sur les caractères. Notre algorithme prend en entrée une séquence binaire (correspondant, par exemple, à la présence ou l'absence de certains gènes) pour chaque espèce considérée, et reconstruit un réseau phylogénétique explicite, dont les feuilles sont en correspondance avec les espèces considérées. Plusieurs simulations ont montré que cet algorithme donne de meilleurs résultats que notre méthode de distances, même si les temps de calculs sont généralement plus longs. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Réseaux phylogénétiques, hybridation, neighbor-joining, maximum de vraisemblance, biolinguistique.

Cette thèse étudie diverses notions en géométrie discrète d'un point de vue algorithmique. Plus particulièrement, elle fournit un cadre d'algorithmes efficaces afin de résoudre des problèmes concernant les figures discrètes en se basant uniquement sur l'étude du contour de ces dernières. Les résultats obtenus s'appuient principalement sur la théorie des graphes et leurs représentations, ainsi que sur la combinatoire des mots. La première théorie permet d'aborder les problèmes étudiés sous un angle géométrique, tandis que la seconde fournit un modèle simple et efficace pour le traitement et l'analyse de chemins et de figures discrètes. Les résultats développés au fil du texte appartiennent principalement aux domaines de la théorie des graphes, de la combinatoire des mots et de l'informatique théorique. En plus de ces contributions théoriques, ils trouvent aussi écho dans plusieurs autres domaines liés aux technologies de l'information, notamment en traitement d'images numériques ou, encore, en cristallographie. Ce document s'articule autour de trois sujets principaux, tous liés de près ou de loin à la notion centrale de polyominos, c'est-à-dire un ensemble de pixels connexes dans le plan discret Z2. Dans un premier temps, nous introduisons le concept de réseau parallélogramme, permettant ainsi d'établir de nouveaux résultats de nature algébrique sur un type particulier de morphisme appelé morphisme parallélogramme. Ensuite, nous étudions la notion de polyomino premier. Notamment, nous fournissons un algorithme polynomial de factorisation. Finalement, nous étudions diverses opérations géométriques fondamentales sur les polyominos. Notons que tous les algorithmes présentés ont été implémentés et testés sur plusieurs exemples. Ce travail de fin d'études constitue un apport aux mathématiques discrètes par l'établissement de nouveaux résultats. Parmi ceux-ci, mentionnons un algorithme linéaire pour le calcul des enveloppes externe et convexe de tout chemin discret de Z2 ainsi que des algorithmes linéaires afin de calculer l'union, l'intersection et la différence de polyominos. _______________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : géométrie discrète, combinatoire des mots, topologie des graphes, algorithmique, polyominos

La biologie évolutive est régie par des forces écologiques correspondant à des échelles géographiques et temporelles différentes. L'interrelation hôte-pathogène constitue une des principales forces évolutives, menant à la croissance de la variabilité génétique. Dans cette thèse, nous présentons d'abord un nouveau modèle permettant de retrouver des régions génomiques fonctionnelles en se basant sur la variabilité des séquences ainsi que sur une analyse de regroupement d'espèces faite selon des critères booléens de pathogénicité. Les méthodes et les fonctions de regroupement qui en découlent ont été appliquées à des jeux de données réelles impliquant la carcinogénicité et l'invasivité des espèces. Ces méthodes et fonctions doivent varier dépendamment de la combinaison des mécanismes évolutionnaires (sélection positive et lignée spécifique) de même que des types de regroupement variés (monophylétique et polyphylétique). Nous utilisons l'index de Rand ajusté pour valider les résultats. Par la suite, nous étudions sur une plus grande échelle le phénomène du transfert horizontal de gènes, complet et partiel, chez les procaryotes. Cette analyse détaillée est effectuée sur plusieurs niveaux taxonomiques, génétiques et écologiques pour permettre d'estimer statistiquement l'ampleur de l'acquisition du matériel génétique tout au long de l'histoire évolutive des procaryotes. Finalement, nous décrivons une nouvelle méthode rapide de détection des transferts horizontaux de gènes complets qui est basée sur des fonctions de regroupement, existantes et nouvelles, accompagnée de la procédure de validation utilisant les p-values. _____________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : analyse de regroupement, arbre phylogénétique, bipartition, carcinogénicité, détection de régions fonctionnelles, invasivité, recombinaison, transfert horizontal de gènes, variabilité génétique.

La technologie moderne permet d'avoir des systèmes sur puce de plus en plus denses et comportant de plus en plus de processeurs, menant ainsi à une grande flexibilité logicielle pour la conception et la réalisation d'applications. Les systèmes doivent pouvoir utiliser les capacités des puces pour l'exécution de tâches applicatives diverses, ce qui pose le problème de l'ordonnancement des tâches. La recherche dans ce domaine a produit une quantité phénoménale et diversifiée de connaissances. Notre travail porte sur l'extraction et la représentation efficace des connaissances pour les concepteurs qui utilisent les puces et les créateurs d'algorithmes d'ordonnancement. Nous proposons d'utiliser l'analyse formelle de concept et les techniques du forage de données pour l'extraction de connaissances sur les algorithmes d'ordonnancement, en partant de diverses sources telles les bancs d'essai et les caractéristiques intrinsèques des algorithmes. Notre recherche montre comment extraire efficacement les informations de performance dans un ensemble d'applications, permettant ainsi la sélection efficace du meilleur algorithme d'ordonnancement pour l'application de l'usager. L'extraction de l'information se fait sans outil statistique, évitant ainsi de tirer des conclusions générales qui peuvent être inappropriées pour le problème spécifique de l'usager. La représentation des connaissances est faite sur plusieurs niveaux et se base sur les patrons logiciels et les langages-patrons. Le tout est intégré dans une plateforme de connaissance qui peut être utilisée pour concevoir plus rapidement et efficacement de nouveaux algorithmes d'ordonnancement et des applications. L'usage de l'analyse formelle de concepts permet à la méthodologie présentée d'offrir une représentation structurée des connaissances sur l'ordonnancement de tâches. Dans un premier temps, les connaissances brutes sont transformées en règles d'associations entre les attributs applicatifs et des métriques de performance pour l'ordonnancement des tâches. Ceci permet non seulement la manipulation formelle du savoir obtenu, mais aussi d'accroître la connaissance du concepteur au sujet d'ordonnancement précis. Une méthode pour cartographier des connaissances obtenues est proposée pour une visualisation rapide. Nous montrons aussi comment automatiser l'extraction et l'exploitation du savoir à l'aide d'une représentation en langage-patron. En particulier, nous présentons une plateforme de documentation et des façons de produire des patrons et de les regrouper pour aider l'architecte logiciel dans l'utilisation des algorithmes d'ordonnancement. En plus, nous exposons différentes perspectives qui combinent les patrons, les règles associatives et l'extraction de données. Finalement, une nouvelle classe d'algorithmes d'ordonnancement est présentée, basée sur le forage des règles d'association pour proposer des algorithmes à la performance améliorée. Notre approche aide les concepteurs à développer leurs applications et les experts à améliorer et créer des méthodes d'ordonnancement. De plus, elle peut servir à intégrer des outils documentaires dans le cycle de design. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Extraction, analyse formelle, connaissance, multi-cœur, patrons, grammaire, forage, ordonnancement.