TP1 đ„ Calcul de racines
Une vidéo expliquant en détail le TP et fournissant quelques conseils est disponible en bas de page.
Un ordinateur, câest trĂšs rapide, mais pas trĂšs intelligent. On va en profiter pour lui faire calculer la racine carrĂ©e⊠de façon trĂšs bĂȘte.
Vous devez implĂ©menter deux mĂ©thodes de calcul « brutales » dâune racine carrĂ©e :
- une méthode par dichotomie (réduction d'un intervalle)
- une méthode chiffre par chiffre (par essais successifs)
Puis vous devrez :
- comparer ces méthodes à la fonction standard
math.sqrt()en termes de performance - étendre le calcul à une racine n-iÚme
Ă la fin de ce travail, vous serez capable de :
- Utiliser des variables, types de base, opérateurs et fonctions
- Utiliser des structures conditionnelles et expressions logiques
- Utiliser des structures répétitives
- Décomposer un algorithme en fonctions réutilisables
- Ăvaluer la performance dâun algorithme avec des mesures de temps
- Appliquer la logique pour résoudre un problÚme numérique complexe sans bibliothÚque
- Valider le fonctionnement de vos algorithmes Ă l'aide de jeux d'essais
âđ€ đ đ«
Si votre travail est suspecté de plagiat (code copié d'un.e autre étudiant.e, code généré par IA, notions non abordées en classe, etc.), deux choses peuvent se produire :
- Le plagiat est prouvé par nos outils : note de 0, automatiquement.
- Le plagiat est plutÎt évident, mais une validation est requise : vous serez convoqué(e) au bureau de votre enseignant(e). Vous devrez répondre à certaines questions pour prouver que vous comprenez et maßtrisez le code qui a été utilisé. Si vous ne réussissez pas à répondre à certaines questions, vous aurez la note de 0 (si vous ne comprenez pas votre propre code, c'est que vous avez plagié, d'une maniÚre ou d'une autre).
Votre enseignant a créé pour vous un dépÎt personnel, accessible seulement par vous.
Clonez-le et utilisez-le tout au long du TP : c'est ce dépÎt que votre enseignant récupérera pour la remise.
La structure du dossier :
âââ .gitignore # Fichiers Ă exclure des commits
âââ autocorrection.py # Script pour l'autocorrection de vos fonctions
âââ performance.py # Tests de performance des fonctions du module racine.py
âââ racine.py # Vos 2 fonctions de calcul de la racine carrĂ©e
âââ README.md # Documentation du projet
âââ requirements.txt # DĂ©pendances du projet
Les fichiers racine.py et performance.py sont ceux que vous devrez compléter.
Votre dépÎt de code ne doit contenir aucun autre fichier que les 6 fichiers fournis.
Le fichier requirements.txt contient la liste des bibliothÚques Python nécessaires à l'exécution de votre code.
Il vous permet d'installer rapidement toutes les dépendances requises pour le projet, en une seule commande.
Par exemple, une fois votre dépÎt de projet cloné, toutes les bibliothÚques nécessaires seront installées lors de la création de votre environnement virtuel Python (en cliquant sur le message en bleu) :

Ainsi, vous n'aurez pas Ă installer manuellement chaque bibliothĂšque.
Dans le script racine.py, vous devez créer 2 fonctions, soit une pour chacune des 2 méthodes du calcul de la racine carrée d'un nombre.
On cherche la racine dans un intervalle qui se réduit de moitié à chaque étape.
On commence par déterminer l'intervalle initial :
Par la suite, on va réduire l'intervalle de moitié de la maniÚre suivante :
- On calcule le milieu :
- Puis :
On rĂ©pĂšte l'opĂ©ration de rĂ©duction de l'intervalle jusqu'Ă ce que le critĂšre dâarrĂȘt soit atteint (voir ci-dessous).
đ CritĂšre dâarrĂȘtâ
On arrĂȘte lorsque les deux bornes donnent le mĂȘme rĂ©sultat, une fois arrondi Ă la prĂ©cision demandĂ©e.
Par exemple, si on veut dĂ©cimales, on arrĂȘte lorsque :
et ce résultat arrondi est la racine approximée.
Exemple (racine de , avec dĂ©cimales)â
On poursuit les itérations jusqu'à ce que :
Supposons quâon obtienne :
bas = 2.8284225463867188haut= 2.82843017578125
Alors :
round(2.828422..., 5) = 2.82842round(2.828430..., 5) = 2.82843
â On continue.
Plus tard :
bas = 2.8284263610839844haut= 2.82843017578125
Alors :
round(2.8284263..., 5) = 2.82843round(2.8284301..., 5) = 2.82843
â On peut donc arrĂȘter.
Résultat retourné : .
On construit le résultat décimale par décimale, en partant de la gauche vers la droite.
Supposons que nous cherchons la racine carrée de .
đ Partie entiĂšreâ
On commence par déterminer la partie entiÚre (à gauche de la virgule) de la racine carrée.
On fait des essais successifs pour trouver le plus grand entier dont le carré est inférieur ou égal à :
Puisque , on retient .
đ Ă cette Ă©tape, on sait que la racine est dans lâintervalle :
Donc, la racine de ressemble Ă point quelque chose (ex : ).
đą DĂ©cimalesâ
On va maintenant ajouter les décimales une à la fois.
PremiĂšre dĂ©cimaleâ
On teste les valeurs possibles :
Puisque , on retient .
đ On a maintenant :
DeuxiĂšme dĂ©cimaleâ
MĂȘme principe :
Puisque , on retient .
đ On a maintenant :
On rĂ©pĂšte ce processus pour chaque dĂ©cimale jusquâĂ atteindre la prĂ©cision souhaitĂ©e.
âïž Traduction en algorithmeâ
à chaque position décimale :
- On fixe les chiffres déjà trouvés
- On teste les chiffres de 0 Ă 9
- On garde le plus grand chiffre tel que :
đ Cela correspond directement Ă :
- une boucle sur les positions
- une boucle imbriquée sur les chiffres de 0 à 9
â Arrondi ou pas ?â
On retourne simplement la borne infĂ©rieure, câest-Ă -dire le plus grand nombre construit tel que :
đ On obtient donc une troncature Ă la prĂ©cision demandĂ©e.
Par exemple, si la vraie valeur est :
Avec une précision de 5 décimales, on retourne :
(et non ).
LES PARAMĂTRES
Ces deux fonctions doivent recevoir les deux paramĂštres suivants :
- Le nombre dont on souhaite calculer la racine
- Vous devez valider que ce nombre est supérieur ou égal à zéro.
- La précision souhaitée (ex. : 4 pour obtenir un maximum de 4 décimales) :
- Ce paramĂštre doit ĂȘtre facultatif (en configurant une valeur par dĂ©faut).
- Vous devez valider que la précision est comprise entre 1 et 10 décimales.
VALEUR RETOURN ĂE
Concernant les valeurs retournées par ces 2 fonctions :
- Elles doivent retourner simplement le résultat en format numérique, comme le fait
math.sqrt(). - Les fonctions ne doivent pas appeler la fonction
print. - Certaines racines n'ont pas de décimales ou en possÚdent peu :
- Exemple : La racine carrée de
9est3.0, peu importe la valeur de votre précision souhaitée. - Ne rajoutez pas de zéros inutiles à votre réponse.
- Exemple : La racine carrée de
RACINE PROPREVotre module racine doit contenir uniquement ces 2 fonctions et le bloc if __name__ == "__main__": fourni.
Aucune instruction ne doit ĂȘtre laissĂ©e Ă l'extĂ©rieur de ces 2 fonctions ou de ce bloc.
Vous pouvez mettre librement vos tests dans le bloc if __name__ == "__main__": :
- ils s'exécutent seulement quand vous lancez
racine.pydirectement (bouton « Run »); - ils ne s'exécutent pas quand le module est importé par
performance.pyouautocorrection.py.
if __name__ == "__main__":
# Vos tests ici, par exemple :
resultat = racine_dicho(2, 5)
print(resultat)
Vous devez exécuter fréquemment le script autocorrection.py.
Votre enseignant va se servir de ce script pour valider le bon fonctionnement de vos 2 fonctions.
Le script nécessite la bibliothÚque requests, qui est listée dans le fichier requirements.txt et donc installée lors de la création de votre environnement virtuel (au besoin, voir la procédure d'installation d'un package).
Cette bibliothÚque permet de télécharger des fichiers en ligne par programmation ; elle est utilisée ici pour vérifier si une nouvelle version du script est disponible et pour la télécharger automatiquement.
Limitations du script
Le script possÚde certaines limites et ne vérifie pas les points suivants :
- La cohérence de vos docstrings ainsi que la qualité du français.
- La présence de code inutile ou redondant à l'intérieur de vos fonctions.
- Le bon fonctionnement du script
performance.py.
Dans le script performance.py, vous allez comparer vos 2 fonctions du module racine avec la fonction math.sqrt() pour comparer leurs performances.
Pour chacune des 3 méthodes (fonction 1, fonction 2, math.sqrt()) vous devez :
- à l'aide d'une boucle, appeler la fonction 100 000 fois avec un nombre flottant aléatoire
- Utilisez un nombre flottant aléatoire différent à chaque appel
- Les nombres flottants gĂ©nĂ©rĂ©s doivent ĂȘtre compris entre 10 et 10 000
- Calculer le temps total nécessaire pour réaliser les 100 000 appels (en ms)
- Afficher :
- Le temps de calcul total pour les 100 000 appels (en millisecondes)
- Le temps moyen par appel de la fonction
Exemple d'affichage attendu (les valeurs sont fictives) :
Résultats des performances :
Méthode 1 (dichotomie) : Temps total = 50 ms, Temps moyen = 0.0005 ms
Méthode 2 (chiffre par chiffre) : Temps total = 150 ms, Temps moyen = 0.0015 ms
Méthode 3 (math.sqrt) : Temps total = 10 ms, Temps moyen = 0.0001 ms
Votre format d'affichage devrait ĂȘtre identique.
Le script doit s'éxécuter en moins de 60 secondes.
Vous devez transformer vos deux fonctions du module racine afin qu'elles puissent calculer la racine n-iĂšme d'un nombre.
Ajout d'un nouveau paramĂštre
- Ajoutez, Ă vos deux fonctions, un paramĂštre
degrecorrespondant Ă lâindice de la racine (2 pour une racine carrĂ©e, 3 pour une racine cubique, etc.). - Ce paramĂštre doit ĂȘtre optionnel et avoir la valeur 2 par dĂ©faut.
- L'ordre des paramĂštres doit ĂȘtre exactement le suivant (sans quoi l'autocorrection ne fonctionnera pas) :
- le nombre
- le degré de la racine
- la précision
RĂšgles de validation et logique
- Nombres négatifs
- Le calcul de la racine d'un nombre nĂ©gatif doit ĂȘtre possible uniquement si le degrĂ© est impair (ex. : la racine cubique de -27 est -3).
- Dans tous les autres cas, une exception doit ĂȘtre levĂ©e.
- Validation du degré
- La valeur du paramĂštre
degrene doit pas ĂȘtre infĂ©rieure Ă 1. - Vous devez valider la valeur passĂ©e en paramĂštre.
- La valeur du paramĂštre
Vérification du bon fonctionnement
- Le script
autocorrection.pyajustera les tests en conséquence dÚs qu'il détectera le paramÚtre supplémentaire dans vos fonctions.
Les docstrings doivent ĂȘtre rĂ©digĂ©es dans un français sans faute.
Elles doivent décrire clairement le rÎle de chaque fonction, ses paramÚtres, sa valeur de retour et les exceptions possibles.
Le projet fonctionne sans plantage et correctement, et le code est clair et facile à lire. Ce pointage fonctionne en négatif. Si le projet fonctionne correctement en tout temps, vous conservez votre note. Dans le cas contraire, vous perdez des points avec un maximum de 2.
- Plantage (un script qui plante lorsqu'on l'exécute) -1 point
- Code illisible (ex : noms de variables incompréhensibles, difficulté à comprendre le code) -1 point
- Information affichée incohérente -1 point
- Autre cas...
Vous pouvez commencer le TP dÚs la fin de la rencontre 4 : validation des paramÚtres, méthode par dichotomie (boucle while) et comparaison des performances (une boucle while avec un compteur suffit).
La méthode chiffre par chiffre nécessite les boucles imbriquées, vues à la rencontre 5.
La rencontre 6 est entiÚrement consacrée au travail sur le TP1.
Vous avez ensuite jusqu'Ă minuit, 6 jours aprĂšs cette rencontre, pour le remettre.
Votre enseignant.e récupérera automatiquement le code de votre dépÎt Git : vous n'avez rien d'autre à faire pour le remettre.