Programmation par contraintes et programmation mathématique
INF580

 Comment résoudre de manière exacte un problème difficile ?

cours et exercices: Christoph Dürr
.
..

Informations

amphi Grégory 13:30-15:00 et 15:15-17:15

Documents

01 | Ve 11/01 Théorie de la programmation par contraintes

02 | Ve 18/01 Pratique de la programmation par contraintes

03 | Ve 25/01 Liens dansants

04 | Ve 01/02 Tout différent

05 | Ve 08/02 Programmation linéaire

06 | Ve 15/02 CSP sur domaine booléens, 2-SAT etc

07 | Ve 22/02 Algorithmes de backtracking pour SAT

08 | Ve 01/03 Recherche locale pour 3SAT

09 | Ve 15/03 Recherche locale

10 | Ve 22/03 Examen

Pour vous préparer à l'examen, révisez les différentes notions de consistance locale et les techniques de propagation. Comprenez vous le fonctionement de AC4 ? Quand est-ce que c'est intéressant d'imposer la consistance de chemin ? En quoi un traitement particulier de la contrainte globale all different est utile par rapport à une collection de contraintes binaires different ? Comprenez vous pourquoi la recherche locale est plus efficace qu'une exploration par backtracking pour le problème des n reines ? Sauriez vous implémenter un solveur pour les contraintes logiques comme HornSAT ?

L'examen aura des questions de difficultées graduées de questions méchaniques vers des questions de réflexion. On traitera essentiellement la résolution et la modélisation.

Les documents du cours, ceux distribués dans le cadre du module, les notes personnelles ainsi que les calculatrices seront autorisés. Les traducteurs ne sont pas nécessaires. Les portables sont strictement interdits à l'intérieur des salles d'examens.

En particulier les livres ne sont pas autorisés. Les notes personnelles peuvent être manuscrites ou imprimées. Il est interdit d'imprimer des chapitres de livres et de les faire passer comme des notes personnelles.