Aller au contenu principal

TP1 – Calcul de racines

🎯 Objectifs pédagogiques

À 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
  • Travailler avec des boucles, listes, tuples et dictionnaires
  • 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
🧠 Contexte

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 :

  1. Une méthode chiffre par chiffre, par essais successifs
  2. 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
  • Effectuer une extension vers le logarithme
Créer le projet

Pour faire ce TP, vous devez créer un projet PyCharm dans le répertoire GitHub Classroom créé pour vous par le prof.

2 points Répertoire Git
  • 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)
4 points 🔧 Calculer la racine carrée « à la main »

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.

➤ Méthode 1 : Chiffre par chiffre

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. Donc, la racine de 8 ressemble à 2.8...

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....

Et ainsi de suite pour les décimales suivantes.
On fait des essais successifs pour chaque décimale jusqu’à la précision désirée.

➤ Méthode 2 : Dichotomie

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.

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.

✅ Tests attendus

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
2 points 📈 Comparaison des performances

Vous allez comparer vos méthodes avec math.sqrt sur 10 000 nombres pseudo-aléatoires.
Pour y parvenir, vous devez :

  1. Générer une liste de 10 000 nombres flottants aléatoires entre 10 et 1000.
  2. 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()
  3. Afficher :
    • Le temps total (ms) pour chaque méthode
    • Le temps moyen par appel de fonction pour chaque méthode
2 points 🌱 Généraliser à une racine n-ième

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, en prenant base et nombre comme paramètres.

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.

Fonctionnement global 2 points négatifs

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...