Autour de la géométrisation dans la logique et l’informatique musicale
Trois usages de notions spatiales en programmation et en représentation des connaissances
Carte blanche à l’équipe "Informatique, Biologie Intégrative et Systèmes Complexes" (IBISC, FRE 3190), Université d’Evry Val d’Essonne, Genopole
Vendredi 13 novembre 2009
de 14h30 à 18h
Ircam, Salle I. Stravinsky
1, place I. Stravinsky 75004 Paris
(Entrée libre dans la mesure des places disponibles)
Cette séance est organisée dans le cadre du Projet Interaction MathST2I "Géométrie de l’Interaction et Musique".
Programme
- 14h30-14h50 Moreno Andreatta : Un survol sur les approches géométriques et topo(s)-logiques en théorie mathématique de la musique
- 14h50-15h20 Olivier Michel : Une brève présentation du langage Huit-et-demi
- 15h40-16h10 Antoine Spicher : Une brève présentation du langage MGS
- 16h30-17h00 Jean-Louis Giavitto : Résoudre des analogies en se déplaçant dans un espace
- Discussion finale
Présentations en powerpoint (dissier compacté .zip)
Problématique de la séance
La logique offre de nombreuses métaphores et de nombreux outils à l'informatique, comme, par exemple, à travers le slogan "calculer = démontrer" ou à travers les nombreux travaux autour de la preuve de programmes. Cependant, d'autre champs des mathématiques peuvent offrir à l'informatique des concepts, des méthodes et des outils complémentaires qui présentent un triple intérêt heuristique, technique et pédagogique. Les travaux menés au sein du groupe de recherche MGS s'appuient sur diverses notions spatiales pour repenser la notion de structure de données et développer de nouvelles approches pour la programmation. Ces travaux mettent en avant le slogan "calculer = se déplacer".
Nous présenterons trois travaux qui sont autant de variations sur ce thème et qui s'appuient sur la notion de forme, l'un des trois aspects de la spatialité, selon Gilles Gaston Granger, avec les notions de texture et de repérage (mesure). Les deux premiers exposés relèvent de la problématique de la "programmation spatiale" [http://www.dagstuhl.de/en/program/calendar/semhp/?semnr=2006361] qui cherche à expliciter la notion d'espace dans les modèles de programmation soit parce que l'espace est vue comme une ressource, soit parce que l'espace est une donnée ou bien un résultat du calcul.
Notre équipe a développé ce thème initialement pour la programmation parallèle (aller plus vite via le parallélisme de données) à travers le langage 81/2 et ensuite pour des problèmes de simulation (modélisation de la morphogenèse et calcul d'une forme dans l'espace) avec le langage MGS. Le dernier exposé introduira une représentation spatiale de propriétés logiques et utilisera un déplacement dans cet espace abstrait pour résoudre un problème d'analogie.
Si les travaux présentés ici ne relèvent pas du projet de la géométrie de l'interaction, ils partagent avec ce domaine la volonté de repenser le calcul de manière intrinsèque, en portant une attention toute particulière à la dynamique et aux représentations mathématiques géométriques.
Résumés
Olivier Michel : Une brève présentation du langage Huit-et-demi
http://www.ibisc.univ-evry.fr/~michel/
Huit et demi, ou 8 1/2 en abrégé, est un langage de programmation qui combine les notions de flots (stream) et de collection en une nouvelle structure de données : le tissu. Un tissu correspond aux valeurs successives d'un ensemble structuré de variables. Il permet donc de représenter directement la notion de trajectoire d'un système dynamique. 8 1/2 est un langage déclaratif qui permet de définir des tissus par des équations récursives. Le style de programmation en 8 1/2 est un style déclaratif, très proche du style mathématique, et il permet d'exprimer implicitement le parallélisme de contrôle et le parallélisme de données présent dans l'évaluation des définitions.
Dans cette présentation, nous introduirons tout d'abord la notion de collection et nous montrerons comment cette notion permet de développer une représentation spatiale du parallélisme de données. Nous montrerons, à travers des exemples, comment la notion de stream synchrone (et d'horloge) permettent de manipuler une séquence de valeurs dans le temps comme un tout (style intensionnel). La notion de tissu qui combine stream et collection sera présentée à travers plusieurs exemples paradigmatiques.
Références
Voir par exemple
Antoine Spicher : Une brève présentation du langage MGS
http://lacl.univ-paris12.fr/spicher
Les formes spatiales qu'il est possible de définir en 81/2 sont relativement limitées. De plus, il est difficile de faire évoluer simplement ces formes. Cela nous a conduit à développer un nouveau langage dédié à la modélisation de processus de morphogenèse. Dans ce domaine, il est nécessaire de simuler l'évolution d'une forme au cours du temps. Souvent, par exemple en biologie, le processus générateur de la forme prend place dans la forme elle-même. Il y a ainsi un couplage entre la forme produite et le processus créateur de la forme. Nous qualifions ce type de système de "système dynamique à structure dynamique". En effet, contrairement aux systèmes dynamiques "classiques", l'espace des états ne peut être simplement spécifié a priori, mais doit être calculé conjointement avec l'état du système au cours du temps.
La modélisation de ce type de système passe par la définition de loi d'évolution locale. Un exemple d'un tel formalisme, utilisé dans la modélisation de la croissance des plantes, est donné par les systèmes de Lindenmayer. Ces modèles se présentent sous la forme de grammaire ou les règles de production s'appliquent "en parallèle". Cette approche, qui a donné lieu à de nombreuses applications, a montré tout sont intérêt mais reste limitée à la génération de structures arborescentes.
Dans le cadre du projet MGS, nous avons montré comment étendre cette approche à des objets spatiaux plus sophistiqués que des structures arborescentes. Cette extension passe d'abord par un détour qui consiste à voir dans chaque structure de données informatique, un espace dans lequel le calcul se déplace et à réinterpréter dans ce cadre la notion de réécriture. Les règles de grammaire correspondent alors à des règles d'évolution locale qui définissent comment un petit voisinage de l'espace évolue dans le temps.
MGS a été appliqué avec succès à des problèmes de simulations de la croissance des plantes à un niveau cellulaire, mais aussi à des modélisations d'organismes génétiquement modifiés ou à des problèmes d'algorithmiques.
Références
Voir par exemple:
Jean-Louis Giavitto : Résoudre des analogies en se déplaçant dans un espace
MGS permet de créer des formes arbitraires. Ces formes ne correspondent pas nécessairement à un objet physique, comme c'est souvent le cas dans les problèmes de simulation, mais peuvent représenter un espace abstrait relié à des propriétés logique. C'est ce point que nous illustrerons dans le dernier exposé.
Le raisonnement diagrammatique est une forme de raisonnement spatial ou visuel qui consiste en la construction d'images spatiales et en opérations perceptives agissant dessus. Un problème, un phénomène ou un système est représenté de manière analogique par une figure, et des relations spatiales comme le voisinage, la connexité, la continuité, qui sont immédiatement perçues par notre appareil perceptif, sont utilisées pour raisonner sur le système. Le raisonnement visuel est souvent présenté comme informel, imprécis et incommunicable, il n'en reste pas moins considéré comme incontournable et nécessaire car offrant une compréhension intuitive ou physique.
Dans ce travail, nous proposons d'étudier l'application de concepts issus de la topologie algébrique (les complexes simpliciaux) à deux problèmes : l'analyse des contes de fée et la résolution d'analogie aristotélicienne (étant donné A, B et C, trouver un D qui est à C ce que B est à A).
Notre approche est inspirée de la Q-analyse développée dans les années 70 par R. Atkin. Elle consiste à représenter un ensemble de propriétés logiques par un espace abstrait : un complexe simplicial. Un complexe simplicial est un ensemble d'éléments fermé par inclusion. Un tel ensemble généralise naturellement la notion de polyèdre : un polyèdre est un ensemble composé de volumes, de faces, d'arêtes, de sommets ; une face est un ensemble d'arêtes et de sommets, etc. Intuitivement, un complexe simplicial est un morceau d'espace construit en collant ensemble des morceaux plus élémentaires. La dynamique du système consiste à se déplacer dans cet espace (sur les arêtes, les faces, etc.). Le complexe simplicial est un objet topologique qui possède une structure très riche : on peut définir des notions d'obstruction, d'excentricité, de bord, de chemin multidimensionnel, de déformation… et associer à cette structure des groupes mathématiques qui caractérisent la structure topologique de l'objet. Ainsi, on dispose d'outils algébriques pour décider, par exemple, si deux complexes simpliciaux sont similaires.