Le contexte de ce travail est la mecanique spatiale. Plus precisement, on s'est interesse, dans le cadre d'une collaboration avec le Centre National d'Etudes Spatiales, au probleme du transfert orbital. Le modele etudie est celui du controle en temps minimal d'un satellite que l'on souhaite inserer sur une orbite geostationnaire. Les contributions de cette these sont de trois ordres. Geometrique, tout d'abord, puisqu'on etudie la controlabilite du systeme ainsi que la geometrie des transferts (structure de la commande) a l'aide d'outils de controle geometrique. Sont ensuite presentees des methodes de resolution spectrales et pseudo-spectrales utilisant les polynomes de Tchebycheff, puis des algorithmes bases sur un calcul adaptatif de discretisation par ondelettes. Ces approches permettent de traiter numeriquement le cas d'un satellite dont la poussee est forte a moyenne. Pour atteindre le domaine des poussees faibles, caracteristiques de la future propulsion electro-ionique, il faut finalement introduire de nouvelles techniques qui ont en commum d'etre parametriques (parametrisation par la poussee ou par le critere). L'analyse des proprietes de ces methodes se fait naturellement a l'aide de resultats de controle parametrique.

Les travaux effectués lors de cette thèse portent sur 1a construction d'algorithmes géométriques dit adaptatifs dans 1e sens ou leur temps de calcul s'adapte a la solution construite. Nous décrivons tout d'abord les principaux paradigmes qui permettent d'obtenir des algorithmes adaptatifs. Puis , nous proposons un algorithme quasi-optimal adaptatif pour le calcul d'enveloppe convexe d'objets planaires dont la complexité de l'enveloppe convexe de toute paire soit bornée. L'algorithme est basé sur une approche composite combinant 1e paradigme mariage avant conquête et 1a méthodologie du groupement en paquets. Nous considérons également le calcul de l'enveloppe supérieure de fonctions et la décomposition convexe partielle d'un ensemble de points. Finalement, nous nous sommes intéressés aux problèmes de perçabílíté d'objets qui ont été montré NP-difficiles. En premier lieu, nous avons étudié le cas de boîtes ísothétíques en donnant une heuristique adaptative dont 1a précision soit elle-même adaptative. Ensuite, nous avons étudié les propriétés combinatoires des objets convexes pour 1a perçabílíté. Nous obtenons une batterie d'algorithmes pour des classes variées d'objets dont certains prouvent l'exístence de théorèmes de type Helly.

Les simulations moléculaires sont devenues un outil essentiel en biologie, chimie et physique. Malheureusement, elles restent très coûteuses. Dans cette thèse, nous proposons des algorithmes qui accélèrent les simulations moléculaires en regroupant des particules en plusieurs objets rigides. Nous étudions d'abord plusieurs algorithmes de recherche de voisins dans le cas des grands objets rigides, et démontrons que les algorithmes hiérarchiques permettent d'obtenir des accélérations importantes. En conséquence, nous proposons une technique pour construire une représentation hiérarchique d'un graphe moléculaire arbitraire. Nous démontrons l'usage de cette technique pour la mécanique adaptative en angles de torsion, une méthode de simulation qui décrit les molécules comme des objets rigides articulés. Enfin, nous introduisons ARPS - Adaptively Restrained Particle Simulations ("Simulations de particules restreintes de façon adaptative") - une méthode mathématiquement fondée capable d'activer et de désactiver les degrés de liberté en position. Nous proposons deux stratégies d'adaptation, et illustrons les avantages de ARPS sur plusieurs exemples. En particulier, nous démontrons comment ARPS permet de choisir finement le compromis entre précision et vitesse, ainsi que de calculer rapidement des proprietésstatiques d'équilibre sur les systèmes moléculaires.

