<jupyter_start><jupyter_text>Mise en place des outils de base 1. Ecrire une fonction `cree_matrice` qui prend trois arguments :nbLignes,nbColonnes, et fonction et qui crée une matrice avec les dimensions fournies remplie par les images `fonction(i,j)` des indices dans la matrice (on utilisera des indices à partir de 0 conformément à l’usage informatique plutôt que l’usage mathématiques).<jupyter_code>def cree_matrice(nbLignes, nbColonnes, fonction):
    matrice = []
    for i in range(nbLignes):
        ligne = []
        for j in range(nbColonnes):
            ligne.append(fonction(i,j))
        matrice.append(ligne)
    return matrice

def cree_matrice(nbLignes, nbColonnes, fonction):
    return [[fonction(i,j) for j in range(nbColonnes)] for i in range(nbLignes)]<jupyter_output><empty_output><jupyter_text>2. Déterminer dans chaque cas une fonction pouvant être utilisée dans la fonction `cree_matrice` pour obtenir :<jupyter_code># 1. matrice constante de terme égal à a
def constante(a):
    return lambda i, j:a

def constante(a):
    def ma_fonction(i,j):
        return a
    return ma_fonction

print_matrice(cree_matrice(2, 3, constante(5)))
# 2. matrice identité
def identite(i, j):
    return int(i==j)

print_matrice(cree_matrice(3, 3, identite))
# 3. aléatoire dans [0,1[
from random import random
def aleatoire(i, j):
    return random()

print_matrice(cree_matrice(2, 2, aleatoire))
# 4. copie d'une matrice mat
def copie(mat):
    return lambda i,j: mat[i][j]

A = cree_matrice(2, 3, identite)
B = cree_matrice(2, 3, copie(A))
#B = A
A[1][0] = 42
print("Matrice A:")
print_matrice(A)

print("Matrice B:")
print_matrice(B)<jupyter_output>Matrice A:
[1, 0, 0]
[42, 1, 0]
Matrice B:
[1, 0, 0]
[0, 1, 0]<jupyter_text>3. En utilisant encore la fonction `cree_matrice` avec en argument une fonction adéquate, écrire une fonction qui calcule la somme de deux matrices si leurs dimensions sont compatibles et renvoie un message d’erreur sinon. (On pourra utiliser le mot-clef assert qui suivi d’une condition déclenche une erreur si cette condition n’est pas vérifiée). Ecrire également une fonction qui multiplie une matrice par un scalaire et renvoie le résultat. Déterminer la complexité de ces fonctions.<jupyter_code>def somme_matrices(A, B):
    assert len(A)==len(B) and len(A[0])==len(B[0])
    return cree_matrice(len(A), len(A[0]), 
                        lambda i,j:A[i][j]+B[i][j])

def multiple_matrice_scalaire(A, x):
    return cree_matrice(len(A), len(A[0]),
                       lambda i, j:x*A[i][j])<jupyter_output><empty_output><jupyter_text>`cree_matrice` contient deux boucles imbriquées de longueur respectives n (le nombre de lignes) et p (le nombre de colonnes). Pour chaque itération elle évalue fonction en i, j, qui est de complexité constante dans tous les exemples.La complexité est donc en $\Theta(n p)$. 4. En utilisant encore la fonction `cree_matrice` avec en argument une fonction adéquate, écrire une fonction quieffectue le produit matriciel entre deux matrices si leurs dimensions sont compatibles et renvoie un message d’erreur sinon. Déterminer la complexité.<jupyter_code>def produit(A,B):
    assert len(A[0])==len(B)
    def coeff(i, j):
        s = 0
        for k in range(len(A[0])):
            s+=A[i][k]*B[k][j]
        return s
    return cree_matrice(len(A), len(B[0]), coeff)

def produit(A,B):
    assert len(A[0])==len(B)
    return cree_matrice(len(A), len(B[0]), lambda i,j: sum([A[i][k]*B[k][j] for k in range(len(A[0]))]))<jupyter_output><empty_output><jupyter_text>Si A : n x p et B : p x k  `cree_matrice` fait n x k itérations dans lesquelles elle calcule `coeff(i,j)` qui est de complexité $\Theta(p)$La complexité est donc $\Theta(n p k)$  Algorithme du pivot de Gauss5. Programmer l'algorithme du pivot de Gauss:  (a) Ecrire une fonction `ligne_pivot(matrice, i)` qui détermine la ligne du coefficient de valeur absolue maximale dans la colonne i à partir de la ligne i<jupyter_code>def ligne_pivot(matrice, i ):
    jMax = i
    for j in range(i+1, len(matrice)):
        if abs(matrice[j][i])>abs(matrice[jMax][i]):
            jMax = j
    return jMax<jupyter_output><empty_output><jupyter_text>Complexité : $\Theta(n-i-1)$ (b) Ecrire une fonction `echange_lignes(matrice, i, j)` qui produit des effets de bords sur la matrice.<jupyter_code>def echange_lignes(matrice, i, j):
    matrice[i], matrice[j] = matrice[j], matrice[i]
