Pierre TALBOT soutiendra sa thèse de doctorat réalisée au sein de l'équipe Représentations musicales (STMS - CNRS/Ircam/Sorbonne Université), intitulée :
"Programmation spatio-temporelle : un langage synchrone par contraintes pour l'exploration combinatoire"
Le jury sera composé de :
Carlos Agon - Sorbonne Université
Emmanuelle Encrenaz - Sorbonne Université
Antoine Miné - Sorbonne Université
Manuel Serrano - INRIA, Inde
Sylvain Soliman - INRIA, Lifeware
Peter Van Roy-Université Catholique de Louvain
Résumé :
La programmation par contraintes est un paradigme basé sur des relations mathématiques appelées contraintes. C'est une approche de programmation déclarative permettant de décrire de nombreux problèmes comme l’ordonnancement de tâches ou des problèmes de composition musicale.
On contraste cette approche avec la programmation procédurale qui décrit comment un problème est résolu, tandis que la programmation par contraintes décrit quel est le problème. Dans ce dernier cas, la partie résolution de contraintes est laissé à un solveur de contraintes générique. Malheureusement, il n'existe pas d'algorithme efficace pour tout type de problème, et par conséquent le solveur doit souvent être configuré à la main. Même les langages par contraintes basés sur ces solveurs sont limités pour exprimer des stratégies d'exploration.
Dans cette thèse, nous proposons un langage de programmation permettant de programmer des stratégies d'exploration.
Nous établissons d'abord une nouvelle formalisation dans la théorie des treillis des problèmes de contraintes. Ceci nous permet de comparer et définir précisément notre langage, appelé programmation spatio-temporelle, et basé sur la programmation synchrone.
Ce paradigme ouvre de nouveaux horizons pour programmer des stratégies d'exploration dans les problèmes de satisfaction de contraintes mais aussi, plus généralement, les problèmes utilisant un mécanisme de retour sur traces (i.e. backtracking).
On applique notamment ce paradigme à la composition musicale par contraintes, où le compositeur peut naviguer dans l'espace des solutions généré par un problème musical.
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
"Spacetime Programming: A Synchronous Language for Constraint Search "
Abstract:
Constraint programming is a paradigm for computing with mathematical relations named constraints.
It is a declarative approach to describe many real-world problems including scheduling, vehicles routing, biology and musical composition.
Constraint programming must be contrasted with procedural approaches that describe how a problem is solved, whereas constraint models describe what the problem is.
The part of how a constraint problem is solved is left to a general constraint solver.
Unfortunately, there is no solving algorithm efficient enough to every problem, because the search strategy must often be customized per problem to attain reasonable efficiency. This is a daunting task that requires expertise and good understanding on the solver's intrinsics. Moreover, higher-level constraint-based languages provide limited support to specify search strategies.
In this dissertation, we tackle this challenge by designing a programming language for specifying search strategies.
It is constructed around two axes: (i) a novel theory of constraint programming based on lattice theory, and (ii) a programming language, called spacetime programming, building on lattice theory for its data structures and on synchronous programming for its computational model.
This paradigm opens the door to new, more complex, search strategies in constraint programming but also in applications requiring backtracking search.
We demonstrated its usefulness in an interactive computer-aided composition system where we designed a search strategy to help the composer navigating in the state space generated by a musical constraint problem.