Les avancées récentes dans le domaine de navigation par satellites (GNSS) ontconduit à une prolifération des applications de géolocalisation dans les milieux urbains. Pourde tels environnements, les applications GNSS souffrent d’une grande dégradation liée à laréception des signaux satellitaires en lignes indirectes (NLOS) et en multitrajets (MP). Cetravail de thèse propose une méthodologie originale pour l’utilisation constructive des signauxdégradés MP/NLOS, en appliquant des techniques avancées de traitement du signal ou àl’aide d’une assistance d’un simulateur 3D de propagation des signaux GNSS. D’abord, nousavons établi le niveau maximal réalisable sur la précision de positionnement par un systèmeGNSS "Stand-Alone" en présence de conditions MP/NLOS, en étudiant les bornes inférieuressur l’estimation en présence des signaux MP/NLOS. Pour mieux améliorer ce niveau deprécision, nous avons proposé de compenser les erreurs NLOS en utilisant un simulateur 3D dessignaux GNSS afin de prédire les biais MP/NLOS et de les intégrer comme des observationsdans l’estimation de la position, soit par correction des mesures dégradées ou par sélectiond’une position parmi une grille de positions candidates. L’application des approches proposéesdans un environnement urbain profond montre une bonne amélioration des performances depositionnement dans ces conditions. / Recent trends in Global Navigation Satellite System (GNSS) applications inurban environments have led to a proliferation of studies in this field that seek to mitigatethe adverse effect of non-line-of-sight (NLOS). For such harsh urban settings, this dissertationproposes an original methodology for constructive use of degraded MP/NLOS signals, insteadof their elimination, by applying advanced signal processing techniques or by using additionalinformation from a 3D GNSS simulator. First, we studied different signal processing frameworks,namely robust estimation and regularized estimation, to tackle this GNSS problemwithout using an external information. Then, we have established the maximum achievablelevel (lower bounds) of GNSS Stand-Alone positioning accuracy in presence of MP/NLOSconditions. To better enhance this accuracy level, we have proposed to compensate for theMP/NLOS errors using a 3D GNSS signal propagation simulator to predict the biases andintegrate them as observations in the estimation method. This could be either by correctingdegraded measurements or by scoring an array of candidate positions. Besides, new metricson the maximum acceptable errors on MP/NLOS errors predictions, using GNSS simulations,have been established. Experiment results using real GNSS data in a deep urban environmentshow that using these additional information provides good positioning performance enhancement,despite the intensive computational load of 3D GNSS simulation.

Dans cette thèse nous proposons quelques contributions à l'analyse variationnelle dans les espaces métriques et à l'optimisation : régularité métrique, théorie métrique des points critiques, sensibilité de constantes de Hoffman, stabilité en programmation quadratique. Dans le cas polyèdral nous établissons des formules explicites de constantes de Hoffman des polyèdres avec égalités explicites. Ensuite, en mettant en évidence le caractère lipschitzien de ces constantes, nous calculons le sous-différentiel de Clarke des fonctions associées. Nous faisons également une revue de la régularité métrique des multi-applications, et nous traitons la stabilité d'un problème quadratique convexe. La considération du concept de pente faible, et donc des techniques de déformation appropriées, nous permet d'établir des résultats de stabilité homotopique des points critiques isolés des fonctions continues.

Cette thèse s'inscrit dans le domaine de l'apprentissage statistique. Le cadre principal est celui de la prévision de suites déterministes arbitraires (ou suites individuelles), qui recouvre des problèmes d'apprentissage séquentiel où l'on ne peut ou ne veut pas faire d'hypothèses de stochasticité sur la suite des données à prévoir. Cela conduit à des méthodes très robustes. Dans ces travaux, on étudie quelques liens étroits entre la théorie de la prévision de suites individuelles et le cadre statistique classique, notamment le modèle de régression avec design aléatoire ou fixe, où les données sont modélisées de façon stochastique. Les apports entre ces deux cadres sont mutuels : certaines méthodes statistiques peuvent être adaptées au cadre séquentiel pour bénéficier de garanties déterministes ; réciproquement, des techniques de suites individuelles permettent de calibrer automatiquement des méthodes statistiques pour obtenir des bornes adaptatives en la variance du bruit. On étudie de tels liens sur plusieurs problèmes voisins : la régression linéaire séquentielle parcimonieuse en grande dimension (avec application au cadre stochastique), la régression linéaire séquentielle sur des boules L1, et l'agrégation de modèles non linéaires dans un cadre de sélection de modèles (régression avec design fixe). Enfin, des techniques stochastiques sont utilisées et développées pour déterminer les vitesses minimax de divers critères de performance séquentielle (regrets interne et swap notamment) en environnement déterministe ou stochastique.

