L'avènement de l'informatique quantique permet de réétudier les primitives cryptographiques avec une sécurité inconditionnelle, c'est à dire sécurisé même contre des adversaires tout puissants. En 1984, Bennett et Brassard ont construit un protocole quantique de distribution de clé. Dans ce protocole, deux joueurs Alice et Bob coopèrent pour partager une clé secrète inconnue d'une tierce personne Eve. Ce protocole a une sécurité inconditionnelle et n'a pasd'équivalent classique.Dans ma thèse, j'ai étudié les primitives cryptographiques à deux joueurs où ces joueurs ne se font pas confiance. J'étudie principalement le pile ou face quantique et la mise-en-gage quantique de bit. En informatique classique, ces primitivessont réalisables uniquement avec des hypothèses calculatoires, c'est-à-dire en supposant la difficulté d'un problème donné. Des protocoles quantiques ont été construits pour ces primitives où un adversaire peut tricher avec une probabilité constante strictement inférieure à 1, ce qui reste impossible classiquement. Néanmoins, Lo et Chau ont montré l'impossibilité de créer ces primitives parfaitement même en utilisant l'informatique quantique. Il reste donc à déterminer quelles sont les limites physiques de ces primitives.Dans une première partie, je construis un protocole quantique de pile ou face où chaque joueur peut tricher avec probabilité au plus 1/racine(2) + eps pour tout eps > 0. Ce résultat complète un résultat de Kitaev qui dit que dans un jeu de pile ou face quantique, un joueur peut toujours tricher avec probabilité au moins 1/racine(2). J'ai également construit un protocole de mise-en-gage de bit quantique optimal où un joueur peut tricher avec probabilité au plus 0,739 + eps pour tout eps > 0 puis ai montré que ce protocole est en fait optimal. Finalement, j'ai dérivé des bornes inférieures et supérieures pour une autre primitive: la transmission inconsciente, qui est une primitive universelle.Dans une deuxième partie, j'intègre certains aspects pratiques dans ces protocoles. Parfois les appareils de mesure ne donnent aucun résultat, ce sont les pertes dans la mesure. Je construis un protocole de lancer de pièce quantique tolérant aux pertes avec une probabilité de tricher de 0,859. Ensuite, j'étudie le modèle dispositif-indépendant où on ne suppose plus rien sur les appareils de mesure et de création d'état quantique.Finalement, dans une troisième partie, j'étudie ces primitives cryptographiques avec un sécurité computationnelle. En particulier, je fais le lien entre la mise en gage de bit quantique et les protocoles zero-knowledge quantiques.

Une qualité de service uniforme pour les utilisateurs mobiles et une utilisation distribuée du spectre représentent les ingrédients clés des réseaux cellulaires de prochaine génération. Dans ce but, la coopération au niveau de la couche physique entre les nœuds de l’infrastructure et les nœuds du réseau sans fil a émergé comme une technique à fort potentiel. La coopération s’appuie sur les propriétés de diffusion du canal sans fil, c’est-à-dire que la même transmission peut être entendue par plusieurs nœuds, ouvrant ainsi la possibilité pour les nœuds de s’aider à transmettre les messages à leur destination finale. La coopération promet aussi d’offrir une façon nouvelle et intelligente de gérer les interférences, au lieu de simplement les ignorer et les traiter comme du bruit. Comprendre comment concevoir ces systèmes radio coopératifs, afin que les ressources disponibles soient pleinement utilisées, est d’une importance fondamentale. L’objectif de cette thèse est de mener une étude du point de vue de la théorie de l’information, pour des systèmes sans fil pertinents dans la pratique, où les nœuds de l’infrastructure coopèrent en essayant d’améliorer les performances du réseau. Les systèmes radio avec des relais semi-duplex ainsi que les scénarios où une station de base aide à servir les utilisateurs mobiles associés à une autre station de base, sont les réseaux sans fil coopératifs étudiés dans cette thèse. Le but principal est la progression vers la caractérisation de la capacité de ces systèmes sans fil au moyen de dérivation de nouvelles bornes supérieures pour les performances et la conception de nouvelles stratégies de transmission permettant de les atteindre. / A uniform mobile user quality of service and a distributed use of the spectrum represent the key-ingredients for next generation cellular networks. Toward this end, physical layer cooperation among the network infrastructure and the wireless nodes has emerged as a potential technique. Cooperation leverages the broadcast nature of the wireless medium, that is, the same transmission can be heard by multiple nodes, thus opening up the possibility that nodes help one another to convey the messages to their intended destination. Cooperation also promises to offer novel and smart ways to manage interference, instead of just simply disregarding it and treating it as noise. Understanding how to properly design such cooperative wireless systems so that the available resources are fully utilized is of fundamental importance.The objective of this thesis is to conduct an information theoretic study on practically relevant wireless systems where the network infrastructure nodes cooperate among themselves in an attempt to enhance the network performance in many critical aspects, such as throughput, robustness and coverage. Wireless systems with half-duplex relay stations as well as scenarios where a base station overhears another base station and consequently helps serving this other base station's associated mobile users, represent the wireless cooperative networks under investigation in this thesis. The prior focus is to make progress towards characterizing the capacity of such wireless systems by means of derivation of novel outer bounds and design of new provably optimal transmission strategies.

