option C 2015/16

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

Modérateur : xcasadmin

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

option C 2015/16

Message par parisse » jeu. sept. 17, 2015 11:50 am

16/9:
Chapitre I: representation des objets mathematiques, algorithmes fondementaux.
1/ entiers machine, precision limitee. Entiers long, lien avec les polynomes.
2/ cout des operations de base + - * sur les entiers (algorithme naif) et comparaison avec la taille du resultat, il existe des algorithmes meilleurs pour la multiplication (ce qu'on peut deviner vu la taille du résultat),
3/ division en O(n^2) + precisement a=b*q+r en O(#b*#q) ou #b=nombre de bits de b, le calcul des bits de q en base 2 a un cout nul
a/ PGCD binaire: si a ou b est nul on renvoie l'autre, si a et b sont pairs pgcd(a,b)=2*pgcd(a/2,b/2), si a est pair b impair, pgcd(a,b)=pgcd(a/2,b), si les 2 sont impairs pgcd(a,b)=pgcd((a-b)/2,min(a,b)) temps en O(n^2) pour entiers longs de taille n,
b/ identite de Bezout pour a>=b>0 a*u+b*v=pgcd(a,b) calcul de u et v avec u_0=1, u_1=0, v_0=0, v_1=1, r_0=a, r_1=b.
Pour verifier
a*u_n+b*v_n=r_n
on definit u_n et v_n par recurrence
u_(n+2)=u_n-q_n*u_(n+1)
v_(n+2)=v_n-q_n*v_(n+1)
ou r_(n+2)=r_n-q_n*u_(n+1)
On a par récurrence v_n*r_(n+1)-v_(n+1)*r_n=(-1)^n*a, et |v_n| strictement croissante, au cran apres Bezout, on a v_n*pgcd(a,b)=a d'ou la suite |v_n| est majoree par a et |v|<a. De meme on prouve que |u|<b.
Complexite en O(taille(max(a,b))^2).
4/ etude detaillee de Karatsuba pour multiplier 2 polynômes à coeffs dans un corps fini de degre<2^n -> temps en 9*3^n-8*2^n, existence d'un seuil pour multiplication naive puis Karatsuba.
Illustration avec la session Exemples>arit>multpoly de Xcas.
Esquisse de l'algorithme de multiplication de 2 polynômes à coeffs approchés par FFT
Si P1 et P2 sont 2 polynomes tels que degré(P1*P2)<n, il suffit de connaitre P1*P2 en n points pour déterminer P1*P2, par exemple les puissances xi^j d'une racine primitive n-ième complexe de 1. Comme P1*P2(x)=P1(x)*P2(x), il suffit de savoir passer des coefficients de P1 (complétés par des 0 pour en avoir n) aux valeurs P1(xi^j) et réciproquement, ce qui est la transformée de Fourier discrète (dft) de C^n dans C^n et son inverse (qui se calcule par une dft en changeant xi en 1/xi). Si n est pair, le calcul de dft(P) se déduit du calcul de dft(coeffs_pairs_de_P) et dft(coeffs_impairs_de_P) en O(n) opérations, car P(x)=Ppair(x^2)+x*Pimpair(x^2) et xi^2 est une racine primitive n/2-ième de 1. Donc si n est une puissance de 2, le calcul de dft(P) se fait en O(n*ln(n)) opérations (algorithme de la fft).

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

Re: option C 2015/16

Message par parisse » jeu. oct. 01, 2015 3:34 pm

23/9 TP programmation de Bezout, restes chinois, inverse modulaire

30/9:
autre methode iterative pour Bezout avec a*u_n-b*v_n=(-1)^n*r_n, les suites u_n et v_n verifient u_{n+2}=u_n+q_n*u_{n+1} et v_{n+2}=v_n+q_n*v_{n+1}, et sont donc positives, et on a la relation u_n*r_{n+1}+u_{n+1}*r_n=b et v_n*r_{n+1}+v_{n+1}*r_n=a.
Lien avec la decomposition en fraction continue de a/b=[q0,...,q_{N-1}], l'avant-derniere reduite [q0,...,q_{N-2}]=v_N/u_N ou u_N et v_N sont les coefficients de Bezout de a et b definis comme ci-dessus. On montre pour cela par recurrence que
[q0,...,q_{n-1},x]=(v_n+x*v_{n+1})/(u_n+x*u_{n+1})
et on fait x=q_n et n=N-2
Applications: inverse modulaire, restes chinois.
Les restes chinois permettent de calculer par exemple le determinant d'une matrice a coeff entiers en le calculant pour plusieurs nombres premiers dont le produit est > a 2 fois une borne a priori sur le determinant (produit des normes des vecteurs lignes ou colonnes).

puissance modulaire rapide, algorithme récursif et itératif, le calcul de a^n mod p se fait en log2(n) etapes necessitant chacune 1 ou 2 multiplications et 1 division d'entiers <p^3 (O(ln(p)^2) operations par des methodes naives).
Applications
1/ test de Miller-Rabin. Complexité en O(ln(p)^3) si on multiplie les entiers naivement.

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

Re: option C 2015/16

Message par parisse » jeu. oct. 15, 2015 3:25 pm

7/10 TP vitesse de multiplication des polynomes et entiers sur des exemples et comparaison avec naif, Karatsuba. Programmation de la puissance rapide.

14/10
Racine carre modulo p, cas ou p=1 [4] par calcul de gcd(x^2-a,(x+r)^(p-1)/2-1) mod p avec r aleatoire. Calcul des complexites. On calcule (x+r)^((p-1)/2) modulo p, x^2-a par la puissance rapide.

Racine carree entiere de a par l'algorithme de soustraction d'impairs consecutifs, exercice: determiner la complexite si n est le nombre de chiffres de a.

Representation des objets mathematiques :
* polynomes à 1 variable: représentation dense par la liste des coefficients, complexite de + - * pgcd (comme pour les entiers en remplacant nombre de chiffres par degre)
* polynomes à plusieurs variables, représentation creuse, ordre des monomes (ex. ordre lexicographique), multiplication en O(n*m*ln(taille du produit)), discussion sur la densité (formule comb(n+d,n) pour le nombre de monomes possibles d'un polynome de degre total d en n variables)
* flottants m*b^e ou b=base (en général 2 ou 10), n precision, la mantisse m est dans [b^(n-1),b^n-1], l'exposant e dans une plage [-l,L] fixee a l'avance. Dans Xcas, si Digits>14 on utilise des flottants multiprécision (m entier long de taille n paramétrée par Digits), sinon des flottants "double" avec 53 bits de mantisse. Erreur relative de representation.
Arithmetique d'intervalles.

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

Re: option C 2015/16

Message par parisse » mar. nov. 10, 2015 1:49 pm

21/10: TP programmation de Horner, puis Taylor P(x+a) en utilisant Horner.

4/11: 2 oraux prepares (texte du jury sur RSA).

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

Re: option C 2015/16

Message par parisse » jeu. nov. 19, 2015 6:33 pm

18/11:
Retour sur le texte RSA du jury, plus particulierement sur la méthode de Pollard-rho:
théorème des anniversaires, la proba d'avoir n nombres entre 0 et N-1 distincts 2 à 2 est équivalente pour N grand à exp(-n^2/(2*N)) si n^2/N tend vers une limite non nulle (on calcule ln(P), on encadre avec une integrale).
Pour l'appliquer à un entier n à factoriser, notons N le plus petit facteur premier de n. On génère les n entiers par une suite récurrente u_{k+1}=f(u_k), avec typiquement f(x)=x^2+1 mod n. Comme on ne connait pas N, on teste l'égalité modulo N par gcd(u_k-u_k',n) non trivial. On ne teste pas toutes les paires k,k', mais seulement k'=2k, en effet la suite est ultimement périodique (d'où le nom rho de la méthode). Il faut de l'ordre de O(sqrt(N)) termes pour trouver le facteur N.
Remarque on ne prend pas f(x)=a*x+b mod n car mod N cette suite a une probabilite assez grande d'avoir une periodicite quasi-maximale N-1 (donc pas du tout en O(sqrt(N)): c'est le cas si a engendre (Z/NZ)*.
Ce type de méthode de factorisation a une complexité qui dépend de la taille du plus petit facteur de x, comme la division. Il diffère des méthodes comme le crible quadratique dont la complexité dépend de x. On utilise en général d'abord des méthodes comme Pollard-rho pour détecter les "petits" facteurs d'un entier x (de taille jusqu'à 10^18 environ pour Pollard-rho)

Representation des objets mathematiques sur machine:
* variable libre/affectee/hypothese
* expression symbolique, evaluation. Niveau d'évaluation (nombre de remplacements récursifs d'un nom de variable par une expression qu'on évalue). Par défaut 25 en mode interactif dans Xcas, 1 en programme. Empêcher l'évaluation, quote. Quote implicite dans certaines instructions comme := pour le membre de gauche, et le membre de droite dans une définition de fonction/programme.
Différence expression/fonction, passage d'une expression à une fonction par unapply. subst pour substituer dans une expression.
* liste/vecteurs, liste de listes de meme taille=matrice
Affectation := remplacement de la liste en temps O(taille de la liste), =< affectation en place en temps O(1).
* autres types : sequences (pas de profondeur), tables, attention aux tables vs listes,

Corps fini: Z/pZ et GF(p,n) de cardinal p^n represente par K=Z/pZ[X]/A(X) ou A irreductible de degre n. Si X mod A engendre le groupe cyclique K* on dit que A est primitif.

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

Re: option C 2015/16

Message par parisse » jeu. nov. 26, 2015 6:06 pm

25/11: TP
Construction d'un corps fini avec l'instruction GF(p,n), puis quelques calculs, par exemple creer une matrice a coefficients dans le corps, un element aleatoire du corps, un polynome a coefficient dans le corps. Factoriser un polynome a coefficients dans Z/pZ sur le corps. Discussion sur le degre d'un irreductible dans Z/pZ et le fait qu'il soit scinde dans GF(p,n). Comment on passe d'une racine aux autres avec Frobenius.

Flottants et arithmetique d'intervalle: calcul de exp(pi*sqrt(163)) et certifier que ce n'est pas un entier.
Exemple d'erreur d'arrondi avec le polynome de Rump.
La puissance rapide n'est rapide que parce qu'on reduit modulo, illustration avec le temps de calcul de normal((x+y+z+1)^64) et a:=normal((x+y+z+1)^32) puis normal(a*a) et debut d'explication avec le nombre de monomes de a.

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

Re: option C 2015/16

Message par parisse » mer. déc. 02, 2015 7:11 pm

2/12:
Construction d'un corps fini.
-> démonstration de la formule X^(p^n)-X=produit des irreductibles de degré divisant n modulo p.
Dans un sens, on utilise que si A est irréductible de degré k, alors Z/pZ[X]/A est un corps ayant p^k éléments donc alpha^p^k=alpha pour tout alpha dans le corps, d'où on déduit que X^p^k-X est divisible par A, et X^p^k=X mod A entraint X^p^n=X mod A en réitérant "prendre à la puissance p^k" n/k fois.
Dans l'autre sens on fait le quotient euclidien de n par k, si n=k*q+r
alors X=X^(p^(k*q+r))=X^(p^r) mod A et cela entraine que r=0 sinon il y a trop de racines pour X^(p^r)=X dans le corps Z/pZ[X]/A
-> on en déduit une majoration du nombre de polynôme irréductibles de degré n, puis une minoration, en raisonnant sur les degrés. Pour p pas trop petit, on a environ une chance sur n de tomber sur un irréductible en prenant un unitaire de degré n à coefficients aléatoires.
-> Déf. de polynôme irréductible primitif: X doit engendrer le groupe cyclique K*. Pour en construire un, on part d'un élément cyclique d'un corps fini et on calcule son polynôme minimal.
Il y a euler_phi(card(K*)) éléments cycliques dans K*, si card(K*)=p^n-1=produit des p_i^r_i, la proba de tomber sur un cyclique est produit(1-1/p_i)
-> Représentation multiplicative (on prend l'exposant entier d'un générateur fixé, et -1 ou p^n-1 pour 0 de K), adaptée à * et inverse rapides, mais il faut une table pour repasser en représentation additive pour faire + et -. Exemple petits corps fini, en particulier de caractéristique 2 où + et - sont un ou exclusif sur des entiers (représentant des polynômes, en écrivant l'entier en base 2, les bits sont les coefficients du polynôme), et la construction de table est très rapide, pour avoir le représentant additif de X^(j+1)=X^j*X on décale d'un cran le réprésentant additif de X^j, on regarde s'il a un terme de degré X^n si oui on fait le ou exclusif avec l'entier représentant le polynôme irréductible primitif en base 2.

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

Re: option C 2015/16

Message par parisse » jeu. déc. 10, 2015 12:38 pm

9/12: TP sur les GF
-> Trouver un polynome irreductible P de degre 5 sur Z/7Z. En deduire une representation de GF(7,5). Factoriser le polynome P sur votre representation de GF(7,5) (on pourra utiliser l'application x -> x^7).
-> Determiner le polynome minimal de quelques elements de GF(7,5) en utilisant votre representation ou celle de Xcas. Meme question mais en degre 4 avec la repr\'esentation de Xcas.
-> Factoriser avec Xcas x^16-x modulo 2 (on pourra utiliser factors(), % 2 et % 0). En deduire les polynomes irreductibles de degre 4 sur Z/2Z, determinez les polynomes irreductibles primitif de degre 4, pour l'un d'entre eux construire une table entre representation multiplicative et additive de GF(2,4).
-> Ecrire une fonction permettant de determiner si un polynome A est irreductible modulo p, en utilisant le PGCD avec les x^{p^k}-x modulo p,A. Quelle est sa complexite si A est irreductible de degre d ?

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

Re: option C 2015/16

Message par parisse » jeu. déc. 17, 2015 1:44 pm

16/12:
Polynome sur Z[X]: déf. de contenu (pgcd des coeffs entiers), partie primitive (une fois divisé par le contenu)
Proposition: Le produit de 2 polynômes primitifs est primitif.
Le contenu du produit est le produit des contenus.
Si A et B sont primitifs et B divise A dans Q[X] alors il divise A dans Z[X].
Définition du pgcd de 2 polynomes primitifs dans Z[X], on prend un pgcd dans Q[X], on multiplie par le ppcm des dénominateurs, on prend la partie primitive, on change de signe si le coeff dominant est négatif. Unicité car si A et B sont primitifs et multiples dans Q[X], alors le coeff multiplicateur est un entier inversible donc est 1 ou -1.

Proposition: si p est un premier ne divisant pas le pgcd des coeff dominants de A et B, le degré du pgcd dans Z/pZ[X] est >= à celui dans Z[X]. En particulier si le degré dans Z/pZ[X] est nul, les polynômes sont premiers entre eux dans Z[X].
Idee de l'algorithme de PGCD modulaire:
Si le degre du pgcd modulo p est nul, on conclut. Sinon, il faut reconstruire un multiple entier connu du pgcd, on prend le multiple de lcoeff g=le pgcd des coefficients de A et B. On normalise le pgcd mod p pour avoir lcoeff=g. Si p est assez grand et de bonne réduction, alors le pgcd dans Z est le reconstruit symétrique du pgcd modulo p. Pour tester on vérifie que le reconstruit symétrique divise A et B dans Z[X]

Estimation sur les racines complexes d'un polynome P a coefficients complexes:
|z| < 1+max(abs(coeffs de P))/abs(lcoeff(P))
On en déduit une majoration des coefficients du PGCD de A et B en développant son écriture factorisée et en utilisant que les racines du PGCD sont racines communes de A et B.

Complexité de l'algorithme modulaire en O(deg(A)^3) dans le cas le pire (grand degré de PGCD), la plupart du temps c'est en O(deg(A)^2) (si degré du pgcd est nul ou petit).

Définition du résultant par l'identité de Bézout:
C'est le déterminant du système
A*U+B*V=C
où A, B, C donnés, U et V inconnus (coefficients dans un anneau intègre unitaire commutatif inclus dans un corps, par exemple Z dans Q ou Z[Y,Z,T...] dans le corps des fractions en Y,Z,T...), degré(U)<degré(B) et degré(V)<degré(A) et degré(C)<degré(A)+degré(B).
Prop: resultant(A,B)=0 si et seulement si A et B ne sont pas premiers entre eux.
Exemple: discriminant(A)=resultant(A,A')/lcoeff(A)
exemple de discriminant en degre 2.
Observation: si A et B sont premiers entre eux et si les coefficients de C sont multiples du résultant alors U et V ont leurs coefficients dans l'anneau.

Preuve: par les formules de Cramer.

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

Re: option C 2015/16

Message par parisse » mar. janv. 12, 2016 2:21 pm

12/1:
Rappel resultants
Si A(x,y)=0 et B(x,y)=0 alors resultant(A,B,x) est un polynome en y qui s'annule. On peut ensuite trouver x en calculant les racines en x du polynome pgcd(A(x,y_k),B(x,y_k)) pour y_k racines du resultant.

Exemples d'application : calcul des points d'intersection d'un cercle et d'une ellipse.

Code : Tout sélectionner

c:=circle(0,2); E:=implicitplot(b); M:=point(x0,y0)
a:=x^2+y^2-4; b:=4x^2+3x*y+y^2-8
r:=resultant(a,b,x)
s:=solve(r,y)
[x0]:=solve(gcd(a(y=s[0]),b(y=s[0])),x); y0:=s[0]
Calcul de l'equation cartesienne d'une courbe parametrique rationnelle

Code : Tout sélectionner

xt:=(t^3-2t^2+4)/(t^2+1); yt:=(8t^2+3t-1)/(t^3+2)
plotparam([xt,yt],t=-5..5)
eq:=resultant(x*denom(xt)-numer(xt),y*denom(yt)-numer(yt),t)
plotimplicit(eq)
resultant(x*denom(x(t))-numer(x(t)),y*denom(y(t))-numer(y(t)),t)
Reciproquement on ne sait pas faire sauf pour les coniques.
Equation a*x^2+b*x*y+c*y^2+d*x+e*y+f=0, a,b,c non tous nuls.
On suppose connu un point de la conique (pour une conique non vide). On translate le repere en ce point ce qui revient a prendre f=0.
On cherche alors la 2eme intersection de la conique avec la droite y=t*x : l'equation est de degre 2 en x, mais on connait une solution x=0, l'autre solution s'obtient avec le 2eme facteur qui donne x en fonction de t puis y=t*x.
L'etude des branches asymptotiques comme courbe parametrique de x,y redonne les differents cas pour une conique (etude des racines du denominateur a+b*t+c*t^2 en fonction de a,b,c et des asymptotes eventuelles en ces racines: si delta=b^2-4ac<0 pas de branches donc ellipse, si racine double une branche parabolique de direction y=racine*x, sinon 2 asymptotes de pente les 2 racines).

Proposition: si A et B sont de degré total a et b, partiel par rapport à X n et m alors le degré total du résultant par rapport à X de A et B est <= a*b, en fait il est <= a*b-(a-n)*(b-m), il y a égalité si les polynômes sont homogènes (si le résultant est non nul).
Preuve par développement du déterminant avec les permutations.

Conséquence: théorème de Bézout sur le nombre d'intersection de 2 courbes algébriques sans composante commune, ce nombre est inférieur au produit des 2 degrés des polynomes équations des 2 courbes.
Preuve en 2 étapes: on commence à montrer que le nombre est fini, puis on change de repère par rotation pour que 2 racines distinctes n'aient jamais la même projection sur Ox, et on applique la proposition sur le degré du résultant.

Exemples: intersection de x*y=4 ou (x-2)^2+y^2=4 et de y^2=(x-3)*(x^2-16), qui met en évidence comment on peut perdre des points d'intersection par rapport au produit des degrés des 2 courbes:
* points à coordonnées complexes et les points d'intersection ayant une multiplicité (se traduit par une tangence des courbes au point d'intersection), cas du cercle inter la cubique
* point à l'infini: (0,1,0) pour l'hyperbole inter la cubique:
Si on fait le résultant en x ou en y en coordonnées "normales", on a un résultant de degré 5 et non 6. En coordonnées homogènes, le résultant est de degré 5 en y et 6 en x (correspond à a*b-(a-n)*(b-m) pour a=2, b=3 et n=1,m=2 ou n=1 et m=3), avec un coefficient en y^6 nul pour le résultant en x de x*y-4t^2 et de y^2*t-(x-3t)*(x^2-16t^2), donc t=0 est racine du résultant. Le point à l'infini se trouve en posant t=0 donc x*y-4t^2=0 devient x*y=0 et y^2*t-(x-3t)*(x^2-16t^2) devient x^3=0 d'où x=0, d'où (0,y,0)=y(0,1,0) est dans l'intersection.

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

Re: option C 2015/16

Message par parisse » mar. janv. 19, 2016 2:55 pm

19/1:
texte sur la moyenne arithmetico-geometrique
Sur la moyenne arithmético-géométrique, on peut montrer que les suites sont adjacentes, montrer une estimation a priori sur |a_n-b_n|<=constante^(2^n-1)*|a_0-b_0|^(2^n), et en deduire la complexite du calcul de la moyenne arithmetico-geometrique avec k digits. On peut comparer la complexite avec celle qui serait issue d'une quadrature usuelle (avec romberg ou gaussquad dans Xcas).
Sur les parametrisations, on peut montrer que toute conique admet un parametrage rationnel en utilisant une droite passant par un point de la conique de pente m et l'autre point d'intersection, l'illustrer (avec un parametre symbolique: menu Edit->ajouter parametres, les instructions conique ou plotimplicit, point, droite(,pente=) et inter()). On peut expliquer comment on peut calculer les integrales de racines carrees de fraction rationnelles en x et en un polynome du second degre en x (sans utiliser des sin/cos, sinh/cosh mais en se ramenant directement a des fractions rationnelles).
On peut effectuer comme suggere par le texte certains des calculs algebriques avec Xcas (selectionner a la souris des morceaux d'expression et appliquer une fonction de reecriture), par contre il n'est pas conseille de les faire au tableau, c'est ennuyeux, les risques d'erreurs sont importants, sauf pour des calculs tres simples (essentiellement calcul mental), par exemple pour montrer que les suites sont adjacentes et l'estimation de l'erreur.
Exemples d'illustrations informatiques: http://www-fourier.ujf-grenoble.fr/~par ... _agreg.xws
On peut enfin exposer le paragraphe qui explique pourquoi une cubique ne peut pas se parametrer rationnellement.
La documentation de Xcas contient un paragraphe sur l'utilisation de la moyenne arithmético-géométrique pour calculer les fonctions transcendantes élémentaires en multi-précision.

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

Re: option C 2015/16

Message par parisse » lun. févr. 08, 2016 9:16 am

26/1: exercices sur les resultants (section 6.3 du manuel algorithmes de Xcas)

2/2: texte du jury sur la molecule http://agreg.org/Textes/pub2008-C2.pdf
Illustrations possibles http://www-fourier.ujf-grenoble.fr/~par ... hexane.xws
Attention, le nombre de solutions pour le cyclohexane est infini, contrairement a ce que pourrait laisser penser l'etude du systeme P(u,v)=0, P(v,w)=0, P(u,w)=0 avec le resultant...

Localisation des racines d'un polynôme:
Suites de Sturm pour P polynome à coeff réels sans racines multiples on pose
R_0=P, R_1=P', R_{n+2}=-rem(R_n,R_ {n+1}), ..., R_N=dernier reste non nul (constant)
Alors le nombre de racines de P sur ]a,b] est la différence entre s(P,a) et s(P,b) où s(P,x) est le nombre de changements de signe de R_n(x) en ignorant les 0.

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).

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

Re: option C 2015/16

Message par parisse » mar. févr. 09, 2016 4:34 pm

9/2: algorithme de Yun pour obtenir la factorisation squarefree d'un polynome, etape prealable a nombre d'algorithmes de factorisation.
Complements sur la localisation de racines: calcul plus efficace en O(degree) operations de la suite de Sturm evalues en un point (au lieu de O(degree^2) en utilisant la suite des quotients. Attention toutefois, les coefficients des restes sont dans Q (ou dans Z avec de tres grands entiers) donc une operation elementaire n'est pas en O(1).
Localisation dans C: on peut localiser re/im des solutions en utilisant le resultant de re/im P(x+i*y) mais c'est tres couteux. On peut aussi construire des suites de Sturm complexes pour compter le nombre de racines dans un rectangle, mais ces suites changent quand on change de rectangle contrairement aux suites reelles. Le mieux reste donc une approximation numerique, puis un calcul exact avec des rationnels complexes du rayon de la boule degree(P)*abs(P(z)/P'(z)).
Regle des signes de Descartes: #racines de P dans R^+* est inferieur ou egal a #changements de signe des coefficients de P par ordre decroissant (on peut meme montrer que la parite de ces 2 entiers est egale).

TP: exercices 1, 5, 6, ... de la section des exercices de factorisation du manuel algorithmes de Xcas (section 16.9).

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

Re: option C 2015/16

Message par parisse » mer. mars 02, 2016 1:23 pm

16/2: exercices factorisation suite

1/3: texte public 2016 sur les design. Ca n'est pas forcement evident de trouver des idees d'illustrations informatiques sur ce texte, voici quelques idees:
1/ construire un 7,3,1 design en partant de la matrice H de taille 4 donnee page 4 et de la suggestion

Code : Tout sélectionner

H4:=[[1,1,1,1],[1,-1,1,-1],[1,1,-1,-1],[1,-1,-1,1]];
H8:=blockmatrix(2,2,[H4,H4,H4,-H4]);
J:=matrix(8,8,1);
tmp:=(J+H8)/2;
tmp[1..7,1..7];
2/ programmer un test comme dans la proposition 1 mais avec renvoi de faux des que possible (donc sans calculer A*A, plutot en faisant les produits scalaires colonne par colonne), le tester avec H4 et avec une autre matrice
3/ enumerer les elements de GL(F_2^3)

S'attendre a une question de majorer grossierement le cout d'un algorithme naif de recherche exhaustive, par exemple sur la matrice d'adjacence, et sur la possibilite de realiser reellement le test sur machine, ou en parler soi-meme pour montrer l'interet des methodes proposees.

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

Re: option C 2015/16

Message par parisse » mar. mars 08, 2016 2:31 pm

8/3: Interpolation polynomiale: calcul par les differences divisees dans la base de Newton en O(n^2), evaluation en O(n). Exemple d'application: calcul du polynome caracteristique d'une matrice nxn sur un corps fini de cardinal >n.

Algebre lineaire sur un corps:
Algorithme du pivot de Gauss pour réduire une matrice de taille L,C.
On initialise l et c à 1.
Tant que l<=L et c<=C faire
- si tous les coefficients sont nuls dans la colonne c à partir de la ligne l, incrémenter c et passer à l'itération suivante
- sinon on échange le cas échéant la ligne avec la ligne l pour avoir un pivot non nul en ligne l, on crée des 0 soit en-dessous de la ligne l (réduction sous-diagonale) soit sur toutes les lignes sauf la ligne l (réduction complète) par des manipulations de type L_k <- L_k - m_{k,c}/m_{l,c} L_l, incrémenter l et c et passer à l'itération suivante.

Décomposition PA=LU pour une matrice à coefficients dans un corps fini. L est triangulaire inférieure avec des 1 sur la diagonale, et les coefficients de la manipulation créant le 0: L_i <- L_i - l_{i,j} L_j si on réduit avec la ligne c (en général la colonne c), P matrice de permutation correspond aux inversions pour mettre le coeff non nul de la colonne c en ligne l.

Applications de LU: résolution de système, déterminant.

Variante de Gauss-Bareiss pour rester à coefficients dans l'anneau: on remplace la manipulation L_k <- L_k - m_{k,c}/m_{l,c} L_l par L_k <- (m_{l,c} *L_k - m_{k,c}*L_l)/pivot_utilisé_pour_réduire_la_colonne_précédente.
Nombre d'opérations O(n^3) dans le corps. Pour Gauss-Bareiss, cela donne un O(n^5*ln(n)^2) avec multiplication naive des entiers (si la matrice est bornée en norme infinie par une constante M). Moins bon que des méthodes modulaires pour calculer le déterminant, mais plus général.

Répondre