Le forum de XCAS

Oui c'est e que j'allais faire ensuite. Le mieux est de calculer par la dernière formule qui s'obtient en remplaçant c par sa valeur donnée par la première expression. On se retrouve avec une multiplication de trois polynômes qui donne une complexité t*log(t) + 2t*log(2t) qui équivaut à une complexi...

En multipliant la première égalité par 1-x^t*c on obtient exactement la deuxième égalité. On remarque dans cette deuxième égalité que l'on trouve l'inverse de b modulo x^2t donc on identifie b_t*(1-x^t*c) à b_2t par unicité de l'inverse modulo x^2t. Il apparait que l'on doit calculer c modulo x^t po...

Dans le calcul de b_t, le polynôme c est bien définit. En effet pour tout t, b est premier avec x^t donc b est inversible modulo x^t et on note b_t son inverse. On trouve donc : b*b_t = 1 modulo x^t ce qui revient à b*b_t = 1 + x^t*c où c est le polynôme définit dans la relation. Pour calculer c on ...

Ici on a pris b le polynôme symétrique de B. Donc b et B sont reliés par la relation b = B(1/x) * x^m. Or B est de degré m donc son coefficient de degré m est non nul. Quant on passe aux polynômes symétriques le coefficient de degré m de B devient le coefficient constant de b. Ainsi b ne s'annule pa...

1/ comparer le calcul de p^n pour p et n entiers par algorithme naif pxpx...xp ou une méthode comme pour la puissance rapide (attention pas de modulo ici), en utilisant la multiplication naive Algorithme naïf : px(px(...x(pxp))...) Coût(p*(p^k))=k*ln(p)^2. Ainsi : Coût(px...xp, k fois)=sum_{j=1}^k k...

Merci,

Est ce que vous auriez un commentaire générale sur mes notes et mes réponses aux questions ? (bien que cela soit quand même très éloigné d'une vrai épreuve )

Anthony

Pour revenir sur TM8
Oui en fait il s'agit d'une permutation des vecteurs de base. Il suffit de faire agir une matrice qui fait la transformation suivante sur la base :
(e_1, e_2, e_3, ..., e_n/2+1, e_n/2+2,..., e_n) --> (e_1, e_n/2+1, e2, e_n/2+2,..., e_n/2, e_n/2+n/2)


Anthony

BP5 Le sqrt(2) ferait passer les calculs en flottant ce que l'on préfère éviter pour des raisons de complexité de calcul et de stockage. Mais peut-être serait il possible de manipuler ce sqrt(2) de manière symbolique sans l'expliciter ce qui éviterait de manipuler des flottants. Dans ce cas on expri...

Pour finir sur BP4, il est vrai que prendre des decimaux peut augmenter le coût de stockage et de calcul mais les nombres restent des rationnels. Dans notre cas on voit par contre que même pour un vecteur petit la transformation d2_tot fait apparaitre un numérateur de taille log_2(n) ce qui peut êtr...

Ma question était plutot de comparer le cout des algorithmes. Sinon, pour la compression à base de FFT, on peut utiliser la meme technique que pour D2, on ramène à 0 tous les coefficients de la FFT qui sont de module plus petits qu'un epsilon donné, ce qui permet de stocker des paires numero de coe...

- BP 4 On part toujours d'une liste d'entiers en effet compris entre 0 et 255. C'est le programme d'inversion qui devrait faire le boulot de ramener à des entiers (ce que je n'ai pas fait dans mon programme par oubli). Il n'est pas important de travailler avec des rationnels car les rationnels stock...

-BP3 Je ne sais pas cexactement comment fonctionne les méthodes par transformation de Fourier donc il m'est difficile de fournir une réponse cohérente à cette question. Je pense que cela pourrait venir du fait que la méthode pas transformation de Fourier ne prend pas en compte le fait qu'on ait une ...

Comme il est 11h je vais passer aux questions de Bernard Parisse. - BP1 Je me suis trompé au début, j'ai changé la matrice Aortho sur le programme mais j'ai oublié de la changer sur mes notes. La bonne matrice est la matrice Aortho du programme. En effet elle fait bien la somme de deux coordonnées s...

-TM6 Je ne sais pas comment va réagir réellement une image à ce traitement pas je peux essayer de prendre un vecteur aléatoire et regarder succéssivement les erreurs relatives lors d'une compression puis décompression : Reprenons les vecteur t = [154,155,149,152,155,154,153,149,157,156,152,151,152,1...

-TM5 vect1=[123,122,124,124,128,129,134,137,140,142,145,147,153,155,156,155] approx(d2_tot(vect1)) = [138.375,-10.75,-4.375,-5.625,-0.75,-3.5,-2.5,-0.75,0.5,0.0,-0.5,-1.5,-1.0,-1.0,-1.0,0.5] l'énoncé nous donnait 138.375,−10.75,−4.375,−5.625,−0.75,−3.5,−2.5,−0.75,0.5,0,−0.5,−1.5,−1,−1,−1,0.5 On a bi...