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

(télécharger le 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 commune MP 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]: