Dans ma thèse, j'ai étudié les liens entre deux notions différentes de la complexité. La complexité algorithmique, d'une part, qui mesure la difficulté de réaliser une tâche automatiquement. La complexité de systèmes, d'autre part, qui est le degré d'intrication des actions des agents du système. Cette approche est relativement nouvelle, à la fois dans les deux théories, et offre des perspectives enthousiasmantes pour parler des grandes conjectures de la complexité. En particulier, nous avons réussi à développer une méthode générique pour construire des bornes inférieures de complexité, et des conditions nécessaires relativement élémentaires sur notre modèle de calcul, ce qui est souvent considéré comme une question difficile en théorie de la complexité. D'autre part, mon travail propose une définition alternative de classes de complexité, basée sur des automates cellulaires, et étudie les relations avec les définitions classiques. Enfin, la dernière partie de mon travail a consisté à utiliser les méthodes de la théorie de la complexité pour ouvrir de nouvelles pistes sur une conjecture ancienne en automates cellulaires, à savoir l'existence d'un automate universel par facteur. J'ai soutenu ma thèse le 26 octobre 2012 à Santiago, au Chili, mais je suis heureux de vous convier à cet exposé, sans doute plus informel, sur les travaux que j'ai effectués pendant ces quelques années au LAMA.