Version interactive avec LaTeX compilé

Mines Informatique Commune MP PC PSI 2016

Notez ce sujet en cliquant sur l'étoile

0.0(0 votes)

🔗 Explorer

Mines MP/PC/PSI Mines 2016 MP/PC/PSI Info Info 2016

2025_08_29_b146da7f76d2e3bfcd41g

É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.

Modélisation de la propagation d'une épidémie

L'étude de la propagation des épidémies joue un rôle important dans les politiques de santé publique. Les modèles mathématiques ont permis de comprendre pourquoi il a été possible d'éradiquer la variole à la fin des années 1970 et pourquoi il est plus difficile d'éradiquer d'autres maladies comme la poliomyélite ou la rougeole. Ils ont également permis d'expliquer l'apparition d'épidémies de grippe tous les hivers. Aujourd'hui, des modèles de plus en plus complexes et puissants sont développés pour prédire la propagation d'épidémies à l'échelle planétaire telles que le SRAS, le virus H5N1 ou le virus Ebola. Ces prédictions sont utilisées par les organisations internationales pour établir des stratégies de prévention et d'intervention.

Le travail sur ces modèles mathématiques s'articule autour de trois thèmes principaux : traitement de bases de données, simulation numérique (par plusieurs types de méthodes), identification des paramètres intervenant dans les modèles à partir de données expérimentales. Ces trois thèmes sont abordés dans le sujet. Les parties sont indépendantes.

Dans tout le problème, on peut utiliser une fonction traitée précédemment. On suppose que les bibliothèques numpy et random ont été importées par :
import numpy as np
import random as rd

Partie I. Tri et bases de données

Dans le but ultérieur de réaliser des études statistiques, on souhaite se doter d'une fonction tri. On se donne la fonction tri suivante, écrite en Python :

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 à la fin de chaque itération 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 triée par ordre croissant à l'issue de l'itération i

est un invariant de boucle. En déduire que tri (L) trie la liste L.

Q3 - Évaluer la complexité dans le meilleur et dans le pire des cas de l'appel tri (L) en fonction du nombre n d'éléments de L . Citer un algorithme de tri plus efficace dans le pire des cas. Quelle en est la complexité dans le meilleur et dans le pire des cas ?
On souhaite, partant d'une liste constituée de couples (chaîne, entier), trier la liste par ordre croissant de l'entier associé suivant le fonctionnement suivant :

>>> L = [['Bresil', 76], ['Kenya', 26017], ['Ouganda', 8431]]
>>> tri_chaine(L)
>>> L
[['Bresil', 76], ['Ouganda', 8431], ['Kenya', 26017]]

Q4 - Écrire en Python une fonction tri_chaine réalisant cette opération.
Pour suivre la propagation des épidémies, de nombreuses données 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 confirmés et le nombre de décès liés au paludisme; certaines lignes de cette table sont données en exemple (on précise que iso est un identifiant unique pour chaque pays) :

nom	iso	annee	cas	deces
Bresil	BR	2009	309316	85
Bresil	BR	2010	334667	76
Kenya	KE	2010	898531	26017
Mali	ML	2011	307035	2128
Ouganda	UG	2010	1581160	8431

la table demographie recense la population totale de chaque pays; certaines lignes de cette table sont données en exemple :

pays	periode	pop
BR	2009	193020000
BR	2010	194946000
KE	2010	40909000
ML	2011	14417000
UG	2010	33987000

Q5 - Au vu des données présentées dans la table palu, parmi les attributs nom, iso et annee, quels attributs peuvent servir de clé primaire? Un couple d'attributs pourrait-il servir de clé primaire? (on considère qu'une clé primaire peut posséder plusieurs attributs). Si oui, en préciser un.

Q6 - Écrire une requête en langage SQL qui récupère depuis la table palu toutes les données de l'année 2010 qui correspondent à des pays où le nombre de décès dus au paludisme est supérieur ou égal à 1000 .

On appelle taux d'incidence d'une épidémie le rapport du nombre de nouveaux cas pendant une période donnée sur la taille de la population-cible pendant la même période. Il s'exprime généralement en «nombre de nouveaux cas pour 100000 personnes par année ». Il s'agit d'un des critères les plus importants pour évaluer la fréquence et la vitesse d'apparition d'une épidémie.
Q7 - Écrire une requête en langage SQL qui détermine le taux d'incidence du paludisme en 2011 pour les différents pays de la table palu.

Q8 - Écrire une requête en langage SQL permettant de déterminer le nom du pays ayant eu le deuxième plus grand nombre de nouveaux cas de paludisme en 2010 (on pourra supposer qu'il n'y a pas de pays ex aequo pour les nombres de cas).
On considère la requête

