Ecole Normale Superieure Departement d'Informatique

Publié par

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


Publié le : mardi 29 mai 2012
Lecture(s) : 18
Source : di.ens.fr
Nombre de pages : 4
Voir plus Voir moins
´ 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.
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.

Diffusez cette publication

Vous aimerez aussi