7 jours d'essai offerts
Cet ouvrage et des milliers d'autres sont disponibles en abonnement pour 8,99€/mois
1
AlgorithmiqueetProgrammation TD n 9 : Fast Fourier Transform
Petits Rappels
Ecolenormalesup´erieure D´epartementdinformatique td-algo@di.ens.fr
2011-2012
ConvolutionLaconvolutionde deux vecteurs (a0, . . . , am1) et (b0, . . . , bn1) est le vecteurc=ab de longueurn+mdont lekeenccoismtet`ee-: X ck=aibj(0i < m,0j < n) i+j=k
2
1 ()),o`ulesvecteursaet Leth´eor`emedeconvolutionditquec=DF Tn+mDF Tm+n(a)DF Tn+m(b bttaandeiussj`quzsedore´se´tcevasnolpe´ctmoeleralatlin+m.
R´einventezlaFFTvous-meˆme
Exercice1:Formenormalealge´briquedunefonctionboole´ennesin.Onesset´erfenoa`nuntcoi n boole´ennef(x1, . . . , xn) : (F2)F2teC.rspaabatdeleerv´e´tiec(-tstefonctionpeutˆertrepe´rsene´tee n `a-direparlalistedes2valeursquelleprendsuccessivement),oubiencommeunemumtlviplonyoˆari´ede degr´eauplusnsurF2[x1, . . . , xnpeapeqll]nr.Ome´le´xustneecrlsuuede`apsorF2, l’addition est leXOR 2 et la multiplication est leAND. Il s’ensuit qu’on a toujoursx=xeptuodcnesertser,etquona`erdni conside´rerdesmonˆomessanscarr´e.Pluspre´cise´ment,onarme(etonvajustier)quefriect:´s X a1an f(x1, . . . , xn) =g(a1, . . . , an)x . . . x 1n n a(F2)
a o`ug(aemoduomnˆeoceitn)seltcex.ttCeaestlatnenoitperese´rrmalmenoforqieue´rbaegl(ANF) n def. Il s’ensuit queg: (F2)F2etsell-eˆmmeueenofcntionbool´eenne.Ltubeledrexeecictdese construire un algorithmeinvolutif(auto-inverse) qui calculegerdtiarpa`f,ruBit.sˆeniqpuercoern´eemt il sera “rapide”. 1. Exprimezgicel`oulscesaafdannclaciuqerude´corapelqueztron.M=1ulegest involutive. 2.Oncherche`a´ecrirefsous la forme :
f(x1, . . . , xn) =f0(x1, . . . , xn1) +xnf1(x1, . . . , xn1)
Exprimezf0etf1en fonction defd´,equmˆemssonellertnameno`l-aptrasetuniend´etbiese.inuq 3.Onconside`relesANFg0etg1def0etf1respectivement. Exprimezgen fonction deg0etg1. Concluez que l’ANF existe et est unique. 4.D´eduisez-enunalgorithmedecalculdegnnoD.mpcosaeze.t´xile 5.Cetalgorithmepermetenfaitdecalculerlatabledev´erite´dunpolynoˆmemultivari´ede F2[x1, . . . , xnly-luerlepoa`tiave´sisnareteqıvcouiureda¨enor´clcpaaeevix´tmplesacoarezComp.] n nˆome2fois. Solution de l’exercice 1 1. Sinoral1,=rchencsoe´rceha`riefsous la formef(x1) =g(1)x1+g(0). En fixantx1= 0, on trouveg(0) =f(0). Ensuite, en fixantx1= 1, on trouveg(1) =f(0) +f)1L.ceraca`treieolnvifut( delop´erationesttrivial.
1