#!/usr/bin/env python # coding: utf-8 # # TP2 - HMLA310: # *** # > __Auteur__: Joseph Salmon --- # > # 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[ ]: get_ipython().run_line_magic('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]: get_ipython().run_line_magic('load_ext', 'memory_profiler') # In[8]: n = 35 # In[25]: get_ipython().run_line_magic('timeit', 'fibonacci_naive(n)') # In[5]: # %memit fibonacci_naive(n) # **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) # In[ ]: get_ipython().run_line_magic('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)) # In[19]: get_ipython().run_line_magic('timeit', 'fibonacci_variables(n)') # 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]: get_ipython().run_line_magic('timeit', 'fibonacci_cache(n)') # 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]: get_ipython().run_line_magic('timeit', 'fibonacci_numpy(n)') # In[ ]: # %memit fibonacci_numpy(n)