Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Ppc14 cours1 print Introduction à la Programmation par Contraintes Cours Problèmes de Satisfaction de Contraintes Ruslan Sadykov INRIA Bordeaux ?? Sud-Ouest Septembre Lignes directrices Introduction Applications de PPC Problèmes de Satisfaction des Contra

Introduction à la Programmation par Contraintes Cours Problèmes de Satisfaction de Contraintes Ruslan Sadykov INRIA Bordeaux ?? Sud-Ouest Septembre Lignes directrices Introduction Applications de PPC Problèmes de Satisfaction des Contraintes Exemples de modélisation Résolution Organisation du cours cours TD TP TD exercices sur le papier - TP introduction à un solveur PPC - TP projet Évaluation de la note pour le projet de la note d ? examen La page du cours www math u-bordeaux fr sadykov teaching MSE C Qu ? est-ce que c ? est la PPC Une technique mathématique pour résoudre des problèmes combinatoires Ça marche en trois phases Modélisation Vous dé n nissez votre problème dans un format spéci n que Implémentation Vous écrivez votre modèle dans un langage de modélisation Résolution Vous utiliser un solveur PPC compatible pour trouver une solution Limitations de PPC La PPC n ? est surtout pas une méthode magic A priori elle n ? est pas meilleure que d ? autres méthodes programmation linéaire programmation dynamique recherches locales etc Tout dépend du type de problème une méthode press button ? du moins pour l ? instant Nécessité de comprendre la technique Nécessité de guidez ? la résolution Source Antoine Jeanjean Spéci n cités de PPC On travaille avec un problème de décision ?? le Problème de Satisfation des Contraintes CSP avec une série des CSPs si c ? est un problème d ? optimisation Grandes possibilités de modélisation contraintes non-linéaires logiques explicites Utilisation des contraintes du problème de manière active pour limiter l ? espace de recherche Plus il y a des contraintes plus facile à résoudre le problème Les objectives du cours Savoir pour quels types de problèmes la méthode de PPC est bonne Savoir modéliser ef n cacement ces problèmes Conna? tre les langages de modélisation et solveurs PPC et savoir les utiliser Savoir comment les solveur marchent à l ? intérieur Un exemple introductive ?? Sudoku Il y a cases o? on peut mettre les chiffres de à On doit mettre les chiffres dans les cases tel que chaque horizontale verticale bloque de cases contienne les chiffres différents On vient presque de formuler un Problème de Satisfaction de Contraintes En PPC le problème est résolu exactement plus ou moins de la même façon que vous résolvez le sudoku Lignes directrices Introduction Applications de PPC Problèmes de Satisfaction des Contraintes Exemples de modélisation Résolution Application réelle I ?? Ligne de production des voitures Source Alan M Frisch Domaines d ? application Agencement Diagnostique et Véri n cation Plani n cation Ordonnancement et Empois du temps Emballage et Placement Logistique Application réelle II ?? Étiquetage de scènes On a un dessin vectoriel d ? une scène contenant des objets planaires avec des sommets trièdres But reconna? tre ces objets c ? est-à-dire donner aux arrêtes une des étiquettes possibles l ? arrêt concave - l ? arrêt convexe ou l ? objet à droite l ? arrière-plan à gauche Source Liu Young Das Application réelle II ?? Étiquetage de