Table des matières - Mathématiques et Informatique en PCSI …pcsidescartes.fr/pdf/ipt2Courant.pdf · · 2018-02-06chemin=calcule_chemin(front) 104 represente(carte,chemin) Une

Table des matières

Résolution du problème du labyrinthe 3

Problème du cavalier d’Euler 9

1 Structure de piles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

I Généralités 15

II Implémentation avec des listes 16

III Exemple d’utilisation des piles 17III.1 Parenthésage d’une expression . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

III.2 Branchement dans les L-system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

Exercices 21

2 Récursivité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

I Fonctions récursives 25

II Étude théorique d’une fonction récursive 27II.1 Terminaison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

II.2 Correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

II.3 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

II.4 Amélioration d’un algorithme récursif . . . . . . . . . . . . . . . . . . . . . . . . 29

III Exemple : algorithme itératif du triangle de Pascal 30

IV Exemple Exponentiation rapide 32

Exercices 33

3 Algorithmes de tris . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

I Algorithme de tri par sélection 38

II Tri par insertion 39

III Tri fusion 42

IV Tri rapide 46

V Comparatif des algorithmes de tris 50

VI Recherche de la médiane 51

Exercices 55

Simulation de variables aléatoires et de tirages 61

4 Révision sur l’ingénierie numérique . . . . . . . . . . . . . . . . . . . . 71

I Résolution de f (x) = 0 71I.1 Méthode de dichotomie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71I.2 Algorithme de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

II Résolution numérique d’équations différentielles 75II.1 Principes généraux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

III Résolution de systèmes linéaires 78III.1 Méthode de remontée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78III.2 Pivot de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80III.3 Variantes de la réduction de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . 82

Algorithme de remplissage Flood Fill 87

Simulation de propagation de maladie 95

Simulation numérique des oscillations d’un pendule 99

Modèle proie-prédateur 105

5 Révisions sur les bases de données . . . . . . . . . . . . . . . . . . . 109

I Vocabulaire des bases de données 109

II Opérateurs usuels sur les ensembles dans un contexte de basede données 111

III Opérateurs de l’algèbre relationnelle 111

IV Agrégations et fonctions d’agrégation 114

V Séquence complète en SQL 115

Exemples de requêtes MySQL 117

Résolution du problème du labyrinthePelletier Sylvain PC, Lycée Descartes

Dans ce projet, il s’agit de faire calculer par Python le plus court chemin permettant de traverser un labyrinthe.Le labyrinthe est représenté par un array carte de taille n par m, dont les cases valent MUR (i.e. 1) si un mur est présent

et VIDE (i.e. 0).Le problème est de trouver un chemin reliant la case en haut à gauche à celle en bas à droite.La technique que l’on va employer est appelée propagation de front.On commence par créer un tableau qui contiendra le temps nécessaire pour atteindre chaque case, en considérant que l’on

avance d’une case par unité de temps. Ce tableau est appelé carte de distance (contenu dans la variable carte_front).Une fois que ce tableau sera suffisamment rempli pour que la destination soit atteinte, on reconstruira le chemin sous la

forme d’une liste listeD contenant SUD (1), NORD (2), OUEST (3) et EST (4). Cette liste est une suite d’instructions qui donnela suite de directions à prendre pour rejoindre la sortie à partir de l’entrée.

O Rappel pour vérifier le bon déroulement de l’algorithme :Tout au long du projet, il faut utiliser la fonction print pour vérifier que l’algorithme fait bien ce qu’on lui demande. On

peut ajouter un arrêt en utilisant la fonction input :

input("--stop --")

N’oubliez pas d’enlever ces lignes de codes avant de passer à des donnée en taille réelle.Vous disposez• d’un script à compléter• d’un module contenant :

– des données simulées (fonction loadTest)– des données taille réelle (fonction loadImage),– les fonctions qui permettent d’afficher le labyrinthe et le trajet trouvé.

On commencera bien sûr par les données en petite taille, avant de tester sur les vraies données.

O Propagation du frontPour propager le front, on procède comme pour la propagation du feu dans une forêt :• on initialise un array carte_front de même taille que le labyrinthe selon :

– la case de départ à la valeur 0, puisqu’elle peut être atteinte en un temps égal à 0,– toutes les autres ont la valeur NON_ATTEINTE (on prendra par exemple cette valeur égale à -1).

• on initialise une liste listeFront contenant la liste des cases au temps courant.• Puis, on propage à partir du temps t = 0

– À chaque temps t, on balaie toutes les cases de listeFront atteintes au temps t.– Pour chacune de ces cases, on atteint les 4 cases voisines au temps t+1, sauf si celles-ci ont déjà été atteintes, ou

si il s’agit de murs.• Ceci jusqu’à ce que la case d’arrivée soit atteinte (il est inutile de propager le front au-delà).On écrira deux fonctions :• une fonction propage(carte,listeFront,carte_front,t) qui propage le front du temps t au temps t +1,• une fonction propage_front(carte) qui étant donné un labyrinthe, calcule la carte des distances.NB : Attention aux cases situées sur le bord.On testera bien avant de passer à la deuxième partie.

O Reconstruction du chemin à partir de la carte de distancePour reconstruire le chemin à partir de la carte de distance, on parcourt le chemin à l’envers :• on part d’un chemin listeD vide,• on place mentalement un pion sur la case en bas à droite, celle-ci ayant été atteinte au temps t, valeur qui est lue dans

la carte des distances.• Il y a (au moins) une case voisine qui a été atteinte au temps t-1, d’où le dernier déplacement.• On déplace alors le pion sur cette nouvelle case, et on note ce dernier déplacement dans la liste listeD.• Puis de même, la case occupée par le pion a été atteinte au temps t-1, donc cette case a au moins une voisine qui a été

atteinte au temps t-2. On déplace alors de nouveau le pion sur cette nouvelle case, et on note ce déplacement dans laliste listeD.

3

On continue ainsi :• étant donné une position (i,j) du pion atteinte au temps t,• on cherche la position voisine atteinte au temps t−1,• on déplace alors le pion sur cette position (en changeant la valeur de i et de j),• on note le déplacement effectué dans la liste listeD,• on remplace t par t−1.

Ceci, jusqu’à ce qu’on ait atteint le t=0, qui doit être la case de départ.Écrire une fonction calcule_chemin(carte_front), qui étant donné une carte, calcule le chemin.Rappel :• le chemin est rentré à l’envers : si on déplace le pion vers le nord, c’est la direction SUD qui est enregistrée, puisque

cela indique que le chemin doit aller vers le sud, etc.• pour enregistrer les différentes directions, on concatène ces directions à la liste chemin. Attention, ici c’est une

concaténation par le dessus . On utilisera donc : listeD = [SUD] + listeD, ce qui signifie : ajouter la directionSUD en entête de la liste chemin.

O Autres problèmes :• Comment partir d’un point de départ et d’arrivée et non des coins ?• Comment ajouter un test pour vérifier qu’il y a une solution ?• Comment retrouver tous les chemins les plus courts (et non un seul) ?• Comment retrouver tous les chemins (et non pas seulement le plus court) ?Correction : Voici un exemple de correction.

# -*- coding : utf -8 -*-2

# on importe la nouvelle version de print et4 # de la division

from __future__ import print_function , division , unicode_literals6

import sys8 if sys. version_info .major <= 2 :

input = raw_input10

from prof import loadTest , represente , loadImage , \12 SUD , NORD , EST , OUEST , MUR , VIDE

14 from pylab import shape , ones

16

## constante noméées:18 NON_ATTEINTE = -1

20

def propage (carte ,listeFront , carte_front ,t):22 """

entrée: carte = array de MUR/VIDE n*m = labyrinthe24 listeFront = liste de couple d’entiers = liste des cases atteintes au temps t

carte_front = array d’entiers n*m = carte26 t = entier = tps courant .

sortie : carte_front : mis à jour ,28 newListeFront = liste de couple d’entiers = liste des cases atteintes au temps t+1

"""30 (n,m)= shape(carte)

newListeFront = []32 for [i,j] in listeFront :

if i>0 and carte_front [i-1,j] == NON_ATTEINTE and carte[i-1,j] == VIDE:34 carte_front [i-1,j] = t+1

newListeFront += [ [i-1,j] ]36 if j>0 and carte_front [i,j -1] == NON_ATTEINTE and carte[i,j -1] == VIDE:

carte_front [i,j -1] = t+138 newListeFront += [ [i,j -1] ]

if i<n-1 and carte_front [i+1,j] == NON_ATTEINTE and carte[i+1,j] == VIDE:

4

40 carte_front [i+1,j] = t+1newListeFront += [ [i+1,j] ]

42 if j<m-1 and carte_front [i,j+1] == NON_ATTEINTE and carte[i,j+1] == VIDE:carte_front [i,j+1] = t+1

44 newListeFront += [ [i,j+1] ]return ([ carte_front , newListeFront ])

46

48 def propage_front (carte) :"""

50 entrée: carte = array n*m de MUR/VIDE = labyrinthesortie : carte_front = array d’entiers de taille n*m =

52 front propag é depuis la case de départ jusqu ’à la case d’arrivée"""

54

(n,m)= shape(carte)56 carte_front = NON_ATTEINTE *ones ((n,m),int)

58 listeFront = [[0 ,0]]carte_front [0 ,0] = 0;

60 t=0

62 while len( listeFront )>0 and carte_front [n-1,m -1] == NON_ATTEINTE :[ carte_front , listeFront ] = propage (carte ,listeFront , carte_front ,t)

64 t=t+1

66 if carte_front [n-1,m -1] == NON_ATTEINTE :print("le labyrinthe n’a pas de solution ")

68 else:print(" sortie atteinte en "+str(t)+" temps")

70 return ( carte_front )

72 def calcule_chemin ( carte_front ) :"""

74 entrée: carte_front = array n*m = carte du front propag é jusqu ’à la sortiesortie : listeD = liste NORD/SUD/OUEST/EST

76 = suite d’intructions permettant de retrouver la sortie à partir de l’entrée"""

78 (n,m)= shape( carte_front )

80 i=n -1; j=m-1 # position du pion à la fint = carte_front [n-1,m -1] # temps courant

82 listeD = [] # liste des directions

84 while t>0 and (i!=0 or j!=0) :if i>0 and carte_front [i-1,j] == t-1 :

86 i = i -1; listeD = [SUD] + listeDelif j>0 and carte_front [i,j -1] == t-1 :

88 j = j -1; listeD = [EST] + listeDelif i<n-1 and carte_front [i+1,j] == t-1 :

90 i = i+1; listeD = [NORD] + listeDelif j<m-1 and carte_front [i,j+1] == t-1 :

92 j=j+1; listeD = [OUEST] + listeDelse :

94 print("perdu en case "+str(i)+" " +str(j))t=t -1

96 return ( listeD )

98

100 carte = loadImage (1)

102 front = propage_front (carte)

5

chemin = calcule_chemin (front)104

represente (carte , chemin )

Une autre manière de coder :

1 # -*- coding : utf -8 -*-

3 # on importe la nouvelle version de print et# de la division

5 from __future__ import print_function , division , unicode_literals

7 import sysif sys. version_info .major <= 2 :

9 input = raw_input

11 from prof import loadTest , represente , loadImage , \SUD , NORD , EST , OUEST , MUR , VIDE

13

from pylab import shape , ones15

17 ## constante noméées:NON_ATTEINTE = -1

19

21 def propage (carte ,listeFront , carte_front ,t):"""

23 entrée: carte = array de MUR/VIDE n*m = labyrinthelisteFront = liste de couple d’entiers = liste des cases atteintes au temps t

25 carte_front = array d’entiers n*m = cartet = entier = tps courant .

27 sortie : carte_front : mis à jour ,newListeFront = liste de couple d’entiers = liste des cases atteintes au temps t+1

29 """(n,m)= shape(carte)

31 newListeFront = []for [i,j] in listeFront :

33

listeVoisinage = [ [i-1,j], [i+1,j], [i,j-1], [i,j+1] ]35

for [ii ,jj] in listeVoisinage :37 # ii ,jj est une case voisine de i,j

if ( 0<=ii <n and 0<=jj <m # existe39 and carte_front [ii ,jj] == NON_ATTEINTE

and carte[ii ,jj] == VIDE ):41 carte_front [ii ,jj] = t+1

newListeFront += [ [ii ,jj] ]43

45 return ([ carte_front , newListeFront ])

47

def propage_front (carte) :49 """

entrée: carte = array n*m de MUR/VIDE = labyrinthe51 sortie : carte_front = array d’entiers de taille n*m =

front propag é depuis la case de départ jusqu ’à la case d’arrivée53 """

55 (n,m)= shape(carte)carte_front = NON_ATTEINTE *ones ((n,m),int)

57

listeFront = [[0 ,0]]

6

59 carte_front [0 ,0] = 0;t=0

61

while len( listeFront )>0 and carte_front [n-1,m -1] == NON_ATTEINTE :63 [ carte_front , listeFront ] = propage (carte ,listeFront , carte_front ,t)

t=t+165

if carte_front [n-1,m -1] == NON_ATTEINTE :67 print("le labyrinthe n’a pas de solution ")

else:69 print(" sortie atteinte en "+str(t)+" temps")

return ( carte_front )71

def calcule_chemin ( carte_front ) :73 """

entrée: carte_front = array n*m = carte du front propag é jusqu ’à la sortie75 sortie : listeD = liste NORD/SUD/OUEST/EST

= suite d’intructions permettant de retrouver la sortie à partir de l’entrée77 """

(n,m)= shape( carte_front )79

i=n -1; j=m-1 # position du pion à la fin81 t = carte_front [n-1,m -1] # temps courant

listeD = [] # liste des directions83

while t>0 and (i!=0 or j!=0) :85 listeVoisinage = [ [i-1,j,SUD], [i+1,j,NORD], [i,j-1, EST], [i,j+1, OUEST] ]

pionDeplace = False;87

for [ii ,jj , direction ] in listeVoisinage :89 if ( not pionDeplace #

and 0<=ii <n and 0<=jj <m # existe91 and carte_front [ii ,jj] == t-1 ):

i = ii; j = jj; pionDeplace = True93 listeD = [ direction ] + listeD

95 if not pionDeplace :print("perdu en case "+str(i)+" " +str(j))

97

t=t -199 return ( listeD )

101 carte = loadImage (1)#carte = loadTest ()

103 front = propage_front (carte)chemin = calcule_chemin (front)

105

represente (carte , chemin )

7

Problème du cavalier d’EulerPelletier Sylvain PC, Lycée Descartes

On se propose de résoudre le problème suivant :

Trouver la trajectoire d’un cavalier sur l’échiquier, posé sur une case de départ quelconque, pour qu’il passe une et uneseule fois par toutes les cases de l’échiquier.

Ce problème est connu sous le nom de problème du cavalier d’Euler. Pour une étude complète du cavalier d’Euler, onpourra consulter l’article wikipedia :https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_cavalier.

On rappelle qu’un cavalier se déplace de deux cases dans une direction et d’une case dans une autre (exemple : deux foisau nord et une fois à l’ouest, ou deux fois à l’est et une fois au sud, etc.). Un cavalier placé au centre de l’échiquier peut ainsise déplacer sur 8 cases, mais un cavalier situé dans un coin n’aura que deux déplacements possibles.

FIGURE 1 – Déplacement du cavalier et une solution du problème d’Euler

Une méthode heuristique pour résoudre ce problème consiste étant donné une position du cavalier à• déterminer la liste des coups possibles depuis cette position,• pour chacun de ces coups possibles, déterminer combien de coups sont possibles depuis cette nouvelle position.• On choisit alors le coup qui possède le minimum de déplacements possibles.Le but de ce projet est donc de programmer cette méthode.

Bien sûr le but n’est pas uniquement de résoudre un problème d’échecs. On peut reformuler le problème ainsi : étant donnéun graphe, on veut visiter tous les noeuds du graphe en passant une et une seule fois par chaque noeud. Ce problème esttrès complexe.

La méthode proposée est une heuristique, rien ne prouve qu’elle donne le bon résultat. Il arrive qu’elle échoue.

La première étape est de définir précisément la structure de données dont on a besoin pour ce projet, c’est-à-dire commenton va représenter les données dans la machine.

Pour l’échiquier, on va utiliser un array 8×8 appelé jeu, qui représentera l’état des cases de l’échiquier.Au début, toutes les cases ont la valeur NON_VISITEE que l’on prendra égale à 0, sauf la case de départ qui contient la

valeur 1. Lorsque le cavalier est placé sur une case, celle-ci prend la valeur du numéro du coup. En affichant (avec print)cet array, on aura la trajectoire du cavalier.

Une case de l’échiquier sera représentée par un couple (i, j) ∈ [[0,7]]2. On aura aussi besoin d’une structure du type : position et nombre de coups possibles depuis cette position . Ce sera donc un triplet (i, j,k) où (i, j) est une case et k unentier donnant le nombre de coups possibles depuis (i, j).

Exemple .1 Voici un exemple de solution (affiché avec Python) :

[[ 29. 12. 33. 46. 35. 14. 63. 58.][ 32. 25. 30. 13. 64. 57. 36. 15.][ 11. 28. 47. 34. 45. 54. 59. 62.][ 26. 31. 24. 53. 56. 61. 16. 37.]

9

[ 23. 10. 27. 48. 1. 44. 55. 60.][ 4. 7. 20. 41. 52. 49. 38. 17.][ 9. 22. 5. 2. 19. 40. 43. 50.][ 6. 3. 8. 21. 42. 51. 18. 39.]]

O Analyse descendante de l’algorithme

Pour résoudre le problème, on commence par le découper en sous-problèmes plus simples. Chacun de ces sous-algorithmescorrespond à une fonction que vous devez écrire.

Pour chaque fonction écrite, il faut prévoir des tests précis permettant de vérifier qu’il n’y a pas d’erreurs. Laissez dans lecode, en commentaire, les tests que vous avez choisis pour tester chaque fonction.

Voici le découpage proposé :• Une fonction cases1move(jeu,i,j) détermine la liste des déplacements possibles à partir d’une position i,j du

cavalier et du jeu. La sortie est une liste de cases.L’entête de cette fonction est :

def cases1move (jeu ,i,j) :"""entrée:jeu = array 8x8

= état actuel de l’é chiquier(i,j) = case = couple de int [|0 ,7|]

= position actuelle du cavaliersortie :lc = liste de cases

= liste des cases que l’on peut atteindreà partir de [i,j]

"""

Le déplacement (i,j) vers (i0,j0) n’est possible que si la case (i0,j0) existe et n’a pas encore été atteinte.• Une fonction casesPoids(jeu,i,j) calcule la liste des déplacements possibles et le nombre de déplacements

possibles depuis chaque nouvelle position à partir des mêmes entrées que case1move.La sortie est une liste de la forme [i1,j1,k], où (i1, j1) est une case que l’on peut atteindre à partir de (i, j), et k est lenombre de cases que l’on peut atteindre à partir de (i1, j1) (y compris (i, j)).Bien entendu, cette fonction utilise la fonction cases1move.L’entête de cette fonction est :

def casesPoids (jeu ,i,j) :"""entrée:jeu = array 8x8


= position actuelle du cavaliersortie :lcp = liste de triplets [i1 ,j1 ,k]

= [i1 ,j1] peut être atteinte depuis [i,j]k nbr de cases que l’on peut atteindreà partir de [i1 ,j1]

"""

• Une fonction calculeMin3(l3uplet) qui prend en entrée une liste l3uplet de 3-uplet et qui renvoie l’indice l du3uplet de l3uplet dont le troisième élément est minimal.Autrement dit, on note i0, j0, n=l3uplet[l], et n vérifie :

n = min

c∣∣∣(a,b,c) ∈ l3uplet

L’entête est :

10

def calculeMin ( l3uplet ) :"""entrée: l3uplet = liste de 3upletsortie : l = int = indice du 3uplet

dont le troisi ème élément est minimal"""

On a alors simplement un calcul de minimum.NB : interdit d’utiliser une fonction min, vous devez refaire à la main .• Une fonction coupSuivant(jeu,i,j) détermine le coup suivant à partir de la position i,j du cavalier. La sortie est

un couple (i1, j1) donnant la nouvelle position choisie du cavalier. Cette fonction utilise les fonctions précédentes.On convient que la sortie est (−1,−1) si aucun coup n’est possible.L’entête est :

def coupsSuivant (jeu ,i,j) :"""entrée:jeu = array 8x8


= position actuelle du cavaliersortie :(i1 ,j1) = case

= position suivante du cavalier(-1,-1) si pas de position possible

"""

• Enfin, le reste des instructions est écrite directement dans le script pour avoir la trajectoire du cavalier. Il faut initialiserl’échiquier puis poser le cavalier sur une case, et déplacer le cavalier de case en case, jusqu’à avoir rempli l’échiquierou ne plus avoir de solution.

Correction : Voici un exemple de correction.

# -*- coding : utf -8 -*-2

"""4 Ré solution du problème du cavalier en Python

"""6

from numpy import zeros , array8

10 # constante nomméesNON_VISITE = 0

12

def cases1move (jeu ,i,j) :14 """

entrée:16 jeu = array 8x8

= état actuel de l’é chiquier18 (i,j) = case = couple de int [|0 ,7|]

= position actuelle du cavalier20 sortie :

lc = liste de cases22 = liste des cases que l’on peut atteindre

à partir de [i,j]24 """

lc = []26

if i+2 < 8 and j-1 >= 0 and jeu[i+2, j -1]== NON_VISITE :28 lc. append ([i+2,j -1])

if i+2 < 8 and j+1 < 8 and jeu[i+2, j+1]== NON_VISITE :30 lc. append ([i+2,j+1])

if i+1 < 8 and j-2 >= 0 and jeu[i+1, j -2]== NON_VISITE :

11

32 lc. append ([i+1,j -2])if i+1 < 8 and j+2 < 8 and jeu[i+1, j+2]== NON_VISITE :

34 lc. append ([i+1,j+2])if i-1 >= 0 and j-2 >= 0 and jeu[i-1, j -2]== NON_VISITE :

36 lc. append ([i-1,j -2])if i-1 >= 0 and j+2 < 8 and jeu[i-1, j+2]== NON_VISITE :

38 lc. append ([i-1,j+2])if i-2 >= 0 and j-1 >= 0 and jeu[i-2, j -1]== NON_VISITE :

40 lc. append ([i-2,j -1])if i-2 >= 0 and j+1 < 8 and jeu[i-2, j+1]== NON_VISITE :

42 lc. append ([i-2,j+1])return lc

44

46 def casesPoids (jeu ,i,j) :"""

48 entrée:jeu = array 8x8

50 = état actuel de l’é chiquier(i,j) = case = couple de int [|0 ,7|]

52 = position actuelle du cavaliersortie :

54 lcp = liste de triplets [i1 ,j1 ,k]= [i1 ,j1] peut être atteinte depuis [i,j]

56 k nbr de cases que l’on peut atteindreà partir de [i1 ,j1]

58 """lcp = []

60 lc = cases1move (jeu ,i,j)for i1 ,j1 in lc :

62 lc2 = cases1move (jeu ,i1 ,j1)k = len(lc2)

64 lcp. append ([i1 ,j1 ,k])return lcp

66

68

def calculeMin ( l3uplet ) :70 """

entrée: l3uplet = liste de 3uplet72 sortie : l = int = indice du 3uplet

dont le troisi ème élément est minimal74 """

l = 076 mini = l3uplet [0][2]

n = len( l3uplet )78 for i in range (1,n) :

if l3uplet [i][2] < mini :80 l = i

mini = l3uplet [i][2]82 return l

84

def coupsSuivant (jeu ,i,j) :86 """

entrée:88 jeu = array 8x8

= état actuel de l’é chiquier90 (i,j) = case = couple de int [|0 ,7|]

= position actuelle du cavalier92 sortie :

(i1 ,j1) = case94 = position suivante du cavalier

12

(-1,-1) si pas de position possible96 """

l3 = casesPoids (jeu ,i,j)98 print(l3)

if l3 == [] :100 print(" erreur : bloqué à la case ",i,j)

return -1,-1102 imd = calculeMin (l3) # indice du meilleur coups

i = l3[imd ][0] # les deux composantes du meilleur coups104 j = l3[imd ][1]

return i,j106

jeu = zeros( (8 ,8))108

# position départ110 i=4

j=4112 jeu[i][j]=1

114 t=2while i!= -1 and t <=64 :

116 print(jeu)[i,j]= coupsSuivant (jeu ,i,j)

118 print(i,j)jeu[i][j]=t

120 print(jeu)t += 1

122

if t==65 :124 print("pb résolu!")

else :126 print("échec de la méthode")

13

GénéralitésImplémentation avec des listesExemple d’utilisation des pilesExercices

1 — Structure de piles

I GénéralitésUne pile est un conteneur dans lequel on peut uniquement :• savoir si la pile est vide,• consulter le dernier élément de la pile,• enlever le dernier élément de la pile (dépiler),• ajouter un élément au-dessus (empiler).

On parle de pile LIFO (last in first out).

Voici des exemples d’utilisation de piles :

. Dans un navigateur d’aide : les pages visités dans la session sont sauvegardésdans une pile. À chaque page consultée, un élément est ajouté à la pile, on peutreculer d’une page (c’est-à-dire dépiler une page).

. Dans quasiment tous les logiciels, il existe une fonction Annuler : toutes lesactions sont sauvegardées dans une pile, et on peut annuler la dernière action endépilant .

. C’est très utile dans les mécanismes bas niveaux : vérifier qu’une expressionest syntaxiquement correcte, c’est-à-dire par exemple qu’à chaque parenthèseouvrante corresponds une parenthèse fermante.C’est particulièrement utile pour les langages marqués comme le HTML qui sert àfaire des pages web. Pour ces langages, il y a des balises ouvrante de la forme<a> et des balises fermantes </a> qui délimitent des blocs.Chaque balise ouvrante doit correspondre à une balise fermante placée avant avecla règle suivante : les blocs délimités par les balises peuvent être imbriquées maispas se croiser .Autrement dit, on peut avoir :

<a>

16 Structure de piles

</a>

mais pas :

<a>

</a>

La vérification syntaxique d’un tel langage se fait en lisant le fichier ligne parligne et en gardant une pile des balises utilisées :

– quand une nouvelle balise ouvrante est lue, elle est ajouté en haut de la pile,– lorsqu’une balise fermante est lue, on dépile la dernière balise et on vérifie

la correspondance entre la balise dépilée et la balise fermante.– à la fin du fichier, la pile doit être vide.

. On peut aussi vérifier qu’un programme Python est bien écrit en vérifiant qu’àchaque ligne :

– soit une nouvelle indentation est crée,– soit on revient à un des niveaux d’indentations précédents.

La principale utilité des piles est la gestion des fonctions récursives que l’on verraau prochaine chapitre.

. On utilise souvent des boucles : while len(pile)>0. Une fonction de terminai-son naturelle est alors la longueur de la pile.

. Il existe aussi la structure de file dite FIFO (first in first out) qui permet parexemple de gérer une file d’attente à un serveur d’impression, ou une file dedonnées qui doivent être acheminées par un routeur. Cette structure étant hors-programme, on ne l’étudiera pas en détail, néanmoins, il est facile de l’implémen-ter avec des listes.

II Implémentation avec des listes

Conformément au programme, on va utiliser des listes pour simuler des files. Onutilisera les syntaxes suivantes :• pile = [] ou encore pile = list() pour créer une pile (ie une liste vide)• len(pile) == 0 pour savoir si la pile est vide,• pile[-1] donne accès au dernier élément,• pile.pop() pour enlever et retourner le dernier élément,• pile.append(x) pour ajouter un nouvel élément x.

R On peut donc utiliser : pile.pop() pour enlever le dernier élément, ouy=pile.pop() pour affecter y à la valeur du dernier élément et l’enlever de lapile.

III Exemple d’utilisation des piles 17

! Pour les types mutables, attention à stocker les valeurs dans la pile et non lesréférences !

III Exemple d’utilisation des piles

III.1 Parenthésage d’une expressionConsidérons une expression constituée de parenthèses (), crochet [] ou accolade

et d’autres lettres.On souhaite vérifier que l’expression est bien parenthésée, c’est-à-dire :• qu’à chaque symbole ouvrant corresponds bien un symbole fermant placée

avant.• Que les symboles ne se croisent pas.On construit donc une pile définie ainsi :• au début la pile est vide,• à chaque caractère lu, si c’est un caractère ouvrant, on empile ce caractère,• si c’est un caractère fermant, on vérifie que le dernier caractère empilé lui corres-

pond. Si il n’y a pas d’erreur, on dépile.• à la fin, on vérifie que la pile est vide.Voici un exemple de programme que l’on peut écrire ainsi :

def bienParenthese (s) :2 """

entrée: s = chaîne de caract ères4 = expression à contrôler

sortie : booléen = True si bien parenth ése ,6 False sinon

"""8

pile = [] # pile des symboles utilis ées10 # = une liste de caract ères.

12 for cara in s :

14 # facultatif : passe directement au caract ère suivant# si cara n’est pas un symbole :

16 if cara not in ("(", ")", "[", "]", "", "") :continue

18

if cara in ( "(", "[", "" ) :20 pile. append (cara)

elif cara == ")" :22 if len(pile) == 0 or pile [-1] != "(" :

return False24 pile.pop ()

elif cara == "]" :26 if len(pile) == 0 or pile [-1] != "[" :


elif cara == "" :30 if len(pile) == 0 or pile [-1] != "" :



34 return ( len(pile) == 0 )

. On peut modifier le programme ci dessus de manière à vérifier que l’ordre desparenthèses est respecté dans le sens où les symboles ouvrants les plus intérieursdoivent être des parenthèses, puis des crochets, puis des accolades.Pour cela, il faut remplacer la ligne :

if cara in ( "(", "[", "" ) :pile. append (cara)

Par :

if cara == "(" :if len(pile) == 0 or pile [-1] == "[" :

pile. append (cara)else :

return Falseelif cara == "[" :

if len(pile) != 0 and pile [-1] == "("pile. append (cara)

else :return False

elif cara == "" :if len(pile) >= 2 and pile [-1] == "[" :

pile. append (cara)else :

return False

III.2 Branchement dans les L-system

Les L-system sont une modélisation fractale de la croissance des plantes.Le principe est de créer avec un processus récursif une liste d’instructions qui

seront exécutées par la machine et qui permettront d’obtenir une représentation dela plante.

Ces instructions sont du type langage tortue : on dispose d’un système graphique(une tortue) qui est défini par :• une position (x,y) ∈ R2, une direction θ ∈ R,• une couleur c ∈ [[0,CMAX]] et une épaisseur de trait t ∈ N∗.L’instruction dans le langage L-systeme est donc une chaîne caractère conte-

nant les symboles :+ pour augmenter la valeur de θ d’une constante ∆θ ,- pour diminuer la valeur de θ de ∆θ ,F pour tracer un trait (de longueur 1) à la couleur et l’épaisseur courante. La

tortue se déplace alors en traçant, ce qui signifie que les valeurs de (x,y) sontchangées en (x+ cosθ ,y+ sinθ).

n pour passer à la couleur suivante si possible,p pour passer à la couleur précédente si possible,

III Exemple d’utilisation des piles 19

l pour augmenter l’épaisseur du trait,s pour diminuer l’épaisseur du trait,[ pour créer un embranchement,] pour revenir à l’embranchement précédent.

Pour mener ce projet, il faut utiliser la structure de données suivante :• La tortue sera représentée sous la forme d’une liste [x,y,theta,c,t] donnant

les indications sur la position, la direction, la couleur et l’épaisseur du trait.• on dispose d’une fonction trace qui prends en entrée une tortue et sort une

tortue (qui s’est déplacée après avoir tracé). Cette fonction modifie le graphique.• Enfin, pour réaliser les embranchements, on utilisera une pile, qui sera donc une

liste de tortue (ie de 5-uplets).Voici un exemple de réalisation :

def execute (ordre) :2 """

ordre = chaîne de caract ères +-Fnpls []4 = listes des instructions tortue

sortie = graphique + True si la chaîne est correcte6 / False sinon

"""8

# initialisation de la tortue10 # au centre et vers le haut

# couleur 0 et é paisseur 112 tortue = [0, 0, pi/2, 0, 1]

14 pile = [] #pile de tortues pour les embranchements

16 for cara in ordre :if cara == "+" :

18 tortue [2] += DTHETAelif cara == "-" :

20 tortue [2] -= DTHETAelif cara == "F" :

22 tortue = trace( tortue )elif cara == "n" and tortue [3] < CMAX :

24 tortue [3] += 1elif cara == "p" and tortue [3] > 0 :

26 tortue [3] -= 1elif cara == "l" :

28 tortue [4] += 1elif cara == "s" and tortue [4] > 0 :

30 tortue [4] -= 1elif cara == "[" :

32 pile. append ( tortue .copy () )elif cara == "]" :

34 if len(pile) == 0 :print("pb de parenth ésage")

36 return Falsetortue = pile.pop ()

38 else :


print(" instruction incorrectes ")40 return False

return ( len(pile) == 0 )

! Il faut utiliser pile.append( tortue.copy() ) et non pile.append( tortue )sinon c’est les références qui sont stockées dans la pile et donc les modificationsultérieures de la liste tortue seront exécutées aussi sur les valeurs stockées.

Structure de pilePelletier Sylvain PC, Lycée Descartes

Exercice 1 Palindromes et pilesUn palindrome est une chaîne de caractères qui est identique à elle-même lue en sens inverse : exemple esse radar

est un palindrome mais math n’en est pas un.En utilisant une structure de pile, écrire une fonction estPalindrome(X) qui renvoie True si la chaîne de caractère X

est un palindrome, False sinon.Estimer la complexité en espace et en temps.

Correction : Voici un exemple de programme

def estPalindrome (X) :2 """

entrée: X = chaîne de caract ères4 = mot à analyser

sortie : booléen = True si X est palindrome6 """

pile = []8 n = len(X)

if n%2 == 0 :10 debut = n//2

suite = n//212 else :

debut = n//214 suite = n//2+1

for lettre in X[: debut ]:16 pile. append ( lettre )

for lettre in X[suite :]:18 if pile.pop () != lettre :

return False20 return True

22

24 for mot in ("esse", "estse", "math", " estsee ", "kayak", "radar") :if estPalindrome (mot) :

26 print(mot + " est un palindrome ")else :

28 print(mot + " n’est pas un palindrome ")

Exercice 2 Notation polonaise inverséeLa notation polonaise inversée est la notation post-fixée d’une expression.Autrement dit, plutôt que d’écrire les opérandes autour de l’opérateur (comme dans 2+3), on écrit les opérandes puis

l’opérateur ([2,3,"+"]).Par exemple, la notation polonaise inverse de l’expression :

J = ((13−1)×2+7/4)

est :

J = [ 13, 1 , "-" , 2 , "*", 7 , 4 , "/" , "+"]

Le gros avantage de cette notation est qu’on n’a pas besoin de parenthèse !En pratique, c’est celle qui est utilisée dans les mécanismes bas-niveaux pour évaluer les expressions.

21

En utilisant une pile, créer une fonction evalueNPI qui permet d’évaluer une expression écrite en notation polonaiseinversée. On utilisera en entrée une liste contenant :• des nombres (flottants ou entiers) pour les opérandes,• des caractères "+","*","/","-" pour les opérateurs.

Correction :

def evalueNPI ( expression ):2 """

entrée: expression = liste de (float ou int )/ string4 = expression à é valuer

sortie : out = float = ré sultat6 """

pile = []8 for symbole in expression :

# on peut aussi faire 4 if.10 if symbole in ( "+", "-", "*", "/" ) :

opr = pile.pop () # opérande de gauche12 opl = pile.pop () # opérande de droite

pile. append (eval( str(opl) + symbole + str(opr )))14 else :

pile. append ( symbole )16 out = pile.pop ()

assert len(pile) == 018 return out

20

J = [ 13, 1 , "-" , 2 , "*", 7 , 4 , "/" , "+"]22 print("l’é valuation de ",J, " est ", evalueNPI (J))

24 J = [ 1, 2, "+", 3, "*"]print("l’é valuation de ",J, " est ", evalueNPI (J))

26

J = [ 1,2,"*" ,3,"+"]28 print("l’é valuation de ",J, " est ", evalueNPI (J))

30 J = [ 1,2, "+", 3, "+"]print("l’é valuation de ",J, " est ", evalueNPI (J))

Exercice 3 Autour des mélanges de cartesOn souhaite simuler le mélange de carte suivant à l’aide de pile :• on prends le paquet dans la main, on coupe au hasard, on a donc deux paquets (un dans chaque main)• on mélange les deux paquets en choisissant au hasard une carte de la main gauche ou une carte de la main droite

jusqu’à épuisement des deux paquets.(c’est le mélange américain)

Écrire une fonction couper qui prend une pile en entrée, et la coupe en enlevant de son sommet un nombrealéatoire d’éléments qui sont renvoyés dans une seconde pile.

Exemple : si la pile initiale est [1, 2, 3, 4, 5]on tire au hasard un entier de [[1,4]] si on obtient 2, alors on renvoie[4,5] (les deux éléments situés au-dessus) et la pile initiale devient [1, 2, 3].

Écrire une fonction mélange qui prends en entrée deux piles et construit la pile mélangée.Ce mélange permet le tour de magie de Gilbreath :• on construit un jeu de 32 cartes en alternant une carte rouge / une carte noire (vous utiliserez une liste de 0,1).• On mélange en introduisant un petit changement : lorsqu’on coupe, on change l’ordre du deuxième paquet. Sur

l’exemple ci-dessus, la pile retournée par la fonction couper est [5,4].• Le paquet obtenu contient alors toujours des couples de cartes rouges / noires.Vérifiez ce principe.Généraliser au cas d’un jeu de n cartes constitué de groupes de k cartes.

22

Correction :

## bilbioth èque2 from pylab import rand

4 def couper ( paquet ) :"""

6 entrée: paquet = list = paquet de cartes à coupersortie : paquetExtrait = list = paquet "sorti par le haut"

8 + modif de paquet"""

10 n = len( paquet )nbrCarteEnleve = int ( rand () * (n -1) ) + 1

12 paquetExtrait = []for i in range( nbrCarteEnleve ) :

14 paquetExtrait . append ( paquet .pop () )return paquetExtrait

16

def melange (paquet1 , paquet2 ):18 """

entrée: paquet1 , paquet2 = liste = deux paquets de cartes .20 sortie : jeuMelange = liste = jeu obtenu en mé langeant alternativement

paquet1 et paquet222 """

jeuMelange = []24 while len( paquet1 ) != 0 and len( paquet2 ) != 0 :

alea = rand ()26 if alea < 0.5 :

jeuMelange . append ( paquet1 .pop () )28 else :

jeuMelange . append ( paquet2 .pop () )30 if len( paquet1 ) == 0 :

jeuMelange . extend ( paquet2 )32 elif len( paquet2 ) == 0 :

jeuMelange . extend ( paquet1 )34 return jeuMelange

36 for test in range (15):carte = [0 ,1 ,2 ,3 ,4 ,5] * 3

38 paquetExtrait = couper (carte)jeu = melange (carte , paquetExtrait )

40 print(jeu)

23

Fonctions récursivesÉtude théorique d’une fonction récursiveExemple : algorithme itératif du triangle dePascalExemple Exponentiation rapideExercices

2 — Récursivité

I Fonctions récursivesDéfinition I.1 Une fonction est récursive si elle contient une instruction qui l’ap-pelle elle-même.

Exemple I.1 La fonction factorielle est le prototype de fonction récursive :

def fac(n):if n == 0 :

return 1return n * fac(n -1)

Exemple I.2 L’autre exemple basique est le calcul d’une suite récursive. Soit (un) lasuite définie par :

u0 = 2 et ∀n ∈ N, un+1 =13(un +u2

n)

Pour écrire l’algorithme correspondant, on écrit : ∀n ∈ N∗, un =13(un−1 +u2

n−1) eton a :

def u(n) :if n == 0

return 2return (1/3) * ( u(n -1) + u(n -1)**2 )

L’écriture d’une fonction récursive est ainsi intiment liée au principe de récur-rence :• on donne les premiers termes (cas particuliers)• on indique comment se ramener à l’hypothèse de récurrence (appel à la fonction

sur des valeurs inférieures).

26 Récursivité

L’utilisation de fonction récursive permet généralement d’écrire des algorithmesélégant, court et très proche de la modélisation mathématique. Néanmoins, ces algo-rithmes ne sont pas toujours efficaces du point de vu de la complexité en temps et enespace. L’étude théorique d’une fonction récursive est plus compliqué que l’étude d’unefonction non récursive.

R Une fonction récursive contient systématiquement plusieurs return.

O Pile d’appel d’une fonction récursivePour utiliser une fonction récursive, le processeur crée une pile d’appel à la fonction.

Par exemple, lorsqu’on calcule fac(4) avec fac la fonction factorielle, le processeur :• crée un appel la fonction avec n = 4, dans lequel il rencontre le nom fac(3).• Il crée alors un nouvel appel à la fonction dans un niveau d’exécution inférieur,

d’après le principe de portée des variables.Il fait donc appel à la fonction avec pour variable d’entrée n = 3,• Il recommence ensuite pour n = 2 et n = 1.• Lorsque la fonction se termine (appelée sur l’entrée n = 1), la valeur est envoyé à

l’espace de nom du niveau d’exécution au-dessus (correspondant donc à l’appelavec n = 2), après multiplication par 2, cette fonction se termine et retourne unevaleur.• Cette valeur est aussi transmise au niveau d’exécution situé au-dessus, et ainsi de

suite, jusqu’au niveau d’exécution situé au sommet.La taille de cette pile est liée au nombre d’appels à la fonction. En Python,

cette pile a une taille limitée à 1000. On obtient l’erreur : RuntimeError: maximumrecursion depth exceeded in comparison On peut changer cette limite en uti-lisant la fonction setrecursionlimit du module sys.

Pour mesurer le nombre d’appel, on pourra utiliser une variable globale :

nbrAppel = 0def fac(n):

global nbrAppelnbrAppel += 1if n == 0 :

return 1return n * fac(n -1)

fac (10)print( nbrAppel )

O Exemples d’algorithme itératif écrit de manière récursive Exemple I.3 Palindromes Pour déterminer si un mot est un palindrome, on peututiliser le définition suivante :• tout mot de longueur 0 ou 1 est un palindrome,• un mot de longueur n > 2 est un palindrome si sa première et dernière lettre

sont les mêmes et si le mot obtenu en considérant les lettres 1 à n− 1 est unpalindrome.

Cela donne :

def estPalindrome (mot) :if len(mot )<= 1 :

II Étude théorique d’une fonction récursive 27

return Trueif mot [0] != mot [-1] :

return Falsereturn estPalindrome ( mot [1:n] )

Exemple I.4 Recherche d’un élément dans une liste Pour savoir si une listecontient un élément nul, on peut utiliser un principe similaire :

def contient0 (liste) :if len(liste) == 0 :

return Falseelif liste [0] == 0

return Trueelse:

return contient0 (liste [1:])

R Une version ultra minimaliste de cet algorithme est donc :

def contient0 (liste) :return (len(liste )>0

and (liste [0] == 0 or contient0 (liste [1:])) )

Exemple I.5 Algorithme d’Euclide récursif Pour calculer le PGCD de (a,b), onutilise la division euclidienne a = bq+ r et on sait que le pgcd de (a,b) est celui de(b,r). On est donc ramené au calcul du pgcd de (b,r), jusqu’à ce que le reste soit nul,auquel cas, on renvoie le dernier reste. Cela donne :

def euclide (a,b) :if b == 0 :

return aelse :

return euclide (b, a%b)

II Étude théorique d’une fonction récursive

II.1 TerminaisonLa terminaison d’un algorithme récursif n’est pas claire : par exemple, la fonction

fac appelée sur un entier négatif ne finira pas.

Pour montrer la terminaison d’une fonction récursive, on peut trouver un entiernaturel qui décroît strictement à chaque appel de la fonction. Le plus souvent c’estl’un des arguments de la fonction récursive.

Exemple II.1 Pour la fonction factorielle, on constate qu’à chaque appel de lafonction, la valeur de l’argument n diminue de 1. On est donc assuré que la fonctiontermine au bout de n appels à la fonction.

28 Récursivité

II.2 CorrectionPour montrer la correction d’un algorithme itératif, on procède généralement parrécurrence avec une propriété du type : P(n) : la fonction ... appelée sur l’entier ntermine et renvoie la valeur correcte.

On prouve alors la correction et la terminaison en même temps.

Exemple II.2 Pour la fonction factorielle, on utilise :

P(n) : la fonction fac appelée sur l’entier n termine et renvoie n!.

L’initialisation pour n = 0 est évidente. Considérons n > 0 fixé tel quel P(n) estvrai, la fonction fac appelée sur n+1 consiste à calculer l’expression n*fac(n-1) quise termine d’après l’hypothèse de récurrence et donne : n× (n−1)! c’est-à-dire n!.

II.3 Complexité

Généralement, on détermine la complexité C(n) du calcul de f (n) par une formulede récurrence.

La complexité en mémoire d’une fonction récursive est liée au nombre d’appelsA(n) de la fonction, qui se calcule aussi par récurrence.

Prenons par exemple, le programme vu dans la première section :

def u(n) :if n == 0

return 2return (1/3) * ( u(n -1) + u(n -1)**2 )

On note C(n) le nombre de calculs nécessaires pour l’expression u(n), et A(n) lenombre d’appels. On voit alors :

C(0) = 0∀n ∈ N∗, C(n) = 2C(n−1)+3

A(0) = 0∀n ∈ N∗, A(n) = 2A(n−1)+2

On a alors facilement

∀n ∈ N, C(n) = 3(2n−1) ainsi C(n) = O(2n) An = 2n+1−2 ainsi An = O(2n).

R En fait, la complexité mémoire est inférieure, car le processeur calcule d’abordsla valeur du premier u(n−1) puis libère cette mémoire pour calculer la valeurdu deuxième u(n−1).

Reprenons cette exemple, de manière plus efficace :

def u(n) :if n == 0

return 2x = u(n -1)return (1/3) * ( x + x**2 )

II Étude théorique d’une fonction récursive 29

On note toujours C(n) le nombre de calculs nécessaires pour l’expression u(n), et A(n)le nombre d’appels. On a alors :

C(0) = 0∀n ∈ N∗, C(n) =C(n−1)+3

A(0) = 0∀n ∈ N∗, A(n) = A(n−1)+1

Et donc on a des valeurs largement inférieures au précédentes :

∀n ∈ N, C(n) = 3n ainsi C(n) = O(n) An = n ainsi An = n.

À chaque appel, il y a deux variables crées (x et n), donc la complexité en mémoire estde l’ordre de 2n.

C’est souvent le cas lorsqu’on utilise un algorithme récursif : la manière dont on leprogramme modifie la complexité.

II.4 Amélioration d’un algorithme récursifConsidérons l’exemple de La suite de Fibonnacci

F0 = 0 F1 = 1 ∀n ∈ N, Fn+2 = Fn +Fn+1.

L’algorithme récursif de calcul est alors le suivant :

1 def fibbo(n):if n == 0 :

3 return 0elif n == 1:

5 return 1else :

7 return fibbo(n -1) + fibbo(n -2)

Cet algorithme est catastrophique en terme de temps de calcul. Si C(n) est la nombrede calcul nécessaire pour calculer fibbo(n), on a :

∀n ∈ N,C(n+2) =C(n)+C(n+1)+1.

La suite C(n) est alors O(ϕn) où ϕ est le nombre d’or.On voit bien le problème : pour calculer Fn, l’algorithme fait le calcul de Fn−1, puis

de Fn−2. Lors du deuxième calcul de Fn−2, il ne se sert pas des valeurs déjà calculées ilrepart à 0. Pour améliorer cet algorithme une idée naturelle est de stocker les valeurs deFn calculés dans un tableau pour éviter de les recalculer.

R On retrouve un grand principe pour la complexité : on diminue la complexité entemps en utilisant plus la mémoire.

Le programme devient alors :

1 NMAX = 100nbrAppel = 0

3

# tabFibbo va contenir les valeurs connues de

30 Récursivité

5 # fibbo (n)tabFibbo = [-1] * NMAX

7 tabFibbo [0]=0tabFibbo [1]=1

9

def fibbo(n):11 """

n <= NMAX !13 """

# global tabFibbo15 global nbrAppel

nbrAppel += 117 if tabFibbo [n] == -1 : # fibbo(n) est inconnu

tabFibbo [n] = fibbo(n -1) + fibbo(n -2)19 return tabFibbo [n]

21 print(fibbo (99))print( nbrAppel )

Plusieurs technique existent pour utiliser le tableau :• utiliser une variable globale comme ci-dessus,• modifier la liste à l’aide d’une méthode (on peut ainsi modifier la liste dans

l’espace d’exécution supérieur), ce qui revient à utiliser une variable globale. Dansle programme ci-dessus, l’instruction global tabFibbo est ainsi facultative.• Utiliser une fonction fibboRec à l’intérieur de la fonction fibbo. C’est la fonc-

tion fibbo qui initialise le tableau, celle-ci est utilisé dans l’espace d’exécutioninférieur de la fonction fibboRec.

Voici un exemple de solution avec la dernière méthode :

def fibbo(n):2

4 tabFibbo = [-1] * (n+1)tabFibbo [0]=0

6 tabFibbo [1]=1

8 def fibboRec (n):if tabFibbo [n] == -1 : # fibbo(n) est inconnu

10 tabFibbo [n] = fibboRec (n -1) + fibboRec (n -2)return tabFibbo [n]

12 return fibboRec (n)

14 print(fibbo (99))

III Exemple : algorithme itératif du triangle de PascalOn cherche à générer les parties de [[1,n]] qui contiennent k éléments, ensemble

d’ensembles noté Pk ([[1,n]]) qui sera représenté sous la forme d’une liste de liste.Toues les éléments X de Pk ([[1,n]]), qui sont donc des parties de [[1,n]] à k éléments,

vérifient une et une seule des conditions suivantes :• Soit n /∈ X et donc essentiellement, X est une partie de [[1,n−1]] à k éléments,

III Exemple : algorithme itératif du triangle de Pascal 31

• Soit n ∈ X et donc si on enlève n, l’ensemble X \n est une partie de [[1,n−1]]à k−1 éléments. Vu d’un autre côté, X est obtenu en considérant une partie àk−1 éléments de [[1,n−1]] à laquelle on a ajouté n.

C’est l’interprétation combinatoire de la propriété de Pascal sur les coefficientbinomiaux : Pk ([[1,n]]) est l’union disjointe de• Pk ([[1,n−1]]) l’ensemble des parties de [[1,n−1]] à k éléments,• un autre ensemble noté B, qui est l’ensemble des parties de [[1,n−1]] à k− 1

éléments auxquelles on a jouté n. On a de manière évidente : B est en bijectionavec Pk−1 ([[1,n−1]]).

Ce qui donne la formule bien connue :(nk

)=

(n−1

k

)+

(n−1k−1

).

Cet démonstration mathématique se transforme naturellement en algorithme car demême que pour le calcul des coefficients

(nk

), on connaît les ensembles à 0 éléments et

à n éléments. Cela donne :

def genereParties (k , n):"""entrée: entiers k entiers nsortie : liste de liste

= les combinaisons de k éléments de 1 n ."""if k==0 :

# seul ensemble à 0 élément est l’ensemble videreturn [[]] #

elif k==n :# seul ensemble à n élément de [|1,n|] est [|1,n|]return [ list(range (1,n+1)) ]

else :# calcul des listes de k éléments de [|1, n -1|]L1 = genereParties (k , n -1)# calcul des listes de k-1 éléments de [|1, n -1|]# auquel on ajoute nL2 = genereParties (k-1 , n -1)for l in L2 :

l. append (n)return L1 + L2

R L’utilisation d’objets mutables et de références permet d’écrire :

for l in L2 :l. append (n)

pour ajouter n à la fin de toutes les liste de L2.Autre détail technique : la fonction range renvoie un itérateur, pour obtenir uneliste, on convertit avec list(range(1,n+1))

Pour prouver que cet algorithme se termine, on peut constater que la valeur max(k,n)est décroissante strictement à chaque appel de la fonction.

Comme on peut le voir cet algorithme est élégant mais loin d’être optimal pour lacompléxité.

32 Récursivité

Exercice 1 Modifier le programme, pour garder en mémoire les valeurs connues degenereParties(k , n).

IV Exemple Exponentiation rapideOn souhaite calcule xn avec x un réel et n un entier. On utilise alors la méthode

suivante :

xn =

(x

n2)2

si n est pair

x×(x

n2)2

si n est impair

Cela donne ainsi l’algorithme :

def exponentiation (x,n) :2 if n == 0 :

return 14 r = exponentiation (x , n//2)

if n%2 == 0 :6 return r*r

else :8 return x*r*r

Pour prouver la correction et la terminaison de cet algorithme, on considère x ∈ R,et on utilise la proposition suivante :

P(n) : exponentiation(x,n) se termine et donne xn.

On raisonne alors par récurrence forte :• P(0) est vrai.• Soit n fixé, tel que ∀k ∈ [[0,n]], P(k) est vrai. Si n est pair, on écrit n = 2k, et en uti-

lisant l’hypothèse P(k), on obtient que l’expression r = exponentiation(x , n//2)se termine et donne xk. D’où l’expression r*r se termine et donne bien x2k ie xn. Sin est impair, on écrit n= 2k+1, et on a toujours r = exponentiation(x , n//2)se termine et donne xk. D’où l’expression x*r*r se termine et donne bien x2k+1

ie xn.• D’où le résultat.

Si on note C(n) le nombre de calcul nécessaire pour obtenir xn, on a :

C(0) = 0 et ∀n ∈ N∗, C(n)6C(⌊n

2

⌋)+2

On en déduit alors que C(n) = O(ln(n)). Le nombre d’appel à la fonction est A(n) =O(ln(n)).

RécursivitéPelletier Sylvain PC, Lycée Descartes

Exercice 1 Écrire une fonction récursive qui calcule la somme des n premiers entiers. Prouver la correction et déterminerle nombre d’opérations et d’appels nécessaires.

def sommeRec (n) :2 if n == 0 :

return 04 return n + sommeRec (n -1)

Il y a bien sûr n appels, donc n additions.La correction et la terminaison se montre par la propriété : P(n) : sommeRec se termine et renvoie ∑

nk=0 k.

Exercice 2 Une autre méthode pour calculer les coefficients binomiaux

Écrire un algorithme qui permet de calculer récursivement la valeur de(

np

)en utilisant :

∀n ∈ N∗,∀p ∈ [[1,n]] ,(

np

)=

np

(n−1p−1

).

Déterminer le nombre d’appels en fonction de n et p.

Correction : Il ne faut pas oublier d’ajouter des conditions d’arrêt :

def binomRec (n,p) :2 if n<0 or p<0 or p>n :

return 04 elif n==0 or n==1 or p==0 or p==n:

return 16 else :

return n/p* binomRec (n-1, p -1)

Normalement seul le cas particulier p = 0 est à considérer. Il n’y a que p appel à la fonction.Par contre, on n’a pas un entier comme résultat.

Exercice 3 Liste miroirÉcrire une fonction récursive qui prends en entrée une liste L et qui construit la liste comportant les mêmes éléments

que L mais dans l’ordre inverse. Bien entendu, on s’interdit d’utiliser la fonction reverse.

Correction : Si la liste est vide, il n’y a rien à faire, sinon , il faut extraire les éléments 1 au dernier, puis mettre lepremier élément à la fin.

1 def reverseRec (L):if L == [] :

3 return []M = reverseRec (L[1:])

5 M. append (L[0])return M

Exercice 4 Générer les permutationsOn considère n ∈ N∗, on souhaite générer les n! permutations de [[0,n−1]].

33

On note σ(n) l’ensemble des permutation de [[0,n−1]] et on remarque que :

σ(n) =n−1⋃k=0

Sk union disjointe

où Sk est l’ensemble des permutation s de [[0,n−1]], vérifiant s(k) = n−1.De manière évidente, Sk est en bijection avec σ(n−1), puisque pour construire une permutation de Sk, il faut placer

les n−1 éléments de [[0,n−2]] dans les n−1 places différentes de k.Autrement dit, chaque permutation s de σ(n−1) donne n permutations de σ(n) : la première avec n−1 en première

place, la deuxième avec n−1 en deuxième place, etc.Écrire un algorithme récursif permettant de générer toutes les permutations en exploitant ce principe.

R On a retrouvé la formule : n! = n× (n−1)!.

from pprint import pprint2

def permutationRec (n):4 """

entrée: n = int6 sortie : L = list = liste des n! permutations de

[|0,n -1|]8 """

if n == 1 :10 return [[0]]

12 L = []for i in range(n-1, -1, -1) :

14 for permut in permutationRec (n -1) :# on insère n-1 en position i

16 permut . insert (i, n -1)L. append ( permut )

18 return L

20 n = 3L = permutationRec (n)

22 print("les ",len(L)," permutations pour n=",n)pprint (L)

Exercice 5 Soit n un entier naturel non nul, une combinaison de l’entier n est une liste (n1, . . . ,np) d’entiers supérieursou égaux à 1 dont la somme fait n, i.e. telle que n = n1 +n2 + · · ·+np.

Une combinaison étant une liste, l’ordre y a de l’importance. Ainsi, la combinaison (2,1), i.e. la décomposition3 = 2+1 diffère de la combinaison (1,2), i.e. 3 = 1+2.

Le but de cet exercice est de générer toutes les combinaisons d’un entier n.Une combinaison sera représentée sous forme de liste et donc l’ensemble des combinaisons sous forme de liste de

listes.Pour n = 1, la seule combinaison est (1), l’ensemble des combinaisons est donc

(1)

, ce qui s’écrit en Python [[1]].

Pour n = 2, les combinaisons sont (2) et (1,1) , ce qui s’écrit :(2),(1,1)

, ou en Python : [[2], [1,1]].

On remarque que l’on peut générer toutes les combinaisons de n de la manière suivante :• Si n = 1 la seule combinaison est [[1]]• Si n > 1, l’une des combinaisons est simplement n, et les autres sont obtenus à partir d’un entier i ∈ [[1,n−1]] : on

génère toutes les combinaisons de i et on ajoute n− i à la fin pour obtenir une combinaison de n.On obtient ainsi toutes les combinaisons de n à l’aide d’un algorithme récursif.

Programmer cet algorithme.Pour vérifier :• Les combinaisons de 3 sont : [[3], [2,1], [1,2], [1,1,1]].

34

• Les combinaisons de 4 sont : [[4], [3,1], [2,2] [1,3], [2,1,1], [1,2,1], [1,1,2], [1,1,1,1] ].• Les combinaisons de 5 sont :

[[5] , [4, 1], [3, 2], [3, 1, 1], [2, 3], [2, 2, 1], [2, 1, 2], [2, 1, 1, 1],2 [1, 4], [1, 3, 1], [1, 2, 2], [1, 2, 1, 1], [1, 1, 3], [1, 1, 2, 1],

[1, 1, 1, 2], [1, 1, 1, 1, 1]]

Correction :

1 # -*- coding : utf -8 -*-"""

3 géné ration des composition d’un entier n:une composition est une liste n1 , ... np telle que:

5 n1+n2+n3+ ... + np = n

7 Le principe est le suivant :les combinaisons de n sont obtenues à partir des combinaisons de n-k

9 pour k dans [|1, n -1|] en ajoutant k à la fin"""

11

13 # Modules et fonctions import és# ##############################

15 from pprint import pprint # pour pouvoir bien afficher des listes .

17 # Fonctions# ##########

19 def compositionRec (n):"""

21 entrée: n entier = l’entier que l’on cherche à dé composersortie : listeComposition = liste de listes d’entiers = la liste des dé composition

23 renvoie la liste des composition de n"""

25 if n == 1 :return [ [1] ]

27 listeComposition = [[n]]for i in range (1,n) :

29 for compo in compositionRec (i):listeComposition . append (compo + [n-i])

31 return listeComposition

33

n=535 print("la liste des composition pour n=",n)

pprint ( compositionRec (n) )

35

Algorithme de tri par sélectionTri par insertionTri fusionTri rapideComparatif des algorithmes de trisRecherche de la médianeExercicesSimulation de variables aléatoires et de ti-rages

3 — Algorithmes de tris

Dans ce chapitre, on étudie un problème important en informatique : trier leséléments d’une liste L.

On va étudier et comparer plusieurs algorithmes permettant de réaliser cettetâche.

L’étude de ces algorithmes va permettre de revoir plusieurs grandes idées del’algorithmique vus en première année (complexité, invariants de boucles preuve dela correction). Mais le tri n’est pas qu’un problème académique : en pratique, unordinateur passe en moyenne un tiers de son temps à trier.

On va noter n la taille de la liste, on a donc : L = [L0, . . . ,Ln−1]. On mesure lacomplexité en nombre de comparaisons, c’est-à-dire le nombre de test du typeL[i] < L[j] que l’on fait. On considère ainsi que l’échange de deux éléments dans laliste et que l’accès à l’élément i est immédiat,

Au niveau de la complexité en mémoire, on parle de tri sur place, lorsque la listeL est triée sans utiliser d’espace supplémentaire : l’algorithme ne requiert qu’un espaceen mémoire constant pour quelques variables.

Pour chaque algorithme, il faut savoir les appliquer sur un exemple, savoir lesprogrammer et comprendre leur étude théorique (complexité et preuve de correction).

R Par convention, on classe la liste par ordre croissant.

Dans le cours on suppose que l’on trie des réels. En pratique, on trie des élémentsd’un type quelconque sur lequel est défini un ordre total.

Le choix de ne compter que les comparaisons est contestable : il correspond aucas de données faciles d’accès (pour lecture et écriture) en mémoire. Si ce n’estpas le cas la performance des algorithmes est différente.

38 Algorithmes de tris

O Méthode sortPour une liste L, on dispose de la méthode sort qui permet de trier la liste (sur

place) et de la fonction sorted qui crée une copie triée de la liste.On peut choisir de trier par ordre décroissant, ou d’indiquer une méthode de tri : La

syntaxe est : L.sort(key=None, reverse=False). L’argument optionnel key est unefonction qui prends un élément de la liste x et qui est appliquée sur chaque élémentavant de faire des comparaison. C’est ainsi la fonction qui indique le critère de tri.L’argument optionnel reverse indique si il faut trier par ordre croissant ou décroissant.

La fonction sorted a la même syntaxe :sorted(iterable, key=None, reverse=False).

Exemple .1 Pour trier une liste de 3-uplets (i, j,k) en fonction de la troisièmecomposante par ordre décroissant, on fait :

L.sort(key = lambda x: x[2], reverse =True)

I Algorithme de tri par sélectionO Principe de l’algorithme

Le tri par sélection consiste à :• chercher l’élément minimum de la liste L, noté L j

• le déplacer en première place, en échangeant l’élément 0 et l’élément j,• recommencer sur les éléments [L1, . . . ,Ln]

On rappelle que pour chercher un minimum :• on considère que le minimum est atteint à la première position,• on conserve sa valeur (ou sa position) dans une variable.• Puis on balaie les éléments suivants,• et on met à jour le minimum selon la valeur lue.Ici, on va utiliser une variable i ∈ [[0,n−2]], en considérant qu’à l’itération i, les

éléments de [[0, i−1]] sont triés. On cherche donc le minimum parmi les éléments de[[i,n−1]].

O RéalisationVoici un exemple d’algorithme de tri par sélection :

1 def tri_selection (L):n = len(L)

3 for i in range(n -1) :# recherche du min dans L[i:n]

5 indMin = ifor j in range(i+1, n):

7 if L[j] < L[ indMin ] :indMin = j

9

# on place le minimum en position i11 L[ indMin ], L[i] = L[i], L[ indMin ]


O Preuve de la correction

Proposition I.1 Un invariant de boucle est :

P(i) : À la fin de la boucle indéxée par i (ie ligne 11), on a :

L0 6 L1 6 · · ·6 Li 6min(Li+1, . . . ,Ln−1) .

Autrement dit, les i premiers éléments sont bien placés et donc à la dernièreitération tous les éléments sont bien placés.

Ainsi, lorsque i = n−2, la liste est triée.

Démonstration. C’est une démonstration par récurrence sur i. En notant :

P(i) : L0 6 L1 6 · · ·6 Li 6min(Li+1, . . . ,Ln−1)

P(0) est dû à la preuve de la recherche du minimum.Si on considère un i fixé, tel que P(i) est vrai, alors l’algorithme de recherche de

minimum assure que P(i+1) est vrai au passage suivant.

O Étude de la complexité

Proposition I.2 La complexité en nombre de comparaison de l’algorithme de tri

est : C(n) =n(n−1)

2∼

n→+∞

n2

2.

Démonstration. Pour l’étape i ∈ [[0,n−1]], il y a n− i−1 comparaisons.Ainsi,

C(n) =n−1

∑i=0

(n− i−1) =n−1

∑i=0

i =n(n−1)

2.

O Application sur un exemple

Exercice 1 Soit la liste L = [13,1,5,6,2,6,7,4,3], décrire les étapes de l’algorithmede tri sur cette liste.

II Tri par insertionO Principe de l’algorithme

Le tri par insertion consiste à exploiter le fait qu’il est facile de placer un élémentdans une liste déjà triée.

On va donc trier progressivement la liste : le début de la liste est déjà trié et oninsère un nouvel élément à la bonne place parmi les premiers.

On procède alors ainsi :• le premier élément est trié (puisqu’il est seul).• On insère le deuxième élément avant ou après le premier, les deux premiers

éléments sons alors triés.


• On insère les troisième élément à la bonne place par rapport aux deux premiers,les trois premiers éléments sont alors triés,• on insère le quatrième à la bonne place par rapport au trois premiers éléments,

etc.

Ainsi, à l’étape i ∈ [[1,n−1]], les i−1 premiers éléments sont triés et on insère lei-ème éléments à la bonne place par rapport aux i−1 premiers.

O RéalisationPour chercher la place de l’élément i dans les i−1 premiers, on utilise une boucle

while comme pour la recherche d’un élément a nul dans une liste :• on place la tête de lecture sur le premier élément,• tant que ce que l’on lit existe et est inférieur à l’élément à insérer on déplace la

tête de lecture vers la droite.On peut aussi partir du dernier élément et déplacer la tête de lecture vers la gauche.Cette recherche peut être écrite dans une fonction externe pour plus de lisibilité ducode.

Pour insérer, on a deux choix :• insérer un nouvel élément L[i] à la bonne place, puis supprimer l’ancien élément

(qui est ensuite à la place i+1)• ou alors en cours d’itération, tant que la tête de lecture lit un élément supérieur à

l’élément L[i], on déplace cet élément vers la droite.Voici une première version de cet algorithme de tri.La fonction place qui détermine la place d’un élément dans une liste triée :

1 def place(Lt , elmt ):"""

3 entrée:elmt = float

5 = l’élément à insérerLt = liste triée par ordre croissant

7 = liste dans laquelle mettre elmtsortie :

9 j = int= bonne position de elmt dans Lt

11 """n = len(Lt)

13 j = 0while j<n and Lt[j] < elmt :

15 j += 1return j

La fonction tri qui appelle la fonction place plusieurs fois :

def tri_insertion1 (L) :2 """

entrée: L = liste4 = liste à trier

sortie : L triée6 la liste L est modifi ée sur place

"""8 n = len(L)


for i in range (1,n) :10 # les éléments L[0] ... L[i -1] sont triés

j = place(L[:i], L[i])12 # dé placement de L[i] en position j

L. insert (j, L[i]); del L[i+1]

. Ici on a utilisé les instructions L.insert(L[i],j); del L[i+1] pour insérer unnouvel élément L[i] en position j puis effacer l’ancien élément L[i] (qui setrouve donc en position L[i+1]).On peut aussi utiliser la syntaxe suivante :

elmt = L.pop(i) # "dépile" l’élément iL. insert (elmt , j) # le place au bon endroit

On peut aussi écrire une autre version de cet algorithme (on le trouve souvent souscette forme dans la littérature) :

def tri_insertion2 (L):2 n = len(L)

for i in range (1,n):4 elmt = L[i]

j = i6 # tête de lecture en position j-1

while j>0 and L[j -1] > elmt :8 # on déplace la tête de lecture et l’élément à placer

# vers la gauche10 L[j] = L[j -1]

j = j-112 L[j] = elmt

. Ici on choisit de chercher la position de l’élément L[i] depuis la droite (puisqu’onplace la tête de lecture sur le dernier élément trié). À chaque fois que l’on déplacela tête de lecture de j−1 à j−2, on déplace l’élément L[ j−1] en position j (ievers la droite).

R La manière dont Python stocke les listes fait que cet algorithme est plus rapideparce qu’il fait moins de déplacement dans la mémoire.

O Preuve de la correctionPour prouver la correction de cet algorithme :

Proposition II.1 Un invariant de boucle est :

P(i) : À la fin de la boucle indéxée par i (ie ligne 13 dans la version 1 et ligne 12dans la version 2) on a :

L0 6 L1 6 · · ·6 Li

Autrement dit les i premiers éléments de la liste sont triés.

Démonstration. Par récurrence sur i.


O ComplexitéOn étudie la complexité dans le meilleur et dans le pire des cas pour la version

2.

Proposition II.2 Dans le pire des cas, la complexité de l’algorithme de tri parinsertion est :

C(n) =n(n−1)

2∼

n→+∞

n2

2

Dans le meilleur des cas, la complexité de l’algorithme de tri par insertion est :

C(n) = n−1 ∼n→+∞

n

Démonstration. Dans le pire des cas, à l’itération i, la variable j va varier de i à 1, il vadonc y avoir i test. Ce qui donne :

C(n) =n−1

∑i=1

i =n(n−1)

2.

Dans le meilleur des cas, à l’itération i, la variable j ne va pas varier (un seul testest effectué). Ce qui donne :

C(n) =n−1

∑i=1

1 = n−1.

R Le pire des cas est obtenu quand la liste est triée par ordre décroissant. Lemeilleur des cas est obtenu quand la liste est déjà triée par ordre croissant.

O Tri par insertion dichotomiqueEn fait le tri par insertion peut être grandement améliorer en cherchant la position j

de l’élément i dans les i−1 premiers éléments déjà triés en utilisant la dichotomie.

Exercice 2 Écrire la fonction place correspondante. Calculer la complexité.

O Application sur un exemple


III Tri fusionO Principe de l’algorithme

III Tri fusion 43

Le tri fusion consiste à appliquer une méthode itérative pour trier : on découpe laliste au milieu et on trie chaque partie.

Ensuite, on fusionne les deux listes obtenues par une méthode récursive quifusionne deux listes triées en un nombre linéaire de comparaison.

Autrement dit, étant donné une liste de taille n, on applique le tri sur les sous-listesL[: n//2] et L[n//2:]. On renvoie les deux listes fusionnées. Si la liste est vide ou necontient qu’un élément on la retourne inchangée.

Pour fusionner deux listes L1 et L2, on utilise encore la récursivité :• Si l’un des listes est vide, on renvoie l’autre,• sinon on compare les deux premiers éléments : si L1[0]< L2[0], on rappelle

la fonction sur les listes L1[1:] et L2 en mettant L1[0] au début sinon c’estl’inverse.

O RéalisationOn écrit donc en premier la fonction qui fusionne deux listes :

def fusion (L1 , L2):2 if L1 == [] :

return L24 elif L2 == [] :

return L16 elif L1 [0] < L2 [0] :

return [ L1 [0] ] + fusion (L1 [1:] , L2)8 else :

return [ L2 [0] ] + fusion (L1 , L2 [1:])

Puis la fonction tri :

1 def tri(L) :n = len(L)

3 if n <=1 :return L

5 m = n//2 # point milieuL[:m] = tri( L[:m] )

7 L[m:] = tri( L[m:] )L[:] = fusion (L[:m], L[m:] )

9 return L


Proposition III.1 La fonction fusion appliquée à deux liste L1 et L2 renvoie bienla bonne valeur. De plus le nombre d’appel est inférieur à la plus grande longueurdes deux listes.

La fonction tri appliquée à une liste L renvoie bien la bonne valeur.

Démonstration. On commence par la fonction fusion par une démonstration parrécurrence :

P(n) appliquée à deux liste L1 et L2 telle que len(L1) + len(L2)= n, la fonctionfusion donne le bon résultat.


Pour n = 0 c’est évident,Soit n fixé tel que P(n) est vrai, on considère deux listes L1 et L2 telle que

len(L1) + len(L2)= n+1,En faisant une disjonction des cas L1[0]<L2[0] (ou l’inverse), on se ramène appeler

la fonction sur deux listes dont la somme des longueur est égale à n.On obtient ainsi le résultat et donc : la fonction fusion donne toujours le bon

résultat.Pour la fonction tri, c’est la même démarche :

P(n) appliquée sur une liste L de longueur inférieure ou égale à n, la fonction tridonne le bon résultat.

on voit que c’est une récurrence forte : pour n ∈ N, on se ramène aux rangs⌊n

2

⌋et⌊n

2

⌋+1.

O Complexité

Proposition III.2 On a les compléxité suivantes (en nombre de comparaisons) pourl’algorithme de fusion :• Dans le pire des cas : len(L1)+len(L2) comparaisons.• Dans le meilleur des cas : min(len(L1),len(L2)) comparaisons.

Démonstration. À chaque appel, la taille d’une des listes est diminuée de 1, jusqu’àque l’un des liste soit vide. Ainsi, le nombre d’appel A vérifie :

min(len(L1),len(L2))6 A6 len(L1)+len(L2).

Chaque appel nécessite une comparaison, d’où la complexité.

Le meilleur des cas arrive lorsque on enlève systématiquement des éléments à la mêmeliste, cela corresponds à dire que tous les éléments de L1 sont inférieurs aux élémentsde L2.

Le pire des cas arrive lorsque on enlève tous les éléments des deux listes. Celacorresponds au cas où les deux listes sont équilibrées .

Proposition III.3 La complexité C(n) de l’algorithme de tri fusion vérifie C(n) =O(n log2(n)), dans le meilleur et dans le pire des cas.

Démonstration. On traite le pire des cas.La complexité de la fonction tri sur une liste de longueur n vérifie :

C(n) = 2×C(n

2

)+n

Puisqu’on fusionne deux listes dont la somme des longueurs fait n.Ainsi, on a :

C(

2k)= 2C(2k−1)+2k

III Tri fusion 45

On écrit rapidement :

C(

2k)=2C(2k−1)+2k Lk

C(

2k−1)=2C(2k−2)+2k−1 Lk−1

C(

2k−2)=2C(2k−3)+2k−2 Lk−2

... =... +

...

C(2) =2C(1)+2 L1

C(1) =0 L0

En faisant

Lk +2Lk−1 +4Lk−2 + · · ·+2kL0

On obtient :

C(

2k)=2k +2k + · · ·+2k = k2k.

Ainsi, si n s’écrit sous la forme : n = 2k, on a :

C (n) = n log2(n)

On souhaite généraliser cette formule à un n ∈ N.On note alors k ∈ N l’entier tel que 2k 6 n < 2k+1. On sait alors que k = blog2(n)cOn utilise alors la croissance de la fonction complexité, qui donne :

on a : 2k 6n < 2k+1

donc C(

2k)6C(n)<C

(2k+1

)ce qui donne : k2k 6C(n)< (k+1)2k+1

en remplaçant :blog2(n)cn6C(n)< (blog2(n)c+1)(2n)

(log2(n)−1)n6C(n)< 2(log2(n)+2)n

D’où C(n) = O(n log2(n)).Dans le meilleur des cas, la complexité de la fonction tri sur une liste de longueur

n vérifie :

C(n) = 2×C(n

2

)+

n2

Puisqu’on fusionne deux liste de longueur n2 . En reprenant le calcul, on obtient de

même : C(n) = O(n log2(n)).

R L’écart entre le meilleur et le pire des cas est simplement un facteur 2.


. Ici, le calcul de la complexité a été très détaillé. En pratique, on peut se contenterd’indiquer comme résultat de complexité : si n s’écrit sous la forme : n = 2k,alors C (n) = n log2(n). Il n’est pas nécessaire de détailler la généralisation à toutn ∈ N. La technique pour généraliser ici est très classique, mais n’est nécessaireque si elle est explicitement demandée.

Proposition III.4 Le tri par fusion n’est pas un tri sur place : il est nécessaire destocker une liste auxiliaire de la même taille que L.

Démonstration. Cela se voit par l’utilisation de l’instruction :L[:] = fusion(L[:m], L[m:] ) qui crée une nouvelle liste de la même taille queL.

O Test sur un exemple


IV Tri rapideO Principe de l’algorithme

Le tri rapide (quicksort) consiste à utiliser un processus récursif :• choisir un élément x comme pivot (généralement le dernier, on peut aussi le

choisir au hasard),• cet élément va permettre de partitionner la liste L en deux parties. On va

déplacer les éléments de L pour que :– les k premiers éléments L[0] ... L[k-1] soient inférieurs à x,– le pivot x soit en position k (donc bien placé),– les éléments suivants L[k+1] ... L[n-1] soient supérieurs à x

• On trie alors récursivement la partie gauche (les k premiers éléments) et lapartie droite (les suivants).

R On ne choisit pas l’entier k, il dépends du pivot. Les deux parties ne sont pasnécessairement de la même taille.

À la deuxième itération, on répète sur les éléments d’indices dans [[0,k−1]], puissur une autre partie de la liste. D’où l’idée d’écrire une fonction qui prends enentrée deux indices p et r et partitionne les éléments d’indices dans [[p,r]].

O RéalisationOn découpe le code ainsi :• Une fonction partition prends en entrée la liste L et deux entiers p et r. Cette

fonction partitionne les éléments d’indices dans [[p,r]] en choisissant l’élément r(ie le dernier) comme pivot. Elle renvoie la position du pivot.• une fonction tri_rapide_rec prends en entrée la liste L et deux entiers p et r.

Si q < r, cette fonction applique la partition des éléments d’indice [[p,r]], puis serappelle sur chacune des parties. Cette fonction est donc récursive.

IV Tri rapide 47

• le fonction principe tri appelle la fonction tri_rapide_rec sur tous les élé-ments.

Pour la fonction partition, on note k la position du pivot, telle que les éléments[[p,k−1]] sont inférieurs au pivot et les éléments [[k+1, p]] sont supérieurs. On procèdealors ainsi :• à l’initialisation, on considère que tous les éléments sont inférieurs au pivot, i.e.

que k = p.• Quand on lit un élément supérieur au pivot, on échange, l’ancienne position du

pivot avec cet élément, et on déplace cette position du pivot.• À la fin, on déplace le pivot à sa place k.

def partition (L ,p , r) :2 """

entrée: L = list = liste à trier4 p,r = deux entiers

= on partitionne les éléments de [|p,r|]6 sortie : k = entier = position du pivot

modification de la liste L8

Cette fonction partitionne la liste L10 entre les éléments p et r ( inclus )

en prenant comme pivot le dernier élément12 """

pivot = L[r] # choix du pivot14

k = p # position courante du pivot16 # les éléments d’indices > k sont supé rieurs à pivot

18 for j in range(p,r) : # élément luif L[j] <= pivot :

20 # L[j] est déplacé dans la partie gaucheL[k], L[j] = L[j], L[k]

22 k += 1 # on déplace la position du pivot

24 #on met le pivot à la bonne placeL[k], L[r] = L[r], L[k]

26 return k

La fonction récursive tri_rapide_rec vérifie que p < r, puis partitionne et enfins’appelle elle-même deux fois.

def tri_rapide_rec (L, p , r):2 """

entrée: L = list = liste à trier4 p,r = deux entiers

= on trie les éléments de [|p,r|]6 sortie : modification de L

Cette fonction ré cursive trie la liste L8 entre les éléments p et r ( inclus )

"""10 if p<r :

k = partition (L, p, r)12 tri_rapide_rec (L, p, k -1)


tri_rapide_rec (L, k+1, r)

Enfin, la fonction tri consiste en un simple appel à la fonction tri_rapide_recsur tous les éléments.

def tri(L):2 tri_rapide_rec (L, 0, len(L)-1)


Proposition IV.1 Pour la fonction partition, on a l’invariant de boucle suivant :

P( j) : à la fin de la boucle sur j (i.e. ligne 22), on a :

∀l ∈ [[p,k−1]] , L[l]6 pivot

et ∀l ∈ [[k, j]] , L[l]> pivot

Ainsi, à la fin de l’algorithme, on a :

∀l ∈ [[p,k−1]] , L[l]6 L[k]

et ∀l ∈ [[k+1,r]] , L[l]> L[k]

Ainsi, l’élément L[k] est bien placé parmi les éléments d’indices [[p,r]].

Démonstration. Comme souvent la propriété se démontre par récurrence sur j ∈[[p,r−1]].

Avant de rentrer dans la boucle, on a : k = p et j = p.Si L[p]>pivot, on a toujours à la fin de la boucle k = p et j = p, donc :

∀l ∈ [[p,k−1]] , L[l]6 pivot car [[p,k−1]] est vide

et ∀l ∈ [[k, j]] , L[l]> pivot car [[k, j]] ne contient que p et L[p]> pivot

Si maintenant L[p]<=pivot, l’instruction L[k], L[j] = L[j], L[k] ne modifiepas la liste et à la fin de la boucle, on a : k = p+1 et j = p. On obtient :

∀l ∈ [[p,k−1]] , L[l]6 pivot car [[p,k−1]] ne contient que p et L[p]6 pivot

et ∀l ∈ [[k, j]] , L[l]> pivot car [[k, j]] est vide

Ainsi, par disjonction des cas, on voit que la propriété est vraie à la fin du premierpassage (i.e. ligne 22 pour j = p).

Considérons maintenant un j fixé, tel que P( j) est vraie. Avant de rentrer dans laboucle, on a donc :

∀l ∈ [[p,k−1]] , L[l]6 pivot

et ∀l ∈ [[k, j]] , L[l]> pivot

On utilise de même une disjonction des cas pour voir comment ces relations évoluelors de la boucle j+1.

IV Tri rapide 49

Si L[j+1]>pivot, la valeur de k n’est pas modifié. On obtient donc :

∀l ∈ [[p,k−1]] , L[l]6 pivot comme précédement

et ∀l ∈ [[k, j+1]] , L[l]> pivot en ajoutant L[j+1]

On a donc la relation au rang j+1 dans ce cas.Si L[j+1]<=pivot, on effectue l’instruction L[k], L[j+1] = L[j+1], L[k]. Après

cette instruction, l’élément L[k] (ancien élément L[j+1]) vérifie L[k]<=pivot, tandisque l’élément L[j+1] (ancien élément L[k]) vérifie L[j+1]> pivot. Ensuite, on effec-tue l’opération k += 1, ce qui assure la relation au rang j+1 :

∀l ∈ [[p,k−1]] , L[l]6 pivot

et ∀l ∈ [[k, j+1]] , L[l]> pivot.

Dans les deux cas, on a la propriété au rang j+1 et donc l’hérédité.Au final, pour j = r−1, on obtient :

∀l ∈ [[p,k−1]] , L[l]6 pivot

et ∀l ∈ [[k,r−1]] , L[l]> pivot.

Après échange des éléments L[k] et L[r], on obtient :

∀l ∈ [[p,k−1]] , L[l]6 L[k]

et ∀l ∈ [[k+1,r]] , L[l]> L[k].

Il reste à passer à la fonction récursive :

Proposition IV.2 La fonction tri_rapide_rec se termine et permet de trier leséléments de L d’indices dans [[p,r]].

Démonstration. Il faut utiliser une récurrence forte sur l = r− p :

P(l) si r− p = l, la fonction tri_rapide_rec se termine et permet de trier leséléments de L d’indices dans [[p,r]].

Pour l = 0 c’est évident, puisque si p− r = 0, la fonction se termine.Considérons l fixé, tel que ∀k 6 l, P(k) est vraie. Cherchons à démontrer P(l +

1).Comme on l’a vu, la fonction partition permet de placer correctement l’élément k.

D’après les hypothèses de récurrence, les appels récursif à la fonction tri_rapide_recse terminent et assurent que :• les éléments d’indices [[p,k−1]] sont bien triés (entre eux),• les éléments d’indices [[k+1,r]] sont bien triés (entre eux),

Comme, on sait que l’élément k est bien placé, on obtient que les éléments d’indices[[p,r]] sont bien triés.

D’où l’hérédité.En conclusion, quelque soit l’écart r− p, la fonction tri_rapide_rec se termine et

permet de trier les éléments d’indices [[p,r]].

La terminaison et la correction de la fonction tri est alors assurée.


O Complexité

Proposition IV.3 Dans le pire des cas, la complexité de l’algorithme de tri rapideest C(n) = O(n2).

Dans le meilleur des cas, la complexité de l’algorithme de tri rapide est C(n) =O(n log2(n)).

Démonstration. On peut déjà remarque que la fonction partition demande r− pcomparaisons (une pour chaque valeur de j).

Dans la pire des cas, la partition des éléments d’indices [[p,r]] est très déséquilibré :la position finale du pivot est systématiquement à une extrémité.

On obtient alors : C(n) =C(n−1)+n−1, car il faut n−1 comparaison pour fairela partition, puis il faut appeler la fonction tri_rapide_rec sur une liste de longueurn−1.

On a donc :

C(n) = n+n−1+ · · ·+1 =n(n−1)

2= O(n2).

Dans le meilleur des cas, la partition des éléments d’indices [[p,r]] est équilibré : laposition finale du pivot est systématiquement au milieu. Ainsi : C(n) = 2C

(n2

)+n−1,

car il faut n− 1 comparaison pour faire la partition puis il faut appeler la fonctiontri_rapide_rec sur deux listes de longueur n

2 .En utilisant le même type de technique que précédement, on en déduit : C(n) =

O(n log2(n)).

R Le pire des cas est obtenu si la liste est déjà triée ou si elle est triée dans lemauvais sens.

. Malgré son nom, le tri rapide est donc théoriquement un tri plutôt lent : dans lepire des cas, sa complexité est quadratique, donc plutôt mauvaise.On voit ici que ce qui est intéressant est en fait la complexité en moyenne,qui se calcule en mettant un modèle probabiliste sur les valeurs de la liste.Généralement, on considère que la liste contient une permutation aléatoire desentiers [[1,n]]. Par un calcul de probabilité, on en déduit alors, l’espérance dunombre de comparaisons nécessaires pour trier la liste. Cette notion est hors-programme. Les calculs mathématiques nécessaires pour obtenir la complexiténe sont pas simples.On admettra qu’en moyenne, le tri à bulle a une complexité en O(n log2(n)).En pratique, on choisit le pivot aléatoirement pour éviter de se retrouver dans lepire des cas.

V Comparatif des algorithmes de tris

Voici un bilan des différents algorithmes de tris que l’on a étudié :


nom complexité complexité complexité sur place stablepire des cas meilleur cas moyenne

Sélection O(n2) O(n2) O(n2) Oui Non

Insertion O(n2) O(n) O(n2) Oui Oui

Fusion O(n log2(n)) O(n log2(n)) O(n log2(n)) Non Oui

Quicksort O(n2) O(n log2(n)) O(n log2(n)) Oui Non

TABLE 3.1 – Comparatif des algorithmes de tris

Voici ce que l’on peut déduire de ce tableau :• Les tris par sélection est plutôt lent. Attention : c’est celui qui fait le moins

d’échange dans la liste, il a donc un intérêt lorsque l’opération qui prends dutemps est l’échange dans la liste.

• Le tri par insertion est le meilleur dans le cas le plus favorable. Il est donc àréserver au cas où la liste est presque déjà triée.

• Le tri fusion est le plus rapide dans tous les cas. Son principal défaut est qu’ildemande beaucoup de place en mémoire.

• Le tri rapide est très rapide dans le cas moyen mais lent dans des cas particulier.C’est souvent le tri par défaut, mais il faut l’éviter si le pire des cas peut seproduire.

VI Recherche de la médianeLa médiane d’une liste de nombre L = [L[0], ... ,L[n-1]] contenant unnombre impair d’éléments est défini comme l’élément x de la liste tel que :

Cardi ∈ [[0,n−1]] |L[i]< x=⌊n

2

⌋et donc Cardi ∈ [[0,n−1]] |L[i]> x=

⌊n2

⌋Autrement dit, il y a autant d’éléments inférieurs à x que supérieur à x dans la liste.

La médiane peut s’obtenir en triant la liste, puis en choisissant l’élément d’indice :⌊n2

⌋(en partant de 0, donc le

⌊n2

⌋+1-ième élément ).

Lorsque la liste est constituée d’un nombre pair d’élément, la médiane estobtenue en triant la liste par ordre croissant, puis en considérant la moyenne desdeux éléments centraux :

12

(L⌊n

2−1⌋+L⌊n

2

⌋)

R La médiane est une mesure statistique permettant de donner une informationde position sur une série statistique. C’est-à-dire qu’elle indique une mesurereprésentative de la série (comme la moyenne).

Elle est plus robuste aux erreurs que la moyenne, car si on ajoute une très fortevaleur à la série, on modifie beaucoup la moyenne mais très peu la médiane.


Plus généralement, étant donné une liste L, on souhaite chercher le k-ième élémentdans l’ordre croissant. Autrement dit, on cherche l’élément j ∈ L tel que :

k−1 = Card(x ∈ L|x < j)

Bien entendu, on peut trier la liste entièrement puis prendre le k-ième élément. Oncherche à faire plus rapidement.

Remarquons déjà qu’on peut supposer k 6⌊n

2

⌋, si ce n’est pas le cas, il suffit de

classer la liste à l’envers , puis de prendre l’élément n− k. Le cas critique est ainsila recherche de la médiane.

On reprends les algorithmes de tri pour voir quelle méthode on peut adapter :tri par sélection Il suffit de s’arrêter une fois que l’on a classé k termes.tri par insertion On ne peut pas l’adapter facilement à la recherche du k-ième élément.tri fusion On ne peut pas l’adapter facilement à la recherche du k-ième élément.tri rapide s’adapte facilement : si le pivot est à la place k, on a terminé, sinon, on ne

trie que la partie intéressante.Voici une adaptation du tri par sélection à la recherche de l’élément pos dans l’ordrecroissant :

def mediane_selection (L, pos ):2 n = len(L)

for i in range(pos +1) :4 # recherche du min dans L[i:n]

indMin = i6 for j in range(i+1, n):

if L[j] < L[ indMin ] :8 indMin = j

10 # on place le minimum en position iL[ indMin ], L[i] = L[i], L[ indMin ]

12 return L[pos]

Voici une adaptation du tri rapide à la recherche de l’élément pos dans l’ordrecroissant :

def partition (L ,p , r) :2 """

entrée: L = list = liste dans laquelle chercher4 p,r = deux entiers

= on partitionne les éléments de [|p,r|]6 sortie : k = entier = position du pivot

modification de la liste L8

Cette fonction partitionne la liste L10 entre les éléments p et r ( inclus )

en prenant comme pivot le dernier élément12 """

pivot = L[r] # choix du pivot14

k = p # position courante du pivot16 # les éléments d’indices > k sont supé rieurs à pivot


18 for j in range(p,r) : # élément luif L[j] <= pivot :

20 # L[j] est déplacé dans la partie gaucheL[k], L[j] = L[j], L[k]

22 k += 1 # on déplace la position du pivot

24 #on met le pivot à la bonne placeL[k], L[r] = L[r], L[k]

26 return k

28 def mediane_rec (L, p , r, pos ):"""

30 entrée: L = list = liste dans laquelle chercherp,r = deux entiers

32 = on trie les éléments de [|p,r|]pos = position de l’é lement

34 recherch é dans la liste triée

36 Cette fonction recherche ré cursivement le pos -ième élémentdans la liste L une fois triée entre les éléments p et r ( inclus )

38 """# cas trivial

40 if p>= r :return L[pos]

42

k = partition (L, p, r)44 if k == pos :

return L[pos]46 elif k> pos:

return mediane_rec (L, p, k-1, pos)48 else :

return mediane_rec (L, k+1, r, pos)50

def mediane (L, pos ):52 """

entrée: L = list54 pos = position de l’é lement

recherch é dans la liste triée56 sortie : l’élément recherch é

"""58

n = len(L)60 return mediane_rec (L[:], 0, len(L)-1, pos)

Algorithmes de triPelletier Sylvain PC, Lycée Descartes

Exercice 1 Tri à bullesLe principe du tri à bulles est le suivant : on parcourt la liste en inversant tout couple non trié d’éléments consécutifs.Après un parcours de la liste, le plus grand élément se trouve en dernière position. On parcourt alors une deuxième

fois la liste, mais seulement jusqu’à l’avant dernier, et ainsi de suite.Le tableau est donc parcouru n−1 fois où n est la taille de la liste.

1. Sur le papier, proposer un exemple de tri à bulles.2. Implémenter en Python l’algorithme de tri à bulles. Tester soigneusement.3. Expliciter un invariant de boucle de cet algorithme.4. Déterminer la complexité de cet algorithme en nombre d’opérations. Pour cela, on commencera par tester sur le

programme pour afficher le nombre de comparaison, puis on démontrera sur le papier.5. Si au j-ième passage, aucune modification n’est nécessaire, c’est que la liste est entièrement triée. Modifier le

programme pour arrêter le programme dans ce cas.Avec cette nouvelle version, la complexité dépends de la liste. Déterminer la complexité dans le meilleur des cas. Àquelle situation corresponds ce meilleur des cas ?

Correction : Voici un exemple de programme :

1 def triBulles (L) :nbrComp = 0 # nbr de comparaison

3 n = len(L)for j in range(n -1) : # j = numéro du passage

5 modif = False # passe à True si chgtfor i in range(n-j -1) :

7 nbrComp += 1if L[i+1] < L[i] :

9 # deux éléments consé cutifs dans le mauvais ordreL[i], L[i+1] = L[i+1], L[i]

11 modif = Trueif not(modif) : # pas de chgt dernier passage

13 return Lreturn L

Un invariant de boucle est :

À la fin de la j-ième boucle : les j+1 derniers éléments sont bien placés, ie :

max(L[0], . . . ,L[n−2− j])6 L[n−1− j]6 · · ·6 L[n−1].

La complexité est

C(n) =n−2

∑j=0

(n− j−1) =n−1

∑j=1

j =n(n−1)

2.

Dans le meilleur des cas, on ne fait que n comparaisons : c’est le cas où la liste est déjà triée.

Exercice 2 Tri par dénombrements On souhaite trier une liste L qui contient plusieurs fois les mêmes éléments.La liste L contenir beaucoup d’éléments, mais peu d’éléments différents.Pour simplifier, on suppose qu’elle contient des éléments de [[0,M]], où M est le maximum.Le principe du tri par dénombrement d’une liste L est d’utiliser cette redondance, en créant une liste annexe nbrRepet

de longueur M+1, telle que :

∀i ∈ [[0,M]] , nbrRepet[i] = Card

j ∈ [[0,n−1]]∣∣∣L[j] = i

.

Une fois la liste annexe nbrRepet construite, on remplit la liste L en plaçant l’élément 0 nbrRepet[0] fois, puis 1

55

nbrRepet[1] fois, etc.Écrire une fonction qui tri une liste L par dénombrements.

Correction : On peut faire en deux fonctions :

def listeRepet (L):2 # calcul du maximum

M = L[0]4 for x in L :

if x> M :6 M = x

8 # remplissage de VnbrRepet = [0 for i in range(M+1)]

10 for x in L :nbrRepet [x] += 1

12 return nbrRepet

et

def tri(L):2 nbrRepet = listeRepet (L)

M = len( nbrRepet )-14

L = []6 for i, n in enumerate ( nbrRepet ) :

L. extend ([i]*n)8 return (L)

Exercice 3 Tri topologiqueOn considère un ensemble fini E sur lequel est défini un ordre partiel.C’est à dire une relation binaire 6 vérifiant :

∀(x,y,z) ∈ E3, x6 y et y6 z =⇒ x6 z

∀(x,y) ∈ E2, x6 y et y6 x =⇒ x = y

∀x ∈ E, x6 x

On représente cet ordre sous la forme d’un graphe en indiquant une flèche de x vers y si x6 y.Par exemple :

On cherche à réordonner les éléments de E sous la forme d’une liste (a0, . . .an−1) telle que :

∀i ∈ [[0,n−1]] ,ai < a j =⇒ i < j

56

Cela revient à modifier le graphique de manière à aligner les nombres et que toutes les flèches soient orientées de gauche àdroite.

Sur l’exemple :

Cet alignement n’est pas unique.Pour la structure de données, on représente le graphe par :• la liste des éléments du graphe (liste d’entiers). Sur l’exemple :

listeElmt = [1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9]

• la liste des arrêtes, sous la forme d’une liste de couple d’entiers (i, j) ∈ E2. Si (i, j) est présent dans cette liste, c’estqu’une flèche est dessinée entre i et j : Sur l’exemple :

arrete = [[1 ,3] , [3,7], [7,5], [7,4],[4,6], [5,8], [8,6], [2,8],[9,2], [9 ,5]]

Le résultat final sera une liste L contenant les éléments de E dans le bon ordre (de gauche à droite dans la listeréordonnée).

Sur l’exemple, on aura :

L = [1, 3, 7, 4, 9, 2, 5, 8, 6]

ou

L = [9, 2, 1, 3, 7, 5, 4, 8, 6]

Le principe du tri topologique est le suivant :• Pour chaque élément de E, déterminer son nombre de prédécesseur.• Trouver un élément qui n’a pas de prédécesseur. Il en existe nécessairement un car sinon il y a une boucle (ce qui

contredit la notion d’ordre). Cet élément est noté NSP.• Enlever NSP du graphe : il faut alors modifier la liste des arrêtes et la liste des éléments.• Retourner la valeur NSP (en premier) suivi du résultat obtenir en relançant récursivement l’algorithme sur ce

nouveau graphe. Jusqu’à obtenir un graphe sans éléments.Pour calculer le nombre de prédécesseur, on choisit ici d’utiliser un dictionnaire.Quelques rappels sur les dictionnaires :• C’est une liste de la forme clé:valeur. Dans notre cas, un dictionnaire pourra être :

8: 2, 9: 0, 2: 1, 5: 1, 6: 1

• On crée un dictionnaire avec des accolades. Dans notre cas, on fera comme une liste en compréhension :

nbrPre = elmt : 0 for elmt in listeElmt

Pour initialiser un dictionnaire qui à chaque élément de listeElmt associe la valeur 0.• On accède à une valeur avec nbrPre[elmt].• On peut boucler sur les clés d’un dictionnaire : for elmt in nbrPre : sur l’exemple ci-dessus, elmt prendra les

valeurs 8,9,2,5,6.Interprétation : si E est un ensemble de tâches, la relation 6 signifie : telle tâche doit être faite avant une autre. Le tri

topologique permet alors d’ordonner les tâches, pour les réaliser une par une. C’est une opération réalisé très souvent parun ordinateur.

Correction : Voici un exemple de code :

def topologicalSort (arrete , listeElmt ):2 """

57

entrée: arrete = liste de couple de int [i,j]4 = liste des liaisons i -> j

listeElmt = liste = liste des éléments de E.6 sortie : L = liste

= liste des éléments de E triée dans le bon ordre.8 """

# cas de sortie : le graphe est vide.10 if listeElmt == [] :

return []12

# étape 1: remplir le dictionnaire du nombre de prédé cesseur14 nbrPre = elmt : 0 for elmt in listeElmt

# nbrPre [i] = nbr de prédé cesseur de i+1 ou ABSENT16 for i,j in arrete :

nbrPre [j] += 118 print( nbrPre )

20

# on recherche ensuite un noeud i present et sans prédé cesseur22 # c’est une simple recherche d’un élément nul dans une liste

for elmt in nbrPre :24 if nbrPre [elmt] == 0 :

iNSP = elmt26 NSPTrouve = True

break28 if not( NSPTrouve ):

print(" erreur graphe cyclique ")30 return []

print("é lement sans prédé cesseur :" + str(iNSP ))32

# on enlève iNSP de la liste des arrêtes et des éléments:34 listeElmt . remove (iNSP)

arrete = [ [i,j] for i,j in arrete if i != iNSP and j != iNSP ]36 # sans liste en compré hension :

# newArrete = []38 # for i,j in arrete :

# if i != iNSP and j != iNSP :40 # newArrete . append ([i,j])

# arrete = newArrete42

44 # on rapelle ré cursivement la fonction sur les nouvelles arrêtes:return [iNSP] + topologialSort (arrete , listeElmt )

R On peut optimiser différemment le code. En particulier, plutôt que de recalculer le nombre de prédecesseur à chaqueappel, on peut procéder plus rapidement.

Exercice 4 Le but de cet exercice est de proposer un algorithme de tri d’une liste dans le cas où l’on ne s’autorise quecertaines modifications sur la liste.

Dans cet exercice, on interprète la liste comme une pile de crêpes : la seule opération possible est d’insérer la spatule à une position donnée et de retourner tous les éléments situés au dessus (ie après dans la liste).

Par exemple, si la liste est :

L = [1, 4, 5, 3, 2, 5, 6, 2, 1, 5, 2, 6, 4, 2, 5, 8, 9]# interpr é tation : fond de la pile <---> sommet de la pile

et que l’on choisit la position i = 10, on obtient :

[1, 4, 5, 3, 2, 5, 6, 2, 1, 5, 9, 8, 5, 2, 4, 6, 2]

C’est la seule opération possible.

58

L’algorithme est alors le suivant :• On place la spatule sous l’élément le plus grand,• on retourne ce qui est au dessus (ie après). L’élément le plus grand passe en dernier.• on place la spatule sous toute la liste, et on retourne donc toute la liste. Le plus grand élément est alors bien situé (en

premier).• On applique alors récursivement le procédé au reste de la liste.

On obtient ainsi un tri de la liste par ordre décroissant.1. Tester à la main sur un exemple,2. Implémenter la méthode, on utilisera la méthode reverse pour inverser une liste.

Correction : On peut par exemple faire :

1 def triCrepier (L):"""

3 entrée: L = list de float= liste à trier

5 sortie : L = liste triée"""

7 n = len(L)if n <= 1 :

9 return L# recherche de l’indice du max

11 maxi = L[0]imax = 0

13 for i,x in enumerate (L) :if x > maxi :

15 imax = imaxi = x

17 # retournement :finL = L[imax :] # extraction de la fin de la liste

19 finL. reverse () # retrournement

21 L = L[: imax ]+ finL # on remet dans la listeL. reverse () # on retourne

23

# appel ré cursif :25 return [L[0]] + triCrepier (L[1:])

Exercice 5 Pour un entier k donné, on dit qu’une liste est k-presque triée, si une des conditions suivantes est vérifiée :• chacun de ses éléments est à au plus k indices de la position où il devrait être,• au plus k de ses éléments ne sont pas à la même place.

Dans le cas d’une liste k-presque triée, montrer que le tri par insertion a une complexité de O(n) en nombre de comparaisons.

Correction : On suppose donc chacun des éléments est à au plus k indices de la position où il devrait être. On reprendsle code :

def tri_insertion2 (L):n = len(L)for i in range (1,n):

elmt = L[i]j = i# tête de lecture en position j-1while j>0 and L[j -1] > elmt :

# on déplace la tête de lecture et l’élément à placer# vers la gaucheL[j] = L[j -1]j = j-1

L[j] = elmt

Pour i ∈ [[1,n]], il faut au plus k étapes dans la boucle while, on a donc moins de kn comparaisons.

59

On suppose maintenant que plus de n− k éléments sont à leur place. Pour ces éléments, on a 1 seule comparaison. Pourles autres, on en a au plus n (en comptant large). Ainsi, on a moins de kn+(n− k) comparaisons.

60

Simulation de variables aléatoires et de tiragesPelletier Sylvain PC, Lycée Descartes

O Créer un nombre aléatoireCréer un nombre aléatoire est une chose impossible pour un ordinateur qui ne peut par définition que suivre des instructions

données à l’avance.Il existe tout de même des techniques pour générer des nombres pseudo-aléatoires sous la forme d’une fonction rand

qui renvoie un nombre aléatoire U de [0,1[. Le nombre U obtenu suit alors une loi uniforme sur [0,1[, loi qui n’est pas auprogramme en PCSI car son univers image n’est pas de cardinal fini, mais qui est vue rapidement en terminale.

Ce nombre U correspond à l’idée intuitive d’un nombre au hasard dans le segment [0,1[.Ce nombre n’est que pseudo-aléatoire puisque par définition, les valeurs renvoyées par la machine sont quantifiées : il n’y

a qu’un nombre fini de valeurs possibles sur [0,1] pour un ordinateur. La fonction rand ne renvoie donc qu’un nombre fini devaleurs. Comme ce nombre est très grand, on considère qu’il s’agit vraiment d’une loi uniforme.

La propriété intéressante est : ∀(a,b) ∈ [0,1]2, p(a6U < b) = b−a. Autrement dit la propriété que ce nombre soit entrea et b est proportionnelle à la longueur [a,b].

Comme pour toute variable continue, on a ∀x ∈ [0,1], p(U = x) = 0. Autrement dit, la probabilité qu’elle soit égale à unnombre fixé d’avance est nulle. En particulier, on ne se préoccupera pas des cas où U = 0 et U = 1, impossible en pratique.

Le but de cette fiche est de voir comment utiliser cette fonction rand pour simuler les lois usuelles.

R La seule fonction à connaître est rand.

O Simulation de lois uniformes

Proposition VI.1 Si U →U ([0,1[), alors :

la VAR X = (b−a)U +a vérifie X →U ([a,b[)

la VAR X = b(n+1)Uc vérifie X →U ([[0,n]])

la VAR X = b(b−a+1)Uc+a vérifie X →U ([[a,b]])

en particulier, la VAR X = bnUc+1 vérifie X →U ([[1,n]])

En conséquence :• l’instruction X=rand()*(b-a)+a permet de simuler une loi uniforme sur [a,b[• l’instruction X=floor(rand()*(n+1)) permet de simuler une loi uniforme sur [[0,n]]• l’instruction X=floor(rand()*(b-a+1)) +a permet de simuler une loi uniforme sur [[a,b]]• l’instruction X=floor(rand()*n) +1 permet de simuler une loi uniforme sur [[1,n]]

Démonstration. Considérons X = (b−a)U +a, on a alors :

06U < 1 donc 06 (b−a)U < a

puis pour tout (c,d) ∈ [a,b[ :

p(c6 X < d) = p(

c−ab−a

6U <d−ab−a

)=

d− cb−a

.

On a bien une loi uniforme sur [a,b[, d’où le premier point.Considérons maintenant :X = b(n+1)Uc, on a :

06U < 1 donc 06 (n+1)U < n+1

puis : 06 b(n+1)Uc6 n

De plus, pour k ∈ [[0,n]],

p(X = k) = p(

k 6 (n+1)U < k+1)= p( k

n+16U <

k+1n+1

)=

1n+1

.

61

On a donc bien une loi uniforme sur [[0,n]].Considérons maintenant le dernier cas X = bnUc+1, on a alors :

06U < 1 donc 16 nU +1 < n+1

puis : 16 1+ bnUc6 n

et pour k ∈ [[1,n]],

p(X = k) = p(

k 6 1+nU < k+1)= p(k−1

n6U <

kn

)=

1n.

On a donc bien une loi uniforme sur [[1,n]].

• Plutôt qu’apprendre par cœur des instructions, il suffit de partir de 0 6U < 1 puis de retrouver les univers images.Exemple pour un dé :

06U < 1 donc 06 6U < 6

puis : 06 b6Uc6 5

enfin : 16 b6Uc+16 6

Ainsi l’instruction floor(6*rand())+1 simule un dé.• La fonction randint permet de faire la même chose directement, mais l’usage de cette fonction est déconseillé, sauf si

l’énoncé y fait clairement référence.En effet :

– dans la bibliothèque pylab, la syntaxe est :randint(low,hight) qui renvoie un entier au hasard entre [[low,hight−1]],

– dans la bibliothèque random, la syntaxe est la même mais la fonction renvoie un entier au hasard entre[[low,hight]], (borne supérieure comprise donc).

D’une manière générale, il est plus utile de bien connaître les applications de la fonction rand que de connaître lasyntaxe de toutes les fonctions construites à partir de rand.

O Simulation de tirages avec remise

Si E est un ensemble de cardinal p, on peut simuler un tirage dans E en suivant la loi uniforme sur E, en utilisant la listeE des éléments de E et en calculant E[i], où i est un indice aléatoire uniforme dans [[0,(p−1)]].

Par exemple :

E = [’a’, ’b’, ’c’, ’d’, ’e’, ’f’, ’g’, ’h’, ’i’]p = length (E)i = floor(rand ()*p) # uniforme dans [|O, p -1|]X = E[i] # X suit la loi uniforme sur E

On peut alors créer très facilement une fonction qui réalise plusieurs tirages avec remise :

def tirageAvecRemise (E,n):2 """

entrée: E = liste de longueur p4 = ensemble des valeurs dans lesquelles on tire

n = entier = nbr de tirages6 sortie : L = liste de longueur n = valeurs tirées

"""8 p = len(E)

L = []10 for k in range(n) :

i = floor(rand ()*p) # uniforme dans [|O, p -1|]12 L += [E[i]]

return (L)

• On utilise ici la concaténation, mais on pourrait aussi initialiser la liste L par exemple avec L = [0]*n, puis la rempliravec L[k] = E[i].

62

O Simulation d’un tirage sans remise

Pour simuler un tirage sans remise dans un ensemble, il faut utiliser une liste E comme dans le cas d’un tirage avec remisesauf que l’on efface avec del la valeur tirée. La longueur de la liste E est alors automatiquement diminuée de 1.

Par exemple : pour tirer 5 fois sans remise dans une urne qui contient des jetons de [[1,20]] :

E = list( range (1, 21) ) # attention au 21!L = [0]*5for k in range (5) :

i = floor( rand ()*(20 -k))# i est alé atoire entre 0 et len(E)-1L[k] = E[i]del(E[i])

• C’est l’indice i dans la liste E que l’on tire, cet indice correspond à l’élément E[i]. On ne peut pas tirer directementE[i].• Petit détail : range ne crée pas une liste (mais un itérateur).• L’interprétation est : on prend l’élément i de E[i] (E est la liste des disponibles) et on l’ajoute à L.• C’est aussi comme cela, que l’on simule des tirages de cartes.• En tirant tous les éléments, on simule ainsi des mélanges (permutations).

O Calcul de la fréquence

Pour vérifier la validité du programme, on pourra réaliser le diagramme en bâtons de la variable aléatoire simulée : onréalise un nombre N d’expériences, et on note Ak le nombre d’apparitions de l’événement X = k. On vérifie que la fréquenceempirique Ak

N est proche de la probabilité théorique pk.

On utilise souvent la fonction bar du module matplotlib, sous la forme : bar(universImage, frequences), avec

• universImage une liste (ou un array unidimensionnel ) des valeurs de X(Ω).

• frequences une liste (ou un array unidimensionnel) des valeurs de la fréquence empirique :Ak

N.

• On peut ajouter l’option align=’center’ pour que les bâtons soient centrés sur les modalités.• Pour créer la liste des fréquences dans le cas usuel où l’univers image est [[0,n]] :

– on part d’un array F qui ne contient que des 0,– à chaque tirage, on obtient une valeur i, et on incrémente F[i],– si on veut avoir la liste des fréquences et non des effectifs, il suffit de diviser cet array par le nombre de tirages

(opérations entre array).– Enfin, l’univers image s’obtient en utilisant la fonction range.

On adapte bien sûr selon l’univers image en ajoutant 1 à F[i-1] si l’univers image est [[1,n]] ou autre.

Exemple pour obtenir le diagramme en bâtons d’une somme de deux dés simulés :

F = zeros (11) #F[i] = fré quence de (X=i+2)2 for t in range (100) : # 100 expé riences

D1 = floor(rand ()*6) +14 D2 = floor(rand ()*6) +1

i = D1+D26 F[i -2] += 1 # on incrémente l’effectif correspondant

F = F / 100 #pour avoir les fré quences et non les effectifs8 bar(range (2 ,13) , F, align=’center ’)

On obtient :

63

0 2 4 6 8 10 12 140.00

0.02

0.04

0.06

0.08

0.10

0.12

0.14

0.16

O Simulation d’une variable aléatoire de Bernoulli, d’un schéma de BernoulliPour simuler une variable de Bernoulli qui vaut 1 avec la probabilité p, il suffit de tester si U < p.

def bernoulli (p):"""entrée: p = float = proba de succèssortie : 1 succès, 0 échec"""alea = rand ()if alea < p :

return (1)else :

return (0)

On peut alors simuler un schéma de Bernoulli en répétant plusieurs fois cette simulation.

def binomial (n,p):"""entrée: n = nbr de tirages

p = float = proba de succèssortie : X = entier = nbr de succès dans n tirages"""X = 0for i in range(n) :

tirage = bernoulli (p)X += tirage # on peut aussi faire un if

return (X)

O Simulation d’une variable aléatoire hypergéométriquePour simuler une variable aléatoire hypergéométrique il faut garder en mémoire le nombre de blanches et de noires dans

l’urne. Tout se passe comme si, à chaque tirage, les blanches sont numérotées de 1 à nbrB, et les noires de nbrB+1 à nbrN.

1 def hypergeometrique (N,n,p) :"""

3 entrée: N = entier = Taille de l’urnen = entier = Nbr de tirages

5 p = float = proportion de B dans l’urne de départsortie : X = entier = nbr de Blanches après n tirages sans remise

7 """X = 0

9 nbrB = N*p

64

nbrN = N*(1-p)11 for i in range(n) :

alea = 1+ floor( rand ()*( nbrB+nbrN) ) # uniforme entre 1 et (nbrB+nbrN)13 if alea <= nbrB :

# tirage d’une B15 X += 1

nbrB = nbrB - 117 else :

# tirage d’une N19 nbrN = nbrN -1

return (X)

O Simulation d’une variable aléatoire quelconqueConsidérons une variable aléatoire X , avec X(Ω) = [[0,n−1]]. On suppose connue la loi de X , c’est-à-dire les n valeurs

p(X = i) pour i ∈ [[1,n−1]], notées(

pi

). Il s’agit, comme indiqué dans le cours, de n réels positifs dont la somme fait 1.

On cherche à obtenir des réalisations de cette variable, comme si on obtenait des résultats possibles de l’expériencealéatoire. On dit que l’on cherche à simuler la variable aléatoire.

On va donc écrire une fonction simule, qui prend en entrée la liste p des n valeurs de(

pi

), et qui sort une valeur X, qui

est comprise entre 0 et n−1, et qui est égale à k avec une probabilité pk.Pour cela, on va utiliser la fonction de répartition. On sait que :

∀k ∈ [[0,n−1]] , p(X = k) =pk

=k

∑i=0

pi−k−1

∑i=0

pi

=p(k−1

∑i=0

pi 6U <k

∑i=0

pi)

On peut donc simuler une variable aléatoire uniforme U puis chercher k tel quek−1

∑i=0

pi 6U <k

∑i=1

pi. Pour cela, on introduit

les sommes :

∀k ∈ [[0,n]] , Sk =k

∑i=1

pi avec S0 = 0.

Comme la suite(

Sk

)est croissante, il s’agit de trouver la plus petite valeur de k telle que : U < ∑

ki=1 pi.

On utilise donc une boucle while qui calcule la valeur suivante de la somme Sk jusqu’à dépasser la valeur de U .Cela donne :

def simule (p):2 """

entrée: p = liste de taille n = n valeurs pi positives dont la somme fait 14 sortie : X = float = valeurs alé atoires entre 1 et n avec p(X=i)=pi

"""6 alea = rand () # alea est la variable alé atoire uniforme

S = p[0] # valeur de la somme8 i = 0 # indice du dernier élément ajouté

while S < alea :10 i += 1

S += p[i]12 return (X)

• C’est aussi ce que l’on fait lorsque l’on simule une loi uniforme sur [[0,n]] : on cherche k tel que k−1n 6U < k

n , i.e.k = bnuc+1.

• On est sûr de sortir du while avant que i = n, carn−1

∑i=0

pi = 0.

65

Exercice 1 On dispose de deux boîtes d’allumettes : la boîte pile et la boîte face , et d’une pièce équilibrée. Audépart, les deux boîtes contiennent 20 allumettes. On tire à pile ou face, si on obtient pile, on enlève une allumette de laboîte pile , idem si on obtient face.

On s’arrête lorsqu’une boite est vide, et on note X le nombre d’allumettes dans la boîte non vide. Ainsi, X est unevaleur aléatoire de [[1,20]].

1. Écrire une fonction simule qui ne prend rien en entrée et qui calcule la valeur de X (aléatoire donc). On utilisera lafonction rand du module numpy.random.NB : une fonction qui n’a rien en entrée s’écrit : def simule():

2. Écrire une fonction simuleMFois qui prend un entier m, qui réalise m expériences et qui sort une liste L, de taille20, tel que : L[i] est le nombre d’expérience parmi les m pour lesquelles le résultat a été X = i+1.

3. Réaliser 2000 expériences avec la fonction précédente.En utilisant uniquement les fonctions de base de python, estimer la valeur empirique de la moyenne de X et sonécart-type.

4. En utilisant la fonction bar du module pylab, dessiner un diagramme en bâton des valeurs de L, c’est-à-dire desvaleurs empiriques de p(X = i).

Correction :

# -*- coding : utf -8 -*-2

4 """Auteur : Sylvain Pelletier

6 simulation des allumettes de Banach"""

8


12 from numpy. random import randfrom math import sqrt

14 from pylab import *

16 # Fonctions# ##########

18

# il est plus facile d’utiliser un paramètre pour cela.20 TAILLE_BOITE = 20

22 def simule ():"""

24 sortie : X = entier= nbr d’allumettes dans la boîte non vide lorsque l’une est vide

26 """nbrPile = TAILLE_BOITE

28 nbrFace = TAILLE_BOITE

30 while nbrFace >0 and nbrPile >0 :alea =rand ()

32 if alea <0.5 : #pilenbrPile = nbrPile -1

34 else :nbrFace = nbrFace -1

36 if (nbrFace >0):return ( nbrFace )

38 else:return ( nbrPile )

40

def simuleMFois (m):42 """

66

entrée: m = entier = nbr d’expé riences44 sortie : L = liste de 20 entiers

= L[i] est le nombre d’expé rience telles que X=i+146 """

L = [0]* TAILLE_BOITE48 for i in range(m) :

X = simule ()50 L[X -1] += 1

return (L)52

def calculeMoyVar (L, nbr_exp ) :54 """

entrée: L = liste d’entiers56 = L[i] est l’effectif de l’événemts X=i+1

après nbr_exp simulations58 nbr_exp = entier

= nbr de simulations60 = somme des valeurs de L[i]

sortie : moyenne = float62 variance = float

sigma = float = ecart -type64 Attention : L contient les effectifs de X=i+1

"""66 moyenne = 0

moyenneCarre = 068 for [i, effectif ] in enumerate (L):

moyenne += (i+1)* effectif70 moyenneCarre += ((i +1)**2) * effectif

72 moyenne = moyenne / nbr_expmoyenneCarre = moyenneCarre / nbr_exp

74

variance = moyenneCarre - moyenne **276 sigma = sqrt( variance )

return ([ moyenne , variance , sigma ])78

80

# Code:82 # ######

84 NBR_EXP = 2000

86 L = simuleMFois ( NBR_EXP )print("\n"+"-"*10+"ré sultats obtenus "+"-"*10)

88 print(L)

90 bar( arange (1, TAILLE_BOITE +1), L)show ()

92

[moyenne , variance , sigma ]= calculeMoyVar (L, NBR_EXP )94 print("-"*30)

print(" moyenne : \t"+str( moyenne ))96 print(" variance : \t"+str( variance )+"\t écart -type: \t"+str(sigma ))

Exercice 2 Soit N un entier naturel non nul. On dispose d’un sac contenant N jetons numérotés de 1 à N dans lequel oneffectue une succession de tirages avec remise d’un jeton en notant, à chaque fois, le numéro obtenu. Pour tout entiernaturel n non nul, on note Tn le nombre de numéros distincts obtenus au cours des n premiers tirages.

1. Exprimer précisément l’univers image Tn(Ω) où Ω désigne l’univers de l’expérience. Dans la suite, on considère queTn(Ω) = [[1,N]] quitte à ajouter artificiellement des valeurs possibles à Tn dont la probabilité d’apparition est nulle.

67

2. Écrire une fonction simule prenant en entrée n et N et simulant une expérience en calculant la valeur de Tn.3. Faire plusieurs expériences pour calculer les fréquences des événements Tn = k. On écrira une fonction loiEmpirique

qui prend en entrée n, N et le nombre d’expériences et qui calcule une liste T de taille N, avec T[i] la probabilitéempirique que Tn = i+1.On dit que l’on détermine la loi empirique de la variable Tn.Représenter cette loi sous forme de diagramme en bâtons.Proposer des représentations graphiques dans les cas où n < N, n≈ N et n très grand devant N.On sauvegardera les images obtenues.

4. Pour un entier naturel non nul tel que k 6 N, on calcule p(Tn+1) = k en utilisant le raisonnement suivant (à savoirfaire) :

on a :(

Tn+1 = k)⊂(

Tn = k)∪(

Tn = k−1)

autrement dit :(

Tn+1 = k)=

((Tn = k

)∩(

Tn+1 = k))∪

((Tn = k−1

)∩(

Tn+1 = k))

on conditionne : p(

Tn+1 = k)=p(

Tn = k)

pTn=k

(Tn+1 = k

)+ p(

Tn = k−1)

pTn=k−1

(Tn+1 = k

)Or, sachant Tn = k, on a N jetons dans l’urne, dont k ont déjà été tirés au moins une fois, l’événement Tn+1 = ksignifie alors que l’on tire l’un de ces k jetons. Ainsi, pTn=k

(Tn+1 = k

)= k

N .Sachant, Tn = k−1, on a N jetons dans l’urne, dont k−1 ont déjà été tirés au moins une fois, l’événement Tn+1 = ksignifie alors que l’on tire un jeton qui n’a pas déjà été tiré, et donc pTn=k

(Tn+1 = k

)= N−k+1

N .Cela donne :

P(Tn+1 = k) =kN×P(Tn = k)+

N− (k−1)N

×P(Tn = k−1).

On dispose d’une formule de récurrence permettant de calculer la loi de Tn+1 en connaissant la loi de Tn, comme lavariable T1 est certaine et égale à 1, on peut déterminer la loi exacte de Tn en fonction de n et N.Écrire une fonction loiExacte prenant en entrées les valeurs de n et de N et calculant la loi de Tn.Proposer une représentation graphique sous forme de diagramme en bâtons, et comparer aux représentationsobtenues en simulant les expériences.Indication : il y a une imprécision dans le raisonnement ci-dessus, la corriger. Attention au décalage : T[i]correspond à p(Tn = i+1).

5. Modifier le code pour calculer les moyennes et les variances des lois empiriques et théoriques.6. Dans cette question, on considère le cas N = 5 et n = 8.

Estimer le nombre d’expériences nécessaires pour obtenir par simulation une loi empirique de Tn proche de la loiréelle. Estimer alors le nombre d’opérations nécessaires pour faire ces simulations. Comparer au nombre d’opérationsnécessaires pour calculer la loi réelle.

Correction :

# -*- coding : utf -8 -*-2

4 """Auteur : Sylvain Pelletier

6 ré solution d’un problème de probabilit é avec Python"""

8

# compatibilit é V2 et V3:10 from __future__ import print_function , division , unicode_literals

import sys12 if sys. version_info .major <= 2 :

input = raw_input14


68

18 from pylab import *

20 # Fonctions# ##########

22 def simule (n, N):"""

24 entrée: n = entier = nbr de tiragesN = entier = taille de l’urne

26 sortie : entier = nbr de jetons différents obtenus en n tirages"""

28 dejaTire = [] # liste des jetons deja tiréfor k in range(n):

30 jeton = floor(rand ()*N)+1if jeton not in dejaTire :

32 dejaTire += [ jeton ]return (len( dejaTire ))

34

def loiEmpirique (nbrExpe , n, N):36 """

entrée: n = entier = nbr de tirages38 N = entier = taille de l’urne

nbrExpe = entier = nbr d’expé riences40 sortie : T = liste = T[i] est l’effectif de (T_n = i+1)

"""42 T = [0]*N

for expe in range( nbrExpe ):44 i = simule (n,N)

T[i -1] += 146 return (T)

48 def loiEmpirique2 (nbrExpe , n, N):"""


52 nbrExpe = entier = nbr d’expé riencessortie : T = liste = T[i] est la fré quence de (T_n = i+1)

54 """T = zeros(N) # o utilise un array

56 for expe in range( nbrExpe ):i = simule (n,N)

58 T[i -1] += 1return (T/ nbrExpe )

60

62 def loiExacte (n, N):"""


66 sortie : T = liste = T[i] est la probabilit é exacte de (T_n = i+1)méthode utilisant uniquement deux liste Tn et Tnp1

68 """

70 # on utilise deux listes : Tn et Tnp1 de taille NxTn= [1] + [0]*(N -1) # initialisation de Tn à 1

72 Tnp1= [0]*N # initialisation de Tn à 1for n in range(n -1):

74 Tnp1 [0] = 1/N*Tn [0]for i in range (1,N):

76 k = i+1Tnp1[i] = (k/N)*Tn[i] + (N-k+1)/N * Tn[i -1]

78 Tn = Tnp1 [:] # attention au piège de la copie de listereturn (Tn)

80

69

def loiExacte2 (n, N):82 """

entrée: n = entier = nbr de tirages84 N = entier = taille de l’urne

sortie : T = liste = T[i] est la probabilit é exacte de (T_n = i+1)86 méthode construisant entiè rement le tableau Tn

"""88 # on utilise un tableau T

# T[i,j] = p (Tn=k ) avec n = i+1 et k = j+190 T = zeros ([n,N])

T[0 ,0] = 1 # 1ère ligne: loi certaine = 1.92 for i in range (1,n): # boucle ligne

T[i ,0] = 1/N * T[i -1 ,0] # 1 ère élément de la ligne94 for j in range (1, N) : # boucle colonne

k=j+196 T[i,j] = (k/N)*T[i-1,j] + (N-k+1)/N * T[i-1,j -1]

print(T)98 return (T[n -1 ,:]) # renvoi la dernière ligne.

100 # Code:# ######

102 N = 5n = 8

104 nbrExpe = 100000

106 empirique = False

108 if empirique :L = loiEmpirique (nbrExpe , n, N)

110 L = array(L) / nbrExpe #on utilise les fré quences et non les effectifs

112 # ou utiliser# L = loiEmpirique2 (nbrExpe , n, N)

114 else:L = loiExacte (n, N)

116

# repré sentation graphique118 bar( range (1,N+1), L, align=’center ’)

show(block =’false ’)120

# calcul de la moyenne et de la variance122 moy = 0

moyCarre = 0124 for i, freq in enumerate (L) :

result = i+1126 moy += result * freq

moyCarre += ( result **2) * freq128 variance = moyCarre - moy **2

print(" moyenne obtenue : "+str(moy )+"\t variance obtenue : "+str( variance ))

70

Résolution de f (x) = 0Résolution numérique d’équationsdifférentiellesRésolution de systèmes linéairesAlgorithme de remplissage Flood FillSimulation de propagation de maladieSimulation numérique des oscillations d’unpenduleModèle proie-prédateur

4 — Révision sur l’ingénierie numérique

Dans ce chapitre, on revoit rapidement les algorithmes à connaître d’ingénierienumérique.

I Résolution de f (x) = 0

I.1 Méthode de dichotomieLa méthode de dichotomie est la méthode la plus simple pour résoudre une équation

qui s’écrit : f (x) = 0.

O PrincipeOn dispose d’une fonction f : [a,b]→ R continue telle que f (a) f (b) < 0 (ie de

signe contraire). On calcule alors le point milieu : c=a+b

2. On utilise alors le principe

suivant :• si f (c) f (a)> 0, on remplace a par c, et on recommence,• si f (c) f (b)> 0, on remplace b par c, et on recommence.

À chaque itération la taille de l’intervalle est diminuée par 2. On choisit de s’arrêterlorsque b−a est inférieure à une précision donnée.

O Implémentaton en version itérative

1 def dichotomie (f,a,b,eps)"""

3 entrée: f fonctiona,b réel avec a0 pré cisionsortie : c valeur approch ée d’une solution

7 de f(c)=0 à 2 epsilon près"""

9 while (b-a>eps) :c=(a+b)/2 # c milieu de l’intervalle

11 if f(c) == 0 : #cas facultatif : f(c)=0

72 Révision sur l’ingénierie numérique

return c13 if f(a)*f(c) > 0 :

a=c15 else

b=c17 return c

R Cet algorithme peut être utilisé (en l’adaptant) pour l’étude numérique de suitesimplicites.on peut aussi écrire des versions qui évitent les appels à la fonctions f en gardanten mémoire les valeurs de f (a) et f (b).

Exemple I.1 On veut calculer les termes de la suites définies par :

∀n ∈ N, unn +u2

n +2un−1 = 0 un ∈ [0,1].

1 def resoudEn (n, eps ):"""

3 entrée: n = entiereps = une pré cision

5 sortie : un = valeur approch ée de la solution deEn à eps près.

7 on calcule un par dichotomie"""

9

a = 011 fa = a**n + a**2 + 2*a -1 # valeur de f(a)

b = 113 fb = b**n + b**2 + 2*b -1 # valeur de f(b)

15 while b-a>eps :c = (a+b) / 2

17 fc = c**n + c**2 + 2*c -1if fa*fc >0 :

19 a = cfa = fc

21 else :b = c

23 fb = fcreturn c

O Implémentation récursiveOn peut aussi écrire un algorithme récursif :

def dichotomie (f,a,b,eps)2 c= (a+b)/2

if b-a < eps :4 return c

if f(a)*f(c) > 0 :6 return dichotomie (f,c,b,eps)

I Résolution de f (x) = 0 73

else :8 return dichotomie (f,a,c,eps)

O Étude théorique

Déjà, le résultat du cours permet d’assurer que si f est continue sur [a,b], alorsl’algorithme s’arrête. Plus précisément, si a = 0, b = 1 et ε = 1

2N alors on est sûr quel’algorithme s’arrête en N itération.

Un invariant de boucle est : f (a) f (b)< 0 .Enfin, on peut remarquer que le test d’arrêt est : la valeur retournée est une

approximation d’une racine à ε près .Dernier point : on a choisi d’arrêter les itérations si f (c) est nul. Or, cela revient à

comparer deux flottants. En pratique, il est impossible que f (c) soit égal à 0. Souventcette condition est omise. Seul le test d’arrêt b−a6 ε devient vraie de manière sûre.

Exemple I.2 Pour calculer une approximation de√

2, on peut appliquer l’algorithmede dichotomie à la fonction f (x) = x2−2 su [0,2]. La suite des termes est alors unesuite de rationnels (puisqu’à chaque itération, on prends le point milieu). On est doncassuré de ne jamais avoir la vraie valeur

√2 puisqu’elle est irrationnelle.

I.2 Algorithme de NewtonO Principe

Considérons une fonction f définie, et dérivable sur un intervalle I. On cherche unesolution de f (x) = 0.

On suppose que l’on dispose d’une valeur x0 proche de la solution.Une technique consiste à construire la suite (xn) en partant de x0 avec la méthode

suivante :• On considère la tangente Tn en xn,• on choisit pour valeur de xn+1 la l’intersection de Tn et de l’axe horizontal.

Plus précisément, l’équation de Tn est :

Tn : y = f (xn)+ f ′(xn)(x− xn).


Ainsi, xn+1 est la solution de l’équation : f (xn)+ f ′(xn)(x− xn) = 0, ie :

xn+1 = xn−f (xn)

f ′(xn).

O Implémentation

def newton (f,df , x0 , eps) :2 """

entrée: f = fonction4 df = fonction = dérivée de f

x0 = réel = point de départ6 eps = réel = pré cision

sortie x = réel8 = valeur approch ée de la solution de f(x)=0

on choisit ici de s’arrêter si on |x_n+1 - x_n| < eps10 """

xp = x0 # xp = point précédent12 x = xp - f(xp) / df(xp)

while abs(xp -x) > eps :14 xp = x

x = x - f(x) / df(x)16 return (x)

O Étude théoriqueContrairement à la dichotomie, on ne dispose pas d’un test d’arrêt évident : on peut

choisir | f (xn)|6 ε , ou |xn+1−xn|6 ε . La convergence de la méthode n’est pas assurée.Il est possible que l’algorithme ne s’arrête pas.

Cette suite n’est bien définie que si elle reste sur un intervalle dans lequel f ′ est nonnul. Il est ainsi possible que cette suite ne soit pas définie pour tout n ∈ N.

De plus, on n’a pas la précision de l’écart entre la solution calculée et la racine.Par contre, on est assurée qu’elle converge rapidement.En effet, si on note r la racine, alors on a pour n ∈ N :

xn+1− r = xn− r− f (xn)

f ′(xn).

On utilise alors Taylor-Lagrange :

∃cn ∈]r,xn[ ou ]xn,r[, f (xn) = f (r)︸︷︷︸=0

+(xn− r) f ′(xn)+(xn− r)2 f ′′(cn)

et donc :

f (xn)

f ′(xn)= (xn− r)+(xn− r)2 f ′′(cn)

f ′(xn)

Et donc :

xn+1− r =−(xn− r)2 f ′′(cn)

f ′(xn)

II Résolution numérique d’équations différentielles 75

En notant

M =max( f ′′)min( f ′)

On suppose que ces quantités existent, avec ∃a > 0,min( f ′)> a alors :

|xn+1− r|6 |xn− r|2M

Ainsi, si |xn− r|= 10k, alors |xn+1− r|6M102k.

II Résolution numérique d’équations différentiellesII.1 Principes généraux

On cherche une fonction y solution sur [0,1] d’une équation différentielle :

y′ = f (y, t) avec y(0) = y0 donné.

La fonction f est une fonction définie sur J× [0,1] et on suppose que y : [0,1]→ J.l’équation peut ainsi s’écrire :

∀t ∈ [0,1], y′(t) = f(

y(t), t)

Notons qu’il n’est pas toujours possible de résoudre analytiquement de telleséquations différentielles.

On discrétise alors l’intervalle [0,1] en N valeurs séparées par un pas de largeur ∆.Autrement dit, on considère les points (ti)i∈[[0,N−1]] définis par :

∀i ∈ [[0,N−1]] , ti =i

N−1

On peut obtenir rapidement une liste des valeurs (ti)i∈[[0,N−1]] par la fonction linspace :

t = linspace (a,b, nbrPoints )

qui renvoie un 1d-array de taille nbrPoints qui contient les valeurs discrétisées del’intervalle [a,b]. Les bornes a et b étant comprises.

On cherche alors à construire la liste Y des valeurs approchées de(

y(ti))

. Onconnaît la première valeur : Y0 = y(0) = y0.

On utilise alors le principe suivant :

∀i ∈ [[0,N−2]] , Yi+1 ≈ y(ti+1) =y(ti)+∫ ti+1

tiy′(u)du

=y(ti)+∫ ti+1

tif (y(u),u)du

Or cette dernière intégrale est sur un intervalle de longueur ∆, on peut donc appliquerune méthode simple pour évaluer cette intégrale, par exemple, écrire par la méthodedes rectangles à gauche :∫ ti+1

tif (y(u),u)du = ∆ f

(y(ti), ti

)


En remplaçant y(ti) par la valeur approchée Yi, on justifie l’algorithme :

∀i ∈ [[0,N−2]] , Yi+1 = Yi +∆ f (Yi, ti)

On peut aussi retrouver cet algorithme en écrivant :

y′(ti) = f (y(ti), ti)

et donc :Yi+1−Yi

∆= f (y(ti), ti)

d’où Yi+1 =Yi +∆ f (Yi, ti)

O ImplémentationVoici un exemple d’implémentation :

1 def euler(f, y0 , N) :Y = [0]*N

3 t = linspace (0,1,N)Y[0] = y0

5 Delta = 1 /(N -1)for i in range(N -1):

7 Y[i+1] = Y[i] + Delta * f(Y[i], t[i])return Y

O Étude théoriqueIl est clair que l’algorithme s’arrête : c’est une boucle for. Le problème est l’étude

de l’erreur commise.

En fait on peut distinguer plusieurs types d’erreurs :• L’erreur commise en remplaçant∫ ti+1

tif (y(u),u)du par ∆ f (y(ti), ti)

Il s’agit d’une erreur de schéma, commise à chaque itération.Intuitivement, plus le pas est petit, plus cette erreur est faible.• L’erreur commise en remplaçant : f (y(ti), ti) par f (Yi, ti). Il s’agit d’une répé-

tition des erreurs précédentes.On pourra utiliser les accroissements finis pour écrire :

| f (y(ti), ti)− f (Yi, ti)|6M|y(ti)−Yi| avec M qui dépends de∂ f∂y

.

• De plus, à chaque opération, il y a des erreurs numériques d’approximation !

Le problème d’étudier les erreurs de ce type de schéma n’est pas simple. Mathémati-quement, on distingue les notions de :• schéma convergent : si lorsque le pas tends vers 0, l’approximation tends

vers la solution. Au sens :

lim∆→0

(max

i∈[[0,N−1]]|Yi− y(ti)|

)= 0.

II Résolution numérique d’équations différentielles 77

• schéma stable lorsque les erreurs ne se propagent pas trop d’un calcul àl’autre.• schéma consistant lorsque qu’à chaque pas l’erreur locale n’est pas trop

grande.

O VariantesOn peut approximer différemment l’intégrale. Par exemple, on peut choisir les

rectangles à droite :∫ ti+1

tif (y(u),u)du = ∆ f

(y(ti+1), ti+1

)On arrive alors à une équation donc Yi+1 est solution :

∀i ∈ [[0,N−2]] , Yi+1 ≈ y(ti+1) =y(ti)+∫ ti+1

tiy′(u)du

=y(ti)+∫ ti+1

tif (y(u),u)du

=Yi +∆ f (Yi+1, ti+1)

Il faut résoudre cette équation pour obtenir la valeur de Yi+1.C’est le schéma d’Euler implicite.Il existe d’autres variantes.

O Cas d’une équation d’ordre 2Pour résoudre une équation différentielles d’ordre 2, on effectue un changement

d’inconnue : on considère que la fonction et sa dérivée sont inconnues. On se ramèneainsi à une équation d’ordre 1.

Si l’équation est :

(E) y′′ = f (y′,y, t) y(0) = y0 y′(0) = v0.

avec f : R3→ R.On considère alors comme inconnue la fonction y à valeur dans R2,

y : t 7→ (y1(t),y2(t))

vérifiant l’équation :

(E) y′ = F(y, t) y(0) = (y0,v0)

avec F :

R2×R → R2

((a,b),c) 7−→(

b, f (a,b,c))

Le rapport ente y et la solution y cherché est : y est solution de (E) si et seulement si(y,y′) est solution de E.

Exemple II.1 Si on étudie l’équation du pendule amorti :

(E) θ′′+λθ

′+ω2 sin(θ) = 0


On va considérer la fonction y à valeur dans R2, solution de :

(E2) y′ = f (y) avec f : (a,b) 7−→ (b,−λb+ω2 sin(a)).

On a alors :

θ est solution de (E) ⇐⇒ (θ ,θ ′) est solution de (E2).

On applique ensuite les méthodes de résolution numériques des équations différen-tielles sur l’équation (E2).

III Résolution de systèmes linéairesIII.1 Méthode de remontée

O PrincipeLe grand intérêt des matrices triangulaires est que si A est une matrice triangulaire

et B un vecteur colonne, le système AX = B se résout par méthode de remontée, c’est-à-dire qu’on part de la dernière ligne et que l’on calcule les inconnues au fur et à mesure,en partant de la dernière.

Soit A une matrice triangulaire supérieure de taille n et inversible, soit B ∈Mn1 unvecteur colonne. Le système AX = B d’inconnu le vecteur X ∈Mn1 s’écrit :

AX = B ⇐⇒

a11 · · · · · · ann

a22 · · · a2n. . .

. . ....

an−1n−1 an−1n

ann

x1x2...

xn−1xn

=

b1b2...

bn−1bn

Résoudre cette équation matricielle, revient donc à résoudre le système d’inconnues(x1, . . . ,xn) :

a11x1+ . . . . . . +annxn = b1

a22x2+ . . . +a2nxn = b2

. . .. . .

... =...

an−1n−1xn−1+ an−1nxn = bn−1

annxn = bn

Si la matrice A est inversible, alors ses coefficients diagonaux sont alors non nuls.Le système a alors une unique solution qui se calcule rapidement :

• la dernière ligne donne xn : xn =bn

ann,

• l’avant-dernière ligne s’écrit :

an−1n−1xn−1 +an−1nxn = bn−1,

on peut donc en déduire xn−1 sous la forme :

xn−1 =1

an−1n−1(bn−1−an−1nxn) .

Comme xn est déjà calculé, on a bien xn−1.

III Résolution de systèmes linéaires 79

• On calcule de même les xi pour i = n . . .1. La ligne i s’écrit (avec le signesomme) :

n

∑k=i

aikxk = bi,

ce qui donne xi en utilisant les valeurs déjà calculées de xk pour k > j :

xi =1aii

(bi−

n

∑k=i+1

aikxk

).

O ImplémentatonVoici un exemple d’algorithme.

def resoudRemontee (A,b)2 """

entrée: A = array ([n,n])4 = matrice triangulaire supé rieure

inversible de taille nxn6 b = array(n) = vecteur

sortie : x = array(n) = vecteur solution de Ax=b8 """

10 [n,m] = shape(A)k = len(B)

12 if n!=m or k !=n :print("pb de taille !")

14 return

16 x = zeros(n)

18 x[n -1] = b[n -1] / A[n-1, n -1] # dernier élément

20 for i in range(n-2,-1,-1):

22 # on calcule la sommesomme =0;

24 for k in range(i+1,n)somme += A[i,k]*x[k] # x[k] est déjà calcul é

26 x[i]= ( b[i] -somme ) / A[i,i]

R L’initialisation du dernier élément à part n’est pas utile : si i = n−1, la bouclefor k in range(i+1,n) ne contient aucun terme, l’exécution ne rentre alorspas dans cette boucle.On peut aussi écrire :

somme = sum( A[i,i+1:] * x[i+1 ,:])

O ComplexitéLe calcul de xn demande 1 opérations, celui de xn−1 demande 3 opérations, celui

de xn−2 demande 5 opérations, etc. Au final, on a O(n) opérations pour le calcul de lasolution.


III.2 Pivot de GaussO PrincipeOn fait des opérations sur les lignes pour réduire un système à un système équivalent

échelonné.À chaque étape, on traite la colonne j :• on cherche k > j tel que ak j 6= 0, puis on fait łk↔ l j pour avoir un pivot non nul.• On effectue les opérations :

∀k > j, lk← lk−ak j

a j jl j

Pour réduire les éléments ak j avec k > j.Les opérations se font sur la matrice et sur le second membre (ou de manière équivalentesur la matrice augmentée).

O ImplémentationOn réduit le système AX = B et UX =C avec U échelonnée.

1 def gauss(A,b) :"""

3 entree : A = array= matrice carrée inversible de taille nxn

5 b = array= vecteur second membre .

7 sortie : A = array= matrice triangulaire supé rieure

9 b = array= vecteur second membre .

11 le système AX=b initial est é quivalent au système final(qui se résout par remont ée)

13 """[n,m] = shape(A)

15 for j in range(n):#on traite la colonne j

17

#étape 1: on é change les lignes19 if A[j,j] != 0:

# on cherche le premier terme non nul21 # dans la colonne j en dessous de ajj:

# comme A est inversible , on est sûr de trouver .23 k = chNonNul (A,j)

# on é change lk et lj25 A[k ,:], A[j ,:] = A[j,:], A[k ,:]

b[k], b[j] = b[j], b[k]27 # arrivé ici , A[j,j] != 0

29 #étape 2: on modifie toutes les lignes en dessousfor k in range(j+1,n) :

31 alpha = A[k,j] / A[j,j]A[k ,:] += -alpha*A[j ,:]

33 b[k] += -alpha*b[j]return A,b


Avec comme fonction chNonNul :

def chNonNul (A,j) :2 """

entrée: A = array = matrice carrée inversible4 de taille nxn

j = entier = indice de ligne6 sortie : k = indice de ligne

on cherche k >= j tel que A[k,j] !=08 """

[n,m] = shape(A)10 for k in range(j,n) :

if A[k,j] != 0 :12 return k

print(" ERREUR matrice non inversible ")14 return

Très souvent, plutôt que de chercher un terme non nul, on va chercher le pivot leplus grand (en valeur absolue). Cela assure une meilleure stabilité numérique. Onparle de pivot partiel.

On va donc utiliser :

def chNonNul (A,j) :2 [n,m] = shape(A)

pivotMax = abs(A[j,j])4 lPivot = j

for k in range(j+1,n) :6 if abs(A[k,j]) > pivotMax :

pivotMax = abs(A[k,j])8 lPivot = k

return lPivot

R On peut aussi utiliser Argmax(abs(A[j,:])) +j.

O ComplexitéL’instruction A[k,:] += -alpha*A[j,:] cache une boucle for (écrite en C). Elle

demande n opérations. On voit ainsi qu’il est plus judicieux (pour des raisons de tempsde calcul, mais aussi de stabilité des erreurs numériques) de la remplacer par :

A[k,j] = 0A[k, j+1:] += - alpha * A[j, j+1:]

Dans ce cas, on voit que cette instruction corresponds à 2(n− j) opérations.Autre manière de voir :

. le traitement de la colonne 1 demande 2(n−1)2 opérations (chaque coefficienttraité demande 2 opérations),

. le traitement de la colonne 2 demande 2(n−2)2 opérations, etc.Au final, on a :

C(n) = 2(n−1)2 +2(n−2)2 + · · ·+1 = 2n(n+1)(2n+1)

6= O(n3)


III.3 Variantes de la réduction de GaussO La factorisation LU

Soit A une matrice carrée, on dit qu’elle admet une décomposition LU si il existe :• une matrice L triangulaire inférieure avec des 1 sur la diagonale (Lower),• une matrice U triangulaire supérieure (Upper) inversible,

telle que A = LU .

Mathématiquement, on peut prouver que cette factorisation existe et est unique à lacondition suivante :• le terme A11 (en haut à gauche) est non nul,• la matrice 2×2 obtenue avec les deux premières lignes et colonnes est inversible,• la matrice 3×3 obtenue avec les trois premières lignes et colonnes est inversible,• etc,• et la matrice A est inversible.

R Lorsque l’on choisit une matrices avec des coefficients réels tirés aléatoirementavec la loi uniforme c’est le cas avec une probabilité 1.

. L’avantage de cette factorisation est que si on a à résoudre un grand nombre desystème de la forme AX = B pour différents second membre B, On se ramèneà résoudre les systèmes échelonnés : LY = B (système triangulaire inférieur) etUX = Y (système triangulaire supérieur).

En pratique, une matrice admet une décomposition LU si lorsqu’on effectue l’al-gorithme de réduction de Gauss, on n’a jamais besoin d’échanger les lignes pouravoir un pivot non nul. Cette factorisation se calcule alors aisément en utilisantla décomposition de Gauss : à l’étape j on traite la colonne j, on met alors les

coefficientsAk j

A j jdans la matrice L en position (k, j).

Démonstration. Montrons comment on obtient la factorisation LU sur une matrice(3,3). La matrice A est noté :

A =

a11 a12 a13a21 a22 a23a31 a32 a33

Par hypothèse a11 est non nul (c’est la matrice extraite d’ordre 1).

On effectue alors les opérations :

l2← l2−a21

a11l1

l3← l3−a31

a11l1

On note α21 =−a21a11

et α31 =−a31a11

.Effectuer ces opérations revient à mutliplier la matrice A à gauche par la matrice : 1 0 0

α21 1 0α31 0 1

.


On arrive alors à une factorisation de la forme :

A =

1 0 0α21 1 0α31 0 1

a11 a12 a130 b22 b230 b32 b33

.

Comme les vecteurs (a11,a12) et (a21,a22) forment une famille libre, le coefficient b22est non nul. On retrouve bien le fait que l’on peut continuer la réduction de Gauss sanséchanger les lignes.

Pour réduire la matrice A, on effectue alors l’opération :

l3← l3−b32

b22l2

On note alors : α32 =−b32b22

, cette opération revient à multiplier à gauche par la matrice :1 0 00 1 00 α32 1

et on obtient la factorisation :

A =

1 0 0α21 1 0α31 0 1

1 0 00 1 00 α32 1

a11 a12 a130 b22 b230 0 c33

.

Il reste à effectuer le produit : 1 0 0α21 1 0α31 0 1

1 0 00 1 00 α32 1

=

1 0 0α21 1 0α31 α32 1

Pour obtenir la factorisation demandée :

A =

1 0 0α21 1 0α31 α32 1

a11 a12 a130 b22 b230 0 c33

.

R On peut constater que c33 est non nul, puisque sinon c’est qu’une combinaisonlinéaire des trois lignes de la matrices A donne un vecteur nul et donc que lamatrice A n’est pas inversible.

À retenir :• Le lien entre opérations sur les lignes et multiplication à gauche par des

matrices.• Les matrices des opérations élémentaires sont faciles à déterminer : on part de

la matrice identité et on effectue l’opération élémentaire sur l’identité.• De même il est facile de faire le produit de matrices d’opérations élémentaires :

il suffit d’effectuer les opérations élémentaires dans le bon ordre.


• On se ramène à des système triangulaires faciles à résoudre.

R En adaptant la méthode précédente, on peut montrer que la réduction de Gaussrevient à écrire qu’une matrice A admet une décomposition de la forme PLU , oùP est une matrice de permutation (un et un seul 1 par ligne), L est triangulaireinférieure, et U est triangulaire supérieure.

L’algorithme est donc :

def reducLU (A) :2 """

entree : A = array4 = matrice carrée inversible de taille nxn

sortie : A = array6 = matrice triangulaire supé rieure U

L = array8 = matrice triangulaire infé rieure

avec A=LU10 """

[n,m] = shape(A)12 assert n==m, " matrice pas carrée"

14 # initialisation de L à l’identit éL = zeros( (n,n))

16 for i in range(n) :L[i] = 1

18 #on peut aussi utiliser la fonction identity

20 for j in range(n):#on traite la colonne j

22 assert A[j,j] !=0, "pas de factorisation LU"

24 for k in range(j+1,n) :alpha = -A[k,j] / A[j,j]

26 A[k ,:] += alpha*A[j ,:]L[k,j]= alpha

28

return L,A

O Réduction de Cholesky

Proposition III.1 Soit A une matrice symétrique définie positive, alors A admet unedécomposition de la forme L tL, où L est triangulaire inférieure.

On peut donc écrire :

a11 a12 . . . . . . a1n

a21 a22 . . . . . . a2n...

......

...a1n . . . ann

=

l11 0 0 . . . 0l21 l22 0 . . . 0...

. . .. . .

......

. . . 0ln1 . . . lnn

l11 l21 . . . . . . ln10 l22

0 0. . .

......

.... . .

. . .

0 0 . . . 0 lnn


. L’intérêt est alors de pouvoir résoudre les systèmes AX = B en résolvant lessystèmes triangulaires : LY = B puis tLX = Y .

Démonstration. En taille (3,3) : On considère la matrice A

A =

a b cb d ec e f

symétrique définie positive

et on cherche la matrice L =

l11 0 0l21 l22 0l31 l32 l33

telle que A = L tL.

On a donc les équations :a b cb d ec e f

=

l11 0 0l21 l22 0l31 l32 l33

l11 l21 L310 l22 l320 0 l33

=

l211 l11l21 l11l31

l11l21 l221 + l2

22 l21l31 + l22l32l11l31 l21l31 + l22l32 l2

31 + l232 + l2

33

On obtient alors : l2

11 = a. Or a > 0 (puisque la matrice est définie positive). On a doncl11 =

√a avec l11 > 0.

En identifiant la première ligne, on obtient :(a b c

)=(l211 l11l21 l11l22

)D’où les valeurs de l21 et de l22 :

l21 =b

l11l22 =

cl11

.

On a obtenu 3 valeurs, on obtient ensuite l22 :

l222 = d− l2

21 et donc : l22 =√

d− l221.

En effet, d− l221 > 0 car la matrice est symétrique définie positive (calculer le détermi-

nant 2×2) pour y voir clair.Puis on en déduit la valeur de l32 :

e = l21l31 + l22l32 et donc : l32 =1

l22(e− l21l31)

Enfin, on en déduit la valeur de l33 :

l231 + l2

32 + l233 = f et donc : l33 =

√f − l2

31− l232.


En généralisant, on voit que l’on détermine la matrice L colonne par colonne. Lecoefficient diagonal est :

l j j =

√√√√a j j−j−1

∑k=1

l2jk

Les autres coefficients sont :

li, j =1l j j

(a ji−

j−1

∑k=1

likl jk

)pour i > j

R La sommej−1

∑k=1

likl jk est le produit scalaire du vecteur (li1, li2, . . . , li, j−1) extrait

de la ligne i et le vecteur (l j1, l j2, . . . , l j, j−1) extrait de la ligne j.

Cela donne l’algorithme

1 def cholevsky (A):"""

3 entrée: A = array 2d= matrice symé trique définie positive .

5 sortie L = array 2d= matrice triang inf

7 avec A = L x tL"""

9 n,m = size(A)assert n==m, " matrice non carrée"

11 L =zeros ((n,n))for j in range(n) :

13 L[j,j] = sqrt( a[j,j] - sum(L[j,:j]**2) )for i in range(j+1,n):

15 L[i,j] = a[j,i] - sum( L[i,:j] * L [j,:j] )return L

Algorithme de remplissage Flood FillPelletier Sylvain PC, Lycée Descartes

Le but de ce projet est d’écrire une application de coloriage pour les jeunes enfants comme il en existe pour les tablettes :• On présente à l’enfant une image à colorier, c’est-à-dire une image noir et blanc où les contours sont en noir,• l’enfant choisit une couleur et un point dans l’image (un pixel donc)• la machine remplit alors la totalité de la zone contenant le point choisi avec la couleur choisie.

O Représentation des images numériques

Une image numérique couleur corresponds à la donnée de trois tableaux. Chaque case du tableau (appelée pixel)correspondant à la valeur en un point des trois composantes chromatiques de l’image : le rouge, le vert et le bleu.

Plus précisément, en python l’image de taille n×m sera représenté sous la forme d’un 3d-array img de taille n×m×3. La valeur de img[i,j,0] est le niveau de rouge du pixel (i,j), la valeur de img[i,j,1] le niveau de vert, et cellede img[i,j,2] le niveau de bleu. On peut ainsi avoir accès et modifier la couleur du pixel (i,j) pour i ∈ [[0,n−1]] etj ∈ [[0,m−1]].

R Souvent, img est en fait un 3d-array de taille n×m×4. La quatrième composante chromatique est la transparenceque l’on n’utilisera pas ici.

Parfois, on préfère travailler sur les trois composantes chromatiques (ie trois 2d-array) plutôt que directement sur le3d-array. Cela revient à écrire : R,G,B = img[:,:,0], img[:,:,1], img[:,:,2]. On utilise alors R[i,j] pouravoir accès à la composante rouge du pixel [i,j]. Tout changement sur les array R, G et B se retrouve sur le array img.

Selon la manière dont l’image est codée et selon comment elle est lue par le logiciel, cet array contiendra :• des entiers de [[0,255]] codés sur 8bits, c’est le type unit8.• des réels de [0,1[.

Dans la suite, on prends la convention que les valeur sont codées sous la forme de uint8. Si ce n’est pas le cas, il est faciled’adapter.

! Il y a un piège lorsqu’on manipule des uint8 : si on fait la somme de deux entiers codés en uint8, on peut obtenir unentier supérieur à 255 et donc un dépassement de capacité ! Il faut les convertir en entier (avec int).

Lorsqu’on manipule les images, il est important de savoir dans lequel de ces cas on s’est placé. Pour vérifier, le plus simpleest d’afficher la valeur et le type du pixel central comme cela est fait sur le script fourni.

Les différentes couleurs sont obtenues en donnant des valeur aux composantes (R,G,B) respectivement, niveau de rouge,vert et bleu. On obtient ainsi les différentes couleurs :

Le blanc corresponds à (R,G,B) = (255,255,255),le noir à (R,G,B) = (0,0,0),le bleu à (R,G,B) = (0,0,255),

le gris moyen à (R,G,B) = (128,128,128),le jaune à (R,G,B) = (255,255,0)le violet à (R,G,B) = (255,0,255) etc.

En particulier, la luminosité d’une pixel corresponds à la somme des trois composantes. Plus le pixel est clair plus cettesomme est importante.

En mélangeant les différents niveaux, on a 2563 = 16777216 couleurs différentes, ce qui corresponds à la résolution desécrans standards.

Exemple III.1 On peut par exemple utiliser le array img de la manière suivante :• pour savoir si un pixel (x,y) est noir, on peut simplement tester si la somme des trois composantes est faible :

int(img[x,y,0]) + int(img[x,y,1])+ int(img[x,y,2]) < SOM_NOIR.Par exemple SOM_NOIR = 10*3 est une bonne valeur,• pour savoir si un pixel (x,y) est blanc, on peut simplement tester :

int(img[x,y,0]) + int(img[x,y,1])+ int(img[x,y,2]) > SOM_BLANC.Par exemple SOM_BLANC = 250*3 est une bonne valeur.

87

• Pour donner la couleur (r,g,b) à un pixel, où (r,g,b) est un triplet d’entier de [[0,255]]. Il suffit d’écrire :img[x,y,0], img[x,y,1], img[x,y,2] = r,g,b.

O Modélisation

Pour modéliser l’application, on utilise la notion de composante connexe discrète (dans un tableau donc).On considère l’ensemble des pixels de l’image qui est identifié comme l’ensemble P = [[0,n−1]]× [[0,m−1]].À une itération de l’algorithme, on note :• N l’ensemble des pixels noirs, et N l’ensemble des pixels qui ne sont pas noirs (peuvent être blanc dans l’image

originale ou de couleur dans la suite).• B l’ensemble des pixels noirs, et B l’ensemble des pixels qui ne sont pas blancs.Deux pixels x = (i, j), y = (i′, j′) sont voisins dans P si |i− i′|+ | j− j′|6 1, c’est-à-dire si ils se touchent par un bords.

On note alors xV y. C’est une relation d’équivalence.

R Par convention, on considère qu’un pixel est son propre voisin, c’est-à-dire que V est réflexive.

C’est ici la 4 connexité que l’on utilise puisqu’un pixel situé au centre a 4 voisins. On peut aussi utiliser la 8-connexité,avec max(|i− i′|, |y− y′|)6 1, c’est-à-dire si ils se touchent par un bords ou par un coin dans l’image.

On définit alors la relation : être dans la même composante connexe de blanc , par la définition suivante : un pixelblanc x ∈B est dans la même composante connexe que le pixel blanc y ∈B si et seulement si

∃p ∈ N,(x0, . . . ,xp) ∈P p, tels que

x0 = x et xp = y,∀i ∈ [[0, p−1]] , xiV xi+1

∀i ∈ [[0, p]] ,xi ∈B.

Autrement dit, si il existe un chemin dans l’image constitué de pixels voisins et tous blancs qui part de x et va jusqu’à y.On note alors xRy et c’est encore une relation d’équivalence.

Ainsi modélisé, le problème peut s’écrire de la manière suivante : pour un pixel x donné trouver tous les pixels ytels que xRy. On cherche donc la classe d’équivalence de x pour la relation R.

Ce problème peut ainsi se généraliser à d’autres relations et ne sert donc pas uniquement aux applications de coloriage.

L’algorithme pour résoudre ce problème s’appelle Flood Fill.Les buts de ce projets sont :• Écrire un algorithme utilisant une pile pour résoudre ce problème,• Ré-écrire le même programme en utilisant la récursivité.• Évaluer la complexité en temps et en espace des deux algorithmes.

O Algorithme non récursif

La fonction floodFillPile prends en entrée :• l’image img (un 3d-array donc),• la couleur de remplissage (une liste de trois entiers r,g,b de [[0,255]]).• le pixel (x,y) (deux entiers)On utilise une pile de pixel (ie de couple d’entiers de [[0,n−1]]× [[0,m−1]]) de la manière suivante :• On initialise la pile avec le pixel (x,y).• À chaque itération, on dépile un pixel de la pile si il est blanc, il passe à la couleur demandé et on empile tous les

voisins.• On continue ainsi jusqu’à ce que la pile soit vide.

Compléter le script fourni en écrivant la fonction floodFillPile

R Il y a donc un voisins pour chaque direction (nord, sud, ouest, est), pensez à indiquer dans vos commentaires quels voisinsvous traitez. Bien sûr : attention aux bords ! Certains pixels ont 4 voisins, d’autres 3 ou 2.

88

O L’algorithme récursifOn va reprendre l’algorithme précédent sans utiliser de pile mais avec la récursivité.

Le principe de l’algorithme récursif est le suivant : on utilise une fonction floodFillRec qui prends en entrée :• l’image img (un 3d-array donc),• la couleur de remplissage (une liste de trois entiers r,g,b de [[0,255]]).• le pixel (x,y) (deux entiers)Cette fonction ne sort aucune valeur mais modifie l’objet image.Étant donné ces valeurs :• si le pixel (x,y) n’est pas blanc (noir ou déjà colorié), la fonction s’arrête sans rien faire.• sinon le pixel (x,y) est mis à la couleur demandé, puis la fonction s’appelle elle-même pour colorier les voisins.

Compléter le script fourni en écrivant la fonction floodFillRec. Tester.

O Les fichiers fournisVous disposez d’un script à compléter et d’une image de test.Plus précisément, vous devez compléter les fonctions floodFillPile et floodFillRec, puis décommenter et modifier

les instruction situées en dessous qui colorie les zones.Le résultat obtenu s’affiche et peut être sauvegardé.

Utilisez les options d’exécution ([F6]) suivantes : dans un interpréteur dédié , option interagir avec l’interpréteuraprès exécution .

! Attention à la taille maximale de la pile de récursion. En particulier, expliquer pourquoi l’algorithme ne peut pasfonctionner depuis le pixel central.

O Évaluation de la complexité en temps et en espacePour évaluer la complexité, on applique l’algorithme à une image carrée [[0,n−1]]× [[0,n−1]] en considérant que tous

les pixels sont blancs.On évalue alors le nombre de test effectué en fonction de n.

1. Évaluer le nombre de test avec la méthode récursive et le nombre d’appel de la fonction. À quoi sert l’instruction :sys.setrecursionlimit(valeur) ? Quelle valeur choisir ? Comment la modifier pour adapter cet algorithme à uneautre taille d’image.

2. Évaluer le nombre de test avec la méthode non récursive, évaluer la taille de la pile avec la méthode non récursive.3. Proposer quelques idées pour améliorer ces algorithmes.

Indiquez vos réponses sous la forme de commentaire (en doc string ) à la fin de votre script.Correction : Voici un exemple de solutions :

# -*- coding : utf -8 -*-2

## librairies4 from scipy.misc import imread , imsave

from numpy import shape6 from pylab import imshow , show

import sys8

#print (" ancienne recursion limite :", sys. getrecursionlimit ())10 #sys. setrecursionlimit (14000)

#print (" recursion limit :", sys. getrecursionlimit ())12

# somme des composantes chromatiques pour un pixel blanc14 # un pixel dont la somme des composantes chromatiques est

# supé rieure à cette valeur est blanc.16 SOM_BLANC = 250*3

SOM_NOIR = 10*318

20 # fonctions à écriredef floodFillRec (img , r,g,b, x,y):

22 """

89

entrée: img = 3d-array nxmx324 = image

r,g,b = 3 entiers26 = couleurs à remplir

x,y = 2 entiers de [|0,n -1|]x[|O,m -1|]28 = pixels de l’image

sortie : rien : img est modifi é durant le processus30 """

estBlanc = ( int(img[x,y ,0]) + int(img[x,y ,1]) + int(img[x,y ,2]) >= SOM_BLANC )32

if not( estBlanc ) :34 return

36 img[x,y,0], img[x,y,1], img[x,y ,2] =r,g,b

38 [n,m,c] = shape(img)if x<n-1 : # sud

40 floodFillRec (img , r,g,b, x+1,y)if y<m-1 : # est

42 floodFillRec (img , r,g,b, x,y+1)if x > 0 : # nord

44 floodFillRec (img , r,g,b, x-1,y)if y > 0 : # ouest

46 floodFillRec (img , r,g,b, x,y -1)return

48

def floodFillPile (img , r,g,b, x,y):50 """





pile= [[x,y]]60 while pile != [] :

[x,y] = pile.pop ()62 estBlanc = ( int(img[x,y ,0]) + int(img[x,y ,1]) + int(img[x,y ,2]) >= SOM_BLANC )

64 if estBlanc :img[x,y,0], img[x,y,1], img[x,y ,2] =r,g,b

66

[n,m,c] = shape(img)68 if x<n-1 : # sud

pile. append ([x+1,y])70 if y<m-1 : # est

pile. append ([x,y+1])72 if x > 0 : # nord

pile. append ([x-1,y])74 if y > 0 : # ouest

pile. append ([x,y -1])76 return

78

##code:80 img = imread (" dessinFloodFillTest .png")

82 [n,m,c] = shape(img)print(" taille de l image :"+str(n)+"x"+str(m)+"x"+str(c))

84 print(" exemple de valeur d un pixel:"+str(img[n//2, m//2 ,0]))print("le type de donnée d un pixel est "+ str(type(img[n//2, m//2 ,0]) ))

90

86

# floodFill = floodFillRec88 # ou alors:

floodFill = floodFillPile90

## met du rouge dans le cercle en haut à gauche :92 floodFill (img , 255, 0 ,0 , n//4, m//4)

## met du jaune dans le cercle intérieur bas gauche94 floodFill (img , 255, 255 ,0 , n//4, 3*m//4)

floodFill (img , 0, 255 ,255 , n//2, 3*m//4)96 floodFill (img , 128, 128 ,255 , 8*n//10 , m//8)

floodFill (img , 255, 128 ,128 , 8*n//10 , 2*m//8)98 floodFill (img , 128, 255 ,0 , n//20 , 3*m//4)

100 ## pixel central : le plus long à faire:# floodFill (img , 255, 255 ,128 , n//2, m//2)

102 # petit coin en bas à gauche :floodFill (img , 64, 255 ,128 , n-1, 0)

104

imshow (img)106 show ()

# imsave (img , "out.png ")

Pour ceux qui veulent voir une version complète :

1 # -*- coding : utf -8 -*-

3 ## librairiesfrom scipy.misc import imread , imsave

5 from numpy import shapefrom pylab import imshow , show , ginput

7 import sysprint(" ancienne recursion limite :", sys. getrecursionlimit ())

9 sys. setrecursionlimit (14000)print(" recursion limit:", sys. getrecursionlimit ())

11 # somme des composantes chromatiques pour un pixel blanc# un pixel dont la somme des composantes chromatiques est

13 # supé rieure à cette valeur est blanc.SOM_BLANC = 250*3

15 SOM_NOIR = 10*3

17 ## constantes nomméesCOULEUR =(

19 [ "rouge", [255 ,0 ,0]] ,["vert" , [0 ,255 ,0]] ,

21 ["bleu" , [0 ,0 ,255]] ,["jaune", [255 ,255 ,0]] ,

23 [" violet ", [255 ,0 ,255]] ,["cyan", [0 ,255 ,255]] ,

25 ["noir", [0 ,0 ,0] ],[" sortie ", [-1,-1,-1] ]

27 )

29

## fonctions fournies31 def clicAPoint (img ):

print(" cliquez un point sur la figure ")33 imshow (img)

[(xc ,yc)] = ginput (1)# clic un point et récupère ses coordonn ées35 xc= int(xc); yc=int(yc) # par défaut les coordonn ées sont float

print("point cliqué:"+str(xc)+","+str(yc))37 return yc ,xc

39 def chooseColor ():

91

print(" choisir une couleur :")41 for i in range(len( COULEUR )):

coul = COULEUR [i][0]43 print(str(i) +" :"+coul)

choix = int( input("choix?"))45 return ( COULEUR [choix ][1])

47 # fonctions à écriredef floodFillRec (img , r,g,b, x,y):

49 """entrée: img = 3d-array nxmx3

51 = imager,g,b = 3 entiers

53 = couleurs à remplirx,y = 2 entiers de [|0,n -1|]x[|O,m -1|]

55 = pixels de l’imagesortie : rien : img est modifi é durant le processus

57 """estBlanc = ( int(img[x,y ,0]) + int(img[x,y ,1]) + int(img[x,y ,2]) >= SOM_BLANC )

59

if not( estBlanc ) :61 return

63 img[x,y,0], img[x,y,1], img[x,y ,2] =r,g,b

65 [n,m,c] = shape(img)if x<n-1 : # sud

67 floodFillRec (img , r,g,b, x+1,y)if y<m-1 : # est

69 floodFillRec (img , r,g,b, x,y+1)if x > 0 : # nord

71 floodFillRec (img , r,g,b, x-1,y)if y > 0 : # ouest

73 floodFillRec (img , r,g,b, x,y -1)return

75

def floodFill (img , r,g,b, x,y):77 """





pile= [[x,y]]87 while pile != [] :

[x,y] = pile.pop ()89 estBlanc = ( int(img[x,y ,0]) + int(img[x,y ,1]) + int(img[x,y ,2]) >= SOM_BLANC )

91 if estBlanc :img[x,y,0], img[x,y,1], img[x,y ,2] =r,g,b

93

[n,m,c] = shape(img)95 if x<n-1 : # sud

pile. append ([x+1,y])97 if y<m-1 : # est

pile. append ([x,y+1])99 if x > 0 : # nord

pile. append ([x-1,y])101 if y > 0 : # ouest

pile. append ([x,y -1])

92

103 return##code:

105 img = imread (" dessin .png")print(shape(img ))

107

x,y = clicAPoint (img)109 r,g,b = chooseColor ()

while r != -1 :111 floodFill (img , r,g,b, x,y)

x,y = clicAPoint (img)113 r,g,b = chooseColor ()

115

print(" ----FIN ------ ( fermez la fenetre pour quitter )")117 imshow (img)

show ()

93

Simulation de propagation de maladiePelletier Sylvain PC, Lycée Descartes

Au temps t = 0, on introduit dans une population d’une espèce donnée un certain nombre d’individus porteurs d’unemaladie contagieuse.

La population se décompose en 3 catégories :• les individus sains (qui n’ont pas encore eu la maladie et peuvent la contracter),• les individus infectés (qui peuvent transmettre la maladie)• et les individus résistants (qui ont eu la maladie, sont guéris et ne peuvent plus la contracter ni la transmettre).

On note respectivement S(t), I(t), R(t) les proportions de population saine, infectée, résistante en fonction du temps.Leur somme vaut toujours 1, et initialement R(0) = 0, I(0) = I0 ∈]0,1[, donc S(0) = 1− I0.On fait les hypothèses suivantes :• la quantité d’individus infectés par unité de temps est proportionnelle au produit IS, (probabilité de rencontre d’un

individu sain et d’un individu infecté)• la quantité d’individus qui guérissent par unité de temps est proportionnelle à I.

Avec ces hypothèses, l’évolution de la maladie est régie par le système d’équations différentielles suivant :

(Σ)

S′(t) = −rI(t)S(t)I′(t) = rI(t)S(t)−aI(t)R′(t) = aI(t)

r et a sont des constantes (respectivement le taux de contagion et le taux de guérison).

On admet que le système (Σ) a une unique solution (dès qu’on impose une condition initiale). Mais il n’existe pas deformule pour la calculer. On va donc utiliser une méthode de résolution numérique approchée.

Résolution numérique : on utilisera la méthode d’Euler, qui consiste à approximer, pour un ∆t suffisamment petit,f (t +∆t) par f (t)+ f ′(t)∆t (cela revient à remplacer la fonction par son DL d’ordre 1).

Par exemple, comme S′(t) =−rI(t)S(t), on posera S(t +∆t) = S(t)− rI(t)S(t)∆t.On admet que cette méthode est convergente, c’est-à-dire si ∆t tend vers 0, alors les valeurs calculées grâce à cette

approximation convergent vers la solution exacte du système (Σ).1. On note sn = S(n∆t), in = I(n∆t) et rn = R(n∆t) (n ∈ N, ∆t : réel > 0 fixé)

Écrire les relations de récurrence vérifiées par les 3 suites (sn), (in), (rn) obtenues en appliquant la méthode expliquéeci-dessus.

2. Écrire une fonction SIR(I0,r,a,N,Dt) qui calcule trois array unidimensionnel de taille N : S, I et R contenant lestermes d’indice 0 à N−1 des suites (sn), (in) et (rn) respectivement, calculés par cette méthode.Les paramètres de cette fonction sont :• I0 : proportion initiale d’individus contaminés (I0)• r, a : taux de contagion et taux de guérison• N : nombre de termes de la suite à calculer• Dt : ∆t (pas de temps)

Le dernier terme calculé correspond donc à l’instant (N−1)∆t.3. En utilisant la fonction represente écrite ci-dessous, écrire un script permettant de déterminer l’évolution de la

maladie (présence ou non d’un pic de contamination, proportion finale d’individus qui ont eu la maladie).On prendra ∆t = 0.1 et N suffisammment grand pour que les valeurs de

S, I,R se stabilisent (essayer par exemple N = 100, et plus si ça ne suffit pas)

On essaiera successivement :• r = 0.3, a = 1, I0 = 0.1 (faible taux de contagion)• r = 2, a = 0.7, I0 = 0.1 (fort taux de contagion)• r = 2, a = 1, I0 = 0.01 (fort taux de contagion, nombre initial d’individus contaminés plus faible)

95

Correction : On applique classiquement la méthode d’Euler explicite.

1 # -*- coding : utf -8 -*-

3

"""5 Auteur : Sylvain Pelletier

Modé lisation d’une épidémie.7 Ré solution d’é quation diffé rentielle avec la méthode d’Euler

"""9

# Modules et fonctions import és11 # ##############################

from pylab import *13

# Fonctions15 # ##########

def SIR(I0 ,r,a,N,Dt) :17 """

entrée: I0 = float = proportion de personnes infect és à t=019 r = float = taux de contagion

a = float = taux de guérison21 N = int = nbr de points

Dt = float = pas de temps23 sortie : R,I, S = trois array unidimensionnel de taille N

= proportion de résistants , infect és et sains au cours du temps25 """

R = zeros(N, float)27 I = zeros(N, float)

S = zeros(N, float)29

I[0] = I031 R[0] = 0

S[0] = 1-I033

for t in range(N -1):35 S[t+1] = S[t] - Dt*r*I[t]*S[t]

I[t+1] = I[t] + Dt*(r*I[t]*S[t] - a*I[t])37 R[t+1] = R[t] + Dt*a*I[t]

return ([S,I,R])39

def represente (S,I,R,Dt):41 """

entrée: S,I,R = des array unidimensionnels de taille N43 = é volution du taux de résistants , infect és et sains pour les temps 0 à

(N -1) DtDt = réel = pas de temps

45 sortie : graphique montrant l’é volution de S I et R en fonction du temps"""

47 N = len(S)xmin = 0

49 xmax = (N -1)* Dtx= linspace (xmin , xmax , N)

51 plot(x,S)plot(x,I)

53 plot(x,R)axis ([xmin ,xmax ,-0.1, 1.1])

55 grid ()show ()

57 return ()

59 # Code:# ######

96

61 Dt = 0.1[S,I,R] = SIR (0.01 , 2, 0.5, 100,Dt)

63 represente (S,I,R, Dt)

97

Simulation numérique des oscillations d’un pendulePelletier Sylvain PC, Lycée Descartes

Le but de ce projet est de simuler numériquement les oscillations d’un pendule pesant simple.Il s’agit d’un petit objet pesant accroché à un fil (ou une tige) de masse négligeable devant celle de l’objet. Déplacé de sa

position d’équilibre (stable) dans laquelle le centre de gravité est à la verticale de l’axe, le solide se met à osciller de part etd’autre de cette position dite d’équilibre.

On repère le solide par l’angle θ(t) entre le fil et la verticale à l’instant t, on note θ0 l’angle initial.

La physique nous apprend que la fonction θ vérifie l’équation différentielle :

θ′′+

gl

sin(θ) = 0,

où g est la gravité, et l la longueur.La valeur de θ(0) = θ0 est supposée connue, et on suppose la vitesse initiale θ ′(0) nulle.De plus, on sait que g = 9,81 (sur terre) et on prendra la longueur égale à 1.Enfin, on a une estimation de la période des oscillations, en considérant la période pour de petites oscillations :

T0 = 2π

√gl .

Il n’y a pas de solution analytique à cette équation en dehors de l’approximation des petites angles.

En mathématiques pour résoudre numériquement ce type d’équation différentielle, on commence par la transformer en uneéquation d’ordre 1, en posant comme inconnue la fonction :

x :

R → R2

t 7→[x1(t),x2(t)

]=[θ(t),θ ′(t)

]On a alors :

x′ =[θ′,θ ′′

]=[x2,−

gl

sin(x1)]= f (x).

Cette manipulation nous a ramené à une équation différentielle du premier ordre, du type x′ = f (x), avec

f :

R2 → R2

(x1,x2) 7→[x2,−g

l sin(x1)]

On a donc obtenu une équation de degré 1, en augmentant la dimension de l’inconnue, puisqu’ici l’inconnue est unefonction de R dans R2.

Pour résoudre numériquement l’équation différentielle on considère n points et un pas de temps ∆. On pose alors ti = i∆ .On se propose alors de donner une valeur approchée de (x(ti))i=0...n−1, noté Xi. Chacune de ces valeurs sont un élément

de R2.Ces valeurs seront stockés dans un array à n lignes et 2 colonnes. La ligne i est l’approximation des deux composantes

de x(ti), c’est-à-dire de :[θ(ti),θ ′(ti)

]Une valeur raisonnable du pas de temps est : T

100 , avec T la période des petites oscillations, ce qui fait donc environ 100points par période. Avec n = 1000 points, on espère ainsi observer 10 oscillations du pendule.

La méthode consiste à• poser X0 égal aux conditions initiales, c’est-à-dire :

[θ0,0

], donnée que l’on suppose connue.

• Puis, calculer Xi+1 à partir de Xi en utilisant une approximation de f ′(x(ti)) :

99

Nous allons comparer deux méthodes : la méthode d’Euler et celle de Runge et Kutta. Vous disposez d’une script àcompléter, qui permet l’affichage des oscillations (sous la forme d’une animation) et du diagramme de phase.

Résolution par la méthode d’Euler expliciteLa méthode d’Euler explicite consiste à poser :

f ′(x(ti))≈f (x(ti+1))− f (xi)

h.

Exercice 11. Exprimer alors Xi+1 en fonction de Xi. À chaque fois, c’est deux composantes qu’il faut déterminer.2. Écrire une fonction euler(theta_0,n,Delta) qui calcule à partir des entrées un array à n lignes et deux

colonnes X donnant les valeurs approchées par la méthode d’Euler.3. Tester avec le script fourni.

Pour retrouver plus facilement la forme du cours, on peut utiliser une fonction f prenant en entrée un array unidimen-sionnel de taille 2 x de taille 2 et calculant un array unidimensionnel (toujours de taille 2) f (x).

Cette fonction s’écrit simplement :

def f(x) :"""entrée: x = array unidmensionnel de taille 2

= (theta(t), theta ’(t))sortie : y = array unidmensionnel de taille 2

= (theta(t), theta ’’(t))= (theta(t), -GRAV/LONG*sin(theta(t)))

"""x1 , x2 = xreturn array( (x2 , -GRAV/LONG*sin(x1)) )

Cette fonction est écrite dans le script.

Exercice 2 Modifier votre programme pour utiliser la fonction f.On utilisera des opérations d’array du type :

X[i+1, : ] = X[i, :] + Delta * f(X[i ,:])

Résolution par la méthode de Runge et Kutta (RK4)La méthode de Runge et Kutta à 4 points consiste à approximer l’intégrale en passant par deux approximations du point

milieu x(ti + ∆

2

), i.e. du centre de l’intervalle [ti, ti+1].

On calcule alors :• tmp1, première approximation de x

(ti + ∆

2

)(point milieu).

• tmp2, deuxième approximation de x(ti + ∆

2

).

• tmp3, une approximation de x(ti+1) (point final).Le calcul est effectué selon :• la première approximation tmp1, est obtenue en utilisant la méthode des rectangles à gauche à l’intervalle

[ti, ti + ∆

2

].

On obtient alors :

tmp1 ≈x(

ti +∆

2

)=x(ti)+

∫ ti+ ∆

2

tif (x(t))dt

≈x(ti)+∆

2f (x(ti))

≈Xi +∆

2f (Xi).

100

On a ainsi une approximation du point milieu.• On fait alors une autre approximation en utilisant cette fois la méthode des rectangles à droite sur le même intervalle, et

en se servant de la valeur de tmp1 comme approximation du point milieu :

tmp2 ≈x(

ti +∆

2

)=x(ti)+

∫ ti+ ∆

2

tif (x(t))dt

≈x(ti)+∆

2f(

x(ti +∆

2)

)≈Xi +

∆

2f (tmp1).

On a ainsi une deuxième approximation de la valeur de x(ti + ∆

2

).

• Enfin, on calcule une approximation du point final x(ti+1), par la méthode du point milieu en utilisant comme valeur dupoint milieu tmp2 :

tmp3 ≈x(ti+1)

=x(ti)+∫ ti+1

tif (x(t))dt

≈x(ti)+∆ f(

x(ti +∆

2)

)≈Xi +∆ f (tmp2).

L’approximation finale est alors :

Xi+1 ≈x(ti+1)

=x(ti)+∫ ti+1

tif (x(t))dt

≈x(ti)+∆

6

(f (x(ti))+4 f (x(ti +

∆

2))+ f (x(ti+1))

)≈Xi +

∆

6( f (Xi)+2 f (tmp1)+2 f (tmp2)+ f (tmp3))

Exercice 31. Écrire une fonction X=RK(theta_0,n,Delta) qui calcule à partir des entrées une matrice X à deux colonnes et n

lignes, la ligne i étant l’approximation de(

x(ti),x′(ti))

.2. Tester à l’aide du script fourni.

Exercice 4 Recommencer avec le pendule simple amorti, dont l’équation est :

θ′′+λθ

′+gl

sin(θ) = 0,

Correction : voici un exemple de correction :

1 # -*- coding : utf -8 -*-

3

"""5 Auteur : Sylvain Pelletier

simulation du mouvement d’un pendule7 """

101

9 # compatibilit é V2 et V3:from __future__ import print_function , division , unicode_literals

11 import sysif sys. version_info .major <= 2 :

13 input = raw_input

15

# Modules et fonctions import és17 # ##############################

from pylab import *19 from modulePyzoPendule import represente , planPhase

21 # Fonctions# ##########

23 GRAV = 9.81LONG = 1.

25 LAMBDA = 0

27 def f(x) :"""

29 entrée: x = array unidmensionnel de taille 2= (theta(t), theta ’(t))

31 sortie : y = array unidmensionnel de taille 2= (theta(t), theta ’’(t))

33 = (theta(t), -GRAV/LONG*sin(theta(t)))"""

35 [x1 ,x2] = xreturn (array ([x2 , - LAMBDA *x2 -GRAV/LONG*sin(x1 )]))

37

39 def euler(theta_0 ,n,Delta ):"""

41 entrée: theta_0 = float = angle initialn = int = nbr de points

43 Delta = float = pas de tempssortie : X = array à n lignes et 2 colonnes .

45 = la ligne i est l’approximation de [theta(t_i), theta ’(t_i )]"""

47 X=zeros ((n,2), float)X[0 ,:] = [ theta_0 , 0] # condition initiale

49 for i in range(n -1) :X[i+1, : ] = X[i, :] + Delta * f(X[i ,:])

51 return (X)

53 def RK(theta_0 ,n,Delta ):"""

55 entrée: theta_0 = float = angle initialn = int = nbr de points

57 Delta = float = pas de tempssortie : X = array à n lignes et 2 colonnes .

59 = la ligne i est l’approximation de [theta(t_i), theta ’(t_i )]"""

61 X=zeros ((n,2), float)X[0 ,:] = [ theta_0 , 0] # condition initiale

63 for i in range(n -1) :tmp1 = X[i ,:] + Delta* f( X[i ,:] ) /2

65 tmp2 = X[i ,:] + Delta* f(tmp1) /2tmp3 = X[i ,:] + Delta* f(tmp2)

67 X[i+1 ,:] = X[i ,:] + Delta /6*( f(X[i ,:] ) +2*f(tmp1) + 2*f(tmp2) + f(tmp3) )return (X)

69

71

102

# Code:73 # ######

T = 2* pi*sqrt(GRAV/LONG)75 #X = euler(pi/4, 1000 , T /1000)

X = RK(pi/4, 1000 , T /1000)77 ani= represente (X[: ,0])

show ()79 planPhase (X)

103

Modèle proie-prédateurPelletier Sylvain PC, Lycée Descartes

Le système proies-prédateurs st régi par les équations de Volterra qui forment le système non linéaire :x′ = ax−bxyy′ = −cy+dxy

où (a,b,c,d) sont des réels strictement positifs.

L’interprétation est que x représente la population de la proie, et y la population de prédateur.En l’absence de prédateur, la population de x grandit (par les naissances) par un modèle malthusien. De même en l’absence

de proie, la population de y diminue par un modèle malthusien. On ajoute un terme à chaque évolution proportionnel à larencontre entre une proie et un prédateur.

On admet le résultat suivant : ce système admet des solutions qui sont toujours positives et qui sont périodiques.

O Utilisation de la méthode d’Euler explicite

On propose de résoudre ces équations (dont on ne connaît pas la solution analytique) par la méthode d’Euler explicite.On considère alors l’intervalle de temps [0,T ], que l’on discrétise en n valeurs ti = T i

n−1 . Le pas de temps est donc∆ = T

n−1 .On cherche des listes X et Y de taille n, telle que :

X[i]≈ x(ti) et Y[i]≈ y(ti)

Q 1 Donner X[i+1] en fonction de X[i] et Y[i] en utilisant la méthode d’Euler explicite. Idem pour Y[i+1].Q 2 Écrire un programme correspondant à la méthode d’Euler.

On choisira comme valeurs :

T = 20n = 200X[0] = 1.5Y[0] = 2a, b, c, d = 1, 1, 1, 1 # tester plusieurs valeurs

Q 3 Tester et interpréter : est-ce que la méthode d’Euler explicite donne un résultat satisfaisant ?

Pour tester, on pourra :1. Représenter x et y sur le même graphique, par les commandes :

plot(X, color="red")plot(Y, color="green")show ()

2. Représenter la courbe paramétrée par :

plot(X,Y)show ()

Q 4 Pour préparer la suite : on considère z la fonction de [0,T ] dans R2 :

z : t 7−→(

x(t),y(t))

Écrire l’équation z′ = f (z) vérifiée par cette fonction.Q 5 Écrire la fonction f. On prendra en entrée et en sortie un 1d array de taille 2.

Correction : pour la méthode d’Euler, on peut simplement faire :

105

from matplotlib . pyplot import plot , show2

a, b, c, d = 1, 1, 1, 1 # tester plusieurs valeurs4 n = 200

T = 206 Delta = T/(n -1)

8 # initialisation des listesX = [0]*n

10 Y= [0]*nX[0] , Y[0]= 1.5, 2

12

for i in range(n -1) :14 X[i+1] = X[i] + Delta *(a*X[i] - b*X[i]*Y[i])

Y[i+1] = Y[i] + Delta *(-c*Y[i] + d*X[i]*Y[i])16 plot(X, color="red")

plot(Y, color="green")18 show ()

20 plot(X,Y)show ()

O Méthode de HeunLa méthode de Heun pour résoudre l’équation différentielle z′ = f (z) consiste à poser, zi étant connue :

fi = f (zi) zi étant connu

fi+1 = f (zi +∆ f (zi)) approximation de f (z(ti+1))

zi+1 =zi +∆

2( fi + fi+1)

Q 6 Tester cette méthode et la comparer à celle d’Euler.On construira un 2d-array de taille (n,2) : la ligne i contenant les approximations de (x(ti),y(ti)).

R Essayez d’écrire les formules fi+1 = f (zi +∆ f (zi)) avec des opérations sur les array.

Pour Afficher, on pourra utiliser :

plot ( Z [: ,0] , color = " red " )plot ( Z [: ,1] , color = " green " )show ()plot ( Z [: ,0] , Z [: ,1])show ()

Correction : pour la méthode de Heun, on peut faire :

1 from matplotlib . pyplot import plot , showfrom numpy import array , zeros

3

a, b, c, d = 1, 1, 1, 1 # tester plusieurs valeurs5 n = 200

T = 207 Delta = T/(n -1)

9 # initialisation des listesZ = zeros ((n ,2))

11 Z[0] = [ 1.5, 2 ]

13 def f(Z) :"""

15 entrée: Z = 1d -array de taille 2= valeur de (x,y)

17 sortie : out = 1d -array de taille 2

106

= valeur de f(x,y)19 """

x,y = Z21 return array( [ a*x - b*x*y, -c*y + d*x*y])

23 for i in range(n -1) :fi = f(Z[i ,:])

25 fip1 = f( Z[i ,:] + Delta * f(Z[i ,:]))Z[i+1, : ] = Z[i ,:] + Delta /2 * (fi + fip1)

27

plot(Z[:,0], color="red")29 plot(Z[:,1], color="green")

show ()31

plot(Z[:,0],Z[: ,1])33 show ()

107

Vocabulaire des bases de donnéesOpérateurs usuels sur les ensembles dansun contexte de base de donnéesOpérateurs de l’algèbre relationnelleAgrégations et fonctions d’agrégationSéquence complète en SQLExemples de requêtes MySQL

5 — Révisions sur les bases de données

Dans ce chapitre, on revoit ce qu’il faut savoir sur les bases de données.Volontairement, on choisit une présentation différente de celle du cours de première

année.

I Vocabulaire des bases de donnéesLe but des bases de données est de gérer de l’information : on souhaite stocker etmanipuler beaucoup d’information et rapidement.

Cette information concerne des entités qui sont liées entre elles. Ces entités sontalors stockées séparément dans des tableaux et on souhaite facilement recouper /mélanger plusieurs tableaux (requêtes croisées).

Exemple I.1 Si on souhaite gérer un site de vente en ligne, on a dans un premiertemps trois types d’entités : les objets vendus, les clients, les fournisseurs.

Les liaisons entre ces entités sont les achats (les clients achètent des objets) et lescommandes (les fournisseurs vendent des produits).

Les achats et les commandes seront donc d’autres entités que l’on devra gérer.On aura donc 5 entités.

En pratique, les données sont stockées physiquement sur un serveur externe.Sur ce serveur est installé un système de gestion de base de données.Le programmeur utilise le client pour envoyer des ordre de recherche ou de

modification d’une base de données qui sont transmises au serveur.On parle de requêtes pour désigner ces ordres de demande d’information en-

voyés au serveur de données.C’est l’architecture client-serveur.

En pratique, on utilise le plus souvent une architecture trois-tiers.

Exemple I.2 Toujours pour un site de vente en ligne, on a trois niveaux :

110 Révisions sur les bases de données

• le navigateur internet installé sur l’ordinateur personnel de la personne quiconsulte le site de chez elle, envoie une demande pour consulter une page, parexemple la liste des articles à moins de 30 euros.• Cette demande est transmise par le formulaire HTML au serveur web, qui la

transforme en requête pour le serveur de données,• le serveur de données envoie les informations au serveur web, qui construit la

page web correspondante,• enfin, cette page s’affiche sur le navigateur internet.

Ceci permet d’avoir un système multi-utilisateur (plusieurs personnes consultentle site internet en même temps) et robuste (pour les problèmes de sécurité d’accès auxdonnées).

Un attribut d’une entité (ou colonne) désigne une caractéristique d’une entité.Cet attribut corresponds à un type de données que l’on appelle domaine.

On appelle relation (ou table) un tableau avec des attributs d’un objet surchaque ligne.

On appelle clé primaire d’une relation, un attribut tel que deux objets distinctsde cette relation ont une clé primaire différente. Ainsi, un objet de cette relation estentièrement déterminée par sa valeur de l’attribut clé primaire. On peut dire que laclé primaire est un identifiant unique des objets de la relation.

R Le mot attribut est donc synonyme de caractéristique pour les bases de données.

Exemple I.3 Toujours dans l’exemple du site marchand.

On a donc 5 tables :

• La table client a pour colonnes le nom, le prénom, la date de naissance, la datedu dernier achat, l’adresse postale.Pour clé, on peut choisir le triplet nom , prénom, date de naissance. En pratique,on ajoute une première colonne numéro de client, qui sert de clé primaire, chaqueclient ayant un numéro unique.• La table des objets auront pour colonnes un numéro unique, un nom, un prix, un

fournisseur.• La table des fournisseurs auront pour colonnes un identifiant unique, une adresse,

un téléphone.• La table des achats contiendra le numéro du client, le numéro de l’objet, la

quantité et la date.• La table des commandes contiendra le numéro de l’objet, le numéro du fournis-

seur, la quantité et la date.

Lorsqu’on crée une table, on indique quelle est la clé primaire.Le système de gestion de base de données incrémente automatiquement cette

valeur de 1 à chaque nouvelle entrée.

II Opérateurs usuels sur les ensembles dans un contexte de base dedonnées 111

II Opérateurs usuels sur les ensembles dans un contexte de basede données

Étant donnée deux relations R1 et R2, on peut utiliser les opérations suivantes :• l’union R1∪R2. On écrit R1 UNION R2.• l’intersection R1∩R2. On écrit R1 INTERSECT R2.• la différence ensemblisteR1 \R2. On écrit R1 MINUS R2.

Exemple II.1 Si on considère deux magasins d’une même société maintenant, onpeut chercher :• les clients de l’un ou l’autre magasin (union de deux relations),• les objets qui sont dans les deux magasins (intersection de deux relations),• les clients du magasin 1 qui ne sont jamais allé dans le magasin 2 (différence de

deux relations).

R Dans le langage MySQL, UNION existe, mais ni INTERSECT, ni MINUS.

Si un élément est présent dans R1 et R2, on peut distinguer UNION ALL quigarde les deux éléments, et UNION DISTINCT (ou simplement UNION) qui n’engarde qu’un.

III Opérateurs de l’algèbre relationnelle

Étant donnée une relation R, on dispose des opérations suivantes :• la projection consiste à ne garder que quelques attributs d’un objet. Le mot

clé pour la projection s’appelle SELECT. La syntaxe est :

SELECT attribut1 , attribut2 FROM nomTable ;

ou pour prendre tous les attributs :

SELECT * FROM nomTable ;

• la sélection (ou restriction) consiste à ne garder que les objets qui vérifientdes conditions données. Le mot clé pour la sélection s’appelle WHERE suivipar les conditions. La syntaxe est :

SELECT attributs FROM nomTable WHERE condition ;

• le renommage consiste à changer le nom d’un attribut. Le mot clé pour lerenommage s’appelle AS suivi par le nouveau nom de l’attribut.La syntaxe est :

SELECT oldName1 AS newName1 , oldName2 AS newName2FROM nomTable WHERE condition ;

! Le mot clé SELECT fait une projection et non une sélection ! En fait on faitgénéralement une sélection suivi d’une projection, d’où l’utilisation de ce motclé.


Une projection ne permet d’avoir une relation, dans le sens où les élémentsobtenus ne sont pas nécessairement distincts. Pour ne garder que les élémentsdistincts, il faut utiliser le mot clé DISTINCT

Exemple III.1 Pour récupérer les noms des clients, on fait :

SELECT nom FROM clients ;

Pour récupérer les noms et prénoms des clients ayant fait leur dernier achat avant le 1erjanvier 2016 :

SELECT nom , prenoms FROM clientsWHERE date_dernier_achat < ’2016 -01 -01 ’ ;

Autre exemple :

SELECT nom , prenoms FROM clientsWHERE date_anniversaire = CURDATE ();

avec CURDATE() est une fonction MySQL qui renvoie la date d’aujourd’hui.Si il y a des homonymes dans les clients (ou qu’un client est susceptible d’être

enregistré deux fois), on peut faire :

SELECT DISTINCT nom , prenoms FROM clients

Ou pour voir les jours où il y a eu des achats :

SELECT DISTINCT date_dernier_achat FROM clients

. Les conditions que l’on peut faire sont classiques : égalité (avec =), comparaisonavec > et >=.Ressemblance des chaînes de caractères avec LIKE (à la limite du programme,on peut utiliser des systèmes de comparaison de caractères très sophistiqué).Tout est prévu pour la comparaison des dates (la syntaxe est un peu complexe etsera rappelée dans le sujet).On peut combiner les relations avec AND et OR ou NOT.

. Si besoin, on peut trier les résultats en utilisant ORDER BY attribut ou ORDERBY attribut DESC. On peut mettre plusieurs attributs.On peut n’afficher que quelques résultats avec LIMIT.

Exemple III.2 Pour afficher la liste des 10 derniers clients :

SELECT nom , prenoms FROM clientsORDER BY date DESC LIMIT 10;

R L’utilisation du renommage est peu claire tant que l’on utilise des petites basesde données.

III Opérateurs de l’algèbre relationnelle 113

O Les jointuresLes jointures permettent de mélanger de relations (des tables) et donc de faire des

requêtes croisées. La jointure la plus simple (et en pratique peu utilisée) est le produitcartésien : à partir d’une table tab1 de n objets notés (xi) d’une autre table tab2 dem objets notés (y j), on construit une liste de n×m objets de la forme

(xi,y j

)pour

i ∈ [[1,n]] et j ∈ [[1,m]].

Exemple III.3 On peut considérer le produit cartésien des clients et des achats :

SELECT clients .id , clients .nom , commandes .id_client ,commandes .id_objet , commandes . quantiteFROM clients , commandes ;

Cela crée une liste des nom des clients et des commandes (qui peuvent être faits pard’autres clients). Cela n’a bien sûr aucun intérêt en pratique.

Par contre, si on filtre en ne gardant que les lignes où l’identifiant client (dans latable clients) est celle de l’identifiant client dans la table commandes :

SELECT clients .id , clients .nom , commandes .id_client ,commandes .id_objet , commandes . quantiteFROM clients , commandesWHERE commandes . id_client = clients .id ;

Alors, là on obtient ce qui est attendu : chaque ligne corresponds à une commanded’un client.

On voit sur l’exemple que ce qui est intéressant en pratique c’est de faire un produitcartésien suivi d’une sélection en ne gardant que les lignes qui se correspondent dansles deux tables. C’est le principe d’une jointure symétrique que l’on va utiliser.

O La jointure symétriqueLa jointure symétrique consiste à combiner deux tables en ne gardant que leséléments qui ont une caractéristique en commun.

Très souvent c’est une clé primaire qui est identique.La syntaxe est :

SELECT attributs FROM tableAJOIN tableB ON tableA .att1 = tableB .att2

La liste obtenue est alors le croisement entre la table A et la table B.

C’est bien sûr plus rapide que de faire un produit cartésien puis de faire une sélection,mais c’est équivalent.

Exemple III.4 Pour retrouver les commandes par clients, on peut faire :

SELECT clients .nom , commandes .id_objet , commandes . quantiteFROM clientsJOIN commandes ON commandes . id_client = clients .id

Si on veut retrouver les commandes faits par le client 3141, il suffit de faire :

SELECT clients .nom , commandes .id_objet , commandes . quantiteFROM clients


JOIN commandes ON commandes . id_client = clients .idWHERE clients .id = 3141

Si on veut les noms des objets et non plus leur identifiant, il faut faire deux jointuressymétriques :

SELECT clients .nom , objets .nom , commandes . quantiteFROM clientsJOIN commandes ON commandes . id_client = clients .idJOIN objets ON commandes . id_objets = objets .id

IV Agrégations et fonctions d’agrégation

L’agrégation consiste à regrouper des données ayant une caractéristique communedans le but d’y appliquer des fonctions statistiques. C’est-à-dire de remplacer unensemble d’objets enregistrés que l’on considère comme équivalent (ils forment un lot)et d’extraire de ce regroupement des caractéristiques qui dépendent de cet ensembled’objets.

O Fonctions d’agrégation

Les fonctions d’agrégation s’appliquent à une colonne complète, c’est à dire à unattribut d’une table, elle permettent de créer une nouvelle valeur.

La syntaxe est FCT(attribut) ou FCT(attribut1, attribut2) ou encore FCT(*).Dans le programme, il y a quatre fonctions d’agrégations :

Minimum et maximum avec MAX et MIN respectivement,Le comptage avec COUNTLa somme et la moyenne avec SUM et AVG

Ces fonctions s’appliquent à un nombre quelconque d’argument (à une colonnede taille quelconque) et ne dépendent pas de l’ordre des éléments sur lesquels elless’appliquent.

Ces fonctions servent à faire des statistiques sur les données.

Exemple IV.1 Pour avoir le prix le plus cher et le prix moyen :

SELECT max(prix), AVG(prix) FROM objets

SELECT countmax (prix), AVG(prix) FROM objets

R Il existe bien sûr de nombreuses autres fonctions d’agrégation.

O AgrégationAvant d’appliquer une fonction d’agrégation, on peut appliquer une agrégation : on

regroupe ensemble les objets ayant un même attribut (une caractéristique commune).On obtient ainsi un agrégat, c’est-à-dire un ensemble d’objet qui ont un attribut encommun.

V Séquence complète en SQL 115

Cela est fait avec le mot clé GROUP BY suivi de l’attribut qui sert d’agrégat.On peut alors sélectionner cet attribut et appliquer une fonction d’agrégation sur les

données regroupées.

Exemple IV.2 Nombre de commandes par jour :

SELECT date , count (*) FROM commandes GROUP BY date

Exemple IV.3 Si on veut calculer l’objet le total des achats d’un client :

SELECT clients .id , SUM( objets .prix)FROM clientsLEFT JOIN achatsON achats . idClient = clients . idClientLEFT JOIN objetsON achats . idObjet = objets . idObjetGROUP BY clients .id

O Sélection après agrégationDernier point, lorsque l’on a regroupé les objets et appliquer une fonction d’agré-

gation, on peut éventuellement choisir de sélectionner que les données vérifiant unecondition. Cette sélection est faite après agrégation et après application des fonctionsd’agrégation. En particulier, on pourra faire dépendre cette condition du résultat desfonctions d’agrégation. Le mot clé est HAVING suivi de la condition.

Il faut comprendre que cela revient juste à changer l’affichage (les valeurs retournéespar la requêtes) : Les calculs sont faits quand même sur les données, simplement ellesne sont pas retournées par la requête. Au contraire, la sélection faite avant l’agrégation(avec WHERE) consiste à effacer les données qui ne vérifient pas la condition. Aucuncalculs n’est alors faits sur ces données.

V Séquence complète en SQL

En conclusion, la séquence complète SQL est :

SELECT att , f(atts)FROM table1LEFT JOIN table2 ON table1 .idx = table2 .idxWHERE conditionGROUP BY attHAVING condition2

On doit donc décider dans l’ordre :• Sur quelle donnée on veut travailler : quelle table veut-on utiliser (FROM) ? Est-

ce que l’on veut croiser cette table avec une autre table (LEFT JOIN ... ON...) ? Est-ce que l’on veut utiliser la table complète ou uniquement les donnéesvérifiant une condition (WHERE) ?• Est-ce que les données doivent être regroupées selon un ou plusieurs attributs

dans le but d’en extraire de l’information statistique ?


• Quels sont les caractéristiques (attributs) que l’on veut récupérer (SELECT) ?quelles sont les statistiques sur les données regroupées (fonction d’agrégations)que l’on veut ?• Éventuellement, on peut choisir de ne pas afficher tous les résultats mais unique-

ment ceux vérifiant une condition (HAVING)

R En SQL pur, SELECT doit être suivi uniquement des attributs qui ont servi àl’agrégation et de fonction d’agrégation.

Exemples de requêtes MySQLPelletier Sylvain PC, Lycée Descartes

Dans cette fiche on montre les exemples à connaître de requêtes sur une base de données. Pour illustrer ces requêtes, onconsidère une base de données de taille moyenne concernant un élevage commercial d’animaux.

Cette base de données fictive provient du cours : Administrez vos bases de données avec MySQL, disponible surle site de site openclassrooms.

Cette base de données est constituée ainsi :

SHOW TABLES ;+-- ----------------+| Tables_in_testPC |+-- ----------------+| Adoption || Animal || Client || Espece || Race |+-- ----------------+

La table Animal contient la liste des animaux dans le magasin :

DESCRIBE Animal ;+-- --------------+----------------------+------+-----+---------+----------------+| Field | Type | Null | Key | Default | Extra |+-- --------------+----------------------+------+-----+---------+----------------+| id | smallint (6) unsigned | NO | PRI | NULL | auto_increment || sexe | char (1) | YES | | NULL | || date_naissance | datetime | NO | | NULL | || nom | varchar (30) | YES | MUL | NULL | || commentaires | text | YES | | NULL | || espece_id | smallint (6) unsigned | NO | MUL | NULL | || race_id | smallint (6) unsigned | YES | MUL | NULL | || mere_id | smallint (6) unsigned | YES | MUL | NULL | || pere_id | smallint (6) unsigned | YES | MUL | NULL | || disponible | tinyint (1) | YES | | 1 | |+-- --------------+----------------------+------+-----+---------+----------------+

On retrouve les attributs, les types (domaines). On voit aussi la clé primaire auto-incrémentée.On voit aussi les liens avec la table espèce et la table race.Une autre entité est les clients stockés dans la table Client :

DESCRIBE Client ;+-- --------------+----------------------+------+-----+---------+----------------+| Field | Type | Null | Key | Default | Extra |+-- --------------+----------------------+------+-----+---------+----------------+| id | smallint (5) unsigned | NO | PRI | NULL | auto_increment || nom | varchar (100) | NO | | NULL | || prenom | varchar (60) | NO | | NULL | || adresse | varchar (200) | YES | | NULL | || code_postal | varchar (6) | YES | | NULL | || ville | varchar (60) | YES | | NULL | || pays | varchar (60) | YES | | NULL | || email | varbinary (100) | YES | UNI | NULL | || date_naissance | date | YES | | NULL | |+-- --------------+----------------------+------+-----+---------+----------------+

Le lien entre les entités animaux et les entités clients est la table Adoption.

DESCRIBE Adoption ;

117

+-- ----------------+-----------------------+------+-----+---------+-------+| Field | Type | Null | Key | Default | Extra |+-- ----------------+-----------------------+------+-----+---------+-------+| client_id | smallint (5) unsigned | NO | PRI | NULL | || animal_id | smallint (5) unsigned | NO | PRI | NULL | || date_reservation | date | NO | | NULL | || date_adoption | date | YES | | NULL | || prix | decimal (7 ,2) unsigned | NO | | NULL | || paye | tinyint (1) | NO | | 0 | |+-- ----------------+-----------------------+------+-----+---------+-------+

Enfin, on a les tables Espece et Race, qui donne plus d’information sur les animaux.

DESCRIBE Espece ;+-- -----------+-----------------------+------+-----+---------+----------------+| Field | Type | Null | Key | Default | Extra |+-- -----------+-----------------------+------+-----+---------+----------------+| id | smallint (6) unsigned | NO | PRI | NULL | auto_increment || nom_courant | varchar (40) | NO | | NULL | || nom_latin | varchar (40) | NO | UNI | NULL | || description | text | YES | | NULL | || prix | decimal (7 ,2) unsigned | YES | | NULL | |+-- -----------+-----------------------+------+-----+---------+----------------+

DESCRIBE Race;+-- -----------+-----------------------+------+-----+---------+----------------+| Field | Type | Null | Key | Default | Extra |+-- -----------+-----------------------+------+-----+---------+----------------+| id | smallint (6) unsigned | NO | PRI | NULL | auto_increment || nom | varchar (40) | NO | | NULL | || espece_id | smallint (6) unsigned | NO | MUL | NULL | || description | text | YES | | NULL | || prix | decimal (7 ,2) unsigned | YES | | NULL | |+-- -----------+-----------------------+------+-----+---------+----------------+

O Opérateurs de l’algèbre relationnellePour projeter sur les noms des animaux (ie ne voir que les noms) :

SELECT nom FROM Animal ;

Pour afficher toute la table :

SELECT * FROM Animal ;

On peut voir que l’ordre est arbitraire.On peut aussi classer par date de naissance :

SELECT * FROM Animal ORDER BY date_naissance DESC;

Sélectionner les trois animaux les plus jeunes :

SELECT * FROM Animal ORDER BY date_naissance DESC LIMIT 3;

Les trois suivants (ordonnés par date de naissance) :

SELECT * FROM Animal ORDER BY date_naissance DESC LIMIT 3 OFFSET 3;

Le deuxième animal le plus jeune :

SELECT * FROM Animal ORDER BY date_naissance DESC LIMIT 1 OFFSET 1;

On peut aussi sélectionner lesLa projection ne renvoie pas des valeurs distinctes :

SELECT Sexe FROM Animal ;

118

renverra ainsi plein de F, M et de NULL.Si on veut les valeurs possibles, il faut faire :

SELECT DISTINCT Sexe FROM Animal ;

Pour chercher des informations sur les espèce à moins de 150 euros, on fait une restriction suivie d’une projection :

SELECT nom_courant , description , prix FROM Espece WHERE prix < 150;

Autre exemple, trouver les noms des animaux nés en 2012 :

SELECT nom , date_naissance FROM Animal WHERE date_naissance > ’2012 -0101 ’;

Si besoin on peut classer par date de naissance avec ORDER BY.Autre exemple : trouver les personne qui ont adopté et pas payé :

SELECT * FROM Adoption WHERE ( date_adoption IS NOT NULL) AND (paye = 0) ;

O Les jointuresSi par exemple, on veut le nom, le nom de l’espèce de chaque animal cela donne :

SELECT Animal .nom , Espece . nom_courant FROM AnimalLEFT JOIN EspeceON Espece .id = Animal . espece_id ;

Idem avec deux jointures et une restriction pour avoir le nom, le nom de l’espèce, le nom de la race pour les chiens etchats :

SELECT Animal .nom , Espece . nom_courant , Race.nom FROM AnimalLEFT JOIN EspeceON Espece .id = Animal . espece_idLEFT JOIN RaceON Race.id = Animal . race_idWHERE Espece . nom_courant = ’Chien ’ OR Espece . nom_courant = ’Chat ’;

Toujours avec deux jointures pour avoir les couples (nom du client, nom de l’animal), avec un renommage pour biendifférentier le nom du client et le nom de l’animal :

SELECT Client .nom AS nomClient , Animal .nom AS nomAnimal , Adoption . date_adoptionFROM AdoptionLEFT JOIN Client ON Client .id = Adoption . client_idLEFT JOIN Animal ON Animal .id = Adoption . animal_idWHERE Adoption . date_adoption IS NOT NULL;

Autre exemple, jointure d’une table deux fois avec elle-même pour obtenir les parents d’un animal :

SELECT Animal .nom AS nomAnimal , Pere.nom AS nomPere , Mere.nom AS nomMereFROM AnimalLEFT JOIN Animal AS Pere ON Animal . pere_id = Pere.idLEFT JOIN Animal AS Mere ON Animal . mere_id = Mere.idWHERE ( Animal . pere_id IS NOT NULL) OR ( Animal . mere_id IS NOT NULL );

O Agrégation et fonctions d’agrégationSi on veut le nombre d’animaux :

SELECT count (*) FROM Animal ;

Le nombre de mâles :

SELECT count (*) FROM Animal WHERE sexe = ’M’;

Le nombre de chiens et chat (avec une jointure pour le nom de l’espèce) :

SELECT count (*) FROM AnimalLEFT JOIN EspeceON Espece .id = Animal . espece_idWHERE Espece . nom_courant = "Chien" OR Espece . nom_courant = "Chat";

119

Le total du prix des animaux en boutique :

SELECT sum( Espece .prix) FROM AnimalLEFT JOIN EspeceON Espece .id = Animal . espece_id ;

Maintenant si on veut compter le nombre d’animal par sexe :

SELECT sexe , count (*) FROM Animal GROUP BY sexe;

Idem par espèce avec une jointure pour avoir le nom de l’espèce :

SELECT Espece . nom_courant , count (*)FROM AnimalLEFT JOIN Espece ON Espece .id = Animal . espece_idGROUP BY Animal . espece_id ;

Le nom et prénom des clients ayant fait plus de deux achats et leur nombre d’adoption :

SELECT Client .nom AS nomClient , Client . prenom AS prenomClient , count (*) AS nbrAdoptionFROM AdoptionLEFT JOIN Client ON Adoption . client_id = Client .idGROUP BY Adoption . client_idHAVING nbrAdoption > 1;

Ici on filtre après avoir calculé le nombre d’adoption, puisque c’est le critère de filtrage.Par contre, si on veut compter combien d’animaux par race mais sans prendre en compte les chiens et les chats. La bonne

méthode est :

SELECT Espece . nom_courant , count (*)FROM AnimalLEFT JOIN Espece ON Espece .id = Animal . espece_idWHERE ( Espece . nom_courant <> ’Chien ’) AND ( Espece . nom_courant <> ’Chat ’)GROUP BY Animal . espece_id ;

puisqu’on efface de la liste dès le début les chats et les chiens.La mauvaise méthode est :

SELECT Espece . nom_courant , count (*)FROM AnimalLEFT JOIN Espece ON Espece .id = Animal . espece_idGROUP BY Animal . espece_idHAVING ( Espece . nom_courant <> ’Chien ’) AND ( Espece . nom_courant <> ’Chat ’);

puisqu’on efface simplement deux lignes de la table obtenue par agrégation.Dernier exemple, en sélectionnant avant l’agrégation et après : on veut le nom et prénom des clients ayant adopté plus de

deux chats.

SELECT Client .nom AS nomClient , Client . prenom AS prenomClient , count (*) AS nbrAdoptionFROM AdoptionLEFT JOIN Client ON Adoption . client_id = Client .idLEFT JOIN Animal ON Adoption . animal_id = Animal .idLEFT JOIN Espece ON Espece .id = Animal . espece_idWHERE Espece . nom_courant = ’Chat ’GROUP BY Adoption . client_idHAVING nbrAdoption > 1;

120

Documents

Table des matières - Mathématiques et Informatique en PCSI …pcsidescartes.fr/pdf/ipt2Courant.pdf · · 2018-02-06chemin=calcule_chemin(front) 104 represente(carte,chemin) Une