ALBATROS CONCEPT 
Accueil : Contact : Tarifs : Présentation
   Assistance informatique      Développement Web      Formation      Logiciels      Multimedia   
Texte si le navigateur ne supporte pas le HTML Canvas
Pseudo ou Email
Mot de passe
S'inscrire
Mot de passe perdu ? Email non reçu ?
Développeur web expert, PHP5, MySQL5, JavaScript, HTML5, LE MANS METROPÔLE
Sommaire.
Fiche complète et vérifiée

Version Math ML de cette fiche

Les Fractions, le PGCD, le PPCM et opérations sur les fractions

  1. Fractions
    Ce sont des opérations de divisions effectuées sur des nombres entiers relatifs.
    Dans la fraction 25÷12, 25 est appelé le Numérateur et 12 est le Dénominateur.
  2. Exemples
    • 26÷13
    • 2÷16
    • (-33)÷11
    • -(3)÷(-12)
  3. Simplification de fractions (Recherche du PGCD / PGDC)
    Il s'agit ici de déterminer si on peut simplifier une fraction en réduisant un maximum la valeur du numérateur et du dénominateur.
    Pour simplifier une fraction, il suffit de décomposer le numérateur et dénominateur en produits de nombres premiers, puis regrouper les sous-groupes de produits de facteurs communs afin de faire la simplification (cela revient à chercher le Plus Grand Commun Diviseur - PGCD ou PGDC ). Le résultat est alors la fraction simplifiée par ce PGCD (division du numérateur et du dénominateur par ce PGCD).

    Exemples:

    1. 156÷156, ici, le numérateur et dénominateur sont égaux, la solution vaut 1
    2. 750÷30
      • 750÷30=(2×3×5×5×5)÷(2×3×5)
      • 750÷30=(2×3×5)×(5×5)÷(2×3×5)
      • 750÷30=5×5×((2×3×5)÷(2×3×5))
      • 750÷30=25
      Ici, le PGCD est 2×3×5=30
    3. -147÷1155
      • -147÷1155=-(3×7×7)÷(3×5×7×11)
      • -147÷1155=-((3×7)×7)÷((3×7)×5×11)
      • -147÷1155=-(7÷(5×11)×((3×7)÷(3×7)))
      • -147÷1155=-7÷55
      Ici, le PGCD est 3×7=21
    4. 37÷1155 ?
      37 étant un nombre premier, il suffit alors de décomposer 1155 en produit de nombres premiers afin de voir si 37 en fait partie... finalement, non. Donc cette fraction n'est pas simplifiable.


  4. Recherche algorithmique de PGCD
    Les ordinateurs ne savent pas décomposer les nombres entiers en produits de facteurs premiers. Il savent encore moins trouver le PGCD de 2 nombres entiers. C'est pourquoi, il est intéressant de décrire des méthodes pour trouver le PGCD par des techniques ittératives (dont les opérations se répètent).

    Avant toute chose, il faut savoir que, pour un ordinateur, l'opération de division prend beaucoup plus de temps qu'une soustraction (ou différence). Sachez que, pour exécuter une multiplication sur 2 nombres entiers, il faut 9 fois plus de temps en moyenne, que pour effectuer une addition. Alors pour une division, sachant que l'ordinateur doit faire la conversion des nombres entiers en nombres à virgule pour ce faire, il faut au moins 15 fois plus de temps pour effectuer cette division que pour une soustraction!! Conclusion, il faut mieux effectuer une série de 10 soustractions ou additions que 2 divisions, qui prennent plus de temps... nous verrons plus bas qu'au niveau algorithmique, ce n'est pas vrai...

    1. Méthode d'Euclide 1
      Soit A et B, avec A>B, 2 nombres entiers dont on cherche le PGCD. On va nommer M le nombre le plus grand et m le nombre le plus petit.
      1. On fait l'opération M-m. On obtient le résultat R
      2. On renomme R en C et m en D. Et on compare C à D
      3. Si C=D, alors on a notre PGCD (C ou D), sinon, on nomme M le maximum de C et D et on nomme m le plus petit d'entre eux, puis on refait l'étape 1

      Démonstration
      Soit A et B 2 nombres entiers dont on sait que le PGCD est k (k>1). A s'écrit alors (i.k) et B s'écrit (j.k)
      Supposons A>B. Nommons M=A et m=B. Remarquons d'ores et déjà que A est le multiple de k le plus grand que l'on aura.
      1. M-m=(i-j).k.
        Soit R le résultat (R=(i-j).k).
        R est alors aussi multiple du PGCD (qui, nous le rappelons, est k)
      2. Renommons donc le m précédent en C et R en D
        • Si C=D alors, ça signifie que (i-j)=j, c'est à dire que i=2j, et donc, M=2m.
          Ainsi M= i.k = 2m = 2j.k
          Or, on a défini que k était le PGCD, donc, à cette étape, j=1, m (renommé C) est donc le PGCD
        • Si C ≠ D, alors on renomme le plus grand des 2 en M et le plus petit en m et on retourne à l'étape 1 de cette boucle.
      Il est important de remarquer qu'à chaque boucle, les coefficients i et j diminuent (puisqu'on ne garde que les 2 plus petits entiers) et donc, j se rapproche de plus en plus de la valeur 1.
      Le nombre maximum de boucles exécutées est forcément inférieur au i initial (A÷k). Le cas extrême étant celui où A=i×k et B=k avec i>2. Dans ce cas, il y aura i boucles effectuées.

      Fin de la démonstration...


      Exemple:
      Cherchez le PGCD de 715 et de 627.
      • On fait 715-627=88
      • Puis 627-88=539
      • Etc...
      • Puis 22-11=11
      • Puis 11-11=0
      11 est donc le PGCD de ces 2 nombres. Cette méthode demande beaucoup de calculs (16 itérations ici), c'est une méthode simple applicable dans le domaine informatique pour calculer le PGCD.

    2. Méthode d'Euclide 2
      Soit A et B, avec A>B, 2 nombres entiers dont dont cherche le PGCD. On va nommer M le nombre le plus grand et m le nombre le plus petit.
      1. On recherche le reste de la division entière M÷m. On obtient le reste R
      2. On renomme m en C et R en D.
      3. Si D=0, alors on a notre PGCD (C), sinon, on renomme C en M et D en m. Puis on refait l'étape 1

      Démonstration
      Cette démonstration reprend la même démarche que celle de la méthode d'Euclide 1.
      • Soit M=i.k et m=j.k, avec k le PGCD. On a ici, une série de divisions Euclidiennes (La division euclidienne est une division de nombres entiers)
      • A chaque boucle on a une division du style (M-R)÷m=Q. En effet, M=Q.m+R
      • De plus, M=i.k et donc, (Q.m)+R est multiple de k, soit Q.(j.k)+R=i.k
      • On cherche R. R=i.k-(Q.j).k
        R=(i-(Q.j)).k. R est donc multiple de k, R s'écrit donc r.k.
      • Donc, à chaque boucle, on a M, m et R multiples de k, avec R<=m
      • La suite de la démonstration coule de source... les dividendes et restes de la division diminuant jusqu'à ce qu'on ait un reste nul.
      Fin de la démonstration...

      Exemple:
      Cherchez le PGCD de 715 et de 627.
      • On fait reste de la division de 715÷627 : 88
      • Puis reste de 627÷88 : 11
      • Puis reste de 88÷11 : 0
      11 est donc le PGCD de ces 2 nombres. On a effectué ici 3 divisions entières ce qui représente au moins 45 cycles d'horloge au niveau microprocesseur, à comparer aux 16 de la méthode précédente. Voir plus bas pour la suite...
      Ecriture algorithmique (en langage C) des 2 méthodes

      Les théories sur les cycles d'horloges des microprocesseurs sont une chose. Le meilleur moyen de se faire une idée sur l'algorithme le plus rapide est encore de tester avec cette Application PHP qui vous montrera qu'en vérité, la dernière méthode d'Euclide est plus rapide que la; première!! Pourquoi ?

      Parce chaque boucle ne contient pas QUE l'opération de soustraction ou de division entière, mais également les instructions de test, d'affectations etc... Donc, si au départ, on comptait un cycle pour la soustration et qu'on compte 9 cycles pour les autres instructions, on aurait 10 cycles par boucle pour la première méthode. Pour la deuxième méthode, on aurait, disons, 25 cycles par boucle. Ce qui ne fait plus qu'un rapport de 2.5 pour entre les 2 méthode par boucle (à la faveur de la première). Si la première méthode d'Euclide nécessite 15 boucles pour trouver le PGCD, alors, on aurait 150 cycles d'horloge en tout. Pour la seconde méthode, on l'effectue en 3 boucles, ce qui fait 75 cycles d'horloge.

      Le gagnant est donc la deuxième méthode en ce qui concerne la vitesse d'exécution du calcul du PGCD. Evidemment tout ceci n''est qu'une estimation. Il convient de réajuster les chiffres, mais cela donne un ordre d'idée...

  5. Somme de 2 fractions
    Soit A÷B et C÷D, 2 fractions.
    On calcule la somme de 2 fractions par:
    (A÷B)+(C÷D)=((A×D)+(C×B))÷(B×D)
    En effet, pour pouvoir additionner les 2 membres du numérateur, il faut que ces 2 membres puissent être divisibles par un dénominateur commun.
    La différence se calcule pareillement, en remplaçant le signe "+" par le signe "-".

  6. Produit de 2 fractions
    Soit A÷B et C÷D, 2 fractions.
    On calcule le produit de 2 fractions par:
    (A÷B)×(C÷D)=(A×C)÷(B×D)

  7. Division de 2 fractions
    Soit A÷B et C÷D, 2 fractions.
    On calcule la division de 2 fractions par:
    • (A÷B)÷(C÷D)=(A÷B)×(D÷C) (Diviser par un nombre revient à multiplier par son inverse)
    • (A÷B)÷(C÷D)=(A×D)÷(B×C)

  8. Plus Petit Commun Multiple - PPCM ou PPMC
    En supplément du PGCD, on pourrait avoir besoin du PPMC pour, par exemple, trouver le diviseur commun lors de la somme de 2 fractions.
    Le PPCM est trouvé en effectuant le produit des 2 nombres et divisant par leur PGCD.
    En effet, soit k le PGCD de A et de B. A=k×m et B=k×n. Le plus grand multiple commun est le produit de l'ensemble des facteurs différents de A et B par leur PGCD, soit k×m×n. Or A×B=k×k×m×n, d'où, le PPMC est donné par A×B÷k.

    Exemple:
    Cherchez le PPCM de 715 et de 627.
    Il s'agit de l'exemple qu'on a eu précédemment dans la recherche du PGCD (Qui est 11).
    Il suffit alors d'effectuer le produit 715×627 et de diviser par le PGCD (11). Le résultat est 40755.

Liens directs

Valid CSS :: Valid XHTML
Copyright © 2011 par Albatros Concept
Maquette graphique par: GET CSS TEMPLATES modifiée par Albatros Concept