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.

Cette thèse explore la relation entre les catégories de modules sur les catégories différentielles graduées (abrégées DG) petites, d'une part, et les catégories triangulées bien engendrées d'autre part. Dans la première partie, on construit la catégorie dérivée $\alpha$-continue D_\alpha A d'une catégorie DG $\alpha$-cocomplète petite A, où $\alpha$ est un cardinal régulier. Cette construction jouit d'une propriété très intéressante, qui est la clef pour démontrer le théorème principal de la thèse. Les catégories D_\alpha A s'avèrent être les prototypes des catégories triangulées algébriques à engendrement $\alpha$-compact. On entend par algébrique, équivalente, en tant que catégorie triangulée à la catégorie stable d'une catégorie de Frobenius. Le résultat principal établit que les catégories algébriques bien engendrées sont précisément celles qui sont des localisations de la catégorie dérivée d'une catégorie DG petite. Ce résultat rappelle beaucoup un théorème de Gabriel et Popescu de 1964, qui caractérise les catégories abéliennes de Grothendieck comme des localisations de catégories de modules sur des anneaux. Il donne aussi une réponse positive à une question de Drinfeld qui demandait si toutes les catégories triangulées bien engendrées sont des localisations de catégories triangulées à engendrement compact, pour la classe des catégories triangulées algébriques. Dans la deuxième partie, on étudie les catégories DA et D_\alpha A en utilisant la structure projective de catégories de modèles de Quillen présente sur la catégorie des DG modules. On introduit la sous-catégorie des DG modules cofibrants homotopiquement $\alpha$-compacts et on montre que sa catégorie homotopique est précisément la catégorie dérivée $\alpha$-continue D_\alpha A. Cela nous permet de donner une deuxième preuve, complètement différente du résultat-clef de la première partie.