Cminesponts16.tex

Ce texte est le corrigé des parties I et II de l'épreuve IPT toutes filières du concours communs Mines Ponts de 2016. La numérotation des questions est conservée depuis le texte original.
\paragraph{Q1} Présentons dans un tableau l'entier représenté par \texttt{i} et la liste représentée par $L$ après chaque itération
\begin{center}
\renewcommand{\arraystretch}{1.3}
\begin{tabular}{l|c|c|c|c}
$i$ & 1                 & 2                 &                 3 & 4                 \\ \hline
$L$ & $[2, 5, 3, 1, 4]$ & $[2, 3, 5, 1, 4]$ & $[1, 2, 3, 5, 4]$ & $[1, 2, 3, 4, 5]$ \\ \hline
\end{tabular}
\end{center}

\paragraph{Q2} Considérons la propriété $\mathcal{P}_i$ :  \og La liste \texttt{L[0:i]} est croissante\fg. \newline
Cette proposition est vraie lorsque $i$ désigne $0$ car la liste contient alors un seul élément. Il s'agit donc de montrer que 
\begin{displaymath}
L[0]\leq \cdots \leq L[i] \text{ (avant itér.)} \Rightarrow  L[0]\leq \cdots \leq L[i] \leq L[i+1] \text{ (après itér.)}. 
\end{displaymath}
Pour le justifier, reformulons l'effet du code Python.\newline
Il sauve d'abord la valeur de $L[j]$ dans une variable $x$. Ensuite, en décrémentant $j$ à partir de $i$, il cherche le premier $j$ tel que $L[j]\leq x$ tout en décalant vers la droite les valeurs de $L$ traversées. Ces valeurs traversées sont croissantes et strictement plus grandes que $x$. Il replace alors le $x$ à la position $j$ libérée par le décalage à droite. On a donc
\begin{displaymath}
  L[0] \leq L[1] \leq \cdots \leq L[i] \leq L[i+1]
\end{displaymath}
Cet algorithme de tri est appelée \emph{tri par insertion}.

\paragraph{Q3} Le meilleur des cas se produit lorsque pour chaque valeur de $i$ le $j$ cherché est $j-1$. Cela signifie que 
\begin{displaymath}
  \forall i, \; L[i-1] \leq L[i]
\end{displaymath}
La liste $L$ est alors croissante. Comme il a fallu quand même parcourir une liste de longueur $n$, la complexité dans le meilleur des cas est linéaire (en  $O(n)$).\newline
Le pire des cas se produit lorsque, pour chaque valeur de $i$, le $j$ cherché est $0$. Cela signifie que chaque nouvelle valeur de $L$ est plus petite que toutes les précédentes c'est à dire que la suite est \emph{décroissante}. Pour chaque valeur de $i$, il faut donc parcourir une liste de longueur $i$ donc au moins $\frac{n(n+1)}{2}$ opérations. La complexité dans le pire des cas est quadratique (en $O(n^2)$).

\paragraph{Q4} On adapte la fonction \texttt{tri} en une fonction \texttt{tri\_chaine} qui utilise le champ numérique de chaque liste. Cela revient essentiellement à ajouter un \og\texttt{[1]}\fg~ aux variables dans le test.
\lstinputlisting[firstline=1, lastline=9]{Cminesponts16.py}
Noter que cette fonction change la liste désignée par \texttt{L} en place (sans la renvoyer) en utilisant la possibilité de modifier une liste.

\paragraph{Q10} Pour écrire le système différentiel sous la forme $X'(t) = f(X)$, on utilise un vecteur 
\begin{displaymath}
  X(t) = (S(t), I(t), R(t), D(t))
\end{displaymath}
et une fonction $f$ définie dans $\R^4$ par 
\begin{displaymath}
  \forall (s,i,r,d),\; f((s,i,r,d)) = \left( -r s i, -rsi -(a+b)i, ai,bi \right) 
\end{displaymath}

\paragraph{Q11} On complète le calcul du champ et son renvoi par la fonction
\lstinputlisting[firstline=16, lastline=22]{Cminesponts16.py}

\paragraph{Q12} L'erreur entre les solutions numériques approchées et les solutions formelles est certainement plus grand avec $N=7$ qu'avec $N=250$. La simulation avec $N=250$ a utilisé un plus grand temps de calcul.

\paragraph{Q13} On modifie d'abord la fonction pour tenir compte de l'effet retard (ligne 7)
\lstinputlisting[firstline=24, lastline=29]{Cminesponts16.py}
puis la boucle de calcul de la méthode d'Euler (ligne 28)
\lstinputlisting[firstline=31, lastline=40]{Cminesponts16.py}

\paragraph{Q14} On peut remplacer la ligne \texttt{Itau = XX[i-p][i]} par 
\begin{verbatim}
  Itau = dt * sum( XX[i-j][1] * h(j*dt) for j in range(p) )
\end{verbatim}