Division euclidienne algorithme

OShine
OShine
dans Algèbre
Bonjour,

J'avoue ne pas réussir à comprendre cette algorithme. Il n'y a aucune explication dans mon livre, seulement un exemple de division euclidienne entre 2 polynômes.
Par ailleurs, à votre avis, est-ce facile de le programmer sur Python ? J'aimerais essayer dès lors que j'aurais compris l'algorithme.98012

Réponses

  • brian
    brian
    Hum, ça ne te rappelle pas un peu la division posée à l'école primaire ? Tu devrais peut-être prendre un polynôme $A$ de degré, disons, 3, un polynôme B de degré 1 ou 2 et te mettre à la place de l'ordinateur : tu effectues scrupuleusement l'algorithme avec le fameux outil papier-crayon. Ensuite, tu peux regarder ce qui se passe si le degré de $B$ est supérieur à celui de $A$.

    Quand tu auras vu comment ça marche, tu pourras démontrer :
    • que l'algorithme se termine en un nombre fini d'étapes (nombre vérifiant une certaine relation fonction des degrés des polynômes $A$ et $B$) ;
    • qu'il donne la réponse attendue.
    Pour cela, il est utile de trouver un « invariant de boucle » : une propriété intéressante qui est vraie à chaque étape au début de la boucle. Montrer que ladite propriété est vraie à chaque étape revient à faire une petite récurrence.
  • noobey
    noobey
    Division euclidienne de X^5 par X^2 + 1

    X^5 = X^3*(X^2 + 1) + R(X)
    R(X) = la différence = -X^3

    Ensuite
    -X^3 = -X(X^2 + 1) + R(X)
    R(X) = X

    Tu vois que :
    R(X) = le dernier terme = X
    Q(X) = somme des quotients = X^3 - X

    On peut vérifier : (X^3 - X)(X^2 + 1) + X = X^5
    A toi de jouer, en python c'est pas compliqué
  • OShine
    OShine
    Merci même si je n'ai pas trop compris comment démontrer qu'un algorithme fonctionne, je n'ai jamais fait ça. Pareil pour l'invariant de boucle, je n'ai jamais étudié ça.

    Si $\deg(n) < deg (p)$ il suffit de prendre $Q=0$ et $R=A$ on a bien $A=B \times 0 + A$ avec $\deg A < \deg B$

    Sinon j'ai réussi à comprendre le programme en posant la division euclidienne.

    J'ai pas envie de rentrer dans la théorie des algorithmes, ce qui m'intéresse c'est son application à Python.

    Je n'arrive pas avec mon programme Python, le $X^{n-p}$ me gêne je ne sais pas comment faire. Mon début de programme :
    def division_euclidienne(a,b):
r=a
q=0
n=len(r)-1
p=len(b)-1
while p=<n:
  q=q+(a[n]/b[p])*
  • raoul.S
    raoul.S
    ta variable q ne doit pas être un nombre mais une liste et le $\frac{a_n}{b_p}X^{n-p}$ représente le terme d'indice $n-p$ de ta liste.
  • noobey
    noobey
    En gros faut reprendre tes fonctions sommes et produits que tu as fait précédemment sur les polynomes...
  • OShine
    OShine
    Ah j'ai compris merci Noobey faut que je retape et réutilise mes fonctions somme et produit que j'ai étudiées hier soir.

    Ensuite j'ai plus qu'à les appeler pour faire la somme et le produit.
  • noobey
    noobey
    C'est ça la programmation. Tu fais des fonctions pour éviter de taper 50 fois la même chose
  • OShine
    OShine
    J'ai tenté un programme mais cela ne fonctionne pas :
    def somme(a,b):
  n_a=len(a)-1
  n_b=len(b)-1
  s=max(n_a+1,n_b+1)*[0]
  for i in range (n_a+1):
    s[ i] = a[ i]
  for i in range (n_b+1):
    s[ i] += b[ i]
  return s

def produit(a,b):
  n_a=len(a)-1
  n_b=len(b)-1
  p=(n_a+n_b+1)*[0]
  for i in range (n_a+1):
    for j in range(n_b+1):
      p[ i+j]+=a[ i]*b[j]

  return p

