Le co-clustering est une technique de classification consistant à réaliser une partition simultanée des lignes et des colonnes d'une matrice de données. Parmi les approches existantes, MODL permet de traiter des données volumineuses et de réaliser une partition de plusieurs variables, continues ou nominales. Nous utilisons cette approche comme référence dans l'ensemble des travaux de la thèse et montrons la diversité des problèmes de data mining pouvant être traités, comme le partitionnement de graphes, de graphes temporels ou encore le clustering de courbes. L'approche MODL permet d'obtenir des résultats fins sur des données volumineuses, ce qui les rend difficilement interprétables. Des outils d'analyse exploratoire sont alors nécessaires pour les exploiter. Afin de guider l'utilisateur dans l'interprétation de tels résultats, nous définissons plusieurs outils consistant à simplifier des résultats fins afin d'en avoir une interprétation globale, à détecter les clusters remarquables, à déterminer les valeurs représentatives de leurs clusters et enfin à visualiser les résultats. Les comportements asymptotiques de ces outils d'analyse exploratoire sont étudiés afin de faire le lien avec les approches existantes. Enfin une application sur des comptes-rendus d'appels de l'opérateur Orange, collectés en Côte d'Ivoire, montre l'intérêt de l'approche et des outils d'analyse exploratoire dans un contexte industriel.

La théorie de l'information quantique étudie les limites fondamentales qu'imposent les lois de la physique sur les tâches de traitement de données comme la compression et la transmission de données sur un canal bruité. Cette thèse présente des techniques générales permettant de résoudre plusieurs problèmes fondamentaux de la théorie de l'information quantique dans un seul et même cadre. Le théorème central de cette thèse énonce l'existence d'un protocole permettant de transmettre des données quantiques que le receveur connaît déjà partiellement à l'aide d'une seule utilisation d'un canal quantique bruité. Ce théorème a de plus comme corollaires immédiats plusieurs théorèmes centraux de la théorie de l'information quantique. Les chapitres suivants utilisent ce théorème pour prouver l'existence de nouveaux protocoles pour deux autres types de canaux quantiques, soit les canaux de diffusion quantiques et les canaux quantiques avec information supplémentaire fournie au transmetteur. Ces protocoles traitent aussi de la transmission de données quantiques partiellement connues du receveur à l'aide d'une seule utilisation du canal, et ont comme corollaires des versions asymptotiques avec et sans intrication auxiliaire. Les versions asymptotiques avec intrication auxiliaire peuvent, dans les deux cas, être considérées comme des versions quantiques des meilleurs théorèmes de codage connus pour les versions classiques de ces problèmes. Le dernier chapitre traite d'un phénomène purement quantique appelé verrouillage: il est possible d'encoder un message classique dans un état quantique de sorte qu'en lui enlevant un sous-système de taille logarithmique par rapport à sa taille totale, on puisse s'assurer qu'aucune mesure ne puisse avoir de corrélation significative avec le message. Le message se trouve donc «verrouillé» par une clé de taille logarithmique. Cette thèse présente le premier protocole de verrouillage dont le critère de succès est que la distance trace entre la distribution jointe du message et du résultat de la mesure et le produit de leur marginales soit suffisamment petite. / Quantum information theory studies the fundamental limits that physical laws impose on information processing tasks such as data compression and data transmission on noisy channels. This thesis presents general techniques that allow one to solve many fundamental problems of quantum information theory in a unified framework. The central theorem of this thesis proves the existence of a protocol that transmits quantum data that is partially known to the receiver through a single use of an arbitrary noisy quantum channel. In addition to the intrinsic interest of this problem, this theorem has as immediate corollaries several central theorems of quantum information theory. The following chapters use this theorem to prove the existence of new protocols for two other types of quantum channels, namely quantum broadcast channels and quantum channels with side information at the transmitter. These protocols also involve sending quantum information partially known by the receiver with a single use of the channel, and have as corollaries entanglement-assisted and unassisted asymptotic coding theorems. The entanglement-assisted asymptotic versions can, in both cases, be considered as quantum versions of the best coding theorems known for the classical versions of these problems. The last chapter deals with a purely quantum phenomenon called locking. We demonstrate that it is possible to encode a classical message into a quantum state such that, by removing a subsystem of logarithmic size with respect to its total size, no measurement can have significant correlations with the message. The message is therefore "locked" by a logarithmic-size key. This thesis presents the first locking protocol for which the success criterion is that the trace distance between the joint distribution of the message and the measurement result and the product of their marginals be sufficiently small.

