## TP9 -- Listes de listes et matrices



## Exercise 9.4

## question 1) b) (ii)

def nombreLignes(M):
	return len(M)

## question 2) b) (ii)

def nombreColonnes(M):
	return len(M[0])



## Exercise 9.5

## question 2) b) (ii)

def estNulle(M):
	n = nombreLigne(M)
	p = nombreColonnes(M)
	for i in range(n):
		for j in range(p):
			if M[i][j] != 0:
				return False
	return True



## Exercise 9.6 -- La matrice nulle

## question 2) b) (ii)

# Voici une première solution :
def matriceNulle(n, p):
	M = []
	for i in range(n):
		L = []
		for j in range(p):
			L.append(0)
		M.append(L)
	return M

# Voici une deuxième solution :
def matriceNulle1(n, p):
	M = []
	for i in range(n):
		L = [0]*p
		M.append(L)
	return M

# Voici une troisième solution :
def matriceNulle2(n, p):
	M = []
	for i in range(n):
		L = [0 for j in range(p)]
		M.append([0]*p)
	return M

# Voici une quatrième solution :
def matriceNulle3(n, p):
	return [ [0]*p for i in range(n)]

# Voici une cinquième solution :
def matriceNulle3(n, p):
	return [ [0 for j in range(p)] for i in range(n)]



## Exercise 9.7 -- La matrice identité

## question 2) b) (ii)

# Voici une première solution :
def matriceIdentite(n):
	M = matriceNulle(n, n)
	for i in range(n):
		M[i][i] = 1
	return M

# Voici une deuxième solution :

def kronecker(i, j):
	if i == j:
		return 1
	else:
		return 0

def matriceIdentite1(n):
	return [ [ kronecker(i, j) for j in range(n)] for i in range(n)]



## Exercise 9.8 -- Somme de matrices

## question 2) b) (ii)

def somme(A, B):
	n = nombreLignes(A)
	p = nombreColonne(A)
	M = matriceNulle(n, p)
	for i in range(n):
		for j in range(p):
			M[i][j] = A[i][j] + B[i][j]
	return M

# Voici une deuxième solution :
def somme1(A, B):
	n = nombreLignes(A)
	p = nombreColonne(A)
	return [ [ A[i][j] + B[i][j] for j in range(p) ] for i in range(n) ]



## Exercise 9.9 -- Produit de matrices

## question 2) b) (ii)

def produit(A, B):
	n = nombreLignes(A)
	M = matriceNulle(n, n)
	for i in range(n):
		for j in range(n):
			S = 0
			for k in range(n):
				S = S + A[i][k]*B[k][j]
			M[i][j] = S
	return M

# Voici une deuxième solution :
def produit1(A, B):
	n = nombreLignes(A)
	return [ [ sum( [ A[i][k]*B[k][j] for k in range(n) ] ) ] for j in range(n) ] for i in range(n) ]



## Exercise 9.10 -- Exponentiation de matrices

## question 2) b) (ii)

def puissance(A, n):
	taille = nombreLignes(A)
	P = matriceIdentite(taille)
	for i in range(n):
		P = produit(P, A)
	return P



## Exercise 9.11 -- Exponentiation de matrices récursive

## question 2) b) (ii)

def puissanceRecursive(A, n):
	if n == 0:
		taille = nombreLignes(A)
		return matriceIdentite(taille)
	else:
		M = puissanceRecursive(A, n-1)
		return produit(M, A)



## Exercise 9.12 -- Exponentiation rapide de matrices

## question 1) b) (ii)

def puissanceRapide(A, n):
	if n == 0:
		taille = nombreLignes(A)
		return matriceIdentite(taille)
	elif n == 1:
		return A
	else:
		A_carre = produit(A, A)
		if n%2 == 0:
			p = n//2
			return puissanceRapide(A_carre, p)
		else:
			p = (n-1)//2
			M = puissanceRapide(A_carre, p)
			return produit(M, A)

## question 2) b) (ii)

def produitEtInfos(A, B):
	n = nombreLignes(A)
	M = matriceNulle(n, n)
	nb_add = 0
	nb_prod = 0
	for i in range(n):
		for j in range(n):
			S = 0
			for k in range(n):
				S = S + A[i][k]*B[k][j]
				nb_add = nb_add + 1
				nb_prod = nb_prod + 1
			M[i][j] = S
	return (M, nb_add, nb_prod)

## question 2) b) (ii)

def puissanceEtInfos(A, n):
	taille = nombreLignes(A)
	P = matriceIdentite(taille)
	nb_add = 0
	nb_prod = 0
	for i in range(n):
		P, n1, n2  = produitEtInfos(P, A)
		nb_add = nb_add + n1
		nb_prod = nb_prod + n2
	return (P, nb_add, nb_prod)

## question 2) b) (ii)

def puissanceRapideEtInfos(A, n):
	if n == 0:
		taille = nombreLignes(A)
		return matriceIdentite(taille), 0, 0
	elif n == 1:
		return (A, 0, 0)
	else:
		nb_add = 0
		nb_prod = 0
		A_carre, n1, n2 = produitEtInfos(A, A)
		nb_add = nb_add + n1
		nb_prod = nb_prod + n2
		if n%2 == 0:
			p = n//2
			nb_prod = nb_prod + 1
			M, m1, m2 = puissanceRapideEtInfos(A_carre, p)
			return (M, nb_add + m1, nb_prod + m2)
		else:
			p = (n-1)//2
			nb_add = nb_add + 1
			nb_prod = nb_prod + 1
			M, m1, m2 = puissanceRapideEtInfos(A_carre, p)
			N, p1, p2 = produitEtInfos(M, A)
			return (N, nb_add+m1+p1, nb_prod+m2+p2)