[PDF] Algorithmes arithmétiques II – Feuille de TD 2

Déter minerun polynôme de connexion de la suite, de degr é<4. On pourra, si besoin, utiliser l"algorithme

Commenter les r ésultatsobtenus.

Dans le cas général, on exécute l"algorithme d"Euclide étendu sur les entréesA(X) =X2netB(X) =å2n1

On notek1 le premier indice pour lequel le resteRk(X)a degré Question 3.-Quelle est la relation entre degVk, degRk1et degA?

Question 4.-Démontrer queVkest un polynôme de connexion de la suiteben étudiant notamment la croissance

Question 5.-Décrire un nouvel algorithme de calcul de polynôme de connexion, et en donner la complexité.Exercice 2.(?)?Implantation du calcul du polynôme de connexion par l"algorithme d"Euclide.Exercice 2.(?)?Implantation du calcul du polynôme de connexion par l"algorithme d"Euclide.Exercice 2.(?)?Implantation du calcul du polynôme de connexion par l"algorithme d"Euclide.Exercice 2.(?)?Implantation du calcul du polynôme de connexion par l"algorithme d"Euclide.Exercice 2.(?)?Implantation du calcul du polynôme de connexion par l"algorithme d"Euclide.Exercice 2.(?)?Implantation du calcul du polynôme de connexion par l"algorithme d"Euclide.Exercice 2.(?)?Implantation du calcul du polynôme de connexion par l"algorithme d"Euclide.Exercice 2.(?)?Implantation du calcul du polynôme de connexion par l"algorithme d"Euclide.Exercice 2.(?)?Implantation du calcul du polynôme de connexion par l"algorithme d"Euclide.Exercice 2.(?)?Implantation du calcul du polynôme de connexion par l"algorithme d"Euclide.Exercice 2.(?)?Implantation du calcul du polynôme de connexion par l"algorithme d"Euclide.Exercice 2.(?)?Implantation du calcul du polynôme de connexion par l"algorithme d"Euclide.Exercice 2.(?)?Implantation du calcul du polynôme de connexion par l"algorithme d"Euclide.Exercice 2.(?)?Implantation du calcul du polynôme de connexion par l"algorithme d"Euclide.Exercice 2.(?)?Implantation du calcul du polynôme de connexion par l"algorithme d"Euclide.Exercice 2.(?)?Implantation du calcul du polynôme de connexion par l"algorithme d"Euclide.Exercice 2.(?)?Implantation du calcul du polynôme de connexion par l"algorithme d"Euclide.

Question 1.-Implanter l"algorithme d"Euclide étendu, puis l"algorithme de calcul de polynôme de connexion vu

Question 2.-Comparer expérimentalement sa complexité avec celle de l"algorithme de Berlekamp-Massey.

Exercice 3.(?)Suite vectorielle et LFSR.Exercice 3.(?)Suite vectorielle et LFSR.Exercice 3.(?)Suite vectorielle et LFSR.Exercice 3.(?)Suite vectorielle et LFSR.Exercice 3.(?)Suite vectorielle et LFSR.Exercice 3.(?)Suite vectorielle et LFSR.Exercice 3.(?)Suite vectorielle et LFSR.Exercice 3.(?)Suite vectorielle et LFSR.Exercice 3.(?)Suite vectorielle et LFSR.Exercice 3.(?)Suite vectorielle et LFSR.Exercice 3.(?)Suite vectorielle et LFSR.Exercice 3.(?)Suite vectorielle et LFSR.Exercice 3.(?)Suite vectorielle et LFSR.Exercice 3.(?)Suite vectorielle et LFSR.Exercice 3.(?)Suite vectorielle et LFSR.Exercice 3.(?)Suite vectorielle et LFSR.Exercice 3.(?)Suite vectorielle et LFSR.

Soitu= (un)n2Nune suite récurrente non-nulle produite par un LFSR de dimensionL. On noteP(x) =ådj=0cjXj

Soitv= (vk)définie par

Question 1.-Démontrer quevest une suite récurrente surFL. En donner une description sous forme de suite

Question 2.-Que vaut detA? En déduire une condition suffisante pour que la suiteune soit pas nulle à partir

Question 3.-À l"aide des questions précédentes, démontrer que siF=Fq, alors la suiteua une périodeqL1.Exercice 4.(? ? ?)?Implantation de la résolution de système creux.Exercice 4.(? ? ?)?Implantation de la résolution de système creux.Exercice 4.(? ? ?)?Implantation de la résolution de système creux.Exercice 4.(? ? ?)?Implantation de la résolution de système creux.Exercice 4.(? ? ?)?Implantation de la résolution de système creux.Exercice 4.(? ? ?)?Implantation de la résolution de système creux.Exercice 4.(? ? ?)?Implantation de la résolution de système creux.Exercice 4.(? ? ?)?Implantation de la résolution de système creux.Exercice 4.(? ? ?)?Implantation de la résolution de système creux.Exercice 4.(? ? ?)?Implantation de la résolution de système creux.Exercice 4.(? ? ?)?Implantation de la résolution de système creux.Exercice 4.(? ? ?)?Implantation de la résolution de système creux.Exercice 4.(? ? ?)?Implantation de la résolution de système creux.Exercice 4.(? ? ?)?Implantation de la résolution de système creux.Exercice 4.(? ? ?)?Implantation de la résolution de système creux.Exercice 4.(? ? ?)?Implantation de la résolution de système creux.Exercice 4.(? ? ?)?Implantation de la résolution de système creux.

Dans cet exercice, on se donne comme objectif de résoudre effectivement un système linéaire creux en tempsO(tn2)

Question 1.-Implanter une structure permettant de gérer et d"effectuer des opérations élémentaires sur des

matrices creuses : création d"une matrice creuse aléatoire, somme de deux matrices, produit matrice-vecteur, échange

Question 2.-Implanter une méthode de Horner pour calculerQ(A)ben tempsO(ndt)et espaceO(nt), oùQ(X)2

F[X]est de degrédetb2Fn.

Question 3.-Implanter une fonction qui calcule le pgcd et le ppcm de deux polynômes de degréden temps

O(d2).

implanter une fonction qui calcule le polynôme annulateur d"une suite v ectorielleitér éev= (Akb)k2N;

Question 6.-En utilisant l"algorithme de Wiedemann, implanter une fonctionkernel_elementqui calcule en

Question 7.-Donner les complexités expérimentales (en temps) des fonctionsone_solutionetkernel_element.

On prendra garde de choisir des valeurs assez grandes denet assez petites det(relativement àn) pour observer la