option C 2018/9

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

Modérateur : xcasadmin

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

option C 2018/9

Message par parisse » jeu. sept. 20, 2018 12:03 pm

12/9:
Rapide presentation de l'option:
* page 10 du programme (http://media.devenirenseignant.gouv.fr/ ... 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) qu'on verra plus tard,
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 arithmetique nul (c'est juste un test)
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,
PGCD avec reste symetrique i.e. on remplace r=irem(a,b) par b-r si r>b/2. On gagne au moins un bit par etape, ce qui permet de montrer une complexite en O(n^2). Pour l'etude du PGCD usuel, il faut majorer le nombre d'etapes en O(n): on montre que si le PGCD de a et b se calcule en n etapes, alors a>=n-ieme nombre de la suite de Fibonacci de 1ers termes 1 et 2.
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)
A retenir: +,- en O(n), * (naif),/,pgcd,Bezout en O(n^2)
4/ 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.

19/9: TP https://www-fourier.ujf-grenoble.fr/~pa ... regtp1.pdf Prise en main et exercices 1 a/b/, 2

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

Re: option C 2018/9

Message par parisse » jeu. sept. 27, 2018 6:22 am

26/9:
Polynômes a coeffs dans un corps ou les operations arithmetiques sont en temps O(1): corps fini ou les complexes represente par des flottants.
Algorithme de multiplication 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).

Representation graphique des 3 complexites: naif, Karatsuba, FFT et existence de 2 seuils.

Division euclidienne de polynomes en O(deg(Q)*deg(B)). PGCD et Bezout en O(n^2). Memes raisonnements qu'avec les entiers, mais majorations plus simples avec les degres qu'avec les tailles d'entiers.

Evaluation en O(n) par Horner: voir exercice de TP

Applications
1/ 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).

2/ de la puissance modulaire rapide
-> petit theoreme de Fermat, test de non primalite en O(ln(p)^3)

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

Re: option C 2018/9

Message par parisse » mer. oct. 24, 2018 11:35 am

3/10: suite du TP1

10/10:
1/ 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.
2/ racine carree modulo p premier: cas facile si p=3[4], si p=1[4] il faut calculer pgcd((x+random)^(p-1)/2-1,x^2-a), la puissance de x+random se calcule elle-meme modulo x^2-a et modulo p
3/ RSA

4/ Types polynomiaux:
Polynomes à 1 variable: représentation dense par la liste des coefficients ou creuse. Complexite de +, -, *,/,Euclide 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]

17/10: TP https://www-fourier.ujf-grenoble.fr/~pa ... regtp2.pdf

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

Re: option C 2018/9

Message par parisse » mer. oct. 24, 2018 5:53 pm

24/10:
"Bestiaire" d'objets mathematiques et representation en machine
* flottant multi-precision et arithmetique d'intervalle
* 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[...]
* rationnel,
* complexe,
* extension algebrique de Q (rootof) couple de polynomes A/B, vaut A(alpha) avec B(alpha)=0, B irreductible sur Q.
* Z/nZ paire d'entiers

Corps finis non premiers de cardinal p^n
1/ construction d'un irreductible de degre n
X^(p^n)-X=produit des irreductibles de degré divisant n modulo p.
Le membre de gauche est sans facteur multiple car la derivee est -1.
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.
-> critere d'irreductibilite: pgcd(A,X^(p^k)-X)=1 pour k<= degre(A)/2
-> critere effectif pgcd(A,X^(p^k) mod A-X)=1 calcul fait avec la puissance rapide mod p et mod A. Complexite du critere en O(n^4*ln(p)^3))

8/11: texte du jury RSA public en 2018

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

Re: option C 2018/9

Message par parisse » mar. nov. 20, 2018 1:15 pm

15/11: TP corps finis. (section 16.3 du manuel Algorithmes).

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

Re: option C 2018/9

Message par parisse » jeu. nov. 29, 2018 9:50 am

28/11: 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 et 3.

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.

Exemple 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]
Plus generallement, resolution de systemes polynomiaux par elimination successive de variables.

Autre application du resultant:
Calcul de l'equation cartesienne d'une courbe parametrique rationnelle.
resultant(x*denom(x(t))-numer(x(t)),y*denom(y(t))-numer(y(t)),t)

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.

Ceci limite la possibilite d'utilisation du resultant en pratique a des systemes polynomiaux 2x2, 3x3, mais rarement plus.

Autre application du resultant: integration de fractions rationnelles N/D avec D sans racine multiple et N de degre<degre(D):
somme sur t racine de resultant(N-t*D',D) de t*log(gcd(N-t*D',D))

Formule donnant le resultant et le discriminant en fonction des racines des polynomes.

5/12 TP resultant: https://www-fourier.ujf-grenoble.fr/~pa ... result.pdf

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

Re: option C 2018/9

Message par parisse » lun. janv. 14, 2019 1:42 pm

