Aller au contenu

Les algorithmes

Objectifs de la section

1-1 Notion de traitement automatique et d’algorithme
1-2 Identification des données disponibles et du résultat attendu
1-3 Techniques de décomposition d’un problème complexe en plusieurs sous-problèmes plus simples
1-6 Méthodes et séquence de développement d’un programme

Temps requis

30 minutes

Un algorithme est une séquence d'opérations pour effectuer un calcul ou produire un résultat. On peut exprimer un algorithme par le langage naturel, des langages visuels ou par langage de programmation.

On peut voir l'algorithme comme la structure d'un programme informatique. Vous avez vu plusieurs petits algorithmes depuis le début de la session, et même, dans d'autres sphères de votre vie. Un exemple d'algorithme dans la vie courante est une recette de cuisine : il s'agit d'une procédure à appliquer de façon méthodique.

Prenons l'exemple du problème suivant : on souhaite à partir de 3 points déterminer les angles intérieurs d'un triangle. Sur l'image ci-dessous, on connait l'information en bleu et l'on cherche l'information en vert.

Exemple du triangle pour lequel on cherche les angles

Si vous deviez résoudre ce problème sur une feuille de papier, vous pourriez par exemple calculer les vecteurs \(\overrightarrow{AB}\) et \(\overrightarrow{AC}\) puis utiliser les propriétés du produit scalaire pour calculer l'angle \(<\overrightarrow{AB}, \overrightarrow{AC}> = ||\overrightarrow{AB}|| \cdot ||\overrightarrow{AC}|| \cdot \cos(\alpha)\). On peut ensuite répéter cette méthode pour trouver \(\beta\) et \(\gamma\).

La démarche mathématique

Voici un exemple de démarche mathématique telle qu'elle serait réalisée à la mitaine pour calculer l'angle \(\alpha\).

Calcul des vecteurs

\[ \begin{align} \overrightarrow{AB} &= (1, 1) - (5, 5) = (-4, -4)\\ \overrightarrow{AC} &= (6, 1) - (5, 5) = (1, -4) \end{align} \]

Calcul des normes

\[ \begin{align} ||\overrightarrow{AB}|| &= \sqrt{(-4)^2 + (-4)^2} = \sqrt{32} \approx 5.66\\ ||\overrightarrow{AC}|| &= \sqrt{1^2 + (-4)^2} = \sqrt{17} \approx 4.12 \end{align} \]

Calcul de l'angle

\[ \begin{align} <\overrightarrow{AB}, \overrightarrow{AC}> &= ||\overrightarrow{AB}|| \cdot ||\overrightarrow{AC}|| \cdot \cos(\alpha)\\ \Rightarrow -4 \cdot 1 + -4 \cdot -4 &= 5.66 \cdot 4.14 \cdot \cos(\alpha)\\ \Rightarrow 12 &= 23.43 \cdot \cos(\alpha)\\ \Rightarrow \arccos(0.51) &= \alpha\\ \Rightarrow \alpha &= 59.34 \text{ degres } \approx 59.04 \text { degres } \end{align} \]

Une autre personne, toujours pour calculer les longueurs \(a\), \(b\) et \(c\) (qui sont respectivement les normes des vecteurs \(\overrightarrow{CB}\), \(\overrightarrow{AC}\) et \(\overrightarrow{AB}\)), ourrait plutôt choisir d'utiliser la loi des cosinus (\(a=\sqrt{b^2+c^2-2bc\cdot\cos(\alpha)}\)) pour trouver les angles.

La démarche mathématique

Voici un exemple de démarche mathématique telle qu'elle serait réalisée à la mitaine pour calculer l'angle \(\alpha\).

Calcul des vecteurs

\[ \begin{align} \overrightarrow{AB} &= (1, 1) - (5, 5) = (-4, -4)\\ \overrightarrow{AC} &= (6, 1) - (5, 5) = (1, -4)\\ \overrightarrow{BC} &= (6, 1) - (1, 1) = (5, 0)\\ \end{align} \]

Calcul des normes

\[ \begin{align} c = ||\overrightarrow{AB}|| &= \sqrt{(-4)^2 + (-4)^2} = \sqrt{32} \approx 5.66\\ b = ||\overrightarrow{AC}|| &= \sqrt{1^2 + (-4)^2} = \sqrt{17} \approx 4.12\\ a = ||\overrightarrow{BC}|| &= \sqrt{5^2 + 0^2} = \sqrt{25} = 5 \end{align} \]

Calcul de l'angle