Cette thèse rassemble trois travaux sur la complexité d'information et sur la complexité en requête quantique. Ces domaines d'études ont pour points communs les outils mathématiques pour étudier ces complexités, c'est-à-dire les problèmes d'optimisation.Les deux premiers travaux concernent le domaine de la complexité en requête quantique, en généralisant l'important résultat suivant: dans l'article cite{LMRSS11}, leurs auteurs parviennent à caractériser la complexité en requête quantique, à l'aide de la méthode par adversaire, un programme semi-définie positif introduit par A. Ambainis dans cite{Ambainis2000}. Cependant, cette caractérisation est restreinte aux modèles à temps discret, avec une erreur bornée. Ainsi, le premier travail consiste à généraliser leur résultat aux modèles à temps continu, tandis que le second travail est une démarche, non aboutie, pour caractériser la complexité en requête quantique dans le cas exact et pour erreur non bornée.Dans ce premier travail, pour caractériser la complexité en requête quantique aux modèles à temps discret, nous adaptons la démonstration des modèles à temps discret, en construisant un algorithme en requête adiabatique universel. Le principe de cet algorithme repose sur le théorème adiabatique cite{Born1928}, ainsi qu'une solution optimale du dual de la méthode par adversaire. À noter que l'analyse du temps d'exécution de notre algorithme adiabatique est basée sur preuve qui ne nécessite pas d'écart dans le spectre de l'Hamiltonien.Dans le second travail, on souhaite caractériser la complexité en requête quantique pour une erreur non bornée ou nulle. Pour cela on reprend et améliore la méthode par adversaire, avec une approche de la mécanique lagrangienne, dans laquelle on construit un Lagrangien indiquant le nombre de requêtes nécessaires pour se déplacer dans l'espace des phases, ainsi on peut définir l'``action en requête''. Or ce lagrangien s'exprime sous la forme d'un programme semi-defini, son étude classique via les équations d'Euler-Lagrange nécessite l'utilisation du théorème de l'enveloppe, un puissant outils d'économathématiques. Le dernier travail, plus éloigné, concerne la complexité en information (et par extension la complexité en communication) pour simuler des corrélations non-locales. Ou plus précisement la quantitié d'information (selon Shannon) que doive s'échanger deux parties pour obtenir ses corrélations. Dans ce but, nous définissons une nouvelle complexité, denommée la zero information complexity IC_0, via le modèle sans communication. Cette complexité a l'avantage de s'exprimer sous la forme d'une optimization convexe. Pour les corrélations CHSH, on résout le problème d'optimisation pour le cas à une seule direction où nous retrouvons un résultat connu. Pour le scénario à deux directions, on met numériquement en évidence la validité de cette borne, et on résout une forme relaxée de IC_0 qui est un nouveau résultat. / Doctorat en Sciences de l'ingénieur et technologie / info:eu-repo/semantics/nonPublished

Ce mémoire présente quelques résultats récents sur les codes identifiants. La thèse est structurée en cinq chapitres. Le Chapitre 1 contient les définitions et présente la notion de code identifiant. Dans le Chapitre 2 nous étudions l'aspect algorithmique des codes identifiants. Le Chapitre 3 contient quelques résultats concernant des classes de graphes particulières, à savoir les hypercubes, les grilles, et les cycles. Nous étudions quelques questions extrémales au Chapitre 4. Enfin, le Chapitre 5 présente quelques résultats récents sur les codes identifiants dans les graphes aléatoires. A la fin du document nous résumons les résultats les plus importants que nous avons présentés et nous donnons quelques problèmes ouverts sur le sujet.

