Une caractéristique contraignante de la complexité de Kolmogorov-Chaitin (dénotée dans ce chapitre par K) est qu'elle n'est pas calculable à cause du problème de l'arrêt, ce qui limite son domaine d'application. Une autre critique concerne la dépendance de K à un langage particulier ou une machine de Turing universelle particulière, surtout pour les suites assez courtes, par exemple, plus courtes que les longueurs typiques des compilateurs des langages de programmation. En pratique, on peut obtenir une approximation de K(s), grâce à des méthodes de compression. Mais les performances de ces méthodes de compression s'écroulent quand il s'agit des suites courtes. Pour les courtes suites, approcher K(s) par des méthodes de compression ne fonctionne pas. On présente dans cet thèse une approche empirique pour surmonter ce problème. Nous proposons une méthode "naturelle" qui permet d'envisager une définition plus stable de la complexité de Kolmogorov-Chaitin K(s) via la mesure de probabilité algorithmique m(s). L'idée est de faire fonctionner une machine universelle en lui donnant un programme au hasard pour calculer expérimentalement la probabilité m(s) (la probabilité de produire s), pour ensuite évaluer numériquement K(s) de manière alternative aux méthodes des algorithmes de compression. La méthode consiste à : (a) faire fonctionner des machines de calcul (machines de Turing, automates cellulaires) de façon systématique pour produire des suites (b) observer quelles sont les distributions de probabilité obtenues et puis (c) obtenir K(s) à partir de m(s) par moyen du théorème de codage de Levin-Chaitin. / In practice, it is a known problem that one cannot compress short strings, shorter, for example, than the length in bits of the compression program which is added to the compressed version of s, making the result (the program producing s) sensitive to the compressor choice and the parameters involved. However, short strings are quite often the kind of data encountered in many practical settings. While compressors' asymptotic behavior guarantees the eventual convergence to K(s) thanks to the invariance theorem, measurements differ considerably in the domain of short strings. We describe a method that combines several theoretical and experimental results to numerically approximate the algorithmic (Kolmogorov-Chaitin) complexity of short bit strings. This is done by an exhaustive execution of abstract machines for which the halting times are known thanks to the Busy Beaver problem. An output frequency distribution is then computed, from which the algorithmic probability is calculated and the algorithmic complexity evaluated by way of the (Levin-Chaitin) coding theorem. The approach we adopt here is different and independent of the machine size (small machines are used only because they allow us to calculate all of them up to a small size) and relies only on the concept of algorithmic probability. The result is a novel approach that we put forward for numerically calculate the complexity of short strings as an alternative to the indirect method using compression algorithms.

Notre travail sur le partage de secret se base sur les points de vue théoriques de la Théorie de l'Information de Shannon et de la Complexité de Kolmogorov. Nous allons expliquer comment ces trois sujets intimement liés.Les inégalité d'information jouent un rôle centrale dans ce manuscrit. Ce sont les inégalités pour l'entropie de Shannon, mais correspondent aussi aux inégalités pour la complexité de Kolmogorov.La complexité de Kolmogorov formalise l'idée d'aléatoire pour les chaînes de caractère. Ce sont là deux raisons qui justifient à elles seules la notion de partage de secret algorithmique dans le cadre de la Théorie Algorithmique de l'information (si l'on sait partager un secret aléatoire, on peut partager n'importe quel secret).Originalement étudié par sa définition combinatoire, le partage de secret a été plus tard généralisé par sa formulation par les quantités définies dans la théorie de l'information. Cette étape a permis l'utilisation des inégalités d'information et s'est révélée très importante dans la caractérisation desschémas de partage de secret efficaces.L'étude des inégalités d'information n'en est qu'à ses débuts. Nous y contribuons en introduisant la notion d'inégalité essentiellement conditionnelles, qui montre une fois de plus que ces inégalités ne sont pas encore complètement comprises. / Our work deals with secret sharing in the theoretical point of views of Shannon's Information Theory and Kolmogorov's Algorithmic Information Theory. We are going to explain how these three subjects are naturally deeply intertwined.Information inequalities play a central role in this text. They are the inequalities for Shannon entropy, but also they are in exact correspondence with the inequalities for Kolmogorov complexity. Kolmogorov complexity formalizes the idea of randomness for strings.These two reasons alone justify to consider the notion of secret sharing in the Algorithmic framework (if one can share a random secret one can share anything).Originally, secret sharing was first studied under the combinatorial lens, only later was it more generally formalized using information-theoretic measures. This step allowed the use of information inequalities which revealed to bevery important to understand the existence of secret-sharing schemes with respect to efficiency.The investigation of information inequalities is at its debut. We contribute to the subject by introducing the notion of essentially conditional inequalities, which shows once again that information inequalities are yet not fully understood.

Cette thèse est une contribution à l'étude des différentes notions effectives d'aléatoire pour les objets individuels (essentiellement les suites binaires finies ou finies). Dans le premier chapitre nous considérons les approches de l'aléatoire par la théorie des jeux (martingales et stratégies) que nous comparons à l'approche historique par les fréquences qui remonte au début du 20ème siècle avec les travaux de von Mises. Le résultat principal de ce chapitre est une relation explicite entre la vitesse de gain d'une martingale (ou stratégie) sur une suite binaire et le biais des sous-suites extraites. Le second chapitre porte sur les liens existant entre les différentes définitions de l'aléatoire pour les suites binaires infinies et la notion de complexité de Kolmogorov, définie comme étant la taille du plus court programme qui génère un objet donné. De nombreux résultats sont déjà connus dans ce domaine. Nous présentons une approche nouvelle, en utilisant non pas la complexité de Kolmogorov elle-même, mais ses bornes supérieures calculables. Cette approche est unificatrice, en ce sens qu'elle permet de caractériser précisément une grande variété de notions d'aléatoire, dont certaines pour qui la complexité de Kolmogorov échoue. Le troisième et dernier chapitre étudie l'extension des notions effectives d'aléatoire à des mesures de probabilité calculables quelconques, et plus particulièrement les relations d'équivalence qu'elles induisent sur ces mesures (où deux mesures sont équivalentes si elles ont les mêmes éléments aléatoires). Une preuve constructive (par les martingales) du théorème de Kakutani (qui caractérise l'équivalence entre les mesures de Bernoulli généralisées) y est notamment obtenue. Enfin, nous discutons en toute généralité (c'est-à-dire pour des mesures quelconques) les relations d'équivalence induites, dont nous donnons une classification complète.

L'objectif général de cette thèse est d'étudier les notions d'aléatoire et d'information algorithmiques - jusqu'ici restreints aux espaces symboliques - sur des espaces plus généraux, précisément les espaces métriques calculables, et d'appliquer ces notions à la théorie des systèmes dynamiques. Les principaux apports sont : (1) le développement d'un cadre robuste pour l'étude d'objets mathématiques (mesures de probabilité, systèmes dynamiques et leurs modèles symboliques) d'un point de vue algorithmique, notamment l'introduction et l'étude détaillée des treillis d'énumération effective; (2) l'extension de l'aléatoire algorithmique aux espaces métriques calculables, améliorant ainsi l'extension menée par Gacs qui imposait une condition supplémentaire à l'espace, et l'étude de quelques notions des probabilités classiques du point de vue de l'aléatoire; (3) un apport à la théorie des systèmes dynamiques, établissant des relations entre l'aléatoire algorithmique et l'aléatoire dynamique. Nous étudions notamment deux notions de complexité algorithmique des orbites, l'une K1 utilisant la mesure, l'autre K2 inspirée du point de vue topologique. Nous montrons que la complexité K1 des orbites partant des points aléatoires est l'entropie du système au sens de la mesure, que la borne supérieure des complexités K2 des orbites est l'entropie topologique, et que K1 et K2 coïncident pour les points aléatoires. Ce travail enrichit les résultats de Brudno et White.

Les méthodes classiques d'apprentissage automatique reposent souvent sur une hypothèse simple mais restrictive: les données du passé et du présent sont générées selon une même distribution. Cette hypothèse permet de développer directement des garanties théoriques sur la précision de l'apprentissage. Cependant, elle n'est pas réaliste dans un grand nombre de domaines applicatifs qui ont émergé au cours des dernières années.Dans cette thèse, nous nous intéressons à quatre problèmes différents en intelligence artificielle, unis par un point commun: tous impliquent un transfer de connaissance d'un domaine vers un autre. Le premier problème est le raisonnement par analogie et s'intéresse à des assertions de la forme "A est à B ce que C est à D". Le second est l'apprentissage par transfert et se concentre sur des problèmes de classification dans des contextes où les données d'entraînement et de test ne sont pas de même distribution (ou n'appartiennent même pas au même espace). Le troisième est l'apprentissage sur flux de données, qui prend en compte des données apparaissant continument une à une à haute fréquence, avec des changements de distribution. Le dernier est le clustering collaboratif et consiste à faire échanger de l'information entre algorithmes de clusterings pour améliorer la qualité de leurs prédictions.La principale contribution de cette thèse est un cadre général pour traiter les problèmes de transfer. Ce cadre s'appuie sur la notion de complexité de Kolmogorov, qui mesure l'information continue dans un objet. Cet outil est particulièrement adapté au problème de transfert, du fait qu'il ne repose pas sur la notion de probabilité tout en étant capable de modéliser les changements de distributions.En plus de cet effort de modélisation, nous proposons dans cette thèse diverses discussions sur d'autres aspects ou applications de ces problèmes. Ces discussions s'articulent autour de la possibilité de transfert dans différents domaines et peuvent s'appuyer sur d'autres outils que la complexité. / Classical learning methods are often based on a simple but restrictive assumption: The present and future data are generated according to the same distributions. This hypothesis is particularly convenient when it comes to developing theoretical guarantees that the learning is accurate. However, it is not realistic from the point of view of applicative domains that have emerged in the last years.In this thesis, we focus on four distinct problems in artificial intelligence, that have mainly one common point: All of them imply knowledge transfer from one domain to the other. The first problem is analogical reasoning and concerns statements of the form "A is to B as C is to D". The second one is transfer learning and involves classification problem in situations where the training data and test data do not have the same distribution (nor even belong to the same space). The third one is data stream mining, ie. managing data that arrive one by one in a continuous and high-frequency stream with changes in the distributions. The last one is collaborative clustering and focuses on exchange of information between clustering algorithms to improve the quality of their predictions.The main contribution of this thesis is to present a general framework to deal with these transfer problems. This framework is based on the notion of Kolmogorov complexity, which measures the inner information of an object. This tool is particularly adapted to the problem of transfer, since it does not rely on probability distributions while being able to model the changes in the distributions.Apart from this modeling effort, we propose, in this thesis, various discussions on aspects and applications of the different problems of interest. These discussions all concern the possibility of transfer in multiple domains and are not based on complexity only.

L'assimilation du contenu informatif à la complexité de calcul a plus de 50 ans, mais une manière d'exploiter pratiquement cette idée est venue plus récemment, avec la définition de mesures de similarité basées sur la compression des données, qui permettent d'estimer la quantité d'information partagée entre deux objets. Ces techniques sont effectivement utilisées dans des applications sur divers types de données avec une approche universelle et pratiquement sans paramètres. Toutefois, les difficultés de les appliquer à des grands ensembles de données ont été rarement abordées. Cette thèse propose une nouvelle mesure de similarité basée sur la compression des dictionnaires qui est plus rapide comparativement aux solutions connues, sans perte de performance. Cela augmente l'applicabilité de ces notions, ce qui permet de les tester sur des ensembles de données de taille jusqu'à 100 fois plus grande que ceux précédemment analysés dans la littérature. Ces résultats ont été obtenus par l'étude des relations entre la théorie du codage classique, la compression des données et la notion de complexité par Kolmogorov. Les objets sont décomposés dans un dictionnaire, qui est considéré comme un ensemble de règles pour générer un code ayant une signification sémantique de la structure de l'image: les dictionnaires extraits décrivent les régularités des données, et sont comparés pour estimer l'information partagée entre deux objets. Cela permet de définir un système de recherche des images qui nécessite une supervision minimale par l'utilisateur, car il saute les étapes d'extraction de caractéristiques typiques, souvent dépendantes de paramètres. Ainsi, les hypothèses subjectives qui peuvent fausser l'analyse sont enlevées, et a leur place une approche guidée par les données est adoptée. Diverses applications sont présentées, et ces méthodes sont employées sans aucun changement des paramètres à différents types de données: photographies numériques, images radar, textes, génomes d'ADN, et signaux sismiques.

La complexité de la communication a été introduite en 1979 par Andrew Chi-Chi Yao. Elle est depuis devenue l'un des modèles de calcul les plus étudiés. L'objectif de celle-ci est d'étudier des problèmes dont les entrées sont distribuées entre plusieurs joueurs, en quantifiant la communication que ceux-ci doivent échanger. Nous utilisons d'abord la complexité de Kolmogorov, une caractérisation algorithmique de l'aléatoire, pour prouver des bornes inférieures sur la complexité de la communication. Notre méthode constitue une généralisation de la méthode d'incompressibilité. L'avantage de cette approche est de mettre en valeur la nature combinatoire des preuves. Nous étudions ensuite la simulation des distributions de probabilité causales avec de la communication. Ce modèle généralise la complexité de la communication traditionnelle et comprend en particulier les distributions quantiques. Nous montrons pour ce problème des bornes inférieures et supérieures. Dans le cas des fonctions booléennes, la borne inférieure que nous proposons est équivalente aux normes de factorisation, une puissante méthode introduite par Linial et Shraibman en 2006. Enfin, nous étudions la complexité en boîte non-locale. Cette ressource a été introduite par Popescu et Rohrlich pour étudier la non-localité. Le problème est de quantifier le nombre de boîtes nécessaire et suffisant pour calculer une fonction ou simuler une distributions. Nous donnons encore des bornes inférieures et supérieures pour ces problèmes, ainsi que des applications à l'évaluation sécurisée, un problème cryptographique très important.

Nous avons développé un cryptosystème à clé symétrique hautement sécuritaire qui est basé sur un réseau de substitutions et de permutations. Il possède deux particularités importantes. Tout d'abord, il utilise de très grandes S-Boxes incompressibles dont la taille peut varier entre 256 Kb et 32 Gb bits d'entrée et qui sont générées aléatoirement. De plus, la phase de permutation est effectuée par un ensemble de fonctions linéaires choisies aléatoirement parmi toutes les fonctions linéaires possibles. Chaque fonction linéaire est appliquée sur tous les bits du bloc de message. Notre protocole possède donc une structure simple qui garantit l'absence de portes dérobées. Nous allons expliquer que notre cryptosystème résiste aux attaques actuellement connues telles que la cryptanalyse linéaire et la cryptanalyse différentielle. Il est également résistant à toute forme d'attaque basée sur un biais en faveur d'une fonction simple des S-Boxes. / We developed a new symmetric-key algorithm that is highly secure. Our algorithm is SPN-like but with two main particularities. First of all, we use very large random incompressible s-boxes. The input size of our s-boxes vary between 256 Kb and 32 Gb.Secondly, for the permutation part of the algorithm, we use a set of random linear functions chosen uniformly and randomly between every possible fonctions. The input of these functions is all the bits of the block of messages to encode. Our system has a very simple structure that guarantees that there are no trap doors in it. We will explain how our algorithm is resistant to the known attacks, such as linear and differential cryptanalysis. It is also resistant to any attack based on a bias of the s-boxes to a simple function.

Cette thèse s'interroge sur les notions d'aléa et de régularité des variations boursières. Nous démontrons sur le plan théorique, la compatibilité des principales théories financières (cf. efficience informationnelle, finance comportementale et approche conventionnaliste) avec l'impossibilité de battre la stratégie "buy and hold". Cette impossibilité est confirmée par les études statistiques dans la mesure où les régularités identifiées dans les séries financières ne permettent pas de prédire le sens des variations futures. Les modèles économétriques disponibles à présent offrent souvent un "hit score" insuffisant (<60%) pour réussir des tentatives fructueuses de "market timing". Une contribution de ce travail se trouve dans l'introduction du concept de complexité algorithmique en finance. Une approche générale est proposée pour estimer la "complexité de Kolmogorov" des séries de rentabilités: après un processus "discrétisation-effacement", des algorithmes de compression sans perte sont utilisés pour détecter des structures régulières qui ne sont pas toujours visibles aux yeux des tests statistiques. En étudiant le degré d'aléa des principaux marchés internationaux à une fréquence "tick-by-tick", on constate une complexité plus élevée pour Euronext-Paris que pour le NYSE et le NASDAQ. Nous expliquons ce résultat par une auto-corrélation plus élevée des volatilités inter-journalières aux Etats-Unis qu'en France. L'inefficacité de "market timing" étant soutenue aussi bien par les théories financières que par les observations empiriques, nous définissons la notion de "battre le marché" dans ce sens spécifique avec un modèle mathématique qui s'inscrit dans le cadre de la calculabilité.

L'informatique quantique, ce surprenant mariage entre informatique et physique, est un domaine riche en nouvelles idées, autant pour la technologie future qu'une meilleure compréhension de notre univers. C'est le phénomène de l'intrication qui est au coeur de cette nouvelle façon de voir l'information. Ce mémoire porte sur l'étude des corrélations quantiques observées dans la nature, mises de l'avant, entre autres, par John Bell. Plus particulièrement, deux jeux non signalants, dans lesquels ces corrélations se manifestent, sont étudiés: le jeu CHSH, probablement l'exemple le plus connu à ce jour, et le jeu de pseudotélépathie du carré magique. Pour ce faire, deux points de vue seront adoptés, soit probabiliste et algorithmique. Le premier est motivé par la prédiction (ce qui aurait pu se passer), tandis que le second s'intéresse à l'information intrinsèque contenue dans un objet (ce qui s'est passé). Les concepts «aléatoire» et «information» seront donc abordés premièrement à la Shannon (approche probabiliste) puis à la Kolmogorov (approche algorithmique). C'est la complexité de Kolmogorov qui sera utilisée pour quantifier l'information de façon factuelle. De plus, le cas particulier où plusieurs répétitions d'un jeu sont jouées en parallèle dans un monde classique sera examiné. Le théorème des répétitions parallèles, résultat important sur le sujet démontré par Ran Raz, sera présenté et utilisé par la suite dans l'étude algorithmique des jeux CHSH et du carré magique. / Quantum information, this intriguing marriage between computer science and physics, is a promising field of research for future technologies as well as a better understanding of our universe. Entanglement is at the very heart of this new way of understanding information. This thesis focuses on quantum correlations that are observed in nature. They have been studied in great detail by, among others, John Bell. More specifically, two non-signaling games, in which these correlations arise, are studied: the CHSH game, which is probably the best-known example of such games, and the magic square pseudotelepathy game. To do so, two points of view will be adopted: probabilistic and algorithmic. The first is motivated by prediction (what could have happened) and the second focuses on the intrinsic information about an object (what happened). Therefore, the concepts of randomness and information are first addressed from Shannon’s point of view (probabilistic approach) and second from Kolmogorov’s point of view (algorithmic approach). Kolmogorov complexity is used to quantify information in a factual way. Furthermore, the particular case in which multiple repetitions of a game are played in parallel in a classical world is considered. The parallel repetition theorem, an important result on the subject proven by Ran Raz, is presented and used in the algorithmic study of the CHSH game and the magic square game.