Bienvenue dans la dernière étape du projet !
Dans cette dernière étape, nous allons implémenter une classe appelée AnneauPolynome qui modélise l'anneau des polynômes sur un corps donné.
Le corps que nous utiliserons au final sera celui implémenté hier, et plus précisément \(\mathbf{F}_{256}\), mais le code que nous allons écrire sera paramètrique sur le corps.
Copiez le code suivant et collez-le dans le fichier galois.py.
Le code contient un squelette à compléter pour la classe AnneauPolynome, ainsi que la classe Correcteur qui est donnée complète.
class AnneauPolynome(object):
def __init__(self, corps):
self.corps = corps
def fois(self, p, q):
r = [0] * (len(p) + len(q) - 1)
# À compléter
def reste_division(self, p, q):
if len(q) == 0:
raise ZeroDivisionError()
# À compléter
def generateur(self, n):
# À compléter
pass
class Correcteur(object):
def __init__(self, n_extra, p):
self.anneau = AnneauPolynome(CorpsGalois(p))
self.generateur = self.anneau.generateur(n_extra)
def encode(self, donnees):
avec_extra = donnees + [0] * (len(self.generateur) - 1)
return self.anneau.reste_division(avec_extra, self.generateur)La classe AnneauPolynome contient trois méthodes à compléter:
fois, qui calcule la multiplication de polynômes,reste_division, qui calcule le reste de la division d'un polynôme par un autre polynôme,generateur, qui calcule un polynôme appelé générateur.Le constructeur de la classe est déjà donné.
La classe AnneauPolynome manipule des polynômes aux coefficients issus d'un corps passé en paramètre au constructeur.
Ces polynômes sont représentés par des listes, chaque élément de la liste représentant un coefficient. Les coefficients sont donnés du plus haut degré au plus petit.
Le tableau suivant présente quelques exemples de polynômes et leur représentation sous forme de liste.
| Polynôme | Liste |
|---|---|
| \(0\) | [] |
| \(1\) | [1] |
| \(x\) | [1, 0] |
| \(x^2 + 3 x + 2\) | [1, 3, 2] |
Attention, on peut aussi parfois avoir des valeurs nulles en tête de liste. Par exemple, la liste [0, 1] correspond au polynôme \(1\), tout comme la liste [1] ou la liste [0, 0, 0, 0, 0, 1].
Vu que les listes contiennent les coefficients de polynômes du plus haut degré au plus petit, l'index de la liste ne correspond pas directement au degré du coefficient. Par exemple, étant donné une liste p représentant un polynôme, l'index 0 représente le plus haut degré, alors que le dernier index (len(p) - 1) représente les unités.
La première méthode à implémenter est la méthode fois.
La méthode prend comme arguments deux polynômes (sous forme de liste) et retourne leur produit (toujours sous forme de liste).
Le code donné suggère de commencer par définir une liste r pour représenter le résultat.
La liste r qui représente le polynôme est de taille suffisante pour stocker tous les coefficients du produit.
Initiallement, chaque coefficient du polynôme est à 0.
L'idée est d'ensuite modifier les coefficients de ce polynôme r dans la méthode.
Pour ce faire, il suffit de parcourir toutes les combinaisons de degré des deux polynômes.
Pour chaque combinaison, on ajoute au coefficient adéquat du polynôme r le produit des coefficients du premier polynôme et du second polynôme.
Pour effectuer des additions ou multiplications sur les coefficients, n'oubliez pas d'utiliser les méthodes de self.corps.
L'opération suivante à implémenter est reste_division, qui calcule le reste de la division de deux polynômes: un polynôme dividende p et un polynôme diviseur q.
Le résultat à retourner est un polynôme représenté par une liste de taille exactement len(q) - 1, et ce même si le degré du polynôme représenté est plus bas.
Le code proposé gère le cas où le diviseur q est nul.
Dans cette situation une exception ZeroDivisionError est lancée.
Le code à compléter commence après ce bloc conditionnel.
L'idée pour calculer le reste de la division polynomiale est assez simple. On procéde de manière itérative : Tant que le dividende p a un degré \(d_p\) supérieur ou égal au degré \(d_q\) du diviseur q, on cherche à trouver un multiple du diviseur q tel que:
Étant donné un tel polynôme multiple de q, on pourrait ensuite soustraire du dividende p ce multiple du diviseur q.
De la sorte, le coefficient au degré \(d_p\) passera à 0, et donc le degré du dividende diminuera.
À chaque itération, pour trouver le multiple du diviseur q en question, on cherche un facteur \(n\) tel que le polynôme \(n \cdot \texttt{q} \cdot x^{d_p - d_q}\) a comme coefficient au degré \(d_p\) le même que \(q\). Pour trouver \(n\), il suffit de diviser le coefficient du degré le plus élevé du dividende p par le coefficient du degré le plus élevé du diviseur q.
self.corps.q qui représente le diviseur ne contient pas d'éléments nuls.xs en utilisant l'instruction xs = xs[1:] ou encore xs.pop(0). Cette opération peut être effectuée pour diminuer la longueur d'une liste qui représente un polynôme, notamment quand le coefficient de degré le plus élévé est à 0.reste_division s'attend à ce que la liste retournée en résultat soit de longueur len(q) - 1 exactement. Si vous retirez les zéros en tête de liste du résultat de manière trop zélée, il se peut que vous retiriez trop d'éléments.Finalement, il reste une unique méthode à implémenter avant la fin du projet: generateur. Cette méthode calcule un polynôme appelé générateur. Étant donné un nombre \(n\), ce polynôme correspond au produit \(\prod_{i=0}^{n-1} (x + 2^i)\), c'est-à-dire \((x + 2^0) \cdot (x + 2^1) \cdot \ldots \cdot (x + 2^{n - 1})\).
self.corps pour calculer les puissances de 2 à l'intérieur du corps.Dans le fichier test.py du projet vous trouverez les tests qui sont fournis pour les différentes étape.
Un test est bout de code qui fait appel à du code que vous avez écrit et qui teste son comportement.
Les tests généralement ne peuvent pas s'assurer que le code est entièrement correct, mais s'ils sont correctement écrits ils aident généralement à déceler des erreurs en pratique.
Testing shows the presence, not the absence of bugs.
Pour l'étape 5, la classe de test (Etape5) est vide. Vous pouvez la remplacer par le code ci-dessous.
class Etape5(unittest.TestCase):
def test_anneau_mult(self):
import galois
anneau = galois.AnneauPolynome(galois.CorpsGalois(285))
in_outs = [
(([], []), []),
(([1], []), []),
(([], [1]), []),
(([1], [1]), [1]),
(([3], [3]), [5]),
(([3], [2]), [6]),
(([1, 3], [4, 5]), [4, 9, 15]),
]
for (a, b), r in in_outs:
self.assertEqual(anneau.fois(a, b), r,
"La multiplication des polynômes {} et {} "
"ne donne pas le résultat attendu".format(a, b))
def test_reste_division(self):
import galois
anneau = galois.AnneauPolynome(galois.CorpsGalois(285))
in_outs = [
(([], [1]), []),
(([1], [1]), []),
(([1], [2]), []),
(([1, 1, 1, 1, 1], [1, 1, 1, 1]), [0, 0, 1]),
(([45, 12, 17], [34, 22]), [181]),
]
for (a, b), r in in_outs:
self.assertEqual(anneau.reste_division(a, b), r,
"La division des polynômes {} par {} "
"ne donne pas le reste attendu".format(a, b))
def test_generateur(self):
import galois
anneau = galois.AnneauPolynome(galois.CorpsGalois(285))
in_outs = [
(2, [1, 3, 2]),
(7, [1, 127, 122, 154, 164, 11, 68, 117]),
(10, [1, 216, 194, 159, 111, 199, 94, 95, 113, 157, 193]),
(13, [1, 137, 73, 227, 17, 177, 17, 52, 13, 46, 43, 83, 132, 120]),
(17, [1, 119, 66, 83, 120, 119, 22, 197, 83, 249, 41, 143, 134, 85, 53, 125, 99, 79]),
]
for i, r in in_outs:
self.assertEqual(anneau.generateur(i), r,
"Le générateur {} n'est pas le bon".format(i))Ce code teste :
AnneauPolynome,AnneauPolynome, et enfinAnneauPolynome.Une fois que vous avez placé cette classe dans test.py, vous pouvez exécuter la commande suivante depuis le dossier du projet pour vérifier si vous avez bien implémenté les fonctionnalités attendues à cette étape :
python -m unittest test.Etape5Alternativement, vous pouvez ouvrir le fichier test.py depuis IDLE et lancer l'exécution depuis Run > Run Module.
Vous pouvez désormais utiliser votre programme pour générer des QR codes contenant les chaînes de caractères que vous désirez (pour peu qu'elles ne soient pas trop longues !). Par exemple :
python generer-qr.py 'Terminé !'Depuis IDLE, il vous faudra ouvrir le script generer-qr.py puis exécuter Run > Run … Customized. Dans l'argument, vous pouvez entrer la chaine à encoder, entourée de simple guillemets.
Tout d'abord, félicitation d'avoir complété le projet ! S'il vous reste du temps, ou si vous souhaitez continuer ce projet par vous-même, n'hésitez pas à contacter l'enseignant, qui se fera une joie de vous guider.
Parmi les améliorations possibles au projet: