Ecole Normale Superieure Departement d'Informatique
4
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
4
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
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.
Voir
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
´ 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+RS, T=X+RTavec degRS< net degRT< m. Sin < mneiray’nli,abnlnoSie.irfa`aelemtniauolce´e´visionderedeladiSparT consistea`tuerletermedeplushautdegr´edeSen effectuant la soustraction δ nδ+δm δ S−aX T= (aX+RS)−(aX+aX RT) =RS−aX RT, 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 Reck(P(X)) =X P(1/Xque). Montrer
−1n−m+1 Recn−m(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) 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.ConGi∈A[X] de´finieparG0= 1 et i+1 2 2 Gi+1= 2Gi−F∙GmodX i pouri≥0. Montrerque pour tour entieri≥0, nous avons i 2 F∙Gi≡1 modX . R´eponse: •i= 0 :trivial i 2 •i+ 1≥1 et vrai pouri(F∙Gi= 1 +P(X)X) : i+1 2 2 F∙Gi+1≡F∙(2Gi−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:Recm(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. Soienta1, . . . , an∈A.
k 1. Supposonsquenpletecom2=estunepuissancee2ednoct´disnorenlsurb’abireirnaT `anfeui:rinap´dfiellse •chacune desnomeunpolynˆlluifea`ee´icossatseseX−ajpourj∈ {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 toutu∈Tqiteneeuirae´mhta,mplexit´vecunecoO(M(n) logn). 2.De´duiredesquestionspr´ece´dentesunalgorithmequicalculeP(a1), . . . , P(an) pourtout n∈Nrieam´thiqetenueaevucenocpmelix´tO(M(n) logn).
Partie III : Interpolation de Lagrange rapide Soienta1, . . . , an∈Aixousetdtneniidtxsueesdtac`A1, . . . , An∈A.
1.Montrerqu’ilexisteuneuniquesuitedepolynoˆmesΔk(X)∈A[X], aveck∈ {1, . . . , n}, dedegre´n−1 telle que n X P(X) :=Ak∙Δk(X) k=1 v´erifieP(ai) =Aipour touti∈ {1, . . . , n}. Q n 2. Soitdkle coefficient dominant de Δkpourk∈ {1, . . . , n}et soitM(X() =X−ai). 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 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 i2 2 sous-matricesBj(avec 1≤j≤n/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.
