Le forum de XCAS

Xcas: un logiciel libre de calcul formel
Nous sommes actuellement le Mer Nov 22, 2017 8:22 pm

Heures au format UTC




Publier un nouveau sujet Répondre au sujet  [ 5 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: 4106
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: 4106
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: 4106
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: 4106
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: 4106
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  
 
Afficher les messages publiés depuis:  Trier par  
Publier un nouveau sujet Répondre au sujet  [ 5 messages ] 

Heures au format UTC


Qui est en ligne ?

Utilisateurs parcourant actuellement ce forum : Bing [Bot] 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:  
Powered by phpBB® Forum Software © phpBB Group
Traduction réalisée par Maël Soucaze © 2009 phpBB.fr