Programmation impérative en Python

Cours 8. Ensembles, dictionnaires et matrices

Olivier Baldellon

Courriel : pré[Link]@[Link]
Page professionnelle : [Link]

Licence 1 — Faculté des sciences et ingénierie de Nice — Université Côte d’Azur

Concours Tk Annonces

▶ Il y aura pour les volontaires un projet Tk noté.

▶ La note sera un bonus
▶ Les règles et les objectifs :
▶ seront données en détail la semaine prochaine.
▶ Vous devez utiliser Python et Tk (et rien d’autre).
▶ Votre code doit être lisible, propre et commenté.
▶ Votre code doit être générique et paramétrable.
▶ Votre code doit fonctionner sans problème sur les machines Linux du
Petit Valrose.
▶ Date limite : date de l’examen final ?

1/40
Sommaire

F Partie i. Ensembles

F Partie ii. Fonctions de hachage

F Partie iii. Dictionnaires

F Partie iv. Mémoïsation

F Partie v. Matrices

F Partie vi. Table des matières

2/40
Type de données Partie i. Ensembles

▶ Nous avons eu l’occasion de voir plusieurs types de données.

>>> type(-29) shell

Des types simples <class 'int'>
>>> type(42.23)
<class 'float'>
>>> type(True)
<class 'bool'>

>>> type((1,2,3)) shell

Des types des <class 'tuple'>
>>> type([11,1.2])
séquences <class 'list'>
>>> type("Salut à toi")
<class 'str'>
▶ Nous allons voir deux autres types

>>> type({1,2,3}) # Les ensembles shell

<class 'set'>
>>> type({'prix':1.2 , 'nom':'banane'}) # Les dictionnaires
<class 'dict'>

3/40
Ensembles Python Partie i. Ensembles

▶ Un ensemble en Python est une collection finie d’objets

▶ Une collection sans répétition et sans ordre

▶ Un ensemble n’est pas une séquence !

▶ On ne peut pas accéder aux éléments via des indices.  
E[i]

▶ Ils sont notés avec des accolades comme en mathématiques.

>>> { 1, 2, 3, 1, 2 } # Ni répétition shell

{1, 2, 3}
>>> { 1, 2, 3 } == { 3, 1, 2 } # ni ordre
True
>>> {False, 'bleu', 2, 'bleu'} == {2, False, 'bleu', 2, 2}
True
▶ L’ensemble vide est noté : set() (et non pas {} qui est un dictionnaire)

>>> type({}) shell

<class 'dict'>
>>> type(set())
<class 'set'>
>>> set()
set()
4/40
Accès aux éléments d’un ensemble Partie i. Ensembles

▶ La notation   n’a pas de sens


E[i]
▶ Les éléments ne sont pas ordonnés : ils n’ont donc pas d’indice.

>>> E = { 22, 31.2, 'Salut', True } shell

>>> E[2]
Traceback (most recent call last):
File "<console>", line 1, in <module>
TypeError: 'set' object is not subscriptable

▶ On peut parcourir un ensemble avec une boucle for :

▶ L’ordre n’est pas respecté (car il n’y a pas d’ordre !)

>>> for x in E: shell

... print(x)
True
Salut
22
31.2

5/40
Appartenance et inclusion Partie i. Ensembles

▶ L’opérateur in permet de savoir si un élément appartient à un ensemble

>>> A = {22, 'Salut'} ; B = { 22, 31.2, 'Salut', True } shell

>>> print( 31.2 in A , 31.2 in B)
False True
▶ En mathématiques, 𝐴 est inclus dans 𝐵 si tout élément de 𝐴 appartient à 𝐵
▶ 𝐴⊆𝐵 ≡ ∀𝑥 ∈ 𝐴, 𝑥 ∈ 𝐵

▶ Traduisons cela en Python avec une boucle for

scRipt >>> inclusion(A,B) shell
def inclusion(A,B): True
for x in A: >>> inclusion(B,A)
if not(x in B): False
return False >>> inclusion(A,A)
return True True

▶ Ou directement avec l’opérateur <= (si on veut l’inclusion stricte : <) :

