Algèbre appliquée - semestre de printemps 2014

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)

Notes de cours et de travaux dirigés

Polycopié printemps 2014 (petites corrections le 18/03/2014)

Cours

  • Cours 1 - Polynômes à plusieurs indétermininées; ensembles algébriques affines; idéaux (lundis 27/01 et 3/02) : Polynômes à plusieurs indéterminées, ensembles algébriques affines (exemples via SAGE), opérations sur les ensembles algébriques affines, présentation de problèmes associés aux systèmes d'équations algébriques (résolution de systèmes, équation algébrique impliquée par un système), idéal d'un ensemble algébrique affine, idéaux finiment engendrés, <f1,…,fs> inclus dans I(V(f1,…,fs)), présentation de problèmes associés aux idéaux (tout idéal est-il finiment engendré ? question de l'appartenance à <f1,…,fs>).
  • Cours 2 - Anneau des polynômes à une indéterminée (lundis 3/02 et 10/02) : Division euclidienne dans K[x], tout idéal de K[x] est principal, <f1,…,fs>= <PGCD(f1,…,fs)>, algorithme d'Euclide, utilisation pour répondre à la question de l'appartenance à <f1,…,fs>.
  • Cours 3 - Ordres et ordres monomiaux (lundis 10/02 et 17/02) : Relation 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 de l'ordre lexicographique, tout ordre monomial est un bon ordre, terme dominant d'un polynôme et propriétés, définition de l'ordre lexicographique gradué.
  • Cours 4 - Algorithme de division en plusieurs indéterminées (lundi 24/02) Algorithme de division, réduction modulo une famille de polynômes, forme normale, confluence, propriété recherchée (base de Gröbner) pour que la réduction en 0 (ou reste nulle par division) correspond à l'appartenance à l'idéal engendré.
  • Cours 5 - Bases de Gröbner (lundis 10/03 et 17/03) : idéaux monomiaux et lemme de Dickson; 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 (réponse à la question de l'appartenance à un idéal par l'algorithme de division ou réduction, voir fin cours 4).
  • Cours 6 - Algorithme de Buchberger (lundis 24/03 et 31/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).
  • Cours 7 - Premières applications des bases de Gröbner (lundi 7/04) : Appartenance à un idéal, résolutions d'équations polynomiales, idéal d'élimination, illustration avec une feuille de calcul sage.
  • Cours 8 - Applications des bases de Gröbner à la géométrie élémentaire (lundis 7/04 et lundi 14/04) : exemple de la droite de Gauss-Newton, hypothèses de généricités, théorème de Poncelet (illustrations sur Geogebra, feuille de calcul Sage)
  • Cours 9 - Application des bases de Gröbner au problème des 3 couleurs (lundi 14/04) : exemple du coloriage de la carte des régions de France, résumé historique du théorème des 4 couleurs, problème des 3 couleurs (pb NP-complet), caractérisation à l'aide d'un idéal de la possibilité de colorier une carte avec seulement 3 couleurs (théorème des zéros de Hilbert admis), exemples (cartes, feuille de calcul Sage). Exercices sur Sage : vérifier que la carte des lands allemands ne peut être coloriée avec seulement 3 couleurs. Est-ce encore le cas, avec la même carte sans la Saxe ?
  • Cours 10 - Application des bases de Gröbner à la programmation linéaire en nombres entiers (lundi 5/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

Planning prévisionnel

  • Les cours auront lieu les lundis de 14h à 16h (premier cours lundi 27 janvier) et les TD et TP les vendredis de 9h45 à 13h (premier TD vendredi 7 février).
  • Quatre séances de TP sur SAGE sont prévues : les vendredis 21/02, 4/04, 25/04 et 16/05.
  • Contrôles : CC1 lundi 10/03 (20%) (Sujet avec corrigé), CC2 lundi 14/04 (20%) (Sujet), Travail en groupes sur SAGE (20%), CCF le 6/06 (40%) (Sujet)

Emploi du temps sur ADE (Groupe A : TD en Darwin 82, Groupe B : TD en Darwin 80)

 
 
Valid XHTML 1.0 Valid CSS Driven by DokuWiki