La complexité des données contenues dans les grandes bases de données a augmenté considérablement. Par conséquent, des opérations plus élaborées que les requêtes traditionnelles sont indispensable pour extraire toutes les informations requises de la base de données. L'intérêt de la communauté de base de données a particulièrement augmenté dans les recherches basées sur la similarité. Deux sortes de recherche de similarité bien connues sont la requête par intervalle (Rq) et par k-plus proches voisins (kNNq). Ces deux techniques, comme les requêtes traditionnelles, peuvent être accélérées par des structures d'indexation des Systèmes de Gestion de Base de Données (SGBDs).Une autre façon d'accélérer les requêtes est d'exécuter le procédé d'optimisation des requêtes. Dans ce procédé les données métriques sont recueillies et utilisées afin d'ajuster les paramètres des algorithmes de recherche lors de chaque exécution de la requête. Cependant, bien que l'intégration de la recherche de similarités dans le SGBD ait commencé à être étudiée en profondeur récemment, le procédé d'optimisation des requêtes a été développé et utilisé pour répondre à des requêtes traditionnelles. L'exécution des requêtes de similarité a tendance à présenter un coût informatique plus important que l'exécution des requêtes traditionnelles et ce même en utilisant des structures d'indexation efficaces. Deux stratégies peuvent être appliquées pour accélérer l'execution de quelques requêtes, et peuvent également être employées pour répondre aux requêtes de similarité. La première stratégie est la réécriture de requêtes basées sur les propriétés algébriques et les fonctions de coût. La deuxième stratégie est l'utilisation des facteurs externes de la requête, tels que la sémantique attendue par les usagers, pour réduire le nombre des résultats potentiels. Cette thèse vise à contribuer au développement des techniques afin d'améliorer le procédé d'optimisation des requêtes de similarité, tout en exploitant les propriétés algébriques et les restrictions sémantiques pour affiner les requêtes.

Ce mémoire a pour vocation de prouver aux membres du jury ma capacité à diriger des recherches. Il est organisé de la manière suivante : La première partie regroupe mon curriculum vitae, et une liste de publications. Le chapitre 2 est une présentation générale d'une partie des travaux que j'ai initié au cours de la dernière décennie. Dans un souci de cohérence d'ensemble je n'ai présenté que les travaux relatifs à la commande de systèmes (max,+) linéaires. Ils constituent le dénominateur commun aux trois thèses que j'ai encadrées. Ce chapitre inclut quelques nouveautés à l'attention du lecteur averti, notamment la synthèse d'un observateur d'état est introduite pour la première fois ici. Il se termine sur la présentation de quelques perspectives de recherche. La troisième partie regroupe quelques publications qui permettront au lecteur de retrouver les preuves des résultats énoncés dans le second chapitre.

Ce travail étudie l'apport de l'algèbre différentielle à deux problématiques principales de la robotique mobile à roues, la localisation et la navigation. La première problématique consiste à être capable de dire où le robot se situe dans son environnement. Nous supposons ici que nous possédons un certain nombre de points d'intérêt de l'espace dont les coordonnées dans cette espace sont connues. En fonction du nombre de points d'intérêt, il est possible ou non de localiser le robot. Cette notion de localisabilité est définie et étudiée dans le cadre algébrique. Nous montrons que ce cadre d'étude est plus intéressant que le cadre géométrique en ce sens que non seulement il permet l'étude de la localisabilité mais en plus il permet de construire des estimateurs d'états permettant de reconstruire la posture du robot. Cette étude est effectuée dans cinq cas d'études pour quatre des cinq classes de robots mobiles à roues. La deuxième problématique étudiée est celle de la navigation d'une flottille décentralisée de robots dans un environnement complexe. Ce travail présente une architecture pouvant être utilisée dans une large classe de problème et bénéficiant des avantages des approches discrètes et des approches continues. En effet, à haut niveau, un bloc stratégie spécifie l'objectif, les contraintes et leurs paramètres ainsi que la fonction coût utilisée, à bas niveau, une trajectoire est calculée afin de minimiser la fonction coût en respectant l'objectif et les contraintes du problème. Cette minimisation est faite sur un horizon glissant de manière à pouvoir prendre en compte des modifications de l'environnement ou de la mission en cours de navigation

