TP2 - HMLA310:


Auteur: Joseph Salmon ---

[email protected]

In [ ]:
# Changer ici par votre Prenom Nom:
prenom = "Joseph"  # à remplacer
nom = "Salmon"  # à remplacer
extension = ".ipynb"
tp = "TP2_HMLA310"
In [ ]:
filename = "_".join([tp, prenom, nom + extension]) 
In [ ]:
filename = filename.lower()
print(filename)
In [ ]:
# utiliser filename pour votre nom de TP

Exercice 1: petit théorème de Fermat

Le petit théorème de Fermat est un résultat connu de la théorie des nombres. Illustrons le dans cet exercice numériquement. Son énoncé est le suivant:

Soit $p$ un nombre premier et $a$ un entier non divisible par $p$ alors $a^{p−1} - 1 \equiv 0 [p]$.

a) Ecrire une fonction nommée 'fermat' qui prend en entrée $a$ et $p$, et qui renvoie $a^{p−1} \textrm{ mod } p$

b) Montrez que ce résultat est vrai pour $p = 13$ et $a = 16$. On testera l'égalité avec le symbole '==' et la fonction fermat.

c) Créer une liste nommée 'prems', contenant les 7 premiers nombre premiers.

d) Tester que le théorème est vrai pour les 7 premiers nombres premiers et pour tous les nombres $a$ plus petit que 100 satisfaisant la contrainte $a$ non divisibles par $p$. On pourra pour cela utiliser

  • la liste prems
  • deux boucles for imbriquées (dont une utilisant enumerate)
  • un test "if"

Question a)

In [ ]:
def fermat(a, p):
    return (a ** (p - 1)) % p

Question b)

In [ ]:
a = 6
p = 13
fermat(a, p) == 1

Question c)

In [ ]:
prems = [2, 3, 5, 7, 11, 13, 17]

Question d)

In [ ]:
a = 1
bolos = True

while a < 101 and bolos:
    for p in prems:
        if a % p != 0: 
            bolos = fermat(a, p) == 1
    a += 1
print(bolos)
In [ ]:
 

Exercies: séries

Calculez la série $\sum_{j=0}^n r^j$ pour $r = .75$ et $n = 10, 20, 30, 40$. On utilisera deux méthodes :

a) une solution avec une boucle sur une liste

b) une solution avec la fonction sum sur un numpy array.

Enfin comparez votre résultat à celui de la formule $(1 − r^{n+1} )/(1 − r)$

Solution liste:

In [ ]:
import numpy as np

n_list = [10, 20,  30, 40]

for n in n_list:
    print('cas n = {} :'.format(n))
    liste = list(range(n + 1))
    somme = 0
    r = .75
    for j in liste:
        somme += r ** j
    print("Somme par liste       : {}".format(somme))
    np_array = np.arange(n + 1)
    somme_numpy = np.sum(r ** np_array)
    print("Somme par numpy       : {}".format(somme_numpy))
    print("Somme formule de Gauss: {}".format((1 - r ** (n + 1)) / (1 - r)))
    print('\n')
In [ ]:
%history

Exercice 3: gymnastique de création de matrices/vecteurs

Créer les vecteurs et matrices suivants sans renter les valeurs une à une:

a) array([1., 1., 1.]) (dont la taille est (3,) )

b) array([[1., 1., 1.]]) (dont la taille est (3,1) )

c) array([1, 2, 3])

d) array([ 2, 1, 0, -1, -2])

e) array([1, 2, 3, 1, 2, 3])

f) array([[1, 2, 3], [4, 5, 6]])

g) array([[0., 0., 0., 0., 0., 0.], [1., 0., 0., 0., 0., 0.], [0., 1., 0., 0., 0., 0.], [0., 0., 1., 0., 0., 0.], [0., 0., 0., 1., 0., 0.], [0., 0., 0., 0., 1., 0.]])

Question a)

In [ ]:
np.ones(3)

Question b)

In [ ]:
np.ones((1, 3))

Question c)

In [ ]:
np.arange(1, 4)

Question d)

In [ ]:
np.arange(2, -3, -1)

Question e)

In [ ]:
np.hstack((np.arange(1, 4), np.arange(1, 4)))
np.repeat(np.arange(1, 4), 2, axis=0)
np.tile(np.arange(1, 4),2)

Question f)

In [ ]:
np.reshape(np.arange(1, 7, 1), newshape=(2, 3))

Question g)

In [ ]:
np.diag(np.ones(5), k=-1)

Exercice: Fibonacci

On se propose de faire l'étude de cette suite et de comparer l'efficacité en mémoire et en temps, en passant par des boucles et des listes, ou bien par un modèle matriciel.

In [1]:
def fibonacci_naive(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci_naive(n - 1) + fibonacci_naive(n - 2)
In [2]:
# pip install memory_profiler  # if needed.
In [3]:
%load_ext memory_profiler
In [8]:
n = 35
In [25]:
%timeit fibonacci_naive(n)
3.01 s ± 75.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
In [5]:
# %memit fibonacci_naive(n)
peak memory: 58.82 MiB, increment: 0.00 MiB

Conclusion: Cette fonction est lente, car on doit recalculer sans cesse des termes qui l'on déjà été... Par exemple pour calculer $F_{35}$ on calcule $F_{34}$ et $F_{33}$, mais le calcul de $F_{34}$ nécessite à son tour le calcul de $F_{33}$ alors que celui-ci a déjà été calculé: cette redondance des calculs s'accumulent avec l'augmentation de $n$.

Implémentation avec une liste:

In [15]:
def fibonacci_list(n):
    l = [0, 1]
    if n == 0:
        return l[0]
    elif n == 1:
        return l
    a = 0
    b = 1
    for i in range(0, n - 1):
        b = a + b
        a = b - a
        l.append(b)
    return l
In [16]:
fibonacci_list(n)
Out[16]:
[0,
 1,
 1,
 2,
 3,
 5,
 8,
 13,
 21,
 34,
 55,
 89,
 144,
 233,
 377,
 610,
 987,
 1597,
 2584,
 4181,
 6765,
 10946,
 17711,
 28657,
 46368,
 75025,
 121393,
 196418,
 317811,
 514229,
 832040,
 1346269,
 2178309,
 3524578,
 5702887,
 9227465]
In [ ]:
%timeit fibonacci_list(n)
In [21]:
# %memit fibonacci_list(n)

Implémentation avec deux variables intermédiaires:

In [17]:
def fibonacci_variables(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    a = 0
    b = 1
    for i in range(0, n - 1):
        b = a + b
        a = b - a
    return b
In [18]:
print(fibonacci_variables(n))
print(fibonacci_naive(n))
9227465
9227465
In [19]:
%timeit fibonacci_variables(n)
2.12 µs ± 62.2 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
In [ ]:
# %memit fibonacci_variables(n)

Implémentation avec cache

In [30]:
from functools import lru_cache


@lru_cache()
def fibonacci_cache(n):
    if n < 2:
        return n
    return fibonacci_cache(n - 1) + fibonacci_cache(n - 2)
In [ ]:
 
In [35]:
%timeit fibonacci_cache(n)
63.4 ns ± 3.8 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
In [ ]:
# %memit fibonacci_cache(35)

Implémentation avec numpy

In [34]:
import numpy as np


def fibonacci_numpy(n):
    F = [[1, 1], [1, 0]]
    return np.linalg.matrix_power(F, n)[0, 1]
In [36]:
%timeit fibonacci_numpy(n)
14.1 µs ± 244 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
In [ ]:
# %memit fibonacci_numpy(n)