Informatique fondamentale & Mathématiques discrètes
Contexte
Au cours des dernières décennies, une interaction très forte entre les mathématiques et l’informatique s’est développée. Ainsi des thématiques classiques comme la géométrie, la topologie, l’algèbre, les probabilités ou les logiques classiques et non-classiques permettent de décrire et comprendre des structures discrètes issues de problématiques informatiques. Réciproquement des outils issus de l’informatique permettent de mieux cerner certaines propriétés mathématiques. Les principaux objectifs peuvent être résumés ainsi : donner des représentations discrètes d’objets continus, développer des outils mathématiques pour étudier des structures discrètes, explorer par le calcul des propriétés mathématiques, optimiser et donner les limites de la complexité des algorithmes utilisés, développer une théorie de la preuve assistée par ordinateur.
Du point de vue national, ces thématiques sont les axes principaux du gdr-im qui regroupent environ 1500 membres permanents. On retrouve ces thématiques de manière éclatées dans les différentes équipes des laboratoires IRIT, LAAS et IMT. Ces dernières années, le Labex CIMI a tout de même développé quelques activités dans ces directions (rencontres CIMI, financement de mini projets, postdoc...).
La création d’une équipe projet permet de créer une dynamique autour des mathématiques discrètes et de l’informatique fondamentale.
Projet
L’interaction de l’informatique fondamentale et le développement d’outils mathématiques discrets
pour modéliser ces problèmes est très riche, on peut souligner les pistes suivantes :
Modèles et systèmes discrets : Un ordinateur manipule des objets discrets, il est naturel de s’intéresser à de tels objets, comprendre leur combinatoire, leur complexité structurelle et essayer de décrire les propriétés d’un élément générique. On peut aussi se demander comment encoder des objets continus par des objets discrets pour les manipuler informatiquement.
Algorithmique sur ces structures : Il est intéressant de développer des algorithmes performants pour résoudre des problèmes sur ces structures. On peut donc s’intéresser à la complexité de ces algorithmes, comprendre s’il y a des instances plus difficile que d’autres et si c’est le cas étudier les transitions de phases qui peuvent apparaitre. L’étude de ces algorithmes passe entre autres par l’utilisation du formalisme logique.
Preuve : L’explosion combinatoire de l’étude de certains objets discrets fait qu’il est intéressant de développer des assistants de preuve efficaces. Cette problématique est liée à la logique, la certification d’algorithmes et preuves de programmes.
Thèmes transverses : Il peut exister des thèmes transverses à ce découpage sur les thèmes de la sécurité mathématique (codage, cryptographie, vérification logicielle).