def division_euclidienne(a,b):
  q=n*[0]
  r=a
n=len(r)-1
p=len(b)-1
while p<=n :
  q=somme(q,(a[n]/b[p])*q[n-p])
  r=somme(r,produit((a[n]/b[p])*q[n-p],b))
  retunr (q,r)
  • noobey
    noobey
    Gros ta fonction somme marche pour 2 polynomes et tu l'appelles sur 1 nombre et un polynome
  • OShine
    OShine
    Pourtant j'ai défini $q$ et $b$ comme des polynômes.

    Python m'envoie un message d'erreur pour la commande 
    n=len(r)-1
    en disant que r n'est pas défini alors que je l'ai défini en posant r=a
  • Rescassol
    Rescassol
    Bonsoir,

    Tu n'as pas respecté l'indentation à partir de la ligne n=len(r) - 1.

    Cordialement,

    Rescassol
  • raoul.S
    raoul.S
    De plus c'est q=[0] et pas q=n*[0].

    Enfin noobey a raison si tu écris q=somme(q,(a[n]/b[p])*q[n-p]) tu fais la somme du polynôme q avec le nombre (a[n]/b[p])*q[n-p] ce qui ne vas pas fonctionner.
  • OShine
    OShine
    Donc je n'ai pas besoin de la fonction produit vu que je multiplie 2 scalaires ?
  • OShine
    OShine
    Mon souci se situe au niveau des commandes 
     q=somme(q,(a[n]/b[p])*q[n-p])
 r=somme((a[n]/b[p])*q[n-p],b))
    D'ailleurs Python me dit que c'est faux. Mais je ne vois pas comment faire avec le $X^{n-p}$
  • noobey
    noobey
    Je reitere. Ta fonction somme prend en arguments 2 polynomes (listes). Là le 2e argument est un nombre.
  • OShine
    OShine
    Je bute toujours, ce programme est un peu dur pour un débutant
    def somme(a,b):
  n_a=len(a)-1
  n_b=len(b)-1
  s=max(n_a+1,n_b+1)*[0]
  for i in range (n_a+1):
    s[ i] = a[ i]
  for i in range (n_b+1):
    s[ i] += b[ i]
  return s

def division_euclidienne(a,b):
  q=[0]
  r=a
  n=len(r)-1
  p=len(b)-1
  while p<=n :
    q=somme(q,(a[n]/b[p])*q)
    r=somme((a[n]/b[p])*q,b)
  retunr (q,r)

division_euclidienne([1,1,1],[2,6])

print (q,r)
  • Rescassol
    Rescassol
    Bonsoir,

    4*[0]. donne [0,0,0,0]. Que crois tu que peut faire (a[n]/b[p])*q surtout si (a[n]/b[p]) n'est pas entier ?
    Il faut te renseigner sur les array de numpy, ou faire des boucles indigestes.

    Cordialement,

    Rescassol
  • noobey
    noobey
    Non mais tu écris les instructions au hasard en pensant que ça va marcher c'est pas une question d'être débutant. T'es pas méthodique

    Commençons par Q.

    Q = Q + constante*X^(n-p)

    Il faut donc
    1) que tu définisses le polynome X^(n-p)
    2) que tu le multiplies avec ta constante. Pour rappel une constante est un polynome de degré....
    3) que tu additionnes avec Q

    Ensuite tu fais la meme pour R

    Et tu oublies pas dactualiser n à chaque étape
  • OShine
    OShine
    D'accord j'ai compris mais je ne vois pas comment définir $X^{n-p}$ sur Python.
  • raoul.S
    raoul.S
    $X^{n-p}$ est une liste python $[0,0,...,0,1]$ de longueur $n-p+1$.
  • raoul.S
    raoul.S
    tu peux la définir de façon concise comme ça :
    [1 if k==n-p else 0 for k in range(n-p+1)]
  • OShine
    OShine
    Merci la commande 
     X=(n-p)*[0]
  X.append(1)
    est-elle correcte ?
  • OShine
    OShine
    Bon je vais abandonner et me consacrer aux mathématiques.

    Je pense que ce programme est un peu trop dur par rapport à mes connaissances de Python. Il y a trop de choses que je ne maitrise pas comme multiplier un réel par une liste etc...

    C'est dommage que je perde des heures qui m'auraient permis d'avancer dans le programme de sup.

    Mais j'ai quand même appris des petites choses.
  • raoul.S
    raoul.S
    oui la commande :
    X=(n-p)*[0]