Cette thèse regroupe des travaux concernant le biais d'usage de codons et son rôle chez les bactéries et leurs phages, en particulier sur les processus de traduction et l'organisation des génomes bactériens. Après une introduction portant sur i) la traduction chez les procaryotes, et ii) les techniques de classification et leurs liens avec la théorie de l'information, un nouvel algorithme de partition d'un ensemble de gènes en fonction de leur usage de codons est présenté. Son application aux génomes d'E. coli et de B. subtilis permet de mettre en évidence plusieurs phénomènes. Le génome de ces organismes se décompose respectivement en 4 et 5 groupes de gènes ayant des usages de codons distincts. Les gènes du même groupe tendent à partager des fonctions similaires, et sont organisés sur le chromosome en domaines cohérents d'une longueur de 10 à 15 gènes. Cette organisation non triviale pourrait permettre une régulation de la vitesse de traduction des gènes en fonction de leur similarité avec leur environnement génétique. <br />Dans la seconde partie le biais de codons et le contenu en ARN de transfert (ARNt) de bactériophages sont analysés, comparativement à ceux de leurs hôtes. L'étude statistique montre que le contenu en ARNt des phages n'est pas aléatoire, mais biaisé en faveur d'ARNt complémentaires aux codons fréquents dans le génome du phage. Un modèle d'équation maîtresse montre que cette distribution des ARNt au sein des génomes de phages pourrait être le résultat de deux processus : l'acquisition aléatoire par le phage d'ARNt, parmi ceux de l'hôte, et la perte préférentielle des ARNt correspondants à des codons moins utilisés par le phage que par son hôte. Un tel mécanisme permettrait au phage de s'adapter en ne conservant au final que les ARNt présents en quantité insuffisante chez son hôte pendant l'infection. Finalement, on observe plus d'ARNt chez les phages lytiques que chez les tempérés, laissant supposer que les processus de traduction sont soumis à une plus forte pression de sélection chez eux.

La théorie de l'information quantique étudie les limites fondamentales qu'imposent les lois de la physique sur les tâches de traitement de données comme la compression et la transmission de données sur un canal bruité. Cette thèse présente des techniques générales permettant de résoudre plusieurs problèmes fondamentaux de la théorie de l'information quantique dans un seul et même cadre. Le théorème central de cette thèse énonce l'existence d'un protocole permettant de transmettre des données quantiques que le receveur connaît déjà partiellement à l'aide d'une seule utilisation d'un canal quantique bruité. Ce théorème a de plus comme corollaires immédiats plusieurs théorèmes centraux de la théorie de l'information quantique. Les chapitres suivants utilisent ce théorème pour prouver l'existence de nouveaux protocoles pour deux autres types de canaux quantiques, soit les canaux de diffusion quantiques et les canaux quantiques avec information supplémentaire fournie au transmetteur. Ces protocoles traitent aussi de la transmission de données quantiques partiellement connues du receveur à l'aide d'une seule utilisation du canal, et ont comme corollaires des versions asymptotiques avec et sans intrication auxiliaire. Les versions asymptotiques avec intrication auxiliaire peuvent, dans les deux cas, être considérées comme des versions quantiques des meilleurs théorèmes de codage connus pour les versions classiques de ces problèmes. Le dernier chapitre traite d'un phénomène purement quantique appelé verrouillage: il est possible d'encoder un message classique dans un état quantique de sorte qu'en lui enlevant un sous-système de taille logarithmique par rapport à sa taille totale, on puisse s'assurer qu'aucune mesure ne puisse avoir de corrélation significative avec le message. Le message se trouve donc «verrouillé» par une clé de taille logarithmique. Cette thèse présente le premier protocole de verrouillage dont le critère de succès est que la distance trace entre la distribution jointe du message et du résultat de la mesure et le produit de leur marginales soit suffisamment petite. / Quantum information theory studies the fundamental limits that physical laws impose on information processing tasks such as data compression and data transmission on noisy channels. This thesis presents general techniques that allow one to solve many fundamental problems of quantum information theory in a unified framework. The central theorem of this thesis proves the existence of a protocol that transmits quantum data that is partially known to the receiver through a single use of an arbitrary noisy quantum channel. In addition to the intrinsic interest of this problem, this theorem has as immediate corollaries several central theorems of quantum information theory. The following chapters use this theorem to prove the existence of new protocols for two other types of quantum channels, namely quantum broadcast channels and quantum channels with side information at the transmitter. These protocols also involve sending quantum information partially known by the receiver with a single use of the channel, and have as corollaries entanglement-assisted and unassisted asymptotic coding theorems. The entanglement-assisted asymptotic versions can, in both cases, be considered as quantum versions of the best coding theorems known for the classical versions of these problems. The last chapter deals with a purely quantum phenomenon called locking. We demonstrate that it is possible to encode a classical message into a quantum state such that, by removing a subsystem of logarithmic size with respect to its total size, no measurement can have significant correlations with the message. The message is therefore "locked" by a logarithmic-size key. This thesis presents the first locking protocol for which the success criterion is that the trace distance between the joint distribution of the message and the measurement result and the product of their marginals be sufficiently small.

