Division euclidienne

Martial
Martial
dans Fondements et Logique
Bonjour à tous,
Je sais pertinemment que ce sujet relève davantage de la pédagogie que de la logique, mais je remercie les modérateurs de ne pas le déplacer de façon à ce que Christophe puisse y répondre, car il a toujours plein d'idées dans ce domaine.

Voilà mon problème : comme tout le monde j'enseigne à distance. Hélas je ne peux pas faire de visioconf car j'ai des groupes de 32. Certains le font en audio, mais ils reconnaissent eux-mêmes que c'est pas facile à gérer. Du coup j'utilise le sous-forum "Enseignement à distance", que les administrateurs de ce forum ont eu l'idée géniale de créer, et que je remercie encore à cette occasion. Les étudiants peuvent donc poser des questions directement sur le forum (bon, apparemment ils ne s'en servent pas beaucoup) et ensuite ils m'envoient leurs résultats ou leurs DMs (et bientôt leurs DSs) par mail.
Les deux dernières semaine en 1ère année d'IUT on a fait l'intégration par parties, ce qui ne pose pas de problème particulier, il suffit de bien détailler deux exemples, et ensuite exos avec corrigé partiel.
Mais si on veut avancer un peu il faut que la semaine prochaine je leur explique la division euclidienne des polynômes, et éventuellement aussi la division selon les puissances croissantes. C'est trivial à faire en live, mais comment rédiger ça en LaTeX ? Pour bien faire il faudrait mettre des couleurs, entourer certains coefficients et mettre des flèches dans tous les sens, sur un ou deux exemples, pour que l'étudiant comprenne bien la démarche... et je ne sais pas faire ça.
Quelqu'un aurait-il connaissance d'un tel document déjà existant sur la toile ?
Quelqu'un a-t-il une idée ?
Evidemment on pourrait tout écrire en français du genre tu mets le machin sous le bidule et tu le soustrais du truc, mais ça prendrait des siècles et l'étudiant s'endormirait dès la page 2.
Merci d'avance
Martial

Réponses

  • GaBuZoMeu
    GaBuZoMeu
    Leur demander de faire un programme (en python, s'ils font du python) pour la division euclidienne des polynômes, représentés par la liste de leurs coefficients ?
    Premier sous-programme : retourner le degré (indice du dernier coefficient non nul).
    Coeur de l'algorithme : tant que le degré du dividende est plus grand que celui du diviseur, tuer le terme de plus haut degré du dividende.
  • Martial
    Martial
    @GBZM : Merci pour l'idée.
    Mais hélas, ils font du python, et pas moi... Et je n'ai pas l'intention de m'y mettre maintenant, je pars à la retraite le 1er septembre, et j'ai déjà assez de boulot comme ça avec la settheory.
    Mais je vais en parler au collègue qui leur enseigne le python.
    Ce qui serait bien c'est d'arriver à leur expliquer ça à la main, et qu'ensuite ils vérifient leurs calculs en python.
    Le collègue a fait ça avec les exos de calculs de primitives et d'IPP, et apparemment ça a bien marché. Quand ils ne trouvent pas pareil, en général l'erreur vient plus du côté des maths que de l'algorithme.

    D'autres idées ?
  • christophe c
    christophe c
    Personnellement, je ne parle de division euclidienne qu'en conclusion. En effet, de mon point de vue, c'est un outil trompeur car cache qu'il a été implémenté en hardware pour optimiser les vitesses d'exécution.

    La THEORIE NON OPTIMISEE, qui "suppose un ordinateur magique qui exécute tout en 0 seconde et qui n'existe pas me parait plus amusante et cinématographique à évoquer devant des jeunes sur ce thème:

    Dans le cas de la division euclidienne des entiers, ça donne:

    DivEucli(a,b) := if a<b then (0,a) else let (q,r) = DivEucli(a-b,b) in (q+1, r)

    Dans le cas des polynômes, ça donne :

    DiVP(P,Q) := if deg(Q)>deg(P) then (0,P) else let d:= f(P,Q) in DivP(P-X^dQ, Q)

    etc. Où $f(P,Q):=deg(P)-deg(Q)$

    edit:

    DivP(P,Q):= if $deg(P)<deg(Q)$ then $(0,P)$ else
    let $d:= deg(P)-deg(Q)$ in
    let $k:= cd(P)/cd(Q)$ in
    let $(A,B) := DiVP(P-kX^dQ,Q)$ in
    $(A + kX^d, B)$





    Ce sont des programmes d'une ligne, tu peux leur demander de jouer avec quelques jours, d'autant qu'ils illustrent la commodité des appels récursifs. Sachant que "une sale mode pédago" (sauf erreur sur les infos que j'ai) a tendance à "trop critiquer" la récursivité, lui donnant une sous-exposition dans le supérieur cycle 1 (L1L2 en gros).
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • GaBuZoMeu
    GaBuZoMeu
    christophe écrivait:

    DiVP(P,Q) := if deg(Q)>deg(P) then (0,P) else let d:= f(P,Q) in $DivP(P-X^dQ, Q)$

    Ça ne marche que si $P$ et $Q$ ont même coefficient dominant. Et, en corrigeant ça, quelle est la différence avec ce que j'écrivais dans mon premier message ?
  • christophe c
    christophe c
    ola oui merci pour la coquille, j'édite...

    Je n'avais pas lu ton msg, mais tu t'exprimais en français disons. Sinon, j'en ai profité pour caser mon habituel "lune" (optimisation qui rend moins facile), mais de toute façon, mea culpa, j'ai un peu été hors-sujet sur ce coup puisque je pensais au calcul du pgcd (où on présente la division euclidienne comme une sous-routine donnée).
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • christophe c
    christophe c
    Pour les lecteurs, je précise ce que j'appelle "ma lune":

    [size=x-small]Premier(n):= let b:= true in
    Begin
    for i:=2 to n-1 do if divisible(n,i) then b:=false else NeRienFaire done
    Renvoyer b
    end

    est la programmation "idéale" sur une machine idéale d'une fonction qui teste si un nombre entier $>1$ est premier.

    La fonction suivante, optimisée est souvent enseignée:

    Premier(n):= let b:= true in let i:=2 in
    while ($i\times i<n+1$ and $b$)
    do
    if divisible(n,i) then b:=false else NeRienFaire;
    i:=i+1
    end
    Renvoyer b
    end    [/size]

    Pour le motif qu'elle s'exécute plus vite.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Dom
    Dom
    Sarcasme :
    « Je n'avais pas lu ton msg, mais tu t'exprimais en français disons.»

    La connerie quoi ;-) s’exprimer en français ;-)
  • Martial
    Martial
    Pour revenir au sujet initial : quelqu'un a une idée ?

    Je précise qu'en dehors du python j'aimerais que mes étudiants sachent faire une division euclidienne à la main, dans des cas simples, par exemple lors d'un DS (même à distance, mais chronométré).
  • Martial
    Martial
    @Dom : j'espère que tout le monde aura apprécié à sa juste valeur à quel point ton dernier message a fait avancer le schilimimi, lol.

    Tu me diras, on peut dire la même chose de celui-ci...
  • raoul.S
    raoul.S
    Martial a écrit:
    Hélas je ne peux pas faire de visioconf car j'ai des groupes de 32

    Pour info Zoom cloud meetings est assez efficace pour des visioconférences à plusieurs (jusqu'à 100 personnes). Il y a une offre gratuite et une payante à 15$/mois.
  • Martial
    Martial
    Merci raoul.S
    Mais je voudrais simplement une solution simple.
    Comment présenter un document expliquant la div eucl en latex ?
    Ça existe, ou ça n'existe pas ?
  • Félix
    Félix
    Bonjour Martial,

    On peut trouver ça sur le net, en bas de la page 27 :

    http://www.lamacs.fr/documents/programmation/latex/Tutorial_Latex.pdf

    Cordialement.
  • Martial
    Martial
    Merci bien, Félix, ça va peut-être m'aider.
    Cordialement
    Martial
  • christophe c
    christophe c
    @Martial, tu poses la question très générale des définitions récursives (au sens informatique) me semble-t-il !
    J'ai utilisé la syntaxe caml, mais si tu veux, je peux te traduire ça en le langage que tu veux ?

    D'une manière générale, je crois qu'il faut absolument comprendre que l'informatique n'est pas les maths et que la récursivité "bouclante" est un BIENFAIT non un danger qu'il faut fuir. Et plus tôt les enfants et étudiants en entendent parler, à mon avis, mieux c'est.

    Je rappelle que l'implémentation en langage machine de la récursivité NE COUTE RIEN. Elle est donc "naturelle" si j'ose dire, ce n'est pas un outil artificiel.
    Par exemple la définition $f(x):=g(f(h(x)), f(k(x))$
    s'implémente comme suit (l'argument ou les arguments** sont sur la pile, un appel de fonction les aspire et renvoie le résultat). 
    [b]Fonction f :[/b] 
[b][color=#0033FF]Begin 
pop a
push a
call h
call f 
pop b
push a
call k
call f
push b
call g
End[/color][/b]
    ** raison pour laquelle ce qui compte, MAIS c'est très important mais cela seul compte, l'arité des fonctions doit être fixe.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Foys
    Foys
    christophe c a écrit:
    Je rappelle que l'implémentation en langage machine de la récursivité NE COUTE RIEN
    Il faut pouvoir faire des copies (de "a" en l'espèce). C'est untruc que tu rappelles parfois en plus.
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • christophe c
    christophe c
    Ah oui bien sûr, foys. Ce que je voulais dire était que la mise dans un compilateur du pouvoir de définir récursivement dans le langage qu'il compile ne pose aucun souci, on n'est pas devant un outil sophistiqué.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • ev
    ev
    Sobre pas de flèche ni de couleur (avec)
    \usepackage{array} 
    \begin{array}{rcrcrcrc|c}
   X^3 &+&        & & X   &+& 1     & & X + 1       \\ \cline{9-9}
 -(X^3 &+& X^2)   & &     & &       & & X^2 - X + 2 \\ \cline{1-3}
       & & -X^2   &+& X   & &       & &             \\
       & & -(-X^2 &-& X)  & &       & &             \\ \cline{3-5}
       & &        & & 2X  &+& 1     & & \\
       & &        & &-(2X &+& 2)    & & \\ \cline{5-7}
       & &        & &     & & -1    & &
 \end{array}
    On a donc: $X^3+X+1= ({X+1})({X^2 - X + 2}) -1$ et $\deg({-1}) =0 < \deg({X+1})=1$.

    e.v.
    Personne n'a raison contre un enfant qui pleure.


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 19

FoysHéhéhébiguine_equationchristianmosellei.zitoussi +14 Invités