Le forum de XCAS

Xcas: un logiciel libre de calcul formel
Nous sommes actuellement le Sam Sep 23, 2017 9:21 am

Heures au format UTC




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

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:  
Powered by phpBB® Forum Software © phpBB Group
Traduction réalisée par Maël Soucaze © 2009 phpBB.fr