Université d'Orléans

Titre :

Modèle géométrique de calcul : fractales et barrières de complexité.

Discipline : Informatique

Résumé :

Les modèles géométriques de calcul permettent d'effectuer des calculs à l'aide de primitives géométriques. Parmi eux, le modèle des machines à signaux se distingue par sa simplicité, ainsi que par sa puissance à réaliser efficacement de nombreux calculs. Nous nous proposons ici d'illustrer et de démontrer cette aptitude, en particulier dans le cas de processus massivement parallèles.
Nous montrons d'abord à travers l'étude de fractales (et  plus généralement  de  structures appelées  accumulations) que les machines à signaux sont capables d'une utilisation massive et parallèle de l'espace.
Une méthode de programmation géométrique modulaire est ensuite proposée pour construire des machines à partir de composants géométriques de base – les  modules – munis de certaines fonctionnalités. Cette   méthode est particulièrement adaptée pour la conception de calculs géométriques parallèles.
Enfin, l'application de cette méthode et l'utilisation de certaines des structures fractales résultent en une   résolution   géométrique de problèmes difficiles comme les problèmes de satisfaisabilité booléenne SAT et Q-SAT. Ceux-ci, ainsi que plusieurs de leurs variantes, sont résolus par machines à signaux avec une complexité en temps intrinsèque au modèle, appélée profondeur de collisions, qui est polynomiale, illustrant ainsi   l'efficacité et le pouvoir de calcul parallèle des machines à signaux.