Intitulé de la matière : Bases de données
Intitulé de l’UE : UED12
Crédits : 2
Coefficients : 1
Objectifs de l’enseignementLa programmation par contraintes est une technique de résolution des problèmes combinatoires.
Connaissances préalables recommandées (descriptif succinct des connaissances requises pour pouvoir suivre cet enseignement – Maximum 2 lignes).
Contenu de la matière :
Introduction,
Modélisation,
Problèmes de satisfaction des contraintes
Exemples des modèles PPC simples
Méthodes de résolution
Recherche arborescente
Consistance locale
Les contraintes globales
Quelques modèles PPC pratiques
Solveurs PPC
Mode d’évaluation : …Examen TP………………………
Références (Livres et polycopiés, sites internet, etc).
- Stavros Athanassopoulos, IoannisCaragiannis, and ChristosKaklamanis. Analysis of approximation algorithms for k-set cover using factor-revealing linear programs. Theory of Computing Systems, 45(3) :555–576, 2009.
- Feige. A threshold of ln n for approximating set cover. Journal of the ACM, 45(4) :634–652, 1998.
- Fedor V. Fomin, FabrizioGrandoni, and Dieter Kratsch. A measure&conquer