Cette thèse porte sur l'étude des techniques d'estimation Bayesienne non-linéaire, et leur applications aux problèmes de synchronisation pour des systèmes de communication par satellite, ainsi qu'au calcul des bornes Bayesiennes pour le problème de synchronisation suréchantillonné. D'abord, on présente le filtrage de Kalman et les méthodes particulaires, et l'on propose une nouvelle vue d'ensemble des méthodes déterministes. Ensuite, on établie la modélisation pour le probléme de la synchronisation fractionnée dans des systémes satellite, et l'on calcule la borne de Cramér-Rao Bayesienne pour le probléme d'estimation de phase, et la borne de Cramér-Rao hybride pour le probléme d'estimation conjointe de phase et d'offset de fréquence. Dans un deuxième temps, on applique les méthodes de filtrage (Kalman, particulaires et déterministes) aux problèmes d'estimation de phase, d'estimation conjointe de phase et d'offset de fréquence, d'estimation de délai et d'estimation de phase avec des bruits non-Gaussiens. Les méthodes proposées ont montré de bonnes performances pour nos problèmes de synchronisation. On présente aussi dans cette thèse, trois études liées aux travaux principaux. Le premier concerne l'estimation conjointe des gains complexes et du délai dans un canal de Rayleigh à variations lentes pour des signaux CPM. Le deuxième présente l'utilisation des méthodes déterministes pour la localisation avec un réseau de capteurs. Et finalement, le troisième présente le couplage GNSS/INS ultra précis et une solution déterministes à cette problèmatique.

La reformulation du théorème de Bayes par R. de Cristofaro permet d'intégrer l'information sur le plan expérimental dans la loi a priori. En acceptant de transgresser les principes de vraisemblance et de la règle d'arrêt, un nouveau cadre théorique permet d'aborder le problème de la séquentialité dans l'inférence bayésienne. En considérant que l'information sur le plan expérimental est contenue dans l'information de Fisher, on dérive une famille de lois a priori à partir d'une vraisemblance directement associée à l'échantillonnage. Le cas de l'évaluation d'une proportion dans le contexte d'échantillonnages Binomiaux successifs conduit à considérer la loi Bêta-J. L'étude sur plusieurs plans séquentiels permet d'établir que l'"a priori de Jeffreys corrigé" compense le biais induit sur la proportion observée. Une application dans l'estimation ponctuelle montre le lien entre le paramétrage des lois Bêta-J et Bêta dans l'échantillonnage fixe. La moyenne et le mode des lois a posteriori obtenues présentent des propriétés fréquentistes remarquables. De même, l'intervalle de Jeffreys corrigé montre un taux de recouvrement optimal car la correction vient compenser l'effet de la règle d'arrêt sur les bornes. Enfin, une procédure de test, dont les erreurs s'interprètent à la fois en terme de probabilité bayésienne de l'hypothèse et de risques fréquentistes, est construite avec une règle d'arrêt et de rejet de H0 fondée sur une valeur limite du facteur de Bayes. On montre comment l'a priori de Jeffreys corrigé compense le rapport des évidences et garantit l'unicité des solutions, y compris lorsque l'hypothèse nulle est composite.

