TP algorithme numérique en python

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))

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
  1. on part de m=n et Trouve=Faux
  2. tant que (non Trouve) et (m>=4)
     1. 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$
     2. si (non Trouve) on fait m=m-1, sinon on sort des deux boucles
  3. fin boucle tant que
  4. 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

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.

1. Écrire la fonction TripletPythagoricien(N)
2. Vérification
   1. 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.
   2. idem pour n=8, avec le résultat dans res1
   3. 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

# ne pas modifier la cellule
## BEGIN HIDDEN TESTS
assert(TripletPythagoricien(33) == (30,24,18))
## END HIDDEN TESTS

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 renvoie True ou False.

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

# ne pas modifier la cellule
## BEGIN HIDDEN TESTS
assert(check_function(Different,'exo58'))
## END HIDDEN TESTS

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.

$$ \alpha_1 \vec{u} + \alpha_2 \vec{v} = \vec{0}$$

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)

\begin{eqnarray} \alpha_1 \vec{u}.\vec{u} + \alpha_2 \vec{v}.\vec{u} &=& 0 \\ \alpha_1 \vec{u}.\vec{v} + \alpha_2 \vec{v}.\vec{v} &=& 0 \\ \end{eqnarray}

qui s'écrit sous forme matricielle:

$$ A X = B \mbox{ avec } X=[\alpha_1,\alpha_2] \mbox{ et } B = [0,0] $$

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

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 :

1. en utilisant les 2 vecteurs U et V précédents et afficher le résultat
2. 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

# ne pas modifier la cellule
### BEGIN HIDDEN TESTS
assert(Colineaire(U,V,eps)==False)
assert(Colineaire(U,U,eps)==True)
### END HIDDEN TESTS

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 :

$$ \vec{c_l} = \alpha_1 \vec{v_1} + \alpha_2\vec{v_2}+\ldots + \alpha_k \vec{v_k}$$

qui est nulle i.e. $\vec{c_l}=\vec{0}$, implique :

$$\alpha_1=\alpha_2=\ldots=\alpha_k=0$$

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 :

$$ A X = B \mbox{ avec } A_{i,j} = \vec{v_i}.\vec{v_j} \mbox{ et } B_i = 0 $$

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

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 :

1. en utilisant les 3 vecteurs U,V,W précédents, mettre le résultat dans res1 et afficher le résultat
2. 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

# 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

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

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 :

1. en utilisant le vecteur X précédent, et stocker le résultat dans la variable M.
2. 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

# ne pas modifier la cellule
## BEGIN HIDDEN TESTS
assert(check_function(Toeplitz,'exo71'))
## END HIDDEN TESTS

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. :

$$ N = a^2 + b^2 + c^2$$

On vérifie aisément les conditions suivantes :

$$ 1 \le a \le b \le c \lt \sqrt{n} $$

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

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:

1. appeler la fonction pour n=14, mettre le résultat dans res1 et afficher et vérifier par rapport au résultat attendu (Vrai).
2. appeler la fonction pour n=10, mettre le résultat dans res2 et afficher et vérifier par rapport au résultat attendu (Faux).
3. 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

# ne pas modifier la cellule
## BEGIN HIDDEN TESTS
assert(check_function(Tricolore,'exo105'))
## END HIDDEN TESTS

FIN