3.5. TP algorithme numérique en python#
3.6. Exercices d’algorithmique#
%matplotlib inline
import sys,os
import numpy as np
import scipy as sp
import matplotlib
import matplotlib.pyplot as plt
from random import random
import importlib
# initialisation
from validation.validation import check_function, info_etudiant, liste_functions, info_function
from validation.valide_markdown import test_markdown, test_code, test_algorithme
from IPython.display import display, Markdown, Latex
def printmd(string):
display(Markdown(string))
# test si numero étudiant spécifier
try: NUMERO_ETUDIANT
except NameError: NUMERO_ETUDIANT = None
if type(NUMERO_ETUDIANT) is not int :
printmd("**ERREUR: numéro d'étudiant non spécifié!!!**")
NOM, PRENOM, NUMERO_ETUDIANT = info_etudiant()
#raise AssertionError("NUMERO_ETUDIANT non défini")
# parametres spécifiques
_uid_ = NUMERO_ETUDIANT
np.random.seed(_uid_)
printmd("**Etudiant** {} {} id={}".format(NOM,PRENOM,NUMERO_ETUDIANT))
ERREUR: numéro d’étudiant non spécifié!!!
Etudiant Marc BUFFAT id=137764122
3.6.1. Algorithme 0 : triplet pythagoricien#
On cherche à déterminer le plus grand entier m inférieur ou égale à n
qui fait partie d’un triplet pythagoricien, i.e. si son carré est la somme des carrés de deux
nombres entiers non nuls: i.e. (m,a,b) vérifie la relation de Pythagore:
$\( m^2 = a^2 + b^2 \)$
On remarque que m, a et b vérifient forcément : \(1 < b < a < m\) et donc la valeur minimale de b est 2, celle de a est 3 et celle de m est 4
exemples
pour n=8 -> m=5 : triplet m=5 a=4 b=3 $\( 5^2 = 4^2 + 3^2\)$
pour n=33 -> m=30 : triplet m=30, a=24, b=18 $\( 30^2 = 24^2 + 18^2 \)$
Il existe plusieurs algorithme pour trouver un triplet pythagoricien. Vous allez implémenter une version simple.
Algorithme simple
on part de m=n et Trouve=Faux
tant que (non Trouve) et (m>=4)
avec 2 boucles imbriquées, on passe en revue toutes les valeurs possibles de a et b vérifiant les conditions \(1 < b < a < m\) et on teste si \(m^2 = a^2 + b^2\)
si (non Trouve) on fait m=m-1, sinon on sort des deux boucles
fin boucle tant que
si Trouve est vrai la solution est m,a,b
Avant de commencer, on vous conseille d’écrire l’algorithme simple sur une feuille en spécifiant les boucles et les tests.
Traduire votre algorithme en Python
Faire afficher le triplet (m,a,b) afin de comparer le résultat avec la solution attendue (pour n=8).
n = 8
## BEGIN SOLUTION
m = n
Trouve = False
while (not Trouve ) and (m>=4) :
for i in range(2,m):
for j in range(i+1,m):
if m**2 == (i**2 + j**2):
Trouve = True
a = j
b = i
break # sort uniquement de la boucle j
# fin boucle j
if Trouve: break # sort de la boucle i
# fin boucle i
if not Trouve: m = m-1
# fin while
if Trouve :
print("Triplet pythagoricien ",m,a,b)
else:
print("Aucun triplet < ",N)
## END SOLUTION
Triplet pythagoricien 5 4 3
Transformation en fonction
On veut transformer les instructions python précédentes en une fonction python TripletPythagoricien(N) où N est l’argument contenant la
valeur de n. La fonction renvoie le tuple (m,a,b) si le triplet existe ou None s’il n’existe pas.
Sur feuille, simplifier l’algorithme en notant que dans la fonction, lorsque l’on a trouvé le triplet on peut directement renvoyer le tuple sans sortir explicitement des boucles. La variable logique Trouve n’est plus utilisée dans ce cas.
Écrire la fonction
TripletPythagoricien(N)Vérification
appeler la fonction pour n=4, mettre le résultat dans res0 et afficher ce qui permet de vérifier par rapport au résultat attendu.
idem pour n=8, avec le résultat dans res1
idem pour n=33, avec le résultat dans res2
# fonction TripletPythagoricien(N)
## BEGIN SOLUTION
def TripletPythagoricien(N):
m = N
while (m>=4) :
for i in range(2,m):
for j in range(i+1,m):
if m**2 == (i**2 + j**2):
return (m,j,i)
# fin boucle j
# fin boucle i
m = m-1
# fin while
return None
## END SOLUTION
# verification
res0 = None
res1 = None
res2 = None
## BEGIN SOLUTION
res0 = TripletPythagoricien(4)
print(res0)
res1 = TripletPythagoricien(8)
print(res1)
res2 = TripletPythagoricien(33)
print(res2)
## END SOLUTION
None
(5, 4, 3)
(30, 24, 18)
# ne pas modifier la cellule
## BEGIN HIDDEN TESTS
assert(TripletPythagoricien(33) == (30,24,18))
## END HIDDEN TESTS
3.6.2. Algorithme 1: test si les valeurs d’un tableau sont différents#
Soit un tableau d’entier TabI, écrire un algorithme simple permettant de déterminer si les éléments du tableau sont tous différents.
Traduire votre algorithme sous forme de fonction python
Different(TabI)qui renvoieTrueouFalse.
On vous donne l’instruction numpy pour créer un tableau I de 10 valeurs entières tirées aléatoirement entre 0 et 99.
Faire afficher ce tableau I
Faire afficher le résultat de l’appel de la fonction
Different(I)Créer un tableau J de 10 valeurs entières tirées aléatoirement entre 0 et 7.
Faire afficher le résultat de l’appel de la fonction avec J.
import numpy as np
## BEGIN SOLUTION
def Different(TabI):
N = TabI.size
for i in range(N):
for j in range(N): # for j in range(i+1,N): # plus concis
if (j!=i) and (TabI[j]== TabI[i]) : # if (TabI[j]== TabI[i]) :
return False
return True
## END SOLUTION
I = np.random.randint(100,size=10)
## BEGIN SOLUTION
print(I)
print(Different(I))
J = np.random.randint(8,size=10)
print(J)
print(Different(J))
## END SOLUTION
[35 50 70 39 90 45 15 23 97 22]
True
[0 4 4 6 0 1 3 6 6 1]
False
# ne pas modifier la cellule
## BEGIN HIDDEN TESTS
assert(check_function(Different,'exo58'))
## END HIDDEN TESTS
validation: exo58
Given a numpy array of integers, return True if all the elements are different, False otherwise
3.6.3. Algorithme 2: colinéarité entre vecteurs#
Soit 2 vecteurs \(\vec{u}\) et \(\vec{v}\) de \(R^n\), on veut écrire un algorithme permettant de savoir si \(\vec{u}\) et \(\vec{v}\) sont colinéaires.
Mathématiquement, \(\vec{u}\) et \(\vec{v}\) sont colinéaires si et seulement si il existe au moins 2 réels non nuls \(\alpha_1\) et \(\alpha_2\) t.q.
En effectuant le produit scalaire respectivement avec \(\vec{u}\) et \(\vec{v}\), on en déduit que \(\alpha_1\) et \(\alpha_2\) sont solutions du système linéaire (2x2)
qui s’écrit sous forme matricielle:
Ce système admet au moins une solution non nulle \(X\neq [0,0]\) si et seulement si le
déterminant de la matrice A est nulle. Le déterminant se calcule avec la fonction np.linalg.det(A).
On vous donne 2 vecteurs de 6 valeurs générés aléatoirement. Ils sont donnés par leurs composantes \(U=[U_k]\) et \(V=[V_k]\) dans \(R^n\).
Écrire les instructions python qui calculent la matrice A
Écrire l’instruction qui calcule le déterminant
Écrire les instructions qui testent si le déterminant est proche de zero à \(\epsilon\) pres et affichent « colinéaire » ou « non colinéaire » suivant le résultat.
import numpy as np
n = 6
U = np.random.rand(n)
V = np.random.rand(n)
eps = 1.e-6
## BEGIN SOLUTION
A = np.zeros((2,2))
A[0,0] = U @ U
A[0,1] = V @ U
A[1,0] = U @ V
A[1,1] = V @ V
print("A=",A)
d = np.linalg.det(A)
if abs(d) < eps :
print("U et V sont colinéaires ",d)
else:
print("U et V ne sont pas colinéaires ",d)
## END SOLUTION
A= [[1.90821962 1.85836136]
[1.85836136 2.6564597 ]]
U et V ne sont pas colinéaires 1.615601589185619
Transformation en fonction
Transformer le code précédent en une fonction python Colineaire(U1,U2,Eps) où U1 et U2 sont
les vecteurs numpy contenants les composantes des vecteurs à tester. La fonction renvoie True si les 2 vecteurs sont colinéaires à Eps près et False sinon.
Vérification
pour vérifier, appeler la fonction :
en utilisant les 2 vecteurs U et V précédents et afficher le résultat
en utilisant U et U et afficher le résultat
# fonction Colineaire(U1,U2,Eps)
## BEGIN SOLUTION
def Colineaire(U1,U2,Eps):
A = np.zeros((2,2))
A[0,0] = U1 @ U1
A[0,1] = U2 @ U1
A[1,0] = U1 @ U2
A[1,1] = U2 @ U2
return abs(np.linalg.det(A)) < Eps
## END SOLUTION
# verification
res1 = None
res2 = None
## BEGIN SOLUTION
res1 = Colineaire(U,V,eps)
print("U V colinéaire : ",res1)
res2 = Colineaire(U,U,eps)
print("U U colinéaire : ",res2)
## END SOLUTION
U V colinéaire : False
U U colinéaire : True
# ne pas modifier la cellule
### BEGIN HIDDEN TESTS
assert(Colineaire(U,V,eps)==False)
assert(Colineaire(U,U,eps)==True)
### END HIDDEN TESTS
3.6.4. Algorithme 3: familleLibre#
k vecteurs \([\vec{v_1},\vec{v_2}\ldots\vec{v_k}]\) forment une famille libre dans \(R^n\), si et seulement si l’unique combinaison linéaire :
qui est nulle i.e. \(\vec{c_l}=\vec{0}\), implique :
En s’inspirant de l’algorithme précédent, on montre que le vecteur \(X=[\alpha_1,\alpha_2,\ldots,\alpha_k]\) est solution du système linéaire :
Ce système admet comme solution unique \(X=[0,0\ldots 0]\) si et seulement si déterminant de A est nulle. Numériquement on teste si le déterminant est proche de 0 à \(\epsilon\) près.
On vous donne 3 vecteurs de 6 valeurs générés aléatoirement. Ils sont donnés par leurs composantes \(U=[U_k]\), \(V=[V_k]\) et \(W=[W_k]\) dans \(R^n\).
Mettre U,V,W dans une liste L.
Écrire les instructions python qui calculent la matrice A en utilisant 2 boucles imbriquées.
Écrire l’instruction qui calcule le déterminant de A.
Écrire les instructions qui testent si le déterminant de A est proche de zéro à \(\epsilon\) pres et et affichent « famille libre » ou « famille non libre » suivant le résultat.
import numpy as np
n = 6
U = np.random.rand(n)
V = np.random.rand(n)
W = np.random.rand(n)
eps = 1.e-6
## BEGIN SOLUTION
L = [U,V,W]
A = np.zeros((3,3))
for i in range(3):
for j in range(3):
A[i,j] = L[i] @ L[j]
d = np.linalg.det(A)
if abs(d) > eps :
print("U,V,W forment une famille libre ",d)
else:
print("U,V,W forment une famille non libre ",d)
## END SOLUTION
U,V,W forment une famille libre 0.6504560088779362
Transformation en fonction
Transformer le code précédent en une fonction python FamilleLibre(LV,Eps) où
LV est une liste de vecteurs numpy. La fonction renvoie True si
les vecteurs de LV forment une famille libre à Eps près et False sinon.
Vérification
pour vérifier, appeler la fonction :
en utilisant les 3 vecteurs U,V,W précédents, mettre le résultat dans res1 et afficher le résultat
en utilisant les 3 vecteurs U,V,U+V, mettre le résultat dans res2 et afficher le résultat
# fonction FamilleLibre(LV,Eps)
## BEGIN SOLUTION
def FamilleLibre(LV,Eps):
k = len(LV)
A = np.zeros((k,k))
for i in range(k):
for j in range(k):
A[i,j] = LV[i] @ LV[j]
return abs(np.linalg.det(A)) > Eps
## END SOLUTION
# verification
res1 = None
res2 = None
## BEGIN SOLUTION
res1 = FamilleLibre([U,V,W],eps)
print("Famille libre ? ",res1)
res2 = FamilleLibre([U,V,U+V],eps)
print("Famille libre ? ",res2)
## END SOLUTION
Famille libre ? True
Famille libre ? False
# ne pas modifier la cellule
### BEGIN HIDDEN TESTS
assert(FamilleLibre([U,V,W],eps)==True)
assert(FamilleLibre([U,V,U+V],eps)==False)
### END HIDDEN TESTS
3.6.5. Algorithme 4: matrice de Toeplitz#
Pour vecteur X de dimension n donné, on veut construire calcule la matrice symétrique de Toeplitz A, donnée par:
A[i,j]=X[j-i] pour j>=i
A[i,j]=X[i-j] pour j<i
Pour le vecteur X donné ci-dessous, construire la matrice A de Toeplitz en effectuant des boucles imbriquées.
Affichez la matrice A obtenue pour vérifier.
import numpy as np
X = np.random.rand(3)
A = None
## BEGIN SOLUTION
n = X.size
A = np.zeros((n,n))
for i in range(n):
for j in range(0,i):
A[i,j] = X[i-j]
for j in range(i,n):
A[i,j] = X[j-i]
print("A = ",A)
## END SOLUTION
A = [[0.46118022 0.09435942 0.16075811]
[0.09435942 0.46118022 0.09435942]
[0.16075811 0.09435942 0.46118022]]
Transformation en fonction
Transformer le code précédent en une fonction python Toeplitz(U) où
U est un vecteur numpy. La fonction renvoie la matrice de Toeplitz construite
à partir de U.
Vérification
pour vérifier, appeler la fonction :
en utilisant le vecteur X précédent, et stocker le résultat dans la variable M.
comparer avec la matrice A en utilisant la fonction numpy
np.allclose(X,Y)qui renvoie True si les 2 tableaux X et Y sont égaux à la précision machine près.
## fonction Toeplitz(U)
## BEGIN SOLUTION
def Toeplitz(U):
n = U.size
A = np.zeros((n,n))
for i in range(n):
for j in range(0,i):
A[i,j] = U[i-j]
for j in range(i,n):
A[i,j] = U[j-i]
return A
## END SOLUTION
# verification
M = None
## BEGIN SOLUTION
M = Toeplitz(X)
if np.allclose(A,M):
print("Verification OK")
else:
print("Erreur")
## END SOLUTION
Verification OK
# ne pas modifier la cellule
## BEGIN HIDDEN TESTS
assert(check_function(Toeplitz,'exo71'))
## END HIDDEN TESTS
3.6.6. Algorithme 5: nombre tricolore#
Un nombre est dit tricolore s’il s’écrit comme la somme de 3 nombres carrés parfaits non nuls. On veut écrire un algorithme en python qui teste si n est tricolore, i.e. :
On vérifie aisément les conditions suivantes :
En s’inspirant de l’algorithme Triplet Pythagoricien , écrire 3 boucles imbriquées sur a, b et c pour tester si n est tricolore et sortir des boucles si c’est le cas.
Écrire le programme Python correspondant pour n=14 (dans ce cas on a \(14 = 1^2 + 2^2 + 3^2\)).
On mettra dans cmax la valeur max de c, i.e. la valeur entière de \(\sqrt(n)\), et on introduit une variable booléenne
tricolore initialisée par défaut à False.
n=14
## BEGIN SOLUTION
import numpy as np
tricolore = False
cmax = int(np.sqrt(n))
for i in range (1,cmax+1):
for j in range(i,cmax+1):
for k in range(j,cmax+1):
if (n == (i**2 + j**2 + k**2)):
tricolore = True
a=i; b=j; c=k;
break;
if tricolore: break;
if tricolore: break;
if tricolore:
print(n," tricolore :",a,b,c)
else:
print(n, "non tricolore")
## END SOLUTION
14 tricolore : 1 2 3
Transformation en fonction
Transformer le code précédent en une fonction python Tricolore(N) où N est l’argument contenant la
valeur de n. La fonction renvoie True si N est tricolore et False sinon.
Simplifier l’algorithme en notant que dans la fonction, lorsque l’on a trouvé (a,b,c) on peut directement renvoyer le résultat True sans sortir explicitement des boucles. La variable tricolore est donc inutile dans ce cas.
Vérification
pour vérifier:
appeler la fonction pour n=14, mettre le résultat dans res1 et afficher et vérifier par rapport au résultat attendu (Vrai).
appeler la fonction pour n=10, mettre le résultat dans res2 et afficher et vérifier par rapport au résultat attendu (Faux).
appeler la fonction pour n=3, mettre le résultat dans res3 et afficher et vérifier par rapport au résultat attendu.
# fonction Tricolore(N)
## BEGIN SOLUTION
def Tricolore(N):
cmax = int(np.sqrt(N))
for i in range (1,cmax+1):
for j in range(i,cmax+1):
for k in range(j,cmax+1):
if (N == (i**2 + j**2 + k**2)):
return True
return False
## END SOLUTION
# verification
res1 = None
res2 = None
res3 = None
## BEGIN SOLUTION
res1 = Tricolore(14)
print("14 tricolore ?",res1)
res2 = Tricolore(10)
print("10 tricolore ?",res2)
res3 = Tricolore(3)
print("3 tricolore ?",res3)
## END SOLUTION
14 tricolore ? True
10 tricolore ? False
3 tricolore ? True
# ne pas modifier la cellule
## BEGIN HIDDEN TESTS
assert(check_function(Tricolore,'exo105'))
## END HIDDEN TESTS