Contexte et objectifs. En 1995, le gouvernement canadien a promulgué la Loi C-68, rendant ainsi obligatoire l’enregistrement de toutes les armes à feu et affermissant les vérifications auprès des futurs propriétaires. Faute de preuves scientifiques crédibles, le potentiel de cette loi à prévenir les homicides est présentement remis en question. Tout en surmontant les biais potentiels retrouvés dans les évaluations antérieures, l’objectif de ce mémoire est d’évaluer l’effet de la Loi C-68 sur les homicides au Québec entre 1974 et 2006. Méthodologie. L’effet de la Loi C-68 est évalué à l’aide d’une analyse des bornes extrêmes. Les effets immédiats et graduels de la Loi sont évalués à l’aide de 372 équations. Brièvement, il s’agit d’analyses de séries chronologiques interrompues où toutes les combinaisons de variables indépendantes sont envisagées afin d’éviter les biais relatifs à une spécification arbitraire des modèles. Résultats. L’introduction de la Loi C-68 est associée à une baisse graduelle des homicides commis à l’aide d’armes longues (carabines et fusils de chasse), sans qu’aucun déplacement tactique ne soit observé. Les homicides commis par des armes à feu à autorisation restreinte ou prohibées semblent influencés par des facteurs différents. Conclusion. Les résultats suggèrent que le contrôle des armes à feu est une mesure efficace pour prévenir les homicides. L’absence de déplacement tactique suggère également que l’arme à feu constitue un important facilitateur et que les homicides ne sont pas tous prémédités. D’autres études sont toutefois nécessaires pour clairement identifier les mécanismes de la Loi responsables de la baisse des homicides. / Context and objectives. Laws with extensive background checks and making mandatory the registration of all guns have been adopted by some governments to prevent firearms-related homicides. On the other hand, methodological flaws found in previous evaluations question the potential of such laws to prevent gun homicides. By taking into account previous limitations, the main objective of this study is to estimate the effect of Bill C-68 on homicides committed in the Province of Quebec, Canada, between 1974 and 2006. Methodology. Using extreme bounds analysis, we assess the effect of Bill C-68 on homicides. Estimates of the immediate and gradual effects of the law are based on a total of 372 equations. More precisely, interrupted time series analyses were conducted, using all possible variable combinations, in order to overcome biases related to model specification. Results. We found that Bill C-68 is associated with a significant and gradual decline in homicides committed with a long gun (either a riffle or a shotgun). The substitution effects are not robust with respect to different model specifications. Patterns observed in homicides involving restricted or prohibited firearms suggest that they are influenced by different factors, not considered in our analyses. Conclusion. Results suggest that enhanced firearm control laws are an effective tool to prevent homicides. The lack of tactical displacement supports the concept of firearm as a crime facilitator and suggests that all homicides are not carefully planned. Other studies are however needed to pinpoint law provisions accountable for the decrease in homicides.

