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.
Pierre Talbot soutiendra sa thèse de doctorat réalisée au sein de l'équipe Représentations musicales (STMS - CNRS/Ircam/Sorbonne Université).
Jury
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