qui s'écrit dans le langage de l'algèbre relationnelle :

On suppose que le résultat de cette requête a été converti en une liste Python stockée dans la variable deces2010 et constituée de couples (chaîne, entier).

Q9 - Quelle instruction peut-on écrire en Python pour trier la liste deces2010 par ordre croissant du nombre de décès dus au paludisme en 2010 ?

Partie II. Modèle à compartiments

On s'intéresse ici à une première méthode de simulation numérique.
Les modèles compartimentaux sont des modèles déterministes où la population est divisée en plusieurs catégories selon leurs caractéristiques et leur état par rapport à la maladie. On considère dans cette partie un modèle à quatre compartiments disjoints : sains ( S , "susceptible"), infectés ( I , "infected"), rétablis ( R , "recovered", ils sont immunisés) et décédés ( D , "dead"). Le changement d'état des individus est gouverné par un système d'équations différentielles obtenues en supposant que le nombre d'individus nouvellement infectés (c'est-à-dire le nombre de ceux qui quittent le compartiment

) pendant un intervalle de temps donné est proportionnel au produit du nombre d'individus infectés avec le nombre d'individus sains.

En notant

la fraction de la population appartenant à chacune des quatre catégories à l'instant

, on obtient le système:

avec

le taux de contagion,

le taux de guérison et

le taux de mortalité. On suppose qu'à l'instant initial

, on a

Q10 - Préciser un vecteur

et une fonction

(en donnant son domaine de définition et son expression) tels que le système différentiel (1) s'écrive sous la forme

Q11 - Compléter la ligne 4 du code suivant (on précise que np. array permet de créer un tableau numpy à partir d'une liste donnant ainsi la possibilité d'utiliser les opérateurs algébriques).

def f(X):
    """ Fonction definissant l'equation differentielle """
    global r, a, b
    # a completer
# Parametres
tmax = 25.
r = 1.
a = 0.4
b = 0.1
X0 = np.array([0.95, 0.05, 0., 0.])
N = 250
dt = tmax/N
t = 0
X = X0
tt = [t]
XX = [X]

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

Figure 1 - Représentation graphique des quatre catégories

en fonction du temps pour

(points) et

(courbes).

Q12 - La figure 1 représente les quatre catégories en fonction du temps obtenues en effectuant deux simulations : la première avec

correspond aux points (cercle, carré, losange, triangle) et la seconde avec

correspond aux courbes. Expliquer la différence entre ces deux simulations. Quelle simulation a nécessité le temps de calcul le plus long?

En pratique, de nombreuses maladies possèdent une phase d'incubation pendant laquelle l'individu est porteur de la maladie mais ne possède pas de symptômes et n'est pas contagieux. On peut prendre en compte cette phase d'incubation à l'aide du système à retard suivant :

où

est le temps d'incubation. On suppose alors que pour tout

En notant

la durée des mesures et

un entier donnant le nombre de pas, on définit le pas de temps

. On suppose que

où

est un entier ; ainsi

est le nombre de pas de retard.

Pour résoudre numériquement ce système d'équations différentielles à retard (avec tmax

), on a écrit le code suivant :

def f(X, Itau):
    """
    Fonction definissant l'equation differentielle
    Itau est la valeur de I(t - p * dt)
    """
    global r, a, b
    # a completer
# Parametres
r = 1.
a = 0.4
b = 0.1
X0 = np.array([0.95, 0.05, 0., 0.])
tmax = 25.
N = 250
dt = tmax/N
p = 50
t = 0
X = X0
tt = [t]
XX = [X]
# Methode d'Euler
for i in range(N):
    t = t + dt
    # a completer
    tt.append(t)
    XX.append(X)

Q13 - Compléter les lignes 7 et 28 du code précédent (utiliser autant de lignes que nécessaire).
On constate que le temps d'incubation de la maladie n'est pas nécessairement le même pour tous les individus. On peut modéliser cette diversité à l'aide d'une fonction positive d'intégrale unitaire (dite de densité)

telle que représentée sur la figure 2 . On obtient alors le système intégro-différentiel :

Figure 2 - Exemple d'une fonction de densité.

On supposera à nouveau que pour tout

. Pour

entier compris entre 0 et

, on pose

. Pour un pas de temps

donné, on peut calculer numériquement l'intégrale à l'instant

à l'aide de la méthode des rectangles à gauche en utilisant l'approximation :

Q14 - On suppose que la fonction

a été écrite en Python. Expliquer comment modifier le programme de la question précédente pour résoudre ce système intégro-différentiel (on explicitera les lignes de code nécessaires).

Partie III. Modélisation dans des grilles

On s'intéresse ici à une seconde méthode de simulation numérique (dite par automates cellulaires).

