La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Partagez cette publication

´ EcoleNormaleSup´erieure D´epartementdInformatique
AlgorithmiqueetProgrammation Examen
Notesdecoursautorise´esa`lexceptiondetoutautredocument.
Ler´esultatdunequestionpeutˆetreutilise´danslasuitedu probl`ememˆemesiellenapase´te´re´solue.
Dure´e:3heures
Exercise 1.SoitAun anneau commutatif unitaire. PartieI:Divisioneuclidiennerapideparlame´thodedeNewton SoientS, TA[X] avec deg(S) =n, deg(T) =metTunitaire.
2009-2010
1. Montrer que l’algorithme classique de division euclienne deSparTenuaet´xilempco 2 arithm´etiqueenO(n). R´eponse:L’algorithme na¨ıf pour calculerQetRtels queS=QT+Ravec degR <degTinomtsanntsosnocopa`etsiserladivision.Poruecaleltsreemds dabordisol´es: n m S=aX+RS, T=X+RTavec degRS< net degRT< m. Sin < mneiraynli,abnlnoSie.irfa`aelemtniauolce´e´visionderedeladiSparT consistea`tuerletermedeplushautdegr´edeSen effectuant la soustraction δ nδ+δm δ SaX T= (aX+RS)(aX+aX RT) =RSaX RT, o`uδ=mna`eL.ylopmoˆneobtenuestcongruSmoduloTm,iandtsemetcirtse´rgede infe´rieur`an´ed´procercet´er`iasuuqaylplIn.´reedomegedpounnˆlytboarinesuje`uq strictementinf´erieur`ancedeets`qaugoardertraccseissfitnestus. Lacomplexit´edecetalgorithmeestfacile`aestimer.Labouclee´le´mentaireseectue enO(mnasdsnoitare´po)A; dans le pire des cas, l’algorithme effectue (nm+ 1) passagesdanscetteboucle,desortequelacomplexit´edeladivisiondeSparTest de O(m(nmsdonsan´)e)optiraA2).une petite constante :. (avec
k 2. PourPA[X] etkdeg(P), nous notons Reck(P(X)) =X P(1/Xque). Montrer
1nm+1 Recnm(Q) = Recn(S)Recm(T) modX ,
o`uQest le quotient de la division euclidienne deSparT.
Re´ponse:Nous avons
S(X) =Q(X)T(X) +R(X)
soit n n X S(1/X) =X(Q(1/X)T(1/X) +R(1/X) dou` n nm mnm+1m1 X S(1/X) = [X Q(1/X)][X T(1/X)] +X[X R(1/X)] etler´esultat. 3. SoitFA[X] avecF(0) = 1 et soit`etiusalsnore´disesomnˆlypode1.ConGiA[X] de´nieparG0= 1 et i+1 2 2 Gi+1= 2GiFGmodX i pouri0. Montrerque pour tour entieri0, nous avons i 2 FGi1 modX . R´eponse: i= 0 :trivial i 2 i+ 11 et vrai pouri(FGi= 1 +P(X)X) : i+1 2 2 FGi+1F(2GiFG) modX i i ii+1 2 22 2 2 + 2P(X)X(1 +P(X)X) modX i+1i+1 2 22 1 +P(X)XmodX
4.End´eduireunalgorithmepourcalculerQet le resteRde la division euclidienne deS parT.
Re´ponse:Recm(Trie)v´enoidelcsdsleitnoen´c´onpue(ueiqTest unitaire).La nm ` m´ethodedeNewtonpermetdecalculersoninversemoduloXuqecAah.ntra´eiten e´tapedelaboucleoneectuedeuxmultiplicationsdespolynˆomesdedegre´auplus i 2.Donclacomplexit´eest:
` 2M(1) + 2M(2) + 2M(4) +2M(2 ) ` o`u2> mn. 5.Montrerquelacomplexit´earithm´etiquedecenouvelalgorithmededivisioneuclidienne applique´`adeuxpolynoˆmesdedegr´e< nest enO(M(no))u`M(nactlplomitex´ese) arithme´tiqueduproduitdedeuxpolynˆomesdedegre´< ndeA[X] (avecM(n+m)M(n) +M(m) pourm, nN).
´ PartieII:Evaluationrapidedepolynˆomes SoitPA[X] unitaire avec deg(P) =n. Soienta1, . . . , anA.
k 1. Supposonsquenpletecom2=estunepuissancee2ednoct´disnorenlsurbabireirnaT `anfeui:rinap´dellse chacune desnomeunpolynˆlluifea`ee´icossatseseXajpourj∈ {1, . . . , n}; pour chaque nœud interneuayant les filsvetwˆoynolxpsmessauase´icoMv(X) et Mw(X) respectivement,uesocistasuae´ylopmoˆneMu(X) =Mv(X)Mw(X). (a) Donnerun algorithme pour construire l’arbreTtirae´tixelpmoceunecavetiquhm´e enO(M(n) logn). (b)Donnerunalgorithmequiprenantenentre´eP, (a1, . . . , an) etT, calculeP(X) mod Mu(X) pour toutuTqiteneeuirae´mhta,mplexit´vecunecoO(M(n) logn). 2.De´duiredesquestionspr´ece´dentesunalgorithmequicalculeP(a1), . . . , P(an) pourtout nNrieam´thiqetenueaevucenocpmelix´tO(M(n) logn).
Partie III : Interpolation de Lagrange rapide Soienta1, . . . , anAixousetdtneniidtxsueesdtac`A1, . . . , AnA.
1.MontrerquilexisteuneuniquesuitedepolynoˆmesΔk(X)A[X], aveck∈ {1, . . . , n}, dedegre´n1 telle que n X P(X) :=AkΔk(X) k=1 v´erieP(ai) =Aipour touti∈ {1, . . . , n}. Q n 2. Soitdkle coefficient dominant de Δkpourk∈ {1, . . . , n}et soitM(X() =Xai). i=1 0 Enappliquantlesre´sultatsdelaPartie IIa`M(X), donner un algorithme pour calculer d1, . . . , dncenucemovaarithm´eplexit´euqitneeO(M(n) logn). 3.Donnerunalgorithmequiprenantenentr´ee(a1, . . . , an) et (A1, . . . , An), calculeP(X) avecunecomplexit´earithme´tiqueenO(M(n) logn).
Exercise 2.L’algorithme de Strassen de multiplication de matrices ne fonctionne que sur des anneaux et non sur lequasi-anneauboes´eolne(sd{0,1},,,0,1) puisque 1 n’a pas d’inverse pournous proposons de trouver des algorithmes de calcul du produit de matrices. Nous boole´ennes.
Partie I : Multiplication des quatre russes SoientAetBxmatricesbool´eesennduen×nsupposons que log (. Nousn) divisenet nous 2 partitionnonsAen sous-matricesA(avec 1in/log (n)) de taillen×log (n) etBen i2 2 sous-matricesBj(avec 1jn/log (n)) de taille log2(n)×n. 2
n/log (n) X 2 1.Montrerquenouspouvonse´crireAB=AiBiaphecuuqu`doortiAiBiest une i=1 matricen×n. 2 2. Montrerque l’algorithme naturel pour calculer chaque matriceAiBidemandeO(nlog (n)) 2 op´erations.