TP1 🥕 Calcul de racines
🏗️ en construction 🏗
À 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
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 chiffre par chiffre, par essais successifs
- Une méthode par dichotomie (recherche binaire)
Puis vous devrez :
- Comparer ces méthodes à la fonction standard
math.sqrt
- Étendre le calcul à une racine n-ième
Pour faire ce TP, vous devez créer un projet PyCharm dans le répertoire GitHub Classroom créé pour vous par le prof.
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).
- Au moins 5 commits de tailles comparables (il n'y a pas un commit avec tout dedans et les autres vides)
- Au moins 1 commit par semaine
- Les commits décrivent l'avancement du projet dans un français sans faute (voir instructions)
- Les fonctions doivent être documetées dans un français sans faute : description de la fonction, paramètres, limites et exceptions possibles
Voici 2 méthodes brutes pour calculer la racine carrée d'un nombre.
Pour les décrire, supposons que nous cherchons la racine carrée de 8.
On construit le résultat décimale par décimale, en commençant par la plus grande.
Pour 8, on commence donc par l'unité :
- 0² = 0
- 1² = 1
- 2² = 4
- 3² = 9
Comme 8 est entre 4 et 9, on sait que la racine de 8 est entre 2 et 3, car 3² est plus grand que 8. Donc, la racine de 8 ressemble à 2 point quelque chose (ex : 2.0..., 2.1..., ..., 2.9...).
On passe à la première décimale :
- 2.0² = 4
- 2.1² = 4.41
- 2.2² = 4.84
- 2.3² = 5.29
- 2.4² = 5.76
- 2.5² = 6.25
- 2.6² = 6.76
- 2.7² = 7.29
- 2.8² = 7.84
- 2.9² = 8.41
La racine de 8 ressemble donc à 2.8...., car 2.9² est plus grand que 8.
Et on fait ainsi de suite pour les décimales suivantes.
On fait des essais successifs pour chaque décimale jusqu’à la précision désirée.
On cherche dans un intervalle [bas, haut] qui se réduit de moitié à chaque étape :
Début : [0, 8] → milieu = 4 → 4² = 16 → trop grand
→ nouvel intervalle [0, 4] → milieu = 2 → 2² = 4 → trop petit
→ nouvel intervalle [2, 4] → etc.
On continue ainsi jusqu'à la précision désirée.
Comment savoir qu'on a atteint la précision désirée?
Il faut regarder la différence entre les 2 intervalles (haut et bas).
Si elle est inférieure à la précision souhaitée, on peut alors considérer qu'on a suffisamment réduit l'intervalle et qu'on a trouvé la réponse.
La réponse recherchée sera alors la moyenne entre les 2 intervalles.
Exemple
Si on souhaite 2 décimales de précision,
on devrait alors arrêter quand la différence entre les 2 intervalles est inférieure à 0.001
Début : [0, 8] → 8 - 0 = 8 ... c'est > 0.001 → on continue ...
nouvel intervalle [0, 4] → 4 - 0 = 4 ... c'est > 0.001 → on continue
nouvel intervalle [2, 4] → 4 - 2 = 2 ... c'est > 0.001 → on continue
...
nouvel intervalle [2.828125, 2.8291015625] →
2.8291015625 - 2.828125 = 0.0009765625... c'est < 0.001 → on arrête
La réponse est la moyenne des 2 intervalles qu'on arrondie à 2 décimales.
Pour chacune des deux méthodes, vous devez créer une fonction qui prendra un nombre en paramètre et renverra la racine carrée de ce nombre en utilisant cette méthode, avec une précision de 0.001.
Pour chacune des 2 méthodes, affichez le résultat des appels suivants :
print(nom_de_la_fonction(0))
print(nom_de_la_fonction(0.1))
print(nom_de_la_fonction(0.2))
print(nom_de_la_fonction(0.9))
print(nom_de_la_fonction(8))
print(nom_de_la_fonction(9))
print(nom_de_la_fonction(81))
print(nom_de_la_fonction(123))
print(nom_de_la_fonction(-3)) # Doit lever une exception
Vous allez comparer vos méthodes avec math.sqrt
sur 10 000 nombres pseudo-aléatoires. Pour y parvenir, vous devez :
- À l'aide d'une boucle, générez 10 000 nombres flottants aléatoires entre 10 et 1000.
- Chronométrer le temps pour :
- Calculer toutes les racines avec votre première fonction
- Calculer les racines avec votre deuxième fonction
- Calculer les racines avec
math.sqrt()
- Afficher :
- Le temps total (ms) pour chaque méthode
- Le temps moyen par appel de fonction pour chaque méthode
Pour chacune de vos 2 fonctions, faites-en une copie et généralisez-la pour qu'elle calcule la
racine n-ième d'un nombre.
Vous devez rajouter un paramètre base
(ex. : 2 pour racine carrée, 3 pour racine cubique, etc.).
Il suffit ensuite de faire un changement minime aux 2 algorithmes pour calculer n'importe quelle racine n-ième.
Appelez chacune de ces 2 nouvelles fonctions et affichez les résultats pour la racine carrée, cubique et quatrième de 8, 9, 81 et 123.
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 -1 point
- Code illisible -1 point
- Information affichée incohérente -1 point
- Autre cas...