Les simulations moléculaires sont devenues un outil essentiel en biologie, chimie et physique. Malheureusement, elles restent très coûteuses. Dans cette thèse, nous proposons des algorithmes qui accélèrent les simulations moléculaires en regroupant des particules en plusieurs objets rigides. Nous étudions d’abord plusieurs algorithmes de recherche de voisins dans le cas des grands objets rigides, et démontrons que les algorithmes hiérarchiques permettent d’obtenir des accélérations importantes. En conséquence, nous proposons une technique pour construire une représentation hiérarchique d’un graphe moléculaire arbitraire. Nous démontrons l’usage de cette technique pour la mécanique adaptative en angles de torsion, une méthode de simulation qui décrit les molécules comme des objets rigides articulés. Enfin, nous introduisons ARPS – Adaptively Restrained Particle Simulations (“Simulations de particules restreintes de façon adaptative”) – une méthode mathématiquement fondée capable d’activer et de désactiver les degrés de liberté en position. Nous proposons deux stratégies d’adaptation, et illustrons les avantages de ARPS sur plusieurs exemples. En particulier, nous démontrons comment ARPS permet de choisir finement le compromis entre précision et vitesse, ainsi que de calculer rapidement des proprietésstatiques d’équilibre sur les systèmes moléculaires. / Molecular simulations have become an essential tool in biology, chemistry and physics. Unfortunately, they still remain computationally challenging. In this dissertation, we propose algorithms that accelerate molecular simulations by clustering particles into rigid bodies.We first study several neighbor-search algorithms for large rigid bodies, and show that hierarchy-based algorithms may provide significant speedups. Accordingly, we propose a technique to build a hierarchical representation of an arbitrary molecular graph. We show how this technique can be used in adaptive torsion-angle mechanics, a simulation method that describes molecules as articulated rigid bodies. Finally, we introduce ARPS – Adaptively Restrained Particle Simulations – a mathematically-grounded method able to switch positional degrees of freedom on and off. We propose two switching strategies, and illustrate the advantages of ARPS on various examples. In particular, we show how ARPS allow us to smoothly trade between precision and speed, and to efficiently compute correct static equilibrium properties on molecular systems.

L'essor des nouvelles technologies de télécommunication et de conception des capteurs a fait apparaître un nouveau domaine du traitement du signal : les réseaux de capteurs. Une application clé de ce nouveau domaine est l'estimation à distance : les capteurs acquièrent de l'information et la transmettent à un point distant où l'estimation est faite. Pour relever les nouveaux défis apportés par cette nouvelle approche (contraintes d'énergie, de bande et de complexité), la quantification des mesures est une solution. Ce contexte nous amène à étudier l'estimation à partir de mesures quantifiées. Nous nous concentrons principalement sur le problème d'estimation d'un paramètre de centrage scalaire. Le paramètre est considéré soit constant, soit variable dans le temps et modélisé par un processus de Wiener lent. Nous présentons des algorithmes d'estimation pour résoudre ce problème et, en se basant sur l'analyse de performance, nous montrons l'importance de l'adaptativité de la dynamique de quantification pour l'obtention d'une performance optimale. Nous proposons un schéma adaptatif de faible complexité qui, conjointement, estime le paramètre et met à jour les seuils du quantifieur. L'estimateur atteint de cette façon la performance asymptotique optimale. Avec 4 ou 5 bits de résolution, nous montrons que la performance optimale pour la quantification uniforme est très proche des performances d'estimation à partir de mesures continues. Finalement, nous proposons une approche à haute résolution pour obtenir les seuils de quantification non-uniformes optimaux ainsi qu'une approximation analytique des performances d'estimation. / With recent advances in sensing and communication technology, sensor networks have emerged as a new field in signal processing. One of the applications of his new field is remote estimation, where the sensors gather information and send it to some distant point where estimation is carried out. For overcoming the new design challenges brought by this approach (constrained energy, bandwidth and complexity), quantization of the measurements can be considered. Based on this context, we study the problem of estimation based on quantized measurements. We focus mainly on the scalar location parameter estimation problem, the parameter is considered to be either constant or varying according to a slow Wiener process model. We present estimation algorithms to solve this problem and, based on performance analysis, we show the importance of quantizer range adaptiveness for obtaining optimal performance. We propose a low complexity adaptive scheme that jointly estimates the parameter and updates the quantizer thresholds, achieving in this way asymptotically optimal performance. With only 4 or 5 bits of resolution, the asymptotically optimal performance for uniform quantization is shown to be very close to the continuous measurement estimation performance. Finally, we propose a high resolution approach to obtain an approximation of the optimal nonuniform quantization thresholds for parameter estimation and also to obtain an analytical approximation of the estimation performance based on quantized measurements.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Sur plusieurs problèmes il est difficile d'avoir un seul algorithme qui résout optimalement (en temps d'exécution) toutes ses instances. Ce constat motive l'élaboration des approches permettant de combiner plusieurs algorithmes résolvant le même problème. Les approches permettant la combinaison d'algorithmes peuvent être mise en oeuvre au niveau système (en construisant des bibliothèques, des langages et composants adaptatifs etc.) ou au niveau purement algorithmique. Ce travail se focalise sur les approches génériques de combinaison d'algorithmes au niveau algorithmique avec en particulier l'approche du portfolio d'algorithmes. Un portfolio d'algorithmes définit une exécution concurrente de plusieurs algorithmes résolvant un même problème. Dans une telle exécution, les algorithmes sont entrelacées dans le temps et/ou l'espace. Sur une instance à résoudre, l'exécution est interrompue dès qu'un des algorithmes trouve une solution. Nous proposons dans cette thèse une classification des techniques de combinaison d'algorithmes. Dans celle ci nous précisons pour chaque technique le contexte le plus adapté pour son utilisation. Nous proposons ensuite deux techniques de construction des portfolio d'algorithmes. La première technique est basée sur une adaptation de la méthode des plus proches voisins en apprentissage automatique pour la combinaison des algorithmes. Cette technique est adaptative car elle essaie sur chaque instance de trouver un sous ensemble d'algorithmes adaptés pour sa résolution. Nous l'appliquons dans la combinaison des algorithmes itératifs pour la résolution des systèmes linéaires et nous montrons sur un jeu d'environ mille matrices creuses qu'elle permet de réduire le nombre d'itérations et le temps nécéssaire dans la résolution. En outre, sur certains jeux d'expérimentations, ces résultats montrent que la technique proposée peut dans la plupart des cas trouver l'algorithme le plus adapté à sa résolution. La seconde technique est basée sur le problème de partage de ressources que nous formulons. Etant donnés, un problème cible, un jeu de données le représentant, un ensemble d'algorithmes candidats le résolvant et le comportement en temps d'exécution du jeu de données sur les algorithmes candidats, le problème de partage de ressources a pour objectif de trouver la meilleure répartition statique des ressources aux algorithmes candidats de sorte à minimiser en moyenne le temps de résolution du jeu de données cibles. Ce problème vise à trouver une solution en moyenne plus robuste que chacun des algorithmes candidats pris séparémment. Nous montrons que ce problème est NP-complet et proposons deux familles d'algorithmes approchés et exacts pour le résoudre. Nous validons les solutions proposées en prenant des données issues d'une base de données pour SAT. Les résultats obtenus montrent que les solutions proposées permettent effectivement de bénéficier de la complémentarité des algorithmes résolvant un même problème pour la construction des algorithmes robustes.

