Ecole Normale Superieure Departement d'Informatique

Description

Niveau: Supérieur
Ecole Normale Superieure 2009-2010 Departement d'Informatique Algorithmique et Programmation Examen Notes de cours autorisees a l'exception de tout autre document. Le resultat d'une question peut etre utilise dans la suite du probleme meme si elle n'a pas ete resolue. Duree : 3 heures Exercise 1. Soit A un anneau commutatif unitaire. Partie I : Division euclidienne rapide par la methode de Newton Soient S, T ? A[X] avec deg(S) = n, deg(T ) = m et T unitaire. 1. Montrer que l'algorithme classique de division euclienne de S par T a une complexite arithmetique en O(n2). Reponse : L'algorithme naıf pour calculer Q et R tels que S = QT + R avec degR < deg T consiste a poser la division. Pour cela les termes dominants sont d'abord isoles : S = aXn +RS, T = X m +RT avec degRS < n et degRT < m. Si n < m, il n'y a rien a faire. Sinon la boucle elementaire de la division de S par T consiste a tuer le terme de plus haut degre de S en effectuant la soustraction S ? aX?T = (aXn +RS)? (aX ?+m + aX?RT ) = RS ? aX ?RT , ou ? = m?n.

• multiplication


• anneau


• quasi-anneau des booleens


• produit dans le quasi-anneau des booleens


• matrice n?


• choix independants de la matrice a?


• algorithme de strassen


• algorithmes de calcul du produit de matrices booleennes


• autorisees sur les composantes des matrices

Sujets

• Multiplication
• Anneau
• Algorithme de Strassen

Informations

• Publié par: profil-nechor-2012
• Nombre de lectures: 18
• Langue: Français

Extrait

´ EcoleNormaleSup´erieure D´epartementd’Informatique

AlgorithmiqueetProgrammation Examen

Notesdecoursautorise´esa`l’exceptiondetoutautredocument.

Ler´esultatd’unequestionpeutˆetreutilise´danslasuitedu probl`ememˆemesiellen’apase´te´re´solue.

Dure´e:3heures

Exercise 1.SoitAun anneau commutatif unitaire. PartieI:Divisioneuclidiennerapideparlame ´ thodedeNewton SoientS, T∈A[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 d’abordisol´es: n m S=aX+R S , T=X+R T avec degR S < net degR T < m. Sin < mneiray’nli,abnlnoSie.irfa`aelemtniauolce´e´visionderedeladiSparT consistea`tuerletermedeplushautdegr´edeSen effectuant la soustraction δ nδ+δm δ S−aX T= (aX+R S )−(aX+aX R T ) =R S −aX R T , o`uδ=m−na`eL.ylopmoˆneobtenuestcongruSmoduloTm,iandtsemetcirtse´rgede infe´rieur`an´ed´procercet´er`’iasuuqaylplI’n.´reedomegedpounnˆlytboarinesuje`’uq strictementinf´erieur`ancedeets`qaugoardertraccseissfitnestus. Lacomplexit´edecetalgorithmeestfacile`aestimer.Labouclee´le´mentaires’effectue enO(mnasdsnoitare´po)A; dans le pire des cas, l’algorithme effectue (n−m+ 1) passagesdanscetteboucle,desortequelacomplexit´edeladivisiondeSparTest de O(m(n−msdonsan´)e)optiraA2).une petite constante :. (avec

k 2. PourP∈A[X] etk≥deg(P), nous notons Rec k (P(X)) =X P(1/Xque). Montrer

−1n−m+1 Rec n−m (Q) = Rec n (S)Rec m (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) d’ou` n n−m mn−m+1m−1 X S(1/X) = [X Q(1/X)][X T(1/X)] +X[X R(1/X)] etler´esultat. 3. SoitF∈A[X] avecF(0) = 1 et soit`≥etiusalsnore´disesomnˆlypode1.ConG i ∈A[X] de´finieparG 0 = 1 et i+1 2 2 G i+1 = 2G i −F∙GmodX i pouri≥0. Montrerque pour tour entieri≥0, nous avons i 2 F∙G i ≡1 modX . R´eponse: •i= 0 :trivial i 2 •i+ 1≥1 et vrai pouri(F∙G i = 1 +P(X)X) : i+1 2 2 F∙G i+1 ≡F∙(2G i −F∙G) 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:Rec m (Trifie)v´enoidelcsdsleitnoen’´c´onpue(ueiqTest unitaire).La n−m ` m´ethodedeNewtonpermetdecalculersoninversemoduloXuqecAah.ntra´eiten e´tapedelaboucleoneffectuedeuxmultiplicationsdespolynˆomesdedegre´auplus i 2.Donclacomplexit´eest:

` 2M(1) + 2M(2) + 2M(4) +∙2M(2 ) ` o`u2> m−n. 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, n∈N).

´ PartieII:Evaluationrapidedepolyn ˆ omes SoitP∈A[X] unitaire avec deg(P) =n. Soienta 1 , . . . , a n ∈A.

k 1. Supposonsquenpletecom2=estunepuissancee2ednoct´disnorenlsurb’abireirnaT `anfeui:rinap´dfiellse •chacune desnomeunpolynˆlluifea`ee´icossatseseX−a j pourj∈ {1, . . . , n}; •pour chaque nœud interneuayant les filsvetwˆoynolxpsmessauase´icoM v (X) et M w (X) respectivement,uesocistasuae´ylopmoˆneM u (X) =M v (X)∙M w (X). (a) Donnerun algorithme pour construire l’arbreTtirae´tixelpmoceunecavetiquhm´e enO(M(n) logn). (b)Donnerunalgorithmequiprenantenentre´eP, (a 1 , . . . , a n ) etT, calculeP(X) mod M u (X) pour toutu∈Tqiteneeuirae´mhta,mplexit´vecunecoO(M(n) logn). 2.De´duiredesquestionspr´ece´dentesunalgorithmequicalculeP(a 1 ), . . . , P(a n ) pourtout n∈Nrieam´thiqetenueaevucenocpmelix´tO(M(n) logn).

Partie III : Interpolation de Lagrange rapide Soienta 1 , . . . , a n ∈Aixousetdtneniidtxsueesdtac`A 1 , . . . , A n ∈A.

1.Montrerqu’ilexisteuneuniquesuitedepolynoˆmesΔ k (X)∈A[X], aveck∈ {1, . . . , n}, dedegre´n−1 telle que n X P(X) :=A k ∙Δ k (X) k=1 v´erifieP(a i ) =A i pour touti∈ {1, . . . , n}. Q n 2. Soitd k le coefficient dominant de Δ k pourk∈ {1, . . . , n}et soitM(X() =X−a i ). i=1 0 Enappliquantlesre´sultatsdelaPartie IIa`M(X), donner un algorithme pour calculer d 1 , . . . , d n cenucemovaarithm´eplexit´euqitneeO(M(n) logn). 3.Donnerunalgorithmequiprenantenentr´ee(a 1 , . . . , a n ) et (A 1 , . . . , A n ), 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 pour∨nous 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 1≤i≤n/log (n)) de taillen×log (n) etBen i 2 2 sous-matricesB j (avec 1≤j≤n/log (n)) de taille log 2 (n)×n. 2

n/log (n) X 2 1.Montrerquenouspouvonse´crireAB=A i B i aphecuuqu`doortiA i B i est une i=1 matricen×n. 2 2. Montrerque l’algorithme naturel pour calculer chaque matriceA i B i demandeO(nlog (n)) 2 op´erations.