\[ \begin{align} a=\sqrt{b^2+c^2-2bc\cdot\cos(\alpha)} \Rightarrow 5 &= \sqrt{\sqrt{17}^2 + \sqrt{32}^2 - 2 \cdot 5.66 \cdot 4.12 \cdot \cos(\alpha)}\\ \Rightarrow 25 &= 17 + 32 - 46.64 \cdot \cos(\alpha)\\ \Rightarrow \cos(\alpha) &= 0.51\\ \Rightarrow \alpha &= \arccos(0.51)\\ \Rightarrow \alpha &= 59.34 \text{ degres } \approx 59.04 \text { degres } \end{align} \]

Ce sont deux algorithmes différents qui permettent d'obtenir le même résultat. Exprimons ces algorithmes avec le langage clair.

Entrée : les 2 coordonnées des 3 points (6 nombres à virgules)
Sortie : affichage des trois angles

  1. Calculer le vecteur \(\overrightarrow{AB}\) et \(\overrightarrow{CB}\);
  2. Calculer la norme de \(\overrightarrow{AB}\) et de \(\overrightarrow{CB}\);
  3. Calculer l'angle \(\beta\) avec la formule du produit scalaire;
  4. Calculer le vecteur \(\overrightarrow{BA}\) et \(\overrightarrow{CA}\);
  5. Calculer la norme de \(\overrightarrow{BA}\) et de \(\overrightarrow{CA}\);
  6. Calculer l'angle \(\alpha\) avec la formule du produit scalaire;
  7. Calculer l'angle \(\gamma\) avec la formule \(\gamma = 180 - \alpha - \beta\);
  8. Afficher les 3 angles.

Entrée : les 2 coordonnées des 3 points (6 nombres à virgules)
Sortie : affichage des trois angles

  1. Calculer les vecteurs \(\overrightarrow{CB}\), \(\overrightarrow{AC}\) et \(\overrightarrow{AB}\);
  2. Calculer la norme de chaque vecteur pour obtenir les valeurs de \(a, b \text{ et } c\);
  3. Utiliser la loi des cosinus pour calculer \(\alpha\) et \(\beta\);
  4. Calculer l'angle \(\gamma\) avec la formule \(\gamma = 180 - \alpha - \beta\);
  5. Afficher les 3 angles.

On peut coder ces algorithmes avec Python maintenant, MAIS on peut aussi continuer de réfléchir avant de continuer et appliquer la règle d'or des programmeurs et programmeuses

Règle d'or de la programmation

Un bon programmeur, une bonne programmeuse agit de la façon la plus paresseuse possible !

