option C 2013/2014 UJF

Utilisation à l'épreuve de modélisation de l'agrégation de mathématiques

Modérateur : xcasadmin

parisse
Messages : 4886
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: option C 2013/2014 UJF

Message par parisse » mer. févr. 26, 2014 11:27 am

Reduction de Smith et application aux groupes abeliens de type fini. On fait Hermite sur les lignes puis sur les colonnes puis a nouveau sur les lignes etc., le processus finit par s'arreter (pour i,j fixes, regarder comment evoluent a_ii, a_jj, a_ij et a_ji si l'un des non diagonaux est non nul, a l'etape suivante on en prend le pgcd avec a_ii ou a_jj et l'autre coeff non diagonal devient plus petit, d'un facteur 2 si on choisit le reste symetrique pour l'etape finale de reduction de Hermite au-dessus de la diagonale par quotient euclidien).
Exemple recherche de la structure du groupe abelien defini par les generateurs x1 et x2 et les relations 2x1+4x2=0 et -2x1+6x2=0, on pose A:=[[2,4],[-2,6]] puis U,B,V:=ismith(A), on en deduit que les diviseurs elementaires sont 2 et 10 donc G est isomorphe a Z/2*Z/10, avec comme generateurs V^(-1)*[x1,x2] soit y1=x1+2x2 et y2=x2 (on a bien 2y1=0 et 10y2=0).

Reduction des endomorphismes:
a/ Interpolation de Lagrange si le cardinal du corps est > n la dimension de la matrice. O(n^4) opérations au lieu de O(n^3) opérations ... mais sur K[X] (c'est mieux car multiplication naive sur K[X] est en O(n^2))
b/ Recherche du polynome minimal relatif à un vecteur aléatoire, il divise le polynome minimal de la matrice donc le polynome caractéristique de la matrice, donc s'il est de degré n, on en déduit que les 3 sont égaux (une fois normalisés). On cherche le noyau de la matrice dont les colonnes sont v_0=v, ..., v_{k+1}=Av_k, ..., v_n=Av_{n-1}. Algorithme en O(n^3) mais ne marche pas toujours (-> Hessenberg marche par contre toujours en O(n^3) cf. Cohen)
c/ Algorithme de Fadeev : (x*I-A)*B(x)=det(x*I-A) I, B(x) transposée de la comatrice de x*I-A. On calcule les coefficients en puissance décroissante de B par une méthode à la Horner, en utilisant une relation supplémentaire pour calculer simultanément les coefficients de det(xI-A) qui est
trace(B(x))=derivée de det(x*I-A)
Algorithme en O(n^4), qui donne en plus B(x) qui peut servir à calculer les espaces propres puisque si x0 est valeur propre simple alors (x0*I-A)*B(x0)=0 et B(x0) n'est pas nul (sinon on divise B(x) par x-x0 et en x0 on a (x0*I-A)*B(x)/(x-x0)=det(x*I-A)/(x-x0)I est inversible alors que (x0*I-A) ne l'est pas). On calcule seulement la 1ere colonne de B(x0) par Horner, si elle est nulle, la 2eme etc. en general on trouve l'espace propre en O(n^2) operations par espace propre (au lieu de O(n^3)).

parisse
Messages : 4886
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: option C 2013/2014 UJF

Message par parisse » jeu. mars 20, 2014 2:37 pm

4 mars: vacances de Grenoble
11 mars: ecrits

18 mars: TP algebre lineaire.
1/ essai de la commande det et ses differentes options pour choisir l'algorithme utilise (Bareiss, interpolation de Lagrange, developpement, modulaire ou p-adique), sur des matrices a coeffs entiers, dans Z/pZ, a coefficient symbolique (purge(a); A:=matrix(4,4,(j,k)->a[j,k])
2/ ecriture d'un programme calculant le polynome caracteristique d'une matrice A par recherche du polynome minimal relativement a v (recherche du noyau de la matrice avec en colonnes v,Av,A^2v,..,A^nv).
Discussion sur la complexite, attention a utiliser v:=A*v pour calculer la suite des vecteurs
3/ programmation de l'algorithme de Leverrier, Fadeev, Souriau. La commande Xcas correspondante est adjoint_matrix

parisse
Messages : 4886
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: option C 2013/2014 UJF

Message par parisse » mer. mars 26, 2014 5:03 pm


parisse
Messages : 4886
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: option C 2013/2014 UJF

Message par parisse » mar. avr. 01, 2014 1:41 pm

1er avril: interpolation de Lagrange.
Méthode 1: polynomes de Lagrange (produit pour j different de i de (x-x_j)/(x_i-x_j)), calcul sous forme factorisee d'un polynome en O(n), calcul du polynome interpolateur en O(n^2) mais évaluation en O(n^2) au lieu de O(n) pour Horner, et le developpement coute O(n^2) opérations par polynôme donc O(n^3) opérations.
Méthode 2: par récurrence, on obtient une écriture ressemblant à Horner évaluable en O(n) opérations, cf. le manuel Algorithmes de Xcas, chapitre 16. Le calcul des coefficients par les différences divisées se fait en O(n^2) opérations.
Méthode 3: on cherche les coefficients du polynôme en posant un système linéaire n+1,n+1 (la matrice du système est une matrice de Vandermonde); Temps de calcul en O(n^3)
Donc il faut utiliser les différences divisées!
Applications: calcul du polynôme caractéristique, calcul de primitive discrète d'un polynôme, i.e. chercher Q tel que Q(X+1)-Q(X)=P(X), le calcul est simple dans la base X,X*(X-1), X*(X-1)*(X-2), ... et l'expression de P dans cette base se fait en interpolant P en 0,1,2,..,degre(P).
TP: programmation de l'algo des différences divisées (un exemple de solution se trouve dans le chapitre 16) et de l'évaluation en un point avec les coefficients renvoyés.

parisse
Messages : 4886
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: option C 2013/2014 UJF

Message par parisse » mar. avr. 08, 2014 1:51 pm

8/4: factorisation d'entiers et test de primalite.
Voir chapitre 10 du manuel algorithme de Xcas.
Exercice: generer un premier p par exemple avec nextprime puis lancer isprime(p,1), expliquer le certificat de primalite obtenu (voir dans Aide->Manuel->PARI/GP pour les explications concernant la commande isprime de PARI dans la section Arithmetique) et faire le lien avec le théorème 13.
Exercice: programmer Pollard-rho (correction dans le menu Exemples>arit>pollard.xws).
Exercice: programmer le certificat de primalite du théorème 13 (recherche des a_p).

parisse
Messages : 4886
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: option C 2013/2014 UJF

Message par parisse » mar. avr. 15, 2014 1:51 pm

15/4: texte sur le partage de secret (jury 2009).
Remarque/conseils: la methode naive du 2.2 est l'ecriture en base 2^tau, exemple si s est le secret (par exemple s:=123,t=9, n=3 donc tau=3)
l:=convert(s,base,2^3) va partager le secret et convert(l,base,2^3) le reconstruit.
L'étude de la sécurité du paragraphe 2.3 est plus difficile que la compréhension du système résistant du paragraphe 3, qui est juste de l'interpolation de Lagrange, et se programme facilement: http://www-fourier.ujf-grenoble.fr/~par ... secret.xws, ce qui peut permettre de faire une partie d'expose honorable avec un petit blabla sur l'algorithme de Horner pour faire le partage, et les differences divisées et la substitution de x par 0 pour la reconstruction (complexités en fonction de n, discussion sur le corps de base...).

parisse
Messages : 4886
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: option C 2013/2014 UJF

Message par parisse » mer. avr. 23, 2014 11:04 am

22/4: texte du jury sur les codes correcteurs avec "tour de magie"
Remarques: ce texte date de l'epoque ou il n'y avait pas d'option C, et pas de codes de Hamming binaires au programme, aujourd'hui les candidats sont censes connaitre les defs donnees dans le texte...
Questions possibles (en plus des suggestions): quels sont les caracteristiques de codes analogues permettant de corriger une erreur ? Par exemple le suivant est n=15, k=11, quels avantage et inconvenients par rapport a celui du jury? Si le taux d'erreur par bit est de 1e-3 par exemple, quelle est la probabilite d'avoir 2 erreurs ou plus (donc de corriger improprement)?
-> Pour n=15, la proba de mauvaise correction est superieure au cas ou n=7, c'est un inconvenient, par contre le taux de transmission d'information utile est superieur (11/15 vs 4/7). Selon le type de donnees a transmettre, on choisira plutot n=7 que n=15, ou on utilisera un code permettant de corriger plus qu'1 erreur

calcul de l'expression de suites recurrentes lineaires/affines (fonctions de Xcas utiles: rsolve, matpow, jordan), voir la section du chapitre Suites du manuel algorithmes de Xcas. Applications: resolution de recurrence apparaissant dans des calculs de complexite, comme la multiplication de Karatsuba ou Strassen, il faut parfois faire un changement d'indice pour s'y ramener, par ex. u_{2n}=3u_n+8, poser n=2^m

parisse
Messages : 4886
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: option C 2013/2014 UJF

Message par parisse » mar. mai 13, 2014 1:37 pm

29/4: vacances de Grenoble.
6/5: oraux blancs, choix entre les 2 textes du jury systèmes linéaires sur N et parametrisation d'une courbe algébrique de degré d ayant 1/2*(d-1)*(d-2) points singuliers.
13/5: retour sur le 2ème texte et courbes algébriques.
Composante irréductible sur C[X,Y]: calcul de la factorisation absolue (differente de la factorisation sur Q[X,Y]) sur l'exemple du manuel algorithmes (menu Aide, Manuels, Algorithmes, rechercher factorisation absolue dans l'index).
Point regulier: tangente (-dP/dy,dP/dx)
Point singulier: definition (dP/dx,dP/dy)=(0,0). Generiquement pas de points singuliers (3 équations à 2 inconnues). Par contre pour une famille de courbes, on a génériquement des valeurs du paramètre pour lesquelles il y a des points singuliers (3 équations à 3 inconnues). Exemple x^4-x^2+y^2+a avec a proche de 0. Le point singulier correspond à 2 (ou plus) arcs de courbes se rapprochant pour la valeur du paramètre où ils se coupent.
Multiplicité du point singulier (supposé en (0,0)): plus petite valeur de m telle que la partie homogène du polynôme (développement de Taylor si on n'est pas en (0,0)) de degré m est non nulle. C'est au moins 2 pour un point singulier. Puis étude locale lorsque ce polynome homogène de degré m a toutes ses racines simples (arcs de courbes avec comme coefficient directeur des tangentes les racines en t de P_m(1,t)).

Exercice de révision sur les complexités: Complexité du calcul du n-ième terme de la suite de Fibonacci F_n
1ere méthode: en appliquant simplement la récurrence,
2ème méthode: on calcule F_n modulo suffisamment de nombres premiers pour pouvoir en déduire F_n. Pour chaque nombre premier, on utilise la récurrence à un cran
u_{n+1}=A*u_n où u_n est le vecteur (F_n,F_{n+1}) et A la matrice [[0,1],[1,1]] qui donne u_n=A^n *u_0 et on calcule A^n mod p par la méthode de la puissance rapide.

=========================

========================
Réponse: 1ère méthode O(n^2) car la taille des nombres à additionner à l'étape i est proportionnelle à i (rappel on obtient un équivalent de F_n en résolvant analytiquement la récurrence, équation caractéristique r^2=r+1 ou avec rsolve)
2ème méthode le calcul de A^n mod p se fait en O(log(n)) opérations, il faut O(n) nombres premiers de taille proche (disons de taille environ 2^30 pour se fixer les idées) puisqu'il suffit que le produit des premiers choisis soit > à F_n pour reconstruire F_n. Donc il faut O(n*log(n)) opérations ... sous réserve de vérifier que la reconstruction par les restes chinois n'est pas plus couteuse!

Session d'illustration
http://www-fourier.ujf-grenoble.fr/~par ... g/fibo.xws
Remarque: pour l'addition simple (1ère méthode)

Code : Tout sélectionner

f(n):={
  local k,u,v,w;
  u:=1; v:=1;
  pour k de 2 jusque n faire
    w:=u+v;
    u:=v;
    v:=w;
  fpour;
  retourne v;
}:;
on observe un temps de calcul presque linéaire et non quadratique. Cela vient du fait que le langage est interprété, le temps d'exécution des :=, du test de la boucle et de l'incrémentation dominent le temps de calcul de l'addition de u et v, la complexité est de la forme a*n+b*n^2, mais a est tellement grand devant b que le terme b*n^2 se voit à peine.

parisse
Messages : 4886
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: option C 2013/2014 UJF

Message par parisse » mar. mai 20, 2014 12:52 pm

20 mai: revision sur calcul du noyau de M dans Q avec la decomposition L*tran(M)=U (L et U s'obtiennent en faisant ref(tran(op(M),idn(ncols(M))) ou par décomposition LU de tran(M) en inversant L, mais attention a la permutation si on utilise lu). Alors M*tran(L)=tran(U) donc pour résoudre M*x=0, on pose x=tran(L)y, on doit alorsrésoudre tran(U)*y=0, ce qui est très facile puisque U est triangulaire supérieure, puis x=tran(y) pour les vecteurs de base trouvés en y. Aux lignes nulles de U correspondent des lignes de L qui sont dans le noyau. Le même raisonnement mais sur Z au lieu de Q et avec ihermite(tran(M)) permet de résoudre un système linéaire sur Z.
Révision sur le degré du résultant et du résultant homogène, s'ils sont différents cela correspond à un point à l'infini dans le cas d'intersection de courbes algébriques, cf. la section Résultants et degrés dans Aide->Manuel->Algorithmes.

Localisation des racines d'un polynôme dont on connait une racine approchée.
Si delta=module(P(z)/P'(z)), alors le disque B(z,n*delta) contient au moins une racine.
Preuve: P'/P=dérivée log de P=somme sur les n racines de 1/(z-racine)
et on raisonne par l'absurde.
On peut ainsi certifier l'existence de racines d'un polynôme, en prenant pour z un rationnel proche d'une racine approchée calculée par proot ou tout autre méthode numérique (voir la commande exact). Par exemple P:=x^4+3x+1; L:=proot(P); z:=exact(L[0]); d:=horner(P,z)/horner(P',z);

Fin du TP sur Fibonacci du 13 mai. La reconstruction par les restes chinois est en O(n^2), donc l'algorithme modulaire n'est pas interessant. En effet, on commence par faire Bezout sur p1 et p2, puis sur p1*p2 et p3, puis etc. jusqu'a p1*p2*...*p_{n-1} et p_n, en temps O(1+2+...+n).

parisse
Messages : 4886
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: option C 2013/2014 UJF

Message par parisse » mar. mai 27, 2014 12:53 pm

27 mai:
Générateurs congruentiels (réf. Knuth ou version condensée dans Aide, Manuels, Algorithmes)
u_{k+1}=a*u_k+c mod m
Si m est premier, c=0, et a générateur de (Z/mZ)* alors on a une périodicité presque maximale, égale à m-1 (u_k parcourt en effet tous les entiers sauf 0).
Théorème: la périodicité maximale possible (m) est atteinte si et seulement si
1/ c et m sont premiers entre eux
2/ a-1 est divisible par tous les facteurs premiers de m
3/ si m est divisble par 4, alors a-1 est divisible par 4
Si on écrit la récurrence en langage compilé, l'opération la plus couteuse en temps de la récurrence est la division euclidienne par m pour avoir le reste. Lorsque m est une puissance de 2 à un près, on peut accélérer cette étape en divisant par la puissance de 2 par décalage de bit A=2^nq+r puis A=(2^n-1)q+(r+q), on compare r+q à 2^n-1 pour voir s'il faut enlever 2^n-1 à r+q ou le laisser tel quel.
Exemple: création d'un générateur congruentiel de période m-1 avec m=2^31-1 qui est premier (vérif avec isprime). Pour trouver un a générateur de Z/mZ*, il faut vérifier que powmod(a,(m-1)/d,m) est différent de 1 lorsque d est un diviseur premier de m-1. Utiliser ifactors(m-1) pour avoir la liste des facteurs premiers de n-1 (liste alternant facteur et muiltiplicité).
Tester ensuite si le générateur est raisonnable: générer 10000 réels entre 0 et 1 (en divisant par m), en faire un histogramme avec des classes de largeur 0.01, ou générer 10000 points dans le carré [0,1]x[0,1] et observer leur répartition (par ex. a=7 n'est pas très bon!).
Voir aussi ce que donne la méthode de Monte-Carlo pour estimer par ex. int(exp(-x^2),x,-2,2) avec ce genérateur!
Sessions de correction: http://www-fourier.ujf-grenoble.fr/~parisse/rand.xws,
http://www-fourier.ujf-grenoble.fr/~par ... ecarlo.xws
N.B.: Xcas n'utilise plus un générateur congruentiel (mais un Mersenne Twister).

Répondre