Ce travail de recherche est consacré à l'élaboration des méthodes de traitement d'antenne multicapteur, multicomposante. Le traitement des signaux enregistrés par ce type d'antenne permet l'estimation de la direction d'arrivée et des paramètres de polarisation des ondes arrivant sur l'antenne. Nous montrons comment l'incorporation (d'une manière judicieuse) de l'information multicomposante permet d'améliorer les performances des algorithmes de traitement. L'originalité des méthodes proposées tient à l'utilisation des modèles mathématiques sortant du cadre de l'algèbre vectorielle classique, et qui se trouvent particulièrement bien adaptés à la nature des signaux multicomposantes. <br /><br />Une première approche est fondée sur un modèle tensoriel, permettant de conserver la structure multimodale des signaux. Le tenseur interspectral est introduit pour représenter la covariance des données. Nous proposons deux algorithmes (Vector-MUSIC et Higher-Order MUSIC) basés sur des décompositions orthogonales du tenseur interspectral. Nous montrons, sur des simulations, que l'utilisation du modèle tensoriel et des décompositions multilinéaires associées améliorent les performances des méthodes proposées par rapport à celles atteignables avec les techniques classiques.<br /><br />Nous proposons également une approche en traitement d'antenne multicomposante fondée sur l'utilisation des algèbres hypercomplexes. Les vecteurs de quaternions et biquaternions sont utilisés pour modéliser les signaux polarisés enregistrés par une antenne à deux, trois ou quatre composantes. Deux algorithmes (Quaternion-MUSIC et Biquaternion-MUSIC), basés sur la diagonalisation des matrices de quaternions et de biquaternions, sont introduits. Nous montrons que l'utilisation des nombres hypercomplexes réduit le temps de calcul et améliore la résolution des méthodes.

Le but de cette thèse est de rendre effectifs certains théorèmes et d'implanter efficacement certains algorithmes en algèbre différentielle, en vue d'une application à l'automatique non linéaire. Nous présentons trois résultats originaux. Le premier est un algorithme, Rosenfeld-Gröbner, qui décrit les modèles d'un système d'équations et d'inéquations polynomiales en algèbre différentielle ordinaire comme en algèbre différentielle partielle. L'algorithme décide du vide et donc de l'appartenance au radical d'un idéal différentiel de type fini. Notre deuxième résultat est une méthode qui calcule un ensemble caractéristique d'un idéal différentiel premier donné par une famille génératrice. Nous donnons enfin de nouvelles preuves des algorithmes d'élimination de Seidenberg. Les algorithmes que nous décrivons sont effectifs : ils n'utilisent que l'addition, la multiplication, les dérivations et le test d'égalité à zéro dans le corps de base des polynômes.

Cette thèse s'inscrit dans la théorie des matrices aléatoires, à l'intersection avec la théorie des probabilités libres et des algèbres d'opérateurs. Elle s'insère dans une démarche générale qui a fait ses preuves ces dernières décennies : importer les techniques et les concepts de la théorie des probabilités non commutatives pour l'étude du spectre de grandes matrices aléatoires. On s'intéresse ici à des généralisations du théorème de liberté asymptotique de Voiculescu. Dans les Chapitres 1 et 2, nous montrons des résultats de liberté asymptotique forte pour des matrices gaussiennes, unitaires aléatoires et déterministes. Dans les Chapitres 3 et 4, nous introduisons la notion de fausse liberté asymptotique pour des matrices déterministes et certaines matrices hermitiennes à entrées sous diagonales indépendantes, interpolant les modèles de matrices de Wigner et de Lévy.