>>> print( A<=B , B<=A , A<=A, A<A , set()<A) shell

True False True False True

6/40
Nombre d’éléments d’un ensemble Partie i. Ensembles

▶ En mathématiques, le cardinal est le nombre d’éléments d’un ensemble.

def cardinal(E): scRipt

c = 0
for x in E:
c=c+1
return c
>>> cardinal({2,2,1,1,3,3,2,1,2,3}) shell
3
>>> {2,2,1,1,3,3,2,1,2,3} # ne contient bien que 3 éléments
{1, 2, 3}
>>> cardinal(set())
0
(( (
(
▶ Comme d’habitude, on( ( (((
s’embête pour rien : fonction len
(
▶ C’est important pédagogiquement de savoir réécrire les fonctions de base.

>>> len({2,2,1,1,3,3,2,1,2,3}) shell

3
>>> len(set())
0

7/40
Construire un ensemble Partie i. Ensembles

▶ On peut construire un ensemble en donnant directement ses valeurs

>>> E = {1 , 2 , 3 , 4} shell
>>> E
{1, 2, 3, 4}

▶ De même que les listes, on peut les construire par compréhension.

>>> L = [ x%10 for x in range(100) if x%6==0 ] shell

>>> L # L est une liste
[0, 6, 2, 8, 4, 0, 6, 2, 8, 4, 0, 6, 2, 8, 4, 0, 6]
>>> E = { x%10 for x in range(100) if x%6==0 }
>>> E # E est un ensemble
{0, 2, 4, 6, 8}

▶ On peut utiliser la fonction de conversion set (voir cours 5 page 18)

>>> set('abc') shell

{'b', 'a', 'c'}
>>> set(['a','b','c'])
{'b', 'a', 'c'}
>>> set(('a','b','c'))
{'b', 'a', 'c'}

8/40
Modifier un ensemble Partie i. Ensembles

▶ Les ensembles sont mutables : Cela signifie que l’on peut les modifier.
▶ On peut ajouter un élément avec la méthode add

>>> E # E contient 3 éléments shell

{1, 2, 3}
>>> [Link](12)
>>> E # E contient maintenant 4 éléments
{1, 2, 3, 12}
>>> [Link](1)
>>> E # E contient toujours 4 éléments
{1, 2, 3, 12}

▶ On peut supprimer un élément avec la méthode remove

>>> E = {'Salut',False,(1,2,3),'Ha ha ha'} shell

>>> [Link]('HA ha ha')
Traceback (most recent call last):
File "<console>", line 1, in <module>
KeyError: 'HA ha ha'
>>> E
{False, 'Ha ha ha', 'Salut', (1, 2, 3)}
>>> [Link]('Ha ha ha')

9/40
Opérations sur les ensembles Partie i. Ensembles

▶ On veut écrire l’union de deux ensembles.

def union(A,B): scRipt shell

>>> A={1,2,3,4}
E = set() # ensemble vide >>> B={2,4,6,8}
for x in A: >>> union(A,B)
[Link](x) {1, 2, 3, 4, 6, 8}
for x in B: >>> union(A,A)
[Link](x) {1, 2, 3, 4}
return E

▶ Comme toujours, la fonction existe déjà sous Python !

▶ L’union 𝐴 ∪ 𝐵 = { 𝑥 ∶ 𝑥 ∈ 𝐴 ou 𝑥 ∈ 𝐵 } se note A | B
▶ L’intersection 𝐴 ∩ 𝐵 = { 𝑥 ∶ 𝑥 ∈ 𝐴 et 𝑥 ∈ 𝐵 } se note A & B
▶ La différence 𝐴 ⧵ 𝐵 = { 𝑥 ∶ 𝑥 ∈ 𝐴 et 𝑥 ∉ 𝐵 } se note A - B

>>> A={1,2,3,4} shell >>> A&B shell

>>> B={2,4,6,8} {2, 4}
>>> A|B >>> A-B
{1, 2, 3, 4, 6, 8} {1, 3}

▶ Exercice : écrire l’intersection et la différence sans utiliser d’opérateurs.

10/40
Que puis-je mettre dans un ensemble? Partie i. Ensembles

▶ Bonne question : essayons !

>>> { '123' , 'abc' } # str : immuable shell

{'123', 'abc'}
>>> { (1,2,3) , ('a','b','c') } # tuple : immuable
{(1, 2, 3), ('a', 'b', 'c')}
>>> { [1,2,3] , ['a','b','c'] } # list : mutable
Traceback (most recent call last):
File "<console>", line 1, in <module>
TypeError: unhashable type: 'list'
>>> { {1,2,3} , {'a','b','c'} } # set : mutable
Traceback (most recent call last):
File "<console>", line 1, in <module>
TypeError: unhashable type: 'set'

▶ Un ensemble est mutable, mais ses éléments doivent être immuable.

▶ On peut faire des ensembles de tuple (ensembles de points du plan)
▶ On ne peut pas faire des ensembles de listes ou d’ensemble.

▶ Que signifie unhashable type du message d’erreur ?

▶ En interne, les ensembles utilisent des fonctions de hachage.

11/40
Sommaire

F Partie i. Ensembles

F Partie ii. Fonctions de hachage

F Partie iii. Dictionnaires

F Partie iv. Mémoïsation

F Partie v. Matrices

F Partie vi. Table des matières

12/40
Qu’est-ce? Partie ii. Fonctions de hachage

▶ Qu’est-ce qu’une empreinte digitale ?

▶ C’est un marqueur biologique en théorie unique.
▶ Facile à stocker, « facile » à comparer, facile à obtenir

▶ Existe-il un équivalent numérique ?

▶ Une fonction de hashage permet de construire une empreinte numérique.

▶ Exemple : la fonction md5

▶ Elle calcule une empreinte (digest) de 128 bits.
▶ On représente l’empreinte le plus souvent par son écriture hexadécimale

>>> from hashlib import md5 shell

>>> def h(x):
... return md5(repr(x).encode()).hexdigest()
>>> h(3)
'eccbc87e4b5ce2fe28308fd9f2a7baf3'
>>> h([1,2,3])
'49a5a960c5714c2e29dd1a7e7b950741'
>>> h(min)
'0f61485fd84d673c233e28e1d2a5acfe'

13/40
Pourquoi? Partie ii. Fonctions de hachage

▶ À quoi ces fonctions servent-elles ?

▶ Elles permettent de créer un identifiant pour un objet quelconque.
▶ En particulier cela sert à comparer des données volumineuses.
▶ Sauriez-vous trouver la différence entre les deux chaînes ?
▶ Grâce à la fonction de hachage, la non-égalité est immédiate.

>>> A='123456789101112131415161718192021222324252627' shell

>>> B='12345678910111213141516171819202l222324252627'
>>> h(A)
'c42012567482404030e362f0c3813c15'
>>> h(B)
'e5a41e2edb893242fe25aad75dfcca66'

▶ Soit s1 et s2 deux chaînes et h(s1) et h(s2) leurs empreintes.

▶ On a la garantie suivante :
▶ Si h(s1)≠h(s2) alors forcément s1≠s2 (car h est une fonction)

▶ Les propriétés suivantes sont extrêmement probables :

▶ Si h(s1)=h(s2) on peut en pratique considérer que s1=s2 (on a 1
chance sur 340 282 366 920 938 463 463 374 607 431 768 211 455 de se tromper)
▶ Si s1 et s2 sont très proches, h(s1) et h(s2) sont très différents.
14/40
Application aux ensembles Partie ii. Fonctions de hachage

▶ Supposons que l’on souhaite implémenter les ensembles par des listes
▶ On réimplémente les ensembles pour des questions pédagogiques

def ajouter(L,x): scRipt

for e in L:
if x == e: return # terminaison car x est déjà dans L
[Link](x) # sinon, on ajoute x
return

▶ Pour ajouter un élément, je dois comparer avec tous les éléments.

▶ S’il y a n éléments de taille T, il faudra faire n*T comparaisons.

▶ Pour gagner en efficacité, on stocke chaque élément avec son empreinte.

def ajouter(L,x): scRipt

hx=h(x) # je calcule l'empreinte de x
for e in L:
(hy,y) = e # y est stocké avec son empreinte
if hx == hy: return # le programme termine
[Link]((hx,x))
return

▶ Dorénavant je dois faire seulement N comparaisons d’empreintes.

15/40
Résumé Partie ii. Fonctions de hachage

▶ Dans Python
▶ Les ensembles sont implémentés de manière bien plus élaborées.
▶ Mais ils utilisent des tables de hachage.
▶ L’ajout d’élément ne dépend pas de la taille des éléments de E.

▶ En informatique en général : on utilise les empreintes

• pour vérifier qu’un téléchargement correspond au bon fichier

▶ On compare les empreintes (MD5 check sum)
▶ Si l’empreinte est bonne, on a bien une version correcte du bon fichier

• pour stocker des mots de passe sans les révéler.

▶ On stocke les empreintes
▶ On compare avec l’empreinte du mot de passe fourni par l’utilisateur.
▶ À aucun moment on ne stocke les mots de passe
▶ Une empreinte ne permet pas de retrouver le mot de passe

• pour certifier la liste chaînée d’une blockchain (bitcoin) ou de git.

16/40
Sommaire

F Partie i. Ensembles

F Partie ii. Fonctions de hachage

F Partie iii. Dictionnaires

F Partie iv. Mémoïsation

F Partie v. Matrices

F Partie vi. Table des matières

17/40
Qu’est-ce? Partie iii. Dictionnaires

▶ Un dictionnaire est une collection de couples clé:valeur.

▶ clé est forcément non mutable ;
▶ valeur peut être modifiée.

>>> mon_panier = {'pommes':243 , 'poires':123 } shell

>>> mon_panier
{'pommes': 243, 'poires': 123}

▶ On accède aux valeurs en utilisant les clés comme indices.

>>> mon_panier['poires'] shell
123
>>> mon_panier['pommes']
243

▶ Un dictionnaire vide se note {} ou mieux dict()

▶ Toutes les clés doivent être distinctes

>>> {'pommes':243 , 'poires':123, 'pommes':23 } shell
{'pommes': 23, 'poires': 123}

18/40
Accès aux éléments Partie iii. Dictionnaires

▶ L’accès à une valeur est extrêmement rapide.

▶ C’est le principal intérêt des dictionnaires.
▶ Les dictionnaires utilisent des tables de hachage

▶ La recherche est unidirectionnelle

▶ on va de la clé vers les valeurs

▶ La clé doit être non mutable.

▶ Typiquement des chaînes et des nombres.
▶ On peut utiliser des tuples ne contenant que des éléments non mutables.

>>> dico = { 'un':234 , 2:[3,4,5] , 3.5:'Bonjour' } shell

>>> dico[3.5]
'Bonjour'
>>> dico['un']
234
>>> dico['Bonjour'] # 'Bonjour' est une valeur !
Traceback (most recent call last):
File "<console>", line 1, in <module>
KeyError: 'Bonjour'

19/40
Exceptions Partie iii. Dictionnaires

▶ Si on utilise une clé qui n’existe pas, une exception est levée.
▶ Pour savoir si une clé existe on peut utiliser mot-clé in

>>> partiel = { 'Alice':15 , 'Bob':13 , "Charline":9} shell

>>> partiel["Gustave"]
Traceback (most recent call last):
File "<console>", line 1, in <module>
KeyError: 'Gustave'
>>> 'Gustave' in partiel # "Gustave" est-il une clé ?
False
▶ On veut affecter à note la valeur associée à l’étudiant étu
▶ Si une telle clé n’existe pas, on pose note="ABS"

try: scRipt if étu in partiel: scRipt

note = partiel[étu] note = partiel[étu]
except KeyError: else:
note = "ABS" note = "ABS"

▶ Ou plus simplement en une ligne avec la méthode get

>>> [Link]("Alice",'ABS') shell

15
>>> [Link]("Gustave",'ABS')
'ABS'
20/40
Modifier un dictionnaire Partie iii. Dictionnaires

▶ Un dictionnaire est mutable : il est modifiable.

▶ On peut modifier la valeur associée à une clé en utilisant l’affectation.

>>> dico = { 11: 'unu' , 22:'Du' , 33:'tri' } shell

>>> dico[22]='du'
>>> dico
{11: 'unu', 22: 'du', 33: 'tri'}

▶ On peut ajouter un nouveau couple clé:valeur en utilisant l’affectation

>>> dico shell

{11: 'unu', 22: 'du', 33: 'tri'}
>>> dico[44]='kvar'
>>> dico
{11: 'unu', 22: 'du', 33: 'tri', 44: 'kvar'}

▶ On peut supprimer un couple (clé:valeur) avec la commande pop

>>> [Link](33) shell

'tri'
>>> dico
{11: 'unu', 22: 'du', 44: 'kvar'}

21/40
Itération Partie iii. Dictionnaires

▶ On peut parcourir un dictionnaire en parcourant les clés ou les valeurs.

def clés(dico): scRipt def valeurs(dico): scRipt

for k in [Link](): for v in [Link]():
v = dico[k] # pas d'accès aux clés
print(f"{k} ({v})") print(v,end=' ')
print('')

>>> naissance["Athos"]=1615 shell

>>> naissance["Porthos"]=1617
>>> naissance["Aramis"]=1620
>>> naissance["d’Artagnan"]=1615
>>> clés(naissance)
Athos (1615)
Porthos (1617)
Aramis (1620)
d’Artagnan (1615)
>>> valeurs(naissance)#une valeur n'est pas forcément unique
1615 1617 1620 1615

22/40
Itérations : Clés et valeurs Partie iii. Dictionnaires

▶ À quoi correspondent [Link]() et [Link]() ?

>>> [Link]() shell

dict_keys(['Athos', 'Porthos', 'Aramis', 'd’Artagnan'])
>>> [Link]()
dict_values([1615, 1617, 1620, 1615])

▶ Ce sont des vues (view).

▶ Ce ne sont pas des listes !
▶ Mais ce sont des objets itérables.
▶ On peut les convertir en tuples, ensembles ou listes.

>>> list([Link]()) shell

['Athos', 'Porthos', 'Aramis', 'd’Artagnan']
>>> set([Link]())
{1617, 1620, 1615}

▶ On peut itérer directement sur un dictionnaire.

▶ C’est comme si on itérait sur les clés.
▶ for k in [Link](): ⇔ for k in dico:

23/40
Exemple : injectivité Partie iii. Dictionnaires

▶ En mathématique une application est injective si :

▶ 𝑓 (𝑥) = 𝑓 (𝑦) implique 𝑥 = 𝑦, dit autrement, si 𝑥 ≠ 𝑦 alors 𝑓 (𝑥) ≠ 𝑓 (𝑦)

▶ On cherche à savoir si un dictionnaire est injectif.

▶ C’est-à-dire si chaque valeur est unique

def est_injectif(dico): scRipt

for k1 in dico:
for k2 in dico:
if k1!=k2 and dico[k1]==dico[k2]:
return False # collision !
return True

▶ On peut aussi comparer la taille des ensembles de clés et de valeurs.

def est_injectif(dico): scRipt

nb_clés = len(set([Link]()))
nb_values = len(set([Link]()))
return nb_clés==nb_values

>>> est_injectif(naissance) shell

False
>>> est_injectif({ 1:'eins' , 2:'zwei' , 3:'drei' })
True
24/40
Sommaire

F Partie i. Ensembles

F Partie ii. Fonctions de hachage

F Partie iii. Dictionnaires

F Partie iv. Mémoïsation

F Partie v. Matrices

F Partie vi. Table des matières

25/40
Principes : exemple de la factorielle Partie iv. Mémoïsation

▶ Objectif : mémoriser les calculs déjà faits pour pouvoir les réutiliser.
▶ Exemple :
▶ on calcule 100! c’est « long », il faut 100 multiplications.
▶ on calcule ensuite 103! : il faut 103 multiplications.
▶ Si on avait mémorisé 100!, il aurait suffit de 3 multiplications.
▶ car 103! = 100! * 101 * 102 * 103

▶ Il suffit de stocker les résultats dans un dictionnaire.

▶ n sera la clé
▶ le résultat de fact(n) sera la valeur.

▶ Principe de l’algorithme
▶ Si n est une clé du dictionnaire, on renvoie la valeur associée.
▶ Sinon, on calcule v=n*fact(n-1) et on ajoute n:v dans le dictionnaire.

▶ Cette méthode s’appelle la mémoïsation.

26/40
Implémentation de la factorielle Partie iv. Mémoïsation

mémoire_cache = { 0:1 } # fact(0)=1 scRipt

def fact(n):
global mémoire_cache # global est facultatif
# on ne modifie pas l'ensemble mais son contenu
if n in mémoire_cache:
return mémoire_cache[n]
else:
v = n*fact(n-1)
mémoire_cache[n]=v
return v

>>> from time import time shell

>>> len(mémoire_cache)
1
>>> t=time(); x=fact(800); t800=time()-t; len(mémoire_cache)
801
>>> t=time(); x=fact(810); t810=time()-t; len(mémoire_cache)
811
>>> print(t810/t800)
0.01189127972819932
>>> print(f'{t810/t800:.1%}')
1.2%

▶ Le calcul de fact(810) est 100 fois plus efficace que celui de fact(800)
27/40
Mémoïsation et Fibonacci Partie iv. Mémoïsation

▶ On a rencontré des récurrences doubles. Exemple : la suite de Fibonacci.

▶ Très peu efficaces
▶ Les mêmes calculs sont faits de nombreuses fois.

def fib(n): scRipt

if n < 2: On souhaite retenir les
return 1 résultats intermédiaires
else:
return fib(n-1) + fib(n-2) (mémoïsation)

fib(100)

fib(99) fib(98)

fib(98) fib(97) fib(97) fib(96)

... ... ... ... ... ... ... ...

28/40
Implémentation de Fibonacci Partie iv. Mémoïsation

▶ Soit 𝑇𝑛 le nombre d’appels récursif lors du calcul de fib(n) on a

▶ 1 + 𝑇𝑛 = 2 ⋅ fib(n) car 1 + 𝑇𝑛 vérifie la même formule de récurrence que
fib(n) (mais en partant de 2 au lieu de 1)

𝑇𝑛 = 1 + 𝑇𝑛−1 + 𝑇𝑛−2 (1 + 𝑇𝑛 ) = (1 + 𝑇𝑛−1 ) + (1 + 𝑇𝑛−2 )

{ et donc {
𝑇0 = 𝑇1 = 1 (1 + 𝑇0 ) = (1 + 𝑇1 ) = 2

▶ Pour calculer fib(100) il faut donc 2 ⋅ fib(100) − 1 appels récursifs

▶ Supposons que le calcul ne prenne que 10−12 s par appel ;
▶ le temps nécessaire sera de ≈ 109 s ≈ 36 années.

mem = dict() scRipt

fib(100)
def fib(n):
if n==0 or n==1:
mem[n] = 1 fib(99) fib(98)
elif n not in mem:
mem[n] = fib(n-1)+fib(n-2)
return mem[n] fib(98) fib(97)

>>> fib(100) #Quasi instantané shell

573147844013817084101 fib(97) fib(96)

Le nouvel arbre d’appels est un « peigne » ... fib(95)

qui compte seulement 201 appels récursifs. 29/40
Sommaire

F Partie i. Ensembles

F Partie ii. Fonctions de hachage

F Partie iii. Dictionnaires

F Partie iv. Mémoïsation

F Partie v. Matrices

F Partie vi. Table des matières

30/40
Définitions Partie v. Matrices

▶ Nous avons représenté une matrice 2 × 2 par une liste de listes (cours 7).
▶ Généralisons cette idée aux matrices 𝑚 × 𝑛 (𝑚 lignes et 𝑛 colonnes).
>>> A = [[0, 1], [1, 2], [2, 3]] shell
>>> len(A)
0 1 𝐴0,0 𝐴0,1 3
>>> (A[0], len(A[0]))
𝐴 = (1 2) = (𝐴1,0 𝐴1,1 ) ([0, 1], 2)
>>> A[2][1]
2 3 𝐴2,0 𝐴2,1 3

▶ Les lignes et colonnes sont numérotées à partir de 0.

▶ len(A) donne le nombre de lignes (hauteur)
▶ len(A[0]) donne le nombre de colonnes (largeur)
▶ A[li] donne la ligne d’indice li
▶ A[li][co] donne le coefficient à la ligne li et à la colonne co : 𝐴𝑙𝑖,𝑐𝑜
▶ et pour la colonne d’indice co ?

def dimensions(A): # Fonction utile pour la suite scRipt

return (len(A),len(A[0])) # nombre de lignes et de colonnes
31/40
Extraire une colonne Partie v. Matrices

▶ On ne peut accéder directement qu’aux lignes.

▶ Comment accéder aux colonnes ?
def colonne(A, co): scRipt
res = []
for li in range(len(A)):
[Link](A[li][co])
return res

▶ En plus pythonesque, en utilisant les compréhensions de listes.

def colonne(A, co): scRipt

return [A[li][co] for li in range(len(A))]

>>> A = [[0, 1], [1, 2], [2, 3]] shell

>>> len(A)
0 1 3
>>> colonne(A,0)
𝐴 = (1 2 ) [0, 1, 2]
2 3 >>> colonne(A,1)
[1, 2, 3]

32/40
Reconnaître une matrice Partie v. Matrices

▶ Comment déterminer si un objet Python est une matrice ?

▶ c’est une liste de listes
▶ Les lignes et les colonnes doivent être non vides
▶ toutes les colonnes ont la même taille

def est_matrice(A): scRipt

# A doit être une liste non-vide
if type(A) != list or A==[]:
return False
# A[0] doit être une liste non-vide
if type(A[0]) != list or A[0]==[]:
return False
#Toutes les lignes doivent être des listes de même taille
for ligne in A:
if type(ligne) != list or len(ligne) != len(A[0]):
return False
return True

>>> est_matrice([]) shell >>> est_matrice([1,2,3]) shell

False False
>>> est_matrice([[],[],[]]) >>> est_matrice([[1,2],[3,4],[5,6]])
False True
>>> est_matrice(12) >>> est_matrice([[1,2],[3],[5,6]])
False False
33/40
Quelques matrices particulières Partie v. Matrices

▶ Une matrice nulle est une matrice ne contenant que des 0

def matrice_nulle(n,m): scRipt
A=[] Matrice 2 × 3 nulle :
for ligne in range(n):
L=[] 0 0
for colonne in range(m):
[Link](0) (0 0)
[Link](L) 0 0
return A

▶ Une matrice identité est une matrice carrée contenant des 1 sur la
diagonale et des 0 ailleurs.
Matrice identité 4 × 4 :
def matrice_identité(n): scRipt
A = matrice_nulle(n,n) 1 0 0 0
for i in range(n): ⎛ ⎞
A[i][i]=1 ⎜0 1 0 0⎟
return A ⎜0 0 1 0⎟⎟
⎜
⎝0 0 0 1⎠

▶ Exercice : écrire ces fonctions en une ligne avec des compréhensions de liste
34/40
Calcul de l’opposé Partie v. Matrices

▶ L’opposé d’une matrice est formé des opposés des élèments initiaux.

1 −2 −1 2
L’opposé de ( ) est ( )
−3 4 3 −4

▶ Comment rédiger un tel programme ?

▶ On crée une matrice nulle de la bonne taille
▶ On y affecte ensuite les bonnes valeurs

def opposé(A): scRipt

(n,m) = dimensions(A)
B = matrice_nulle(n,m)
for i in range(n):
for j in range(m):
B[i][j] = - A[i][j]
return B

▶ On est obligé de partir d’une nouvelle matrice.

▶ En effet si j’écris B=A, toute modification de B affectera A.
▶ Voir le cours 5 sur la gestion de la mémoire concernant les listes.

35/40
Calcul de la trace Partie v. Matrices

▶ La trace d’une matrice est la somme des éléments diagonaux.

1 2 3 4
⎛ ⎞
5 6 7 8⎟
𝐴 = ⎜⎜ La trace de 𝐴 vaut 1 + 6 + 2 + 7 = 16
⎜9 1 2 3⎟⎟
⎝4 5 6 7⎠

▶ Le concept n’a de sens que dans une matrice carrée

def trace(A): scRipt

(n,m)=dimensions(A)
if n != m :
raise ValueError('Trace : matrice non carrée')
tr = 0
for i in range(n):
tr = tr + A[i][i]
return tr

36/40
Calcul de la somme Partie v. Matrices

▶ On peut ajouter deux matrices coefficient par coefficient

▶ les matrices doivent être de même dimensions.

30 1 20 4 60 3 34 61 23
( ) + ( ) = ( )
3 11 50 20 −1 7 23 10 57

def somme(A,B): scRipt

(n,m) = dimensions(A)
if (n,m) != dimensions(B):
raise ValueError('Dimensions incompatibles')
C = matrice_nulle(n,m)
for i in range(n):
for j in range(m):
C[i][j] = A[i][j] + B[i][j]
return C

37/40
Calcul du produit Partie v. Matrices

▶ On peut multiplier deux matrices entre elles [Wikipédia]

▶ la longueur de la première doit être égale à la hauteur de la deuxième
▶ On pose 𝑁 ce nombre en commun.
𝑁
▶ La matrice produit 𝑀 = 𝐴𝐵 est définie par 𝑀𝑖,𝑗 = ∑ 𝐴𝑖,𝑘 × 𝐵𝑘,𝑗
𝑘=1

def coefficient_produit(A,B,i,j): scRipt

(n,m)=dimensions(A)
c = 0
for k in range(n):# de 0 à n-1 (et non comme en math de 1 à n)
c = c + A[i][k]*B[k][j]
return c
def produit(A,B):
(la,ca) = dimensions(A) ; (lb,cb) = dimensions(B)
if lb != ca:
raise ValueError('Dimensions incompatibles')
C = matrice_nulle(la,cb)
for i in la:
for j in cb:
C[i][j] = coefficient_produit(A,B,i,j)
return C

▶ On utilise une sous-fonction pour éviter d’avoir trop de for imbriqués.

38/40
Application : images bitmaps Partie v. Matrices

▶ Une image est un tableau de pixels.

▶ Un pixel (en noir et blanc) ne peut avoir que deux valeurs :
▶ 0 : pixel blanc
▶ 1 : pixel noir

▶ Une image pourra donc être représentée par une matrice de 0 et de 1

▶ Voir TP !

39/40
Merci pour votre attention
Questions

?
40/40
Cours 8 — Ensembles, dictionnaires et matrices

Concours Tk Application aux ensembles Implémentation de Fibonacci

F Partie i. Ensembles Résumé

Type de données F Partie iii. Dictionnaires F Partie v. Matrices

Ensembles Python Qu’est-ce ? Définitions

Accès aux éléments d’un ensemble Accès aux éléments Extraire une colonne

Appartenance et inclusion Exceptions Reconnaître une matrice

Nombre d’éléments d’un ensemble Modifier un dictionnaire Quelques matrices particulières

Construire un ensemble Itération Calcul de l’opposé

Modifier un ensemble Itérations : Clés et valeurs Calcul de la trace

Opérations sur les ensembles Exemple : injectivité Calcul de la somme

Que puis-je mettre dans un ensemble ? F Partie iv. Mémoïsation Calcul du produit

F Partie ii. Fonctions de hachage Principes : exemple de la factorielle Application : images bitmaps

Qu’est-ce ? Implémentation de la factorielle

Pourquoi ? Mémoïsation et Fibonacci F Partie vi. Table des matières