Nouvelles formes algorithmiques de la théorie de l'information – NAFIT

La théorie algorithmique de l'information (ou complexité de Kolmogorov) a été conçue comme une théorie de l'information issue de la notion d'algorithme. Fondée dans les années 60 mais principalement développée dans les années 70 à 80, cette théorie est devenue célèbre par la beauté et la simplicité de ses raisonnements. Elle a eu des applications directes et indirectes dans des domaines aussi variés que la combinatoire pour lesquels elle a permis de développer des outils puissants, pour l'analyse des algorithmes pour lesquels elle permet des raisonnement compréhensibles dans des situations complexes, mais aussi dans des domaines aussi divers que la sociologie ou l'économie (nous n'en sommes pas spécialistes). Un fort regain d'intérêt pour cette théorie se développe actuellement (et peut être vérifié dans les grandes conférences d'informatique théorique) dans des modèles un peu différents, plus adaptés à l'algorithmique moderne qui traite rarement de la résolution par un programme d'un problème à une entrée mais traite plutôt de flux de données, d'informatique interactive et d'informatique 'online'. Nous nous proposons dans ce projet d'étudier la théorie des flux d'information en la liant aux notions d'aléatoirité, d'imprédictabilité, et de complexité d'interaction. Notre étude a aussi l'intérêt de faire un lien avec la théorie de l'information de Shannon, la théorie des probabilités et c'est un sujet très moderne que de rapprocher les deux domaines des algorithmiques et des probabilités. Dans ce rapprochement, nous nous situons clairement en informatique théorique.