2eme et 3eme semaine de decembre: oraux blancs sur les textes 2016c2 et 2017c2 (http://agreg.org/textes.html)

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

Re: option C 2018/9

Message par parisse » jeu. janv. 17, 2019 4:23 pm

16/1
Localisation des racines d'un polynome a coefficients reels ou complexes.
-> Prealable commode et parfois indispensable: remplacer P par P/gcd(P,P') pour avoir des racines de multiplicite 1.
-> majoration des racines par 1+max|coeff|/|coeff dominant|
-> racines complexes
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 (avec la commande exact ou en multipliant par une puissance de 2 ou 10, arrondi a l'entier le plus proche et division par cette puissance).

-> racines reelles d'un polynome a coefficients reels
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 de ]0,M[ 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)
Intervalle d'isolation: ne contenant qu'une racine et une seule.
Commande realroot

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.
Preuve. Nombre d'operations arithmetique sur Q en O(n^2) pour calculer la suite. Attention, ceci ne caracterise pas la complexite car les calculs sur Q ne se font pas en O(1).
Pour calculer s(P,a) on peut faire O(n) operations arithmetiques sur Q au lieu de n^2 en stockant R0, R1 et les quotients au lieu des restes.
Il existe une generalisation a C (nombre de racines dans un rectangle) mais couteuse. Commandes sturm, sturmab.
Utilisation du resultant pour se ramener a un systeme polynomial 2x2, P1(x,y)=re(P(x+i*y))=0 et P2(x,y)=0=im(P(x+i*y)) puis a une equation polynomiale en x et en y avec resultant(P1,P2), mais trop couteuse (degre total du resultant<=n^2 et de plus les coefficients sont grands!)

23/1: TP prevu sur section 18.9 du manuel de Xcas

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

Re: option C 2018/9

Message par parisse » jeu. févr. 07, 2019 9:28 am

30/1:
Interpolation polynomiale, construction par recurrence, base de Newton. 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

Algorithme permettant d'exprimer tout polynome symetrique polynomialement en fonction des polynomes symetriques elementaires.

6/2: partie interpolation du tp https://www-fourier.ujf-grenoble.fr/~pa ... gtplin.pdf

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

Re: option C 2018/9

Message par parisse » jeu. mars 07, 2019 9:42 am

13/2: Algebre lineaire sur un corps fini.
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).
Decomposition LU en O(n^3) operations, resolution de systeme avec LU en O(n^2) operations, exemple 3x3 sur Z/11Z. Application au calcul de determinant, inverse, calcul du rang.
Algorithme de Gauss-Bareiss (reduction de Gauss sans fraction sur un anneau comm. integre unitaire), cout en O(n^5*ln(n)^2) sur les entiers avec multiplication naive. Alternative: determinant multi-modulaire en O(n^4*ln(n)).

20/2: TP partie algebre lineaire de la feuille precedente.

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

Re: option C 2018/9

Message par parisse » jeu. mars 07, 2019 9:51 am

6/3: Code correcteurs. Cf. §16.5 du manuel Algorithmes de Xcas.
En complement, codes de Hamming binaires vus comme codes polynomiaux sur Z/2[X] de polynome generateur G un polynome irreductible primitif de degre m a coeffs dans Z/2 -> code de parametre n=2^m-1, k=n-m. On verifie qu'un tel code polynomial est de distance 3, car s'il etait de distance plus petite on aurait un multiple du polynome generateur de la forme x^a+x^b, qui s'annule sur alpha un generateur du corps a 2^m elements, impossible si a et b<n. Et qu'il est 1 correcteur parfait, si on a un polynome non divisible par G, on calcule le reste par G, en alpha cela donne un element inversible du corps a 2^m elements, donc une puissance de alpha dont l'exposant est l'indice de coefficient a changer dans le polynome.
Codes de Reed-Solomon: code polynomial sur K[X], de generateur G=(X-g)*...*(X-g^(2t)) ou g est un generateur de K*, preuve du fait que la distance du code est 2t+1.

13/3: TP : exercices du § 16.5

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

Re: option C 2018/9

Message par parisse » mer. avr. 03, 2019 7:48 am

27/3: quelques complements
Calcul du polynome caracteristique par Le Verrier/Fadeev/Souriau cout en O(n^4), permet de calculer les vecteurs propres correspondant a des valeurs propres simples.
Comment retrouver certains algorithmes pour les adapter dans la doc de Xcas: manuel Algorithmes HTML puis Index ou Table des matieres. Exemples: Leverrier et application a la diagonalisation d'une matrice a coeffs dans Z/nZ en creant une extension de corps pour factoriser le polynome caracteristique, decomposition de Dunford par la methode de Newton, generateurs congruentiels aleatoires lineaires.

3/4: TP/TD
exercices de revisions complexite:
1/ comparer le calcul de p^n pour p et n entiers par algorithme naif pxpx...xp ou methode comme puissance rapide (attention pas de modulo ici), en utilisant la multiplication naive ou une multiplication rapide
2/ cout du calcul du n-ieme nombre de Fibonacci. Par addition ou en utilisant les flottants multi-precision.
3/ cout du calcul d'un inverse dans GF(p,n), cout du calcul de l'inverse d'une matrice kxk dans GF(p,n)
4/ cout du pgcd de 2 polynomes de degre n dans GF(p,n) en fonction de n

Répondre