Le Network Calculus est une théorie visant à calculer des bornes pire-cas sur les performances des réseaux de communication. Le réseau est modélisé par un graphe orienté où les noeuds représentent des serveurs, et les flux traversant le réseau doivent suivre les arcs. S'ajoutent à cela des contraintes sur les courbes de trafic (la quantité de données passées par un point depuis la mise en route du réseau) et sur les courbes de service (la quantité de travail fournie par chaque serveur). Pour borner les performances pire-cas, comme la charge en différents points ou les délais de bout en bout, ces enveloppes sont combinées à l'aide d'opérateurs issus notamment des algèbres tropicales : min, +, convolution-(min, +)... Cette thèse est centrée sur l'algorithmique du Network Calculus, à savoir comment rendre effectif ce formalisme. Ce travail nous a amené d'abord à comparer les variations présentes dans la littérature sur les modèles utilisés, révélant des équivalences d'expressivité comme entre le Real-Time Calculus et le Network Calculus. Dans un deuxième temps, nous avons proposé un nouvel opérateur (min, +) pour traiter le calcul de performances en présence d'agrégation de flux, et nous avons étudié le cas des réseaux sans dépendances cycliques sur les flux et avec politique de service quelconque. Nous avons montré la difficulté algorithmique d'obtenir précisément les pires cas, mais nous avons aussi fourni une nouvelle heuristique pour les calculer. Elle s'avère de complexité polynomiale dans des cas intéressants.

Les facteurs de forme et les fonctions de corrélation déterminent les quantités dynamiques mesurables associées aux modèles de théorie des champs et de mécanique statistique. Dans le cas de modèles intégrables en dimension 2, au-delà des propriétés du spectre ou de la fonction de partition, un des grands défis actuels concerne le calcul exact des facteurs de forme et des fonctions de corrélation.Le but de cette thèse est de développer une approche permettant de résoudre ce problème dans le cadre de la méthode de séparation des variables quantique de Skyanin. Cette méthode généralise au cas quantique et pour des systèmes avec un grand nombre de degrés de liberté la méthode de Hamilton-Jacobi en mécanique analytique. Le Hamiltonien est exprimé avec des opérateurs séparés, son spectre et ses états propres caractérisés par un système d'équations de Baxter résultant des structures algébriques de Yang-Baxter, caractéristiques de l'intégrabilité de ces modèles.Cette thèse a permis, pour les modèles de sine-Gordon (théorie des champs quantique) et de Potts chiral (modèle de physique statistique), le calcul des produits scalaires entre états propres du Hamiltonien, la résolution du problème inverse, i. e. l'expression des opérateurs du modèle en termes des variables séparées, ainsi que le calcul en termes de déterminants des facteurs de forme, i. e. des éléments de matrice des opérateurs locaux du modèle dans la base propre du Hamiltonien, ce qui constitue un pas important vers le calcul des fonctions de corrélation de ces modèles.

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

Dans cette thèse nous développons de nouveaux algorithmes de calcul numérique pour les matrices polynomiales. Nous abordons le problème du calcul de la structure propre (rang, espace nul, structures finie et infinie) d'une matrice polynomiale et nous appliquons les résultats obtenus au calcul de la factorisation J-spectrale des matrices polynomiales. Nous présentons également quelques applications de ces algorithmes en théorie de la commande. Tous les nouveaux algorithmes décrits ici sont basés sur le calcul d'espaces nuls constants de matrices bloc Toeplitz associées à la matrice polynomiale analysée. Pour calculer ces espaces nuls nous utilisons des méthodes standard de l'algèbre linéaire numérique comme la décomposition en valeurs singulières ou la factorisation QR. Nous étudions aussi l'application de méthodes rapides comme la méthode généralisée de Schur pour les matrices structurées. Nous analysons les algorithmes présentés au niveau complexité algorithmique et stabilité numérique, et effectuons des comparaisons avec d'autres algorithmes existants dans la littérature.