Mines Informatique MP-PC-PSI 2016

Thème de l'épreuve Modélisation de la propagation d'une épidémie
Principaux outils utilisés algorithmique, bases de données
Mots clefs algorithme de tri, intégration numérique, automate cellulaire

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                             

Rapport du jury

(PDF non trouvé ! |/net/www/doc-solus.fr/www//prepa/sci/adc/pdf/rapports.pdf/2016/PSI_INFO_MINES_1_2016.rapport.pdf|)

Énoncé obtenu par reconnaissance optique des caractères


A 2016 - INFO.

École des PONTS ParisTech,
ISAE-SUPAERO, ENSTA ParisTech,
TÉLÉCOM ParisTech, MINES ParisTech,
MINES Saint-Étienne, MINES Nancy,
TÉLÉCOM Bretagne, ENSAE ParisTech (Filière MP).
CONCOURS 2016
ÉPREUVE D'INFORMATIQUE
TOUTES LES FILIÈRES
(Durée de l'épreuve : 1 h 30)
L'usage de l'ordinateur ou de la calculatrice est interdit.
Sujet mis à la disposition des concours :
Concours Commun TPE/EIVP, Concours Mines-Télécom,
Concours Centrale-Supélec (Cycle international).
Les candidats sont priés de mentionner de façon apparente
sur la première page de la copie :

INFORMATIQUE
L'énoncé de cette épreuve comporte 9 pages de texte.

Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur
d'énoncé, il le signale sur sa copie et poursuit sa composition en expliquant
les raisons des initiatives qu'il est amené à prendre.

Modelisation de la propagation d'une epidemie
L'etude de la propagation des epidemies joue un role important dans les 
politiques de sante
publique. Les modeles mathematiques ont permis de comprendre pourquoi il a ete 
possible d'eradiquer la variole a la fin des annees 1970 et pourquoi il est 
plus difficile d'eradiquer d'autres maladies
comme la poliomyelite ou la rougeole. Ils ont egalement permis d'expliquer 
l'apparition d'epidemies
de grippe tous les hivers. Aujourd'hui, des modeles de plus en plus complexes 
et puissants sont
developpes pour predire la propagation d'epidemies a l'echelle planetaire 
telles que le SRAS, le
virus H5N1 ou le virus Ebola. Ces predictions sont utilisees par les 
organisations internationales
pour etablir des strategies de prevention et d'intervention.
Le travail sur ces modeles mathematiques s'articule autour de trois themes 
principaux : traitement de bases de donnees, simulation numerique (par 
plusieurs types de methodes), identification
des parametres intervenant dans les modeles a partir de donnees experimentales. 
Ces trois themes
sont abordes dans le sujet. Les parties sont independantes.
Dans tout le probleme, on peut utiliser une fonction traitee precedemment. On 
suppose que les
bibliotheques numpy et random ont ete importees par :
import numpy as np
import random as rd
Partie I. Tri et bases de donnees
Dans le but ulterieur de realiser des etudes statistiques, on souhaite se doter 
d'une fonction tri.
On se donne la fonction tri suivante, ecrite en Python :
1
2
3
4
5
6
7
8
9

def tri(L):
n = len(L)
for i in range(1, n):
j = i
x = L[i]
while 0 < j and x < L[j-1]:
L[j] = L[j-1]
j = j-1
L[j] = x

 Q1 ­ Lors de l'appel tri(L) lorsque L est la liste [5, 2, 3, 1, 4], donner le 
contenu de la
liste L a la fin de chaque iteration de la boucle for.
 Q2 ­ Soit L une liste non vide d'entiers ou de flottants. Montrer que « la 
liste L[0:i+1] (avec
la convention Python) est triee par ordre croissant a l'issue de l'iteration i 
» est un invariant de
boucle. En deduire que tri(L) trie la liste L.
 Q3 ­ Evaluer la complexite dans le meilleur et dans le pire des cas de l'appel 
tri(L) en fonction
du nombre n d'elements de L. Citer un algorithme de tri plus efficace dans le 
pire des cas. Quelle
en est la complexite dans le meilleur et dans le pire des cas ?
On souhaite, partant d'une liste constituee de couples (chaine, entier), trier 
la liste par ordre
croissant de l'entier associe suivant le fonctionnement suivant :
>>> L = [['Bresil', 76], ['Kenya', 26017], ['Ouganda', 8431]]
>>> tri_chaine(L)
>>> L
[['Bresil', 76], ['Ouganda', 8431], ['Kenya', 26017]]

1

 Q4 ­ Ecrire en Python une fonction tri_chaine realisant cette operation.
Pour suivre la propagation des epidemies, de nombreuses donnees sont 
recueillies par les institutions
internationales comme l'O.M.S. Par exemple, pour le paludisme, on dispose de 
deux tables :
­ la table palu recense le nombre de nouveaux cas confirmes et le nombre de 
deces lies au
paludisme ; certaines lignes de cette table sont donnees en exemple (on precise 
que iso est
un identifiant unique pour chaque pays) :
nom
iso annee
cas
deces
Bresil
BR 2009
309 316
85
Bresil
BR 2010
334 667
76
Kenya
KE 2010
898 531 26 017
Mali
ML 2011
307 035
2 128
Ouganda UG 2010 1 581 160 8 431
...
­ la table demographie recense la population totale de chaque pays ; certaines 
lignes de cette
table sont donnees en exemple :
pays periode
pop
BR
2009
193 020 000
BR
2010
194 946 000
KE
2010
40 909 000
ML
2011
14 417 000
UG
2010
33 987 000
...
 Q5 ­ Au vu des donnees presentees dans la table palu, parmi les attributs nom, 
iso et annee, quels
attributs peuvent servir de cle primaire ? Un couple d'attributs pourrait-il 
servir de cle primaire ?
(on considere qu'une cle primaire peut posseder plusieurs attributs). Si oui, 
en preciser un.
 Q6 ­ Ecrire une requete en langage SQL qui recupere depuis la table palu 
toutes les donnees de
l'annee 2010 qui correspondent a des pays ou le nombre de deces dus au 
paludisme est superieur
ou egal a 1 000.
On appelle taux d'incidence d'une epidemie le rapport du nombre de nouveaux cas 
pendant une
periode donnee sur la taille de la population-cible pendant la meme periode. Il 
s'exprime generalement en « nombre de nouveaux cas pour 100 000 personnes par 
annee ». Il s'agit d'un des criteres
les plus importants pour evaluer la frequence et la vitesse d'apparition d'une 
epidemie.
 Q7 ­ Ecrire une requete en langage SQL qui determine le taux d'incidence du 
paludisme en 2011
pour les differents pays de la table palu.
 Q8 ­ Ecrire une requete en langage SQL permettant de determiner le nom du pays 
ayant eu le
deuxieme plus grand nombre de nouveaux cas de paludisme en 2010 (on pourra 
supposer qu'il n'y
a pas de pays ex æquo pour les nombres de cas).
On considere la requete R qui s'ecrit dans le langage de l'algebre 
relationnelle :
R = nom, deces (annee=2010 (palu))
On suppose que le resultat de cette requete a ete converti en une liste Python 
stockee dans la
variable deces2010 et constituee de couples (chaine, entier).
 Q9 ­ Quelle instruction peut-on ecrire en Python pour trier la liste deces2010 
par ordre croissant
du nombre de deces dus au paludisme en 2010 ?
2

Partie II. Modele a compartiments
On s'interesse ici a une premiere methode de simulation numerique.
Les modeles compartimentaux sont des modeles deterministes ou la population est 
divisee en
plusieurs categories selon leurs caracteristiques et leur etat par rapport a la 
maladie. On considere
dans cette partie un modele a quatre compartiments disjoints : sains (S, 
"susceptible"), infectes
(I, "infected"), retablis (R, "recovered", ils sont immunises) et decedes (D, 
"dead"). Le changement
d'etat des individus est gouverne par un systeme d'equations differentielles 
obtenues en supposant
que le nombre d'individus nouvellement infectes (c'est-a-dire le nombre de ceux 
qui quittent le
compartiment S) pendant un intervalle de temps donne est proportionnel au 
produit du nombre
d'individus infectes avec le nombre d'individus sains.
En notant S(t), I(t), R(t) et D(t) la fraction de la population appartenant a 
chacune des quatre
categories a l'instant t, on obtient le systeme :

d

S(t) = -r S(t)I(t)

dt

d

I(t) = r S(t)I(t) - (a + b) I(t)
dt
(1)
d

R(t) = a I(t)

dt

d

D(t) = b I(t)
dt
avec r le taux de contagion, a le taux de guerison et b le taux de mortalite. 
On suppose qu'a l'instant
initial t = 0, on a S(0) = 0,95 , I(0) = 0,05 et R(0) = D(0) = 0.
 Q10 ­ Preciser un vecteur X et une fonction f (en donnant son domaine de 
definition et son
expression) tels que le systeme differentiel (1) s'ecrive sous la forme
d
X = f (X).
dt
 Q11 ­ Completer la ligne 4 du code suivant (on precise que np.array permet de 
creer un tableau
numpy a partir d'une liste donnant ainsi la possibilite d'utiliser les 
operateurs algebriques).
1
2
3
4

def f(X):
""" Fonction definissant l'equation differentielle """
global r, a, b
# a completer

5
6
7
8
9
10
11

# Parametres
tmax = 25.
r = 1.
a = 0.4
b = 0.1
X0 = np.array([0.95, 0.05, 0., 0.])

12
13
14

N = 250
dt = tmax/N

15
16
17
18
19

t = 0
X = X0
tt = [t]
XX = [X]

3

20
21
22
23
24
25
26

# Methode d'Euler
for i in range(N):
t = t + dt
X = X + dt * f(X)
tt.append(t)
XX.append(X)

S
I
R
D

1.2
1.0
0.8
0.6
0.4
0.2
0.0
0.2
0

5

10

Temps

15

20

25

Figure 1 ­ Representation graphique des quatre categories S, I, R et D en 
fonction du temps
pour N = 7 (points) et N = 250 (courbes).

 Q12 ­ La figure 1 represente les quatre categories en fonction du temps 
obtenues en effectuant
deux simulations : la premiere avec N = 7 correspond aux points (cercle, carre, 
losange, triangle) et
la seconde avec N = 250 correspond aux courbes. Expliquer la difference entre 
ces deux simulations.
Quelle simulation a necessite le temps de calcul le plus long ?
En pratique, de nombreuses maladies possedent une phase d'incubation pendant 
laquelle l'individu
est porteur de la maladie mais ne possede pas de symptomes et n'est pas 
contagieux. On peut
prendre en compte cette phase d'incubation a l'aide du systeme a retard suivant 
:

d

S(t) = -r S(t)I(t -  )

dt

d

I(t) = r S(t)I(t -  ) - (a + b) I(t)
dt
d

R(t) = a I(t)

dt

 d D(t) = b I(t)
dt
4

ou  est le temps d'incubation. On suppose alors que pour tout t  [-, 0], S(t) = 
0,95 , I(t) = 0,05
et R(t) = D(t) = 0.
En notant tmax la duree des mesures et N un entier donnant le nombre de pas, on 
definit le pas
de temps dt = tmax/N . On suppose que  = p × dt ou p est un entier ; ainsi p 
est le nombre de pas
de retard.
Pour resoudre numeriquement ce systeme d'equations differentielles a retard 
(avec tmax = 25,
N = 250 et p = 50), on a ecrit le code suivant :
1
2
3
4
5
6
7

def f(X, Itau):
"""
Fonction definissant l'equation differentielle
Itau est la valeur de I(t - p * dt)
"""
global r, a, b
# a completer

8
9
10
11
12
13

# Parametres
r = 1.
a = 0.4
b = 0.1
X0 = np.array([0.95, 0.05, 0., 0.])

14
15
16
17
18

tmax = 25.
N = 250
dt = tmax/N
p = 50

19
20
21
22
23

t = 0
X = X0
tt = [t]
XX = [X]

24
25
26
27
28
29
30

# Methode d'Euler
for i in range(N):
t = t + dt
# a completer
tt.append(t)
XX.append(X)

 Q13 ­ Completer les lignes 7 et 28 du code precedent (utiliser autant de 
lignes que necessaire).
On constate que le temps d'incubation de la maladie n'est pas necessairement le 
meme pour tous
les individus. On peut modeliser cette diversite a l'aide d'une fonction 
positive d'integrale unitaire
(dite de densite) h : [0,  ]  R+ telle que representee sur la figure 2. On 
obtient alors le systeme
integro-differentiel :
Z 

d

I(t - s)h(s) ds
S(t) = -r S(t)

dt

0

Z 

d

I(t) = r S(t)
I(t - s)h(s) ds - (a + b) I(t)
dt
0

d

R(t) = a I(t)

dt

 d D(t) = b I(t)
dt
5

h(t)
Fonction densite
0

t

Figure 2 ­ Exemple d'une fonction de densite.
On supposera a nouveau que pour tout t  [-, 0], S(t) = 0,95 , I(t) = 0,05 et 
R(t) = D(t) = 0.
Pour j entier compris entre 0 et N , on pose tj = j × dt. Pour un pas de temps 
dt donne, on peut
calculer numeriquement l'integrale a l'instant ti (0  i  N ) a l'aide de la 
methode des rectangles
a gauche en utilisant l'approximation :
Z

I(ti - s)h(s) ds  dt ×
0

p-1
X

I(ti - tj )h(tj ).

j=0

 Q14 ­ On suppose que la fonction h a ete ecrite en Python. Expliquer comment 
modifier le
programme de la question precedente pour resoudre ce systeme 
integro-differentiel (on explicitera
les lignes de code necessaires).
Partie III. Modelisation dans des grilles
On s'interesse ici a une seconde methode de simulation numerique (dite par 
automates cellulaires).
Dans ce qui suit, on appelle grille de taille n × n une liste de n listes de 
longueur n, ou n est
un entier strictement positif.
Pour mieux prendre en compte la dependance spatiale de la contagion, il est 
possible de simuler
la propagation d'une epidemie a l'aide d'une grille. Chaque case de la grille 
peut etre dans un des
quatre etats suivants : saine, infectee, retablie, decedee. On choisit de 
representer ces quatre etats
par les entiers :
0 (Sain), 1 (Infecte), 2 (Retabli) et 3 (Decede).
L'etat des cases d'une grille evolue au cours du temps selon des regles 
simples. On considere un
modele ou l'etat d'une case a l'instant t + 1 ne depend que de son etat a 
l'instant t et de l'etat de
ses huit cases voisines a l'instant t (une case du bord n'a que cinq cases 
voisines et trois pour une
case d'un coin). Les regles de transition sont les suivantes :
­ une case decedee reste decedee ;
­ une case infectee devient decedee avec une probabilite p1 ou retablie avec 
une probabilite
(1 - p1 ) ;
­ une case retablie reste retablie ;
­ une case saine devient infectee avec une probabilite p2 si elle a au moins 
une case voisine
infectee et reste saine sinon.
On initialise toutes les cases dans l'etat sain, sauf une case choisie au 
hasard dans l'etat infecte.
 Q15 ­ On a ecrit en Python la fonction grille(n) suivante
6

def grille(n) :
M=[ ]
for i in range(n) :
L=[ ]
for j in range(n): L.append(0)
M.append(L)
return M

Decrire ce que retourne cette fonction.
On pourra dans la question suivante utiliser la fonction randrange(p) de la 
bibliotheque random
qui, pour un entier positif p, renvoie un entier choisi aleatoirement entre 0 
et p - 1 inclus.
 Q16 ­ Ecrire en Python une fonction init(n) qui construit une grille G de 
taille n × n ne
contenant que des cases saines, choisit aleatoirement une des cases et la 
transforme en case infectee,
et enfin renvoie G.
 Q17 ­ Ecrire en Python une fonction compte(G) qui a pour argument une grille G 
et renvoie la
liste [n0, n1, n2, n3] formee des nombres de cases dans chacun des quatre etats.
D'apres les regles de transition, pour savoir si une case saine peut devenir 
infectee a l'instant
suivant, il faut determiner si elle est exposee a la maladie, c'est-a-dire si 
elle possede au moins une
case infectee dans son voisinage. Pour cela, on ecrit en Python la fonction 
est_exposee(G, i, j)
suivante.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

def est_exposee(G, i, j):
n = len(G)
if i == 0 and j == 0:
return (G[0][1]-1)*(G[1][1]-1)*(G[1][0]-1) == 0
elif i == 0 and j == n-1:
return (G[0][n-2]-1)*(G[1][n-2]-1)*(G[1][n-1]-1) == 0
elif i == n-1 and j == 0:
return (G[n-1][1]-1)*(G[n-2][1]-1)*(G[n-2][0]-1) == 0
elif i == n-1 and j == n-1:
return (G[n-1][n-2]-1)*(G[n-2][n-2]-1)*(G[n-2][n-1]-1) == 0
elif i == 0:
# a completer
elif i == n-1:
return 
(G[n-1][j-1]-1)*(G[n-2][j-1]-1)*(G[n-2][j]-1)*(G[n-2][j+1]-1)*(G[n-1][j+1]-1) 
== 0
elif j == 0:
return (G[i-1][0]-1)*(G[i-1][1]-1)*(G[i][1]-1)*(G[i+1][1]-1)*(G[i+1][0]-1) == 0
elif j == n-1:
return 
(G[i-1][n-1]-1)*(G[i-1][n-2]-1)*(G[i][n-2]-1)*(G[i+1][n-2]-1)*(G[i+1][n-1]-1) 
== 0
else:
# a completer

 Q18 ­ Quel est le type du resultat renvoye par la fonction est_exposee ?
 Q19 ­ Completer les lignes 12 et 20 de la fonction est_exposee.
 Q20 ­ Ecrire une fonction suivant(G, p1, p2) qui fait evoluer toutes les cases 
de la grille G a
l'aide des regles de transition et renvoie une nouvelle grille correspondant a 
l'instant suivant. Les
arguments p1 et p2 sont les probabilites qui interviennent dans les regles de 
transition pour les
cases infectees et les cases saines. On pourra utiliser la fonction 
bernoulli(p) suivante qui simule
une variable aleatoire de Bernoulli de parametre p : bernoulli(p) vaut 1 avec 
la probabilite p et
0 avec la probabilite (1 - p).

7

def bernoulli(p):
x = rd.random()
if x <= p:
return 1
else:
return 0

On reproduit ci-dessous le descriptif de la documentation Python concernant la 
fonction random
de la bibliotheque random :
random.random()
Return the next random floating point number in the range [0.0, 1.0).

Avec les regles de transition du modele utilise, l'etat de la grille evolue 
entre les instants t et t + 1
tant qu'il existe au moins une case infectee.
 Q21 ­ Ecrire en Python une fonction simulation(n, p1, p2) qui realise une 
simulation complete avec une grille de taille n×n pour les probabilites p1 et 
p2, et renvoie la liste [x0, x1, x2, x3]
formee des proportions de cases dans chacun des quatre etats a la fin de la 
simulation (une simulation s'arrete lorsque la grille n'evolue plus).
 Q22 ­ Quelle est la valeur de la proportion des cases infectees x1 a la fin 
d'une simulation ?
Quelle relation verifient x0, x1, x2 et x3 ? Comment obtenir a l'aide des 
valeurs de x0, x1, x2 et x3
la valeur x_atteinte de la proportion des cases qui ont ete atteintes par la 
maladie pendant une
simulation ?

Figure 3 ­ Representation de la proportion de la population qui a ete atteinte 
par la maladie
pendant la simulation en fonction de la probabilite p2 .

8

On fixe p1 a 0,5 et on calcule la moyenne des resultats de plusieurs 
simulations pour differentes
valeurs de p2. On obtient la courbe de la figure 3.
 Q23 ­ On appelle seuil critique de pandemie la valeur de p2 a partir de 
laquelle plus de la moitie
de la population a ete atteinte par la maladie a la fin de la simulation. On 
suppose que les valeurs
de p2 et x_atteinte utilisees pour tracer la courbe de la figure 3 ont ete 
stockees dans deux listes
de meme longueur Lp2 et Lxa. Ecrire en Python une fonction seuil(Lp2, Lxa) qui 
determine par
dichotomie un encadrement [p2cmin, p2cmax] du seuil critique de pandemie avec 
la plus grande
precision possible. On supposera que la liste Lp2 croit de 0 a 1 et que la 
liste Lxa des valeurs
correspondantes est croissante.
Pour etudier l'effet d'une campagne de vaccination, on immunise au hasard a 
l'instant initial une
fraction q de la population. On a ecrit la fonction init_vac(n, q).
1
2
3
4
5
6
7
8
9
10
11

def init_vac(n, q):
G = init(n)
nvac = int(q * n**2)
k = 0
while k < nvac:
i = rd.randrange(n)
j = rd.randrange(n)
if G[i][j] == 0:
G[i][j] = 2
k += 1
return G

 Q24 ­ Peut-on supprimer le test en ligne 8 ?
 Q25 ­ Que renvoie l'appel init_vac(5, 0.2) ?

Fin de l'epreuve.

9

Extrait du corrigé obtenu par reconnaissance optique des caractères



Mines Informatique PSI 2016 -- Corrigé
Ce corrigé est proposé par Virgile Andreani (ENS Ulm) ; il a été relu par Julien
Dumont (Professeur en CPGE) et Jean-Julien Fleck (Professeur en CPGE).

Ce sujet d'informatique propose d'étudier la propagation des épidémies. Ses 
trois
parties sont indépendantes.
· La première partie, très classique, est l'occasion d'étudier un algorithme de
tri. Elle comporte quelques questions de difficulté croissante sur les bases de
données relationnelles.
· Dans la deuxième partie, il faut compléter un code permettant d'intégrer un
système d'équations différentielles modélisant la propagation d'une épidémie.
Le système est ensuite modifié pour introduire un retard, puis on passe à un
ensemble d'équations intégro-différentielles dont on doit calculer l'intégrale 
par
la méthode des rectangles.
· La troisième partie, un peu plus originale, propose d'ajouter des dimensions
spatiales au modèle, simulé cette fois-ci par un automate cellulaire non 
déterministe.
Peu de programmation est demandée. Hormis une ou deux questions, le sujet
est d'une difficulté modérée ; il est accessible dès la première année de 
prépa. Les
réponses attendues sont souvent plus courtes que les questions. C'est un bon 
sujet d'entraînement pour s'assurer que l'on sait appliquer le cours sur des 
exemples
simples.

Indications
Partie I
2 Raisonner par récurrence pour prouver l'invariant de boucle.
7 Il faut faire une jointure : associer les colonnes ayant la même 
signification entre
les tables.
Partie II
13 Itau est une information qui figure dans la liste XX.
14 Utiliser XX pour calculer la valeur de l'intégrale, inutile de modifier la 
fonction f.
Partie III
17 Il existe deux manières de répondre à cette question, l'une est plus 
efficace que
l'autre et serait probablement valorisée lors de la correction.
20 Attention à faire en sorte que la mise à jour de toutes les cellules soit 
simultanée :
on ne doit pas appeler la fonction est_exposee sur une grille partiellement mise
à jour.
21 L'énoncé demande ici les proportions de cases dans les différents états et 
non pas
leur nombre comme précédemment.

I. Tri et bases de données
1 Lors de l'itération i de la boucle for, l'élément i de la liste de départ est 
descendu jusqu'à sa place dans la liste triée constituée des i + 1 premiers 
éléments. Par
conséquent, le contenu de la liste évolue de la manière suivante :
· Début de la fonction : [5, 2, 3, 1, 4] ;
· Fin de l'itération i = 1 : [2, 5, 3, 1, 4] ;
· Fin de l'itération i = 2 : [2, 3, 5, 1, 4] ;
· Fin de l'itération i = 3 : [1, 2, 3, 5, 4] ;
· Fin de l'itération i = 4 : [1, 2, 3, 4, 5] ;
· Sortie de la fonction : [1, 2, 3, 4, 5].
Vous aurez sûrement reconnu le tri par insertion !
2 Soit P(i) la propriété
La liste L[0:i+1] est triée par ordre croissant à l'issue de l'itération i.
On va montrer par récurrence sur i que P(i) est vraie pour tout i  [[ 1 ; n - 1 
]].
· Lors de la première itération, i = 1 donc la valeur du deuxième élément de la
liste est affectée à x. Deux cas sont alors possibles : soit L[0] > x et le 
corps de
la boucle while est effectué une seule fois, ce qui a pour effet d'échanger L[0]
et L[1]. Soit L[0] 6 x et le corps de la boucle n'est jamais exécuté. Dans les
deux cas, les deux premiers éléments de la liste se retrouvent triés par ordre
croissant à la fin de la première itération, ce qui satisfait P(1).
· P(i - 1) = P(i) : P(i - 1) nous permet de considérer que les i premiers
éléments de L (soit de 0 à i - 1 inclus) sont triés à la fin de l'itération i - 
1, et
donc également au début de l'itération i. On peut alors distinguer deux cas :
­ L[i] est supérieur ou égal à tous les éléments de L[0:i]. Dans ce cas, le
programme n'entre pas dans la boucle while puisque sa deuxième condition est 
fausse, et l'affectation de la ligne 9 ne fait que remplacer L[j]
par lui-même puisque j est toujours égal à i. La liste L[0:i+1] est par
conséquent elle aussi triée.
­ Il existe au moins un élément de L[0:i] strictement supérieur à L[i].
La boucle while est exécutée et, à sa sortie, on sait que L[i] < L[j]
(la condition de la boucle était vraie à l'itération précédente), et que soit
j = 0, soit L[j-1] 6 L[i] (la condition de la boucle est fausse). Comme
tous les éléments de L d'indices compris entre j et i - 1 avant la boucle
ont été décalés d'un cran vers la droite, la place est libre en L[j] pour
accueillir l'ancien L[i]. La liste L[0:i+1] est donc également triée.
Par conséquent

La propriété P(i) est un invariant de boucle.

La dernière itération correspond à i = n - 1, ainsi P(n - 1) assure que la liste
L[0:n], donc toute la liste, est triée.
Une manière mathématiquement équivalente mais un peu plus succincte
de démontrer le cas de base de la récurrence aurait été de partir de P(0) :
bien que l'itération i = 0 ne soit pas explicite dans le code, elle correspond à
l'état de la liste au début de la fonction, avant la première itération. La 
liste
L[0:1] ne contient qu'un seul élément, on peut donc la considérer comme

triée. Donc P(0) est vraie.
Par ailleurs, cela n'était sûrement pas demandé (la démonstration est
assez longue ainsi), mais pour être complet, on aurait dû démontrer deux
propriétés supplémentaires. D'une part, que l'on indice toujours la liste L
dans les limites de sa taille et d'autre part que la fonction change uniquement
l'ordre des éléments et pas leur valeur. Concernant cette dernière propriété,
l'énoncé commet un abus par hypothèse implicite en invitant à déduire de
P(n) la conclusion que tri(L) trie, au sens de l'énoncé, la liste L. En effet,
cette condition, bien que nécessaire, n'est pas suffisante : imaginons que la
boucle for écrase progressivement chaque élément de L avec son premier
élément : P(i) est toujours vraie pour tout i, la liste finale est bien triée
puisqu'elle ne contient que n copies de son premier élément, mais elle n'a
plus rien à voir avec la liste initiale. Il est donc nécessaire de démontrer
également la propriété Q(i) :
À l'issue de l'itération i, la liste L[0:i+1] contient
les mêmes éléments qu'au début de la fonction.
Cette démonstration, à faire également par récurrence, est laissée en exercice
au lecteur !
3 À taille de liste fixée, seul le corps de la boucle while est exécuté un 
nombre
variable de fois. Dans le meilleur cas, cette portion de code n'est jamais 
exécutée :
c'est ce qui se passe pour les listes déjà triées. En définissant la complexité 
de cet
algorithme par le nombre de comparaisons entre éléments de la liste qu'il 
effectue,
on trouve dans le meilleur cas que celui-ci est égal à n - 1 (une par itération 
de for,
dans la condition du while), par conséquent
Le meilleur cas, obtenu pour les listes déjà triées, est linéaire (O(n)).
Dans le pire cas, la boucle while s'exécute le maximum de fois à chaque 
itération,
soit i fois à l'itération i. C'est ce qui se passe lorsque L est initialement 
triée dans
l'ordre décroissant. Le nombre de comparaisons d'éléments de la liste est alors
1 + 2 + · · · + (n - 1) =

n-1
P

i=

i=1

n × (n - 1)
2

Le pire cas, celui des listes triées dans l'ordre inverse, est quadratique 
(O(n2 )).
Le tri fusion a une complexité quasi-linéaire en O(n log n) dans le meilleur
comme dans le pire cas.
Attention à ne pas citer le tri rapide, qui, bien que quasi-linéaire en moyenne,
est quadratique dans le pire cas.
4 On dispose déjà d'une fonction de tri, il suffit de l'adapter très légèrement 
pour
effectuer la comparaison sur le deuxième élément de chaque liste. On reprend 
donc
entièrement le code de tri en modifiant seulement la condition du while :
def tri_chaine(L):
n = len(L)
for i in range(1, n):
j = i
x = L[i]
while 0 < j and x[1] < L[j-1][1]: