Le forum de XCAS

Xcas: un logiciel libre de calcul formel
Nous sommes actuellement le Mar Fév 20, 2018 3:31 am

Heures au format UTC




Publier un nouveau sujet Répondre au sujet  [ 9 messages ] 
Auteur Message
 Sujet du message: option C 2017/18
MessagePublié: Jeu Sep 14, 2017 6:59 am 
Hors-ligne

Inscrit le: Mar Déc 20, 2005 4:02 pm
Messages: 4246
13/9:
Rapide presentation de l'option:
* page 10 du programme (http://media.devenirenseignant.gouv.fr/file/agregation_externe/59/3/p2018_agreg_ext_math_759593.pdf),
* page agreg de Xcas (https://www-fourier.ujf-grenoble.fr/~parisse/agreg.html) : tronc commun ("chapitre 13") et option C, doc en ligne (Aide>Manuel>Algorithmes dans Xcas)
* presence de "Cout des algorithmes" pour chaque point au programme (EEE, E comme exact, E comme effectif, E comme efficace).
Epreuve: choix entre 2 textes, mots-clefs, 4h preparation, 35 mn expose+25 minutes de questions (complexite si le candidat n'en a pas parle), epreuve de maths (donc enonces avec hypotheses/etc.), on peut admettre un resultat (a condition de le dire clairement). Plan en debut d'expose, avec indication des illustrations informatiques. En premiere partie de prepartion, commencer par faire une illustration informatique en ligne de commande (juste avec les commandes du logiciel). On peut faire des programmes ensuite, mais il ne faut pas passer plus de 5 minutes a debugguer un programme qui ne marche pas et il faut le montrer quand meme au jury, qui sait bien que le format de l'epreuve et le stress ne permettent pas de mettre au point un programme sereinement.

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+1)*a, et |v_n| strictement croissante (a partir du rang 2 pour strict), 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) (on admet pour l'instant qu'il y a au plus O(taille(max))) etapes).
A retenir: +,- en O(n), * (naif),/,pgcd,Bezout en O(n^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.


Haut
 Profil  
 
 Sujet du message: Re: option C 2017/18
MessagePublié: Ven Sep 29, 2017 5:22 pm 
Hors-ligne

Inscrit le: Mar Déc 20, 2005 4:02 pm
Messages: 4246
27/9:
Algorithme de multiplication de 2 polynômes
Par Karatsuba, existence d'un seuil en-deca duquel il vaut mieux faire la multiplication naive.

Par FFT, a coeff approches sur C (ou exact sur Z/pZ avec p tel qu'il existe une racine n-ieme primitive de 1).
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 et en divisant par n). 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).

Retour a l'arithmetique des entiers:
Nombre d'etapes d'Euclide avec restes symetriques. Avec reste positif, en comparant avec une suite de Fibonacci.

Applications de Bezout:
-> inverse modulaire inv(a mod n) s'obtient par Bezout a*u+v*n=1
Pour l'inverse modulaire on n'a pas besoin de calculer v.
-> restes chinois on cherche c=alpha mod a et =beta mod b, avec a et b premiers entre eux
donc alpha+a*U=beta+b*V et a*U-b*V=beta-alpha
donc on part de a*u+b*v=1, on pose U=(beta-alpha)*u et c=alpha+U*a
Dans les applications en calcul modulaire, a est souvent un grand entier, produit de n nombres premiers et b un entier court nombre premier. On a alors interet a faire les calculs intermediaires de U modulo b (comme ensuite on multiplie U par a, cela ne change pas le fait que c est solution).
U=irem((beta-irem(alpha,b))*u,b)
Ainsi le calcul de U est en O(n), et le calcul de c en O(n).
On peut par exemple calculer 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, le calcul de a^n mod p se fait en log2(n) etapes necessitant chacune 1 ou 2 multiplications et 1 division d'entiers. Algorithme iteratif.


Haut
 Profil  
 
 Sujet du message: Re: option C 2017/18
MessagePublié: Mar Oct 24, 2017 4:25 pm 
Hors-ligne

Inscrit le: Mar Déc 20, 2005 4:02 pm
Messages: 4246
4/10: TP suite https://www-fourier.ujf-grenoble.fr/~parisse/agreg/agregtp1_.pdf

11/10:
-> Applications de la puissance modulaire rapide
1/ Test de Fermat.
2/ Test de Miller-Rabin. Complexité en O(ln(p)^3) si on multiplie les entiers naivement.
Thm admis: si p n'est pas premier, le cardinal de l'ensemble des a<p tels que Miller-Rabin reussit est <=p/4
Si on prend a au hasard, on a donc 1 malchance sur 4 au plus de reussir le test alors que p n'est pas premier. Si on prend une vingtaine de a "independants", si tous les tests passent, on a au plus 1 malchance sur 4^20 que p ne soit pas premier. En pratique on prend des a premiers.
3/ Racine carre modulo p, cas ou p=3[4] a^(p+1)/4 mod p
4/ RSA

-> Types polynomiaux
Polynomes à 1 variable: représentation dense par la liste des coefficients ou creuse. Complexite de +, -, *,/ en representation dense: comme les entiers en remplacant taille par degre.
Polynomes en d variables: representation recursive ou distribuee. En general on utilise des representations creuses car le nombre de monomes possibles est vite tres grand: en d variables et degre total n c'est comb(n+d,d) : choisir de noircir d cases noires parmi n+d blanches revient en effet a associer les degres partiels d'un monome a des zones de cases blanches contigues. En degres partiels faire le produit des degres partiels+1.
Exemple d'ordre sur les monomes: lexicographique, degre total puis lexicographique, compatible avec la *
Temps de calcul d'une somme ou difference de polynomes creux en d variables: O(somme des tailles), il faut faire une sorte de tri fusion en additionnant ou soustrayant lorsque les monomes sont identiques.
Pour un produit, c'est plus delicat, on peut montrer que c'est en O(produit des tailles* ln(taille produit)) en utilisant une structure de donnees appelee tas (heap) [hors programme]

18/10: TP https://www-fourier.ujf-grenoble.fr/~parisse/agreg/agregtp2.pdf


Haut
 Profil  
 
 Sujet du message: Re: option C 2017/18
MessagePublié: Jeu Oct 26, 2017 11:41 am 
Hors-ligne

Inscrit le: Mar Déc 20, 2005 4:02 pm
Messages: 4246
25/10:
Arithmetique des polynomes 1-d dense: +/- O(n), * naif O(n^2), division, pgcd, Bezout (comme pour les entiers en remplacant nombre de chiffres par degre)
Evaluation: methode de Horner. Changement d'origine avec Horner repete (cf. ex 17).

"Bestiaire" d'objets mathematiques et representation en machine
* rationnel,
* flottant multi-precision et arithmetique d'intervalle
* complexe,
* 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, utilisation pour representer 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) mais a utiliser avec precaution
* autres types de listes : sequences (pas de profondeur), ensembles set[], polynome 1-d dense poly1[...]
* extension algebrique de Q (rootof) couple de polynomes A/B, vaut A(alpha) avec B(alpha)=0, B irreductible sur Q.


Haut
 Profil  
 
 Sujet du message: Re: option C 2017/18
MessagePublié: Mar Nov 14, 2017 1:17 pm 
Hors-ligne

Inscrit le: Mar Déc 20, 2005 4:02 pm
Messages: 4246
7/11: oraux prepares en temps libre sur les 2 textes RSA du jury.

14/11:
Construction d'un corps fini non premier.
-> 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 en regardant les degres une majoration du nombre de polynôme irréductibles de degré n par p^n/n, puis une minoration par 1/n*(p^n-somme pour k diviseur strict de n de p^k). Pour p/n 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)
-> On peut preferer un polynome irreductible non primitif creux, ayant ses coefficients non nuls dans les bas degres, ceci afin d'accelerer la division euclidienne par A, en particulier si on multiplie des elements du corps dont la representation est creuse.
-> 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.


Haut
 Profil  
 
 Sujet du message: Re: option C 2017/18
MessagePublié: Mer Jan 10, 2018 10:13 am 
Hors-ligne

Inscrit le: Mar Déc 20, 2005 4:02 pm
Messages: 4246
fin 2017
seance TP 21/11 exercices sur les corps finis (section 16.3 du manuel Algorithmes).

28/11 1er cours sur le resultant: Définition 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.

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

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.

5/12 TP resultant: section 8.4 du manuel algorithmes de Xcas
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.

semaine du 18/12: oraux blancs sur les textes http://agreg.org/Textes/public2013-C1.pdf (compression de fichiers par moyennes/details) et http://agreg.org/Textes/pub2008-C2.pdf (geometrie d'une molecule)


Haut
 Profil  
 
 Sujet du message: Re: option C 2017/18
MessagePublié: Jeu Jan 18, 2018 3:30 pm 
Hors-ligne

Inscrit le: Mar Déc 20, 2005 4:02 pm
Messages: 4246
17/1: resultant et intersection de courbes algebriques:
Exemple de l'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.

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

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 l'intervalle 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.
Exemple et preuve.


Haut
 Profil  
 
 Sujet du message: Re: option C 2017/18
MessagePublié: Mar Fév 13, 2018 10:23 am 
Hors-ligne

Inscrit le: Mar Déc 20, 2005 4:02 pm
Messages: 4246
24/1: TP section 18.9 du manuel de Xcas

31/1: pour evaluer les restes de la suite de Sturm, il vaut mieux evaluer la suite des quotients (O(n) operations au lieu de O(n^2)). Sturm travaille dans Q, le nombre d'perations arithmetiques n'est pas tres representatif du cout reel. On peut se ramener dans Z par pseudo-division euclidienne.
Algorithme d'Euclide avec pseudo-division, probleme de la taille des coefficients, on peut simplifier par le contenu du pseudo-reste a chaque etape, mais cela reste couteux, on prefere utiliser un gros diviseur du contenu calcule a priori, c'est l'algorithme dit du sous-resultant (donne mais non justifie car tres technique), en lien avec la formule donnant resultant(A,B) en fonction de resultant(B,rem(A,B)) et l'algorithme de Gauss-Bareiss pour calculer un determinant.
Majoration du module des racines d'un polynome par M=1+max(valeur absolue des coeffs)/abs(coeff dominant)
regle des signes de Descartes, application a l'isolation des racines positives d'un polynome P. Isolation des racines dans ]0,1[: P(x=1/x)*x^degree(P) permet de se ramener a ]1,inf[ puis P(x=x+1) a ]0,inf[
Changement de variables P(x=M*x) pour se ramener a ]0,1[. Si le critere donne 0 ou 1 racine, on a isole, sinon on decoupe ]0,1[ en deux en utilisant P(x=x/2) et P(x=(x+1)/2)
Algorithme de Yun pour ecrire un polynome P comme produit des P_i^i avec pgcd(P_i,P_i')=1 et pgcd(P_i,P_j)=1

7/2: suite du TP et application de la regle des signes sur un exemple de polynome pour trouver un intervalle d'isolation.


Haut
 Profil  
 
 Sujet du message: Re: option C 2017/18
MessagePublié: Jeu Fév 15, 2018 9:51 am 
Hors-ligne

Inscrit le: Mar Déc 20, 2005 4:02 pm
Messages: 4246
14/2:
Interpolation polynomiale. Differences divisees, calcul en O(n^2) operations, evaluation avec les differences divisees en O(n) operations. Commandes Xcas: si X et Y sont les listes des abscisses/ordonnees, lagrange(X,Y) -> polynome (ecrit dans la base de Newton), D:=lagrange(X,Y,lagrange) renvoie la liste des differences divisees, qu'on peut utiliser dans horner: horner(X,D,x) evalue en x le polynome d'interpolation.
Applications:
1/ polynome caracteristique en O(n^4) operations sur le corps
2/ resultant en 2 variables resultant(P(X,Y),Q(X,Y),Y) se calcule avec degre_total(P)*degre_total(Q)+1 valeurs de X en interpolant resultant(P(X=x_i,Y),Q(X=x_i,Y),Y), attention ces valeurs doivent conserver le degre en Y de P et Q (coeff dominant de P et Q evalue en X=x_i non nul). Attention, il faut que le corps ait suffisamment d'elements en caracteristique non nulle. Attention, les versions <= 1.4.9-47 de Xcas ne font pas ce test et renvoient un resultant faux pour de petites valeurs de caracteristique si le resultant est calcule par interpolation, ceci va etre corrige en version 1.4.9-49.
3/ Calcul de sommes discretes de polynome evalue en n

Algebre lineaire sur un corps: decomposition LU en O(n^3) operations, resolution de systeme avec LU en O(n^2) operations, exemple 3x3 sur Z/5Z. Application au calcul de determinant, inverse, calcul du rang.
Multiplication matrice, matrice en O(n^3) operations. Existence d'algorithmes asymptotiquement plus efficaces, par exemple Strassen en O(n^(ln(7)/ln(2))), multiplication par bloc (analogue a Karatsuba pour les polynomes). LU peut aussi se faire avec cette complexite. Devient plus rapide pour des n relativement grands (quelques centaines).
Algorithme de Gauss-Bareiss.


Haut
 Profil  
 
Afficher les messages publiés depuis:  Trier par  
Publier un nouveau sujet Répondre au sujet  [ 9 messages ] 

Heures au format UTC


Qui est en ligne ?

Utilisateurs parcourant actuellement ce forum : Aucun utilisateur inscrit et 2 invités


Vous ne pouvez pas publier de nouveaux sujets dans ce forum
Vous ne pouvez pas répondre aux sujets dans ce forum
Vous ne pouvez pas éditer vos messages dans ce forum
Vous ne pouvez pas supprimer vos messages dans ce forum
Vous ne pouvez pas insérer de pièces jointes dans ce forum

Rechercher pour:
Sauter vers:  
cron
Powered by phpBB® Forum Software © phpBB Group
Traduction réalisée par Maël Soucaze © 2009 phpBB.fr