Inscription / Connexion Nouveau Sujet
Niveau Maths sup
Partager :

Algorithme division deux polynômes

Posté par
believesh
09-04-17 à 12:18

Bonjour!

Je cherche à écrire un algorithme permettant de calculer le reste et le quotient de la division euclidienne de deux polynômes.
Voilà ce que j'ai fait, mais j'aimerai savoir si c'est correct:

Initialisation des variables: Valeurs d'entrée: A et B (on cherche à faire la DE de A par B), Q=0

Tant que degA<=degB,
M<--(domA/domB)*X^(degA)
A<--A-B*M
Q<--Q+M

Sorties: Q et A avec Q le quotient et A le reste

Il faut par ailleurs que je prouve la terminaison de l'algorithme cad qu'à partir d'un certain rang, degA>degB. Pour cela, je pensais justifier en disant que degA est une suite d'entiers strictement décroissante, alors que degB est constant. Donc forcément, degA>degB à partir d'un certain rang. Mais je ne suis pas très convaincu car degA peut très bien décroitre sans pour autant devenir inférieur à degB non?

Merci d'avance pour votre réponse!

Posté par
luzak
re : Algorithme division deux polynômes 09-04-17 à 12:34

Bonjour !
Tu démontres simplement que la suite (deg A) est strictement décroissante.  Pour une suite d'entiers la propriété (deg(A)<(deg B) sera atteinte en un nombre fini d'itérations.

Posté par
believesh
re : Algorithme division deux polynômes 09-04-17 à 12:51

Merci pour cette réponse rapide!Mon algorithme est donc correct?
Pour montrer que degA décroissante je propose ce raisonnement:

Il s'agit de montrer que deg(Ak+1)-deg(Ak)<=0

deg(Ak+1)=deg(Ak-B*Mk)
dc deg(Ak+1)<=max(deg(Ak);deg(BMk)

1er cas: max(deg(Ak);deg(BMk)=deg(Ak)
alors deg(Ak+1)-Ak<=0

2nd cas: max(deg(Ak);deg(BMk)=deg(BMk)

deg(Ak+1)-deg(Ak)<=deg(BMk)-deg(Ak) mais là je n'arrive pas à montrer que c'est inférieur  à 0 ... Faut-il écrire deg(BMk)=degB+deg(Mk)? Mais je trouve que cela ne mène à rien ...

Posté par
luzak
re : Algorithme division deux polynômes 09-04-17 à 15:08

Citation :

Il s'agit de montrer que deg(Ak+1)-deg(Ak)<=0

Non tu dois établir la décroissance stricte...

Il suffit de regarder le coefficient dominant du nouveau A (si tu préfères celui de A_{k+1} par rapport à celui de A_k).



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1741 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !