Algèbre appliquée - semestre de printemps 2013

Thomas Blossier (responsable du cours), Riccardo Biagioli et Xavier Roblot (chargés des TD et des TP)

Emploi du temps

Planning sur ADE

Contrôles

CC1 (20% - Lundi 18 mars) : sujet, corrigé
CC2 (20% - Lundi 29 avril 14h-15h30) : sujet, corrigé (Pour réviser : sujet du contrôle continu du 27 avril 2012 et corrigé)
CC3 (20% - Travail en groupes sur SAGE)

CCF (40% - Vendredi 14 juin -date à confirmer) : le sujet portera uniquement sur la première partie du cours. (Pour réviser, voir 1ère partie du contrôle final de 2012 : sujet)

Cours

Partie 1 : Introduction aux bases de Gröbner et à leurs applications

Cours I - Polynômes à plusieurs indétermininées; ensembles algébriques affines; idéaux (lundi 28/01) : rappel structures de nombres (N, Z, Q, R, C), plus exemple du corps à 2 éléments; Polynômes à plusieurs indéterminées, ensembles algébriques affines (exemples via SAGE), opérations sur les ensembles algébriques affines.
Cours I(Suite) (lundi 4/02) : Présentation de problèmes associés aux systèmes d'équations algébriques (résolution, implicitation de systèmes paramétrés, é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 II - Anneau des polynômes à une indéterminée (lundi 4/02) : Division euclidienne dans K[x], tout idéal de K[x] est principal, <f1,f2>=<pgcd(f1,f2)>.
Cours II(Suite) (lundi 11/02) : algorithme d'Euclide, <f1,…,fs>= <PGCD(f1,…,fs)>, utilisation pour répondre à la question de l'appartenance à <f1,…,fs>.
Cours III- Algorithme de division en plusieurs indéterminées (lundi 11/02) : Exemple des systèmes linéaires; Ordres (ordre total, bon ordre, ordre monomial, exemple de l'ordre lexicographique).
Cours III(Suite) (lundi 18/02) : propriétés des ordres monomiaux (tout ordre monomial est un bon ordre), définition du multidegré, algorithme de division.
Cours IV - Bases de Gröbner (lundi 4/03) : définition des bases de Gröbner et propriétés de la division par une base de Gröbner; idéaux monomiaux et lemme de Dickson; Théorème de la base de Hilbert et d'existence de bases de Gröbner.
Cours V - Algorithme de Buchberger (lundi 11/03) : réduction, confluence, S-polynômes et paires critiques, critère de Buchberger.
Cours V(Suite) (lundi 18/03) : algorithme de Buchberger; exemple de calculs d'une base de Gröbner.
Cours VI - Premières applications des bases de Gröbner (lundi 25/03) : Appartenance à un idéal, résolution d'équations polynomiales, méthode d'élimination.
Cours VII - Applications des bases de Gröbner à la géométrie élémentaire (lundi 8/04).

Partie 2 : Le théorème de Perron et une application aux moteurs d'indexation du web

Cours I - Matrice du PageRank (lundi 15/04) : Chaînes de Markov, matrices stochastiques, marche aléatoire sur un graphe orienté, formalisation du PageRank. Exemple d'une marche aléatoire (page web, fichier Geogebra)
Cours II - Calcul des puissances d'une matrice (vendredi 3/05) : rappels décomposition spectrale, diagonalisation et trigonalisation. Cas particulier d'une matrice ayant 1 comme valeur propre simple et dominante. Exemples : feuille de calcul Sage (sws, pdf)
Cours III - Théorème de Perron (lundi 6/05) : Enoncé du théorème, application du théorème aux matrices stochastiques strictement positives, preuve du théorème.

Notes de cours et de travaux dirigés

Notes de Philippe Malbos du printemps 2012 (très légèrement modifiées au printemps 2013)

Partie 1 : Introduction aux bases de Gröbner et à leurs applications

Préliminaires algébriques (pdf; format livret)
Polynômes, ensembles algébriques affines et idéaux (pdf,format livret)
Prise en main du système de calcul Sage (pdf, format livret)
Algorithmes de division (pdf, format livret)
Les bases de Gröbner (pdf, format livret)
L'algorithme de Buchberger (pdf, format livret)
Premières applications des bases de Gröbner (pdf, format livret)
Applications des bases de Gröbner à la géométrie élémentaire (pdf, format livret) (Nouveau chapitre printemps 2013)
D'autres applications des bases de Gröbner (pdf, format livret) (Ce chapitre ne sera pas traité en cours)

Partie 2 : Le théorème de Perron-Frobenius et les moteurs d'indexation du web

Partie 2 complète : pdf (le chapitre II a été en partie modifié au printemps 2013)
Référence : Langville, Meyer, Google's PageRank and beyond : the science of search engine rankings (empruntable à la BU Sciences au 4ème étage côte 004.678 LAN)