Introduction aux bases de Gröbner et à leurs applications
Thomas Blossier (responsable du cours), Jean-Christophe Beniere et Xavier Roblot (chargés des TD et des TP)
Cours
Cours 1 (vendredi 31/01) : présentation du cours, rappel sur les anneaux de polynômes à une indéterminée (division euclidienne, PGCD, identité de Bézout et algorithme d'Euclide, racines).
Cours 2 (lundis 2/02 et 9/02) : Polynômes à plusieurs indéterminées, ensembles algébriques affines, opérations sur les ensembles algébriques affines, idéal d'un ensemble algébrique affine, idéaux finiment engendrés, <f1,…,fs> inclus dans I(V(f1,…,fs)), idéaux de K[x]. Polycopié chapitres 1 et 2
Cours 3 (lundis 9/02, 23/02 et 2/03) : Relations d'ordre : exemples, ordres totaux, bons ordres, caractérisation des bons ordres par suites strictement décroissantes, principe de récurrence sur les bons ordres. Ordres monomiaux (exemples : ordre lexicographique et ordre lexicographique gradué). Algorithme de division, exemples, problème de non unicité du reste, interprétation de l'algorithme de division en termes de réductions et de formes normales, confluence, définition des bases de Gröbner et propriétés. Polycopié chapitre 3
Cours 4 (lundis 9/03 et 23/03) : Idéaux monomiaux (définition, exemples, lemme de Dickson admis), Idéal des termes dominants et bases de Gröbner. Théorème de la base de Hilbert et d'existence de bases de Gröbner; rappel rapide des premières propriétés des bases de Gröbner. (Polycopié chapitre 4)
Intermède (lundi 16/03) : Théorème des 4 couleurs. Problème du coloriage d'une carte en 3 couleurs. Traduction en termes d'idéaux (version faible du théorème des zéros de Hilbert admis). Généralisation aux coloriages de graphes. (Polycopié chapitre 8)
Cours 5 - Algorithme de Buchberger (lundis 23/03 et 30/03) : S-polynômes et paires critiques, critère de Buchberger, algorithme de Buchberger, exemple de calculs d'une base de Gröbner, cas particuliers pour les calculs (termes dominants de f et g premiers entre eux; terme dominant de g divisant le terme dominant de f). (Polycopié chapitre 5)
Cours 6 - Premières applications des bases de Gröbner (lundi 20/04) : Résolutions d'équations polynomiales, idéal d'élimination, implicitation d'ensembles paramétrés, illustration avec une feuille de calcul sage. (Polycopié chapitre 6)
Cours 8 - Application des bases de Gröbner à la programmation linéaire en nombres entiers (lundi 4/05) : exemples de problèmes linéaires (dont le problème du voyageur de commerce). Traduction par une équation algébrique et utilisation d'une base de Gröbner avec un ordre monomial adapté. Exemples : voir feuille de calcul Sage. (Polycopié chapitres 9 et 10)
Quatre séances de TP sur SAGE sont prévues : les vendredis 20/03, 10/04, 24/04 et 22/05. (Annexe poly sur SAGE)
Contrôles : CC1 lundi 9/03 (20%) (Sujet avec correction), CC2 lundi 27/04 (10%) (Sujet), Travail en groupes sur SAGE (30%), CCF vendredi 5 juin à 8h (40%)