Dans ce qui suit, on appelle grille de taille

une liste de

listes de longueur

, où

est un entier strictement positif.

Pour mieux prendre en compte la dépendance spatiale de la contagion, il est possible de simuler la propagation d'une épidémie à l'aide d'une grille. Chaque case de la grille peut être dans un des quatre états suivants : saine, infectée, rétablie, décédée. On choisit de représenter ces quatre états par les entiers :

é é é é é

L'état des cases d'une grille évolue au cours du temps selon des règles simples. On considère un modèle où l'état d'une case à l'instant

ne dépend que de son état à l'instant

et de l'état de ses huit cases voisines à l'instant

(une case du bord n'a que cinq cases voisines et trois pour une case d'un coin). Les règles de transition sont les suivantes :

une case décédée reste décédée;
une case infectée devient décédée avec une probabilité ou rétablie avec une probabilité ;
une case rétablie reste rétablie;
une case saine devient infectée avec une probabilité si elle a au moins une case voisine infectée et reste saine sinon.
On initialise toutes les cases dans l'état sain, sauf une case choisie au hasard dans l'état infecté.
Q15 - On a écrit en Python la fonction grille(n) suivante

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

Décrire ce que retourne cette fonction.
On pourra dans la question suivante utiliser la fonction randrange(p) de la bibliothèque random qui, pour un entier positif

, renvoie un entier choisi aléatoirement entre 0 et

inclus.

Q16 - Écrire en Python une fonction init(n) qui construit une grille

de taille

ne contenant que des cases saines, choisit aléatoirement une des cases et la transforme en case infectée, et enfin renvoie

.
Q17 - Écrire en Python une fonction compte (G) qui a pour argument une grille G et renvoie la liste [n0, n1, n2, n3] formée des nombres de cases dans chacun des quatre états.

D'après les règles de transition, pour savoir si une case saine peut devenir infectée à l'instant suivant, il faut déterminer si elle est exposée à la maladie, c'est-à-dire si elle possède au moins une case infectée dans son voisinage. Pour cela, on écrit en Python la fonction est_exposee(G, i, j) suivante.

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 résultat renvoyé par la fonction est_exposee?
Q19 - Compléter les lignes 12 et 20 de la fonction est_exposee.
Q20 - Écrire une fonction suivant (

, p1, p2) qui fait évoluer toutes les cases de la grille G à l'aide des règles de transition et renvoie une nouvelle grille correspondant à l'instant suivant. Les arguments p1 et p2 sont les probabilités qui interviennent dans les règles de transition pour les cases infectées et les cases saines. On pourra utiliser la fonction bernoulli(p) suivante qui simule une variable aléatoire de Bernoulli de paramètre

: bernoulli(p) vaut 1 avec la probabilité p et 0 avec la probabilité (

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 bibliothèque random :

random.random()
    Return the next random floating point number in the range [0.0, 1.0).

Avec les règles de transition du modèle utilisé, l'état de la grille évolue entre les instants

tant qu'il existe au moins une case infectée.
Q21 - Écrire en Python une fonction simulation(n, p1, p2) qui réalise une simulation complète avec une grille de taille

pour les probabilités p1 et p2, et renvoie la liste [

] formée des proportions de cases dans chacun des quatre états à la fin de la simulation (une simulation s'arrête lorsque la grille n'évolue plus).

Q22 - Quelle est la valeur de la proportion des cases infectées x1 à la fin d'une simulation? Quelle relation vérifient

et x 3 ? Comment obtenir à l'aide des valeurs de

et x 3 la valeur x_atteinte de la proportion des cases qui ont été atteintes par la maladie pendant une simulation?

Figure 3 - Représentation de la proportion de la population qui a été atteinte par la maladie pendant la simulation en fonction de la probabilité

On fixe p1 à 0,5 et on calcule la moyenne des résultats de plusieurs simulations pour différentes valeurs de p2. On obtient la courbe de la figure 3.

Q23 - On appelle seuil critique de pandémie la valeur de p2 à partir de laquelle plus de la moitié de la population a été atteinte par la maladie à la fin de la simulation. On suppose que les valeurs de p2 et x_atteinte utilisées pour tracer la courbe de la figure 3 ont été stockées dans deux listes de même longueur Lp2 et Lxa. Écrire en Python une fonction seuil(Lp2, Lxa) qui détermine par dichotomie un encadrement [p2cmin, p2cmax] du seuil critique de pandémie avec la plus grande précision possible. On supposera que la liste Lp2 croît de 0 à 1 et que la liste Lxa des valeurs correspondantes est croissante.

Pour étudier l'effet d'une campagne de vaccination, on immunise au hasard à l'instant initial une fraction

de la population. On a écrit la fonction

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) ?