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 et des contraintes, et leur résolution par des algorithmes généraux de réécriture de contraintes symboliques, logiques et arithmétiques.
Chaque cours magistral de 2h est suivi de 2h de travaux dirigés sur ordinateurs individuels pour illustrer les concepts vus de programmation logique avec contraintes, et programmer dans le langage Prolog et ses bibliothèques de modélisation, la résolution de problèmes de représentation des connaissances et d'aide à la décision.
Modalités d'évaluation : 50% 7 meilleurs sur 9 TPs, 50% examen écrit
Langue du cours : documents en anglais, oral en anglais sur demande
Crédits ECTS: 4
Diplôme(s) concerné(s)
- Programmes d'échange internationaux
- MScT-Artificial Intelligence and Advanced Visual Computing
- Titre d’Ingénieur diplômé de l’École polytechnique
Parcours de rattachement
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
- Résolution de contraintes par filtrage des domaines
- 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
- Algorithmes évolutionnaires à base de contraintes
- TD algorithmes d'escalade, recuit simulé, recherche Tabu, pour la satisfaction de contraintes.
- Examen final.