Descriptif
Ce cours présente des méthodes d'intelligence artificielle formelle 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 principes de résolution logique.
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.
Modalités d'évaluation :
50% examen écrit,
50% moyenne des 7 meilleures notes données aux 9 TDs (la note de TD 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 TD).
Langue du cours : documents en anglais, oral en anglais sur demande
Crédits ECTS: 4
effectifs minimal / maximal:
/25Diplô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 réduitPour les étudiants du diplôme Titre d’Ingénieur diplômé de l’École polytechnique
Le rattrapage est autorisé (Note de rattrapage conservée)- Crédits ECTS acquis : 5 ECTS
La note obtenue rentre dans le calcul de votre GPA.
Pour les étudiants du diplôme M1 MPRI - Fondements de l'Informatique
L'UE est acquise si note finale transposée >=- Crédits ECTS acquis : 5 ECTS
Pour les étudiants du diplôme MScT-Artificial Intelligence and Advanced Visual Computing
Le rattrapage est autorisé (Note de rattrapage conservée)- 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
Le rattrapage est autorisé (Note de rattrapage conservée)- 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
- TD représentation des connaissances en Datalog avec contraints
- Logique des predicats du premier ordre et égalité sur les termes
- TD calcul symbolique sur listes et tableaux en Prolog
- Algorithmes de filtrage des domaines et propagation de contraintes
- TD programmation en Prolog d'un solveur de contraintes sur les nombres entiers
- Procéures de recherche et heuristiques
- TD comparaison d'heuristiques, 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 en Prolog 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.