Dans ce mémoire, j'examine différents aspects d'un objet simple mais omniprésent en informatique: la séquence de symboles (appelée selon le contexte mot ou chaîne de caractères). La notion de mot est au carrefour de domaines comme la théorie de l'information et la théorie des langages. S'il est simple, il reste fondamental: nous n'avons, au plus bas niveau, que cela à disposition puisqu'il arrive toujours un moment où une donnée doit être encodée en symboles stockables en mémoire. La quantité d'information croissante de données mise à disposition et qu'on peut stocker, par exemple des génomes d'individus ou des documents numérisés, justifie que les algorithmes et les structures de données qui les manipulent soient optimisés. En conséquence, les besoins d'analyse se font sentir pour guider le choix et la conception des programmes qui manipulent ces données. L'analyse en moyenne est ici particulièrement adaptée puisque les données atteignent une variété et des volumes tellement importants que c'est le cas typique qui traduit le mieux la complexité et non pas le cas le pire. Cela évidemment pose le problème de la modélisation de données qui reste encore très épineux. En effet on souhaite deux choses contradictoires: un modèle au plus près des données, qui traduise vraiment leurs spécificités, mais aussi un modèle permettant de donner des résultats, c'est-à-dire de prédire les performances (et on comprend vite que le modèle doit donc rester relativement simple pour qu'il subsiste un espoir de le traiter!). Les méthodes sont le plus souvent celles de la combinatoire analytique et font appel à un objet mathématique, les séries génératrices, pour mener les analyses à bien.

Doctorat en philosophie et lettres / info:eu-repo/semantics/nonPublished

Cette thèse porte sur la conception de contrôleurs pour robots explorateurs autonomes basée sur une approche en ligne (online) intégrée, ne nécessitant pas de vérité terrain ni d'intervention de l'expert humain au cours du processus d'entrainement.Le travail présenté se focalise sur le domaine de la robotique autonome et plus particulièrement la conception de controleurs robotiques pour les essaims de robots.Ce contexte présente deux difficultés spécifiques. Premièrement, les approches basées sur l'usage de simulateur sont d'efficacité limitée : d'une part, la précision du simulateur est limitée compte tenu de la variabilité des robots élémentaires; d'autre part, la complexité de la simulation est super-linéaire en fonction du nombre de robots de l'essaim. Deuxièmement, les approches guidées par le but se heurtent au fait que la fonction objectif n'est pas définie au niveau du robot individuel, mais au niveau de l'essaim.Une première étape vers la conception de contrôleur explorateur autonome est proposée dans cette thèse. L'approche proposée, appelée exploration robotique fondée sur l'évolution et l'information (Ev-ITER) se fonde sur l'hybridation de la robotique évolutionnaire et de l'apprentissage par renforcement utilisant l'entropie. Cette approche procède en deux phases: (i) dans une première phase l'évolution artificielle est utilisée pour générer des contrôleurs primaires (crawlers), dont les trajectoires sont d'entropie élevée dans l'espace sensori-moteur; (ii) dans une seconde phase, l'archive des trajectoires acquises par les controleurs primaires est exploitée pour définir les controleurs secondaires, inspirés de la motivation intrinsèque robuste et permettant l'exploration rigoureuse de l'environnement.Les contributions de cette thèse sont les suivantes. Premièrement, comme désiré Ev-ITER peut être lancé en ligne, et sans nécessiter de vérité terrain ou d'assistance. Deuxièmement, Ev-ITER surpasse les approches autonomes en robotique évolutionnaire en terme d'exploration de l'arène. Troisièmement, le contrôleur Ev-ITER est doté d'une certaine généralité, dans la mesure où il est capable d'explorer efficacement d'autres arènes que celle considérée pendant la première phase de l'évolution. Il est à souligner que la généralité du contrôleur appris vis-à-vis de l'environnement d'entrainement a rarement été considérée en apprentissage par renforcement ou en robotique évolutionnaire. / This thesis is concerned with building autonomous exploratory robotic controllers in an online, on-board approach, with no requirement for ground truth or human intervention in the experimental setting.This study is primarily motivated by autonomous robotics, specifically autonomous robot swarms. In this context, one faces two difficulties. Firstly, standard simulator-based approaches are hardly effective due to computational efficiency and accuracy reasons. On the one hand, the simulator accuracy is hindered by the variability of the hardware; on the other hand, this approach faces a super-linear computational complexity w.r.t. the number of robots in the swarm. Secondly, the standard goal-driven approach used for controller design does not apply as there is no explicit objective function at the individual level, since the objective is defined at the swarm level.A first step toward autonomous exploratory controllers is proposed in the thesis. The Evolution & Information Theory-based Exploratory Robotics (Ev-ITER) approach is based on the hybridization of two approaches stemming from Evolutionary Robotics and from Reinforcement Learning, with the goal of getting the best of both worlds: (i) primary controllers, or crawling controllers, are evolved in order to generate sensori-motor trajectories with high entropy; (ii) the data repository built from the crawling controllers is exploited, providing prior knowledge to secondary controllers, inspired from the intrinsic robust motivation setting and achieving the thorough exploration of the environment.The contributions of the thesis are threefold. Firstly, Ev-ITER fulfills the desired requirement: it runs online, on-board and without requiring any ground truth or support. Secondly, Ev-ITER outperforms both the evolutionary and the information theory-based approaches standalone, in terms of actual exploration of the arena. Thirdly and most importantly, the Ev-ITER controller features some generality property, being able to efficiently explore other arenas than the one considered during the first evolutionary phase. It must be emphasized that the generality of the learned controller with respect to the considered environment has rarely been considered, neither in the reinforcement learning, nor in evolutionary robotics.