L'objet de cette thèse est l'étude d'algorithmes itératifs permettant de résoudre des problèmes d'optimisation convexe avec ou sans contraintes fonctionnelles, des problèmes de résolutions d'inégalités variationnelles à opérateur monotone et des problèmes de recherche de point selle. Ces problèmes sont envisagés lorsque la dimension de l'espace de recherche est grande et lorsque les valeurs des différentes fonctions étudiées et leur sous/sur-gradients ne sont pas connues exactement et ne sont accessibles qu'au travers d'un oracle stochastique. Les algorithmes que nous étudions sont des adaptations au cas stochastique de deux algorithmes : le premier inspiré de la méthode de descente en miroir de Nemirovski et Yudin et le second, de l'algorithme d'extrapolation duale de Nesterov. Pour chacun de ces deux algorithmes, nous donnons des bornes pour l'espérance et pour les déviations modérées de l'erreur d'approximation sous différentes hypothèses de régularité pour tous les problèmes sans contraintes fonctionnelles envisagées et nous donnons des versions adaptatives de ces algorithmes qui permettent de s'affranchir de connaître certains paramètres de ces problèmes non accessibles en pratique. Enfin nous montrons comment, à l'aide d'un algorithme auxiliaire inspiré de la méthode de Newton et des résultats obtenus lors de la résolution des problèmes de recherche de point selle, il est possible de résoudre des problèmes d'optimisation sous contraintes fonctionnelles.

L'essor des nouvelles technologies de télécommunication et de conception des capteurs a fait apparaître un nouveau domaine du traitement du signal : les réseaux de capteurs. Une application clé de ce nouveau domaine est l'estimation à distance : les capteurs acquièrent de l'information et la transmettent à un point distant où l'estimation est faite. Pour relever les nouveaux défis apportés par cette nouvelle approche (contraintes d'énergie, de bande et de complexité), la quantification des mesures est une solution. Ce contexte nous amène à étudier l'estimation à partir de mesures quantifiées. Nous nous concentrons principalement sur le problème d'estimation d'un paramètre de centrage scalaire. Le paramètre est considéré soit constant, soit variable dans le temps et modélisé par un processus de Wiener lent. Nous présentons des algorithmes d'estimation pour résoudre ce problème et, en se basant sur l'analyse de performance, nous montrons l'importance de l'adaptativité de la dynamique de quantification pour l'obtention d'une performance optimale. Nous proposons un schéma adaptatif de faible complexité qui, conjointement, estime le paramètre et met à jour les seuils du quantifieur. L'estimateur atteint de cette façon la performance asymptotique optimale. Avec 4 ou 5 bits de résolution, nous montrons que la performance optimale pour la quantification uniforme est très proche des performances d'estimation à partir de mesures continues. Finalement, nous proposons une approche à haute résolution pour obtenir les seuils de quantification non-uniformes optimaux ainsi qu'une approximation analytique des performances d'estimation.

No description available.