Descriptif
Ce cours présente des méthodes d'intelligence artificielle symbolique basées sur une modélisation du problème à résoudre par des variables mathématiques, des contraintes et des formules logiques, et sa résolution en utilisant des solveurs de contraintes généraux et des procédures de recherche.
Chaque session est composée d'un cours magistral de 2h et de 2h de travaux dirigés sur ordinateurs individuels pour expérimenter les concepts présentés de Programmation Logique avec Contraintes. Vous utiliserez le système SWI-Prolog avec ses bibliothèques de modélisation et résolution de contraintes, dans une suite de 9 TDs pour apprendre à résoudre des questions de représentation des connaissances, bases de données déductives, résolution de contraintes générales, algorithmes de recherche, résolution de problèmes d'optimisation combinatoire, allocation de ressources, placement, planification et ordonnancement de tâches pour l'aide à la décision.
Langue du cours : documents en anglais, oral en anglais sur demande
Crédits ECTS: 4
Objectifs pédagogiques
Apprendre à modéliser un problème sous la forme d'un problème de satisfaction de contraintes sur des variables mathématiques.
Apprendre l'usage et la conception de solveurs de contraintes généraux et de procédures de recherche efficaces.
Apprendre les concepts fondamentaux de la logique du premier ordre par les concepts de la programmation par contraintes.
effectifs minimal / maximal:
/24Diplôme(s) concerné(s)
- Programmes d'échange internationaux
- Titre d’Ingénieur diplômé de l’École polytechnique
- MScT-Artificial Intelligence and Advanced Visual Computing
Parcours de rattachement
Objectifs de développement durable
ODD 12 Consommation et production responsables.Pour les étudiants du diplôme Programmes d'échange internationaux
Aucun
Pour les étudiants du diplôme Titre d’Ingénieur diplômé de l’École polytechnique
Aucun
Pour les étudiants du diplôme MScT-Artificial Intelligence and Advanced Visual Computing
Aucun
Format des notes
Numérique sur 20Littérale/grade américainPour les étudiants du diplôme Titre d’Ingénieur diplômé de l’École polytechnique
Vos modalités d'acquisition :
50% examen écrit,
50% moyenne des 7 meilleures notes données aux 9 TPs (la note de TP porte sur le fichier rendu à la fin de la séance de 2h auquel peut s'ajouter un bonus pour des réponses tardives rendues en dehors du TP).
Le rattrapage est autorisé (Max entre les deux notes)
- le rattrapage est obligatoire si :
- Note initiale < 10
- le rattrapage peut être demandé par l'étudiant si :
- Note initiale < 10
- Crédits ECTS acquis : 5 ECTS
La note obtenue rentre dans le calcul de votre GPA.
Pour les étudiants du diplôme MScT-Artificial Intelligence and Advanced Visual Computing
Vos modalités d'acquisition :
idem
Le rattrapage est autorisé (Max entre les deux notes)- le rattrapage est obligatoire si :
- Note initiale < 10
- le rattrapage peut être demandé par l'étudiant si :
- Note initiale < 10
- Crédits ECTS acquis : 4 ECTS
La note obtenue rentre dans le calcul de votre GPA.
Pour les étudiants du diplôme Programmes d'échange internationaux
Vos modalités d'acquisition :
idem
Le rattrapage est autorisé (Max entre les deux notes)- le rattrapage est obligatoire si :
- Note initiale < 10
- le rattrapage peut être demandé par l'étudiant si :
- Note initiale < 10
- Crédits ECTS acquis : 5 ECTS
La note obtenue rentre dans le calcul de votre GPA.
Programme détaillé
- Introduction à la programmation logique avec contraintes, unification de termes
- TD bases de données déductives, calcul symbolique
- Sémantique opérationnelle des langages CLP(X), preuves de programmes
- TD navigation in a map
- Algorithmes de filtrage des domaines et propagation de contraintes
- TD programmation d'un solveur arithmétique d'intervalles
- Procéures de recherche et heuristiques
- TD ordonnancement disjonctif
- Contraintes de brisure de symétries
- TD coloriage de graphes, élmination des symétries dans les problèmes de placement
- Constraintes sur les nombres rééls CLP(R)
- TD planification de production et analyse coût-bénéfices
- Modèles booléens et solveurs SAT
- TD Programmiation d'un solveur SAT
- NP-complétude et transitions de phases
- TD problèmes k-SAT aléatoires et coloriage de graphes aléatoires
- Recherche locale à base de contraintes
- TD algorithmes d'escalade, recuit simulé, recherche Tabu, pour la satisfaction de contraintes.
- Examen final.