Feuille d’exercices 5 – avancé

Feuille d’exercices 5 – avancé#

Objectifs

  • Introduction à Sagemath

  • Calcul exact : entiers, rationnels, complexes

  • Notions sur le calcul symbolique

  • Notion de méthode et de classe

Avertissement

Ces exercices sont prévus pour les étudiant·e·s ayant déjà réussi la feuille d’exercices « classiques ».

Exercice 6. Entiers de Gauss#

Un entier de Gauss est un nombre complexe de la forme \(a + ib\) avec \((a, b) \in \mathbb{Z}^2\). On peut vérifier que l’ensemble des entiers de Gauss forme un anneau (avec les opérations usuelles d’addition et de multiplication sur les complexes), que l’on note \(\mathbb{Z}[i]\).

Question 1. Écrire une fonction est_entier_de_gauss(z) qui prend en entrée un nombre complexe z, et qui teste si z est un entier de Gauss. La fonction retournera la valeur logique associée.

# Votre réponse ici

Étant donné un nombre complexe \(z \in \mathbb{C}\), on peut calculer son arrondi dans les entiers de Gauss, en arrondissant des parties réelles et imaginaires. Par exemple, \(z = \frac{1}{4} - \frac{5}{3}i\) a pour arrondi \(-2i\) dans les entiers de Gauss.

Question 2. Écrire une fonction arrondi_de_gauss(z) qui prend en entrée un nombre complexe z, et qui retourne l’arrondi de z dans les entiers de Gauss.

# Votre réponse ici

Question 3. Une fois votre fonction arrondi_de_gauss bien programmée (et testée), exécuter la fonction affiche_arrondi() écrite ci-dessous, puis observer le résultat. À quoi correspond géométriquement l’arrondi de Gauss ?

def affiche_arrondi():
    Z = [1 + I,  7/6 - (3/2)*I, 3/4 + 2*I, -I-12/5]
    arrZ = [ arrondi_de_gauss(z) for z in Z ]
    P = list_plot(Z, color="blue", marker='o', size=35) + list_plot(arrZ, color="red", marker='*', size=40)
    P.show(gridlines=True, xmin=-3, xmax=3, ymin=-3, ymax=3)

# affiche_arrondi()

On peut démontrer que l’anneau des entiers de Gauss est euclidien, autrement dit, qu’il admet une division euclidienne. Cette division (avec reste) est définie de la sorte : si \(a\) et \(b\) sont deux entiers de Gauss, alors le quotient \(q\) de la division euclidienne de \(a\) par \(b\) est l’arrondi du complexe \(a/b\). Le reste de la division est alors \(r = a - bq\).

Par exemple, le quotient et le reste de la division euclidienne de \(a = 8 - 3i\) par \(b = 3 + 2i\) sont \(q = 1-2i\) et \(r = 1+i\), car \(\frac{a}{b} = \frac{18}{13} -\frac{25}{13}i\).

Question 5. Écrire une fonction quotient_gauss(a, b) qui prend en entrée deux nombres complexes a et b, et qui retourne le quotient de la division euclidienne (dans \(\mathbb{Z}[i]\)) de a par b.

# Votre réponse ici

Question 6. Écrire une fonction reste_gauss(a, b) qui prend en entrée deux nombres complexes a et b, et qui retourne le reste de la division euclidienne (dans \(\mathbb{Z}[i]\)) de a par b.

# Votre réponse ici

Question 7. Testez vos fonctions quotient_gauss(a, b)et reste_gauss(a, b) avec les paires d’entiers de Gauss suivantes :

  • \((a, b) = (5 + 2i, 3-4i)\), pour laquelle vous devriez obtienir un quotient \(q = i\) et un reste \(r = 1-i\) ;

  • \((a, b) = (5, 2+i)\), pour laquelle vous devriez obtienir un quotient \(q = 2-i\) et un reste \(r = 0\).

Remarque : suivant ce que vous avez écrit pour les fonctions précédentes, vous pourriez avoir besoin de faire une coercion de l’entier \(5\) vers les complexes.

# Votre réponse ici

Enfin, le pgcd de deux entiers de Gauss se calcule par l’algorithme d’Euclide, comme pour des entiers de \(\mathbb{Z}\). La seule différence est une étape de normalisation pour obtenir un pgcd dans le quadrant supérieur droit du plan complexe (c’est-à-dire, on veut que le pgcd ait une partie réelle strictement positive et une partie imaginaire positive).