Les enjeux du développement durable, le réchauffement climatique, la pollution dans les grandes villes, la congestion et les nuisances sonores, l'augmentation des prix de carburants, sont parmi des nombreux facteurs qui incitent les pays développés à l'innovation dans les transports publics. Dans ce contexte, l'introduction des systèmes de vélos en libre-service, au cours de ces dernières années, est une des solutions adoptées par de nombreuses grandes villes. Malgré leur succès fulgurant dans le monde entier, il existe peu d'études fondamentales sur ce type transport urbain. Pourtant, leur exploitation et leur management par des opérateurs soulèvent de nombreuses questions notamment d'ordre opérationnel. Dans ce contexte, cette thèse s'adresse aux problèmes d'ordonnancement et de rééquilibrage des stations de vélos en libre-service. Ce sont des problèmes cruciaux pour la qualité de service et la viabilité économique de tels systèmes. Le rééquilibrage consiste à redistribuer le nombre de vélos entre les différentes stations afin de satisfaire au mieux les demandes des usagers. Cette régulation se fait souvent par le biais de véhicules spécifiques qui font des tournées autour des différentes stations. Ainsi, deux problèmes d'optimisation difficiles se posent : la recherche de la meilleure tournée du véhicule de régulation (ordonnancement de la tournée) et la détermination des nombres de véhicules à utiliser (rééquilibrage des stations). Dans cette optique, les travaux de cette thèse constituent une contribution à la modélisation et à l'optimisation de performances des systèmes de vélos en libre-service en vue de leur rééquilibrage et leur ordonnancement. Plusieurs méthodes d'optimisation et ont été développées et testées. De telles méthodes incorporent différentes approches de simulation ou d'optimisation comme les réseaux de Petri, les algorithmes génétiques, les algorithmes gloutons, les algorithmes de recherche par voisinage, la méthode arborescente de branch-and-bound, l'élaboration des bornes supérieures et inférieures, etc. Différentes facettes du problème ont été étudiées : le cas statique, le cas dynamique, l'ordonnancement et le rééquilibrage avec un seul (ou multiple) véhicule(s). Afin de montrer la pertinence de nos approches, la thèse comporte également plusieurs applications réelles et expérimentations / In our days, developed countries have to face many public transport problems, including traffic congestion, air pollution, global oil prices and global warming. In this context, Public Bike sharing systems are one of the solutions that have been recently implemented in many big cities around the world. Despite their apparent success, the exploitation and management of such transportation systems imply crucial operational challenges that confronting the operators while few scientific works are available to support such complex dynamical systems. In this context, this thesis addresses the scheduling and balancing in public bicycle-sharing systems. These problems are the most crucial questions for their operational efficiency and economic viability. Bike sharing systems are balanced by distributing bicycles from one station to another. This procedure is generally ensured by using specific redistribution vehicles. Therefore, two hard optimization problems can be considered: finding a best tour for the redistribution vehicles (scheduling) and the determination of the numbers of bicycles to be assigned and of the vehicles to be used (balancing of the stations). In this context, this thesis constitutes a contribution to modelling and optimizing the bicycle sharing systems' performances in order to ensure a coherent scheduling and balancing strategies. Several optimization methods have been proposed and tested. Such methods incorporate different approaches of simulation or optimization like the Petri nets, the genetic algorithms, the greedy search algorithms, the local search algorithms, the arborescent branch-and-bound algorithms, the elaboration of upper and lower bounds, ... Different variants of the problem have been studied: the static mode, the dynamic mode, the scheduling and the balancing by using a single or multiple vehicle(s). In order to demonstrate the coherence and the suitability of our approaches, the thesis contains several real applications and experimentations