X.append(1)

    est correcte.
    OShine a écrit:
    Je pense que ce programme est un peu trop dur par rapport à mes connaissances de Python. Il y a trop de choses que je ne maitrise pas comme multiplier un réel par une liste etc...

    OK. Au cas où si tu reviens à Python il y a cette version en ligne qui te permet d'exécuter rapidement des scripts https://repl.it/languages/python3 (enfin si tu ne connaissais pas déjà...)
  • brian
    brian
    J'ajouterais qu'un outil très basique mais qui a fait ses preuves pour débuguer un programme consiste à utiliser print() pour contrôler qu'à chaque étape, les variables ou expressions importantes ont bien la valeur attendue par l'auteur du programme.
  • OShine
    OShine
    @RaoulS
    J'ai utilisé cette version mais j'ai toujours des erreurs c'est lassant.

    @Brian
    Oui j'essaie d'utiliser print souvent mais ici je me suis perdu avec $\dfrac{a_n}{b_p} X^{n-p} B$ que je n'ai pas réussi à programmer. Je n'ai rien trouvé sur google pour multiplier une liste par un réel non entier.
  • Rescassol
    Rescassol
    Bonjour,
    OShine a écrit:
    Je n'ai rien trouvé sur google pour multiplier une liste par un réel non entier.
    Moi a écrit:
    Il faut te renseigner sur les array de numpy, ou faire des boucles indigestes.
    Tu lis les réponses quelquefois ?

    Cordialement,

    Rescassol
  • Rescassol
    Rescassol
    Bonjour,

    Exemple: 
    import numpy as np

Tab=np.array([1,7,42])
print(Tab)
Tab2=2.5*Tab
print(Tab2)

    Cordialement,

    Rescassol
  • noobey
    noobey
    Sans parler de numpy array pour l'instant (alors que c'est aussi la base de python) 
    aP = []
for k in range(len(P))  :
    aP.append(a*P[k])

# mieux
aP = []
for x in P  :
    aP.append(a*x)

#encore mieux
aP = [a*x for x in P]
    PS : si tu veux faire de l'info va falloir être un peu autonome tu ne vas pas nous faire le coup de ce que tu fais déjà en maths "g jamé vu ca dan mon cour donc je sé pa fair", (comportement de collégien)
  • brian
    brian
    Numpy, c'est peut-être un peu compliqué pour OShine dans l'état actuel. Je propose une list comprehension : 
    >>> [ 4*x for x in [0, 5, 1, 2, 3] ]
[0, 20, 4, 8, 12]

    Edit : grillé par noobey.
  • OShine
    OShine
    @Noobey
    Oui vous avez raison mais je vais m'acheter un bouquin de Python pour justement poser moins de questions.
    Dans vos minis programmes je ne comprends pas la différence entre aP et P.

    @Brian
    Ah une commande qui a l'air facile à manipuler. J'avais cherché des trucs sur Numpy mais j'ai pas compris grand chose.
    Votre commande marche très bien 
    X= [ (2/3)*x for x in [0, 5, 1, 2, 3] ]
print(X)
    Ça m'affiche le bon résultat.
  • noobey
    noobey
    Je note P ton polynome et aP le polynome a*P (:P) (:P) (:P) (:P) (:P) (:P) (:P) (:P) (:P) (:P)

    C'est exactement le même programme que celui de Brian, sauf qu'il faut définir en amont P et a .....
  • OShine
    OShine
    Ok merci !
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 23

AleshaFin de partieRescassolbiguine_equationjean-éricpozzarshinitchi +16 Invités