Dunod Informatique Avec Python Exercice 2ed
Dunod Informatique Avec Python Exercice 2ed
© Dunod, 2023
11 rue Paul Bert, 92240 Malakoff
[Link]
ISBN 978-2-10-085373-1
Jean-Noël Beury
INFORMATIQUE
AVEC PYTHON
MPSI·PCSI·PTSI
MP·PC·PSI·PT·TSI·TPC
EXERCICES
INCONTOURNABLES
2e édition
Table des matières
Avant-proposVI
Partie 1
Prise en main de Python
1. Prise en main de Python 3
2. Graphiques 25
Partie 2
Terminaison, correction, complexité
3. Terminaison, correction, complexité 31
Partie 3
Algorithmes de recherche
4. Algorithmes 45
5. Algorithmes de dichotomie 51
Partie 4
Récursivité
6. Récursivité 57
Partie 5
Algorithmes gloutons
7. Algorithmes gloutons (sauf TSI et TPC) 85
III
Table des matières
Partie 6
Lecture et écriture de fichiers – Matrices de pixels et images
8. Lecture et écriture de fichiers 93
9. Matrices de pixels et images, traitement d’images 99
Partie 7
Tris
10. Tris 109
Partie 8
Dictionnaire, pile, file, deque
11. Dictionnaire, pile, file, deque 131
Partie 9
Graphes
12. Graphes 149
Partie 10
Recherche d’un plus court chemin
13. Recherche d’un plus court chemin (sauf TSI et TPC) 185
Partie 11
Programmation dynamique
14. Programmation dynamique (Spé) (sauf TSI et TPC) 211
Partie 12
Intelligence artificielle et jeux
15. Intelligence artificielle et jeu à deux joueurs (Spé) 239
IV
Table des matières
Partie 13
Bases de données
16. Bases de données (Spé) 271
Partie 14
Algorithmique numérique
17. Algorithmique numérique (Spé) (uniquement TSI et TPC) 291
Index 313
[Link]
V
Avant-propos
Cet ouvrage de la série « Exercices incontournables » traite de l’intégralité du nou-
veau programme d’informatique commune pour les deux années des différentes
filières de classes préparatoires aux grandes écoles (sauf BCPST).
La première partie reprend la base de la programmation avec Python. Des rappels
de cours et des exercices classiques vous permettront de vous familiariser avec la
syntaxe Python.
Dans les exercices de certains chapitres (« Prise en main de Python », « Terminai-
son, correction, complexité », « Matrices de pixels et images, traitement d’images »,
« Dictionnnaire, pile, file, deque », « Graphes », « Intelligence artificielle et jeux à
deux joueurs », « Bases de données »), vous trouverez un rappel de cours détaillé
présentant le vocabulaire utilisé.
Pour chaque exercice classique, vous trouverez :
•• La méthode de résolution expliquée et commentée étape par étape.
•• Le corrigé rédigé détaillé.
•• Les astuces à retenir et les pièges à éviter.
VI
Partie 1
Prise en main
de Python
Plan
1. Prise en main de Python 3
1.1 : Assertion, moyenne, variance et écart-type d’une liste
de nombres 3
1.2 : Boucle, test, fonction (banque PT 2015) 11
1.3 : Variables locales, variables globales 14
1.4 : Affectation, objet immuable, copie 15
1.5 : Passage par référence pour les listes, effet de bord 20
1.6 : Slicing, extraction de tranche 22
2. Graphiques 25
2.1 : Tracé d’une fonction avec matplotlib 25
2.2 : Tracé d’un histogramme avec matplotlib 28
Prise en main
de Python
1
Exercice 1.1 : Assertion, moyenne, variance et écart-type d’une
liste de nombres
On considère la liste de nombres : L=[9, 10, 11, 20.5, 0, 12.0, -5,
-8.3e1].
1. Écrire une fonction rec_moy qui admet comme argument L une liste non
vide de nombres et retourne la moyenne de L.
2. Écrire une fonction rec_variance qui admet comme argument L une
liste non vide de nombres et retourne la variance de la liste L.
3. Écrire une fonction rec_ecart_type qui admet comme argument L une
liste non vide de nombres et retourne l’écart-type de la liste L.
4. Les en-têtes des fonctions peuvent être annotés pour préciser les types des
paramètres et du résultat. Ainsi,
def uneFonction(n:int, X:[float], c:str, u) -> list:
Analyse du problème
On utilise une boucle for pour parcourir les différents éléments de la liste. On peut
alors calculer la somme des éléments de la liste pour en déduire la valeur moyenne.
Une assertion est une aide de détection de bugs dans les programmes. La levée
d’une assertion entraîne l’arrêt du programme.
3
·
Partie 1 Prise en main de Python
Cours :
L’installation de Python 3 peut se faire avec Pyzo.
Un script Python est formé d’une suite d’instructions. Une instruction simple est contenue
dans une seule ligne. Si une instruction est trop longue pour tenir sur une ligne ou si on sou-
haite améliorer la lisibilité du code, le symbole « \ » en fin de ligne permet de poursuivre
l’écriture de l’instruction sur la ligne suivante (voir corrigé 4).
Une affectation se fait avec l’instruction n=3 : n prend la valeur 3 (voir exercice 1.4
« Affectation, objet immuable, copie »).
On peut utiliser « _ » dans le nom des variables mais pas « - ».
Le typage des variables est dynamique : l’interpréteur détermine le type à la volée lors de
l’exécution du code. Dans l’exemple précédent, le type de n est int.
Le symbole dièse permet d’ajouter des commentaires dans les programmes Python : #
commentaire sur le programme.
Le type d’une variable n s’obtient avec l’instruction : type(n).
Les types de base des variables dans Python sont :
•• Nombres entiers (positifs ou négatifs) : int
•• Nombres à virgule flottante (ou nombres flottants) : float
Exemple
a=-3.2e2 : -3,2 × 102 = -320
•• Booléens : bool
Les variables booléennes sont True (vrai) et False (faux).
Opérations de base sur les entiers (int) : +, -, *, //, **, %
n=28
n//10 : 2 = quotient de la division euclidienne de n par 10
n%10 : 8 = reste de la division euclidienne de n par 10
n**3 : n puissance 3
Opérations de base sur les nombres flottants (float) : +, -, *, /, **
a=1/3 : a vaut 0.3333333333333333
2.6**(a) : 2,6 puissance a
Comparaisons :
a==b : cet opérateur compare a et b. Si a=b, Python retourne True, sinon
False
a!=b : a différent de b
a>b, a<b, a>=b, a<=b : strictement supérieur, strictement inférieur, supérieur ou égal,
inférieur ou égal
Opérations sur les booléens (bool) :
or : ou
and : et
not : non
4
·
Chapitre 1 Prise en main de Python
•• Tuples : tuple
Les tuples sont des structures indicées immuables. Une fois le tuple créé, il ne peut pas
être modifié. On peut créer un tuple avec ou sans parenthèses.
M=(2, 3, 8) : crée le tuple M
Ne pas confondre avec les listes, où on met des crochets.
On crée le même tuple si on omet les parenthèses
5
·
Partie 1 Prise en main de Python
•• Dictionnaires : dict
Pour l’utilisation des dictionnaires, voir les exercices 11.1 « Opérations de base sur les
dictionnaires » et 11.2 « Comptage des éléments d’une liste à l’aide d’un dictionnaire »
dans le chapitre « Dictionnaire, pile, file, deque ».
Remarque : Pour le type None, voir la remarque de la question 2 dans l’exer-
cice 10.1 « Tri par insertion » dans le chapitre « Tris ». On ne l’utilisera pas dans
les autres exercices.
Il existe deux catégories d’objets dans Python :
•• les objets dont la valeur peut changer sont dits muables (en anglais : mutable) : listes,
dictionnaires, deques (voir chapitre 11 « Dictionnaire, pile, file, deque »)… ;
•• les objets dont la valeur ne peut pas changer sont dits immuables (en anglais : immu-
table) : entiers, nombres flottants, booléens, chaînes de caractères, tuples…
Voir les exercices 1.4 « Affectation, objet immuable, copie » et 1.5 « Passage par référence
pour les listes, effet de bord » pour les affectations et les arguments d’entrée des fonctions.
Quelques fonctions intrinsèques :
abs(x) : renvoie la valeur absolue de x
int(x) : convertit x en entier
float(x) : convertit x en flottant
str(x) : convertit x en chaîne de caractères
bool(x) : convertit x en booléen
6
·
Chapitre 1 Prise en main de Python
Boucle while :
i=0
while i<=10: # ne pas oublier : à la fin de la ligne while
print(i) # affichage de i
i=i+1 # on incrémente i de 1 à chaque étape
L’instruction break fait sortir d’une boucle while ou for et passe à l’instruction sui-
vante (voir exercice 10.6 « Tri à bulles » dans le chapitre « Tris »). Lorsqu’il y a plusieurs
boucles imbriquées, l’instruction break ne fait sortir que de la boucle la plus interne.
Définition d’une fonction :
def f(x): # définition de la fonction f ayant pour argument d’entrée x
# ne pas oublier ':' à la fin de la ligne
y=x+3 # y est une variable locale : elle est créée à l’appel
# de la fonction et est détruite à la fin de la fonction
# voir exercice 1.3 "Variables locales, variables globales"
return y # fin de la fonction et retourne la valeur y
# attention à l’indentation
L’instruction return quitte la fonction même en cours d’exécution d’une boucle for ou
while.
Structure conditionnelle :
if x==3: # teste si x = 3
y=3*x
elif x>3 and x<=4: # si le test précédent n’est pas vérifié,
# alors teste si x >3 et si x <=4
y=x+2
elif x>4 and x <5: # si le test précédent n’est pas vérifié,
# alors teste si x >4 et si x <5
y=x-2
else: # sinon (les tests précédents ne sont pas vérifiés)
y=0
7
·
Partie 1 Prise en main de Python
Importation de modules
Des fonctions traitant d’un même domaine sont regroupées dans des modules (par exemple
les fonctions mathématiques cos, sin, tan… sont regroupées dans le module math).
Différents modules peuvent être regroupés dans une bibliothèque. On utilise l’instruction
import module pour importer un module.
import math # importation du module math
Le module math contient des fonctions et des variables : cos(), sin(), tan(), exp(),
sqrt() (racine carrée), log() (logarithme népérien), log10() (logarithme décimal),
pi (nombre p )…
Pour utiliser les fonctions et les variables du module math :
a=[Link]/4
b=[Link]([Link]/4)
c=[Link]([Link])
print(b) # affiche 0.7071067811865476
print(c) # affiche 1.2246467991473532e-16
Les nombres flottants ne permettent pas un calcul exact à cause de la représentation des
nombres à virgule sur des mots de taille fixe. Un test du type a==b n’a en général pas
de sens si a et b sont des nombres à virgule flottante. On remplacera donc ce test par :
abs(a-b)<epsilon où epsilon est une valeur proche de zéro, choisie en fonction
du problème à traiter et de l’ordre de grandeur des erreurs auxquelles on peut s’attendre
sur a et b.
Ainsi, pour effectuer le test sin(x)==0, on n’utilisera pas l’instruction :
[Link](x)==0 # si x=pi, ceci retourne pourtant False
Lorsqu’on utilise l’instruction from math import *, il n’est plus nécessaire d’ajouter
le nom du module pour utiliser ses fonctions :
from math import * # module math
a=pi/4
Certaines fonctions portent le même nom dans des bibliothèques différentes. Il est donc
préférable de ne pas utiliser from math import * mais plutôt import math. On
peut renommer le module math en m par exemple :
import math as m # module math renommé m
a=[Link]/4
Voir exercice 1.4 « Affectation, objet immuable, copie » pour l’utilisation du module copy.
8
·
Chapitre 1 Prise en main de Python
Cours : N
Soit une liste de valeurs X1, X2… XN. La moyenne des valeurs est définie par : X =
1
N ∑X . i
i =1
2
La variance (ou écart quadratique moyen) est définie par : var ( X ) = X 2 − X avec
N
X2 =
1
N ∑ X . L’écart-type est défini par ∆X =
2
i var (X ) .
i =1
2.
def rec_variance(L):
# la fonction retourne la variance de la liste L
S=0 # initialisation de S à 0
n=len(L) # longueur de la liste L
for i in range(n): # i varie entre 0 inclus et n exclu
S=S+L[i]**2 # on pourrait écrire S+=L[i]**2
variance=S/n-rec_moy(L)**2
return variance # retourne la variance de L
3.
def rec_ecart_type(L):
#la fonction retourne l’écart-type(float) de la liste L
import math as m # module math renommé m
return([Link](rec_variance(L)))
Cours :
Une assertion est une aide de détection de bugs dans les programmes.
9
·
Partie 1 Prise en main de Python
•• La fonction rec_moy peut être appelée si le type de L est list. On ajoute la ligne
suivante dans la fonction def rec_moy2 :
assert type(L)==list
Le programme teste si len(L)>0, sinon on aurait une division par 0 dans la fonction.
Si la condition est vérifiée, le programme continue à s’exécuter normalement. Si la
condition len(L)>0 n’est pas vérifiée (on dit qu’on a une levée de l’assertion), alors
le programme Python s’arrête et affiche le message d’erreur :
assert len(L)>0 AssertionError
On supprime les assertions dans la version finale du programme Python.
4.
def rec_moy2(L:list)->float:
# la fonction retourne la moyenne (float) des éléments
# de la liste L
# On pourrait écrire : def rec_moy2(L:[float])->float:
# L est une liste de nombres flottants
assert type(L)==list
assert len(L)>0
S=0 # initialisation de S à 0
n=len(L) # longueur de la liste L
for i in range(n): # i varie entre 0 inclus et n exclu
assert type(L[i])==float or type(L[i])==int
S=S+L[i] # on pourrait écrire S+=L[i]
moyenne=S/n # calcul de la moyenne
return moyenne # retourne la moyenne de L
Remarques :
On peut ajouter une chaîne de caractères dans l’instruction assert :
assert type(L)==list, 'Le type de L doit être une liste.'
ou
assert type(L[i])==float or type(L[i])==int,\
"Type de L[i] non correct."
On peut ajouter des commentaires dans les programmes Python avec le symbole
dièse. Pour ajouter un commentaire qui s’étend sur plusieurs lignes, on peut le
commencer avec ''' (trois apostrophes) ou """ (trois guillemets) et le terminer
de la même façon :
'''
La fonction retourne la moyenne (float) des éléments de la liste L.
On pourrait écrire : def rec_moy2(L:[float])->float:
'''
Les assertions servent à tester des conditions critiques qui ne devraient jamais arri-
ver. Ce sont des aides au développement des programmes.
Si ces erreurs (liste vide, type de L incorrect, type de L[i] incorrect) sont suscep-
tibles d’arriver lors de l’exécution du programme final, alors il faut utiliser le test
if len(L)==0 et gérer par programmation l’erreur.
11
·
Partie 1 Prise en main de Python
Analyse du problème
Cet exercice permet de s’entraîner à manipuler les fonctions, les boucles, les tests
et les différents types rencontrés dans Python.
# programme principal
n=int(input('Taper un entier strictement positif : '))
# conversion en entier du résultat de la saisie
12
·
Chapitre 1 Prise en main de Python
# programme principal
n=1234
print(somcube(n)) # affiche 100 pour n = 1234
3.
def affiche_liste_entier_cube(): # pas d’argument d'entrée
# la fonction renvoie tous les nombres entiers strictement
# inférieurs à 1000 et égaux à la somme des cubes
# de leurs chiffres
L=[] # création d’une liste vide
for i in range(1000): # i varie entre 0 inclus et 1000 exclu
if i==somcube(i): # teste si i est égal à la somme
# des cubes de ses chiffres
[Link](i) # ajoute i dans la liste L
return L # fin de la fonction et renvoie la liste L
# programme principal
print(affiche_liste_entier_cube()) # affiche
# [0, 1, 153, 370, 371, 407]
4.
def somcube2(n):
# la fonction convertit l’entier n en une chaîne de caractères
# pour récupérer ses chiffres sous forme de caractères
somme=0
chaine=str(n) # convertit n en une chaîne de caractères
L=[] # création d’une liste vide
for elt in chaine: # elt prend successivement
# les éléments de chaine
[Link](elt) # elt est un caractère que l’on ajoute
# dans L
somme=somme+(int(elt))**3 # il faut convertir elt
# en entier
return L,somme # on pourrait écrire return(L, somme)
13
·
Partie 1 Prise en main de Python
# programme principal
n=int(input('Taper un entier strictement positif : '))
L1,res=somcube2(n) # L1 contient la liste des chiffres de n
# res = somme des cubes des chiffres de n
Remarque :
La fonction somcube2(n) renvoie un tuple contenant deux éléments. Pour récu-
pérer les éléments de ce tuple, on a plusieurs possibilités :
•• Dépaquetage d’un tuple :
La ligne return L, somme retourne un tuple : (L, somme).
Pour récupérer dans des variables séparées les éléments du tuple, on peut écrire :
L1, res=somcube2(25)
On obtient alors : L1=['2', '5'] et res=133.
•• On définit un tuple A :
A=somcube2(25)
Le tuple A vaut : (['2', '5'], 133).
Pour récupérer ['2', '5'], le premier élément du tuple : A[0].
Pour récupérer 133, le deuxième élément du tuple : A[1].
a=2
b=2
d=3
print("Print avant l’appel de la fonction f : a =", a)
print("Print avant l’appel de la fonction f : b =", b)
f()
print("Print après l’appel de la fonction f : a =", a)
print("Print après l’appel de la fonction f : b =", b)
Analyse du problème
Ce programme permet de comprendre la différence entre les variables globales et
les variables locales dans une fonction.
Cours :
Une variable locale est créée au début d’une fonction et est détruite lorsque la fonction est
terminée. Elle existe uniquement dans le corps de la fonction.
Une variable globale est définie à l’extérieur d’une fonction. Le contenu de cette variable est
visible à l’intérieur d’une fonction. L’instruction global b permet de définir la variable
globale b dans la fonction f.
Le programme Python affiche :
Print avant l’appel de la fonction f : a = 2
Print avant l’appel de la fonction f : b = 2
d = 3
Premier print dans la fonction f : b = 2
Deuxième print dans la fonction f : b = 7
Troisième print dans la fonction f : a = 3
Print après l’appel de la fonction f : a = 2
Print après l’appel de la fonction f : b = 7
La variable a vaut toujours 2 après l’exécution de la fonction f.
Dans le corps de la fonction f, a est une variable locale qui n’a rien à voir
avec la variable a définie dans le programme principal.
La variable b est modifiée par la fonction f car b est une variable globale
(instruction global b). On retrouve 7 après l’appel de la fonction f.
La variable c est une variable locale. Elle n’est pas définie en dehors de la
fonction. L’instruction print(c) en dehors de la fonction entraîne un
message d’erreur de Python.
La variable d n’est pas définie dans la fonction f. Python cherche alors la
valeur de d dans le programme principal. Python affiche alors : d = 3.
Remarque : L’instruction global i,j permet de désigner deux variables glo-
bales i et j dans une fonction.
15
·
Partie 1 Prise en main de Python
Analyse du problème
Ce programme permet de comprendre les problèmes rencontrés lors de copies de
listes, deques et dictionnaires (voir chapitre 11 « Dictionnaire, pile, file, deque »).
Cours :
Il existe deux catégories d’objets dans Python :
•• les objets dont la valeur peut changer sont dits muables (en anglais : mutable) : listes,
dictionnaires, deques… ;
•• les objets dont la valeur ne peut pas changer sont dits immuables (en anglais : immu-
table) : entiers, nombres flottants, booléens, chaînes de caractères, tuples…
Objets muables – Partage de valeurs par plusieurs variables
L1=[1, 2, 3, 4]
Cette affectation (ou assignation) est une instruction qui réalise les opérations suivantes :
•• Création d’un objet muable (appelé obj1) de type list à une adresse mémoire. Cet
objet possède un identifiant (adresse mémoire), un type et une valeur. La valeur de
obj1 vaut : [1, 2, 3, 4].
•• Création de la variable L1.
•• Association de la variable L1 avec l’objet obj1 contenant la valeur [1, 2, 3, 4].
16
·
Chapitre 1 Prise en main de Python
Cours :
Contrairement à d’autres langages de programmation (C ou Java), une affectation dans
Python est une association d’une variable avec un objet contenant la valeur. C’est le choix
des concepteurs du langage Python.
L2=L1
L’instruction L2=L1 n’affecte pas [1, 2, 3, 4] à L2 mais réalise les opérations sui-
vantes :
•• Création du nom de variable L2.
•• Affectation à la variable L2 de la référence (ou adresse mémoire) où est stocké [1,
2, 3, 4].
L1 et L2 font donc référence au même objet [1, 2, 3, 4].
La copie est très rapide puisqu’on n’occupe pas deux fois plus de place mémoire.
Si on modifie [1, 2, 3, 4] via L1, alors cette modification sera également visible
par L2.
L1[0]=10
On constate que L2[0] vaut 10 également. C’est tout à fait normal car L1 et L2 font réfé-
rence à la même adresse mémoire de [10, 2, 3, 4].
On ajoute un élément dans L1 avec la fonction append :
[Link](12)
17
·
Partie 1 Prise en main de Python
•• Création de la variable a.
•• Association de la variable a avec l’objet obj2 contenant la valeur 10.
Cours :
b=a
Cette instruction n’affecte pas 10 à la variable a mais affecte la référence (ou l’adresse
mémoire) où est stocké 10.
a=11
Comme on ne peut pas modifier 10 (objet immuable), on crée un nouvel objet 11 avec
une nouvelle adresse mémoire dans l’ordinateur. La variable a fait référence à l’adresse
mémoire où est stocké 11.
Par contre, b fait toujours référence à l’adresse mémoire où est stocké 10.
print(b) # b reste égal à 10
On retrouve le même résultat pour tous les objets immuables : entiers, nombres flottants,
booléens, chaînes de caractères, tuples…
Cours :
On rencontre deux catégories de copies pour les objets muables (listes, dictionnaires,
deques…) :
•• La fonction copy() réalise une copie superficielle. Les éléments sont copiés s’il
n’y pas de structure imbriquée. Si les éléments sont des listes par exemple, alors
l’adresse mémoire des listes est copiée.
•• La fonction deepcopy() réalise une copie profonde pour les structures imbri-
quées. Si les éléments sont des listes, alors la copie profonde copie bien les listes
imbriquées.
import copy
L2=[Link](L1)
18
·
Chapitre 1 Prise en main de Python
Python exécute une copie superficielle de L1, c’est-à-dire qu’il crée une nouvelle
liste L2 en copiant tous les éléments de L1 dans L2 puisqu’ils ne contiennent pas
de structure imbriquée. Dans ce cas, L1 et L2 ne font plus référence à la même
adresse mémoire.
La copie superficielle s’applique également aux dictionnaires et deques (voir cha-
pitre 11 « Dictionnaire, pile, file, deque »).
Remarque :
Avec certains langages (langage C++, Java par exemple), le typage des variables
est statique, c’est-à-dire qu’il faut d’abord déclarer (ou définir) le nom et le type
des variables et ensuite leur affecter (ou assigner) une valeur compatible avec le
type déclaré.
Avec le langage Python, le typage des variables est dynamique : l’interpréteur
détermine automatiquement le type qui correspond au mieux à la valeur fournie
lors de l’affectation.
1. Python affiche :
Avant modification de i : i, j = 3 3
Après modification de i : i, j = 5 3
Les résultats affichés dans Python sont tout à fait prévisibles. On va voir
dans la question 2 que la même syntaxe appliquée aux listes donne des
résultats surprenants !
2. Python affiche :
Avant modification de L2 : L1,L2 = [1, 3, 5, 7]
[1, 3, 5, 7]
Après modification de L2 : L1,L2 = [1, 3, 5, 2]
[1, 3, 5, 2]
Le programme de la question 2 est exactement le même que celui de la
question 1 sauf qu’on manipule des listes au lieu de manipuler des entiers.
Le comportement est complétement différent : la liste L1 a été modifiée !
L’instruction L2=L1 n’a pas effectué une copie de L1 dans L2 mais a
copié uniquement la référence de la liste, c’est-à-dire l’adresse mémoire de
la liste. L1 et L2 font donc référence à la même adresse mémoire de l’or-
dinateur. Si on modifie un élément de L2 alors L1 est également modifié.
3. Python affiche :
Avant modification de L4 : L3,L4 = [1, 3, 5, 7]
[1, 3, 5, 7]
Après modification de L4 : L3,L4 = [1, 3, 5, 7]
[1, 3, 5, 2]
L’instruction L4=[Link](L3) permet de réaliser une copie super-
ficielle de L3. Les listes L3 et L4 ont des adresses mémoire différentes.
19
·
Partie 1 Prise en main de Python
Exercice 1.5 : Passage par référence pour les listes, effet de bord
On considère le programme suivant :
def f(a, b, L):
a+=1
print('Print dans la fonction : a =', a)
b=b+1
print('Print dans la fonction : b =', b)
print('Print dans la fonction : d =', d)
[Link](4) # on ajoute un élément dans L
print('Print dans la fonction : L =', L)
return a
a=3
b=5
d=3
L=[1, 2, 3]
c=f(a, b, L)
print('Print après la fonction : a =', a)
print('Print après la fonction : b =', b)
print('Print après la fonction : c =', c)
print('Print après la fonction f : L =', L)
Analyse du problème
Ce programme permet de comprendre les problèmes rencontrés lors de l’utilisation
de listes dans les arguments d’entrée des fonctions.
20
·
Chapitre 1 Prise en main de Python
Cours :
Les arguments d’entrée des fonctions sont tous passés par référence. On considère deux
cas :
•• Objet muable (liste, dictionnaire, deque…) : toute modification de cet objet dans la
fonction est visible en dehors de la fonction. C’est « l’effet de bord » puisque la fonc-
tion modifie des données définies hors de sa portée locale.
•• Objet immuable (entier, nombre flottant, booléen, chaîne de caractères, tuple…) : toute
modification de cet objet dans la fonction n’est pas visible en dehors de la fonction.
Pour simplifier, tout se passe comme si ces objets étaient passés par valeur.
Python affiche :
Print dans la fonction : a = 4
Print dans la fonction : b = 6
Print dans la fonction : d = 3
Print dans la fonction : L = [1, 2, 3, 4]
Print après la fonction : a = 3
Print après la fonction : b = 5
Print après la fonction : c = 4
Print après la fonction f : L = [1, 2, 3, 4]
La fonction f retourne la valeur 4 qui est affectée dans la variable c.
Avant l’appel de la fonction f, la variable b fait référence à 5. La variable
b est passée par référence dans la fonction f et fait toujours référence à 6.
L’instruction b=b+1 dans la fonction f ne peut affecter 5 qui est immuable.
La variable b dans la fonction f fait donc référence à une nouvelle valeur 6.
La variable b du programme principal garde donc la même valeur 6.
Pour simplifier, cela revient à dire que les variables a et b sont passées par
valeur : l’exécution de la fonction f évalue d’abord a et b puis exécute f
avec les valeurs calculées a et b.
La variable L fait référence à la liste [1, 2, 3] qui est un objet muable.
La liste L est passée par référence. Lorsqu’on modifie L dans la fonction f,
on modifie la liste [1, 2, 3].
La variable L dans la fonction f fait référence à la même adresse mémoire
que la variable L dans le programme principal.
Lorsqu’une expression fait référence à une variable à l’intérieur d’une fonc-
tion (variable d par exemple), Python cherche la valeur définie à l’intérieur
de la fonction et à défaut la valeur dans l’espace global du programme.
Remarque : Voir l’exercice précédent, « Affectation, objet immuable, copie »,
pour avoir une copie profonde avec la fonction deepcopy().
21
·
Partie 1 Prise en main de Python
Analyse du problème
La technique du slicing, ou extraction de tranche, permet d’extraire des éléments
d’une liste.
Cours :
Lorsqu’on veut extraire des éléments d’une liste, d’un tuple ou d’une chaîne de caractères,
on utilise la technique du slicing, ou extraction de tranche. Il suffit de mettre entre crochets
les indices correspondant au début et à la fin de la « tranche ». On utilise la syntaxe :
L[start:stop]
Cours :
On peut utiliser l’extraction de tranche avec un pas différent de 1. On utilise alors la syntaxe
suivante :
L[start:stop:step]
22
·
Chapitre 1 Prise en main de Python
Cours :
On utilise la même technique pour les tuples et les chaînes de caractères.
L=(3, 5, 8, -2) # tuple
L2=L[0:3] # L2=(3, 5, 8)
c="C’est un mot" # chaîne de caractères
c2=c[0:3] # c2="C’e"
Python affiche :
L1 = [2, 4, 6]
[2, 4]
Liste L1 : i varie entre 2 inclus et 7 exclu avec un pas de 2.
L1[:-1] extrait les éléments de L1 : le dernier élément de L1 est exclu.
23
Graphiques 2
Exercice 2.1 : Tracé d’une fonction avec matplotlib
On considère les fonctions f1 et f2 définies sur [0, 2] par :
x pour 0 ≤ x < 1
f1 ( x ) = et f2 ( x ) = sin ( x ) + 0, 1.
1 pour 1 ≤ x ≤ 2
Les fonctions suivantes permettent le tracé de fonctions :
import [Link] as plt # module [Link] renommé plt
[Link]()
# nouvelle fenêtre graphique
[Link](x, y, color='r', linewidth=3, marker='o')
# color : choix de la couleur
# ('r' : red, 'g' : green, 'b' : blue, 'black' : black)
# linewidth : épaisseur du trait
# marker : différents symboles '+', '.', 'o', 'v'
# linestyle : style de la ligne ('-' ligne continue,
# '--' ligne discontinue, ':' ligne pointillée)
[Link](x, y, '*') # points non reliés représentés par '*'
[Link]() # affichage de la grille
[Link]('Titre') # ajout d’un titre
[Link]('axe x') # affiche 'axe x' en abscisse d’un graphique
[Link]('axe y') # affiche 'axe y' en ordonnée d’un graphique
[Link] ([xmin, xmax, ymin, ymax]) # précise les bornes pour les
# abscisses et les ordonnées
[Link](['courbe 1', 'courbe 2']) # permet de légender les courbes
[Link]() # affiche la figure à l’écran
25
·
Partie 1 Prise en main de Python
Analyse du problème
Il faut bien connaître les fonctions suivantes pour tracer une fonction :
import [Link] as plt # module [Link] renommé plt
[Link]() # nouvelle fenêtre graphique
[Link](x, y) # représentation graphique de y en fonction de x
[Link]() # affiche la figure à l’écran
Cours :
Le module [Link] de la bibliothèque matplotlib permet d’afficher
des graphiques. On l’importe à l’aide de la commande :
import [Link] as plt # module [Link] renommé plt
26
·
Chapitre 2 Graphiques
27
·
Partie 1 Prise en main de Python
Analyse du problème
Voir exercice précédent « Tracé d’une fonction avec matplotlib » pour l’affichage
du titre, de l’axe des abscisses et de l’axe des ordonnées.
Il faut bien connaître les fonctions suivantes pour tracer un histogramme :
import [Link] as plt # module [Link] renommé plt
[Link]() # nouvelle fenêtre graphique
[Link](L) # tracé de l’histogramme
[Link]() # affiche la figure à l’écran
28
Partie 2
Terminaison,
correction,
complexité
Plan
3. Terminaison, correction, complexité 31
3.1 : Comparaison de deux listes (Mines Ponts 2017) 31
3.2 : Amélioration de la complexité (Mines Ponts 2018) 34
3.3 : Décomposition en base b d’un entier (CCP MP Maths 2015) 36
3.4 : Recherche du nombre de zéros (banque PT 2015) 39
Terminaison,
correction, complexité
3
Exercice 3.1 : Comparaison de deux listes (Mines Ponts 2017)
1. Proposer une fonction egal(L1, L2) retournant un booléen permettant de
savoir si deux listes L1 et L2 sont égales.
2. Que peut-on dire de la complexité de cette fonction ?
3. Préciser le type de retour de cette fonction.
Analyse du problème
On se place dans le pire des cas avec deux listes égales. On calcule le nombre total
d’opérations élémentaires pour déterminer la complexité de cette fonction.
Cours :
Terminaison d’un programme
Un programme itératif est constitué d’une boucle for ou while. On cherche à démontrer
que cette boucle se termine.
On considère un variant de boucle, par exemple un entier naturel qui décroît à chaque ité-
ration de la boucle et qui atteindra 0 à un moment, ce qui permet de montrer que la boucle
se termine.
On considère le programme suivant qui cherche un élément dans une liste non triée.
L=[3, 1, 6, 9, 19, -1,20]
def rec_pos(L, x):
# la fonction renvoie True et i l’indice si x est dans la liste L,
# False sinon
i=0 # initialisation de l’indice i
n=len(L)
while i<n:
if x==L[i]:
return True,i # return provoque un arrêt de boucle
# si x est dans L
i=i+1
return False, -1 # l’élément n’est pas trouvé
print(rec_pos(L,6)) # le programme affiche : (True, 2)
31
·
Partie 2 Terminaison, correction, complexité
32
·
Chapitre 3 Terminaison, correction, complexité
La complexité est une mesure du nombre d’opérations élémentaires que l’algorithme effec-
tue. Si on se place dans les conditions les plus favorables, on calculera la complexité dans
le meilleur des cas. Si on se place dans les conditions les plus défavorables, on calculera la
complexité dans le pire des cas.
On considère le programme suivant, qui cherche le maximum d’une liste non triée.
def rec_max(L):
# la fonction renvoie le maximum des éléments de la liste L
maxi=L[0]
n=len(L) # nombre d’éléments de L
for i in range(1, n): # i varie entre 1 inclus et n exclu
if L[i]>maxi:
maxi=L[i]
return maxi
1.
def egal(L1, L2):
# la fonction renvoie True si les deux listes L1 et L2
# sont égales, False sinon
if len(L1)!=len(L2): # listes de longueurs différentes
return False
else:
for i in range(len(L1)):# parcourt tous les éléments de L1
if L1[i]!=L2[i]:
return False
33
·
Partie 2 Terminaison, correction, complexité
return True
L1=[3, 2, 5, 8]
L2=[3, 2, 5, 8]
print(egal(L1, L2) # retourne True
2. On se place dans le pire des cas avec deux listes égales. On appelle n la
longueur de la liste L1.
On calcule le nombre d’opérations élémentaires de la fonction egal(L1,
L2) :
•• 3 opérations élémentaires : appel de la longueur de L1, appel de la
longueur de L2, test.
•• À chaque appel de la boucle for : 3 opérations élémentaires (test et
appel de L1[i], L2[i]).
On a donc 3 + 3n opérations élémentaires.
La complexité est linéaire en O(n).
Remarque : On peut accepter des petites différences dans l’évaluation du nombre
total d’opérations élémentaires. La complexité de l’algorithme ne sera pas modi-
fiée.
∑(H − H)
1
× 3 ×
n 3
S= et
( n − 1)( n − 2) σ i =1
i
3 ( n − 1)
n 2
∑(H − H)
1
× ×
n 4
K= −
( n − 1)( n − 2)( n − 3) σ 4 i =1
i
( n − 2)( n − 3)
On suppose disposer de la fonction ecartType qui permet de retourner la
valeur de l’écart-type non biaisé σ .
34
·
Chapitre 3 Terminaison, correction, complexité
1. Proposer une fonction moyenne prenant en argument une liste non vide L
et retournant sa valeur moyenne.
2. Un codage de la fonction skewness pour une liste ayant au moins 3 élé-
ments est donné ci-dessous. Le temps d’exécution est anormalement long. Pro-
poser une modification simple de la fonction pour diminuer le temps d’exécution
(sans remettre en cause le codage des fonctions ecartType et moyenne).
def skewness (liste_hauteurs):
n=len(liste_hauteurs)
et3=(ecartType(liste_hauteurs))**3
S=0
for i in range(n):
S+=(liste_hauteurs[i]-moyenne(liste_hauteurs))**3
S=n/(n-1)/(n-2)*S/et3
return S
Analyse du problème
On calcule le nombre total d’opérations élémentaires pour déterminer la complexité
de cette fonction.
1.
def moyenne(L):
# la fonction renvoie la valeur moyenne de la liste L
som=0 # initialisation de som à 0
n=len(L) # nombre d'éléments de L
for i in range(n): # i varie entre 0 inclus et n exclu
som=som+L[i]
return(som/n)
35
·
Partie 2 Terminaison, correction, complexité
S=0
for i in range(n):
S+=(liste_hauteurs[i]-moy)**3
S=n/(n-1)/(n-2)*S/et3
return S
Pour k ∈ ℕ*, on note ck, tk et nk les valeurs prises par les variables c, t et n à
la sortie de la k-ième itération de la boucle while. Quelle liste est renvoyée
lorsque l’on exécute mystere(256,10) ?
On recopiera et complétera le tableau suivant, en ajoutant les éventuelles
colonnes nécessaires pour tracer entièrement l’exécution.
k 1 2 …
ck …
tk …
nk …
3. Soit n > 0 un entier. On exécute mystere(n,10). On pose n0 = n.
a. Justifier la terminaison de la boucle while.
b. On note p le nombre d’itérations lors de l’exécution de mystere(n,10).
n
Justifier que, pour tout k ∈[ 0, p ], on a nk ≤ k . En déduire une majoration de
10
p en fonction de n.
4. En s’aidant du script de la fonction mystere, écrire une fonction somme_
chiffres qui prend en argument un entier naturel et renvoie la somme de ses
chiffres. Par exemple, somme_chiffres(256) devra renvoyer 13.
5. Écrire une version récursive de la fonction somme_chiffres, on la nom-
mera somme_chiffres_rec.
36
·
Chapitre 3 Terminaison, correction, complexité
Analyse du problème
On étudie dans cet exercice, extrait du concours CCP MP Maths 2015, la décompo-
sition en base b d’un entier. La méthode est d’effectuer des divisions euclidiennes
successives pour obtenir la liste des chiffres de la décomposition en base b d’un
entier.
Remarque :
On peut effectuer les divisions euclidiennes suivantes :
a) Division euclidienne de l’entier 21 par 2 :
21//2 = 10 = quotient
21%2 = 1 = reste
Le premier reste fournit le premier chiffre du code binaire, c’est-à-dire 1010 1 b.
b) Division euclidienne du quotient précédent par 2 :
10//2 = 5
10%2 = 0
Le deuxième reste fournit le deuxième chiffre du code binaire, c’est-à-dire
101 0 1b.
c) Division euclidienne du quotient précédent par 2 :
5//2 = 2
5%2 = 1
d) Division euclidienne du quotient précédent par 2 :
2//2 = 1
2%2 = 0
e) Division euclidienne du quotient précédent par 2 :
1//2 = 0
1%2 = 1
On en déduit que : 21 = 10101b = 24 + 22 + 1 = 1 + 2 × ( 0 + 2 × ( 1 + 2 × ( 0 +
2 × ( 1 )))).
On peut envisager une boucle où on effectue les divisions euclidiennes successives.
On termine la boucle dès que le quotient est nul.
Cet algorithme permet d’effectuer la division euclidienne de l’entier n par deux
jusqu’à ce que le résultat soit nul. La suite des restes donne le code binaire en ordre
inverse.
37
·
Partie 2 Terminaison, correction, complexité
2.
k 1 2 3
ck 256%10 = 6 25%10 = 5 2%10 = 2
tk [6] [6, 5] [6, 5, 2]
nk 25 2 0
38
·
Chapitre 3 Terminaison, correction, complexité
Cours :
Dans toute fonction récursive, l’instruction return doit être présente au moins deux fois :
une fois pour la condition d’arrêt (premier return dans le programme) et une autre fois
pour l’appel récursif (dernier return dans le programme)
5.
def somme_chiffres_rec(n, b):
"""Données: n > 0 un entier et b > 0 un entier
Résultat: ......."""
if n==0:
return 0 # condition d’arrêt
else:
return n%b + somme_chiffres_rec(n//b,b) # appel
# récursif
Remarque :
L’entier 37 s’écrit 100101b en binaire. On utilise une liste contenant les valeurs
des différents bits. Il existe deux conventions pour repérer les bits dans une
liste :
•• L = [1,0,0,1,0,1] : L[0] représente le bit de poids le plus fort et L[5] représente le
bit de poids le plus faible.
•• L = [1,0,1,0,0,1] : L[0] représente le bit de poids le plus faible et L[5] représente
le bit de poids le plus fort.
Il faut bien regarder si l’énoncé impose une convention. Sinon il faut bien la définir
dans le programme pour éviter toute ambiguïté. La fonction mystere(37,2)
retourne alors : [1, 0, 1, 0, 0, 1]. On utilise donc la deuxième convention
dans tout l’exercice.
39
·
Partie 2 Terminaison, correction, complexité
dire figurant dans des cases consécutives). Par exemple, le nombre maximal de
zéros contigus de la liste L1 suivante vaut 4 :
i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
L1[i] 0 1 1 1 0 0 0 1 0 1 1 0 0 0 0
Analyse du problème
Dans cet exercice, on parcourt une liste pour déterminer le nombre maximal de
zéros contigus dans celle-ci. On verra comment améliorer l’algorithme. Cet exer-
cice est extrait du sujet de concours 0 de la banque PT 2015.
1.
def nombreZeros(L, i):
# la fonction renvoie nbr_zeros pour la liste L
# et un indice i (int)
if L[i]==1:
return 0
else:
nbr_zeros=0
j=i
while j<len(L) and L[j]==0:
# il faut mettre j<len(L) avant L[j]
# sinon message dʼerreur pour j=len(L)
nbr_zeros+=1 # incrémente de 1
# le nombre de zéros
j+=1
return nbr_zeros
40
·
Chapitre 3 Terminaison, correction, complexité
41
·
Partie 2 Terminaison, correction, complexité
42
Partie 3
Algorithmes de
recherche
Plan
4. Algorithmes 45
4.1 : Recherche du minimum et du maximum d’une liste
de nombres, complexité 45
4.2 : Assertion. Recherche du maximum, du second
maximum d’une liste 46
4.3 : Recherche d’un mot dans un texte, boucles imbriquées 47
5. Algorithmes de dichotomie 51
5.1 : Recherche d’un élément dans une liste non triée,
algorithme naïf, complexité 51
5.2 : Recherche dichotomique dans une liste triée, complexité 52
Algorithmes 4
Exercice 4.1 : Recherche du minimum et du maximum d’une
liste de nombres, complexité
On considère la liste de nombres : L=[9, 10, 11, 56, 15, 16, 12,
18, 20, 12, -5, -8].
1. Écrire une fonction rec_min qui admet comme argument une liste non
vide de nombres. Cette fonction retourne le minimum de cette liste. On n’utili-
sera pas la fonction min.
2. Écrire une fonction rec_max qui admet comme argument une liste non
vide de nombres. Cette fonction retourne le maximum de cette liste. On n’uti-
lisera pas la fonction max.
3. Évaluer la complexité de ces deux fonctions dans le cas le moins favorable.
Analyse du problème
On considère une liste non vide. On définit une variable mini définie par le pre-
mier élément de la liste. On parcourt la liste en comparant chaque élément de la
liste à la variable mini.
1.
def rec_min(L):
# la fonction retourne le minimum de la liste L
mini=L[0] # ne pas utiliser la variable min
# cʼest une fonction Python pour avoir le minimum : min(L)
for i in range(len(L)):
if L[i]<mini:
mini=L[i]
return mini
Remarques :
•• Ne pas utiliser « − » mais « _ » dans les noms de variables et de fonctions.
•• La fonction min(L) de Python retourne le minimum d’une liste de valeurs.
2.
def rec_max(L):
# la fonction retourne le maximum de la liste L
maxi=L[0] # ne pas utiliser la variable max
# cʼest une fonction Python pour avoir
# le maximum : max(L)
for i in range(len(L)):
if L[i]>maxi:
45
·
Partie 3 Algorithmes de recherche
maxi=L[i]
return maxi
Analyse du problème
On considère une liste non vide contenant au moins 2 éléments. On définit une
variable max1 définie par le premier élément de la liste ainsi que indmax1 l’indice
du premier maximum. On parcourt une fois la liste en comparant chaque élément
de la liste à la variable max1.
On parcourt une seconde fois la liste pour déterminer le second maximum en s’as-
surant que l’indice du second maximum est différent de indmax1.
46
·
Chapitre 4 Algorithmes
1.
def rec_max2(L):
# la fonction retourne le maximum et le second maximum
# de la liste L
n=len(L) # nombre dʼéléments de la liste L
assert n>=2
# recherche du premier maximum
indmax1=0
max1=L[0]
for i in range(1, n): # i varie entre 1 inclus et n exclu
if L[i]>max1:
max1=L[i] # valeur du premier maximum
indmax1=i # indice du premier maximum
# recherche du second maximum
# lʼindice du 2nd maximum est différent du 1er maximum
if indmax1==0: # indice du premier maximum = 0
max2=L[1]
else: # indice du premier maximum différent de 0
max2=L[0]
for i in range(1, n): # i varie entre 1 inclus et n exclu
if L[i]>max2 and i!=indmax1:
# lʼindice i doit être différent de indmax1
max2=L[i] # valeur du second maximum
return max1, max2
47
·
Partie 3 Algorithmes de recherche
Analyse du problème
On parcourt la chaîne de caractères texte jusqu’à ce qu’on trouve le premier carac-
tère de mot. On parcourt ensuite successivement tous les caractères de mot pour savoir
s’ils sont présents les uns à la suite des autres. On utilise deux boucles for imbriquées.
2.
def recherche_mot_occurrence(texte, mot):
# la fonction retourne le nombre dʼoccurrences où mot(str)
# est présent dans texte(str) ainsi que la liste des indices
# de la première lettre des occurrences de mot
nbr_rep=0
i=0
liste=[]
while i<=(len(texte)-len(mot)):
j=0
while j<=(len(mot)-1) and mot[j]==texte[i+j]:
j+=1
if j==len(mot): # le mot est bien présent
nbr_rep+=1
[Link](i)
48
·
Chapitre 4 Algorithmes
i+=1
return nbr_rep, liste
49
Algorithmes de
dichotomie
5
Exercice 5.1 : Recherche d’un élément dans une liste
non triée, algorithme naïf, complexité
On considère la liste : L=[16, 9, 11, 32, 15, 17, 18, 10, 25].
1. Écrire une fonction rec_elt1 qui admet comme arguments une liste L non
triée et un élément x. Cette fonction retourne True si x est dans la liste, False
sinon.
2. Évaluer la complexité de cet algorithme pour une liste de longueur n dans le
cas le moins favorable.
3. Écrire une fonction rec_elt2 qui admet comme arguments une liste et
un élément à rechercher. Cette fonction retourne True si l’élément est présent
dans la liste ainsi que l’indice de la première occurrence dans la liste. Si l’élé-
ment n’est pas présent, cette fonction retourne False et -1.
Analyse du problème
On parcourt la liste en partant du premier élément jusqu’à ce qu’on trouve x. On
étudiera dans l’exercice suivant la méthode dichotomique, qui ne s’applique qu’aux
listes triées.
51
·
Partie 3 Algorithmes de recherche
52
·
Chapitre 5 Algorithmes de dichotomie
Analyse du problème
La méthode dichotomique utilise le fait que la liste est triée. Elle consiste à compa-
rer l’élément recherché à l’élément se trouvant au milieu d’une liste triée. Comme
la liste est triée, cela permet d’éliminer une moitié de la liste comme emplacement
possible de l’élément, sauf si on l’a déjà trouvé. Ensuite, on prend la moitié de la
liste qui reste et on recommence…
Voir exercice 6.5 « Recherche dichotomique dans une liste triée, version récur-
sive » dans le chapitre « Récursivité » pour une version récursive de ce programme.
Cours :
La méthode dichotomique divise le problème initial et élimine une partie des données.
On verra la méthode générale « diviser pour régner » qui profite de la subdivision pour
effectuer moins de calculs : voir l’exercice 6.2 « Exponentiation naïve, exponentiation
rapide » dans le chapitre « Récursivité », et les exercices 10.3 « Tri rapide » et 10.4 « Tri
par partition-fusion » dans le chapitre «Tris ».
1.
def rec_dicho(L, x):
# la fonction retourne True si x est dans la liste L,
# False sinon, et l’indice de l’élément recherché
# s’il est présent dans la liste
deb, fin=0, len(L)-1
rep=False
while fin>=deb and rep==False:
milieu=(deb+fin)//2
if x==L[milieu]:
rep=True
elif x>L[milieu]: # x est dans la deuxième moitié
deb=milieu+1
else: # x est dans la première moitié
fin=milieu-1
return rep, milieu
53
·
Partie 3 Algorithmes de recherche
Remarque :
On peut noter également la complexité : O ( log n ).
On peut accepter des petites différences dans l’évaluation du nombre total d’opéra-
tions élémentaires. La complexité de l’algorithme ne sera pas modifiée.
3. La complexité de l’algorithme naïf est linéaire alors que la complexité de
l’algorithme dichotomique est logarithmique. On a une recherche d’un élé-
ment dans une liste beaucoup plus rapide avec l’algorithme dichotomique
pour des listes comportant un grand nombre d’éléments.
54
Partie 4
Récursivité
Plan
6. Récursivité 57
6.1 : Factorielle d’un entier naturel 57
6.2 : Exponentiation naïve, exponentiation rapide 60
6.3 : Tours de Hanoï 65
6.4 : Recherche du pgcd (CCP MP Maths 2016) 69
6.5 : Recherche dichotomique dans une liste triée, version récursive 73
6.6 : Dessins de fractales 75
6.7 : Suite des nombres de Fibonacci 80
Récursivité 6
Exercice 6.1 : Factorielle d’un entier naturel
On souhaite calculer la factorielle d’un entier naturel n.
1. Écrire une fonction fact qui admet comme argument un entier naturel n et
qui retourne la valeur de la factorielle de n en utilisant un programme itératif.
2. Écrire une fonction fact_rec qui admet comme argument un entier natu-
rel n et qui retourne la valeur de la factorielle de n en utilisant un programme
récursif.
3. Démontrer la terminaison pour la fonction fact_rec.
4. Représenter les différentes activations de la fonction récursive fact_
rec(3) sous la forme d’un arbre.
5. Démontrer la correction de la fonction fact_rec.
6. Évaluer la complexité de la fonction fact_rec.
7. Que se passe-t-il si on exécute fact_rec(-3) ?
Analyse du problème
On va étudier la différence entre une fonction itérative et une fonction récursive.
Les méthodes mises en place dans cet exercice seront utilisées dans de très nom-
breux exercices concernant les fonctions récursives.
Cours :
Une fonction est récursive lorsque le corps de cette fonction fait appel à cette même fonc-
tion (c’est une fonction qui s’appelle elle-même). Sinon, on dit que cette fonction est itéra-
tive (elle peut être constituée de boucles while ou for).
Il est essentiel de prévoir qu’une procédure récursive se termine ! L’instruction return
doit être présente au moins deux fois :
•• une fois pour la condition d’arrêt (premier return dans le programme) ;
•• une autre fois pour l’appel récursif (dernier return dans le programme).
1.
def fact (n):
# la fonction renvoie la factorielle d’un entier naturel n
# programme itératif
res=1
for i in range(1, n+1): # i varie entre 1 inclus et n+1 exclu
57
·
Partie 4 Récursivité
res=res*i
return res
2.
def fact_rec(n):
# la fonction renvoie la factorielle d’un entier naturel n
# programme récursif
if n==0:
return (1) # condition d’arrêt
else:
return (n*fact_rec(n-1)) # rappel récursif
Cours :
Pour démontrer la terminaison d’un programme, on cherche une grandeur positive, que
l’on appelle variant de boucle, qui décroît entre deux appels de la fonction récursive et qui
converge vers une valeur d’un cas correspondant à un appel de la condition d’arrêt.
De façon générale, il faut montrer que l’on arrivera en un nombre fini d’étapes à un appel
de la condition d’arrêt.
3. On considère le variant de boucle n. À chaque appel de la fonction récur-
sive, il décroît d’une unité et finit par atteindre la valeur 0 correspondant
à une condition d’arrêt. Le programme se termine donc dans tous les cas
si n ≥ 0 .
4. L’arbre ci-dessous représente les différents appels de la fonction fact_
rec(3).
Les différents appels de la fonction récursive sont stockés dans une pile :
c’est la phase de descente. Quand on atteint la condition d’arrêt, on passe
à la phase de remontée et les appels sont désempilés jusqu’à retourner à
l’appel initial.
main()
6
fact_rec(3)
2
fact_rec(2)
1
fact_rec(1)
1
fact_rec(0)
58
·
Chapitre 6 Récursivité
Remarque : Dans l’exercice 10.4 « Tri par partition-fusion » dans le chapitre « Tris »,
l’arbre des appels de la fonction récursive ressemble encore plus à un « arbre » !
Remarque :
Dans la phase de descente, les appels successifs sont stockés dans une pile.
Une fois que la condition d’arrêt est obtenue, les appels sont ensuite désempilés
jusqu’à arriver à l’appel initial dans la phase de montée.
Le nombre d’appels récursifs est limité à 1 000 avec Python. Tout dépassement
provoquera une erreur.
Pour calculer la factorielle de n, on applique la fonction fact_rec à plusieurs
sous-problèmes. Cette méthode de décomposition/recomposition est appelée divi-
ser pour régner. On utilisera cette méthode dans les algorithmes de tri.
Cours :
Pour démontrer la correction d’un programme, il faut montrer que l’algorithme effectue
bien la tâche souhaitée. On utilise souvent une démarche proche du raisonnement par récur-
rence.
On établit une propriété (appelée invariant de boucle) Pn :
•• la propriété Pn doit être vraie pour n = 0 ;
•• si Pn est vraie, alors Pn+1 doit être vraie.
59
·
Partie 4 Récursivité
Cours :
La complexité est une mesure du nombre d’opérations élémentaires que l’algorithme effec-
tue. On évalue la complexité d’une fonction récursive à partir d’une relation de récurrence.
60
·
Chapitre 6 Récursivité
Analyse du problème
Une fonction est récursive lorsque le corps de cette fonction fait appel à cette même
fonction. On va étudier plusieurs améliorations pour calculer la puissance d’un
nombre réel.
1.
def puiss(x, n):
# la fonction renvoie x**n avec x réel et n entier > 0
res=1
for i in range(n): # i varie entre 0 inclus et n exclu
res=res*x
return res
2.
def puiss_rec(x, n):
# la fonction renvoie x**n avec x réel et n entier > 0
# calcule x**n avec x réel et n>0
if n==0:
return 1 # condition d’arrêt avec x**0=1
else:
return (x*puiss_rec(x, n-1)) # appel récursif
61
·
Partie 4 Récursivité
Remarque :
Il est essentiel de prévoir qu’une procédure récursive se termine ! L’instruction
return doit être présente au moins deux fois :
•• une fois pour la condition d’arrêt (premier return dans le programme),
•• une autre fois pour l’appel récursif (dernier return dans le programme).
x=float(input('Entrez un réel x : '))
n=int(input('Entrez un entier positif n : '))
print('Le résultat x**n = ', puiss_rec(x, n))
62
·
Chapitre 6 Récursivité
( )
T n = 2k = uk = ak ( u0 − r ) + r = 2k 1 −
4
+
4
1 − 2 1 − 2
= 5n − 4.
63
·
Partie 4 Récursivité
64
·
Chapitre 6 Récursivité
Remarques :
•• La méthode « diviser pour régner » profite de la subdivision pour effectuer moins
de calculs (voir les exercices 10.3 « Tri rapide » et 10.4 « Tri par partition-
fusion » dans le chapitre «Tris »).
•• La méthode dichotomique divise uniquement le problème initial et élimine une
partie des données (voir exercice 5.2 « Recherche dichotomique dans une liste
triée, complexité » dans le chapitre « Algorithmes de dichotomie »).
On définit la liste tour : tour[0] est une liste représentant les disques de la
tour A, tour[1] (respectivement tour[2]) représente les disques de la tour
B (respectivement tour C).
Par exemple, pour n = 4, on a : tour = [[4, 3, 2, 1], [], []].
65
·
Partie 4 Récursivité
Analyse du problème
L’utilisation d’une fonction récursive permet de résoudre facilement le problème
de Hanoï. La question 2 permet de comprendre la fonction récursive hanoi.
Les différents schémas montrent comment déplacer 4 tours sachant que l’on sait
résoudre le problème pour 3 tours.
Il reste à déplacer les n−1 = 3 disques (en pointillés sur le schéma ci-des-
sus) de la tour B vers la tour C.
3. On met en place un programme récursif. On a vu dans la question
précédente que l’on pouvait déplacer les 4 disques à condition de savoir
déplacer 3 disques. Pour déplacer les 3 disques d’une tour vers une
autre, on applique le programme récursif à 2 disques. Pour déplacer les
2 disques, on applique le programme récursif à 1 disque que l’on sait
déplacer.
def hanoi(tour, n, a, b, c):
# a : tour de départ (a peut être égal à 0, 1 ou 2)
# b : tour intermédiaire (b peut être égal à 0, 1 ou 2)
# c : tour d’arrivée (c peut être égal à 0, 1 ou 2)
67
·
Partie 4 Récursivité
68
·
Chapitre 6 Récursivité
F0 = 0, F1 = 1, ∀n ∈ , Fn + 2 = Fn + 1 + Fn
a. Écrire les divisions euclidiennes successivement effectuées lorsque l’on cal-
cule le pgcd de F6 = 8 et F5 = 5 avec la fonction euclide.
b. Soit n ≥ 2 un entier. Quel est le reste de la division euclidienne de Fn+2 par
Fn+1 ? On pourra utiliser librement le fait que la suite (Fn)n ∈ est strictement
croissante à partir de n = 2. En déduire, sans démonstration, le nombre un de
divisions euclidiennes effectuées lorsque l’on calcule le pgcd de Fn+2 et Fn+1
avec la fonction euclide.
5. Écrire une fonction fibo qui prend en argument un entier naturel n et ren-
voie le nombre de Fibonacci Fn. Par exemple, fibo(6) renverra 8.
6. Écrire une fonction récursive fibo_rec qui permet de renvoyer le nombre
de Fibonacci.
7. En utilisant la fonction euclide, écrire une fonction gcd_trois qui ren-
voie le pgcd de trois entiers naturels. Par exemple, gcd_trois(18, 30,
12) renverra 6.
69
·
Partie 4 Récursivité
Analyse du problème
On étudie dans cet exercice l’algorithme d’Euclide permettant de calculer le pgcd
de deux entiers naturels. Cet exercice est extrait du concours CCP MP Maths 2016.
Cours :
Dans toute procédure récursive, l’instruction return doit être présente au moins deux
fois : une fois pour la condition d’arrêt (premier return dans le programme) et une autre
fois pour l’appel récursif (dernier return dans le programme).
3.
def euclide_rec(a, b):
# la fonction renvoie le pgcd de deux entiers naturels
# algorithme d’Euclide
if b==0: # condition d’arrêt
return a
else:
return euclide_rec(b,a%b) # appel récursif
Remarque :
Les appels successifs d’une fonction récursive sont stockés dans une pile.
Prenons l’exemple suivant : pgcd(16,12).
Appel de euclide_rec(12,4)
Appel de euclide_rec(4,0)
Retour de 4
70
Retour de 4
·
Chapitre 6 Récursivité
4. a.
•• 1er appel de la boucle : a = F6 = 8 et b = F5 = 5.
Le reste de la division euclidienne de 8 par 5 vaut 3. Le quotient vaut 1.
On a F4 = 3.
a = 5 et b = 3.
•• 2e appel de la boucle : a = F5 = 5 et b = F4 = 3.
Le reste de la division euclidienne de 5 par 3 vaut 2. Le quotient vaut 1.
On a F3 = 2.
a = 3 et b = 2.
•• 3e appel de la boucle : a = F4 = 3 et b = F3 = 2.
Le reste de la division euclidienne de 3 par 2 vaut 1. Le quotient vaut 1.
On a F2 = 1.
a = 2 et b = 1.
•• 4e appel de la boucle : a = F3 = 2 et b = F2 = 1.
Le reste de la division euclidienne de 2 par 1 vaut 0.
a = 1 et b = 0.
On n’a plus d’appel de la boucle et le programme retourne 1.
b. La suite de Fibonacci est définie par : Fn+2 = Fn+1 + Fn et 0 ≤ Fn < Fn+1.
On en déduit que le reste de la division euclidienne de Fn+2 par Fn+1 est Fn.
D’après la question précédente :
•• 1er appel de la boucle : division euclidienne de Fn+2 par Fn+1.
•• 2e appel de la boucle : division euclidienne de Fn+2 par Fn.
•• …
•• Le dernier appel de la boucle correspond à la division euclidienne de F3
par F2. Le reste est nul et l’algorithme retourne 1.
On obtient alors la suite de valeurs :
F0 = 0
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
Le nombre de divisions euclidiennes effectuées lorsqu’on calcule le pgcd de
Fn+2 et Fn+1 est n.
5. a) Première version du programme, en utilisant une liste F pour stocker
tous les résultats intermédiaires.
def fibo1(n):
# renvoie le nombre de Fibonacci Fn pour l’entier naturel n
if n==0:
return 0
71
·
Partie 4 Récursivité
elif n==1:
return 1
else:
F=[]
[Link](0)
[Link](1)
for i in range(2, n+1):
[Link](F[i-1]+F[i-2])
return F[i]
c) Troisième version
On peut remplacer les trois lignes dans la boucle par une seule ligne : F_2,
F_1=F_1, F_2+F_1.
def fibo3(n):
# renvoie le nombre de Fibonacci Fn pour l’entier naturel n
if n==0:
return 0
elif n==1:
return 1
else:
# F[n]=F[n-1]+F[n-2]
F_2=0 # F[n-2]
F_1=1 # F[n-1]
for i in range(2, n+1):
F_2, F_1=F_1, F_2+F_1
return F_1
6.
def fibo_rec(n):
# renvoie le nombre de Fibonacci Fn pour l’entier naturel n
if n==0:
return 0 # condition d’arrêt
elif n==1:
return 1 # condition d’arrêt
72
·
Chapitre 6 Récursivité
else:
return (fibo_rec(n-1)+fibo_rec(n-2))
# appel récursif
Remarque : Ceci sera traité dans l’exercice 14.1 « Suite des nombres de Fibonacci, Top
Down et Bottom Up » dans le chapitre « Programmation dynamique » pour une opti-
misation du programme récursif.
7. Le pgcd est associatif donc pgcd(a, b, c) = pgcd(pgcd(a, b), c).
def gcd_trois(a, b, c):
return euclide(euclide(a, b), c)
Analyse du problème
On a étudié une version itérative de ce programme (voir exercice 5.2 « Recherche
dichotomique dans une liste triée, complexité » dans le chapitre « Algorithmes de
dichotomie »).
La méthode dichotomique utilise le fait que la liste est triée. Elle consiste à compa-
rer l’élément recherché à l’élément se trouvant au milieu d’une liste triée. Comme
la liste est triée, cela permet d’éliminer la moitié de la liste comme emplacement
possible de l’élément, sauf si on l’a déjà trouvé. Ensuite, on prend la moitié de la
liste qui reste et on recommence.
1.
def rec_dicho_recursive(L, x):
# la fonction affiche "Elément présent" si x est dans la
# liste triée L, sinon affiche "Elément non présent"
if L==[]: # condition d’arrêt si liste vide
return ("Elément non présent")
else:
# la liste est non vide
milieu=len(L)//2 # calcul du milieu de la liste
if x==L[milieu]: # recherche si l’élément est au milieu
return ("Elément présent")
elif x>L[milieu]:
# recherche entre milieu+1 et la fin de la liste
return rec_dicho_recursive(L[milieu+1:], x)
73
·
Partie 4 Récursivité
# appel récursif
else:
# recherche entre début de liste et milieu-1
return rec_dicho_recursive(L[:milieu], x)
# appel récursif
74
·
Chapitre 6 Récursivité
2. Écrire une fonction polygone qui admet comme arguments deux entiers
naturels n et a. Cette fonction trace un polygone régulier à n côtés de même
longueur a.
3. On souhaite tracer le segment de Koch de longueur a à l’ordre n.
•• On part d’un segment de longueur a à l’ordre 0.
•• À l’étape 1, on remplace le tiers du segment central par un triangle équilatéral
sans base au-dessus.
•• On réitère le processus n fois.
Écrire une fonction récursive koch qui admet comme arguments deux entiers
naturels n et a. Cette fonction trace un segment de Koch de longueur a à l’ordre n.
4. Pour tracer le flocon de neige, on part d’un triangle équilatéral et on applique
la fonction koch à l’ordre n à chacun des côtés du triangle équilatéral de lon-
gueur a. La figure représente le flocon de Von Koch à l’ordre 2.
Analyse du problème
Le module graphique turtle permet de piloter une tortue afin de tracer des figures
géométriques.
Une figure fractale est un objet géométrique « infiniment morcelé » dont les détails
sont observables à une échelle arbitrairement choisie. Le flocon de Von Koch est
un exemple de courbe fractale. En zoomant sur une partie de la figure, on retrouve
toute la figure : on dit qu’elle est autosimilaire. À chaque étape, la longueur de la
n n
4 4
base est multipliée par . Le périmètre du flocon à l’étape n est : 3a et
3 3
tend vers l’infini si n tend vers l’infini. La courbe fractale n’admet de tangente en
aucun point.
2.
def polygone(n, a): # la fonction dessine un polygone
# régulier à n côtés de longueur a
for i in range(n): # i varie entre 0 inclus et n exclu
forward(a) # avance la tortue de a pixels
left(360/n) # tourne la tortue vers la gauche de
# 360/n degrés
polygone(10, 50) : # 10 côtés de longueur 50
mainloop() # laisse la fenêtre graphique turtle
# ouverte à la fin du programme
77
·
Partie 4 Récursivité
ordre 0 ordre 1
78
·
Chapitre 6 Récursivité
# à l’ordre n-1
koch(n-1, a/3) # appel récursif ordre n-1 et longueur a/3
left(60) # tourne la tortue vers la gauche de 60°
# deuxième tiers : on appelle la fonction récursive
# à l’ordre n-1
koch(n-1, a/3) # appel récursif ordre n-1 et longueur a/3
right(120) # tourne la tortue vers la droite de 120°
# troisieme tiers : on appelle la fonction récursive
# à l’ordre n-1
koch(n-1, a/3) # appel récursif ordre n-1 et longueur a/3
left(60) # tourne la tortue vers la gauche de 60°
koch(n-1, a/3) # appel récursif ordre n-1 et longueur a/3
79
·
Partie 4 Récursivité
Analyse du problème
La méthode « diviser pour régner » permet de décomposer le problème initial en
deux sous-problèmes.
Afin d’éviter de calculer plusieurs fois le même nombre de Fibonacci, on utilise la
technique de mémoïsation.
Cours :
La méthode « diviser pour régner » peut se décomposer en trois étapes :
•• Diviser : on divise le problème initial en plusieurs sous-problèmes.
•• Régner : on traite récursivement chacun des sous-problèmes.
•• Combiner : on combine les différents sous-problèmes pour résoudre le problème de
départ.
Cette méthode donne de très bons résultats dans de nombreux problèmes : dichotomie, tri
par partition-fusion, tri rapide.
La méthode « diviser pour régner » a parfois des faiblesses avec des appels récursifs
redondants. Les sous-problèmes ne sont pas toujours indépendants. On peut être amené à
résoudre plusieurs fois le même sous-problème.
Une solution consiste à utiliser la technique de mémoïsation en stockant les résultats déjà
calculés (voir chapitre 14 « Programmation dynamique »).
1.
def fibo1(n):
# la fonction renvoie le nombre de Fibonacci Fn
# pour l’entier n
if n==0:
return 0 # condition d’arrêt
elif n==1:
return 1 # condition d’arrêt
else:
return (fibo1(n-1)+fibo1(n-2))
# appel récursif
80
·
Chapitre 6 Récursivité
main()
5
fib(5) 2
3
fib(4) fib(3)
2 1
1 1
fib(1) fib(0)
81
Partie 5
Algorithmes
gloutons
Plan
7. Algorithmes gloutons (sauf TSI et TPC) 85
7.1 : Rendu de monnaie 85
7.2 : Problème du sac à dos 87
7.3 : Allocation de salle de spectacles 88
Algorithmes gloutons
(sauf TSI et TPC)
7
Exercice 7.1 : Rendu de monnaie
On dispose des pièces entières suivantes : S = [1, 2, 5, 10, 20, 50, 100] = [S0,
S1, …, Sn–1] où S[i] représente la valeur de la pièce d’indice i. On suppose
que la liste S est triée par ordre croissant des valeurs. On cherche à rendre
une certaine somme entière X en utilisant le moins de pièces, qui peuvent être
identiques.
1. On utilise la méthode la plus intuitive qui consiste à commencer par rendre
la plus grande pièce possible. Pour X = 11, on commence par rendre la pièce
de 10.
On appelle L[x] le nombre de pièces nécessaires pour rendre la somme x. La
récurrence (1) peut s’écrire :
•• L[0] = 0
•• Si x ≥ 1 : L[ x ] = 1 + L x − S [ i ] avec i le plus grand tel que S [ i ] ≤ x .
Écrire une fonction récursive rendu1 qui admet comme arguments une liste S
et un entier X. La fonction retourne le nombre de pièces nécessaires pour rendre
la somme X en utilisant la récurrence (1).
2. L’algorithme utilise-t-il la méthode « diviser pour régner » ? Pourquoi cette
méthode est-elle appelée gloutonne ? Est-ce que rendu1([1, 4, 6], 8)
retourne la solution optimale ?
Analyse du problème
On étudie plusieurs algorithmes permettant d’optimiser le rendu de monnaie. La
méthode « diviser pour régner » permet de décomposer le problème initial en deux
sous-problèmes.
La programmation dynamique (voir chapitre 14 « Programmation dynamique »)
permet d’obtenir une solution optimale. On verra la différence entre la méthode
gloutonne et la programmation dynamique.
85
·
Partie 5 Algorithmes gloutons
1.
def rendu1(S, X):
# la fonction renvoie le nombre de pièces nécessaires pour
# rendre la somme X en utilisant la liste S :
# S[i]=valeur de la pièce d’indice i
if X==0: # condition d’arrêt
return 0
else:
# recherche de i le plus grand tel que S[i] <= X
i=len(S)-1
while S[i]>X:
i=i-1
# ajoute 1 au nombre de pièces
# puisqu’on utilise la pièce S[i]
# il reste donc à rendre la monnaie à X - S[i]
return 1+rendu1(S, X-S[i]) # appel récursif
S=[1, 4, 6]
X=8
print(rendu1(S, X)) # on obtient : 3
Cours :
La méthode « diviser pour régner » peut se décomposer en trois étapes :
•• Diviser : on divise le problème initial en plusieurs sous-problèmes.
•• Régner : on traite récursivement chacun des sous-problèmes.
•• Combiner : on combine les différents sous-problèmes pour résoudre le problème de
départ.
Dans la méthode gloutonne (greedy, en anglais), on effectue une succession de choix, cha-
cun d’eux semble être le meilleur sur le moment. On résout alors le sous-problème mais on
ne revient jamais sur le choix déjà effectué.
86
·
Chapitre 7 Algorithmes gloutons (sauf TSI et TPC)
Analyse du problème
On étudie plusieurs méthodes permettant de maximiser la valeur des objets insérés
dans un sac à dos. La programmation dynamique (voir chapitre 14 « Programma-
tion dynamique ») permet d’obtenir une solution optimale en utilisant deux tech-
niques : « Top Down » et « Bottom Up ».
1.
def algo1(S, M):
# S est une liste de listes avec [valeur, masse].
# Les objets sont triés par ordre décroissant valeur/masse.
# La fonction retourne la valeur des objets que l’on peut
# insérer avec une masse maximale M
v_total=0 # initialisation de la valeur totale des objets
m_total=0 # initialisation de la masse totale des objets
n=len(S)
for i in range(n):
if m_total+S[i][1]<=M: # teste si nouvelle masse totale<=M
v_total+=S[i][0] # calcule la nouvelle valeur totale
m_total+=S[i][1] # calcule la nouvelle masse totale
return v_total # retourne la valeur totale des objets
87
·
Partie 5 Algorithmes gloutons
2. Cette méthode est appelée méthode gloutonne car elle consiste à faire le
meilleur choix sur le moment, c’est-à-dire insérer l’objet qui a le plus grand
rapport valeur/masse.
M=30
S=[[15, 6], [60, 25], [10, 5], [7, 8], [10, 20]] # [valeur, masse]
print('ALGO1 :', algo1(S, M)) # affiche 32
88
·
Chapitre 7 Algorithmes gloutons (sauf TSI et TPC)
Analyse du problème
On utilise la méthode gloutonne, qui consiste à effectuer une succession de choix,
chacun d’eux semblant être le meilleur sur le moment.
1.
def gestion(L, début, fin):
# retourne le nombre maximum de spectacles que l’on peut
# organiser entre début(int) = heure de début et
# fin(int) = heure de fin dans la salle ainsi que la liste
# des spectacles retenus L = liste de listes
# L[i]=[di, fi] = heure de début et de fin du spectacle i
n=len(L) # nombre de spectacles
p=0 # initialisation du nb de spectacles organisés
LISTE_CONF=[] # initialisation de la liste des
# spectacles organisés
for i in range(n): # i varie entre 0 inclus et n exclu
if LISTE_CONF==[] and L[i][0]>=début and L[i][1]<=fin:
p=p+1
LISTE_CONF.append(i) # indice du premier spectacle
# ajouté
elif p>=1:
indice=LISTE_CONF[p-1] # indice du dernier spectacle
# ajouté
if L[i][0]>=L[indice][1] and L[i][1]<=fin:
p=p+1
LISTE_CONF.append(i) # indice du spectacle ajouté
return(p, LISTE_CONF)
89
·
Partie 5 Algorithmes gloutons
3.
L1=[[0, 2], [1, 3], [2, 4], [1, 5], [3, 6], [4, 7], [5, 9],\
[6, 11], [9, 12]]
début=1 # heure de début des spectacles
fin=11 # heure de fin des spectacles
p1, LISTE_CONF1=gestion(L1, début, fin)
print('Nombre de spectacles :', p1)
print("Spectacles que l'on peut organiser :", LISTE_CONF1)
90
Partie 6
Lecture et écriture
de fichiers –
Matrices de pixels
et images
Plan
8. Lecture et écriture de fichiers 93
8.1 : Lecture et écriture de fichiers, calculs statistiques 93
8.2 : Lecture de fichiers 96
9. Matrices de pixels et images, traitement d’images 99
9.1 : Traitement d’images et filtrage passe-bas 99
9.2 : Filtrage d’images 104
Lecture et écriture
de fichiers
8
Exercice 8.1 : Lecture et écriture de fichiers, calculs
statistiques
Rappels pour la gestion des fichiers :
f=open('[Link]','w') : '[Link]' désigne le nom du
fichier. Le mode d’ouverture peut être 'w' pour « écriture » (write), 'r'
pour « lecture » (read) ou 'a' pour « ajout » (append)
[Link]() : lecture d'une ligne de l’objet fichier f
\n : caractère d’échappement : saut de ligne
[Link]() : renvoie une chaîne sans les espaces et les caractères
d’échappement (saut de ligne par exemple) en début et fin de la chaîne de
caractères c1
[Link](';') : sépare une chaîne de caractères (c1) en une liste de
mots avec le séparateur ';'
[Link]('exemple') : écrit dans l’objet fichier f la chaîne de carac-
tères 'exemple'
[Link]() : ferme le fichier
1. Écrire un programme Python permettant de créer le fichier '[Link]'
contenant les éléments suivants :
10 : nombre de points du fichier
25;10.9 : abscisse et ordonnée du premier point
20;9.3
15;8.2
12;7.5
9;6.2
6;5.8
3;4.2
93
·
Partie 6 Lecture et écriture de fichiers – Matrices de pixels et images
0;3.9
-3;2.8
-6;2 : abscisse et ordonnée du dixième point
2. Écrire un programme Python permettant d'ouvrir un fichier .txt (par exemple
'[Link]') et de récupérer les abscisses et les ordonnées dans deux listes.
3. On cherche à modéliser les n points expérimentaux ( x1 , y1 ), ( x2 , y2 )…
( xn , yn ) par une fonction polynôme du premier ordre, de la forme : y = ax + b.
n
n
n
n ∑ x y − ∑ x ∑ y
i i i i
i =1 i =1 i =1
a= 2 et b = y − ax en notant x la moyenne des xi et y
n
n
n ∑ xi2 −
∑ xi
i =1 i =1
Analyse du problème
Cet exercice utilise les fonctions d’écriture et de lecture de fichiers avec Python.
Il faut convertir les entiers en chaînes de caractères avant d’utiliser [Link].
Lors de la lecture du fichier, on parcourt les différentes lignes du fichier avec
[Link](). On enlève ensuite les caractères d’échappement (saut de ligne
par exemple) et on sépare la chaîne de caractères obtenue en une liste de mots.
1.
x=[25,20,15,12,9,6,3,0,-3,-6]
y=[10.9,9.3,8.2,7.5,6.2,5.8,4.2,3.9,2.8,2]
n=len(x)
94
·
Chapitre 8 Lecture et écriture de fichiers
2.
f=open('[Link]', 'r')
n=int([Link]()) # nombre de points
x=[]
y=[]
for i in range(n): # i varie entre 0 inclus et n exclu
ligne=[Link]()
ligne2=[Link]() # enlève les caractères d’échappement
xchaine,ychaine=[Link](';')
[Link](float(xchaine)) # conversion de l’abscisse en
# type float
# xchaine est une chaîne de caractères qu’il faut
# convertir en type float
[Link](float(ychaine)) # conversion de l’ordonnée en
# type float
[Link]() # fermeture du fichier
3.
sumx=0
sumy=0
sumxy=0
moy_x=0
moy_y=0
sumx2=0
for i in range(n):
sumx=sumx+x[i]
sumy=sumy+y[i]
sumxy=sumxy+x[i]*y[i]
moy_x+=x[i]
moy_y+=y[i]
sumx2+=x[i]**2
moy_x=moy_x/n
moy_y=moy_y/n
a=(n*sumxy-sumx*sumy)/(n*sumx2-sumx**2)
b=moy_y-a*moy_x
La première variable dans [Link] est la liste des abscisses des points. La
deuxième variable est la liste des ordonnées des points.
95
·
Partie 6 Lecture et écriture de fichiers – Matrices de pixels et images
Analyse du problème
Cet exercice utilise les fonctions de lecture de fichiers avec Python. Dans l’exer-
cice précédent, on lit les lignes du fichier au fur et à mesure en utilisant la méthode
[Link](). Ici on récupère directement une liste de chaînes de caractères
avec la méthode [Link](). Il faut alors parcourir cette liste pour récu-
pérer les différentes lignes du fichier. Pour chaque ligne, on enlève les caractères
d’échappement (saut de ligne par exemple) et on sépare la chaîne de caractères
obtenue en une liste de mots.
Cours :
Pour initialiser une liste, on utilise X=[].
Pour ajouter des éléments dans une liste, on utilise [Link](valeur).
Pour supprimer le dernier élément d’une liste, on utilise [Link]().
Il faut bien connaître les arguments de la fonction [Link](X, Y) : la première liste
X représente l’abscisse des points, la deuxième liste Y représente l’ordonnée des points.
2.
[Link]() # nouvelle fenêtre graphique
[Link](X, Y)
# ou utilisation de la fonction ci-dessous, qui permet
# de mettre une croix pour les points expérimentaux
# et de relier les points entre eux :
# [Link](LX, LY, '+', linestyle="-")
[Link]() # affiche la figure à l′écran
97
·
Partie 6 Lecture et écriture de fichiers – Matrices de pixels et images
Cours :
Il faut bien connaître la syntaxe de range :
for i in range(start, stop, step):
i varie entre start inclus et stop exclu avec un pas égal à step.
Lorsque step n’est pas indiqué, le pas vaut 1 par défaut.
3.
def trapeze(Y, X):
# la fonction renvoie l’intégrale I par la méthode des
# trapèzes
n=len(X) # nombre d’éléments de la liste
I=0 # initialisation de la variable I
for i in range(1, n): # i varie entre 1 inclus et n exclu
I+=(X[i]-X[i-1])*(Y[i]+Y[i-1])/2
return I
print(trapeze(Y, X))
On pourrait écrire :
I=I+(X[i]-X[i-1])*(Y[i]+Y[i-1])/2
au lieu de :
I+=(X[i]-X[i-1])*(Y[i]+Y[i-1])/2
98
Matrices de pixels et
images, traitement
9
d’images
99
·
Partie 6 Lecture et écriture de fichiers – Matrices de pixels et images
5. On souhaite réaliser un filtre passe-bas qui adoucit les détails d’une image
représentée par la matrice M. On considère la matrice A :
Analyse du problème
On repère un pixel par (i, j) où i désigne l’indice de la ligne et j l’indice de la
colonne. Pour chaque pixel, on a un niveau de gris compris entre 0 et 255. On
obtient ainsi une matrice dont chaque valeur correspond au niveau de gris. On peut
alors modifier facilement les valeurs de la matrice pour effectuer un traitement
d’images.
Cours :
Manipulation des images avec Python
Une image est définie par le nombre de pixels. Par exemple, une image 800×600 contient
800 pixels en largeur et 600 pixels en hauteur, soit 480 000 pixels. On peut la représenter
par une matrice 600×800 contenant 600 lignes et 800 colonnes. Le point supérieur gauche
de l’image a pour coordonnées [0, 0], le point inférieur droit [599, 799].
Utilisation d’une liste de listes
Matrice
On représente une matrice 2 × 3 par la liste L contenant 2 listes de longueur 3. Chacune de
ces listes de longueur 3 représente une ligne de la matrice 3 2 1 .
8 6 4
L=[[3, 2, 1], [8, 6, 4]]
100
·
Chapitre 9 Matrices de pixels et images, traitement d’images
Chaque élément de la liste est une liste. Pour extraire le premier élément de la liste L :
M=L[0] # M vaut [3,2,1]
Bibliothèque PIL
On utilise le module Image de la bibliothèque PIL. Les instructions permettant d’obtenir
la liste L seraient rappelées dans un problème de concours :
from PIL import Image
img=[Link]('[Link]') # stockage des pixels de l’image
# '[Link]' dans la liste img
p, n=[Link] # n=nombre de lignes (hauteur)
# p=nombre de colonnes (largeur)
L=list([Link]())
La liste L est une simple liste contenant à la suite les pixels de la première ligne de l’image,
les pixels de la deuxième ligne…
Images en niveaux de gris
Chaque élément de la liste L est caractérisé par un entier compris entre 0 (noir) et 255
(blanc).
M est la matrice qui représente l’ensemble des pixels. La première sous-liste contient la
première ligne de l’image. La deuxième sous-liste contient la deuxième ligne de l’image.
M=[[0 for j in range(p)] for i in range(n)]
for i in range(n):
for j in range(p):
M[i][j]=L[i*p+j]
Pour créer une matrice correspondant à une image vide 800×600 en niveaux de gris :
M=[[0 for j in range(800)] for i in range(600)]
Images en couleurs
Chaque élément de la liste L est caractérisé par un tuple de 3 valeurs entières comprises
entre 0 (intensité nulle) et 255 (intensité maximale) correspondant au codage RVB (rouge,
vert, bleu) ou RGB (red, green, blue). On peut représenter 2563 couleurs différentes. On
rencontre parfois une quatrième valeur correspondant à un coefficient de transparence.
M est la matrice qui représente l’ensemble des pixels. La première sous-liste contient la
première ligne de l’image. La deuxième sous-liste contient la deuxième ligne de l’image.
Chaque pixel de la matrice contient la liste des 3 valeurs entières correspondant au codage
RVB.
101
·
Partie 6 Lecture et écriture de fichiers – Matrices de pixels et images
2.
def inv_contraste(M):
# argument d’entrée : matrice M (liste de listes)
# en niveaux de gris
# la fonction retourne M2 la moitié inférieure de l’image M
# avec inversion du contraste
n=len(M) # n = nombre de lignes (hauteur)
n2=n//2
p=len(M[0]) # p = nombre de colonnes (largeur)
M2=[[0 for j in range(p)] for i in range(n2, n)]
for i in range(n2, n):
for j in range(p):
M2[i-n2][j]=255-M[i][j] # inversion du contraste
return M2
3.
def trois_niveaux_gris(M):
# la fonction renvoie une matrice M2 (liste de listes)
# avec 3 niveaux de gris uniquement
# argument d’entrée : matrice M (liste de listes)
# en niveaux de gris
n=len(M) # n = nombre de lignes (hauteur)
p=len(M[0]) # p = nombre de colonnes (largeur)
M2=[[0 for j in range(p)] for i in range(n)]
for i in range(n):
for j in range(p):
if M[i][j]<=80: # teste si le niveau de gris
# est <= 80
M2[i][j]=60
elif M[i][j]<=150 : # teste si le niveau de gris
# est <= 150
102
·
Chapitre 9 Matrices de pixels et images, traitement d’images
M2[i][j]=120
else: # le niveau de gris est > 150
M2[i][j]=220
return M2
5.
def somtab(A): # somme de tous les éléments de
# la matrice A (liste de listes)
n=len(A) # n = nombre de lignes (hauteur)
p=len(A[0]) # p = nombre de colonnes (largeur)
som=0
for i in range(n):
for j in range(p):
som=som+A[i][j]
return int(abs(som)) # int pour obtenir un entier
def filtrage(M):
# la fonction renvoie une matrice M2 (liste de listes)
# filtrage passe-bas de la matrice M
# argument d’entrée : matrice M (liste de listes)
# en niveaux de gris
n=len(M) # n = nombre de lignes (hauteur)
p=len(M[0]) # p = nombre de colonnes (largeur)
M2=[[0 for j in range(p)] for i in range(n)]
103
·
Partie 6 Lecture et écriture de fichiers – Matrices de pixels et images
A=[[1/12,1/12,1/12],[1/12,4/12,1/12],[1/12,1/12,1/12]]
for i in range(1, n-1):
for j in range(1, p-1):
B=[[M[i1][j1] for j1 in range(j-1, j+2)]\
for i1 in range(i-1, i+2)]
C=multipAB(A, B)
M2[i][j]=somtab(C)
return M2
Remarque : Voir le site Dunod pour télécharger les programmes Python avec des
exemples d’images.
104
·
Chapitre 9 Matrices de pixels et images, traitement d’images
2. La dérivée dans la direction horizontale peut être approchée par Mi, j − Mi −1, j .
Proposer un filtre permettant de détecter le changement d’intensité d’une couleur
selon la direction horizontale. On appelle M2 la matrice de l’image ainsi filtrée.
3. Proposer un filtre permettant de détecter le contour selon la direction verti-
cale. On appelle M3 la matrice de l’image ainsi filtrée.
4. Proposer un filtre permettant de détecter les contours dans les deux direc-
(M2 ) + (M3 )
2 2
tions en utilisant pour chaque point de l’image i, j i, j .
Analyse du problème
On repère un pixel par (i, j) où i désigne l’indice de la ligne et j l’indice de la
colonne. Pour chaque pixel, on a un niveau de gris compris entre 0 et 255. On uti-
lise deux boucles for pour décrire tous les pixels de l’image.
1.
def somtab(A): # somme de tous les éléments de
# la matrice A (liste de listes)
n=len(A) # n = nombre de lignes (hauteur)
p=len(A[0]) # p = nombre de colonnes (largeur)
som=0
for i in range(n):
for j in range(p):
som=som+A[i][j]
return int(abs(som)) # int pour obtenir un entier
105
·
Partie 6 Lecture et écriture de fichiers – Matrices de pixels et images
0 0 0
−1 1 0
0 0 0
0 −1 0
0 1 0
0 0 0
A=[[0,-1,0],[0,1,0],[0,0,0]]
M3=filtre(M, A)
4.
def contour(M2, M3):
import math as m
n=len(M3) # n = nombre de lignes (hauteur)
p=len(M3[0]) # p = nombre de colonnes (largeur)
M5=[[0 for j in range(p)] for i in range(n)]
for i in range(n):
for j in range(p):
M5[i][j]=[Link]((M3[i][j])**2+(M3[i][j])**2)
return M5
Remarque : Voir le site Dunod pour télécharger les programmes Python avec des
exemples d’images.
106
Partie 7
Tris
Plan
10. Tris 109
10.1 : Tri par insertion 109
10.2 : Tri par sélection 112
10.3 : Tri rapide (sauf TSI et TPC) 115
10.4 : Tri par partition-fusion 118
10.5 : Tri par comptage, histogramme 122
10.6 : Tri à bulles (sauf TSI et TPC) 125
Tris 10
Exercice 10.1 : Tri par insertion
Le tri par insertion est souvent utilisé pour trier des cartes. Il consiste à insérer
les éléments d’une partie de la liste non triée dans la liste triée.
Présentation du tri par insertion :
On considère la liste non triée : L= 8 5 3 9 2 comprenant n = 5 éléments.
Avec Python, on a : L [ 0 ] = 8 … et L [ n − 1] = 2. On parcourt la liste du deu-
xième au dernier élément. Lorsqu’on est à l’étape k (k variant de 1 à n–1, les
éléments précédents L [ k ] sont déjà triés. Il faut donc insérer cet élément d’in-
dice k dans la liste triée.
Mise en place de l’algorithme :
On envisage deux boucles pour réaliser le tri par insertion :
•• Première boucle d’indice k (k variant de 1 à n–1). Quand on considère l’élé-
ment d’indice k, on considère que les éléments précédents sont déjà triés.
Par exemple, pour k = 2. On a la liste suivante : 5 8 3 9 2 avec L[2]=3.
↑
•• k = 2 : 5 8 3 9 2 → 3 5 8 9 2
↑ ↑
k =2 k =2
•• k = 3 : 3 5 8 9 2 → 3 5 8 9 2
↑ ↑
k =3 k =3
109
·
Partie 7 Tris
•• k = 4 : 3 5 8 9 2 → 2 3 5 8 9
↑ ↑
k =4 k =4
Analyse du problème
On étudie dans cet exercice le tri par insertion qui est un tri en place car il n’utilise
pas de liste auxiliaire. Sa complexité spatiale est faible.
1.
def tri_insertion(L):
# la fonction trie par ordre croissant la liste L
n=len(L)
for k in range(1, n): # k varie entre 1 inclus et n exclu
i=k-1 # deuxième boucle démarre à k-1
# les éléments entre 0 et k-1 sont triés
x=L[k] # mémorisation de la valeur de L[k]
while i>=0 and L[i]>x:
L[i+1]=L[i] # décale les éléments de la liste
i=i-1 # décrémente de 1 la valeur de i
L[i+1]=x # met la valeur dans le trou
# return L est inutile car L est passé en référence
110
·
Chapitre 10 Tris
2.
L=[8, 5, 3, 9, 2]
print(L)
tri_insertion(L)
print(L)
Python affiche :
[2, 3, 5, 8, 9]
Remarques :
Le programme principal suivant affiche None puisqu’il n’y a pas de return.
print(tri_insertion([5, 2, 3, 1, 4])) # affiche None
def tri_insertion_test(L):
# la fonction trie par ordre croissant la liste L
n=len(L)
for k in range(1, n): # k varie entre 1 inclus et n exclu
i=k-1 # deuxième boucle démarre à k-1
# les éléments entre 0 et k-1 sont triés
x=L[k] # mémorisation de la valeur de L[k]
while i>=0 and L[i]>x:
L[i+1]=L[i] # décale les éléments de la liste
i=i-1 # décrémente de 1 la valeur de i
L[i+1]=x # met la valeur dans le trou
return # ne retourne pas de variable
Cours :
On cherche à trier un ensemble d’éléments, c’est-à-dire à les ordonner en fonction d’une
relation d’ordre définie sur ces éléments.
•• Un tri comparatif est basé sur la comparaison des éléments entre eux.
•• Un tri itératif est basé sur un ou plusieurs parcours itératifs de la liste.
•• Un tri récursif est basé sur une procédure récursive.
•• Un tri en place n’utilise qu’un espace mémoire de taille constante en plus de l’espace
servant à stocker les éléments à trier. Il n’utilise pas de liste auxiliaire.
•• Un tri stable conserve l’ordre initial des éléments de même clé. Deux éléments avec des
clés égales apparaîtront dans le même ordre dans la liste triée et dans la liste non triée.
On rencontre différents algorithmes de tri :
•• Tri par insertion : tri comparatif, itératif, stable. Tri en place.
•• Tri par sélection : tri comparatif, itératif, instable. Tri en place.
•• Tri rapide : tri comparatif, récursif, instable. Tri en place.
•• Tri par partition-fusion : tri comparatif, récursif, stable. Le tri n’est pas en place
•• Tri par comptage : tri itératif. Le tri n’est pas comparatif. Le tri n’est pas en place. On
n’étudie pas la stabilité pour le tri par comptage.
•• Tri à bulles : tri comparatif, itératif, stable. Tri en place.
4. Le tri par insertion est comparatif et itératif.
La liste initiale est triée par ordre alphabétique : [[67, 'France'],
[40, 'Irak'], [47, 'Kenya'], [32, 'Pérou'], [66,
'Royaume-Uni'], [66, 'Thaïlande']].
La liste triée par ordre croissant de la population est : [[32, 'Pérou'],
[40, 'Irak'], [47, 'Kenya'], [66, 'Royaume-Uni'],
[66, 'Thaïlande'], [67, 'France']].
Le tri par insertion est stable puisqu’on garde l’ordre alphabétique dans la
liste triée pour les pays qui ont la même population.
Le tri par insertion est un tri en place car il n’utilise pas de liste auxiliaire.
112
·
Chapitre 10 Tris
1. Écrire une fonction tri_sélection qui admet comme argument une liste
L et permet de la trier par ordre croissant en utilisant la méthode du tri par
sélection. Écrire le programme principal permettant de trier la liste L=[8, 5,
3, 9, 2].
2. Partant d’une liste de couples (entier, chaîne de caractères), on souhaite
trier la liste L2 par ordre croissant de la population en millions d’habitants :
L2=[[67, 'France'], [40, 'Irak'], [47, 'Kenya'], [32,
'Pérou'], [66, 'Royaume-Uni'], [66, 'Thaïlande']]. Écrire
une fonction tri_sélection2 permettant de trier la liste L2 par ordre crois-
sant de la population.
3. Donner les caractéristiques du tri par sélection.
4. Évaluer la complexité dans le pire des cas lors de l’appel de la fonction
tri_sélection.
Analyse du problème
On étudie dans cet exercice le tri par sélection, qui est un tri en place car il n’utilise
pas de liste auxiliaire. Le premier élément d’une liste L a pour indice 0 avec Python.
1.
def tri_sélection(L):
# la fonction trie par ordre croissant la liste L
n=len(L)
for i in range(0, n-1):
# recherche du minimum de la liste L[i: n]
mini=L[i]
ind_mini=i
for j in range(i+1, n):
if L[j]<mini:
ind_mini=j
mini=L[j]
# on permute L[i] et L[ind_mini] si on a trouvé
# un nouveau minimum
if ind_mini!=i: # ind_mini est différent de i
L[i], L[ind_mini]=L[ind_mini], L[i]
# return L est inutile car L est passé en référence
L=[8, 5, 3, 10, 2, 9]
tri_sélection(L)
print(L)
2.
def tri_sélection2(L):
# la fonction trie par ordre croissant la liste L
# L[i][0] valeur à trier
n=len(L)
for i in range(0, n-1):
# recherche du minimum de la liste L[i: n]
113
·
Partie 7 Tris
mini=L[i][0]
ind_mini=i
for j in range(i+1, n): # parcourt L[j] pour j>i
if L[j][0]<mini:
ind_mini=j
mini=L[j][0]
# on permute L[i] et L[ind_mini] si on a trouvé
# un nouveau minimum
if ind_mini!=i: # ind_mini est différent de i
L[i], L[ind_mini]=L[ind_mini], L[i]
# return L est inutile car L est passé en référence
∑ (3 + 5 (( n − 1) − (i + 1)) + 6) = −2 +
3n 5 2
2+ + n
i =0
2 2
( )
La complexité est quadratique en O n2 .
Remarque :
On peut accepter des petites différences dans l’évaluation du nombre total d’opéra-
tions élémentaires. La complexité de l’algorithme ne sera pas modifiée.
On peut montrer que la complexité est quadratique dans tous les cas.
114
·
Chapitre 10 Tris
2. Écrire une fonction récursive tri_rapide permettant de trier une liste par
ordre croissant en utilisant la fonction pivot.
3. Écrire le programme principal permettant de trier la liste L=[10, 3, 9,
6, 8]. Représenter l’arbre des appels de la fonction récursive tri_rapide.
4. Donner les caractéristiques du tri rapide.
Analyse du problème
Le tri rapide s’appuie sur le principe « diviser pour régner » comme le tri par
partition-fusion. On réalise un tri en place.
1.
def pivot(L, a, b): # a = indice de début, et b = indice de fin
# la fonction renvoie la position du pivot dans la liste
# éléments inférieurs ou égaux sont à gauche du pivot
# L[i][0] valeur à trier
p=L[b] # valeur du pivot = dernier élément de la liste
ind_p=a # indice du pivot
for i in range(a, b): # i varie entre a inclus et b exclu
if L[i]<=p:
L[i], L[ind_p]=L[ind_p], L[i] # on échange les
# 2 éléments
ind_p+=1
L[b], L[ind_p]=L[ind_p], L[b] # échange les 2 éléments
# inutile de retourner L car passage par référence
# la valeur L[ind_p] est bien placée dans la liste à trier
return ind_p
2.
def tri_rapide(L, a, b):
# a = indice de début, et b = indice de fin
# la fonction trie par ordre croissant la liste L
if b>a:
ind_p=pivot(L, a, b)
tri_rapide(L, a, ind_p-1) # tri_rapide pour les indices
# entre a et ind_p-1
tri_rapide(L, ind_p+1, b) # tri rapide pour les indices
# entre ind_p+1 et b
# si a=b alors la sous-liste est triée : condition d’arrêt
# si a>b pas de changement. Il faut bien considérer ce cas
# comme condition d’arrêt
116
·
Chapitre 10 Tris
3.
L=[10, 3, 9, 6, 8]
n=len(L)
print(L)
tri_rapide(L, 0, n-1) # la fonction retourne none
# puisque L est triée en place
print(L)
[10,3,9,6, ])8
pivot [3,6,8,9,10])
8
[3,6, ,10,9])
[3,6] tri_rapide
[9,10]
tri_rapide
6
[3, ] [10, ]9
[3,6] pivot pivot
[9,10]
6
[3, ] 9
[ ,10]
tri_rapide
[3] tri_rapide
[10]
[3] [10]
Remarque :
Lorsqu’on applique la fonction tri_rapide à la sous-liste [10, 9] avec a = 3 et
b = 4, il y a trois actions :
•• appel de la fonction pivot : le pivot vaut 9 et l’indice du pivot vaut ind_p = 3
puisque 9 fait partie de la liste L = [3, 6, 8, 9, 10] ;
•• appel de la fonction tri_rapide à la sous-liste définie par a = 3 et ind_p −
1 = 2. La fonction tri_rapide ne modifie rien : c’est une condition d’arrêt ;
•• appel de la fonction tri_rapide à la sous-liste définie par ind_p + 1 = 4 et
b = 4. La fonction tri_rapide ne modifie rien puisque la sous-liste constituée
d’un seul élément est déjà triée : c’est une condition d’arrêt.
La complexité du tri rapide est quasi linéaire en O ( n log n ). Le tri rapide est plus
efficace que le tri par insertion dont la complexité est quadratique en O( n2 ) dans le
pire des cas.
117
·
Partie 7 Tris
118
·
Chapitre 10 Tris
1. Écrire une fonction itérative fusion qui admet comme arguments deux
listes L1 et L2 triées et retourne la fusion triée des deux listes.
2. Réécrire une version récursive de la fonction précédente que l’on appellera
fusion_rec.
3. Écrire une fonction récursive tri_fusion permettant de trier la liste L. On
pourra partager la liste initiale L en deux sous-listes L1 et L2.
4. Écrire le programme principal permettant de trier par ordre croissant la liste
L=[8, 3, 5, 1, 9, 5, 12, 15]. La fonction tri_fusion comporte
plusieurs appels récursifs. Représenter l’arbre des appels de la fonction tri_
fusion pour la liste L.
5. Donner les caractéristiques du tri par partition-fusion.
Analyse du problème
Le tri par partition-fusion s’appuie sur le principe « diviser pour régner », c’est-
à-dire que l’on divise (partitionne) le problème en deux sous-problèmes que
l’on sait résoudre. Il reste à utiliser les deux solutions pour résoudre le problème
initial.
1.
def fusion(L1, L2):
# la fonction L retourne la fusion triée des deux listes
# L1 et L2
i1, i2=0, 0 # position du pointeur de chaque
# liste
n1, n2=len(L1), len(L2) # longueur des listes
n=n1+n2 # longueur de L1+L2
L=[]
while i1+i2<n: # il faut parcourir tous les
# éléments de L1+L2
if i1==n1: # la liste L1 est parcourue
# entièrement
return L+L2[i2:] # il faut ajouter les éléments
# restants de L2
elif i2==n2: # la liste L2 est parcourue
# entièrement
return L+L1[i1:] # il faut ajouter les éléments
# restants de L1
elif L1[i1]<L2[i2]:
L=L+[L1[i1]] # ajoute L1[i1]
i1+=1 # incrémente de 1 le pointeur de L1
else: # on a forcément L1[i1]>=L2[i2]
L=L+[L2[i2]]
i2+=1
return L
119
·
Partie 7 Tris
Il faut bien connaître le slicing ou extraction de tranche pour les listes : instruction
L[start:stop] (voir exercice 1.6 « Slicing, extraction de tranche, » dans le
chapitre « Prise en main de Python »).
••start désigne l’indice de départ.
••stop–start désigne la longueur de la liste extraite (lorsque le pas vaut 1).
L’indice final vaut stop–1 !
Cours :
Dans toute procédure récursive, l’instruction return doit être présente au moins deux
fois : une fois pour la condition d’arrêt (premier return dans le programme) et une autre
fois pour l’appel récursif (dernier return dans le programme).
2.
def fusion_rec(L1, L2):
# la fonction retourne la fusion triée des deux listes
# L1 et L2
if L1==[]:
return L2 # condition d’arrêt
elif L2==[]:
return L1 # condition d’arrêt
elif L1[0]<L2[0]:
return ([L1[0]]+fusion_rec(L1[1:], L2))
else:
return ([L2[0]]+fusion_rec(L1, L2[1:]))
3.
def tri_fusion(L):
# la fonction trie par ordre croissant la liste L
n=len(L)
if n==1:
return L # condition d’arrêt
else:
L1=L[:n//2] # indices compris entre 0 inclus et n//2 exclu
# la longueur de L1 vaut n//2
L2=L[n//2:] # indices compris entre n//2 inclus et n exclu
return fusion_rec(tri_fusion(L1), tri_fusion(L2))
4.
L=[8, 3, 5, 1, 9, 5, 12, 15]
L_tri=tri_fusion(L)
print(L_tri)
Remarque :
À chaque appel de la fonction récursive, on coupe la liste en deux. On arrive tou-
jours à une sous-liste comportant un seul élément, qui est donc triée (condition
d’arrêt de la fonction récursive) !
120
Chapitre 10 Tris ·
La complexité spatiale est très mauvaise puisqu’on utilise une fonction récursive
qui appelle elle-même une fonction récursive. Le tri n’est pas en place comme avec
le tri par insertion.
1er appel de la fonction tri_fusion : L1=[8, 3, 5, 1] et L2=
[9, 5, 12, 15]. Avant de fusionner L1 et L2, il faut les trier de façon
récursive en appelant la fonction tri_fusion.
L’arbre ci-dessous représente les différents appels de la fonction tri_
fusion notée tri_f.
main() [5,9,12,15]
[1,3,5,8]
tri_f([8,3,5,1]) tri_f([9,5,12,15])
[3,8] [12,15]
[1,5] [5,9]
121
·
Partie 7 Tris
Analyse du problème
On étudie dans cet exercice le tri par comptage. On crée une liste HISTO qui repré-
sente l’histogramme (ou liste de comptage) des éléments de L. Voir exercice 2.2
« Tracé d’un histogramme avec matplotlib » dans le chapitre « Graphiques ».
1.
def tri_comptage(L):
# la fonction retourne L_tri, qui est la liste L triée par
# ordre croissant
122
·
Chapitre 10 Tris
123
·
Partie 7 Tris
124
·
Chapitre 10 Tris
Analyse du problème
On étudie dans cet exercice le tri à bulles. On parcourt la liste L en comparant les
éléments consécutifs deux à deux et en faisant remonter vers la fin de la liste les
plus grands éléments. Au bout du premier parcours, l’élément le plus grand est
remonté comme une bulle, d’où le nom « tri à bulles ».
1. On considère la boucle :
for i in range(n-1, 0, -1): # i varie entre n-1 inclus
# et 0 exclu avec pas=-1
125
·
Partie 7 Tris
Le tri à bulles est un tri en place car il n’utilise pas de liste auxiliaire.
3. On cherche à calculer le nombre d’opérations élémentaires :
•• Ligne n=len(L) : 2 opérations élémentaires (appel de len(L) et
affectation).
•• Boucle for i in range(n-1, 0, -1) :
OOBoucle for j in range(1, i+1) : on se place dans le pire des
cas. On a 7 opérations élémentaires (appel de l’élément L[j], appel
de l’élément L[j-1], test, appel de l’élément L[j], appel de l’élé-
ment L[j-1], 2 affectations).
n −1
7 7
Le nombre total d’opérations élémentaires vaut : 2 + ∑ 7i = n2 − n + 2.
2 2
i =1
La complexité est quadratique en O(n2 ).
L’instruction break fait sortir d’une boucle while ou for et passe à l’instruc-
tion suivante alors que l’instruction return quitte la fonction.
127
Partie 8
Dictionnaire, pile,
file, deque
Plan
11. Dictionnaire, pile, file, deque 131
11.1 : Opérations de base sur les dictionnaires 131
11.2 : Comptage des éléments d'une liste à l’aide d’un
dictionnaire134
11.3 : Opérations de base sur les piles 136
11.4 : Parenthésage 139
11.5 : Opérations de base sur les files 140
11.6 : Utilisation des deques 142
Dictionnaire, pile,
file, deque
11
Exercice 11.1 : Opérations de base sur les dictionnaires
On considère des opérations de base sur les dictionnaires.
1. Écrire une fonction dico_vide qui renvoie un dictionnaire vide.
2. Écrire une fonction ajout_cle qui admet comme arguments un diction-
naire, une clé et une valeur. Cette fonction ajoute le couple (clé, valeur) au
dictionnaire.
3. Écrire une fonction supp_cle qui admet comme arguments un diction-
naire et une clé. Cette fonction supprime le couple (clé, valeur) correspon-
dant à clé.
Analyse du problème
Les dictionnaires sont très souvent utilisés en informatique. Chaque élément du
dictionnaire a une clé unique. Les éléments du dictionnaire ne sont pas ordonnés.
Cours :
Rappels sur les listes et les tuples
Les éléments d’une liste ou d’un tuple sont ordonnés. Pour récupérer un élément, on utilise
un indice.
L1=["MPSI", "PTSI"] # liste (objet modifiable) contenant 2 éléments
print(L1[1]) # affiche "PTSI", d’indice 1 dans la liste L1
L2=(48, 46) # tuple (objet non modifiable) contenant 2 éléments
print(L2[0]) # affiche 48, d’indice 0 dans la liste L2
Dictionnaires
Une table de hachage est une structure de données permettant de stocker des couples
(clé, valeur). Elle permet de retrouver une clé très rapidement. Les tables de hachage
sont appelées dictionnaires avec Python. Dans un dictionnaire, on associe une valeur à
une clé.
Le type de la clé peut être un entier, un nombre flottant, une chaîne de carac-
tères… mais pas une liste.
Le type de la valeur associée à la clé peut être quelconque.
131
·
Partie 8 Dictionnaire, pile, file, deque
Les éléments d’un dictionnaire ne sont pas ordonnés. On ne peut pas utiliser un indice
comme pour les listes pour accéder à un élément.
Chaque élément du dictionnaire est identifié par une clé unique.
On utilise la clé pour rechercher la valeur correspondante du couple (clé, valeur).
On définit un élément du dictionnaire dans Python en précisant la clé, suivie de « : » et de
la valeur associée.
d1={"MPSI":48} # dictionnaire dico1 constitué d’un seul élément
print(d1) # affiche {'MPSI': 48}. On visualise la clé
# et la valeur
print(type(d1)) # affiche le type de d1 : dict (type dictionnaire)
La clé est unique dans un dictionnaire. On ne peut pas ajouter "MPSI" : 45 dans d.
Par contre, on peut modifier une valeur :
d["MPSI"]=45
print(d) # {'MPSI': 45, 'MP': 46}
132
·
Chapitre 11 Dictionnaire, pile, file, deque
Les clés d’un dictionnaire ne sont pas obligatoirement des chaînes de caractères. On va voir
plusieurs méthodes pour parcourir un dictionnaire.
Parcours des clés d’un dictionnaire
dico={3:5, 8:5} # les clés du dictionnaire doivent être différentes
for clé in dico: # on parcourt les clés de dico
print(clé)
On obtient alors :
3
8
On peut utiliser également .keys() :
for clé in [Link](): # on parcourt les clés de dico
print(clé)
Parcours des clés et valeurs d’un dictionnaire avec .items()
for elt in dico_classe.items(): # elt est un tuple
print("Elément du dictionnaire : ", elt)
a=elt[0] # récupère la clé
b=elt[1] # récupère la valeur
L’instruction d2=d n’a pas réalisé une copie de d puisque d2 et d pointent vers la même
adresse mémoire.
Si on modifie un élément du dictionnaire d, alors cet élément est modifié dans d2.
Par contre, la modification n’apparaît pas dans d3 puisque d et d3 pointent vers des
adresses mémoire différentes.
Les dictionnaires sont des objets muables (voir exercice 1.4 « Affectation, objet immuable,
copie » dans le chapitre « Prise en main de Python »).
133
·
Partie 8 Dictionnaire, pile, file, deque
Remarque : On rencontre deux catégories de copies pour les objets muables (listes,
dictionnaires, deques…) :
•• La fonction copy() réalise une copie superficielle. Les valeurs des clés sont bien
copiées s’il n’y a pas de structure imbriquée (liste par exemple). Si les valeurs
d’un dictionnaire sont des listes, alors l’adresse mémoire des listes est copiée.
•• La fonction deepcopy() réalise une copie profonde pour les structures imbri-
quées. Si les valeurs sont des listes, alors la copie profonde copie bien les listes
imbriquées.
1.
def dico_vide(): # la fonction renvoie un dictionnaire vide
return {}
2.
def ajout_cle(dico, clé, valeur):
# la fonction ajoute le couple (clé, valeur) à dico
dico[clé]=valeur
3.
def supp_cle(dico, clé):
# la fonction supprime le couple (clé, valeur)
# correspondant à clé pour dico
del dico[clé]
Remarque :
Le programme suivant permet de tester les fonctions précédentes :
d={}
print(d)
ajout_cle(d,"MPSI",48)
ajout_cle(d,"MP",46)
ajout_cle(d,"PCSI1",48)
ajout_cle(d,"PCSI2",48)
print(d)
print()
supp_cle(d,"MPSI")
print(d)
134
·
Chapitre 11 Dictionnaire, pile, file, deque
Analyse du problème
Les éléments du dictionnaire ne sont pas ordonnés. Chaque élément du dictionnaire
a une clé unique. La valeur de la clé est égale au nombre d’occurrences de la clé
dans la liste.
1.
def comptagedico(L):
# la fonction renvoie un dictionnaire permettant de connaître
# le nombre d’occurrences de chaque élément de la liste
d={} # création d’un dictionnaire vide
for elt in L:
if elt in d:
d[elt]=d[elt]+1 # incrémente de 1 la valeur
# de la clé elt
else:
d[elt]=1 # ajoute clé elt au dictionnaire
# elt apparaît la première fois dans d
# la valeur de la clé elt vaut 1
return d
2.
L=[10, 12, 10, 8, 6, 10, 12, -5, 8.2, 8.2]
d=comptagedico(L)
print(d) # affichage du dictionnaire
135
·
Partie 8 Dictionnaire, pile, file, deque
Analyse du problème
Les piles sont très souvent utilisées en informatique (voir chapitre 12 « Graphes »).
On étudie dans ce chapitre une modélisation des piles avec des listes. Toutes les
opérations sur la pile sont effectuées sur la même extrémité : on utilise le principe
LIFO (Last In, First Out).
Cours :
Une pile est une structure de données qui utilise le principe LIFO (Last In, First Out : « der-
nier entré, premier sorti »). On peut comprendre le fonctionnement d’une pile en considé-
rant une pile d’assiettes.
•• La fonction empiler consiste à ajouter une assiette sur le sommet de la pile (ou tête
de la pile).
Soit une pile P contenant 3 éléments : 3, 5 et 8.
pile P
136
·
Chapitre 11 Dictionnaire, pile, file, deque
10
pile P
10
pile P
10
pile P
La fonction « Undo » (Annulation de la frappe) des traitements de texte utilise une pile.
Remarque : L’ajout et la suppression d’un élément en fin de liste Python est très
rapide. L’utilisation des listes Python pour gérer des piles est très efficace.
1.
def empiler(P,x):
# la fonction ajoute l’élément x au sommet de la pile P
[Link](x) # on ajoute l’ élément x à la liste P
137
·
Partie 8 Dictionnaire, pile, file, deque
2.
def depiler(P):
# la fonction supprime le dernier élément entré dans la pile P
# et retourne cet élément
x=[Link]() # supprime le dernier élément de la liste P
return x # retourne la valeur du dernier élément
# de la liste P
3.
def pile_vide(P):
# la fonction retourne True si la pile P est vide
# et False sinon
if P==[]: # on pourrait écrire : if len(P)==0:
return True
else:
return False
Remarque :
Le programme suivant permet de visualiser les étapes du rappel de cours précédent :
P1=[] # création d’une liste vide
print(pile_vide(P1))
empiler(P1,3)
empiler(P1,5)
empiler(P1,8)
empiler(P1,10)
empiler(P1,2)
print(P1)
y=depiler(P1)
print(y)
print(P1)
print(pile_vide(P1))
138
·
Chapitre 11 Dictionnaire, pile, file, deque
Analyse du problème
La structure de piles est parfaitement adaptée à la résolution de cet exercice. On par-
court les différents caractères de la chaîne L. On empile les parenthèses ouvrantes
et on dépile dès qu’on a une parenthèse fermante.
On définit une pile P initialement vide. On parcourt tous les caractères de
la chaîne L.
Dès qu’on rencontre une parenthèse ouvrante, on empile le caractère « ( »
dans P.
Quand on rencontre une parenthèse fermante, plusieurs cas interviennent :
•• Si la pile P est vide, alors la fonction parenthesage retourne False
puisqu’il manque une parenthèse ouvrante avant la parenthèse fermante.
•• Sinon, on dépile la parenthèse ouvrante de P.
Lorsqu’on a parcouru tous les caractères de L, on doit avoir rencontré
autant de parenthèses ouvrantes que fermantes. La pile P est nécessaire-
ment vide. Si ce n’est pas le cas, la fonction parenthesage retourne
False.
def parenthesage(L):
P=[] # initialisation de la pile
for elt in L:
# on parcourt tous les caractères de L
if elt=="(": # parenthèse ouvrante empilée dans P
empiler(P,elt)
elif elt==")": # parenthèse fermante
if pile_vide(P)==True:
# la pile ne doit pas être vide
139
·
Partie 8 Dictionnaire, pile, file, deque
if pile_vide(P)==True:
return True
else:
return False
Analyse du problème
Les files sont très souvent utilisées en informatique (voir chapitre 12 « Graphes »).
On étudie une modélisation des files avec des listes. On utilise le principe FIFO
(First In, First Out).
140
·
Chapitre 11 Dictionnaire, pile, file, deque
Cours :
Une file (queue en anglais) est une structure de données qui utilise le principe FIFO (First
In, First Out : « premier entré, premier sorti »).
Dans une file d’attente à un distributeur de billets, les personnes font la queue les unes der-
rière les autres. Le premier arrivé dans la queue est le premier sorti (c’est-à-dire le premier
servi pour obtenir les billets).
•• La fonction enfiler (enqueue) consiste à ajouter un élément à la queue de la file (on
dit aussi à l’arrière de la file d’attente).
Soit une file d’attente F contenant 3 éléments :
DEFILER ENFILER
(dequeue) (enqueue)
distributeur
de billets
3 5 8
tête queue
front of queue rear of queue
tête queue
tête queue
On modélise la file d’attente par une liste Python : F = [3, 5, 8, 10, 2]. On
dit que 3 est à la tête de la file F et 2 est à la queue de la file F.
•• La fonction défiler (dequeue) consiste à supprimer l’élément situé à la tête de la
file (on dit aussi au début de la file d’attente). On a bien une structure FIFO puisque le
premier élément rentré est le premier sorti.
On obtient alors la file :
DEFILER ENFILER
(dequeue) (enqueue)
5 8 10 2
tête queue
141
·
Partie 8 Dictionnaire, pile, file, deque
Remarque : La suppression d’un élément en tête de liste Python n’est pas très
rapide puisque tous les autres éléments doivent être décalés d’une position. On uti-
lisera dans l’exercice suivant, « Utilisation des deques », la classe collections.
deque qui est conçue pour ajouter et supprimer rapidement des éléments aux deux
extrémités.
1.
def enfiler(F, x): # F est une liste Python
[Link](x) # ajoute x à la queue de la file ou à la fin
# de la liste F
2.
def défiler(F): # F est une liste Python
x=[Link](0) # supprime l’élément situé à la tête de la file F
# c’est le premier élément de la liste F
return x # retourne x
3.
def file_vide(F): # F est une liste Python
# la fonction retourne True si la file F est vide
# et False sinon
return F==[]
142
·
Chapitre 11 Dictionnaire, pile, file, deque
Analyse du problème
On considère les deques (double-ended queue), qui sont une généralisation des piles
et des files. Les deques permettent d’ajouter et de supprimer très rapidement des
éléments aux deux extrémités. On utilisera les deques dans le parcours des graphes.
Cours :
Une deque (se prononce « dèque ») est une structure de données qui généralise le fonction-
nement des piles et des files. On peut ajouter et supprimer des éléments aux deux extrémités.
from collections import deque # module permettant d’utiliser
# les deques
10 8 3 5
143
·
Partie 8 Dictionnaire, pile, file, deque
8 3
Pour réaliser une copie superficielle de D, il ne faut pas écrire E=D mais utiliser la fonction
copy.
import copy
E=[Link](D) # copie superficielle de D
[Link]() # supprime l’élément à l’extrémité droite de la deque E
# D n'est pas modifié puisque D ne pointe pas vers la même
# adresse mémoire que E
1.
def insere_gauche_deque(D, x):
[Link](x) # ajoute x à l’extrémité gauche de la deque D
2.
def insere_droite_deque(D, x):
[Link](x) # ajoute x à l’extrémité droite de la deque D
144
·
Chapitre 11 Dictionnaire, pile, file, deque
145
Partie 9
Graphes
Plan
12. Graphes 149
12.1 : Matrice d’adjacence 149
12.2 : Graphe avec liste d’adjacence. Dictionnaire des sommets
adjacents154
12.3 : Graphe avec liste d’adjacence. Liste des sommets adjacents 156
12.4 : Parcours en largeur d’un arbre en utilisant une file 157
12.5 : Parcours en largeur d’un graphe avec une deque 161
12.6 : P arcours en largeur d’un graphe avec une matrice d’adjacence 164
12.7 : Parcours en profondeur d’un graphe 167
12.8 : Test de connexité d’un graphe – Parcours en profondeur –
Arbre couvrant 171
12.9 : Algorithme récursif du parcours en largeur 176
12.10 : Algorithme récursif du parcours en profondeur 178
12.11 : Recherche d’un cycle, graphe non orienté,
parcours en largeur 180
Graphes 12
Exercice 12.1 : Matrice d’adjacence
On considère le graphe G = ( S , A) non orienté, où le nombre situé sur l’arête
joignant deux sommets est leur distance, supposée entière :
1 1
2 9
3
0
4
8
2 7
3
On utilise les listes de listes pour représenter les matrices dans Python.
1. Construire la matrice d’adjacence Mi , j ( )
0 ≤i , j ≤ 4
(appelée également matrice
de distance) du graphe G, définie par :
Pour tous les indices i, j, Mi, j représente la distance entre les sommets i et j, ou
encore la longueur de l’arête reliant les sommets i et j.
On convient que, lorsque les sommets ne sont pas reliés, cette distance vaut
l’infini. On définit la variable inf=1e10 qui représente une distance infinie.
Écrire la matrice M.
2. Écrire une fonction voisins, d’arguments une matrice d’adjacence M, un
sommet i, renvoyant la liste des voisins du sommet i.
3. Écrire une fonction degré, d’arguments une matrice d’adjacence M, un
sommet i, renvoyant le nombre de voisins du sommet i, c’est-à-dire le nombre
d’arêtes issues de i.
4. Écrire une fonction longueur, d’arguments une matrice d’adjacence M,
une liste L de sommets de G, renvoyant la longueur du trajet décrit par la liste L,
c’est-à-dire la somme des longueurs des arêtes empruntées. Si le trajet n’est pas
possible, la fonction renverra -1.
Analyse du problème
On définit une matrice d’adjacence contenant les distances entre les différents som-
mets. Si deux sommets i et j ne sont pas reliés, alors M[i][j] = inf. Cet exercice est
extrait du concours banque PT 2015 Sujet 0. Comme le graphe n’est pas orienté, la
matrice est symétrique : M[i][j] = M[j][i].
149
·
Partie 9 Graphes
Cours :
Un graphe G est un schéma contenant des points appelés sommets (ou nœuds ou points),
reliés ou non par des arêtes (ou segments ou liens ou lignes).
On utilise la notation suivante : G = (S, A) est un couple d’ensemble finis, dont :
•• S est l’ensemble des sommets de G ;
•• A est l’ensemble des arêtes de G.
Si une arête relie les sommets s et s’, on dit que les sommets s et s’ sont voisins ou
adjacents.
L’ordre d’un graphe est le nombre total de sommets.
Un graphe est orienté si les arêtes sont orientées, c’est-à-dire si on ne peut les parcourir que
dans un sens.
Pour les graphes non orientés :
•• Deux sommets sont adjacents lorsqu’ils sont reliés par une arête.
•• La taille d’un graphe non orienté est le nombre total d’arêtes.
•• Le degré d’un sommet s, noté d(s) est égal au nombre d’arêtes dont ce sommet est une
extrémité. Une boucle est une arête reliant un sommet à lui-même. Les boucles sont
comptées deux fois.
5 0
Remarque : Des arêtes reliant la même paire de sommets sont des arêtes multiples.
Un graphe est simple s’il ne contient ni boucle ni arête multiple. Conformément au
programme, on n’étudiera par la suite que des graphes simples.
On appelle graphe pondéré un graphe dont les arêtes sont affectées d’un nombre appelé
poids (ou coût). Le poids d’un arc peut représenter la distance entre deux sommets voisins
pour un réseau routier. Dans certains graphes, le poids des arcs peut être négatif.
On peut implémenter un graphe par une matrice d’adjacence ou une liste d’adjacence.
Matrice d’adjacence :
On utilise une liste de listes. Par exemple la matrice 3 2 est représentée par la liste M
8 6
contenant deux listes de longueur 2 : M=[[3, 2], [8, 6]]. Chacune de ces listes de
longueur 2 représente une ligne de la matrice. 151
·
Partie 9 Graphes
152
·
Chapitre 12 Graphes
0 9 3 ∞ 7
9 0 1 8 ∞
1. La matrice d’adjacence est : M = 3 1 0 4 2 .
∞ 8 4 0 ∞
7 ∞ 2 ∞ 0
Remarque :
Tous les éléments de la diagonale sont nuls puisque la distance entre les sommets
i et i est nulle : M[i][j] = 0.
Les éléments sont symétriques par rapport à la diagonale puisque la distance entre
les sommets i et j est la même qu’entre les sommets j et i : M[i][j] = M[j][i].
On peut déduire de la deuxième ligne de la matrice que le sommet 1 est relié aux
sommets : 0, 2 et 3.
Pour la troisième ligne, le sommet 2 est relié aux sommets : 0, 1, 3 et 4.
M=[[0,9,3,inf,7],[9,0,1,8,inf],[3,1,0,4,2],\
[inf,8,4,0,inf],[7,inf,2,inf,0]]
2.
def voisins(M, i):
# la fonction renvoie la liste des voisins du sommet i
# pour la matrice M
n=len(M) # nb de lignes de la matrice d’adjacence
L=[] # initialisation de la liste L
for j in range(n): # j varie entre 0 inclus et n exclu
if M[i][j]>0 and M[i][j]<inf:
[Link](j) # si 0 < distance < inf, on ajoute le
# sommet dans L
return (L)
153
·
Partie 9 Graphes
1 1
2 9
3
0
4
8
2 7
3
154
·
Chapitre 12 Graphes
Analyse du problème
On définit un dictionnaire où chaque clé représente un sommet. Pour un sommet
donné, la valeur de la clé est un dictionnaire qui contient l’ensemble des sommets
adjacents avec les distances entre les deux sommets.
1. Le dictionnaire est :
dico={0:{1:9, 2:3, 4:7},\
1:{0:9, 2:1, 3:8},\
2:{0:3, 1:1, 3:4, 4:2},\
3:{1:8, 2:4},\
4:{0:7, 2:2} }
Voir exercice 11.1 « Opérations de base sur les dictionnaires » dans le cha-
pitre « Dictionnaire, pile, file, deque » pour l’utilisation des dictionnaires.
On peut écrire également :
dico=dict()
dico[0]={1:9, 2:3, 4:7} # ajoute la clé 0 dans dico
dico[1]={0:9, 2:1, 3:8} # ajoute la clé 1 dans dico
dico[2]={0:3, 1:1, 3:4, 4:2} # ajoute la clé 2 dans dico
dico[3]={1:8, 2:4} # ajoute la clé 3 dans dico
dico[4]={0:7, 2:2} # ajoute la clé 4 dans dico
2.
def voisins_dict(dico, i):
# la fonction renvoie la liste des voisins du sommet i
# pour le dictionnaire dico
L=[] # initialisation de la liste L
if i in dico: # teste si la clé i est dans le diction. dico
for clé, valeur in dico[i].items():
# parcourt les couples (clé, valeur) de dico[i]
[Link](clé)
return L
155
·
Partie 9 Graphes
156
·
Chapitre 12 Graphes
Analyse du problème
On définit un dictionnaire où chaque clé représente un sommet. Pour un som-
met donné, la valeur de la clé est une liste qui contient l’ensemble des sommets
adjacents.
157
·
Partie 9 Graphes
2 3 4
5 6 8
7 9
On utilisera les deux opérations de base sur les files : defiler pour la sup-
pression d’un élément et enfiler pour l’ajout d’un élément. On rappelle que
[Link](0) permet de supprimer F[0] dans la liste F.
On cherche à parcourir en largeur tous les sommets de cet arbre G (toutes les
pages web de ce site).
Les étapes de l’algorithme de parcours en largeur sont les suivantes :
•• Ajouter le sommet de départ dans la file F initialement vide.
•• Tant que la file F n’est pas vide, supprimer l’élément x à la tête de la file.
Ajouter les fils de x dans la file.
1. Définir un dictionnaire dico représentant l’arbre G. Chaque clé est associée
à un sommet x. La valeur de la clé représente la liste des fils du sommet x.
2. Écrire une fonction parcourslargeur qui admet comme arguments un
dictionnaire dico et un sommet de départ début permettant de parcourir en
largeur un arbre.
3. Dans quel ordre sont parcourus les sommets dans la fonction
parcourslargeur(dico, 1) ?
Analyse du problème
L’algorithme de parcours en largeur (ou BFS, Breadth First Search, en anglais) per-
met de traiter les sommets adjacents à un sommet donné pour ensuite les explorer
un par un.
L’implémentation repose sur une file F dans laquelle on place le premier sommet à
la queue de F et les sommets adjacents non explorés à la queue de F. On utilise le
principe FIFO (First In, First Out : « premier entré, premier sorti »).
Voir exercice 11.5 « Opérations de base sur les files » dans le chapitre
« Dictionnaire, pile, file, deque » pour l’implémentation des files par les listes de
Python en utilisant le principe FIFO.
Cours :
Un graphe non orienté connexe et acyclique est un arbre. Chaque élément de l’arbre est
appelé un nœud.
158
·
Chapitre 12 Graphes
Au niveau élevé, on trouve le nœud racine (1). Au niveau juste en dessous, on a trois nœuds
fils (2, 3 et 4). Un nœud n’ayant aucun fils est appelé feuille. Les nœuds 3, 5, 7, 8 et 9 sont
des feuilles.
Le nombre total de niveaux de l’arbre est appelé hauteur. La hauteur de l’arbre G vaut 4.
G est un arbre ternaire puisque chaque nœud comporte au plus trois fils au niveau inférieur.
Du point de vue d’un fils, le nœud dont il est issu au niveau supérieur est appelé père.
On utilise une liste F pour modéliser une file. Par exemple F=[10, 3, 5, 8].
défiler enfiler
10 3 5 8
tête queue
Si on ajoute l’élément 2 (ou si on enfile l’élément 2), on obtient F=[10, 3, 5, 8, 2].
Enfiler un élément à une file consiste à ajouter un élément à la queue de la file.
Défiler un élément d’une file consiste à enlever l’élément situé à la tête de la file.
défiler enfiler
10 3 5 8 2
tête queue
def defiler(F):
x=[Link](0) # supprime l’élément situé à la tête de F : F[0]
return x # retourne x
while F!=[]:
x=defiler(F) # supprime l’élément à la tête de
# la file F : F[0]
for elt in dico[x]:
enfiler(F, elt) # ajoute les fils du sommet x
# à la queue de la file F
Remarque :
dico[x] contient les fils du sommet x. G ne contient pas de cycle par définition
d’un arbre. Tous les fils sont nécessairement non explorés. On peut donc tous les
ajouter dans la file F.
On étudiera un graphe dans l’exercice suivant « Parcours en largeur d’un graphe
avec une deque » : il faudra tester si les sommets adjacents ont déjà été explorés.
3. F=[1] au début de l’algorithme.
•• On enlève 1 de la file F et on explore ce sommet. Les fils de « 1 » sont ajou-
tés au fur et à mesure à la queue de F. La file F vaut alors : [2, 3, 4].
•• On enlève 2, le premier élément de F (élément situé à la tête de la file).
On explore le sommet 2. Les fils de « 2 » sont ajoutés à la queue de F.
La file F vaut alors : [3, 4, 5, 6].
•• On enlève 3, le premier élément de F (élément situé à la tête de la file). On
explore le sommet 3. Il n’y a pas de fils. La file F vaut alors : [4, 5, 6].
•• On enlève 4, le premier élément de F (élément situé à la tête de la file).
On explore le sommet 4. Les fils de « 4 » sont ajoutés à la queue de F.
La file F vaut alors : [5, 6, 8].
•• On enlève 5, le premier élément de F (élément situé à la tête de la file).
On explore le sommet 5.
•• …
Finalement, on a exploré les sommets dans l’ordre :
•• 1,
•• 2, 3, 4,
•• 5, 6, 8,
•• 7, 9.
Les flèches sur le graphe représentent le sens de parcours niveau par niveau
et de gauche à droite. On a bien exploré les sommets en largeur.
2 3 4
5 6 8
7 9
160
·
Chapitre 12 Graphes
2 3 4
5 6 8
7 9
161
·
Partie 9 Graphes
Analyse du problème
L’algorithme de parcours en largeur (ou BFS, Breadth First Search, en anglais) per-
met de traiter les sommets adjacents à un sommet donné pour ensuite les explorer
un par un.
L’implémentation repose sur une deque D dans laquelle on place le premier sommet
à l’extrémité droite de D initialement vide et les sommets adjacents non explorés à
l’extrémité droite de D. On utilise le principe FIFO (First In, First Out : « premier
entré, premier sorti »). Voir exercice 11.6 « Utilisation des deques » dans le cha-
pitre « Dictionnaire, pile, file, deque » pour la manipulation des deques.
Le graphe contient des cycles. Pour ne pas explorer plusieurs fois un même som-
met, on marque les sommets déjà explorés.
1.
dico={1:[2, 3, 4], 2:[1, 5, 6],3:[1, 6], 4:[1, 6, 8],\
5:[2], 6:[2, 7, 9],7:[6], 8:[4],9:[6]}
162
·
Chapitre 12 Graphes
Remarque :
dico[x] contient les sommets adjacents au sommet x. G peut contenir des cycles
puisqu’on ne considère pas d’arbre dans cet exercice. Il faut tester si les sommets
adjacents ont déjà été explorés.
Dans l’exercice précédent « Parcours en largeur d’un arbre en utilisant une file »,
on n’avait pas besoin de tester si les fils étaient déjà explorés puisqu’on considérait
un arbre, sans cycle par définition.
3. La deque D vaut [1] au début de l’algorithme.
•• On supprime l’élément à l’extrémité gauche de D. On explore ce sommet.
Les sommets adjacents à 1 non explorés sont ajoutés à l’extrémité droite
de D. La deque D vaut alors : [2, 3, 4].
•• On supprime l’élément à l’extrémité gauche de D. On explore le sommet 2.
Les sommets adjacents à 2 non explorés sont ajoutés à l’extrémité droite
de D. La deque D vaut alors : [3, 4, 5, 6].
•• On supprime l’élément à l’extrémité gauche de D. On explore le sommet 3.
Le sommet 6 a déjà été exploré. On ne l’ajoute pas. La deque D vaut
alors : [4, 5, 6].
•• On supprime l’élément à l’extrémité gauche de D. On explore le sommet 4.
Les sommets adjacents à 4 non explorés sont ajoutés à l’extrémité droite
de D. La deque D vaut alors : [5, 6, 8].
•• On supprime l’élément à l’extrémité gauche de D. On explore le sommet 5.
Pas de nouveau sommet non exploré. La deque D vaut alors : [6, 8].
•• On supprime l’élément à l’extrémité gauche de D. On explore le sommet 6.
La deque D vaut alors : [8, 7, 9].
•• On supprime l’élément à l’extrémité gauche de D. On explore le sommet 8.
Pas de nouveau sommet non exploré. La deque D vaut alors : [7, 9].
•• On supprime l’élément à l’extrémité gauche de D. On explore le sommet 7.
Pas de nouveau sommet non exploré. La deque D vaut alors : [9].
•• On supprime l’élément à l’extrémité gauche de D. On explore le sommet 9.
Pas de nouveau sommet non exploré. La deque D est vide.
163
·
Partie 9 Graphes
On utilise les listes de listes pour représenter les matrices dans Python.
1. Construire la matrice d’adjacence Mi, j du graphe G. Si deux sommets diffé-
rents i et j sont reliés par une arête, alors M[i][j] = 1 sinon M[i][j] = 0.
2. Écrire une fonction parcourslargeur_mat d’arguments une matrice
d’adjacence M et un sommet de départ début permettant de parcourir en lar-
geur le graphe. On utilise une deque pour parcourir en largeur le graphe. La
fonction affiche la liste des sommets explorés.
3. Dans quel ordre sont parcourus les sommets dans la fonction
parcourslargeur_mat(M, 0) ?
4. Calculer la complexité de cet algorithme dans le pire des cas.
Analyse du problème
L’algorithme de parcours en largeur (ou BFS, Breadth First Search, en anglais) permet
de traiter les sommets adjacents à un sommet donné pour ensuite les explorer un par
un. Il utilise une deque D dans laquelle il place le premier sommet à l’extrémité droite
164
·
Chapitre 12 Graphes
0 1 1 0 1
1 0 1 1 0
1. La matrice d’adjacence est : M = 1 1 0 1 1 .
0 1 1 0 0
1 0 1 0 0
M=[[0,1,1,0,1],[1,0,1,1,0],[1,1,0,1,1],\
[0,1,1,0,0],[1,0,1,0,0]]
Remarque :
Tous les éléments de la diagonale sont nuls d’après la définition de la matrice
d’adjacence : M[i][i] = 0.
Les éléments sont symétriques par rapport à la diagonale puisque le graphe n’est
pas orienté : M[i][j] = M[j][i].
On peut déduire de la deuxième ligne de la matrice que le sommet 1 est relié aux
sommets : 0, 2 et 3.
Pour la troisième ligne, le sommet 2 est relié aux sommets : 0, 1, 3 et 4.
165
·
Partie 9 Graphes
166
·
Chapitre 12 Graphes
2 3 4
5 6 8
7 9
On considère une pile P et une liste PARCOURS qui contient la liste des som-
mets explorés. On pose début=1 le sommet de départ.
Les étapes de l’algorithme de parcours en profondeur sont les suivantes :
Initialisation de l’algorithme :
La pile P contient le sommet de départ : P=[début].
La liste PARCOURS contient le sommet de départ : PARCOURS=[début].
Boucle tant que la pile P n’est pas vide :
•• S’il existe un sommet elt non exploré adjacent au sommet x (situé en haut de
la pile P) qui n’est pas dans la liste PARCOURS, alors on empile elt dans P et
on ajoute elt dans la liste PARCOURS.
•• Si le sommet x (situé en haut de la pile P) ne possède pas de voisin non
exploré, alors on dépile cet élément de la pile.
On utilisera un flag trouve (de valeur True ou False) qui permet de savoir
si le sommet x possède un voisin non exploré.
1. Définir un dictionnaire dico représentant le graphe G. Chaque clé est asso-
ciée à un sommet. La valeur de la clé représente la liste des sommets adjacents.
2. Écrire une fonction itérative parcoursprofondeur qui admet comme
arguments un dictionnaire dico et un sommet de départ début. La fonction
retourne la liste PARCOURS.
3. Que retourne parcoursprofondeur(dico, 1) ?
Analyse du problème
L’algorithme de parcours en profondeur (ou DFS, Depth First Search, en anglais)
explore une branche en profondeur depuis un sommet avant de passer à la suivante.
167
·
Partie 9 Graphes
1.
dico={1:[2, 3, 4], 2:[1, 5, 6], 3:[1], 4:[1, 8],\
5:[2], 6:[2, 7, 9], 7:[6], 8:[4], 9:[6]}
168
·
Chapitre 12 Graphes
On utilise très souvent trois opérations de base avec les piles : « empiler »,
« dépiler » et « tester si la pile est vide ». Voir exercice 11.3 « Opérations
de base sur les piles » dans le chapitre « Dictionnaire, pile, file, deque ».
Les lignes suivantes permettent de récupérer le sommet x en haut de la pile
pour obtenir la liste des sommets adjacents.
x=[Link]() # dépile pour récupérer l’élément en haut de la pile
[Link](x) # empile x
L=dico[x] # x est l’élément en haut de la pile
169
·
Partie 9 Graphes
170
·
Chapitre 12 Graphes
On utilise les listes de listes pour représenter les matrices dans Python.
1. Construire la matrice d’adjacence Mi, j du graphe G. Si deux sommets diffé-
rents i et j sont reliés par une arête, alors M[i][j] = 1 sinon M[i][j] = 0.
2. Écrire une fonction testgrapheconnexe_profondeur qui admet
comme argument une matrice d’adjacence M et retourne True si le graphe est
connexe et False sinon en utilisant le parcours en profondeur.
3. Écrire une fonction arbrecouvrant_profondeur qui admet comme
arguments une matrice d’adjacence M et un sommet de départ début permet-
tant de récupérer une matrice d’adjacence représentant l’arbre couvrant corres-
pondant au parcours en profondeur pour un graphe non orienté et connexe.
On considère deux listes (PERE, PARCOURS) et une pile P. La liste PARCOURS
contient la liste des sommets explorés. PERE[k] représente le père de
PARCOURS[k].
171
·
Partie 9 Graphes
Analyse du problème
Un graphe non orienté est connexe (ou simplement connexe) si on peut relier,
directement ou non, n’importe quel sommet à n’importe quel autre sommet du
graphe par un chemin. Il n’y a pas de sommet isolé.
On utilise le parcours en profondeur pour construire un arbre inclus dans le graphe
G et qui relie tous les sommets de ce graphe (voir exercice précédent « Parcours en
profondeur d’un graphe »).
Pour construire l’arbre couvrant, on définit deux listes : PARCOURS et PERE. La
liste PERE contient la liste des pères pour chaque sommet de PARCOURS. Il faut
en effet connaître la liste des sommets parcourus et savoir comment on a atteint ce
sommet.
0 1 1 0 1
1 0 1 1 0
1. La matrice d’adjacence est : M = 1 1 0 1 1 .
0 1 1 0 0
1 0 1 0 0
M=[[0,1,1,0,1],[1,0,1,1,0],[1,1,0,1,1],\
[0,1,1,0,0],[1,0,1,0,0]]
Remarque :
Tous les éléments de la diagonale sont nuls d’après la définition de la matrice
d’adjacence : M[i] [i] = 0.
Les éléments sont symétriques par rapport à la diagonale puisque le graphe n’est
pas orienté : M[i][j] = M[j][i].
172
·
Chapitre 12 Graphes
On peut déduire de la deuxième ligne de la matrice que le sommet 1 est relié aux
sommets : 0, 2 et 3.
Pour la troisième ligne, le sommet 2 est relié aux sommets : 0, 1, 3 et 4.
2. Pour savoir si le graphe G est connexe, on récupère la liste des sommets
explorés avec l’algorithme de parcours en profondeur. Si tous les sommets
du graphe G sont dans cette liste, alors G est connexe.
On appelle début le sommet de départ. On pose par exemple début = 0.
On aurait pu prendre un autre sommet de G.
def testgrapheconnexe_profondeur(M):
# la fonction retourne True si le graphe est connexe
# et False sinon pour la matrice d’adjacence M
n=len(M)
début=0 # on prend un sommet quelconque, par exemple 0
P=[début]
PARCOURS=[début]
while len(P)!=0:
x=[Link]() # dépile pour récupérer l’élément en haut
# de la pile
[Link](x) # empile x car il ne faut pas dépiler x
# à ce stade
trouve=False
i=0
while i<n and trouve==False:
if M[x,i]>0 and i not in PARCOURS: # cherche un sommet
# non exploré
trouve=True # on a trouvé un sommet non exploré
[Link](i)
[Link](i) # marque ce sommet exploré
i+=1
if trouve==False:
[Link]() # dépile le haut de la pile
if len(PARCOURS)==n:
return True # le graphe est connexe
else:
return False # le graphe n’est pas connexe
173
·
Partie 9 Graphes
print('Parcours :',PARCOURS)
print('Pere :',PERE)
Remarque :
On utilise très souvent trois opérations de base avec les piles : « empiler », « dépi-
ler » et « tester si la pile est vide ». Voir exercice 11.5 « Opérations de base sur
les piles » dans le chapitre « Dictionnaire, pile, file, deque ». Les lignes suivantes
permettent de récupérer le sommet x du haut de la pile.
174
·
Chapitre 12 Graphes
1
0
2
1
0
2
3
3 4 4
175
·
Partie 9 Graphes
2 3 4
5 6 8
7 9
Analyse du problème
L’algorithme de parcours en largeur (ou BFS, Breadth First Search, en anglais) per-
met de traiter les sommets adjacents à un sommet donné pour ensuite les explorer
un par un. L’implémentation repose sur une deque D dans laquelle on place le pre-
mier sommet à l’extrémité droite de D initialement vide et les sommets adjacents
non explorés à l’extrémité droite de D. On utilise le principe FIFO (First In, First
Out : « premier entré, premier sorti »).
176
·
Chapitre 12 Graphes
1.
dico={1:[2, 3, 4], 2:[1, 5, 6], 3:[1, 6], 4:[1, 6, 8],\
5:[2], 6:[2, 7, 9], 7:[6], 8:[4],9:[6]}
177
·
Partie 9 Graphes
2 3 4
5 6 8
7 9
On définit la liste PARCOURS qui contient la liste des sommets parcourus par
l’algorithme. La liste PARCOURS est initialement vide.
Principe de l’algorithme récursif :
•• On ajoute le sommet s dans la liste PARCOURS.
•• On appelle la fonction récursive pour le premier sommet non exploré
adjacent à s.
1. Définir un dictionnaire dico représentant le graphe G. Chaque clé est asso-
ciée à un sommet. La valeur de la clé représente la liste des sommets adjacents.
2. Écrire une fonction récursive profondeur_rec qui admet comme argu-
ments un dictionnaire dico, un sommet de départ s et une liste PARCOURS.
3. Qu’affiche le programme suivant ?
profondeur_rec(dico, 1, [])
print(PARCOURS)
Analyse du problème
L’algorithme de parcours en profondeur (ou DFS, Depth First Search, en anglais)
explore une branche en profondeur depuis un sommet avant de passer à la suivante.
On va le plus profond possible pour chaque branche.
1.
dico={1:[2, 3, 4], 2:[1, 5, 6], 3:[1, 6], 4:[1, 6, 8],\
5:[2], 6:[2, 7, 9], 7:[6], 8:[4],9:[6]}
178
·
Chapitre 12 Graphes
179
·
Partie 9 Graphes
2 3 4
5 0
Analyse du problème
On utilise le parcours en largeur du graphe.
Un chemin est simple si toutes les arêtes du chemin sont différentes. Un cycle est
un chemin simple tel que le sommet d’arrivée est le même que le sommet de départ.
180
·
Chapitre 12 Graphes
0 0 1 1 1 0
0 0 1 1 1 0
1 1 0 0 0 1
1. La matrice d’adjacence est : M = .
1 1 0 0 0 0
1 1 0 0 0 0
0 0 1 0 0 0
181
·
Partie 9 Graphes
if rec_cycle_larg(M)==True:
print('Le graphe possède au moins un cycle.')
else:
print('Le graphe ne possède pas de cycle.')
182
Partie 10
Recherche d’un
plus court chemin
Plan
13. Recherche d’un plus court chemin (sauf TSI et TPC) 185
13.1 : Recherche d’un plus court chemin, graphe orienté 185
13.2 : Algorithme de Dijkstra187
13.3 : Algorithme A* 195
13.4 : Variantes de l’algorithme A*, distance de Manhattan 200
Recherche d’un plus
court chemin
13
(sauf TSI et TPC)
Exercice 13.1 : Recherche d’un plus court chemin, graphe orienté
On considère le graphe orienté G = ( S , A) :
1
2 3 4
8
5 6
7 9
[Link]() permet d’inverser les éléments de la liste L.
On considère dans l’algorithme une liste PARCOURS et un dictionnaire PERE :
•• La liste PARCOURS contient la liste des sommets d’un plus court chemin du
sommet de départ début jusqu’au sommet d’arrivée fin différent de début.
•• PERE[i] représente le père du sommet i lors du parcours en largeur du
graphe depuis le sommet de départ début.
1. Définir un dictionnaire dico représentant le graphe G. La clé associée à
chaque sommet représente la liste des successeurs.
2. Écrire une fonction itérative BFS qui admet comme arguments un diction-
naire dico et un sommet de départ début. La fonction retourne un diction-
naire PERE en utilisant l’algorithme de parcours en largeur.
3. La liste PARCOURS est initialement vide.
Principe de l’algorithme d’un plus court chemin :
Pour obtenir les sommets d’un plus court chemin de début jusqu’à fin, il
faut remonter dans l’arborescence du dictionnaire PERE depuis le sommet fin
jusqu’à la racine début.
Écrire une fonction récursive pluscourtchemin qui admet comme arguments
un sommet de départ début, un sommet d’arrivée fin, un dictionnaire PERE et une
liste PARCOURS permettant d’obtenir un plus court chemin de début jusqu’à fin.
4. Écrire le programme principal permettant d’afficher un plus court chemin
entre le sommet de départ début et le sommet d’arrivée fin. Qu’obtient-on
pour début = 1 et fin = 8 ?
185
·
Partie 10 Recherche d’un plus court chemin
Analyse du problème
Un plus court chemin de début jusqu’à fin est le chemin comportant le moins
d’arcs. On utilise l’algorithme de parcours en largeur (BFS, Breadth First Search,
en anglais) permettant de traiter les sommets adjacents à un sommet donné pour
ensuite les explorer un par un. Voir exercice 12.5 « Parcours en largeur d’un graphe
avec une deque » dans le chapitre « Graphes ».
1.
dico={1:[3], 2:[1, 5], 3:[6],\
4:[1, 8], 5:[], 6:[2, 4, 9],\
7:[6], 8:[1, 9], 9:[]}
Le sommet 2 a deux successeurs : 1 et 5. La valeur de la clé 2 est la liste
des successeurs [1, 5]. Le sommet 6 n’est pas le successeur du sommet 4.
2. Les sommets déjà visités sont marqués pour éviter d’explorer plusieurs
fois un même sommet. La liste VISITED contient les sommets visités.
Les étapes de l’algorithme de parcours en largeur sont les suivantes :
Initialisation de l’algorithme :
•• Mettre le sommet de départ dans la deque D initialement vide.
•• La liste VISITED contient le sommet de départ : VISITED =
[début].
Boucle tant que la deque D n’est pas vide :
•• Supprimer le sommet x à l’extrémité gauche de D.
•• Ajouter dans VISITED et à l’extrémité droite de D les sommets non
explorés adjacents au sommet x.
def BFS(dico, début):
# la fonction renvoie le dictionnaire PERE avec un parcours
# en largeur pour le dictionnaire dico
from collections import deque # module permettant d’utiliser
# les deques
D=deque() # deque vide
[Link](début) # ajoute le sommet de départ
PERE={ } # dictionnaire vide
VISITED=[début]
while len(D)!=0:
x=[Link]() # supprime le sommet x à l’extrémité
# gauche de D
L=dico[x] # liste contenant les sommets adjacents à x
for elt in L: # parcourt les éléments de L
if elt not in VISITED: # teste si le sommet n’a pas
# déjà été exploré
[Link](elt) # ajoute le sommet elt à l’extrémité
# droite de D
[Link](elt) # le sommet elt a été exploré
PERE[elt]=x # ajoute clé, valeur dans le dico PERE
return PERE
3.
def pluscourtchemin(début, fin, PERE, PARCOURS):
# la fonction permet d’avoir un plus court chemin
# de début (int) à fin (int) dans la liste PARCOURS
# à partir du dictionnaire PERE
if début==fin:
[Link](fin)
return() # condition d’arrêt
elif PERE[fin]=='':
PARCOURS=[]
return () # condition d’arrêt
else:
[Link](fin) # on ajoute le sommet fin dans
# la liste PARCOURS
pluscourtchemin(début, PERE[fin], PERE, PARCOURS)
# appel récursif
4.
début, fin=1, 8
PERE=BFS(dico, début)
if fin not in PERE: # teste si le sommet fin est dans
# le dictionnaire PERE
print("Il n’y a pas de chemin entre", début, "et", fin,".")
else:
PARCOURS=[]
pluscourtchemin(début, fin, PERE, PARCOURS)
[Link]() # inverse les éléments de la liste
print('Un plus court chemin :', PARCOURS)
Si le sommet fin n’est pas dans le dictionnaire PERE, alors il n’y a pas de
chemin entre début et fin.
Le programme Python affiche :
Parcours : [1, 3, 6, 4, 8]
1 1
2 9
3
0
4
8
2 7
3
187
·
Partie 10 Recherche d’un plus court chemin
On utilise les listes de listes pour représenter les matrices dans Python.
[Link]() permet d’inverser les éléments de la liste L.
1. Construire la matrice d’adjacence (Mi, j)0≤i,j≤n−1 (appelée également matrice
de distance) du graphe G, définie par :
Pour tous les indices i, j, Mi, j représente la distance entre les villes d’origine i
et d’extrémité j.
Lorsque les villes ne sont pas reliées, cette distance vaut l’infini. On définit la
variable inf=1e10 qui représente une distance infinie.
2. On cherche à déterminer un plus court chemin pour aller d’une ville de
départ notée départ à une ville d’arrivée notée arrivée en utilisant l’algo-
rithme de Dijkstra :
On définit la liste VILLES contenant les informations suivantes pour chaque
ville : [ville précédente sur le chemin, distance parcourue depuis la ville de
départ, ville sélectionnée ou non (booléen vrai ou faux)].
a) Initialisation de l’algorithme :
Toutes les villes sont non sélectionnées sauf la ville de départ. Pour cette ville,
la distance parcourue vaut 0.
Pour les villes non sélectionnées, les distances parcourues depuis la ville de
départ sont initialisées à l’infini.
On définit une variable position qui correspond à la ville pour laquelle
l’algorithme est appliqué. Cette variable prend initialement la valeur départ.
b) Tant que la variable position n’est pas égale à la variable arrivée, répé-
ter les opérations suivantes pour toutes les villes i non sélectionnées :
•• Calculer la variable somme = distance entre la ville départ et la ville
position + distance entre la ville position et la ville i.
•• Si la variable somme est inférieure à la distance entre la ville départ et la
ville i, alors remplacer cette distance par somme. La ville précédente sur le
chemin est alors position.
Chercher la ville (parmi les villes non sélectionnées) pour laquelle la distance
entre celle-ci et la ville départ est la plus petite. Cette ville définit alors la
nouvelle valeur de la variable position et cette ville devient sélectionnée.
Écrire une fonction dijkstra qui admet comme arguments d’entrée la matrice
d’adjacence M, la ville départ et la ville arrivée. Cette fonction retourne
le chemin suivi ainsi que la distance parcourue entre départ et arrivée en
utilisant l’algorithme de Dijkstra.
Écrire le programme principal permettant de déterminer un plus court chemin
entre la ville de départ 3 et la ville d’arrivée 0. Le programme affichera le che-
min suivi ainsi que la distance parcourue.
3. Pourquoi cet algorithme est appelé algorithme glouton ?
188
·
Chapitre 13 Recherche d’un plus court chemin (sauf TSI et TPC)
2 4
8
4 10 2
1 3
1
Analyse du problème
On étudie l’algorithme de Dijkstra, qui un algorithme de plus court chemin. On
définit la matrice d’adjacence qui contient l’ensemble des distances entres les villes.
La longueur d’un chemin est la somme des poids des arêtes qui le constituent.
0 9 3 ∞ 7
9 0 1 8 ∞
1. La matrice d’adjacence est : M = 3 1 0 4 2 .
∞ 8 4 0 ∞
7 ∞ 2 ∞ 0
189
·
Partie 10 Recherche d’un plus court chemin
190
·
Chapitre 13 Recherche d’un plus court chemin (sauf TSI et TPC)
else:
[Link]([-1, inf, False])
# la valeur -1 n'est pas utilisée car distance infinie
# False : ville non sélectionnée
return VILLES
# initialisation du programme
M=[[0, 9, 3, inf, 7], [9, 0, 1, 8, inf], [3, 1, 0, 4, 2],\
[inf, 8, 4, 0, inf], [7, inf, 2, inf, 0]]
191
·
Partie 10 Recherche d’un plus court chemin
192
·
Chapitre 13 Recherche d’un plus court chemin (sauf TSI et TPC)
2e itération : position = 2
•• On parcourt les villes X non sélectionnées : 0, 1, 4.
On obtient alors : VILLES=[[2,7,False],[2,5,False],[3,4,True],[−1,0,True],
[2,6,False]].
•• On cherche dans les villes X non sélectionnées (variable False) celle où la
variable « distance depuis la ville de départ » est minimale. C’est la ville 1.
On obtient alors : position = 1 et VILLES=[[2,7,False],[2,5,True],[3,4,True],
[−1,0,True],[2,6,False]].
3e itération : position = 1
•• On parcourt les villes X non sélectionnées : 0, 4.
On obtient alors : VILLES=[[2,7,False],[2,5,True],[3,4,True],[−1,0,True],
[2,6,False]].
•• On cherche dans les villes X non sélectionnées (variable False) celle où la
variable « distance depuis la ville de départ » est minimale. C’est la ville 4.
On obtient alors : position = 4 et VILLES=[[2,7,False],[2,5,True],[3,4,True],
[−1,0,True],[2,6,True]].
4e itération : position = 4
•• On parcourt les villes X non sélectionnées : 0.
On obtient alors : VILLES=[[2,7,False],[2,5,True],[3,4,True],[−1,0,True],
[2,6,True]].
•• On cherche dans les villes X non sélectionnées (variable False) celle où la
variable « distance depuis la ville de départ » est minimal. C’est la ville 0.
On obtient alors : position = 0 et VILLES = [[2,7,True], [2,5,True], [3,4,True],
[−1,0,True], [2,6,True]].
Pour obtenir le trajet, on part de la ville d’arrivée, la distance minimale entre la ville
de départ et la ville d’arrivée est obtenue par VILLES[arrivée][1] = 7. Pour
obtenir le trajet, on obtient la ville précédente avec VILLES[arrivée][0] = 2
et, de proche en proche, on remonte à la ville de départ.
193
·
Partie 10 Recherche d’un plus court chemin
Dans le pire des cas, on a (n-1) itérations dans la boucle while. Pour
chaque valeur de position, on a :
•• 1 comparaison, 1 calcul de somme, 1 test et deux affectations pour
chaque valeur de i : 5n opérations élémentaires.
•• 1 affectation : 1 opération élémentaire.
•• Recherche du minimum : trois comparaisons et deux affectations pour
chaque valeur de i : 5n opérations élémentaires.
•• 2 affectations : 2 opérations élémentaires.
On a donc ( 2n + 1) + ( n − 1) × ( 5n + 1 + 5n + 2 ) = 2n + 1 + ( n − 1)(10 n + 3) opé-
rations élémentaires.
La complexité dans le pire des cas est quadratique en O(n2).
0 8 18 ∞ 3
8 0 4 1 10
5. La matrice d’adjacence est : M2 = 18 4 0 ∞ ∞ .
∞ 1 ∞ 0 2
3 10 ∞ 2 0
194
·
Chapitre 13 Recherche d’un plus court chemin (sauf TSI et TPC)
Une heuristique est un algorithme qui calcule rapidement une solution pouvant
être approximative. On utilise la distance euclidienne (ou distance à vol
d’oiseau) pour estimer le coût restant h ( i ) permettant d’atteindre le sommet
arrivée à partir du sommet i.
On utilise les listes de listes pour représenter les matrices dans Python.
[Link]() permet d’inverser les éléments de la liste L.
1. Construire la matrice d’adjacence (Mi, j)0≤i,j≤n−1 (appelée également matrice
de distance) du graphe G, définie par :
Pour tous les indices i, j, Mi, j représente la distance entre les sommets d’origine
i et d’extrémité j.
Lorsque les sommets ne sont pas reliés, cette distance vaut l’infini. On définit la
variable inf=1e10 qui représente une distance infinie.
2. L’algorithme A* est une variante de l’algorithme de Dijkstra. On dispose
pour chaque sommet i d’une estimation du coût restant pour atteindre le som-
met arrivée à partir du sommet i : h ( i ) = distance euclidienne (ou distance à
vol d’oiseau) entre le sommet i et le sommet arrivée. On définit la fonction
d’évaluation f telle que : f ( i ) = g ( i ) + h ( i ).
•• g ( i ) est le coût réel du chemin optimal entre le sommet départ et le sommet
i dans la partie déjà explorée ;
•• h ( i ) est le coût estimé du chemin qui reste à parcourir entre i et arrivée.
On définit la liste SOMMETS contenant les informations suivantes pour chaque
sommet :
[sommet précédent sur le chemin, distance parcourue depuis le sommet de départ,
195
·
Partie 10 Recherche d’un plus court chemin
Analyse du problème
La fonction h est une fonction heuristique telle que h ( i ) est le coût estimé du che-
min qui reste à parcourir entre le sommet i et le sommet arrivée. On utilise
la distance à vol d’oiseau dans ce problème alors que, dans l’exercice suivant
« Variantes de l’algorithme A* − Distance de Manhattan », on utilise la distance de
Manhattan. L’idée est de choisir un sommet qui semble être le plus prêt du sommet
d’arrivée.
La fonction d’évaluation permet de déterminer quel sommet est sélectionné en
premier, c’est-à-dire retiré de la frontière entre les sommets sélectionnés et les
sommets non sélectionnés : f ( i ) = g ( i ) + h ( i ) renvoie une estimation de la distance
entre le sommet de départ et le sommet d’arrivée en passant par le sommet i du
graphe. On considère un graphe orienté dont le poids des arcs est un réel positif.
196
·
Chapitre 13 Recherche d’un plus court chemin (sauf TSI et TPC)
0 3 2 ∞ ∞ ∞
∞ 0 3 3 2 ∞
∞ 3 0 5 4 ∞
1. La matrice d’adjacence est : M = .
∞ ∞ ∞ 0 ∞ 2
∞ ∞ 4 2 0 ∞
∞ ∞ ∞ 2 2 0
198
·
Chapitre 13 Recherche d’un plus court chemin (sauf TSI et TPC)
3.
inf=float("inf")
M=[[0,3,2,inf,inf,inf],[inf,0,3,3,2,inf],\
[inf,3,0,5,4,inf],[inf,inf,inf,0,inf,2],\
[inf,inf,4,2,0,inf],[inf,inf,inf,2,2,0]]
départ, arrivée=0, 5
H=[5, 2, 3.2, 1.5, 1, 0]
L2, dist2=algoA(M, H, départ, arrivée)
print('Algo A* chemin :',L2,'; distance',dist2)
199
·
Partie 10 Recherche d’un plus court chemin
200
·
Chapitre 13 Recherche d’un plus court chemin (sauf TSI et TPC)
201
·
Partie 10 Recherche d’un plus court chemin
Écrire une fonction MANHATTAN qui admet comme arguments d’entrée un dic-
tionnaire dico, le sommet départ, le sommet arrivée et le réel w. Cette
fonction retourne le chemin suivi ainsi que la distance parcourue entre départ
et arrivée en utilisant l’algorithme décrit précédemment.
Écrire le programme principal permettant de déterminer un plus court chemin
entre le sommet de départ 10 et le sommet d’arrivée 13. Le programme affi-
chera le chemin suivi ainsi que la distance parcourue pour w = 0, w = 0.5 et
w = 1.
5. Comment appelle-t-on les algorithmes lorsque w = 0, w = 0.5 et w = 1 ?
Analyse du problème
La fonction h est une fonction heuristique telle que h ( i ) est le coût estimé du che-
min qui reste à parcourir entre le sommet i et le sommet arrivée. On utilise la
distance de Manhattan alors que dans l’exercice précédent « Algorithme A* » on
utilise la distance euclidienne (ou distance à vol d’oiseau).
On considère différentes fonctions d’évaluation dans ce problème pour sélection-
ner un sommet :
•• Algorithme glouton BFS (question 3) : la fonction d’estimation f ( i ) = h ( i ) ren-
voie la distance de Manhattan entre le sommet i et le sommet arrivée.
•• Algorithme de la question 4 : la fonction d’évaluation f ( i ) = (1 − w ) ⋅ g ( i ) + w ⋅ h ( i )
renvoie une estimation de la distance entre le sommet de départ et le sommet
d’arrivée en passant par un sommet i.
1.
dico={0:[1,5], 1 :[0,2,6], 2 :[1,3], 3 :[2,4], 4 :[3,9],\
5 :[0,6,10], 6 :[1,5,11], 7 :[], 8 :[], 9 :[4,14],\
10 :[5,11,15], 11 :[6,10], 12 :[], 13 :[14, 18],\
14 :[9,13,19], 15 :[10,20], 16 :[], 17 :[],\
18 :[13, 19, 23], 19 :[14,18, 24], 20 :[15,21],\
21 :[20,22], 22 :[21,23], 23 :[18, 22,24], 24 :[19,23]}
Voir exercice 11.1 « Opérations de base sur les dictionnaires » dans le chapitre
« Dictionnaire, pile, file, deque » pour l’utilisation des dictionnaires.
Le sommet 6 est relié aux sommets 1, 5 et 11. La valeur de la clé 6 est la
liste des sommets adjacents [1, 5, 11].
Le nombre d’éléments du dictionnaire correspond au nombre n de sommets
du graphe. On définit nb_rues le nombre de rues. Comme le nombre
d’avenues est égal au nombre de rues, alors :
import math as m # module math renommé m
nb_rues=int([Link](n)) # n = nombre de sommets
# = nombre de rues * nombre d’avenues
202
·
Chapitre 13 Recherche d’un plus court chemin (sauf TSI et TPC)
203
·
Partie 10 Recherche d’un plus court chemin
204
·
Chapitre 13 Recherche d’un plus court chemin (sauf TSI et TPC)
position=départ
while (position!=arrivée):
indice=position
for i in range(n): # i décrit tous les sommets
if SOMMETS[i][2]==False: # sommet non sélectionné
L=dico[position]
if i in L: # position et i sont adjacents
g_i=SOMMETS[position][1]+1
# g(i) = coût réel entre départ et i
f_i=H[i] # coût estimé entre i et arrivée
if f_i<SOMMETS[i][3]:
SOMMETS[i][1]=g_i
# distance départ->i = g(i)
SOMMETS[i][3]=f_i
# fonction d’évaluation f(i) = H[i]
SOMMETS[i][0]=position
# sommet précédent sur le chemin
# recherche du minimum des valeurs de f(i) = H[i]
# pour les sommets non sélectionnés
val_min=inf # initialisation de val_min à +infini
for i in range(n): # i varie entre 0 inclus et n exclu
if SOMMETS[i][2]==False and SOMMETS[i][3]<val_min:
indice=i
val_min=SOMMETS[i][3] # f(i)
if indice==position:
return [],inf # on n’atteint pas le sommet arrivée
else:
SOMMETS[indice][2]=True # ce sommet est sélectionné
position=indice # nouvelle valeur de position
205
·
Partie 10 Recherche d’un plus court chemin
# initialisation du programme
départ, arrivée=10, 13 # sommet de départ et sommet d'arrivée
L2, dist2=BFS(dico, départ, arrivée)
print('Algo BFS : chemin :', L2, '; distance', dist2)
w=0
for i in range(3):
L2, dist2=MANHATTAN(dico, départ, arrivée, w)
print('w =',w, '; chemin :', L2, '; distance', dist2)
w=w+0.5
206
·
Chapitre 13 Recherche d’un plus court chemin (sauf TSI et TPC)
207
Partie 11
Programmation
dynamique
Plan
14. Programmation dynamique (Spé) (sauf TSI et TPC) 211
14.1 : Suite des nombres de Fibonacci, Top Down et Bottom Up 211
14.2 : Rendu de monnaie 214
14.3 : Problème du sac à dos 223
14.4 : Algorithme de Floyd-Warshall 231
Programmation 14
dynamique (Spé)
(sauf TSI et TPC)
Analyse du problème
La méthode « diviser pour régner » permet de décomposer le problème initial en
deux sous-problèmes.
Afin d’éviter de calculer plusieurs fois le même nombre de Fibonacci, on utilise la
technique de mémoïsation.
Cours :
La méthode « diviser pour régner » peut se décomposer en trois étapes :
•• Diviser : on divise le problème initial en plusieurs sous-problèmes.
•• Régner : on traite récursivement chacun des sous-problèmes.
•• Combiner : on combine les différents sous-problèmes pour résoudre le problème de
départ. 211
·
Partie 11 Programmation dynamique
Cette méthode donne de très bons résultats dans de nombreux problèmes : dichotomie, tri
par partition-fusion, tri rapide.
La méthode « diviser pour régner » a parfois des faiblesses avec des appels récursifs
redondants. Les sous-problèmes ne sont pas toujours indépendants. On peut être amené à
résoudre plusieurs fois le même sous-problème.
Une solution consiste à utiliser la technique de mémoïsation en stockant les résultats déjà
calculés. On rencontre deux techniques :
•• Technique récursive « Top Down » (de haut en bas) de mémoïsation. Lors d’un appel
récursif, on regarde dans une liste intermédiaire si le sous-problème est déjà traité.
Top Down : on résout dans le sens des données de grande taille vers les données de
petite taille.
•• Technique itérative « Bottom Up » (de bas en haut) : on résout dans le sens des données
de petite taille vers les données de grande taille (c’est l’ordre inverse de « Top Down »).
On stocke également les résultats obtenus dans une liste intermédiaire.
L’algorithme « Bottom Up » résout tous les sous-problèmes de taille inférieure alors que l’al-
gorithme « Top Down » ne résout que les sous-problèmes de taille inférieure dont il a besoin.
1.
def fibo1(n):
# la fonction renvoie le nombre de Fibonacci Fn
# pour l’entier n
if n==0:
return 0 # condition d’arrêt
elif n==1:
return 1 # condition d’arrêt
else:
return (fibo1(n-1)+fibo1(n-2))
# appel récursif
fib(4) fib(3)
2 1
1 1
fib(1) fib(0)
212
·
Chapitre 14 Programmation dynamique (Spé) (sauf TSI et TPC)
dico={}
n=15
print('fibo2 =', fibo2(n, dico))
213
·
Partie 11 Programmation dynamique
214
·
Chapitre 14 Programmation dynamique (Spé) (sauf TSI et TPC)
4. Écrire une fonction itérative rendu4 qui admet comme arguments une liste
S, un entier X et une liste L. La fonction retourne le nombre minimal de pièces
nécessaires pour rendre la somme X. On part de la plus petite somme possible
à rendre et on calcule les éléments suivants de L en utilisant la récurrence (2).
Utilise-t-on la technique « Top Down » ou « Bottom Up » ?
5. On souhaite reconstruire la solution optimale à partir de l’information calcu-
lée, c’est-à-dire obtenir la liste des pièces utilisées. On définit la liste T :
•• T[x] > 0 si on a utilisé la pièce d’indice T[x] pour rendre la somme x dans la
récurrence (2) ;
•• T[x] = 0 sinon.
On définit une liste PIECES initialement vide. On considère une boucle while
en partant de x = X :
•• T[x] désigne l’indice de la pièce utilisée pour rendre la somme x dans la récur-
rence (2) ;
•• ajouter dans la liste PIECES la valeur de la pièce utilisée ;
•• retrancher cette valeur à x.
Modifier la fonction rendu3 qui utilise la technique « Top Down » pour obte-
nir la liste des pièces utilisées.
6. Modifier la fonction rendu4 qui utilise la technique « Bottom Up » pour
obtenir la liste des pièces utilisées.
Analyse du problème
On étudie plusieurs algorithmes permettant d’optimiser le rendu de monnaie. La
méthode « diviser pour régner » permet de décomposer le problème initial en deux
sous-problèmes. La programmation dynamique permet d’obtenir une solution opti-
male en utilisant deux techniques : « Top Down » et « Bottom Up ».
On verra la différence entre la méthode gloutonne et la programmation dynamique.
1. On suppose que la liste S est triée par ordre croissant des valeurs.
def rendu1(S, X):
# la fonction renvoie le nombre de pièces nécessaires
# pour rendre la somme X en utilisant la liste S :
# S[i] = valeur de la pièce d’indice i
if X==0: # condition d’arrêt
return 0
else:
# recherche de i le plus grand tel que S[i] <= X
i=len(S)-1
while S[i]>X:
i=i-1
# ajoute 1 au nombre de pièces ;
215
·
Partie 11 Programmation dynamique
S=[1, 4, 6]
X=8
print(rendu1(S, X)) # on obtient : 3
Cours :
La méthode « diviser pour régner » peut se décomposer en trois étapes :
•• Diviser : on divise le problème initial en plusieurs sous-problèmes.
•• Régner : on traite récursivement chacun des sous-problèmes.
•• Combiner : on combine les différents sous-problèmes pour résoudre le problème de
départ.
Dans la méthode gloutonne (greedy en anglais), on effectue une succession de choix, cha-
cun d’eux semble être le meilleur sur le moment. On résout alors le sous-problème mais on
ne revient jamais sur le choix déjà effectué.
L’algorithme est de type « diviser pour régner » puisqu’on décompose le
problème (calcul de L[X]) en un sous-problème (calcul de L[X − S[i]] avec i
le plus grand tel que S[i] ≤ X). On calcule récursivement le sous-problème.
À chaque étape de l’algorithme, on commence par rendre la plus grande
pièce possible, c’est-à-dire la plus grande pièce dont la valeur est infé-
rieure à la somme à rendre. C’est la solution qui semble être la meilleure
et la plus intuitive. On déduit alors de cette pièce la somme à rendre et on
est ramené à un sous-problème avec une somme à rendre plus petite. On
recommence jusqu’à obtenir une somme nulle.
Cet algorithme est très simple mais à chaque étape on n’étudie pas tous les
cas possibles puisqu’on se contente de choisir la pièce la plus grande que
l’on peut rendre.
Dans le cas où S = [1, 4 , 6] et X = 8, on n’obtient pas la solution optimale.
L’algorithme glouton (greedy algorithm, en anglais) renvoie 3 (1 pièce de
6 et 2 pièces de 1) alors que la solution optimale est 2 (2 pièces de 4).
2.
def rendu2(S, X):
# la fonction renvoie le nombre de pièces nécessaires
# pour rendre la somme X en utilisant la liste S :
# S[i] = valeur de la pièce d’indice i
if X==0: # condition d’arrêt
return 0
else:
mini=X # recherche du minimum de X-S[i]
for i in range(len(S)): # i varie entre 0 inclus
# et len(S) exclu
if S[i]<=X: # il faut que Si <= X
res=rendu2(S, X-S[i])
# appel récursif pour
# rendre la monnaie à X-S[i]
216
·
Chapitre 14 Programmation dynamique (Spé) (sauf TSI et TPC)
if res<mini:
mini=res
return 1+mini # ajoute 1 au nombre de pièces
S=[1, 4, 6]
X=8
print(rendu2(S, X)) # on obtient 2, c’est-à-dire la solution
# optimale alors que rendu1(S, X)
# retourne 3
3 2
2 1 1 0
1 0 0 0
217
·
Partie 11 Programmation dynamique
218
·
Chapitre 14 Programmation dynamique (Spé) (sauf TSI et TPC)
dico={}
S=[1, 4, 6]
X=8
print(rendu3_dico(S, X, dico))
Cours :
La programmation dynamique est souvent utilisée pour résoudre des problèmes d’optimi-
sation. Elle comprend différentes étapes :
•• Recherche d’une récurrence pour déterminer la valeur d’une solution optimale.
•• Utilisation de la technique Top Down ou Bottom Up.
La programmation dynamique et la méthode gloutonne reposent sur l’utilisation de
sous-problèmes. Il y a une différence importante :
•• Dans la programmation dynamique, on calcule toutes les solutions des sous-problèmes
que l’on combine pour obtenir une solution optimale.
•• Dans la méthode gloutonne, on choisit une solution qui semble être la meilleure et on
résout le sous-problème qui en résulte.
On rencontre deux techniques dans la programmation dynamique :
•• Technique récursive « Top Down » de mémoïsation : on résout dans le sens des don-
nées de grande taille vers les données de petite taille. Lors d’un appel récursif, on
regarde dans une liste intermédiaire si le sous-problème est déjà traité.
•• Technique itérative « Bottom Up » : on résout dans le sens des données de petite taille
vers les données de grande taille (c’est l’ordre inverse de « Top Down »). On stocke
également les résultats obtenus dans une liste intermédiaire.
L’arbre ci-dessous représente les différents appels de la fonction
rendu3([1, 2, 5], 4).
219
·
Partie 11 Programmation dynamique
3 2
2 1
1 0
220
·
Chapitre 14 Programmation dynamique (Spé) (sauf TSI et TPC)
221
·
Partie 11 Programmation dynamique
if res<mini:
mini=res
indice=i
L[X]=1+mini # technique de mémoïsation
T[X]=indice # indice de la pièce utilisée
# pour rendre la somme X
return 1+mini # ajoute 1 au nombre de pièces
S=[1, 2, 5]
X=4
L=[0 for i in range(X+1)] # initialisation - liste L
# avec des valeurs nulles
T=[0 for i in range(X+1)] # initialisation - liste T
# avec des valeurs nulles
print(rendu3_piece(S, X, L, T))
PIECES=[]
x=X
while x>0:
[Link](S[T[x]])
# T[x] = indice de la pièce utilisée pour
# rendre la somme x
# S[T[x]] = valeur de la pièce d’indice T[x]
x=x-S[T[x]]
# on retranche la valeur S[T[x]] à x pour
# chercher les autres pièces
print(PIECES)
222
·
Chapitre 14 Programmation dynamique (Spé) (sauf TSI et TPC)
# et len(S) exclu
if S[i]<=x and L[x-S[i]]<mini:
mini=L[x-S[i]]
indice=i # indice de la pièce
L[x]=1+mini
T[x]=indice # indice de la pièce utilisée
# pour rendre la somme x
# création de la liste des pièces utilisées
# pour rendre la monnaie
PIECES=[]
x=X
while x>0:
[Link](S[T[x]])
# T[x] = indice de la pièce utilisée pour
# rendre la somme x
# S[T[x]] = valeur de la pièce d’indice T[x]
x=x-S[T[x]]
# on retranche la valeur S[T[x]] à x pour
# chercher les autres pièces
return L[X], PIECES
S=[1, 2, 5]
X=4
L=[0 for i in range(X+1)] # initialisation - liste L
# avec des valeurs nulles
T=[0 for i in range(X+1)] # initialisation - liste T
# avec des valeurs nulles
print(rendu4_piece(S, X, L, T))
223
·
Partie 11 Programmation dynamique
224
·
Chapitre 14 Programmation dynamique (Spé) (sauf TSI et TPC)
Analyse du problème
On étudie plusieurs méthodes permettant de maximiser la valeur des objets insérés
dans un sac à dos. La programmation dynamique permet d’obtenir une solution
optimale en utilisant deux techniques : « Top Down » et « Bottom Up ». Une liste
temporaire permet de stocker les résultats des sous-problèmes. On verra la diffé-
rence entre les deux techniques concernant le nombre de sous-problèmes à traiter.
1.
def algo1(S, M): # S liste de listes avec [valeur, masse]
# les objets sont triés par ordre décroissant valeur/masse
# la fonction retourne la valeur des objets que l’on peut
# insérer avec une masse maximale M
v_total=0 # initialisation de la valeur totale des objets
m_total=0 # initialisation de la masse totale des objets
n=len(S)
for i in range(n):
if m_total+S[i][1]<=M: # teste si nouvelle
# masse totale <= M
v_total+=S[i][0] # calcule la nouvelle
# valeur totale
m_total+=S[i][1] # calcule la nouvelle
# masse totale
return v_total # retourne la valeur totale
# des objets
225
·
Partie 11 Programmation dynamique
Cette méthode est appelée méthode gloutonne car elle consiste à faire le
meilleur choix sur le moment, c’est-à-dire insérer l’objet qui a le plus grand
rapport valeur/masse.
M=30
S=[[15, 6], [60, 25], [10, 5], [7, 8], [10, 20]]
# [valeur, masse]
print('ALGO1 :', algo1(S, M)) # affiche 32
226
·
Chapitre 14 Programmation dynamique (Spé) (sauf TSI et TPC)
M=30
S=[[15, 6], [60, 25], [10, 5], [7, 8], [10, 20]]
# [valeur, masse]
print('ALGO2 :', algo2(S, M, len(S)))
227
·
Partie 11 Programmation dynamique
M=30
S=[[15, 6], [60, 25], [10, 5], [7, 8], [10, 20]]
# [valeur, masse]
L=[[0 for j in range(len(S)+1)] for i in range(M+1)]
print('ALGO3 :', algo3(S, M, len(S), L))
228
·
Chapitre 14 Programmation dynamique (Spé) (sauf TSI et TPC)
M=30 # entier
S=[[15, 6], [60, 25], [10, 5], [7, 8], [10, 20]]
# [valeur, masse]
229
·
Partie 11 Programmation dynamique
Pour obtenir la liste des objets insérés, il faut créer une liste OBJETS
vide et considérer une boucle for en partant de len(S). Si le ième objet
d’indice i–1 a été inséré, on l’ajoute dans la liste OBJETS. Il faut ensuite
retrancher à m la masse de cet objet inséré et tester T[m][i] avec la
nouvelle masse et le nouvel indice.
Le programme principal affiche :
70 # valeur totale du sac à dos
[[10, 5], [60, 25]] # on a ajouté 1 objet de valeur 10
# et une autre de valeur 60
230
·
Chapitre 14 Programmation dynamique (Spé) (sauf TSI et TPC)
M=30 # entier
S=[[15, 6], [60, 25], [10, 5], [7, 8], [10, 20]]
# [valeur, masse]
L=[[0 for j in range(len(S)+1)] for i in range(M+1)]
T=[[0 for j in range(len(S)+1)] for i in range(M+1)]
print('algo4_objets :', algo4_objets(S, M, L, T))
dk ( i , j ) = min ( dk −1 ( i , j ) , dk −1 ( i , k − 1) + dk −1 ( k − 1, j ))
231
·
Partie 11 Programmation dynamique
0
18 3
2 4
8
4 2 -1
1 3
1
On utilise les listes de listes pour représenter les matrices dans Python.
[Link]() permet d’inverser les éléments de la liste L.
( )
1. Construire la matrice d’adjacence Mi , j 0≤i , j ≤n−1 du graphe G, définie par :
Pour tous les indices i, j, Mi, j représente le poids de l’arc d’origine i et
d’extrémité j.
Lorsque les sommets ne sont pas reliés, le poids de l’arc vaut l’infini. On définit
la variable inf=1e10 qui représente un poids infini.
2. Écrire une fonction récursive Floyd1 qui admet comme arguments d’en-
trée la matrice d’adjacence M, le sommet de départ i, le sommet d’arrivée j et
l’entier k. Cette fonction retourne dk ( i , j ) avec la programmation dynamique.
Écrire le programme principal permettant d’afficher la plus petite distance par-
courue entre le sommet de départ 0 et le sommet d’arrivée 1 en utilisant la
fonction Floyd1.
L’algorithme utilise-t-il la méthode « diviser pour régner » ?
3. Pour éviter de calculer plusieurs fois dk ( i , j ), on définit une liste DIST
telle que DIST [ i ][ j ][ k ] = dk ( i , j ). L’indice k varie entre 0 et n inclus. Lorsque
DIST [ i ][ j ][ k ] n’a pas été calculé, DIST [ i ][ j ][ k ] = −∞ . Écrire une fonction
récursive Floyd2 qui admet comme arguments d’entrée la matrice d’adjacence
M, le sommet de départ i, le sommet d’arrivée j, l’entier k et la liste DIST ser-
vant à stocker les résultats intermédiaires. Cette fonction retourne dk ( i , j ) avec
la programmation dynamique.
Utilise-t-on la technique « Top Down » ou « Bottom Up » ?
4. Écrire une fonction itérative Floyd3 qui admet comme arguments d’en-
trée la matrice d’adjacence M, le sommet départ et le sommet arrivée.
Cette fonction retourne la distance d’un plus court chemin entre départ et
arrivée en utilisant l’algorithme de Floyd-Warshall avec la programmation
dynamique.
Utilise-t-on la technique « Top Down » ou « Bottom Up » ?
232
·
Chapitre 14 Programmation dynamique (Spé) (sauf TSI et TPC)
dk ( i , j ) = dk −1 ( i , k − 1) + dk −1 ( k − 1, j ) et dk ( i , j ) ≠ ∞
et PRECEDENT [ k − 1][ j ][ k − 1] ≠ −1
Écrire le programme principal permettant d’afficher le chemin suivi entre les
sommets départ et arrivée.
Analyse du problème
On considère des graphes orientés contenant des arêtes de poids négatif et n’ayant
pas de cycle de poids négatif. Le graphe n’est pas nécessairement fortement
connexe.
L’algorithme de Floyd-Warshall définit dk ( i , j ) la distance minimale d’un chemin
du sommet i au sommet j en empruntant des sommets intermédiaires d’indice stric-
tement inférieur à k.
0 ∞ 18 ∞ 3
8 0 4 ∞ ∞
1. La matrice d’adjacence est : M = ∞ ∞ 0 ∞ ∞ .
∞ 1 ∞ 0 ∞
∞ 2 ∞ −1 0
Comme le graphe est orienté, la matrice n’est pas nécessairement symé-
trique.
Cours :
La méthode « diviser pour régner » peut se décomposer en trois étapes :
•• Diviser : on divise le problème initial en plusieurs sous-problèmes.
•• Régner : on traite récursivement chacun des sous-problèmes.
•• Combiner : on combine les différents sous-problèmes pour résoudre le problème de
départ.
233
·
Partie 11 Programmation dynamique
Cours :
On rencontre deux techniques dans la programmation dynamique :
•• Technique récursive « Top Down » (de mémoïsation). Lors d’un appel récursif, on
regarde dans une liste intermédiaire si le sous-problème est déjà traité.
Top Down : on résout dans le sens des données de grande taille vers les données de
petite taille.
•• Technique itérative « Bottom Up » : on résout dans le sens des données de petite taille
vers les données de grande taille (c’est l’ordre inverse de « Top Down »). On stocke
également les résultats obtenus dans une liste intermédiaire.
3. La fonction Floyd2 utilise la programmation dynamique avec la tech-
nique « Top Down » (de mémoïsation) et permet d’obtenir une solution
optimale sans résoudre plusieurs fois le même sous-problème.
Dans le programme principal, on part de la plus grande valeur de k (ici
n) : distance2=Floyd2(M, départ, arrivée, n, DIST). On
décompose le problème (calcul dk (i , j ) en plusieurs sous-problèmes (calcul
de dk −1 (i , j ) , dk −1 (i , k − 1) , dk −1 ( k − 1, j )).
Pour éviter de calculer plusieurs fois dk (i , j ), on garde en mémoire le résul-
tat dans la liste DIST : DIST [i ][ j ] [ k ] = dk (i , j ). La liste doit contenir
(n)(n)(n + 1) valeurs.
•• i et j varient de 0 inclus à n exclu.
•• k varie de 0 inclus à n inclus.
234
·
Chapitre 14 Programmation dynamique (Spé) (sauf TSI et TPC)
235
·
Partie 11 Programmation dynamique
DIST[i][j][k]=min(a,b)
return DIST[départ][arrivée][n]
dk (i , j ) = dk −1 (i , k − 1) + dk −1 ( k − 1, j ) et dk (i , j ) ≠ ∞
et PRECEDENT [ k − 1] [ j ] [ k − 1] ≠ −1
PRECEDENT=[[[-1 for k in range(n+1)] for j in range(n)]\
for i in range(n)]
# tous les éléments valent -1
for i in range(n):
for j in range(n):
if i!=j and M[i][j]<inf:
PRECEDENT[i][j][0]=i
for k in range(1, n+1):
for i in range(n):
for j in range(n):
if DIST[i][j][k]==DIST[i][j][k-1]:
PRECEDENT[i][j][k]=PRECEDENT[i][j][k-1]
if DIST[i][j][k]==DIST[i][k-1][k-1]\
+DIST[k-1][j][k-1]\
and DIST[i][j][k]!=inf\
and PRECEDENT[k-1][j][k-1]!=-1:
PRECEDENT[i][j][k]=PRECEDENT[k-1][j][k-1]
239
·
Partie 12 Intelligence artificielle et jeux
1.
def fic_data(fichier):
# la fonction retourne une matrice :
# n lignes et trois colonnes
# n = nombre de lignes du fichier
f=open(fichier, 'r') # ouverture de fichier (str)
# en lecture
f_données=[Link]() # récupère toutes les lignes du
# fichier dans la liste f_données
n=len(f_données) # nombre de lignes du fichier
data=[[0 for j in range(3)] for i in range(n)]
# matrice : n lignes et 3 colonnes
# longueur, largeur et numéro de l’espèce
for i in range(0, n): # i varie entre 0 inclus et n exclu
ligne=f_données[i].strip().split(";")
# split(';') permet de séparer la ligne en une liste
# de mots avec le séparateur ";"
# strip() permet d’enlever les caractères d’échappement
# (ici saut de ligne)
data[i][0], data[i][1]=float(ligne[0]), float(ligne[1])
if (ligne[2]=="setosa"):
data[i][2]=0 # numéro 0 désigne setosa
elif (ligne[2]=="versicolor"):
data[i][2]=1 # numéro 1 désigne versicolor
else: # virginica
data[i][2]=2 # numéro 2 désigne virginica
[Link]()
return data
2.
def calc_dist(ptA, ptB):
# distance euclidienne entre ptA et ptB
# ptA est une liste [longueurA, largeurA]
# ptB est une liste [longueurB, largeurB]
return ((ptB[0]-ptA[0])**2+(ptB[1]-ptA[1])**2)**(0.5)
Remarque :
On peut envisager plusieurs définitions de la distance entre A ( x A , yA ) et B ( xB , yB ) :
•• distance euclidienne : distance = ( xB − x A )2 + ( yB − yA )2
•• distance de Manhattan : distance = xB − x A + yB − yA
(
•• distance de Tchebychev : distance = max xB − x A , yB − yA )
241
·
Partie 12 Intelligence artificielle et jeux
3. Pour une valeur de k fixée, on calcule la distance d’un point à tous les
points du fichier de données. On cherche l’espèce majoritaire parmi les k
plus proches voisins.
def algoknn(data, pt_search, k):
# calcul de la distance de pt_search à tous les points
# de data
# la fonction retourne une prédiction de l’espèce de l’iris
# algorithme des k(int) plus proches voisins
# pt_search : liste de deux valeurs :
# longueur et largeur des pétales
n=len(data) # nombre de lignes de data
tab_dist=[[0 for j in range(2)] for i in range(n)]
# matrice avec distance et numéro espèce
for i in range(len(data)): # i varie entre 0 inclus
# et len(data) exclu
iris1=[data[i][0],data[i][1]]
mat_dist[i][0]=calc_dist(pt_search,iris1)
tab_dist[i][1]=data[i][2]
# on récupère la distance et la désignation
# de l’espèce
tab_dist.sort() # tri par ordre croissant
# des distances
# on récupère la liste des distances triées par ordre
# croissant
# choix de l’espèce
list_nb_espece=[[0, i] for i in range(3)]
# liste de listes : (total, numéro de l’espèce)
for i in range(k): # i varie entre 0 inclus
# et k exclu
indice=int(tab_dist[i][1]) # tab_dist[i][1] :
# numéro de l’espèce
list_nb_espece[indice][0]+=1
list_nb_espece.sort() # tri de list_nb_espece par ordre
# croissant de total
242
·
Chapitre 15 Intelligence artificielle et jeu à deux joueurs (Spé)
elif data[i][2]==1:
[Link](data[i][0])
[Link](data[i][1])
else:
[Link](data[i][0])
[Link](data[i][1])
[Link]()
[Link]("longueur des pétales")
[Link]("largeur des pétales")
[Link](x1, y1, color='blue', marker='v')
[Link](x2, y2, color='red', marker='.')
[Link](x3, y3, color='green', marker='+')
[Link](pt_search[0], pt_search[1], color='black',\
linewidth=8)
[Link](['iris setosa', 'iris versicolor',\
'iris virginica'])
[Link]()
predict=algoknn(data, pt_search, k)
if predict==0:
print(predict, 'setosa')
elif predict==1:
print(predict, 'versicolor')
else:
print(predict, 'virginica')
On obtient le graphique suivant avec le fichier « [Link] » (voir le site Dunod
pour télécharger le fichier de données).
1.5
1.0
0.5
0.0
1 2 3 4 5 6 7
longuer des pétales
243
·
Partie 12 Intelligence artificielle et jeux
Remarque :
L’algorithme des k plus proches voisins est basé sur un algorithme d’apprentissage
à partir d’observations étiquetées. Le modèle prédictif est utilisé dans plusieurs cas :
•• Régression : le résultat est un réel. Le résultat est la moyenne des valeurs des k
plus proches voisins.
Exemples : prédiction de la solubilité d’une molécule dans l’eau en mg/mL.
•• Classification : le résultat obtenu est une classe d’appartenance (0, 1, 2, …, C–1)
si on considère C classes possibles. Dans l’exemple précédent, on a C = 3 classes
(0 pour setosa, 1 pour versicolor et 2 pour virginica).
•• Classification binaire : le résultat obtenu est 0 ou 1. Exemples : l’e-mail reçu
est-il un spam ? La photo est-elle celle d’un chat ? On utilise un nombre impair
de voisins pour ne pas avoir d’ex-aequo.
244
·
Chapitre 15 Intelligence artificielle et jeu à deux joueurs (Spé)
Classe réelle
setosa versicolor virginica
setosa … … …
Classe
versicolor … … …
prédite
virginica … … …
Classe réelle
versicolor non versicolor
Classe versicolor True Positives (TP) False Positives (FP)
prédite non versicolor False Negatives (FN) True Negatives (TN)
245
·
Partie 12 Intelligence artificielle et jeux
TN
•• spécificité =
TN + FP
TP
•• précision =
TP + FP
Écrire une fonction matconf_indicateurs qui admet comme arguments
data1 (liste d’apprentissage) et data2 (liste de test). La fonction
retourne la matrice de confusion pour l’iris versicolor avec k = 2, rappel,
spécificité et précision.
5. Écrire une fonction predict_k qui admet comme arguments data1 (liste
d’apprentissage) et data2 (liste de test). La fonction retourne la valeur opti-
male de k en utilisant les étapes suivantes :
•• Pour toutes les valeurs de k possibles, on applique l’algorithme des k plus
proches voisins à toutes les espèces du fichier de test.
•• On calcule pour chaque valeur de k le pourcentage d’espèces mal prédites du
fichier de test.
•• On en déduit la valeur optimale de k correspondant au pourcentage d’espèces
mal prédites le plus faible.
Analyse du problème
L’objectif de l’algorithme des k plus proches voisins est de prédire la classe (clas-
sification) ou la valeur (régression) d’un échantillon à partir d’exemples connus.
On sépare les données en un jeu d’entraînement (fichier d’apprentissage : « fic01.
csv ») et un jeu de test (fichier de test : « [Link] »). La répartition des données
entre le jeu d’entraînement et le jeu de test peut être 80 %-20 %, 70 %-30 % ou
même 50 %-50 %. Le jeu d’entraînement sert à apprendre le modèle (algorithme
des k plus proches voisins). Le jeu de test sert à estimer l’erreur de généralisation
du modèle.
246
·
Chapitre 15 Intelligence artificielle et jeu à deux joueurs (Spé)
ligne=f_données[i].strip().split(";")
# split(';') permet de séparer la ligne en une liste
# de mots avec le séparateur ';'
# strip() permet d’enlever les caractères d’échappement
# (ici saut de ligne)
data[i][0], data[i][1]=float(ligne[0]), float(ligne[1])
if (ligne[2]=="setosa"):
data[i][2]=0 # numéro 0 désigne setosa
elif (ligne[2]=="versicolor"):
data[i][2]=1 # numéro 1 désigne versicolor
else: # virginica
data[i][2]=2 # numéro 2 désigne virginica
[Link]()
return data
2.
def calc_dist(ptA, ptB):
# distance euclidienne entre ptA et ptB
# ptA est une liste [longueurA, largeurA]
# ptB est une liste [longueurB, largeurB]
return ((ptB[0]-ptA[0])**2+(ptB[1]-ptA[1])**2)**(0.5)
247
·
Partie 12 Intelligence artificielle et jeux
Classe réelle
setosa versicolor virginica
setosa … … …
Classe
versicolor … … …
prédite
virginica … … …
248
·
Chapitre 15 Intelligence artificielle et jeu à deux joueurs (Spé)
Classe réelle
setosa versicolor virginica
setosa … … …
Classe
versicolor … … …
prédite
virginica … … …
Classe réelle
setosa versicolor virginica
setosa … … …
Classe
versicolor … … …
prédite
virginica … … …
Remarque : On peut avoir des faux négatifs ou des faux positifs avec les tests pour
la Covid.
5. On sépare le fichier de l’exercice précédent « Algorithme des k plus
proches voisins » en deux fichiers : fichier1 (fichier d’apprentissage
correspondant au jeu d’entraînement) et fichier2 (fichier de test cor-
respondant au jeu de test).
249
·
Partie 12 Intelligence artificielle et jeux
250
·
Chapitre 15 Intelligence artificielle et jeu à deux joueurs (Spé)
251
·
Partie 12 Intelligence artificielle et jeux
Analyse du problème
Dans l’apprentissage non supervisé, l’objectif est de comprendre la structure des
données. Contrairement à l’apprentissage supervisé (voir exercice 15.1 « Algo-
rithme des k plus proches voisins » avec la prédiction de la classe d’un échantillon à
partir d’exemples connus), on ne connaît pas les clusters. En pratique, on regroupe
les données proches entre elles, on leur attribue des clusters qu’il faut interpréter
ensuite.
Exemple : regrouper des clients qui ont des profils similaires, regrouper les docu-
ments d’un corpus par thème (les thèmes émergeant de cet algorithme ne sont pas
connus). C’est une méthode d’apprentissage non supervisé puisqu’on ne connaît
pas les clusters à l’avance.
4
y
33
11
33 44 55 66 77 88
xx
252
·
Chapitre 15 Intelligence artificielle et jeu à deux joueurs (Spé)
3 Clusters
4
y
3 4 5 6 7 8
x
3 Clusters
4
y
3 4 5 6 7 8
x
253
·
Partie 12 Intelligence artificielle et jeux
2.
import random as rd # module random renommé rd
def initpoints(pts_groupe):
# la fonction retourne deux listes X et Y
# contenant 3 groupes
# le nombre de valeurs aléatoire pour chaque groupe
# est pts_groupe
N=pts_groupe*3 # N = nombre total de points
X=[0 for i in range(N)] # liste des abscisses pour
# les N points
Y=[0 for i in range(N)] # liste des ordonnées pour
# les N points
for k in range(3): # k varie entre 0 inclus et 3 exclu
if k==0:
xcentre=3 # abscisse du centre du premier
# groupe (ex.3)
ycentre=1 # ordonnée du centre du premier
# groupe (ex. 1)
delta=2.6 # 2.6 ou 0.6
elif k==1:
xcentre=8 # abscisse du centre du deuxième
# groupe (ex. 8)
ycentre=2 # ordonnée du centre du premier
# groupe (ex. 2)
delta=2.5 # 2.5 ou 1
else:
xcentre=4 # abscisse du centre du troisième
# groupe (ex. 4)
ycentre=5 # ordonnée du centre du troisième
# groupe (ex. 5)
delta=2.8 # 2.8 ou 0.8
for i in range(pts_groupe): # i varie entre 0 inclus
# et pts_groupe exclu
x=xcentre+delta*(2*[Link]()-1)
# x compris entre xcentre-delta et xcentre+delta
y=ycentre+delta*(2*[Link]()-1)
# y compris entre ycentre-delta et ycentre+delta
X[i+k*pts_groupe]=x
Y[i+k*pts_groupe]=y
return X, Y
3.
def distance(ptA, ptB):
# distance euclidienne entre ptA et ptB
# ptA est une liste [xA, yA] désignant l’abscisse
# et l’ordonnée de A
# ptB est une liste [xB, yB] désignant l’abscisse
# et l’ordonnée de B
return ((ptB[0]-ptA[0])**2+(ptB[1]-ptA[1])**2)**(0.5)
4. On choisit aléatoirement K points différents parmi le nuage de points.
Il ne faut pas utiliser la boucle for avec K étapes puisqu’on peut obtenir
deux indices identiques avec la fonction [Link](0, n-1).
254
·
Chapitre 15 Intelligence artificielle et jeu à deux joueurs (Spé)
while flag_stable==False:
flag_stable=True # flag initialisé à True
# il passe à False si le point i
# change de cluster
# on place chaque point dans le cluster k
# le plus proche
for i in range(N): # i varie entre 0 inclus et N exclu
val_min=inf # initialisation de val_min
# à infini
ind_min=0 # indice du cluster correspondant
# au minimum
255
·
Partie 12 Intelligence artificielle et jeux
256
·
Chapitre 15 Intelligence artificielle et jeu à deux joueurs (Spé)
[Link](X,Y,color='black')
[Link](L3[0][0],L3[0][1],color='red')
[Link](L3[1][0],L3[1][1],color='blue')
[Link](L3[2][0],L3[2][1],color='green')
[Link]('x')
[Link]('y')
[Link]('3 clusters')
[Link]() # affiche la figure à l’écran
print(L3) # affichage des coordonnées
# des clusters
3 clusters
8
4
y
–2
0 2 4 6 8 10
x
Les coordonnées des 3 clusters sont : [[7.96, 1.76], [2.62, 0.94], [4.20,
4.87]].
Les centres correspondent bien aux 3 groupes centrés sur [[8, 2], [3, 1],
[4, 5]].
Remarque : En pratique, on utilise cet algorithme pour former des groupes incon-
nus à l’avance mais qu’il faut interpréter ensuite.
7.
def predict(L,pt_search):
# cette fonction retourne l’indice du numéro du cluster
# le plus proche de pt_search
# arguments d’entrée : L = liste des coordonnées des
# centres des clusters, pt_search = liste contenant
# l’abscisse et l’ordonnée de pt_search
# L[i] = liste contenant l’abscisse et l’ordonnée
# du cluster d’indice i
dist_cluster=inf # distance du pt_search à un centre
# du cluster
257
·
Partie 12 Intelligence artificielle et jeux
On considère le jeu de morpion avec une grille 3×3. Les joueurs ajoutent au
fur et à mesure un pion sur la grille en commençant par un pion noir. Les pions
noirs sont représentés par « X » et les pions blancs par « O ». Les cases vides
sont représentées par « . ». Le but est d’aligner 3 pions sur la grille.
On utilise la liste jeu pour représenter le plateau de jeu avec Python. Le pla-
teau de jeu suivant est représenté par la liste : jeu=['.', '.', '.', 'O',
'.', 'X', '.', 'X', '.']. On repère une case par son indice. Par
exemple l’indice 3 correspond à la case avec un pion blanc (« O »).
. . .
O . X
. X .
258
·
Chapitre 15 Intelligence artificielle et jeu à deux joueurs (Spé)
Analyse du problème
L’algorithme min-max est un algorithme très utilisé dans les jeux à somme nulle
et à nombre fini de stratégies. On explore toutes les possibilités. On définit un gain
pour chaque joueur. À chaque coup, les joueurs cherchent à maximiser leur gain
minimum et donc à minimiser le gain maximum de l’adversaire.
Cours
L’intelligence artificielle est « l’ensemble des théories et des techniques mises en œuvre en
vue de réaliser des machines capables de simuler l’intelligence ».
Principe de l’algorithme min-max pour le jeu de morpion
Le morpion est un jeu à somme nulle (les gains d’un joueur sont l’opposé des gains de
l’autre joueur) et avec un nombre fini de stratégies. Le meilleur gain possible pour le joueur
1 est +1 (victoire pour le joueur 1 et défaite pour le joueur 2) et le meilleur gain pour le
joueur 2 est –1 (défaite pour le joueur 1 et victoire pour le joueur 2).
•• Le joueur 1, que l’on appellera MAX, pose les pions noirs.
•• Le joueur 2, que l’on appellera MIN, pose les pions blancs.
Le joueur 2 cherche à minimiser ses gains alors que le joueur 1 cherche à maximiser ses
gains.
L’algorithme min-max est utilisé dans de nombreux jeux : Othello, échecs…
Principe de l’algorithme min-max dans le cas général
On considère le cas général d’un jeu à deux joueurs à somme nulle et avec un nombre fini
de stratégies.
À un moment donné du jeu, c’est au joueur 1 (MAX) de jouer. On suppose qu’il a trois
possibilités. On représente sur l’arbre de jeu ci-dessous les trois possibilités. Ensuite c’est
au joueur 2 (MIN) de jouer. On suppose qu’il a également trois possibilités. On représente
sur le graphe ci-dessous la valeur du gain quand MAX et MIN ont joué.
Chaque nœud correspond à une position de jeu.
MAX joue
MIN joue
6 4 2 1 9 6 8 5 9
260
·
Chapitre 15 Intelligence artificielle et jeu à deux joueurs (Spé)
jeu à somme nulle, le joueur 1 (MAX) cherche à maximiser ses gains alors que le joueur 2
(MIN) cherche à les minimiser à chaque coup.
Le joueur MAX a trois possibilités pour jouer et choisit le coup qui va maximiser ses gains.
Lorsque le joueur MAX a joué, le joueur MIN va jouer en cherchant à minimiser ses gains.
On parcourt en profondeur cet arbre en utilisant la fonction GAIN pour déterminer le meil-
leur coup à jouer pour MAX.
On considère les feuilles : 6, 4 et 2. On remonte dans l’arbre. C’est à MIN de jouer.
MIN joue
6 4 2
Il choisit le coup qui minimise le gain. Il choisit alors le coup avec un gain égal à 2.
MIN joue 2
6 4 2
MIN joue 2 1 5
6 4 2 1 9 6 8 5 9
On remonte dans l’arbre et on se pose la question : Quel coup choisir pour le joueur1
(MAX) ?
MAX joue
2 1 5
Le joueur1 (MAX) cherche à maximiser ses gains. Il va donc choisir le coup avec un gain
égal à 5.
MAX joue 5
2 1 5
261
·
Partie 12 Intelligence artificielle et jeux
MAX joue 5
MIN joue 2 1 5
6 4 2 1 9 6 8 5 9
Plus la profondeur est grande, plus le coup choisi sera de meilleure qualité.
1.
def init(): # début de partie
# la fonction retourne une liste jeu avec
# un plateau vide
# les cases vides sont représentées par '.'
L=9*['.'] # 9 cases avec '.'
return L
def affiche(jeu):
# la fonction affiche le plateau de jeu
# jeu = liste de 9 éléments
print(jeu[0:3]) # 1re ligne du plateau de jeu
print(jeu[3:6]) # 2e ligne du plateau de jeu
print(jeu[6:9]) # 3e ligne du plateau de jeu
def choixjoueur(jeu):
# la fonction retourne le joueur 'O' ou 'X' devant jouer
# pour la liste jeu
som1=0 # initialisation du nombre de cases noires
som2=0 # initialisation du nombre de cases blanches
for i in range(9):
if jeu[i]=='X':
som1=som1+1 # nombre de cases noires
elif jeu[i]=='O':
som2=som2+1 # nombre de cases blanches
if som1==som2: # si autant de pions noirs que de
# pions blancs
return 'X' # c’est à X de jouer
else:
return 'O' # c’est à O de jouer
def listecoups(jeu):
# la fonction retourne la liste L des indices des cases
# vides pour la liste jeu
L=[]
for i in range (9):
if jeu[i]=='.':
[Link](i) # ajoute les cases sans pion
return L
262
·
Chapitre 15 Intelligence artificielle et jeu à deux joueurs (Spé)
def gain(jeu):
# la fonction retourne 1 si les noirs ont gagné,
# -1 si les blancs ont gagné et 0 sinon pour la liste jeu
liste1=['X', 'X', 'X']
liste2=['O', 'O', 'O']
if jeu[0:3]==liste1 or jeu[3:6]==liste1 or jeu[6:9]==liste1\
or [jeu[0], jeu[3], jeu[6]]==liste1\
or [jeu[1], jeu[4], jeu[7]]==liste1\
or [jeu[2], jeu[5], jeu[8]]==liste1\
or [jeu[0], jeu[4], jeu[8]]==liste1\
or [jeu[2], jeu[4], jeu[6]]==liste1:
return 1 # 3 pions noirs alignés
elif jeu[0:3]==liste2 or jeu[3:6]==liste2 or jeu[6:9]==liste2\
or [jeu[0], jeu[3], jeu[6]]==liste2\
or [jeu[1], jeu[4], jeu[7]]==liste2\
or [jeu[2], jeu[5], jeu[8]]==liste2\
or [jeu[0], jeu[4], jeu[8]]==liste2\
or [jeu[2], jeu[4], jeu[6]]==liste2:
return -1 # 3 pions blancs alignés
else:
return 0
2. On ne peut pas écrire : jeu2=jeu pour réaliser une copie de la liste
jeu. Si on modifie un élément de jeu, alors jeu2 aura la même modi-
fication puisque les deux listes jeu et jeu2 font référence à la même
adresse mémoire.
On utilise le module copy (voir exercice 1.4 « Affectation, objet immuable,
copie » dans le chapitre « Prise en main de Python ») pour réaliser une
copie superficielle de jeu.
def jouercoup(jeu, coup):
# la fonction retourne une nouvelle liste jeu2
# en ajoutant un pion à l’indice coup de la liste jeu
import copy # module copy
jeu2=[Link](jeu) # copie superficielle de jeu
# si on modifie jeu2, la liste jeu
# est inchangée
pion=choixjoueur(jeu)
if coup in listecoups(jeu):
jeu2[coup]=pion
return jeu2
3.
def valMax(jeu):
# retourne la valeur du maximum du gain et l’indice
# de la case à jouer pour la liste jeu
L=listecoups(jeu)
if len(L)==0 or gain(jeu)!=0:
# condition d’arrêt de la fonction récursive
# partie finie car plus de coups à jouer
# un des joueurs a gagné avec trois pions alignés
return gain(jeu), -1 # la partie est finie
else:
calculmax=-2 # maximum de tous les coups
# possibles
263
·
Partie 12 Intelligence artificielle et jeux
def valMin(jeu):
# retourne la valeur du minimum du gain et l’indice
# de la case à jouer pour la liste jeu
L=listecoups(jeu)
if len(L)==0 or gain(jeu)!=0:
# condition d’arrêt de la fonction récursive
# partie finie car plus de coups à jouer
# un des joueurs a gagné avec trois pions alignés
return gain(jeu), -1 # la partie est finie
else:
calculmin=2 # minimum de tous les coups
# possibles
ind_coup=-1 # initialisation de l’indice
# du coup à jouer
for coup in L: # parcourt tous les coups
# possibles
jeu2=jouercoup(jeu,coup)
calcul, indice=valMax(jeu2)
if calcul<calculmin:
calculmin=calcul # minimum de tous les coups
# possibles
ind_coup=coup # indice du coup à jouer
return calculmin, ind_coup # minimum du coup à jouer
4.
def jouerminmax(jeu):
# cette fonction affiche les plateaux de jeu à chaque étape
# la liste jeu est modifiée à chaque étape
while gain(jeu)==0 and len(listecoups(jeu))!=0:
# la partie n’est pas terminée et il reste des coups
# à jouer
nomjoueur=choixjoueur(jeu)
if nomjoueur=='X': # les noirs jouent
calcul, ind_coup=valMax(jeu)
# récupère l’indice du coup à jouer pour les noirs
jeu=jouercoup(jeu, ind_coup)
# on passe à l’étape suivante du jeu
else:
calcul, ind_coup=valMin(jeu)
# récupère l’indice du coup à jouer pour les blancs
jeu=jouercoup(jeu, ind_coup)
# passe à l’étape suivante du jeu
264
·
Chapitre 15 Intelligence artificielle et jeu à deux joueurs (Spé)
if gain(jeu)==1:
print("Le joueur X a gagné.")
elif gain(jeu)==-1:
print("Le joueur O a gagné.")
else:
print("Partie nulle")
Le programme principal permettant de visualiser les étapes du jeu de mor-
pion est le suivant :
jeu=init() # début de partie avec cases '.'
jouerminmax(jeu)
5.
def jouercontreIA(jeu):
# cette fonction affiche les plateaux de jeu à chaque étape
# la liste jeu est modifiée à chaque étape
# ordinateur ou IA : pions noirs ; l’humain : pions blancs
while gain(jeu)==0 and len(listecoups(jeu))!=0:
# la partie n’est pas terminée et il reste des coups
# à jouer
nomjoueur=choixjoueur(jeu)
if nomjoueur=='X': # les noirs jouent
calcul, ind_coup=valMax(jeu)
# on récupère l’indice du coup à jouer
jeu=jouercoup(jeu, ind_coup)
# passe à l’étape suivante du jeu
print("Joueur qui pose les pions :", nomjoueur)
affiche(jeu)
else:
ind_coup=int(input("Tapez l’indice de la case : "))
# on récupère l’indice du coup à jouer
jeu=jouercoup(jeu, ind_coup)
# passe à l’étape suivante du jeu
if gain(jeu)==1:
print("L’ordinateur (joueur X) a gagné.")
elif gain(jeu)==-1:
print("Vous avez gagné (joueur O).")
else:
print("Partie nulle")
Le programme principal permettant de jouer contre l’ordinateur est le sui-
vant :
jeu=init() # début de partie avec cases '.'
jouercontreIA(jeu)
265
·
Partie 12 Intelligence artificielle et jeux
Analyse du problème
L’algorithme min-max peut nécessiter un temps de calcul très important pour par-
courir toutes les branches en profondeur. Dans cet exercice, on limite la profondeur
d’étude dans l’arbre de jeu. On peut ainsi déterminer un niveau de difficulté du jeu.
1.
def valMax2(jeu, profondeur):
# retourne la valeur du maximum du gain et l’indice
# de la case à jouer pour la liste jeu
# profondeurmaxi = nombre de coups calculés à l’avance
# par l’algorithme
L=listecoups(jeu)
if len(L)==0 or gain(jeu)!=0 or profondeur ==0:
# condition d’arrêt de la fonction récursive :
# partie finie car plus de coups à jouer,
# ou un des joueurs a gagné avec trois pions alignés,
# ou profondeur nulle (on n’explore pas plus en
# profondeur l’arbre)
return gain(jeu), -1 # la partie est finie
else:
calculmax=-2 # maximum de tous les coups
# possibles
ind_coup=-1 # initialisation de l’indice
# du coup à jouer
for coup in L: # parcourt tous les coups
# possibles
jeu2=jouercoup(jeu, coup)
266
·
Chapitre 15 Intelligence artificielle et jeu à deux joueurs (Spé)
267
·
Partie 12 Intelligence artificielle et jeux
else:
ind_coup=int(input("Tapez l’indice de la case : "))
# récupère l’indice du coup à jouer
jeu=jouercoup(jeu, ind_coup)
# passe à l’étape suivante du jeu
if gain(jeu)==1:
print("L’ordinateur (joueur X) a gagné.")
elif gain(jeu)==-1:
print("Vous avez gagné (joueur O).")
else:
print("Partie nulle")
Le programme principal permettant de jouer contre l’ordinateur en choisis-
sant le niveau de difficulté et la couleur des pions est :
jeu=init() # début de partie avec cases '.'
profondeurmaxi=10 # 2 : niveau débutant, 6 : intermédiaire,
# 10 : expert
jouercontreIA2(jeu, profondeurmaxi)
268
Partie 13
Bases de données
Plan
16. Bases de données (Spé) 271
16.1 : Joueurs de tennis 271
16.2 : Tournois et joueurs de tennis 275
16.3 : Numéros de sécurité sociale 280
16.4 : Imprimantes (Mines Ponts 2015) 284
16.5 : Paludisme (Mines Ponts 2016) 286
Bases de données
(Spé)
16
Exercice 16.1 : Joueurs de tennis
On considère la base de données TENNIS pour gérer les joueurs de tennis.
La table joueurs contient les colonnes :
• id_joueur, de type entier, identifie chaque joueur ;
• nom, de type chaîne de caractères, désigne le nom du joueur ;
• annee, de type entier, désigne l’année de naissance ;
• nationalite, de type chaîne de caractères, désigne la nationalité du joueur.
271
·
Partie 13 Bases de données
6. Écrire une requête qui renvoie l’année de naissance et le nom des joueurs
dont l’année de naissance est strictement supérieure à 1980 et de nationalité
suisse.
7. Écrire une requête qui renvoie le nombre de joueurs ayant la même année de
naissance. Les années sont affichées par ordre croissant.
8. Écrire une requête qui renvoie les identifiants et les noms des 3 premiers
joueurs sans le tout premier de la table.
Analyse du problème
Dans cet exercice, on n’utilise qu’une seule table. Pour lire les données d’une base
de données, on utilise la commande SELECT qui retourne les enregistrements
sélectionnés dans un tableau.
Cours :
La requête de base pour rechercher des données est la commande SELECT :
SELECT *
FROM table
WHERE condition;
SELECT *
FROM table
WHERE condition1 AND condition2;
On peut ajouter DISTINCT après SELECT pour éviter d’afficher des lignes en double.
SELECT DISTINCT colonne
FROM table ;
272
·
Chapitre 16 Bases de données (Spé)
Dans certains cas, on veut éviter d’avoir plusieurs fois la même ligne. On utilise alors la
commande GROUP BY qui permet de regrouper les lignes en une seule. La commande
COUNT(*) compte alors le nombre de lignes concernées.
SELECT *
FROM table
WHERE condition
GROUP BY expression;
On peut utiliser d’autres fonctions statistiques : MAX (maximum), MIN (minimum), SUM
(somme), AVG (moyenne).
AS permet de renommer une colonne ou une table. On utilisera la requête suivante :
SELECT table.colonne1 AS 'nouvellecolonne1', colonne2 AS 'nouvellecolonne2'
FROM table AS t;
On peut omettre AS :
FROM table t
La commande LIMIT 3 permet de sélectionner les trois premiers résultats sans utiliser les
deux premiers de table.
SELECT colonne1, colonne2
FROM table
LIMIT 3 OFFSET 2;
Voir exercice 16.4 « Imprimantes (Mines Ponts 2015) » pour une requête imbriquée.
Remarque : On pourra tester les requêtes SQL en utilisant SQLite Database Brow-
ser ([Link]
1.
SELECT * FROM joueurs;
273
·
Partie 13 Bases de données
Cours :
Les fonctions d’agrégation permettent de réaliser des opérations statistiques.
SELECT COUNT(*)
FROM joueurs;
On obtient : 1993.
4.
SELECT AVG(annee)
FROM joueurs
WHERE nationalite='française';
5.
SELECT nationalite AS 'nationalité', annee AS 'année', nom
FROM joueurs
WHERE annee >=1988;
Remarque :
On peut écrire également :
SELECT annee, nom
FROM joueurs
WHERE (annee >1980 AND nationalite='suisse');
Cours :
La commande GROUP BY évite d’avoir plusieurs fois la même ligne. On regroupe les
lignes d’un même joueur en une seule.
La commande COUNT(*) compte alors le nombre de lignes concernées.
La commande ORDER BY annee permet de trier les lignes par année. Par défaut, le tri
est par ordre croissant (ou ascendant).
Les fonctions d’agrégation SUM(nom_col), AVG(nom_col), MAX(nom_col),
MIN(nom_col), COUNT(nom_col), COUNT(*) calculent respectivement la somme,
la moyenne arithmétique, le maximum, le minimum, le nombre de valeurs non nulles de la
colonne nom_col et le nombre de lignes pour chaque groupe de lignes défini par la clause
GROUP BY. Si la requête ne comporte pas de clause GROUP BY, le calcul est effectué pour
l’ensemble des lignes sélectionnées par la requête.
274
·
Chapitre 16 Bases de données (Spé)
7.
SELECT annee, COUNT(*)
FROM joueurs
GROUP BY annee
ORDER BY annee;
8.
SELECT id_joueur, nom
FROM joueurs
LIMIT 3 OFFSET 1;
275
·
Partie 13 Bases de données
4. Écrire une requête qui renvoie le nombre de victoires pour chaque joueur.
5. Écrire une requête qui renvoie le total des gains pour chaque joueur.
6. Écrire une requête qui renvoie le gain moyen de chaque joueur d’origine serbe.
7. Écrire une requête qui renvoie le gain moyen de chaque tournoi. Les noms
des tournois sont triés par ordre croissant.
8. Écrire une requête qui renvoie la liste des joueurs ayant gagné au moins
deux tournois et nés après 1986. On affichera également le nombre de tournois
gagnés.
9. Écrire une requête qui renvoie le joueur ayant gagné le plus de tournois.
10. Écrire une requête qui renvoie pour chaque joueur le nombre de partici-
pations à une demi-finale d’un tournoi. On renommera les tables joueurs et
tournois respectivement j et t. Les joueurs sont affichés par ordre croissant.
11. Représenter le schéma relationnel de la base de données.
Analyse du problème
On utilise dans cet exercice deux tables : joueurs et tournois. On cherche à
les mettre en relation en utilisant plusieurs clés (joueurs en demi-finale). On pourra
utiliser JOIN… ON… pour réaliser une jointure. La commande HAVING permet de
réaliser des fonctions d’agrégation comme COUNT.
Cours :
Les jointures permettent de mettre en relation plusieurs tables. Dans la plupart des cas, on
impose l’égalité des valeurs d’une colonne d’une table à celles d’une colonne d’une autre
table.
SELECT *
FROM joueurs
JOIN tournois;
Cette requête réalise le produit cartésien des deux tables joueurs et tournois. À
chaque ligne de la table tournois, il accole l’ensemble des lignes de la table joueurs.
Le nombre de lignes affichées vaut 12×6=72. On a réalisé une jointure entre les deux tables.
id_ id_
nom annee nationalite nom annee (1) (2) (3) (4) gain
joueur tournoi
ROLAND-
1 MURRAY 1987 britannique 1 2016 4 1 7 10 2000000
GARROS
ROLAND-
1 MURRAY 1987 britannique 2 2015 10 4 9 1 1800000
GARROS
(1) num_finaliste1 ; (2) num_finaliste2 ; (3) num_joueur3 ; (4) num_joueur4
On peut préciser une condition de jointure avec le mot-clé ON.
SELECT *
FROM joueurs
JOIN tournois ON id_joueur=num_finaliste1;
276
·
Chapitre 16 Bases de données (Spé)
La requête SQL n’affiche pas les 72 lignes mais uniquement celles dont la condition id_
joueur=num_finaliste1 est vérifiée. On a réalisé une jointure interne. On aurait pu
écrire INNER JOIN au lieu de JOIN.
GROUP BY permet de regrouper les lignes en une seule. HAVING fait quasiment la même
chose que WHERE mais permet d’utiliser des fonctions d’agrégation comme COUNT pour
compter le nombre d’éléments.
La requête est alors la suivante :
SELECT *
FROM table1
JOIN table2 ON table1.colonne1=table2.colonne2
WHERE condition
GROUP BY expression HAVING COUNT(*)>=1
ORDER BY colonne1
LIMIT 3 OFFSET 2;
On rencontre parfois des jointures d’une table sur elle-même. On parle d’autojointure (voir
exercice 16.3 « Numéros de sécurité sociale »).
1. Une clé primaire sert à identifier une ligne de manière unique. Chaque
joueur est désigné par un numéro d’identifiant id_joueur. Chaque tour-
noi est désigné par un numéro d’identifiant id_tournoi.
Une clé étrangère permet de lier des relations (ou tables) entre elles. La
clé num_finaliste1 permet d’avoir le numéro d’identifiant du joueur
qui a gagné la finale du tournoi. Les clés num_finaliste1, num_
finaliste2, num_joueur3 et num_joueur4 sont des clés étrangères.
2. Il faut réaliser une jointure entre les tables tournois et joueurs. La
colonne nom peut prêter à confusion puisqu’elle est utilisée dans les deux
tables. Le nom du joueur est alors désigné par [Link].
SELECT [Link]
FROM joueurs
JOIN tournois ON num_finaliste1=id_joueur
WHERE [Link]='ROLAND-GARROS' AND [Link]=2016;
277
·
Partie 13 Bases de données
Cours :
SELECT AVG(gain)
FROM tournois;
On obtient : 1998333.33.
On peut utiliser des fonctions d’agrégation avec la commande GROUP BY.
SELECT nom, AVG(gain)
FROM tournois
GROUP BY nom;
La commande GROUP BY évite d’avoir plusieurs fois la même ligne. Il faut donc regrouper
les lignes d’un même tournoi.
La commande AVG(gain) donne la moyenne des gains pour chaque tournoi.
On obtient :
OPEN AUSTRALIE 2180000.0
ROLAND-GARROS 1816666.67
4.
SELECT [Link], COUNT(*)
FROM joueurs, tournois
WHERE num_finaliste1=id_joueur
GROUP BY [Link];
7.
SELECT nom, AVG([Link])
FROM tournois
GROUP BY nom
ORDER BY nom;
8.
SELECT [Link], COUNT([Link])
FROM joueurs
JOIN tournois ON num_finaliste1=id_joueur
WHERE [Link]>1986
GROUP BY [Link]
HAVING COUNT([Link])>=2;
9.
SELECT [Link], COUNT([Link])
FROM joueurs
JOIN tournois ON num_finaliste1=id_joueur
GROUP BY [Link]
ORDER BY COUNT([Link]) DESC
LIMIT 1;
Cours :
LIMIT 1 permet d’afficher le premier résultat.
10.
SELECT [Link], COUNT([Link])
FROM joueurs AS j
JOIN tournois as t ON num_finaliste1=id_joueur OR num_
finaliste2=id_joueur OR num_joueur3=id_joueur OR num_joueur4=id_
joueur
GROUP BY [Link]
ORDER BY [Link];
11.
joueurs tournois
num_finaliste2 INTEGER
num_joueur3 INTEGER
num_joueur4 INTEGER
gain INTEGER
279
·
Partie 13 Bases de données
280
·
Chapitre 16 Bases de données (Spé)
tab_aquitaine
1. Écrire une requête SQL qui renvoie le nom, le prénom, le numéro de sécu-
rité sociale et l’année de naissance des assurés dont l’année de naissance est
supérieure ou égale à 1980 pour la Bretagne et 1985 pour la Nouvelle-Aqui-
taine. Les noms des assurés sont affichés par ordre croissant.
2. Écrire une requête qui renvoie la liste des couples de Bretagne. Chaque ligne
contiendra le nom et le prénom de l’assuré ainsi que le nom et le prénom de son
mari ou de sa femme.
3. Écrire une requête qui renvoie le nom et le prénom des assurés qui ont les
mêmes noms et prénoms en Bretagne et Nouvelle-Aquitaine.
4. Écrire une requête qui renvoie le nom et le prénom des assurés de Bretagne
sauf ceux qui ont même nom et même prénom en Bretagne et Nouvelle-Aquitaine.
5. Écrire une requête qui renvoie les deux plus grands remboursements des
couples de Nouvelle-Aquitaine. Chaque ligne contiendra le nom, le prénom et
le remboursement.
6. Écrire une requête qui renvoie la moyenne des remboursements par année de
naissance des assurés de Bretagne. Le minimum du remboursement des assurés
pour chaque année de naissance doit être supérieur ou égal à 50. Les années
sont affichées par ordre décroissant.
Analyse du problème
On utilise dans cet exercice des opérateurs ensemblistes : UNION, INTERSECT et
EXCEPT. Ils permettent de combiner dans un résultat unique des lignes provenant
de deux requêtes SELECT.
Cours :
La commande UNION permet d’obtenir la réunion des enregistrements de deux requêtes
SELECT. Pour chaque requête SELECT, on doit avoir le même nombre de colonnes et
le même type pour chaque colonne. Les enregistrements identiques sont affichés une
seule fois.
SELECT nom, prenom FROM tab_bretagne
UNION
SELECT nom, prenom FROM tab_aquitaine
ORDER BY nom;
281
·
Partie 13 Bases de données
On obtient :
BERDYCH Bertrand
BOULEAU Marie
BOULEAU Patrick
CHASSAT Paul
CHEMIN Marie
DJOKOVIC Anne
DUPE Bertrand
DUPONT Thomas
DURAND Alfred
FALQUIER Anne
MAUREL Juliette
1.
SELECT nom, prenom, numsecu, annee FROM tab_bretagne WHERE
annee>=1980
UNION
SELECT nom, prenom, numsecu, annee FROM tab_aquitaine WHERE
annee>=1985
ORDER BY nom;
Cours :
Une autojointure consiste à joindre une table à elle-même. On peut afficher sur une même
ligne une personne ou son mari ou sa femme. On renomme les deux tables pour éviter toute
confusion.
SELECT [Link],[Link], [Link], [Link]
FROM tab_bretagne AS t1
JOIN tab_bretagne AS t2
ON t1.id_personne2=t2.id_personne;
282
·
Chapitre 16 Bases de données (Spé)
On obtient :
Cours :
La commande INTERSECT permet d’obtenir l’intersection de deux requêtes SELECT,
c’est-à-dire les enregistrements communs aux deux requêtes.
3.
SELECT nom, prenom FROM tab_bretagne
INTERSECT
SELECT nom, prenom FROM tab_aquitaine;
Cours :
La commande EXCEPT permet de récupérer les enregistrements de la première requête
SELECT sans inclure les résultats de la deuxième requête SELECT.
4.
SELECT nom, prenom FROM tab_bretagne
EXCEPT
SELECT nom, prenom FROM tab_aquitaine
ORDER BY nom;
On obtient :
BERDYCH Bertrand
DJOKOVIC Anne
DUPONT Thomas
DURAND Alfred
MAUREL Juliette
5.
SELECT [Link], [Link], [Link], [Link], [Link]+[Link]
FROM tab_aquitaine AS t1
JOIN tab_aquitaine AS t2
ON t1.id_personne2=t2.id_personne
ORDER BY [Link]+[Link] DESC
LIMIT 2;
Remarque :
On peut écrire :
SELECT [Link], [Link], [Link], [Link], [Link]+[Link]
FROM tab_aquitaine t1
JOIN tab_aquitaine t2
ON t1.id_personne2=t2.id_personne
ORDER BY [Link]+[Link] DESC
LIMIT 2;
283
·
Partie 13 Bases de données
On obtient :
On obtient :
1985 225.0
1980 50.0
284
·
Chapitre 16 Bases de données (Spé)
Analyse du problème
Cet exercice est extrait de l’épreuve d’informatique du concours Mines Ponts 2015.
On utilise une rubrique imbriquée. Le résultat d’une requête imbriquée en SQL
peut retourner un champ (question 2) ou une colonne (question 3).
1.
SELECT nSerie
FROM testfin
WHERE Imoy>Imin and Imoy<Imax;
2.
SELECT nSerie,Iec,fichierMes
FROM testfin
WHERE Iec<(SELECT AVG(Iec) FROM testfin);
Cours :
La requête imbriquée (SELECT AVG(Iec) FROM testfin) retourne un champ : la
valeur moyenne de la colonne Iec.
3.
SELECT nSerie,fichierMes
FROM testfin
WHERE nSerie NOT IN (SELECT nSerie from production);
285
·
Partie 13 Bases de données
1. Au vu des données présentées dans la table palu, parmi les attributs nom,
iso et annee, quels attributs peuvent servir de clé primaire ? Un couple d’at-
tributs pourrait-il servir de clé primaire ? (on considère qu’une clé primaire
peut posséder plusieurs attributs). Si oui, en préciser un.
2. Écrire une requête SQL qui récupère depuis la table palu toutes les données
de l’année 2010 qui correspondent à des pays où le nombre de décès dus au
paludisme est supérieur ou égal à 1 000.
3. On appelle taux d’incidence d’une épidémie le rapport du nombre de nou-
veaux cas pendant une période donnée sur la taille de la population-cible pen-
dant la même période. Il s’exprime généralement en « nombre de nouveaux
cas pour 100 000 personnes par année ». Il s’agit d’un des critères les plus
importants pour évaluer la fréquence et la vitesse d’apparition d’une épidémie.
Écrire une requête qui détermine le taux d’incidence du paludisme en 2011
pour les différents pays de la table palu.
286
·
Chapitre 16 Bases de données (Spé)
Analyse du problème
Cet exercice est extrait de l’épreuve d’informatique du concours Mines Ponts 2016.
On utilise une rubrique imbriquée. Le résultat d’une requête imbriquée en SQL ne
fournit qu’un champ dans cet exercice (maximum du nombre de nouveaux cas de
paludisme en 2010).
Cours :
La sélection σ annee=2010 ( palu ) s’applique à la table palu et permet d’extraire de celle-ci les
éléments qui satisfont un critère de sélection (annee=2010 ) .
La projection π nom,deces ( R ') s’applique à une relation R’ et ne garde que les colonnes nom,
deces. Contrairement à la sélection, la projection ne supprime pas des lignes mais des
colonnes.
1. Une clé primaire sert à identifier une ligne de manière unique. Aucune
colonne dans la table palu n’est une clé primaire.
Le couple (iso, annee) est une clé primaire.
2.
SELECT *
FROM palu
WHERE annee=2010
AND deces>=1000;
287
·
Partie 13 Bases de données
3.
SELECT nom, cas/pop*100000 AS 'taux incidence'
FROM palu
JOIN demographie ON iso=pays AND periode=annee
WHERE annee=2011;
4.
SELECT nom, cas
FROM palu
WHERE annee=2010;
6.
SELECT nom, cas
FROM palu
WHERE annee=2010 AND cas =(SELECT max(cas) FROM palu WHERE
annee=2010);
288
Partie 14
Algorithmique
numérique
Plan
17. Algorithmique numérique (Spé)(uniquement TSI et TPC) 291
17.1 : Équation différentielle du premier ordre 291
17.2 : Équation différentielle du deuxième ordre 295
17.3 : Résolution d’un système linéaire par la méthode de Gauss 298
17.4 : Interpolation polynomiale de Lagrange 307
17.5 : Interpolation par morceaux 310
Algorithmique
numérique (Spé)
17
(uniquement TSI et
TPC)
dy E − y
On considère l’équation différentielle : = avec E et τ des constantes.
dt τ
La réponse y ( t ) recherchée sur l’intervalle t0 , tmax sera obtenue par la méthode
d’Euler. Le pas de calcul, noté h, sera choisi constant. L’intervalle de temps dis-
crétisé est représenté par la liste T = t0 , t1 ,..., tN −1 = tmax . Pour chaque instant
ti, une valeur approchée yi de la solution y ( ti ) de l’équation différentielle est
recherchée. L’ensemble des yi est représenté par la liste Y.
1. Écrire une relation de récurrence permettant de calculer yi +1 en fonction de
yi , E , h et τ.
2. Écrire une fonction Euler(y0, t0, h, N, E, tau) qui admet comme
arguments y0= y ( 0 ), t0 le temps initial de calcul, h le pas de calcul, N le
nombre de points, E une constante et tau une constante. Cette fonction ren-
verra les listes T et Y.
3. Écrire le programme principal permettant d’afficher graphiquement y en
fonction du temps t avec les conditions suivantes : t0 = 0, y ( 0 ) = 0, E = 10,
h = 0,2 ms, τ = 30 ms et N = 1 000. Le graphique doit avoir les caractéristiques
suivantes :
•• affichage de « t » pour l’axe des abscisses,
•• affichage de « y » pour l’axe des ordonnées,
•• affichage du titre : « Méthode d’Euler ».
4. Commenter la courbe obtenue avec h = 59 ms, les autres conditions précé-
dentes demeurant inchangées.
291
·
Partie 14 Algorithmique numérique
Méthode d'Euler
20.0
17.5
15.0
12.5
y
10.0
7.5
5.0
2.5
0.0
0 10 20 30 40 50 60
t
Analyse du problème
On utilise la méthode d’Euler pour résoudre numériquement une équation différen-
tielle du premier ordre. On étudie l’influence du pas sur la qualité de la solution.
Cours :
du
On cherche à résoudre numériquement l’équation différentielle : = F (u (t ) , t ).
dt t
La fonction u(t) est une fonction continue du temps (qui est également continu). On réalise
la discrétisation du signal en récupérant les valeurs de la tension u à intervalles de temps
réguliers h. On appelle h le pas de calcul et N le nombre d’échantillons. On obtient deux
suites de nombres :
•• {ti = ih , i variant de 0 à N − 1},
•• {ui = u (t = ih ), i variant de 0 à N − 1}.
T [i ] = ti
Avec Python, on définit deux listes T et U telles que .
U [i ] = ui
On a alors :
•• {T [i ] = ti = ih , i variant de 0 à N − 1},
•• {U [i ] = ui = u (t = ih ), i variant de 0 à N − 1}.
On considère un point d’abscisse ti. On applique la formule de Taylor au premier ordre au
voisinage de ti :
du
u (ti+1 ) = u (ti ) + (ti+1 − ti ) + ...
dt ti
292
·
Chapitre 17 Algorithmique numérique (Spé) (uniquement TSI et TPC)
du
u (ti+1 ) = u (ti ) + h + ...
dt ti
du
≈
dt ti ( ) = u (t
∆u
∆t ti
i+1 ) − u (ti ) = ui+1 − ui
h h
=
U [ i + 1] − U [ i ]
h
La méthode d’Euler est une méthode du premier ordre.
du
•• La méthode d’Euler explicite consiste à évaluer en utilisant la valeur de la déri-
dt ti
du
vée à l’ancienne position, c’est-à-dire à l’instant ti : = F (ui , ti ). On a un schéma
dt ti
explicite puisqu’on calcule chaque point en fonction du point précédent. La relation de
u −u
récurrence s’écrit : i+1 i = F (ui , ti ) .
h du
•• La méthode d’Euler implicite consiste à évaluer en utilisant la valeur de la déri-
dt ti
du
vée à la nouvelle position, c’est-à-dire à l’instant ti+1 : = F (ui+1 , ti+1 ). La relation
u −u dt ti
de récurrence s’écrit : i+1 i = F (ui , ti ) .
h
Sauf indication contraire, on utilisera la méthode d’Euler explicite dans les exercices.
dy y − yi E − yi
1. La méthode d’Euler explicite permet d’écrire : ≈ i +1 = .
dt ti h τ
E − yi
On en déduit la relation de récurrence : yi +1 = yi + h .
τ
Remarque : Sans indication contraire de l’énoncé, on utilise la méthode d’Euler
explicite.
2.
def Euler(y0, t0, h, N, E, tau):
T=[t0] # 1er élément de la liste T
Y=[y0] # 1er élément de la liste Y
for i in range(N-1): # i varie entre 0 inclus et N-1 exclu
[Link](T[i]+h) # ajout d’un élément à la liste T
[Link](Y[i]+h*(E-Y[i])/tau) # ajout d’un élément
# à la liste Y
return T, Y
3.
import [Link] as plt
# module [Link] renommé plt
293
·
Partie 14 Algorithmique numérique
y0=0
E=10
tau=30e-3
T, Y=Euler(y0, t0, h, N, E, tau)
Méthode d'Euler
10
6
y
0
0.000 0.025 0.050 0.075 0.100 0.125 0.150 0.175 0.200
t
dy
Remarque : Si on considère l’équation différentielle : = λ y. On peut écrire que
dt
yi +1 = yi + hλ yi = yi (1 + hλ ). Pour que la méthode soit stable, il faut que 1 + hλ < 1.
On peut en déduire un critère de stabilité sur le pas.
294
·
Chapitre 17 Algorithmique numérique (Spé) (uniquement TSI et TPC)
Analyse du problème
On cherche à résoudre numériquement une équation différentielle du deuxième
ordre, on se ramène à deux équations différentielles du premier ordre. On utilise la
méthode d’Euler explicite étudiée dans l’exercice précédent.
295
·
Partie 14 Algorithmique numérique
du
1. On pose g (t ) = . L’équation différentielle (1) s’écrit alors sous la
dt
dg dg
forme : + bg + cu = 0, soit = −cu − bg . On transforme alors l’équation
dt dt
différentielle (1) en un système de deux équations différentielles du pre-
du
g (t )
dt
mier ordre : = .
dg −cu (t ) − bg (t )
dt
dY u (t )
On a donc = F (Y (t ) , t ) avec Y (t ) = et F (Y (t ) , t ) =
dt g (t )
g (t )
.
−cu (t ) − bg (t )
gi
À l’instant ti, on a : F (Yi (ti ) , ti ) = . Il faut donc retourner la
liste : [ gi , −cui − bgi ]. −cui − bgi
dY
2. Pour évaluer numériquement à l’instant ti, on utilise la méthode
d’Euler explicite : dt t i
dY Y (ti +1 ) − Y (ti )
≈
dt ti h
Y (ti +1 ) − Y (ti )
On a alors : = F (Y (ti ) , ti ). La relation de récurrence s’écrit
donc : h
ui +1 = ui + hgi
Yi +1 = Yi + h (F (Yi , ti )), soit
gi +1 = gi + h (−cui − bgi )
Remarques :
( )
•• La relation de récurrence s’écrit : Yi +1 = Yi + h F (Yi , ti ) . On a un schéma explicite
puisqu’on calcule le point suivant en fonction du point précédent.
Y −Y
(
•• Dans un schéma implicite, on a Yi +1 = Yi + h F (Yi +1 , ti +1 ) , soit i+1 i = ) h
F (Yi+1 , ti+1 ). Dans ce cas, la nouvelle valeur Yi +1 est calculée en utilisant la valeur
de la dérivée à la nouvelle position.
g (t ) u (t )
3. On a vu que F (Y (t ) , t ) = et Y (t ) = .
−cu (t ) − bg (t ) g (t )
gi
À l’instant ti, on a : F (Yi (ti ) , ti ) = . Il faut donc retourner la
liste : [ gi , −cui − bgi ]. −cui − bgi
296
·
Chapitre 17 Algorithmique numérique (Spé) (uniquement TSI et TPC)
[Link]()
[Link](T, U) # représentation graphique
# de U en fonction de T
[Link]('t')
[Link]('u(t)')
[Link]("Oscillateur harmonique amorti")
[Link]()
297
·
Partie 14 Algorithmique numérique
On obtient le graphe :
1.5
1.0
0.5
u (t)
0.0
–0.5
–1.0
–1.5
0 2 4 6 8 10
t
298
·
Chapitre 17 Algorithmique numérique (Spé) (uniquement TSI et TPC)
Étape 1 :
Le calculateur doit déterminer les indices i et j tels que P [ j ] ≤ Pcol ≤ P [ j +1]
et OMEGA [i ] ≤ OMEGAmot ≤ OMEGA [i + 1].
1. Écrire une fonction indice(A, val) qui prend pour arguments une liste
notée A et un réel noté val. La liste A est triée par ordre croissant. La fonction
doit retourner un entier id tel que : A [id ] ≤ val ≤ A [id + 1] . On supposera que
id existe toujours.
Le calculateur doit ensuite lire dans la liste de listes T les durées d’injection
correspondant aux indices i et j précédemment déterminés.
299
·
Partie 14 Algorithmique numérique
[T [i + 1, j ] , T [i + 1, j + 1] , P [ j + 1] , OMEGA [i + 1]]
3. Écrire la suite d’instructions qui, à partir des variables OMEGAmot, Pcol,
des listes P et OMEGA et de la liste de listes T, permet de déterminer la liste de
listes ST telle que définie à la question précédente.
Étape 2 :
Une fois les quatre valeurs de durée d’injection déterminées, il est nécessaire de
calculer une durée d’injection t à partir d’une interpolation bilinéaire. L’inter-
polation bilinéaire de la fonction de deux variables t ( x , y ) s’écrit comme suit :
t ( x , y ) = b0 + b1 x + b2 y + b3 xy ; x ∈[ 0,1] et y ∈[ 0,1]
PQ = R et Q = P−1 R
P est une matrice carrée de dimension n×n ; Q et R sont des matrices colonnes
de dimension n.
On envisage dans un premier temps l’utilisation de la méthode de Gauss
avec recherche du pivot partiel pour résoudre le système linéaire et obtenir la
matrice Q.
4. Écrire l’algorithme du pivot de Gauss permettant d’obtenir la matrice Q. On
admettra que les termes diagonaux sont tous non nuls.
5. Quelle est la complexité du pivot de Gauss en fonction de la dimension de la
matrice ? Justifier votre réponse.
Pcol − P [ j ] OMEGAmot − OMEGA [ i ]
On posera par la suite : x = et y = .
P [ j + 1] − P [ j ] OMEGA [ i + 1] − OMEGA [ i ]
On connaît les valeurs de t ( x , y ) pour quatre couples de valeurs ( x , y ) par lec-
ture de la cartographie :
t ( x = 0, y = 0 ) = ST [ 0, 0 ] t ( x = 1, y = 0 ) = ST [ 0,1]
t ( x = 0, y = 1) = ST [1, 0 ] t ( x = 1, y = 1) = ST [1,1]
300
·
Chapitre 17 Algorithmique numérique (Spé) (uniquement TSI et TPC)
1 0 0 0 b0 ST [ 0, 0 ]
b ST [ 0,1]
1 1 0 0 1=
1 0 1 0 b2 ST [1, 0 ]
1 1 1 1 b3 ST [1,1]
b0 = ST [ 0, 0 ]
b1 = ST [ 0,1] − ST [ 0, 0 ]
b2 = ST [1, 0 ] − ST [ 0, 0 ]
b3 = ST [1,1] − ST [ 0,1] − ST [1, 0 ] + ST [ 0, 0 ]
8. Comparer la complexité de cet algorithme à celui présenté à la question 5.
9. Écrire une fonction interpol(ST, Pcol, OMEGAmot) qui retourne
une valeur de la durée d’injection obtenue par une interpolation bilinéaire des
éléments de la table.
Analyse du problème
On utilise la méthode de Gauss avec recherche partielle du pivot pour résoudre un
système linéaire d’ordre n.
Cours :
Un système linéaire est de Cramer d’ordre n si c’est un système de n équations linéaires à
n inconnues et s’il admet une solution unique.
2 4 2
On cherche à résoudre le système PQ = R. On prend par exemple : P = 1 4 2 ;
q0 1 2 9 3
Q = q1 et R = 1 .
q 1
2 2 4 2 q0 2q0 + 4 q1 + 2q2 1
Le système s’écrit alors : 1 4 2 q1 = q0 + 4 q1 + 2q2 = 1 .
2 9 3 q
2 2q0 + 9q1 + 3q2 1
2 4 2 1
Avant de décrire l’algorithme, on pose P ' = P = 1 4 2 et R ' = R = 1 .
2 9 3 1
301
·
Partie 14 Algorithmique numérique
Étape p = 0 :
2 4 2
P' = 1 4 2 . Le pivot est P'i =0, p=0 = 2 avec i ≥ p. Les étapes 1 et 2 sont inutiles. On
2 9 3 1 2 1 0,5
divise la ligne 0 par le pivot. On obtient : P' = 1 4 2 et R' = 1 .
2 9 3 1
Combinaison linéaire i ≠ p :
•• i = 1 : valeur = P'i =1, p=0 = 1. D’où : ligne (i = 1)← ligne (i = 1) − valeur × ligne ( p = 0 ).
1 2 1 0,5
On a alors : P' = 0 2 1 et R' = 0,5 .
2 9 3 1
•• i = 2 : valeur = P'i =2, p=0 = 2. D’où : ligne (i = 1)← ligne (i = 2) − valeur × ligne ( p = 0 ). On
1 2 1 0,5
a alors : P' = 0 2 1 et R' = 0,5 .
0 5 1 0
Étape p = 1 :
1 2 1
P' = 0 2 1 .
0 5 1
Le pivot est P'i =2, p=1 = 5 avec i ≥ p. On permute les lignes i et p. On obtient alors :
1 2 1 0,5
P' = 0 5 1 et R' = 0 .
0,5
0 2 1 1 2 1
On divise la ligne p = 1 par le pivot. On obtient alors P' p=1, p=1= 1 et P' = 0 1 1 / 5
0,5 0 2 1
et R' = 0 .
0,5
302
·
Chapitre 17 Algorithmique numérique (Spé) (uniquement TSI et TPC)
Combinaison linéaire i ≠ p :
•• i = 0 : valeur = P'i =0, p=1 = 2. D’où : ligne (i = 0 ) ← ligne (i = 0 ) − valeur × ligne ( p = 1).
1 0 3/5 0,5
On a alors : P' = 0 1 1 / 5 et R' = 0 .
0 2 1 0,5
•• i = 2 : valeur = P'i =2, p=1 = 2. D’où : ligne (i = 2) ← ligne (i = 2) − valeur × ligne ( p = 1).
1 0 3/5 0,5
On a alors : P' = 0 1 1 / 5 et R' = 0 .
0 0 3/5 0,5
Étape p = 2 :
1 0 3/5 3
P' = 0 1 1 / 5 . Le pivot est P'i =2, p=2 = avec i ≥ p = 2 . Les étapes 1 et 2 sont inu-
5
1 0 3/5 0,5
0 0 3/5
tiles. On divise la ligne p = 2 par le pivot. On obtient : P' = 0 1 1 / 5 et R' = 0 .
0 0 1 5 / 6
Combinaison linéaire i ≠ p :
3
•• i = 0 : valeur = P'i =0, p=2 = . D’où : ligne (i = 0 ) ← ligne (i = 0 ) − valeur × ligne ( p = 2).
5
1 3 5
1 0 0 2 − 5 × 6 0
On a alors : P' = 0 1 1 / 5 et R' = 0 = 0 .
0 0 1
5 / 6 5 / 6
1
•• i = 1 : valeur = P'i =1, p=2 = . D’où : ligne (i = 1) ← ligne (i = 1) − valeur × ligne ( p = 2).
5
1 0 0 0
On a alors : P' = 0 1 0 et R' = −1 / 6 .
0 0 1 5 / 6
1 0 0 0 0
On a alors Q = P' R' = 0 1 0 −1 / 6 = −1 / 6 .
0 0 1 5 / 6 5 / 6
0
On peut vérifier facilement que Q = −1 / 6 est solution du système de départ :
5 / 6
2 4 2 1
PQ = 1 4 2 Q = 1
2 9 3 1
303
·
Partie 14 Algorithmique numérique
1.
def indice(A, val):
id=0
while A[id] > val or val > =A[id+1]:
id+=1
return id
# suppose que id existe toujours
# sinon la boucle pourrait ne pas se terminer
2.
def extraire(T, P, OMEGA, i, j):
ST=[] # création d’une liste vide
[Link]([T[i][j],T[i][j+1],P[j],OMEGA[i]])
[Link]([T[i+1][j],T[i+1][j+1],P[j+1],OMEGA[i+1]])
return ST
3.
j=indice(P, Pcol)
i=indice(OMEGA, OMEGAmot)
ST2=extraire2(T2, P, OMEGA, i, j) # liste de listes
304
·
Chapitre 17 Algorithmique numérique (Spé) (uniquement TSI et TPC)
305
·
Partie 14 Algorithmique numérique
b0 b0 t (0,0) ST [0,0]
1 0 0 0
b b + b t (1,0) ST [0,1]
1 1 0 0
On a bien
1 0 1
= = = .
1 0 1 0 b2 b0 + b2 t (0,1) ST [1,0]
1 1 1 1 b3 b0 + b1 + b2 + b3 t (1,1) ST [1,1]
7. On résout directement ce système :
b0 = ST [0,0] ; b1 = ST [0,1] − b0 = ST [0,1] − ST [0,0] ; b2 = ST [1,0] − b0 =
ST [1,0] − ST [0,0] .
b3 = ST [1,1] − b0 − b1 − b2 = ST [1,1] − ST [0,0] − ( ST [0,1] − ST [0,0]) −
( ST [1,0] − ST [0,0])
Après simplification, on a : b3 = ST [1,1] + ST [0,0] − ST [0,1] − ST [1,0].
On obtient finalement :
b0 = ST [0,0]
b1 = ST [0,1] − ST [0,0]
b2 = ST [1,0] − ST [0,0]
b3 = ST [1,1] − ST [0,1] − ST [1,0] + ST [0,0]
306
·
Chapitre 17 Algorithmique numérique (Spé) (uniquement TSI et TPC)
Analyse du problème
On détermine les n+1 composantes du polynôme d’interpolation qui passe par les
n+1 points imposés. Le phénomène de Runge apparaît lorsque n est trop grand.
1.
def lagrange(i, x, n):
# i entier
# x réel, n entier
Li=1
307
·
Partie 14 Algorithmique numérique
2.
def poly(x, n):
# x réel, n entier
som=0
for i in range(n+1): # i varie entre 0 inclus et n+1 exclu
som+=ys[i]*lagrange(i, x, n)
return som
3.
import math as m
# module math renommé m
import [Link] as plt
# module [Link] renommé plt
def f(x):
return 1/(1+x**2)
a=-5
b=5
# interpolation d’ordre n
# le nombre de points vaut n+1
n=4
h=(b-a)/n
xs=[a+i*h for i in range(n+1)] # liste des abscisses
ys=[f(xs[i]) for i in range(n+1)] # liste des ordonnées
# représentation graphique
[Link]() # nouvelle fenêtre graphique
[Link](X, Y) # graphe Y en fonction de X
[Link](X, YL) # graphe YL en fonction de X
[Link]() # affiche le graphique
308
·
Chapitre 17 Algorithmique numérique (Spé) (uniquement TSI et TPC)
Interpolation d'ordre 4
1.0
0.8
0.6
0.4
y
0.2
0.0
−0.2
−0.4
−4 −2 0 2 4
x
Interpolation d'ordre 10
2.0
1.5
1.0
y
0.5
0.0
−4 −2 0 2 4
x
Interpolation d'ordre 14
4
y
–1
–4 –2 0 2 4
x
309
·
Partie 14 Algorithmique numérique
p1h ( x ) = p1,i ( x ) , ∀x ∈ Ii
Le polynôme p1,i est un polynôme de degré 1, pour tout i ∈ 0, n − 1.
Les abscisses xi et les ordonnées fi sont stockées respectivement dans les listes
xs et ys.
1. Donner l’expression de p1,i sur chaque intervalle Ii, pour i ∈ 0, n − 1.
2. Écrire une fonction interpol qui admet comme argument x et retourne
p1h ( x ) , x ∈ [ a, b ].
Écrire le programme principal permettant de représenter graphiquement la fonc-
n
tion f, le polynôme d’interpolation de degré n = 6 ( p ( x ) = ∑ f L ( x ),
i i x∈
i =0
n
x − xj
avec Li ( x ) = ∏ x − x , i ∈ 0, n ) et une interpolation linéaire par morceaux
i j
j =0
j ≠i
Analyse du problème
Pour résoudre le problème d’oscillations qui apparaît lorsque n est trop grand, on
utilise une interpolation par morceaux.
1. On considère une loi affine entre deux points successifs. Soit i ∈ 0, n − 1 ,
∀x ∈ [ xi , xi +1 ] : y = yi + ( x − xi ) yi +1 − yi . Pour l’intervalle Ii , on en déduit
xi +1 − xi
y − yi
la fonction polynôme définie par p1,i ( x ) = yi + ( x − xi ) i +1 .
xi +1 − xi
310
·
Chapitre 17 Algorithmique numérique (Spé) (uniquement TSI et TPC)
b−a
2. On pose h = et xi = a + ih, i ∈ 0, n .
n
Soit x ∈ [a, b]. On cherche un entier i tel que x appartienne au sous-
intervalle Ii = [ xi , xi +1 ] , i ∈ 0, n − 1.
x − x0
Avec Python, on obtient i en calculant int .
h
3h x − x0 3
•• Si x = x 0 + , alors int = int = 1, x est bien dans l’intervalle
2 h 2
I1 = [ x1 , x2 ].
x − x0
•• Si x = x n , alors int n = n . Dans ce cas, la fonction retourne direc-
h
tement yn car l’intervalle [ x n , x n+1 ] n’est pas défini.
import math as m
# module math renommé m
import [Link] as plt
# module [Link] renommé plt
def f(x):
return 1/(1+x**2)
a=-5
b=5
# interpolation d’ordre n
# le nombre de points vaut n+1
n=6
h=(b-a)/n
xs=[a+i*h for i in range(n+1)] # liste des abscisses
ys=[f(xs[i]) for i in range(n+1)] # liste des ordonnées
311
·
Partie 14 Algorithmique numérique
if x!=xs[n]:
# x est dans l’intervalle Ii=[xi, xi+1]
return ys[i]+(x-xs[i])*(ys[i+1]-ys[i])/(xs[i+1]-xs[i])
else:
# l’intervalle [xn, xn+1] n’est pas défini
return ys[n]
# représentation graphique
[Link]() # nouvelle fenêtre graphique
[Link](X, Y) # graphe Y en fonction de X
[Link](X, YL) # graphe YL en fonction de X
[Link](X, Ym) # graphe Ym en fonction de X
[Link]() # affiche le graphique
Interpolation d'ordre 6
1.0
0.8
0.6
y
0.4
0.2
0.0
–4 –2 0 2 4
x
312
Index
A D
algorithme A* 195 degré 150
appel récursif 39, 57, 70, 177 dépaquetage d’un tuple 14
arbre des appels 80, 116, 178 dépassement de la taille de la pile 60
arc 151 deque 142, 161, 176
arête 150, 180 dichotomie 52
autojointure (SQL) 282 dictionnaire 131, 167, 176
dijkstra 187
B distance
bibliothèque de Manhattan 200
collections 142, 162, 177 euclidienne 195
turtle 75 DISTINCT (SQL) 272, 273
boucle diviser pour régner 59, 80, 116
for 127, 166
while 168, 194, 204 F
boucles imbriquées 48
factorielle 57
break 127
FIFO 140, 152, 158
file 140, 157
C
filtrage des agrégats avec HAVING (SQL)
chaîne de caractères 47, 239, 271 277, 279
chemin 151, 185 fonction
clé itérative 57, 87, 119
étrangère 277 récursive 57, 85, 119
primaire 277 fonctions d’agrégation : AVG, COUNT,
primaire (SQL) 287 MAX, MIN, SUM (SQL) 273, 278
complexité 33, 41, 52, 54, 62
fractales 75
condition d’arrêt 39, 57, 80
copie
G
profonde 18
superficielle 18, 144 glouton 85, 88, 201
correction 32, 57, 59, 61 graphe
partielle 32, 59 connexe 150, 162, 180
totale 32, 59 non orienté 150, 161, 167, 171
cycle 150, 160, 162, 180 orienté 151, 185
313
Index
I R
int 4 récursivité 57, 80, 178
invariant de boucle 32, 59 regrouper des lignes avec GROUP BY
(SQL) 274, 277
L requête
lecture de fichiers 94 imbriquée (SQL) 285
LIFO 136, 152, 168 SELECT (SQL) 272, 278, 282
LIMIT (SQL) 273 return 7, 13, 31, 39
liste
d’adjacence 152, 156 S
de listes 87, 99, 223 segment de Koch 75
par compréhension 23 slicing 22, 120
M T
matrice d’adjacence 151, 164, 197 terminaison 31, 36, 57, 61
mise en relation de deux tables JOIN
tri
(SQL) 276
par comptage 122
multiplicité (SQL) 280
par insertion 109, 121
par partition-fusion 118
O
par sélection 112
opérateurs ensemblistes UNION, rapide 115
INTERSECT, EXCEPT (SQL) 281 tri (SQL) 274, 278
opérations élémentaires 41, 62, 114
type
bool 4
P
deque 6
parcours dict 132
en largeur 157, 164, 176 float 4
en profondeur 167, 171, 178 int 4
passage list 5
par référence 116, 177
str 5
par valeur 177
tuple 5, 14, 102, 131
pile 59, 136
[Link] 25, 95, 240
[Link] 25, 124 V
[Link] 25, 124 variant de boucle 31, 38, 58