Dans cette vidéo pédagogique, le présentateur explique comment calculer la racine carrée d’un nombre réel positif en utilisant la méthode de dichotomie (bisection). Après avoir rappelé le principe général de la recherche dichotomique, il montre comment appliquer cette technique à la fonction f(a)=a²‑x pour trouver √x. Il souligne la nécessité d’introduire une tolérance (précision) afin d’éviter les boucles infinies lorsque la racine n’est pas exacte, et décrit le critère d’arrêt |M²‑nbr| ≤ pr. Le discours détaille les variables nécessaires (nbr, pr, vmin, vmax, M) et le choix de la structure itérative, privilégiant une boucle « Répéter » qui, en Python, se traduit par un while True avec une condition de sortie. Le pseudo‑algorithme est présenté, puis implémenté en Python : initialisation des bornes, calcul du milieu, mise à jour de l’intervalle selon le signe de M²‑nbr, vérification de la précision et sortie de la boucle. Des exemples concrets (√16, √11, √2, √25) illustrent le fonctionnement et la précision obtenue, avec des remarques sur l’ajustement de la tolérance ou l’arrondi du résultat. La vidéo se conclut par un rappel des résultats et une invitation à poursuivre l’apprentissage.
Chapters
Bonjour à tous et bienvenue dans cette nouvelle vidéo d'algorithmique où nous allons traiter l'exercice suivant: Proposer un algorithme qui permet de calculer la racine carrée d'un nombre réel positif par dichotomie. Nous avons déjà vu dans un exercice précédent comment trouver un élément dans un tableau en procédant à la recherche par dichotomie. Le principe consiste à chercher l'élément en réduisant l'intervalle de la recherche de moitié à chaque itération. Cette méthode permet de trouver l'élément beaucoup plus rapidement que si l'on procède à la manière classique de balayage du tableau entier élément par élément. Dans cet exercice aussi, on procédera de la même manière. En effet, on sait tous que la racine carrée d'un nombre réel positif est un nombre a qui lorsqu'il est élevé au carré donnera x. Autrement dit, l'écriture racine carrée de x vaut a est équivalente à a au carré vaut x. Il existe plusieurs méthodes qui permettent de calculer la racine carrée d'un nombre. La plus célèbre consiste à y procéder par dichotomie. Imaginons que l'on souhaite calculer la racine carrée du nombre 16. Pour simplifier, nous allons dire que la racine carrée de 16 est comprise dans l'intervalle situé entre 0 et 16. Et comme nous l'avons fait dans l'exercice de la recherche dichotomique dans un tableau, on va calculer la valeur du milieu qui est 16+ 0 divisé par 2, ce qui donne 8. Maintenant, on calcule le carré du nombre 8 qui vaut 64. Puisque 64 est supérieur au nombre 16 dont on veut calculer la racine carrée, alors on peut en déduire que cette racine est située dans la première moitié de l'intervalle, c'est-à-dire entre 0 et 8. On procède encore au calcul de la valeur du milieu de cet intervalle-là qui vaut 8+ 0 divisé par 2, ce qui donne 4. On élève 4 au carré et on obtient 16. Ce résultat correspond parfaitement au nombre initial dont on cherche à calculer la racine carrée. Par conséquent, la racine carrée de 16 vaut 4. Or, si par exemple on cherche à calculer la racine carrée de 11, la méthode énoncée ne trouvera aucun nombre exact dont le carré vaut 11, ce qui risque de faire tourner l'algorithme à l'infini. La solution consiste donc à spécifier la tolérance ou la précision qui nous convient dans une situation donnée. Autrement dit, si la différence entre le nombre 11 et le carré du nombre du milieu de l'intervalle est inférieure ou égale à la précision, alors on estime que c'est ce nombre-là qui est la racine carrée de 11. Pour être plus méthodique, supposons que la précision voulue vaut 0,5. Alors, on commence par calculer la valeur du milieu du premier intervalle qui vaut 11+ 0 divisé par 2, ce qui donne 5,5. On calcule ensuite le carré de 5,5, ce qui donne 30,25. Ce nombre-là est supérieur à 11. En plus, la différence entre 30,25 et le nombre 11 est supérieure à la précision qui vaut 0,5. Donc, on estime que la racine carrée du nombre 11 est comprise entre 0 et 5,5. On recalcule l'intervalle du milieu qui vaut dans ce cas / 2, ce qui donne 2,75. On élève ce nombre-là au carré, ce qui donne 7,56. Puisque ce nombre est inférieur à 11, et en plus la différence entre 11 et 7,56 est supérieure à la précision 0,5, alors on peut en déduire que la racine carrée de 11 est située entre 2,75 et 5,5. On recalcule l'intervalle du milieu, on refait le même traitement et à chaque fois on vérifie si la différence entre 11 et le carré de la valeur du milieu de l'intervalle est inférieure à 0,5. Si c'est le cas, alors c'est la valeur du milieu de l'intervalle courant qui représente la racine carrée la plus proche du nombre 11. Sinon, on recommence le même traitement. Il est clair que l'on va encore une fois recourir à une structure itérative, et vu que le nombre d'itérations à exécuter est incertain, alors on peut exclure la boucle Pour. Il nous reste les 2 boucles TantQue et Répéter. En fait, les 2 structures peuvent être utilisées, mais il y a quand même un certain avantage en faveur de la structure Répéter vu la nature du traitement. Dans notre cas, nous allons écrire l'algorithme avec la boucle Répéter, mais puisque le langage Python ne dispose pas de cette structure, alors on va écrire le programme avec la boucle TantQue ou While. Dans cet algorithme, nous aurons besoin des variables suivantes: nbr représente le nombre dont on cherche à calculer la racine carrée, Pr qui représente la précision voulue, Vmin et Vmax qui représentent respectivement le début et la fin de l'intervalle pour le calcul. Au début Vmin sera initialisé avec la valeur 0 et Vmax avec la valeur nbr, et M qui représente la valeur du milieu de l'intervalle. Toutes ces variables seront de type réel. Je propose l'algorithme suivant: On commence par demander à l'utilisateur de saisir le nombre dont on veut calculer la racine carrée. La valeur de ce nombre-là est ensuite stockée dans la variable nbr. Cette opération est placée dans la structure Répéter qui exécutera le traitement jusqu'à ce que l'utilisateur saisisse un nombre positif. Après, on demande à l'utilisateur de spécifier la précision voulue. Cette valeur est stockée dans la variable pr. Ensuite, on initialise les variables vmin et vmax qui indiquent les extrémités de l'intervalle de calcul. On affecte 0 à la variable vmin et nbr à la variable Vmax. Le traitement principal de notre algorithme consiste au calcul de la racine carrée du nombre entré par dichotomie. Justement, ce traitement est assuré à l'aide de la structure Répéter qui va tourner jusqu'à ce que la différence entre le carré de la valeur du milieu et le nombre entré par l'utilisateur soit inférieur ou égal à la précision spécifiée. Remarquez l'utilisation de la fonction Abs qui permet de calculer la valeur absolue de cette différence afin d'éviter les valeurs négatives. Notez que cette fonction est présente dans quasiment tous les langages de programmation, mais avec une syntaxe qui peut être différente. Dans la boucle, on calcule la valeur du milieu de l'intervalle que l'on stocke dans la variable M. Ensuite, on vérifie si le carré de cette valeur est supérieur au nombre nbr. Si c'est le cas, alors la valeur de la racine carrée que l'on cherche à calculer est forcément inférieure à la valeur du milieu calculée précédemment. Donc, on réduit l'intervalle en affectant à la variable Vmax la valeur de M. La variable vmin reste inchangée dans ce cas. Sinon, c'est-à-dire si le carré de la valeur du milieu est inférieur à nbr, dans ce cas on sait que la racine carrée recherchée est supérieure à la valeur du milieu calculée précédemment. Alors, on affecte à la variable vmin la valeur de la variable m et on maintient la valeur de la variable vmax telle qu'elle est. Le fait de sortir de la boucle signifie que la racine carrée du nombre nbr a été calculée avec la précision spécifiée par la valeur pr. On affiche donc un message qui indique cette racine carrée. Maintenant, on passe à l'implémentation de notre algorithme à l'aide du langage de programmation Python. Pour faire simple, je vais fixer la valeur de nbr et per de manière statique. On prendra par exemple nbr égal à 16, c'est-à-dire que l'on veut calculer la racine carrée de 16, et la précision égale 0,001 par exemple. Ensuite, on va initialiser les variables vmin et vmax qui représentent les extrémités de l'intervalle. vmin égale à 0 et vmax vaut nbr. Ensuite, on procède à la structure itérative qui va faire le traitement. Comme je l'ai mentionné, le langage Python ne dispose pas de la structure répéter, donc on va remplacer cette structure-là par while ou bien tant que. While True, c'est une boucle infinie qui va s'exécuter de manière indéfinie, mais bien sûr on va intercaler une clause afin de sortir prématurément de cette boucle. Alors on calcule la valeur du milieu qui vaut Vmax+ Vmin divisé par 2, puis on va énoncer la condition. Alors si M² est supérieur à nbr, dans ce cas on va réduire l'intervalle en affectant à Vmax la valeur de M. Sinon, dans ce cas c'est à vmin que l'on va affecter le m. Maintenant on va vérifier la condition de sortie pour voir si la différence entre le carré calculé et le nombre nbr est inférieur à la précision. Donc si la valeur absolue de la différence entre le m² et nbr est inférieure ou égale à pr, Dans ce cas, on sort de la boucle. Il nous reste maintenant à afficher le résultat à l'écran. Donc la racine carrée de nbr vaut m. Exécutons. Donc là, ça nous affiche la racine carrée de 16 vaut 4. On va essayer par exemple le nombre 2. Donc là c'est 1,41. Le nombre 25, donc c'est 4,999 etc. Donc en fait c'est presque 5. En réalité on sait que la racine carrée de 25 vaut 5, mais vu l'approche que nous avons suivie, c'est une approximation de ce nombre-là qui a été calculée à l'aide de l'algorithme. Et pour éviter ce genre de problème, vous avez le choix entre augmenter la précision, c'est-à-dire réduire la valeur de la variable PR, ou ou bien arrondir carrément le résultat obtenu après 3 ou bien 4 chiffres après la virgule. J'espère que vous avez apprécié cet exercice. Merci pour votre attention et à la vidéo prochaine.
