Série 4

Dans cette série, nous allons regarder comment utiliser des classes pour mémoriser des informations dans le but d'implémenter efficacement diverses fonctions. Dans le premier exercice, nous nous intéresserons à la suite de Fibonacci, dans le second aux nombres premiers.

Exercice 1

Dans ce premier exercice, nous allons nous intéresser à la suite de Fibonacci. La suite de Fibonacci est une suite de nombres entiers définie de manière inductive comme suit :

\[ \begin{aligned} F_0 &:= 0\\ F_1 &:= 1\\ F_{n + 2} &:= F_n + F_{n + 1} \end{aligned} \]

Les deux premiers éléments de la suite sont définis comme 0 et 1, et les suivants sont obtenus en additionant les deux nombres qui les précédent.

La suite de Fibonacci est liée de façon intéressante au nombre d'or et apparaît naturellement dans de nombreuses structures biologiques. La suite a aussi de nombreuses applications en mathématiques et même en informatique.

Le but de ce premier exercice est d'implémenter la suite de Fibanocci dans Python.

Partie 1 - Version naïve

La suite de Fibonacci peut être écrite de manière très simple en utilisant le principe recursivité, comme suit :

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

Copiez le code dans un fichier Python (ou directement dans la console Python). Essayez ensuite d'appeler la fonction fibonacci avec différents arguments : 5, 10, 20, 30, 40. Qu'observez-vous ?

Question : Comment expliquez-vous le phénomène observé ?

Indice : Pour mieux comprendre le phénomène, vous pouvez ajouter une instruction print dans le corps de la fonction afin d'observer les appels récursifs.

def fibonacci(n):
    print("fibonacci({})".format(n))
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

Partie 2 - Version efficace

L'implémentation de la fonction fibonacci dans la partie 1 est malheureusement assez peu efficace. En effet, cette version fait de nombreux appels récursifs, et par conséquent de nombreux index doivent être calculés à de multiples reprises. Par exemple, pour calculer fibonacci(10), les appels suivants sont effectués :

Question : Qu'observez-vous ?

Retenir la suite en mémoire

Pour éviter ce problème, nous allons utiliser une liste pour mémoriser les éléments de la suite. Cette liste sera stockée et maintenue par une classe que l'on appelera Fibonacci. Cette classe offrira une méthode element pour accéder à un élément de la liste en fonction de son index.

Dans un premier temps, copiez le code suivant, qui contient le squelette de la classe :

class Fibonacci(object):

    def __init__(self): 
        pass

    def element(self, n):
        pass

Le constructeur

L'unique fonction du constructeur de la classe Fibonacci est d'initialiser la liste self.suite qui contiendra la suite de Fibonacci. Initialement, on remplira cette liste avec les deux premiers éléments de la suite uniquement.

Implémentez le constructeur de la classe Fibonacci.

La méthode element

La méthode element sert à accéder à un élément de la suite en fonction de son index n. En théorie, il suffit simplement de se référer à la liste self.suite.

Cependant, il se peut que la liste self.suite ne contiennent pas assez d'éléments au moment de l'appel. Dans ce cas, il faut compléter la liste jusqu'à ce sa taille soit suffisante pour que l'index demandé soit dans la liste. Pour compléter la liste, on utilise la relation :

\[ F_{n + 2} := F_n + F_{n + 1} \]

Implémentez la méthode element.

Tester la performance

Après avoir implémenté puis testé la classe Fibonacci, comparez la performance de la méthode element par rapport à la version proposée dans la première partie.

Exercice 2

Le but de ce second exercice est de concevoir une classe appelée Premiers. Le but de cette classe est de fournir une méthode est_premier qui retourne True quand on lui passe un nombre premier et False autrement. La technique à utiliser pour implémenter cette classe se base sur le crible d'Ératosthène.

Cet exercice est beaucoup moins guidé que le précédent. Nous vous invitons à consulter la page Wikipédia pour en apprendre plus sur la technique. À noter qu'il est tout à fait acceptable dans le cadre de cet exercice d'exiger un nombre maximum en argument au constructeur de la classe Premiers, ce qui simplifie grandement l'exercice.

Exercice 3

En vous inspirant de l'exercice 2, concevez une classe Irreductibles qui offre une méthode est_irreductible qui prend en argument un nombre entier et retourne True si et seulement si ce nombre représente un polynôme irreductible sur \(GF(2)[X]\). Pour ce faire, adaptez le crible d'Ératosthène aux opérations de \(GF(2)[X]\). Pour simplifier cette classe, vous pouvez y prendre comme argument un degré maximum à considérer pour les polynômes.