<aside> ℹ️ Titre du cours (idée … pas encore sûr à 100%)

Résolution de problèmes de satisfaction de contraintes en Python

</aside>

Dans ce cours, nous allons aborder un paradigme de programmation fascinant, la programmation par contraintes. Cette manière de programmer est née de la bonne vieille intelligence artificielle des années 1980-2010. Elle consiste à décrire des problèmes de satisfaction de contraintes (par exemple la résolution de Sudoku) sous forme déclarative et laisser l’ordinateur trouver la solution en expérimentant différentes stratégies et approches de résolution (heuristiques).

Dans ce cours, vous allez développer votre propre solveur de contraintes en Python en utilisant abondamment la programmation orientée objets. Nous jetterons également également un oeil au code source du module python-constraint.

Ce que vous maîtriserez à l’issue du cours

• La programmation orientée objets en Python
• D’autres fonctionnalités avancées du langage Python
• Les notions fondamentales de la programmation par contraintes
  • Notions de base (Domaines, variables, contraintes)
  • Modélisation de problèmes par satisfaction de contraintes (n-dames, problèmes cryptarithmétiques, …)
  • Propagation de contraintes
  • Heuristiques de recherche
  • Recherche en profondeur, recherche en largeur
  • $k$-cohérence
  • Structures de données : arbres, graphes
  • …
• Applications : résolution automatique de Sudoku, problèmes de planification, …
• Applications modernes de la programmation par contrainte (résolution de dépendances dans les logiciels, …)

Quelques références

Classic Computer Science Problems in Python

Constraint Processing

Handbook of Constraint Programming

Full Table of Contents for AI: A Modern Approach

Programming with Constraints: an Introduction. Course Material

Building Decision Support Systems

Quelques outils

• https://www.minizinc.org/
• https://www.gecode.org/