L'avènement de l'informatique quantique permet de réétudier les primitives cryptographiques avec une sécurité inconditionnelle, c'est à dire sécurisé même contre des adversaires tout puissants. En 1984, Bennett et Brassard ont construit un protocole quantique de distribution de clé. Dans ce protocole, deux joueurs Alice et Bob coopèrent pour partager une clé secrète inconnue d'une tierce personne Eve. Ce protocole a une sécurité inconditionnelle et n'a pasd'équivalent classique.Dans ma thèse, j'ai étudié les primitives cryptographiques à deux joueurs où ces joueurs ne se font pas confiance. J'étudie principalement le pile ou face quantique et la mise-en-gage quantique de bit. En informatique classique, ces primitivessont réalisables uniquement avec des hypothèses calculatoires, c'est-à-dire en supposant la difficulté d'un problème donné. Des protocoles quantiques ont été construits pour ces primitives où un adversaire peut tricher avec une probabilité constante strictement inférieure à 1, ce qui reste impossible classiquement. Néanmoins, Lo et Chau ont montré l'impossibilité de créer ces primitives parfaitement même en utilisant l'informatique quantique. Il reste donc à déterminer quelles sont les limites physiques de ces primitives.Dans une première partie, je construis un protocole quantique de pile ou face où chaque joueur peut tricher avec probabilité au plus 1/racine(2) + eps pour tout eps > 0. Ce résultat complète un résultat de Kitaev qui dit que dans un jeu de pile ou face quantique, un joueur peut toujours tricher avec probabilité au moins 1/racine(2). J'ai également construit un protocole de mise-en-gage de bit quantique optimal où un joueur peut tricher avec probabilité au plus 0,739 + eps pour tout eps > 0 puis ai montré que ce protocole est en fait optimal. Finalement, j'ai dérivé des bornes inférieures et supérieures pour une autre primitive: la transmission inconsciente, qui est une primitive universelle.Dans une deuxième partie, j'intègre certains aspects pratiques dans ces protocoles. Parfois les appareils de mesure ne donnent aucun résultat, ce sont les pertes dans la mesure. Je construis un protocole de lancer de pièce quantique tolérant aux pertes avec une probabilité de tricher de 0,859. Ensuite, j'étudie le modèle dispositif-indépendant où on ne suppose plus rien sur les appareils de mesure et de création d'état quantique.Finalement, dans une troisième partie, j'étudie ces primitives cryptographiques avec un sécurité computationnelle. En particulier, je fais le lien entre la mise en gage de bit quantique et les protocoles zero-knowledge quantiques. / Quantum computing allows us to revisit the study of quantum cryptographic primitives with information theoretic security. In 1984, Bennett and Brassard presented a protocol of quantum key distribution. In this protocol, Alice and Bob cooperate in order to share a common secret key k, which has to be unknown for a third party that has access to the communication channel. They showed how to perform this task quantumly with an information theoretic security; which is impossible classically.In my thesis, I study cryptographic primitives with two players that do not trust each other. I study mainly coin flipping and bit commitment. Classically, both these primitives are impossible classically with information theoretic security. Quantum protocols for these primitives where constructed where cheating players could cheat with probability stricly smaller than 1. However, Lo, Chau and Mayers showed that these primitives are impossible to achieve perfectly even quantumly if one requires information theoretic security. I study to what extent imperfect protocols can be done in this setting.In the first part, I construct a quantum coin flipping protocol with cheating probabitlity of 1/root(2) + eps for any eps > 0. This completes a result by Kitaev who showed that in any quantum coin flipping protocol, one of the players can cheat with probability at least 1/root(2). I also constructed a quantum bit commitment protocol with cheating probability 0.739 + eps for any eps > 0 and showed that this protocol is essentially optimal. I also derived some upper and lower bounds for quantum oblivious transfer, which is a universal cryptographic primitive.In the second part, I study some practical aspects related to these primitives. I take into account losses than can occur when measuring a quantum state. I construct a Quantum Coin Flipping and Quantum Bit Commitment protocols which are loss-tolerant and have cheating probabilities of 0.859. I also construct these primitives in the device independent model, where the players do not trust their quantum device. Finally, in the third part, I study these cryptographic primitives with information theoretic security. More precisely, I study the relationship between computational quantum bit commitment and quantum zero-knowledge protocols.