L’algorithme est donc le suivant :

  • Tant que \(b \ne 0\):

    • Calculer \(q\) et \(r\) le quotient et le reste de la division euclidienne de \(a\) par \(b\)

    • Remplacer \(a\) par \(b\) et \(b\) par \(r\)

  • Multiplier \(a\) par \(1\), \(-1\), \(i\) ou \(-i\), afin que \({\rm Re}(a) \ge 1\) et \({\rm Im}(a) \ge 0\)

  • Retourner \(a\)

Question 8. Écrire une fonction pgcd_gauss(a, b) qui prend en entrée deux nombres complexes a et b, et qui retourne le pgcd (dans \(\mathbb{Z}[i]\)) de a et b.

Exemple (pour tester) : \({\rm pgcd}(3+i, 3-i) = 1+i\) et \({\rm pgcd}(47+29i,-11+23i) = 7i+1\).

# Votre réponse ici

Exercice 7. Crible d’Eratosthène#

Le crible d’Ératosthène permet d’obtenir la liste des nombres premiers entre \(0\) et \(N-1\), pour un certain entier \(N \ge 1\). L’idée du crible est la suivante :

  • On initialise une liste T de longueur N, qui ne contient que des valeurs booléennes égales à True. La liste T a pour vocation de savoir quels sont les nombres premiers. Le but est qu’à la fin de l’algorithme, T[i] vaut True si i est un nombre premier.

  • On affecte à T[0] et T[1] la valeur False (ce ne sont pas des nombres premiers).

  • Ensuite, on parcourt la liste de l’indice \(i = 2\) à \(N-1\). Pour chaque valeur de \(i\), si T[i] est vrai, alors on modifie T[j] en False pour tous les \(j > i\) tels que \(i\) divise \(j\). La raison est la suivante : comme \(i\) divise strictement \(j\), l’entier \(j\) ne peut pas être premier.

  • On retourne la liste des indices \(i\) tels que T[i] vaut True.

Pour plus de détails sur le fonctionnement du crible, voir par exemple la page wikipedia :

https://fr.wikipedia.org/wiki/Crible_d’Ératosthène

Dans cet exercice, on n’utilisera donc pas la méthode is_prime(), acr le but est d’implanter par soi-même une fonction qui liste des nombres premiers.

Question 1 : Écrire une fonction initialiser_tableau(N) qui retourne une liste de longueur \(N\) ne comportant que la valeur True.

# Votre réponse ici

Question 2 : Écrire une fonction eliminer_diviseurs(T, p, N) qui prend en entrée une liste de booléens T, un entier \(p \ge 2\) et la taille \(N\) de la liste, et qui modifie la liste T en affectant False à T[j] pour tous les indices \(j\) divisibles par \(p\) et strictement supérieurs à \(p\). Pour faire cela, on pourra parcourir les indices de la liste par pas de \(p\).

Attention : Votre fonction ne devra ni créer de nouvelle liste, ni retourner de liste. Elle modifiera la liste T passée en paramètre.

Par exemple, si on donne en entrée de la fonction eliminer_diviseurs une liste T égale à

[False, False, True, True, False, True, False, True, False, True, False, True, False, True, False, True]

ainsi qu’une taille N = 16 et l’entier p = 3, alors, en sortie de la fonction, la liste T devient :

T = [False, False, True, True, False, True, False, True, False, False, False, True, False, True, False, False]

(les valeurs d’indice \(6\), \(9\), \(12\) et \(15\) sont égales à False).

# Votre réponse ici

Question 3 : À l’aide des questions précédentes, implanter le crible d’Eratosthène présenté en début d’exercice, sous la forme d’une fonction eratosthene(N) qui retourne la liste des nombres premiers compris entre \(2\) et \(N\).

On vérifiera que pour eratosthene(100), on obtient la liste :

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

# Votre réponse ici

On dit que \(p\) est un nombre premier de Sophie Germain si \(p\) et \(2p+1\) sont des nombres premiers.

Question 4 : Écrire une fonction premiers_sophie_germain(N) qui retourne la liste des nombres premiers de Sophie Germain inférieurs ou égaux à N.

# Votre réponse ici

On dit que \(p\) et \(q\) sont deux nombres premiers jumeaux si \(p\) et \(q\) sont premiers et si \(|p - q| = 2\).

Question 5 : Écrire une fonction premiers_jumeaux(N) qui retourne la liste des nombres premiers jumeaux inférieurs ou égaux à N.

# Votre réponse ici
Contenu