v2.3.2 (2860)

Cours scientifique - IA302 : Programmation par contraintes

Descriptif

La programmation par contraintes est un paradigme de programmation permettant de résoudre des problèmes combinatoires de grandes tailles tels que les problèmes de planification et d'ordonnancement. Dans cette approche, une séparation entre la partie modélisation à l'aide de problèmes de satisfaction de contraintes (une contrainte étant une relation logique entre différentes variables) et la partie résolution est réalisée. Cet enseignement présente les fondements de la programmation par contraintes en mettant l’accent sur la modélisation et les algorithmes de résolution (systématique, filtrage) pour les problèmes dont les variables prennent des valeurs discrètes ou continues.  

Objectifs pédagogiques

- Savoir formaliser un problème sous forme de CSP (discret ou continu)
 
- Connaitre quelques algorithmes de résolution (en discret et en continu)
 
- Apprendre les bases de l'arithmétique d'intervalles
 
- Découverte de deux outils (un outil graphique de résolution de CSP discret et Ibex pour les CSPs continus)

nombre d'heure en présentiel

24

nombre de blocs

8

effectifs minimal / maximal

10/30

Diplôme(s) concerné(s)

Pour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole Nationale Supérieure de Techniques Avancées

-  Savoir programmer en C/C++  - Bases des mathématiques ensemblistes

Format des notes

Numérique sur 20

Littérale/grade européen

Pour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole Nationale Supérieure de Techniques Avancées

Vos modalités d'acquisition :

Examen sous la forme d'un mini-projet à réaliser seul en 3h30 (un programme+un rapport)

Le rattrapage est autorisé (Max entre les deux notes écrêté à une note seuil)
  • le rattrapage est obligatoire si :
    Note initiale < 6
  • le rattrapage peut être demandé par l'étudiant si :
    6 ≤ note initiale < 10
L'UE est acquise si Note finale >= 10
  • Crédits ECTS acquis : 1.6 ECTS

Le coefficient de l'UE est : 1.6

La note obtenue rentre dans le calcul de votre GPA.

L'UE est évaluée par les étudiants.

Programme détaillé

Séance 1

Les contraintes et les CSPs.

Séance 2

Algorithmes de résolution

Séance 3

Un outil de résolution de CSPs discrets.

Séance 4

Les CSPs continus ou numériques.

Séance 5

Résolution des CSPs continus.

Séance 6

CSPs sous ou sur contraints.

Mots clés

CSP
Veuillez patienter