# ne marche pas si c'est un tableau numpy<jupyter_output><empty_output><jupyter_text>Complexité : $\Theta(1)$ (si on fait comme ça mais $\Theta(n+p)$ si on le fait par itération) (c) Ecrire une fonction `transvection(matrice, i, j, mu)` ($L_i←L_i+μL_j$) qui produit des effets de bords sur la matrice.<jupyter_code>def transvection(matrice, i, j, mu):
    for k in range(len(matrice[0])):
        matrice[i][k] += mu*matrice[j][k]<jupyter_output><empty_output><jupyter_text>Complexité : $\Theta(n+p)$ (d) Ecrire une fonction `multiplie_ligne(matrice, i, mu)` ($L_i←μL_i$) qui produit des effets de bords sur la matrice.<jupyter_code>def multiplie_ligne(matrice, i, mu):
    for k in range(len(matrice[0])):
        matrice[i][k] *= mu<jupyter_output><empty_output><jupyter_text>Complexité : $\Theta(n+p)$ (e) Implanter  l’algorithme  du  pivot  de  Gauss  sur  ces  matrices  sous  la  forme  d’une  fonction $pivot(A,b)$ quirenvoie le membre droit de la matrice augmentée après exécution de l’algorithme.<jupyter_code>def augmente(A, B):
    assert len(A)==len(B)
    return cree_matrice(len(A), len(A[0])+len(B[0]),
        lambda i, j: A[i][j] if j<len(A[0]) else B[i][j-len(A[0])])<jupyter_output><empty_output><jupyter_text>Complexité $\Theta(n (n+p))$<jupyter_code>def pivot_gauss(A, b):
    n = len(A)
    mat = augmente(A, b) # Theta(n(n+p))
    p = len(b[0])
    # mise sous forme triangulaire
    for i in range(n-1): # n-1  itérations
        j = ligne_pivot(mat, i) # Theta(n-i-1)
        echange_lignes(mat, i, j) # Theta(1)
        for k in range(i+1, n): # (n-i-1) itérations
            transvection(mat, k, i, -mat[k][i]/mat[i][i]) # Theta(n+p)
        #print("tour de boucle", i)
        #print_matrice(mat)
    # somme sur tous les i de: (Theta(n-i) + (n-i-1) Theta(n+p)) ) = Theta(n² (n+p))
    print("Après mise sous forme triangulaire")
    print_matrice(mat)
    
    # remontée
    for k in range(n-1,-1,-1): # n itérations
        multiplie_ligne(mat, k, 1/mat[k][k]) # Theta(n+p)
        for j in range(k+1, n):
            transvection(mat, k, j, -mat[k][j]) # Theta(n+p)
        multiplie_ligne(mat, k, 1/mat[k][k]) # Theta(n+p)
    # même principe
    print("Après remontée")
    print_matrice(mat)
    return cree_matrice(n,p,lambda i,j:mat[i][j+n])
print_matrice(pivot_gauss([[0,1],[2,3]], [[4], [5]]))
A=[[0,1],[2,3]]
I=[[1,0],[0,1]]
invA = pivot_gauss(A, I)
print("Inverse de A:")
print_matrice(invA)
print("Vérification : A x invA")
print_matrice(produit(A,invA))<jupyter_output>Après mise sous forme triangulaire
[2, 3, 0, 1]
[0.0, 1.0, 1.0, 0.0]
Après remontée
[1.0, 0.0, -1.5, 0.5]
[0.0, 1.0, 1.0, 0.0]
Inverse de A:
[-1.5, 0.5]
[1.0, 0.0]
Vérification : A x invA
[1.0, 0.0]
[0.0, 1.0]
{'fraction_non_alphanumeric': 0.1403361344537815, 'fraction_numerical': 0.018487394957983194, 'mean_word_length': 4.258468335787923, 'pattern_counts': {'":': 0, '<': 40, '<?xml version=': 0, '>': 40, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '10', 'dir': 'jupyter-structured-clean-dedup', 'id': '187005', 'license': 'CC0-1.0', 'n_tokens_mistral': 2899, 'n_tokens_neox': 2859, 'n_words': 781, 'path': 'pivot de Gauss.ipynb', 'repo_name': 'ljospin/mp2i_jospin_public', 'size': '7140'}