Cette maxime de sagesse populaire (qu'il faut prendre avec un grain de sel) résume bien des règles importantes dans l'élaboration d'un bon code, soit qu'on évite de répéter du code. En effet, répéter le même code, en plus de nous prendre plus de temps à créer, peut amener les erreurs à se répéter.

Division de l'algorithme avec le produit scalaire

Concentrons-nous pour l'instant dans l'algorithme avec le produit scalaire et cherchons les opérations répétées :

  1. Calculer deux vecteurs à partir de quatre points;
  2. Calculer la norme d'un vecteur;
  3. Appliquer la formule du produit scalaire.

On va donc créer un algorithme spécifiquement pour trouver un angle à partir de quatre points que l'on va pouvoir appeler 2 fois. Dans le livre du cours, c'est ce qui est appelé sous-programme, mais nous utiliserons plutôt le terme fonction. À la page sur les fonctions, vous avez toutes les informations sur la syntaxe des fonctions.

Voici donc les algorithmes de ce programme.

Entrée : les coordonnées des extrémités des vecteurs.
Sortie : retourne la norme du vecteur sous forme d'un nombre à virugle.

  1. Calculer la coordonnée en X du vecteur;
  2. Calculer la coordonnée en Y du vecteur;
  3. Appliquer la formule de la norme;
  4. Retourner le résultat.

Entrée : les coordonnées des extrémités des deux vecteurs pour lesquels calculer le produit scalaire.
Sortie : retourne le produit scalaire des vecteurs sous forme d'un nombre à virugle.

  1. Calculer le produit scalaire;
  2. Retourner le produit scalaire.

Entrée : les coordonnées des trois points qui crée l'angle. L'angle calculé est celui du premier point.
Sortie : l'angle en degrée entre les deux vecteurs.

  1. Calculer la norme des deux vecteurs;
  2. Calculer le produit scalaire des deux vecteurs;
  3. Calculer l'angle avec la relation du produit scalaire;
  4. Retourner le résultat.

Entrée : les coordonnées des trois points qui forment le triangle. Sortie : affichage des trois angles.

  1. Calculer l'angle \(\alpha\);
  2. Calculer l'angle \(\beta\);
  3. Calculer l'angle \(\gamma\) avec la formule \(\gamma = 180 - \alpha - \beta\);
  4. Afficher les 3 angles.
Programme avec l'algorithme du produit scalaire
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
from numpy import sqrt, arccos, rad2deg


def calculer_norme(x1, y1, x2, y2):
    norme = sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
    return norme


def calculer_produit_scalaire(xu1, yu1, xu2, yu2, xv1, yv1, xv2, yv2):
    xu = xu2 - xu1
    yu = yu2 - yu1
    xv = xv2 - xv1
    yv = yv2 - yv1

    produit_scalaire = xu * xv + yu * yv
    return produit_scalaire


def calculer_angle(ax, ay, bx, by, cx, cy):
    norme_ab = calculer_norme(ax, ay, bx, by)
    norme_ac = calculer_norme(ax, ay, cx, cy)
    produit_scalaire = calculer_produit_scalaire(ax, ay, bx, by, ax, ay, cx, cy)

    # Calcul de l'angle avec la relation entre le produit scalaire et les normes
    cos_angle = produit_scalaire / (norme_ab * norme_ac)
    angle = rad2deg(arccos(cos_angle))

    return angle


def afficher_angles_triangle(ax, ay, bx, by, cx, cy):
    angle_alpha = calculer_angle(ax, ay, bx, by, cx, cy)
    angle_beta = calculer_angle(bx, by, ax, ay, cx, cy)
    angle_gamma = 180 - angle_alpha - angle_beta

    print(f"Les angles sont alpha={angle_alpha:.2f}, beta={angle_beta:.2f} et gamma={angle_gamma:.2f}.")


if __name__ == "__main__":
    afficher_angles_triangle(1, 1, 5, 5, 6, 1)

Télécharger le code complet avec la documentation

Division de l'algorithme avec la loi des cosinus

Reportons-nous maintenant à l'algorithme avec la loi des cosinus et cherchons les opérations répétées :

  1. Calculer la norme de chaque vecteur à partir de ces coordonnées;
  2. Appliquer la formule de la loi des cosinus.

Nous allons pouvoir réutiliser la fonction calculer_norme de la précédente démonstration, car elle répond toujours à nos besoins.

Voici donc les algorithmes de ce programme.

Entrée : les coordonnées des extrémités des vecteurs.
Sortie : retourne la norme du vecteur sous forme d'un nombre à virugle.

  1. Calculer la coordonnée en X du vecteur;
  2. Calculer la coordonnée en Y du vecteur;
  3. Appliquer la formule de la norme;
  4. Retourner le résultat.

Entrée : les coordonnées des trois côté du triangle. L'angle calculé est celui opposé au premier point.
Sortie : l'angle opposé au premier côté en degrées.

  1. Appliquer la formule de la lois des cosinus pour calculer l'angle;
  2. Retourner le résultat.

Entrée : les coordonnées des trois points qui forment le triangle.
Sortie : affichage des trois angles.

  1. Calculer l'angle \(\alpha\);
  2. Calculer l'angle \(\beta\);
  3. Calculer l'angle \(\gamma\) avec la formule \(\gamma = 180 - \alpha - \beta\);
  4. Afficher les 3 angles.
Programme avec l'algorithme de la loi des cosinus
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from numpy import sqrt, arccos, rad2deg


def calculer_norme(x1, y1, x2, y2):
    norme = sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
    return norme


def calculer_angle(a, b, c):
    cosinus_angle = (a**2 - b**2 - c**2) / (-2*b*c)
    angle = rad2deg(arccos(cosinus_angle))
    return angle


def afficher_angles_triangle(ax, ay, bx, by, cx, cy):
    # Longueur des côtés
    cote_a = calculer_norme(bx, by, cx, cy)
    cote_b = calculer_norme(ax, ay, cx, cy)
    cote_c = calculer_norme(ax, ay, bx, by)

    angle_alpha = calculer_angle(cote_a, cote_b, cote_c)
    angle_beta = calculer_angle(cote_b, cote_c, cote_a)
    angle_gamma = 180 - angle_alpha - angle_beta

    print(f"Les angles sont alpha={angle_alpha:.2f}, beta={angle_beta:.2f} et gamma={angle_gamma:.2f}.")


if __name__ == "__main__":
    afficher_angles_triangle(5, 5, 1, 1, 6, 1)

Télécharger le code complet avec la documentation

Gabarits de travail

Les gabarits suivants sont utilisés pour aider à structurer les algorithmes.

Gabarit de planification
Gabarit de planification (avec consigne)
Exemple du gabarit de planification avec le problème des trois angles