La recherche a retourné 24 résultats
Aller sur la recherche avancée
- mer. avr. 08, 2020 9:20 am
- Forum : UGA - option C 2020
- Sujet : exercice de complexité: division euclidienne rapide
- Réponses : 14
- Vues : 4805
Re: exercice de complexité: division euclidienne rapide
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...
- mer. avr. 08, 2020 9:06 am
- Forum : UGA - option C 2020
- Sujet : exercice de complexité: division euclidienne rapide
- Réponses : 14
- Vues : 4805
Re: exercice de complexité: division euclidienne rapide
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...
- mer. avr. 08, 2020 8:56 am
- Forum : UGA - option C 2020
- Sujet : exercice de complexité: division euclidienne rapide
- Réponses : 14
- Vues : 4805
Re: exercice de complexité: division euclidienne rapide
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 ...
- mer. avr. 08, 2020 8:26 am
- Forum : UGA - option C 2020
- Sujet : exercice de complexité: division euclidienne rapide
- Réponses : 14
- Vues : 4805
Re: exercice de complexité: division euclidienne rapide
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...
- mer. avr. 01, 2020 8:32 am
- Forum : UGA - option C 2020
- Sujet : 1/4
- Réponses : 32
- Vues : 10565
Re: 1/4
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...
- mer. mars 25, 2020 11:03 am
- Forum : UGA - option C 2020
- Sujet : 25/3
- Réponses : 33
- Vues : 10096
Re: 25/3
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
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
- mer. mars 25, 2020 10:54 am
- Forum : UGA - option C 2020
- Sujet : 25/3
- Réponses : 33
- Vues : 10096
Re: 25/3
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
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
- mer. mars 25, 2020 10:46 am
- Forum : UGA - option C 2020
- Sujet : 25/3
- Réponses : 33
- Vues : 10096
Re: 25/3
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...
- mer. mars 25, 2020 10:40 am
- Forum : UGA - option C 2020
- Sujet : 25/3
- Réponses : 33
- Vues : 10096
Re: 25/3
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...
- mer. mars 25, 2020 10:32 am
- Forum : UGA - option C 2020
- Sujet : 25/3
- Réponses : 33
- Vues : 10096
Re: 25/3
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...
- mer. mars 25, 2020 10:26 am
- Forum : UGA - option C 2020
- Sujet : 25/3
- Réponses : 33
- Vues : 10096
Re: 25/3
- 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...
- mer. mars 25, 2020 10:18 am
- Forum : UGA - option C 2020
- Sujet : 25/3
- Réponses : 33
- Vues : 10096
Re: 25/3
-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 ...
- mer. mars 25, 2020 10:12 am
- Forum : UGA - option C 2020
- Sujet : 25/3
- Réponses : 33
- Vues : 10096
Re: 25/3
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...
- mer. mars 25, 2020 10:02 am
- Forum : UGA - option C 2020
- Sujet : 25/3
- Réponses : 33
- Vues : 10096
Re: 25/3
-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...
- mer. mars 25, 2020 9:46 am
- Forum : UGA - option C 2020
- Sujet : 25/3
- Réponses : 33
- Vues : 10096
Re: 25/3
-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...