restart:
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">Calcul de la TFD par une proc\303\251dure "na\303\257ve"</Font></Text-field>Cette proc\303\251dure calcule les coefficients de Fourier par une m\303\251thode dite "naive".TFDSimple:=proc(x)
local n,X:
n:=nops(x):
X:=[seq(sum(x[j]*exp(-2*I*(j-1)*(k-1)*Pi/n),j=1..n),k=1..n)];
end proc:
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">Calcul de la TFD par une proc\303\251dure r\303\251cursive</Font></Text-field>Cette proc\303\251dure prend en entr\303\251e une liste repr\303\251sentant les coefficients d'un polyn\303\264me dont on cherche \303\240 calculer les coefficients de Fourier.TFDRecur:=proc(x)
local N,CoefFFT,xp,xi,u,v,omega:
N:=nops(x):
if N=1 then CoefFFT:=x:
else
xp:=[seq(x[2*i],i=1..N/2)]:
xi:=[seq(x[2*i-1],i=1..N/2)]:
u:=TFDRecur(xp):
v:=TFDRecur(xi):
omega:=exp(-2*I*Pi/N):
CoefFFT:=[seq(omega^(k-1)*u[k]+v[k],k=1..N/2),seq(-omega^(k-1)*u[k]+v[k],k=1..N/2)];
end if:
CoefFFT;
end proc:
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">Calcul de la TFD par it\303\251ration</Font></Text-field>On va utiliser l'\303\251criture des divers coefficients en binaire.TFDIter:=proc(x)
local n,i,j,k,a,b,p,l,z,w,h,m,tmp:
n:=nops(x):
l:=Array(1..n):
l:=Array(x):
p:=n/2:#p: puissance de 2 dans d\303\251composition.
while p>=1 do
z:=1: #premi\303\250re valeur de omega.
w:=exp(-I*Pi/p): #c'est omega.
for h from 1 to p do #Variable servant \303\240 la d\303\251composition
for m from 1 to n/(2*p) do
#On va calculer le signal xm
a:=h+2*(m-1)*p: #Premi\303\250re valeur du signal x_(m-1)
b:=a+p: #Seconde valeur du signal x_(m-1)
tmp:=(l[a]-l[b])*z:
l[a]:=l[a]+l[b]: #x_m(a) = x_(m-1)(a)+x_(m-1)(b)
l[b]:=tmp: #x_m(b) = (x_(m-1)(a)-x_(m-1)(b))*z
end do:
#On passe au signal m+1 -> w<-w^(m+1)
z:=z*w:
end do:
p:=p/2:
end do:
#On a maintenant notre liste contenant les signaux x_r
#Il reste \303\240 remettre les signaux dans le bon ordre.
j:=1:
for i from 1 to n do
if j>i then tmp:=l[j]:
l[j]:=l[i]:
l[i]:=tmp:
end if:
p:=n/2:
while p>=2 and j>p do
j:=j-p:
p:=p/2:
end do:
j:=j+p:
end do:
l;
end proc:
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">Calcul de la Transform\303\251e Inverse.</Font></Text-field>De m\303\252me, il est possible d'effectuer deux m\303\251thodes pour calculer la transform\303\251e inverse de Fourier :
<Text-field style="Heading 2" layout="Heading 2"><Font encoding="UTF-8">La m\303\251thode na\303\257ve</Font></Text-field>En utilisant le m\303\252me algorithme, on obtient : TFDISimple:=proc(X)
local n,F:
n:=nops(X):
F:=[seq((1/n)*sum(X[i]*exp(2*I*(j-1)*(i-1)*Pi/(n)),i=1..n),j=1..n)];
end proc:
<Text-field style="Heading 2" layout="Heading 2"><Font encoding="UTF-8">La m\303\251thode r\303\251cursive</Font></Text-field>Attention : Pour que l'on puisse retrouver les valeurs initiales, il ne faut pas oublier de diviser par le nombre de valeurs.TFDIRecur:=proc(X)
local Coef,N,Xi,Xp,U,V,Omega,k;
N:=nops(X);
if N=1 then Coef:=X:
else
Xi:=[seq(X[2*k-1],k=1..N/2)];
Xp:=[seq(X[2*k],k=1..N/2)];
U:=TFDIRecur(Xi);
V:=TFDIRecur(Xp);
Omega:=exp(2*I*Pi/N);
Coef:=[seq(U[k]+Omega^(k-1)*V[k],k=1..N/2),seq(U[k]-Omega^(k-1)*V[k],k=1..N/2)]:
end if;
Coef;
end proc:
<Text-field style="Heading 2" layout="Heading 2"><Font encoding="UTF-8">La m\303\251thode it\303\251rative</Font></Text-field>TFDIIter:=proc(x)
local n,i,j,k,a,b,p,l,z,w,h,m,tmp:
n:=nops(x):
l:=Array(1..n):
l:=Array(x):
p:=n/2:
while p>=1 do
z:=1:
w:=exp(I*Pi/p); #C'est la diff\303\251rence
for h from 1 to p do
for m from 1 to n/(2*p) do
a:=h+2*(m-1)*p:
b:=a+p:
tmp:=(l[a]-l[b])*z:
l[a]:=l[a]+l[b]:
l[b]:=tmp:
end do:
z:=z*w:
end do:
p:=p/2:
end do:
j:=1:
for i from 1 to n do
if j>i then tmp:=l[j]:
l[j]:=l[i]:
l[i]:=tmp:
end if:
p:=n/2:
while p>=2 and j>p do
j:=j-p:
p:=p/2:
end do:
j:=j+p:
end do:
for i from 1 to n do
l[i]:=l[i]/n:
end do:
return l;
end proc:
<Text-field style="Heading 1" layout="Heading 1">Mesure du temps de calcul</Text-field>On va ici s'int\303\251resser \303\240 la mesure du temps n\303\251cessaire pour calculer les coefficients de Fourier (Transform\303\251e Directe) pour n "grand", par exemple n=2^5, n=2^10,... .
Pour cela, on va d\303\251finir la liste de nos coefficients par une m\303\251thode "pseudo-al\303\251atoire" : with(RandomTools[MersenneTwister]):
A:=[seq(GenerateFloat(),i=1..2^8)]:
<Text-field style="Heading 2" layout="Heading 2"><Font encoding="UTF-8">M\303\251thode na\303\257ve</Font></Text-field>On effectue le calcul pour la m\303\251thode na\303\257ve : t:=time():
TFDSimple(A):
Temps := time()-t;
<Text-field style="Heading 2" layout="Heading 2"><Font encoding="UTF-8">M\303\251thode r\303\251cursive</Font></Text-field>Calcul pour la m\303\251thode r\303\251cursive : t:=time():
TFDRecur(A):
Temps := time()-t;
<Text-field style="Heading 2" layout="Heading 2"><Font encoding="UTF-8">M\303\251thode it\303\251rative</Font></Text-field>Mesure pour la m\303\251thode it\303\251rative :t:=time():
TFDIter(A):
Temps:= time()-t;
<Text-field style="Heading 1" layout="Heading 1"><Font encoding="UTF-8">Multiplication de polyn\303\264mes</Font></Text-field>
<Text-field style="Heading 2" layout="Heading 2">Algorithme</Text-field>On va prendre en entr\303\251e deux listes contenant les coefficients des deux polyn\303\264mes dont on cherche \303\240 calculer le produit.Il faut prendre des pr\303\251cautions, car la proc\303\251dure ne v\303\251rifie pas si les deux polyn\303\264mes sont de m\303\252me degr\303\251, qui doit \303\252tre une puissance de 2, si l'on souhaite utiliser la m\303\251thode r\303\251cursive ou it\303\251rative.Multiplication:=proc(P,Q)
local n,N,R,A,B,i,j,k:
n:=nops(P):
N:=2*n:
#On cr\303\251e la liste des coefficients \303\251tendus \303\240 2n \303\251l\303\251ments.
A:=[seq(P[k],k=1..n),seq(0,k=n+1..N)];
B:=[seq(Q[k],k=1..n),seq(0,k=n+1..N)];
#On calcule la TFD de chacune de ces listes.
A:=TFDIter(A):
B:=TFDIter(B):
#On effectue les produits
R:=[seq(A[k]*B[k],k=1..N)]:
#On r\303\251cup\303\250re les coefficients.
TFDIIter(R);
end proc:
<Text-field style="Heading 2" layout="Heading 2">Exemple</Text-field>On va poser LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYmLUkjbWlHRiQ2OVEiUEYnLyUnZmFtaWx5R1EwVGltZXN+TmV3flJvbWFuRicvJSVzaXplR1EjMTJGJy8lJWJvbGRHUSZmYWxzZUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUqdW5kZXJsaW5lR0Y3LyUqc3Vic2NyaXB0R0Y3LyUsc3VwZXJzY3JpcHRHRjcvJStmb3JlZ3JvdW5kR1EoWzAsMCwwXUYnLyUrYmFja2dyb3VuZEdRLlsyNTUsMjU1LDI1NV1GJy8lJ29wYXF1ZUdGNy8lK2V4ZWN1dGFibGVHRjcvJSlyZWFkb25seUdGNy8lKWNvbXBvc2VkR0Y3LyUqY29udmVydGVkR0Y3LyUraW1zZWxlY3RlZEdGNy8lLHBsYWNlaG9sZGVyR0Y3LyUwZm9udF9zdHlsZV9uYW1lR1EoMkR+TWF0aEYnLyUqbWF0aGNvbG9yR0ZDLyUvbWF0aGJhY2tncm91bmRHRkYvJStmb250ZmFtaWx5R0YxLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy8lKW1hdGhzaXplR0Y0LUkjbW9HRiQ2M1EjOj1GJy8lJWZvcm1HUSZpbmZpeEYnLyUmZmVuY2VHRjcvJSpzZXBhcmF0b3JHRjcvJSdsc3BhY2VHUS90aGlja21hdGhzcGFjZUYnLyUncnNwYWNlR0Zqby8lKXN0cmV0Y2h5R0Y3LyUqc3ltbWV0cmljR0Y3LyUobWF4c2l6ZUdRKWluZmluaXR5RicvJShtaW5zaXplR1EiMUYnLyUobGFyZ2VvcEdGNy8lLm1vdmFibGVsaW1pdHNHRjcvJSdhY2NlbnRHRjcvJTBmb250X3N0eWxlX25hbWVHRlcvJSVzaXplR0Y0LyUrZm9yZWdyb3VuZEdGQy8lK2JhY2tncm91bmRHRkYtRiM2Jy1GLDY5USFGJ0YvRjJGNUY4RjtGPUY/RkFGREZHRklGS0ZNRk9GUUZTRlVGWEZaRmZuRmhuRltvLUkrbXVuZGVyb3ZlckdGJDYnLUZebzYzUSYmU3VtO0YnL0Zib1EncHJlZml4RidGZG9GZm8vRmlvUSQwZW1GJy9GXHBRLnRoaW5tYXRoc3BhY2VGJy9GXnBGOkZfcEZhcEZkcC9GaHBGOi9GanBGOkZbcUZdcUZfcUZhcUZjcS1GIzYnRmdxLUYsNjlRImlGJ0YvL0YzUSMxMEYnRjVGOEY7Rj1GPy9GQlEsWzIwMCwwLDIwMF1GJ0ZERkdGSUZLRk1GT0ZRL0ZURjpGVS9GWUZhc0ZaRmZuRmhuL0Zcb0Zfcy1GXm82M1EiPUYnRmFvRmRvRmZvRmhvRltwRl1wRl9wRmFwRmRwRmdwRmlwRltxRl1xRl9xRmFxRmNxLUkjbW5HRiQ2OVEiMEYnRi9GMkY1L0Y5RjdGO0Y9Rj9GQUZERkdGSUZLRk1GT0ZRRlNGVUZYRlpGZm4vRmluUSdub3JtYWxGJ0Zbb0ZncS1GaXM2OVEiN0YnRi9GMkY1Rlx0RjtGPUY/RkFGREZHRklGS0ZNRk9GUUZTRlVGWEZaRmZuRl10RltvRltxLyUsYWNjZW50dW5kZXJHRjdGZ3EtSSVtc3VwR0YkNiUtRiw2OVEjaVhGJ0YvRjJGNUY4RjtGPUY/RkFGREZHRklGS0ZNRk9GUUZTRlVGWEZaRmZuRmhuRltvLUYsNjlGXXNGL0YyRjVGOEY7Rj1GP0ZBRkRGR0ZJRktGTUZPRlFGU0ZVRlhGWkZmbkZobkZbby8lMXN1cGVyc2NyaXB0c2hpZnRHUSIwRidGZ3FGZ3E= et LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYmLUkjbWlHRiQ2OVEiUUYnLyUnZmFtaWx5R1EwVGltZXN+TmV3flJvbWFuRicvJSVzaXplR1EjMTJGJy8lJWJvbGRHUSZmYWxzZUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUqdW5kZXJsaW5lR0Y3LyUqc3Vic2NyaXB0R0Y3LyUsc3VwZXJzY3JpcHRHRjcvJStmb3JlZ3JvdW5kR1EoWzAsMCwwXUYnLyUrYmFja2dyb3VuZEdRLlsyNTUsMjU1LDI1NV1GJy8lJ29wYXF1ZUdGNy8lK2V4ZWN1dGFibGVHRjcvJSlyZWFkb25seUdGNy8lKWNvbXBvc2VkR0Y3LyUqY29udmVydGVkR0Y3LyUraW1zZWxlY3RlZEdGNy8lLHBsYWNlaG9sZGVyR0Y3LyUwZm9udF9zdHlsZV9uYW1lR1EoMkR+TWF0aEYnLyUqbWF0aGNvbG9yR0ZDLyUvbWF0aGJhY2tncm91bmRHRkYvJStmb250ZmFtaWx5R0YxLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy8lKW1hdGhzaXplR0Y0LUkjbW9HRiQ2M1EjOj1GJy8lJWZvcm1HUSZpbmZpeEYnLyUmZmVuY2VHRjcvJSpzZXBhcmF0b3JHRjcvJSdsc3BhY2VHUS90aGlja21hdGhzcGFjZUYnLyUncnNwYWNlR0Zqby8lKXN0cmV0Y2h5R0Y3LyUqc3ltbWV0cmljR0Y3LyUobWF4c2l6ZUdRKWluZmluaXR5RicvJShtaW5zaXplR1EiMUYnLyUobGFyZ2VvcEdGNy8lLm1vdmFibGVsaW1pdHNHRjcvJSdhY2NlbnRHRjcvJTBmb250X3N0eWxlX25hbWVHRlcvJSVzaXplR0Y0LyUrZm9yZWdyb3VuZEdGQy8lK2JhY2tncm91bmRHRkYtRiM2KS1GLDY5USFGJ0YvRjJGNUY4RjtGPUY/RkFGREZHRklGS0ZNRk9GUUZTRlVGWEZaRmZuRmhuRltvLUkrbXVuZGVyb3ZlckdGJDYnLUZebzYzUSYmU3VtO0YnL0Zib1EncHJlZml4RidGZG9GZm8vRmlvUSQwZW1GJy9GXHBRLnRoaW5tYXRoc3BhY2VGJy9GXnBGOkZfcEZhcEZkcC9GaHBGOi9GanBGOkZbcUZdcUZfcUZhcUZjcS1GIzYmRmdxLUYsNjlRImlGJ0YvL0YzUSMxMEYnRjVGOEY7Rj1GPy9GQlEsWzIwMCwwLDIwMF1GJ0ZERkdGSUZLRk1GT0ZRL0ZURjpGVS9GWUZhc0ZaRmZuRmhuL0Zcb0Zfcy1GXm82M1EiPUYnRmFvRmRvRmZvRmhvRltwRl1wRl9wRmFwRmRwRmdwRmlwRltxRl1xRl9xRmFxRmNxLUkjbW5HRiQ2OVEiMEYnRi9GMkY1L0Y5RjdGO0Y9Rj9GQUZERkdGSUZLRk1GT0ZRRlNGVUZYRlpGZm4vRmluUSdub3JtYWxGJ0Zbby1GaXM2OVEiN0YnRi9GMkY1Rlx0RjtGPUY/RkFGREZHRklGS0ZNRk9GUUZTRlVGWEZaRmZuRl10RltvRltxLyUsYWNjZW50dW5kZXJHRjdGZ3EtSSVtc3VwR0YkNiUtRiw2OUZdc0YvRjJGNUY4RjtGPUY/RkFGREZHRklGS0ZNRk9GUUZTRlVGWEZaRmZuRmhuRltvRmd0LyUxc3VwZXJzY3JpcHRzaGlmdEdRIjBGJ0ZncS1GZXQ2JS1GLDY5USJYRidGL0YyRjVGOEY7Rj1GP0ZBRkRGR0ZJRktGTUZPRlFGU0ZVRlhGWkZmbkZobkZbb0ZndEZpdEZncUZncQ== doncLUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYpLUkjbW9HRiQ2M1ExJkludmlzaWJsZVRpbWVzO0YnLyUlZm9ybUdRJmluZml4RicvJSZmZW5jZUdRJmZhbHNlRicvJSpzZXBhcmF0b3JHRjQvJSdsc3BhY2VHUS90aGlja21hdGhzcGFjZUYnLyUncnNwYWNlR0Y5LyUpc3RyZXRjaHlHRjQvJSpzeW1tZXRyaWNHRjQvJShtYXhzaXplR1EpaW5maW5pdHlGJy8lKG1pbnNpemVHUSIxRicvJShsYXJnZW9wR0Y0LyUubW92YWJsZWxpbWl0c0dGNC8lJ2FjY2VudEdGNC8lMGZvbnRfc3R5bGVfbmFtZUdRKDJEfk1hdGhGJy8lJXNpemVHUSMxMkYnLyUrZm9yZWdyb3VuZEdRKFswLDAsMF1GJy8lK2JhY2tncm91bmRHUS5bMjU1LDI1NSwyNTVdRictSSNtaUdGJDY5USJuRicvJSdmYW1pbHlHUTBUaW1lc35OZXd+Um9tYW5GJy8lJXNpemVHRlEvJSVib2xkR0Y0LyUnaXRhbGljR1EldHJ1ZUYnLyUqdW5kZXJsaW5lR0Y0LyUqc3Vic2NyaXB0R0Y0LyUsc3VwZXJzY3JpcHRHRjQvJStmb3JlZ3JvdW5kR0ZULyUrYmFja2dyb3VuZEdGVy8lJ29wYXF1ZUdGNC8lK2V4ZWN1dGFibGVHRjQvJSlyZWFkb25seUdGNC8lKWNvbXBvc2VkR0Y0LyUqY29udmVydGVkR0Y0LyUraW1zZWxlY3RlZEdGNC8lLHBsYWNlaG9sZGVyR0Y0LyUwZm9udF9zdHlsZV9uYW1lR0ZOLyUqbWF0aGNvbG9yR0ZULyUvbWF0aGJhY2tncm91bmRHRlcvJStmb250ZmFtaWx5R0Zobi8lLG1hdGh2YXJpYW50R1EnaXRhbGljRicvJSltYXRoc2l6ZUdGUS1GLDYzUSI9RidGL0YyRjVGN0Y6RjxGPkZARkNGRkZIRkpGTEZPRlJGVS1JI21uR0YkNjlRIjhGJ0ZmbkZpbkZbby9GXm9GNEZgb0Zib0Zkb0Zmb0Zob0Zqb0ZccEZecEZgcEZicEZkcEZmcEZocEZqcEZccUZecS9GYXFRJ25vcm1hbEYnRmNxRmVxLUklbXN1cEdGJDYlLUZpcTY5USIyRidGZm5GaW5GW29GXHJGYG9GYm9GZG9GZm9GaG9Gam9GXHBGXnBGYHBGYnBGZHBGZnBGaHBGanBGXHFGXnFGXXJGY3EtRmlxNjlRIzMuRidGZm5GaW5GW29GXHJGYG9GYm9GZG9GZm9GaG9Gam9GXHBGXnBGYHBGYnBGZHBGZnBGaHBGanBGXHFGXnFGXXJGY3EvJTFzdXBlcnNjcmlwdHNoaWZ0R1EiMEYnLUZZNjlRIUYnRmZuRmluRltvRl1vRmBvRmJvRmRvRmZvRmhvRmpvRlxwRl5wRmBwRmJwRmRwRmZwRmhwRmpwRlxxRl5xRmBxRmNx
<Text-field style="Heading 3" layout="Heading 3">Algo</Text-field>On va demander la liste des coefficients du polyn\303\264me R=P*Q. Pour une lecture plus facile, nous en prendrons les valeurs arrondies.P:=[seq(i,i=0..7)]:Q:=[seq(i^i,i=0..7)]:R:=evalf(Multiplication(P,Q)):[seq(R[j],j=1..2*nops(P))];R:=[seq(round(R[j]),j=1..2*nops(P))];
<Text-field style="Heading 3" layout="Heading 3">Maple</Text-field>On va evaluer le polyn\303\264me P*Q :P:=sum(i*X^i,i=0..7):Q:=sum(i^i*X^i,i=0..7):sort(expand(P*Q),X,ascending);