Cette thèse est consacrée à l'étude des mesures convexes ainsi qu'aux analogies entre la théorie de Brunn-Minkowski et la théorie de l'information. Je poursuis les travaux de Costa et Cover qui ont mis en lumière des similitudes entre deux grandes théories mathématiques, la théorie de Brunn-Minkowski d'une part et la théorie de l'information d'autre part. Partant de ces similitudes, ils ont conjecturé, comme analogue de la concavité de l'entropie exponentielle, que la racine n-ième du volume parallèle de tout ensemble compact de $R^n$ est une fonction concave, et je résous cette conjecture de manière détaillée. Par ailleurs, j'étudie les mesures convexes définies par Borell et je démontre pour ces mesures une inégalité renforcée de type Brunn-Minkowski pour les ensembles convexes symétriques. Cette thèse se décompose en quatre parties. Tout d'abord, je rappelle un certain nombre de notions de base. Dans une seconde partie, j'établis la validité de la conjecture de Costa-Cover sous certaines conditions et je démontre qu'en toute généralité, cette conjecture est fausse en exhibant des contre-exemples explicites. Dans une troisième partie, j'étends les résultats positifs de cette conjecture de deux manières, d'une part en généralisant la notion de volume et d'autre part en établissant des versions fonctionnelles. Enfin, je prolonge des travaux récents de Gardner et Zvavitch en améliorant la concavité des mesures convexes sous certaines hypothèses telles que la symétrie / This thesis is devoted to the study of convex measures as well as the relationships between the Brunn-Minkowski theory and the Information theory. I pursue the works by Costa and Cover who highlighted similarities between two fundamentals inequalities in the Brunn-Minkowski theory and in the Information theory. Starting with these similarities, they conjectured, as an analogue of the concavity of entropy power, that the n-th root of the parallel volume of every compact subset of $R^n$ is concave, and I give a complete answer to this conjecture. On the other hand, I study the convex measures defined by Borell and I established for these measures a refined inequality of the Brunn-Minkowski type if restricted to convex symmetric sets. This thesis is split in four parts. First, I recall some basic facts. In a second part, I prove the validity of the conjecture of Costa-Cover under special conditions and I show that the conjecture is false in such a generality by giving explicit counterexamples. In a third part, I extend the positive results of this conjecture by extending the notion of the classical volume and by establishing functional versions. Finally, I generalize recent works of Gardner and Zvavitch by improving the concavity of convex measures under different kind of hypothesis such as symmetries