<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
- $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, …)

Planning du cours

Date	Description approximative
11 janvier	séance 1 :
• Présentation du module et objectifs généraux
• Présentation générale programmation par contraintes + concept de problème de satisfaction / optimisation de contraintes
• Rappels Python (POO + autres sujets avancés nécessaires)

Cette séance va me permettre de sentir le niveau général et les disparités entre les participants. | | 18 janvier | Pause : conférence commune avec les autres du cours Turing | | 25 janvier | Séance 2 : introduction à la CP (Constraint Programming) : variables, domaines, contraintes, ... + début implémentation solveur | | 8 février | séance 3 => propagation de contraintes / graphe de contraintes / ... => amélioration du solveur / premières applications à des problèmes concrets | | 15 février | pause 1e samedi des relâches VD) | | 22 février | Pause 2e samedi des relâches VD | | 1er mars | Séance 4 : algorithmes de recherche en profondeur / recherche en largeur / heuristiques => amélioration du solveur / applications | | 8 mars | Séance 5 : applications / pour aller plus loin / utilisation et étude de "vrais" solveurs state of the art avec Python / intro à la modélisation et résolution de "vrais" problèmes |