Dans cette thèse, nous étudions le spectre conforme d'une surface fermée et le spectre de Steklov conforme d'une surface compacte à bord et leur application à la géométrie conforme et à la topologie. Soit (Σ, c) une surface fermée munie d'une classe conforme c. Alors la k-ième valeur propre conforme est définie comme Λ_k(Σ,c)=sup{λ_k(g) Aire(Σ,g)| g ∈ c), où λ_k(g) est la k-ième valeur propre de l'operateur de Laplace-Beltrami de la métrique g sur Σ. Notons que nous commeçons par λ_0(g) = 0. En prennant le supremum sur toutes les classes conformes C sur Σ on obtient l'invariant topologique suivant de Σ: Λ_k(Σ)=sup{Λ_k(Σ,c)| c ∈ C}. D'après l'article [65], les quantités Λ_k(Σ, c) et Λ_k(Σ) sont bien définies. Si une métrique g sur Σ satisfait λ_k(g) Aire(Σ, g) = Λ_k(Σ), alors on dit que g est maximale pour la fonctionnelle λ_k(g) Aire(Σ, g). Dans l'article [73], il a été montré que les métriques maximales pour λ_1(g) Aire(Σ, g) peuvent au pire avoir des singularités coniques. Dans cette thèse nous montrons que les métriques maximales pour les fonctionnelles λ_1(g) Aire(T^2, g) et λ_1(g) Aire(KL, g), où T^2 et KL dénotent le 2-tore et la bouteille de Klein, ne peuvent pas avoir de singularités coniques. Ce résultat découle d'un théorème de classification de classes conformes par des métriques induites d'une immersion minimale ramifiée dans une sphère ronde aussi montré dans cette thèse. Un autre invariant que nous étudions dans cette thèse est le k-ième invariant de Friedlander-Nadirashvili défini comme: I_k(Σ) = inf{Λ_k(Σ, c)| c ∈ C}. L'invariant I_1(Σ) a été introduit dans l'article [34]. Dans cette thèse nous montrons que pour toute surface orientable et pour toute surface non-orientable de genre impaire I_k(Σ)=I_k(S^2) et pour toute surface non-orientable de genre paire I_k(RP^2) ≥ I_k(Σ)>I_k(S^2). Ici S^2 et RP^2 dénotent la 2-sphère et le plan projectif. Nous conjecturons que I_k(Σ) sont des invariants des cobordismes des surfaces fermées. Le spectre de Steklov conforme est défini de manière similaire. Soit (Σ, c) une surface compacte à bord non vide ∂Σ, alors les k-ièmes valeurs propres de Steklov conformes sont définies comme: σ*_k(Σ, c)=sup{σ_k(g) Longueur(∂Σ, g)| g ∈ c}, où σ_k(g) est la k-ième valeur propre de Steklov de la métrique g sur Σ. Ici nous supposons que σ_0(g) = 0. De façon similaire au problème fermé, on peut définir les quantités suivantes: σ*_k(Σ)=sup{σ*_k(Σ, c)| c ∈ C} et I^σ_k(Σ)=inf{σ*_k(Σ, c)| c ∈ C}. Les résultats de l'article [16] impliquent que toutes ces quantités sont bien définies. Dans cette thèse on obtient une formule pour la limite de σ*_k(Σ, c_n) lorsque la suite des classes conformes c_n dégénère. Cette formule implique que pour toute surface à bord I^σ_k(Σ)= I^σ_k(D^2), où D^2 dénote le 2-disque. On remarque aussi que les quantités I^σ_k(Σ) sont des invariants des cobordismes de surfaces à bord. De plus, on obtient une borne supérieure pour la fonctionnelle σ^k(g) Longueur(∂Σ, g), où Σ est non-orientable, en terme de son genre et le nombre de composants de bord. / In this thesis, we study the conformal spectrum of a closed surface and the conformal Steklov spectrum of a compact surface with boundary and their application to conformal geometry and topology. Let (Σ,c) be a closed surface endowed with a conformal class c then the k-th conformal eigenvalue is defined as Λ_k(Σ,c)=sup{λ_k(g) Aire(Σ,g)| g ∈ c), where λ_k(g) is the k-th Laplace-Beltrami eigenvalue of the metric g on Σ. Note that we start with λ_0(g) = 0 Taking the supremum over all conformal classes C on Σ one gets the following topological invariant of Σ: Λ_k(Σ)=sup{Λ_k(Σ,c)| c ∈ C}. It follows from the paper [65] that the quantities Λ_k(Σ, c) and Λ_k(Σ) are well-defined. Suppose that for a metric g on Σ the following identity holds λ_k(g) Aire(Σ, g) = Λ_k(Σ). Then one says that the metric g is maximal for the functional λ_k(g) Aire(Σ, g). In the paper [73] it was shown that the maximal metrics for the functional λ_1(g) Aire(Σ, g) at worst can have conical singularities. In this thesis we show that the maximal metrics for the functionals λ_1(g) Aire(T^2, g) and λ_1(g) Aire(KL, g), where T^2 and KL stand for the 2-torus and the Klein bottle respectively, cannot have conical singularities. This result is a corollary of a conformal class classification theorem by metrics induced from a branched minimal immersion into a round sphere that we also prove in the thesis. Another invariant that we study in this thesis is the k-th Friedlander-Nadirashvili invariant defined as: I_k(Σ) = inf{Λ_k(Σ, c)| c ∈ C}. The invariant I_1(Σ) was introduced in the paper [34]. In this thesis we prove that for any orientable surface and any non-orientable surface of odd genus I_k(Σ)=I_k(S^2) and for any non-orientable surface of even genus I_k(RP^2) ≥ I_k(Σ)>I_k(S^2). Here S^2 and RP^2 denote the 2-sphere and the projective plane respectively. We also conjecture that I_k(Σ) are invariants of cobordisms of closed manifolds. The conformal Steklov spectrum is defined in a similar way. Let (Σ, c) be a compact surface with non-empty boundary ∂Σ then the k-th conformal Steklov eigenvalues is defined by the formula: σ*_k(Σ, c)=sup{σ_k(g) Longueur(∂Σ, g)| g ∈ c}, where σ_k(g) is the k-th Steklov eigenvalue of the metric g on Σ. Here we suppose that σ_0(g) = 0. Similarly to the closed problem one can define the following quantities: σ*_k(Σ)=sup{σ*_k(Σ, c)| c ∈ C} and I^σ_k(Σ)=inf{σ*_k(Σ, c)| c ∈ C}. The results of the paper [16] imply that all these quantities are well-defined. In this thesis we obtain a formula for the limit of the k-th conformal Steklov eigenvalue when the sequence of conformal classes degenerates. Using this formula we show that for any surface with boundary I^σ_k(Σ)= I^σ_k(D^2), where D^2 stands for the 2-disc. We also notice that I^σ_k(Σ) are invariants of cobordisms of surfaces with boundary. Moreover, we obtain an upper bound for the functional σ^k(g) Longueur(∂Σ, g), where Σ is non-orientable, in terms of its genus and the number of boundary components.