Ce manuscrit est dédié à l'analyse de performances en traitement d'antenne pour l'estimation des paramètres d'intérêt à l'aide d'un réseau de capteurs. Il est divisé en deux parties :- Tout d'abord, nous présentons l'étude de certaines bornes inférieures de l'erreur quadratique moyenne liées à la localisation de sources dans le contexte champ proche. Nous utilisons la borne de Cramér-Rao pour l'étude de la zone asymptotique (notamment en terme de rapport signal à bruit avec un nombre fini d'observations). Puis, nous étudions d'autres bornes inférieures de l'erreur quadratique moyenne qui permettent de prévoir le phénomène de décrochement de l'erreur quadratique moyenne des estimateurs (on cite, par exemple, la borne de McAulay-Seidman, la borne de Hammersley-Chapman-Robbins et la borne de Fourier Cramér-Rao).- Deuxièmement, nous nous concentrons sur le concept du seuil statistique de résolution limite, c'est-à-dire, la distance minimale entre deux signaux noyés dans un bruit additif qui permet une "correcte" estimation des paramètres. Nous présentons quelques applications bien connues en traitement d'antenne avant d'étendre les concepts existants au cas de signaux multidimensionnels. Par la suite, nous étudions la validité de notre extension en utilisant un test d'hypothèses binaire. Enfin, nous appliquons notre extension à certains modèles d'observation multidimensionnels

Nous introduisons un nouveau modèle de la communication à deux parties dans lequel nous nous intéressons au temps que prennent deux participants à effectuer une tâche à travers un canal avec délai d. Nous établissons quelques bornes supérieures et inférieures et comparons ce nouveau modèle aux modèles de communication classiques et quantiques étudiés dans la littérature. Nous montrons que la complexité de la communication d’une fonction sur un canal avec délai est bornée supérieurement par sa complexité de la communication modulo un facteur multiplicatif d/ lg d. Nous présentons ensuite quelques exemples de fonctions pour lesquelles une stratégie astucieuse se servant du temps mort confère un avantage sur une implémentation naïve d’un protocole de communication optimal en terme de complexité de la communication. Finalement, nous montrons qu’un canal avec délai permet de réaliser un échange de bit cryptographique, mais que, par lui-même, est insuffisant pour réaliser la primitive cryptographique de transfert équivoque. / We introduce a new communication complexity model in which we want to determine how much time of communication is needed by two players in order to execute arbitrary tasks on a channel with delay d. We establish a few basic lower and upper bounds and compare this new model to existing models such as the classical and quantum two-party models of communication. We show that the standard communication complexity of a function, modulo a factor of d/ lg d, constitutes an upper bound to its communication complexity on a delayed channel. We introduce a few examples on which a clever strategy depending on the delay procures a significant advantage over the naïve implementation of an optimal communication protocol. We then show that a delayed channel can be used to implement a cryptographic bit swap, but is insufficient on its own to implement an oblivious transfer scheme.

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. / Network Calculus is a theory aiming at computing worst-case bounds on performances in communication networks. The network is usually modelled by a digraph : the servers are located on the nodes and the flows must follow path in the digraph. There are constraints on the trafic curves (how much data have been through a given point since the activation of the network) and on the service curves (how much work each server may provide). To derive bounds on the worst-case performances, as the backlog or the end-to-end delay, these envelopes are combined thanks to tropical algebra operators: min, +, convolution... This thesis focuses on Network Calculus algorithmics, that is how effective is this formalism. This work led us to compare various models in the litterature, and to show expressiveness equivalence between Real-Time Calculus and Network Calculus. Then, we suggested a new (min, +) operator to compute performances bounds in networks with agregated flows and we studied feed-forward networks under blind multiplexing. We showed the difficulty to compute these bounds, but we gave an heuristic, which is polynomial for interesting cases.

La complexité algorithmique est l'étude des ressources nécessaires — le temps, la mémoire, … — pour résoudre un problème de manière algorithmique. Dans ce cadre, la théorie de la complexité algébrique est l'étude de la complexité algorithmique de problèmes de nature algébrique, concernant des polynômes.Dans cette thèse, nous étudions différents aspects de la complexité algébrique. D'une part, nous nous intéressons à l'expressivité des déterminants de matrices comme représentations des polynômes dans le modèle de complexité de Valiant. Nous montrons que les matrices symétriques ont la même expressivité que les matrices quelconques dès que la caractéristique du corps est différente de deux, mais que ce n'est plus le cas en caractéristique deux. Nous construisons également la représentation la plus compacte connue du permanent par un déterminant. D'autre part, nous étudions la complexité algorithmique de problèmes algébriques. Nous montrons que la détection de racines dans un système de n polynômes homogènes à n variables est NP-difficile. En lien avec la question « VP = VNP ? », version algébrique de « P = NP ? », nous obtenons une borne inférieure pour le calcul du permanent d'une matrice par un circuit arithmétique, et nous exhibons des liens unissant ce problème et celui du test d'identité polynomiale. Enfin nous fournissons des algorithmes efficaces pour la factorisation des polynômes lacunaires à deux variables. / Computational complexity is the study of the resources — time, memory, …— needed to algorithmically solve a problem. Within these settings, algebraic complexity theory is the study of the computational complexity of problems of algebraic nature, concerning polynomials. In this thesis, we study several aspects of algebraic complexity. On the one hand, we are interested in the expressiveness of the determinants of matrices as representations of polynomials in Valiant's model of complexity. We show that symmetric matrices have the same expressiveness as the ordinary matrices as soon as the characteristic of the underlying field in different from two, but that this is not the case anymore in characteristic two. We also build the smallest known representation of the permanent by a determinant.On the other hand, we study the computational complexity of algebraic problems. We show that the detection of roots in a system of n homogeneous polynomials in n variables in NP-hard. In line with the “VP = VNP ?”question, which is the algebraic version of “P = NP?” we obtain a lower bound for the computation of the permanent of a matrix by an arithmetic circuit, and we point out the links between this problem and the polynomial identity testing problem. Finally, we give efficient algorithms for the factorization of lacunary bivariate polynomials.