Matrices

Matrices

def zero(n,p):
    """
    Renvoie la matrice nulle a n lignes et p colonnes
    """
    mat=[]
    for i in range(n):
        ligne=[]
        for j in range(p):
            ligne.append(0)
        mat.append(ligne)
    return mat

def identite(n):
    """
    Renvoie la matrice identite d'ordre n
    """
    mat = zero(n,n)
    for i in range(n):
        mat[i][i] = 1
    return mat

def taille(mat):
    """
    Renvoie le couple nombre de lignes/nombre de colonnes de la matrice
    """
    if mat == []:
        return 0,0
    else:
        return len(mat), len(mat[0])

def somme(mat1,mat2):
    """
    Calcule la somme de deux matrices si les tailles sont compatibles
    """
    n1,p1 = taille(mat1)
    n2,p2 = taille(mat2)
    assert (n1,p1)==(n2,p2)
    result = zero(n1,p1)
    for i in range(n1):
        for j in range(p1):
            result[i][j] = mat1[i][j] + mat2[i][j]
    return result

def difference(mat1,mat2):
    """
    Calcule la différence de deux matrices si les tailles sont compatibles
    """
    n1,p1 = taille(mat1)
    n2,p2 = taille(mat2)
    assert (n1,p1)==(n2,p2)
    result = zero(n1,p1)
    for i in range(n1):
        for j in range(p1):
            result[i][j] = mat1[i][j] - mat2[i][j]
    return result

def prod_sc(x,mat):
    """
    Calcule le produit d'une matrice par un scalaire
    """
    n,p=taille(mat)
    result = zero(n,p)
    for i in range(n):
        for j in range(p):
            result[i][j] = x*mat[i][j]
    return result

def transposee(mat):
    """
    Calcule la transposee d'une matrice
    """
    n,p=taille(mat)
    result = zero(p,n)
    for i in range(p):
        for j in range(n):
            result[i][j] = mat[j][i]
    return result

def produit(mat1,mat2):
    """
    Calcule le produit de deux matrices si les tailles sont compatibles
    """
    n1,p1 = taille(mat1)
    n2,p2 = taille(mat2)
    assert (p1 == n2)
    result = zero(n1,p2)
    for i in range(n1):
        for j in range(p2):
            coef=0
            for k in range(p1):
                coef += mat1[i][k] * mat2[k][j]
            result[i][j] = coef
    return result

def decoupe(mat):
    """
    Divise une matrice en quatre sous-matrices
    """
    n,p=taille(mat)
    a11 = [[mat[i][j] for j in range(n//2)] for i in range(n//2)]
    a12 = [[mat[i][j+n//2] for j in range(n//2)] for i in range(n//2)]
    a21 = [[mat[i+n//2][j] for j in range(n//2)] for i in range(n//2)]
    a22 = [[mat[i+n//2][j+n//2] for j in range(n//2)] for i in range(n//2)]
    return a11,a12,a21,a22

def recolle(a11,a12,a21,a22):
    """
    Recolle quatre sous matrices de même taille pour obtenir une matrice deux fois plus grande
    """
    n,p = taille(a11)
    mat = zero(2*n,2*n)
    for i in range(n):
        for j in range(n):
            mat[i][j] = a11[i][j]
            mat[i][j+n] = a12[i][j]
            mat[i+n][j] = a21[i][j]
            mat[i+n][j+n] = a22[i][j]
    return mat

def strassen(a,b):
    """
    Calcule le produit de deux matrices dont la taille est une puissance de 2 avec l'algorithme de Strassen
    """
    n,p = taille(a)
    if n==1:
        return produit(a,b)
    else:
        a11,a12,a21,a22 = decoupe(a)
        b11,b12,b21,b22 = decoupe(b)
        m1 = strassen(somme(a11,a22),somme(b11,b22))
        m2 = strassen(somme(a21,a22),b11)
        m3 = strassen(a11,difference(b12,b22))
        m4 = strassen(a22,difference(b21,b11))
        m5 = strassen(somme(a11,a12),b22)
        m6 = strassen(difference(a21,a11),somme(b11,b12))
        m7 = strassen(difference(a12,a22),somme(b21,b22))
        c11 = somme(m1,somme(difference(m4,m5),m7))
        c12 = somme(m3,m5)
        c21 = somme(m2,m4)
        c22 = somme(difference(m1,m2),somme(m3,m6))
        c = recolle(c11,c12,c21,c22)
        return c

def affiche_naif(mat):
    """
    Affiche une matrice avec un algorithme naif
    """
    for ligne in mat:
        for coef in ligne:
            print(coef, end=" ")
        print("")

def affiche_naif2(mat):
    """
    Affiche une matrice avec un algorithme naif, mais joli
    """
    n,p = taille(mat)
    print("╔"+(2*p+1)*' '+"╗")
    for ligne in mat:
        print('║ ',end='')
        for coef in ligne:
            print(coef,end=" ")
        print('║')
    print("╚"+(2*p+1)*' '+"╝")

def plus_long_coef(mat):
    """
    Calcule la longueur du plus long coefficient d'une matrice
    """
    longueur = 0
    for ligne in mat:
        for coef in ligne:
            n=len(str(coef))
            if n > longueur:
                longueur = n
    return longueur

def ajuste_taille(n,p):
    """
    Renvoie une chaine de caractere de longueur p representant n
    """
    s= str(n)
    k=len(s)
    if k < p:
        if (p-k)%2 == 0:
            return " "*((p-k)//2)+s+" "*((p-k)//2)
        else:
            return " "*((p-k)//2)+s+" "*((p-k)//2)+" "
    else:
        return str(n)

def affiche_matrice(mat):
    """
    Affiche joliment une matrice
    """
    longueur = plus_long_coef(mat)
    for ligne in mat:
        for coef in ligne:
            coefstr = ajuste_taille(coef,longueur)
            print(coefstr,end=" ")
        print("")

from math import *
from copy import deepcopy

def plus_grand_pivot(mat,k):
    """
    Calcule le plus grand pivot d'une matrice sur la colonne k
    """
    pivot=0
    ligne=k
    n,p=taille(mat)
    for i in range(k,n):
        if abs(mat[i][k]) > pivot:
            pivot=mat[i][k]
            ligne=i
    return pivot,ligne

def colonne_pivot(mat,k):
    """
    Applique l'algorithme de Gauss pour la k-ieme colonne
    """
    n,p =taille(mat)
    pivot,ligne = plus_grand_pivot(mat,k)
    mat2 = deepcopy(mat)
    for j in range(p):
        mat2[k][j],mat2[ligne][j] = mat2[ligne][j],mat2[k][j]
    for i in range(k+1,n):
        coef1 = mat2[i][k]
        for j in range(k,p):
            mat2[i][j] = mat2[i][j]*pivot - mat2[k][j]*coef1
    return(mat2)

def gauss(mat):
    """
    L'algorithme de Gauss
    """
    n,p=taille(mat)
    mat2 = deepcopy(mat)
    for k in range(n):
        mat2 = colonne_pivot(mat2,k)
    return(mat2)

def gauss_ind(mat):
    """
    L'algorithme de Gauss, mais avec une fonction recursive
    """
    def aux(mat,k):
        n,_ = taille(mat)
        if k==n:
            return(mat)
        else:
            return aux(colonne_pivot(mat,k),k+1)
    return aux(mat,0)

def rang(mat):
    """
    Calcule le rang d'une matrice avec le pivot de Gauss
    """
    echel = gauss(mat)
    n,p = taille(mat)
    rk = 0
    for i in range(n):
        if echel[i][i] != 0:
            rk+=1
    return rk