Aller au contenu

Activité 1 - Algorithmie

Tous les TP seront notés (barème indicatif).

  • Tout TP non rendu avant la fin de la séance sera noté zéro.
  • Veuillez mettre clairement vos noms sur votre code source ou noms de fichiers.

Assertions en Python.

L'instruction assert permet de vérifier qu'une instruction Python renvoie bien le bon résultat

Par exemple si je souhaite vérifier que ma fonction somme renvoie bien le bon résultat :

def somme(a, b):
    return a + b

Je peux ajouter ces assertions :

assert somme(2, 3) == 5
assert somme(-2, 3) == 1

Si l'assertion est vérifiée alors aucune erreur n'est retournée, sinon une erreur est retournée :

Traceback (most recent call last):
  File "<input>", line 4, in <module>
AssertionError

Pour chacun des exercices ci-dessous vous devez créer des fonctions.

Exercice 1 (6 points)

  • Implémentez en Python le pseudo code suivant :
Factorielle
------------------------------
entrée : un entier n
sortie : n factorielle
------------------------------
 n_factorielle  ← 1
 Pour i allant de 1 à n
     n_factorielle  ← n_factorielle * i

 Sortir : n_factorielle

Exercice 2 (6 points)

  • Ecrivez le code Python qui permet de renvoyer le maximum d'une liste.
  • Testez à l'aide d'assertions le cas où la liste ne contient que des valeurs négatives.

Exercice 3 (8 points)

Nous allons nous intéresser à la suite de fibonacci : https://fr.wikipedia.org/wiki/Suite_de_Fibonacci

La suite de Fibonacci est définie par la relation de récurrence :

\(F_{n} = F_{n-1} + F_{n-2}\)

Le nième terme s'obtient donc en calculant la somme des deux termes précédents.

Les premiers termes de la suite :

F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610

On a par exemple \(F_{5} = F_{4} + F_{3} = 3 + 2 = 5\)

  • Compléter le code ci-dessous pour renvoyer la nième valeur de la suite de Fibonacci :
def fibo(n):
    """Calcule le nième terme de la Suite de Fibonacci"""
    if n == 0:
        return #COMPLETER_ICI
    else:
        f0, f1 = #COMPLETER_ICI
        # Initialisation
        fn_precedent = f0
        fn_suivant = f1
        for k in range(1, #COMPLETER_ICI):
            # Somme des deux termes précédents
            somme_tmp = fn_precedent + fn_suivant
            # On passe au terme suivant
            fn_precedent = #COMPLETER_ICI
            # ON réactualise le terme suivant avec la somme des deux termes précédents
            fn_suivant =  #COMPLETER_ICI
        return fn_suivant

Une autre manière de développer cette fonction, consiste à calculer les termes de la suite de manière récursive :

def fibo_rec(n):
    """Suite de Fibonacci version récursive"""
    # Cas de base (sinon la fonction ne s'arrête jamais)
    if n == 0 or n == 1:
        return n
    else:
        return fibo_rec(n - 2) + fibo_rec(n - 1)

Vous constaterez qu'on appelle la fonction fibo_rec dans sa définition.

Afin de comparer l’efficacité de ces deux fonctions Python, on peut mesurer leur temps d’exécution en fonction de la taille des données. Le module timeit de Python permet de faire cela.

Par exemple, pour afficher le temps d’exécution de 50 appels à la fonction fibo avec l'argument 3, on entre le script suivant :

import matplotlib.pyplot as plt
import timeit

temps_execution = timeit.timeit('fibo(3)', number=50, globals=globals())
print(temps_execution)

Dans le script suivant, nous définissions un tableau des abscisses correspondant aux différentes valeurs de \(n\) pour lesquelles nous calculons les termes de la suite de Fibonacci pour \(n\) allant de 0 à 24.

abscisses = [k for k in range(0, 25)]
ordonnees_rec = []
ordonnees_iter = []
for x in abscisses:
    ordonnees_iter.append(timeit.timeit(
        'fibo(x)', number=100, globals=globals()))
    ordonnees_rec.append(timeit.timeit(
        'fibo_rec(x)', number=100, globals=globals()))
plt.plot(abscisses, ordonnees_iter, 'b')
plt.plot(abscisses, ordonnees_rec, 'r')
plt.show()

Exécutez ce code et observez l'allure des deux courbes.

Pour mieux observer l'allure de la courbe bleue nous allons augmenter le nombre de valeurs calculées pour la fonction non récursive et n'afficher qu'une seule courbe :

abscisses = [k for k in range(0, 1000)]
ordonnees_iter = []
for x in abscisses:
    ordonnees_iter.append(timeit.timeit(
        'fibo(x)', number=100, globals=globals()))

plt.plot(abscisses, ordonnees_iter, 'b')
plt.show()

Exécutez ce code et observez l'allure de cette courbe.

  • Décrivez (dans un commentaire à l'intérieur du fichier contenant votre code ) et interprétez (formulez une hypothèse) l'allure de la courbe bleue et celle de la courbe rouge.
"""
    J'observe que bla bla

    Signé John McNugget / étudiant expert en NSI
"""

  • Faites des recherches sur internet et essayez de comprendre et d'expliquer ce qu'il se passe dans la mémoire vive de l'ordinateur lorsque l'on exécute la fonction Fibonacci récursive.

  • Si vous avez trouvé des informations concernant la complexité algorithmique de ces deux fonctions alors ajoutez un commentaire à ce sujet.

    image