Help on module PC_Mat2_2015_28: NAME PC_Mat2_2015_28 - Correction d'un exercice de maths avec Python, issu des annales pour les oraux du concours Centrale-Supélec. FILE /home/lilian/teach/info-mp-2015-2016/oraux/PC_Mat2_2015_28.py DESCRIPTION - *Sujet :* PC 2, http://www.concours-centrale-supelec.fr/CentraleSupelec/MultiY/C2015/PC-Mat2-2015-28.pdf - *Dates :* séances de révisions, vendredi 10 et samedi 11 juin (2016). - *Auteur :* Lilian Besson, pour le cours d'informatique pour tous en prépa MP au Lycée Lakanal (http://perso.crans.org/besson/infoMP/), - *Licence :* MIT Licence (http://lbesson.mit-license.org). ----------------------------------------------------------------------------- FUNCTIONS Sn(n) Calcul naïf et rapide de :math:`S_n` définie par : .. math:: S_n := \sum_{0 \leq 2k \leq n} (-1)^k {n \choose 2k}. Tn(n) Calcul naïf et rapide de :math:`T_n` définie par : .. math:: T_n := 2^{\frac{n}{2}} \cos\left(n \frac{\pi}{4} \right). Un(n) Calcul naïf et rapide de :math:`U_n` définie par : .. math:: U_n := \sum_{0 \leq 2k+1 \leq n} (-1)^k {n \choose 2k+1}. .. hint:: On a calculé ``n_moins_1_sur_2_plus_1`` ``1 +`` le plus grand entier ``k`` tel que :math:`2k+1 \leq n`, par ``n_moins_1_sur_2_plus_1 = ((n - 1) // 2) + 1`` (le ``1 +`` vient de ce que ``range(debut, dernier)`` demande à avoir ``dernier = 1 + fin`` pour inclure ``fin``). Vn(n) Calcul naïf et rapide de :math:`V_n` définie par : .. math:: V_n := 2^{\frac{n}{2}} \sin\left(n \frac{\pi}{4} \right). binom(n, k) Calcule efficacement en :math:`\mathcal{O}(\min(k, n-k))` multiplication et division entières le nombre ``binom(n, k)`` :math:`= {n \choose k}` (et en :math:`\mathcal{O}(1)` en mémoire !). - Exemples : >>> binom(6, -3) 0 >>> binom(6, 0) 1 >>> binom(6, 1) 6 >>> binom(6, 2) 15 >>> binom(6, 3) 20 >>> binom(6, 4) 15 >>> binom(6, 5) 6 >>> binom(6, 6) 1 binom_factorial(n, k) Coefficient binomial calculé en utilisant des factorielles (via :py:func:`math.factorial`) : .. math: {n \choose k} = \frac{n!}{k! (n-k)!}. - Exemples : >>> binom_factorial(6, 0) 1 >>> binom_factorial(6, 1) 6 >>> binom_factorial(6, 2) 15 >>> binom_factorial(6, 3) 20 >>> binom_factorial(6, 4) 15 >>> binom_factorial(6, 5) 6 >>> binom_factorial(6, 6) 1 factorial(...) factorial(x) -> Integral Find x!. Raise a ValueError if x is negative or non-integral. q0() Préliminaires : - Comme pour tous ces exercices, on commence par **importer** les modules requis, ici `numpy `_ et `matplotlib `_ : >>> import numpy as np >>> import matplotlib.pyplot as plt q1() Question 1. On commence par écrire une fonction pour calculer :math:`{n \choose k}`, `plusieurs approches `_ sont possibles : 1. on écrit une fonction :py:func:`factorial` (de :math:`\mathbb{N} \to \mathbb{N}`) qui calcule :math:`n!`, et on utilise :math:`{n \choose k} = \frac{n!}{k! (n-k)!}`. Ça marche, mais ce sera assez lent, et très redondant en calculs (cf. :py:func:`binom_factorial`). 2. ou on écrit une fonction :py:func:`binom` directement, en se basant sur la propriété élémentaire :math:`{n \choose k} = (\frac{n-k+1}{k}) {n \choose k-1}`. C'est la deuxième approché, itérative et facile à écrire, que je recommande. - Note: on pense à l'optimisation gratuite qui consiste à remplacer :math:`k` par :math:`\min(k, n-k)`. Ça donne quelque chose comme ça : :: def binom(n, k): if k < 0 or k > n: # Cas de base (n k) = 0 return 0 if k == 0 or k == n: # Cas de base (n k) = 1 return 1 k = min(k, n - k) # Utilise la symétrie ! produit = 1 for i in range(k): produit *= (n - i) for i in range(k): produit //= (i + 1) return int(produit) # Force à être entier ! .. seealso:: En fait, on peut aussi utiliser :py:func:`scipy.special.binom` du module :py:mod:`scipy.special`, qui fonctionne très bien (elle renvoit un flottant attention) : >>> from scipy.special import binom as binom2 >>> binom2(10, 2) 45.0 q2() Question 2. - Dès qu'on dispose d'une fonction :py:func:`binom`, comme demandé en `Q1 <#PC_Mat2_2015_28.q1>`_, on peut écrire très facilement la fonction :py:func:`Sn`, juste en écrivant sa définition : :: def Sn(n): n_sur_2_plus_1 = (n // 2) + 1 return sum((-1)**k * binom(n, 2*k) for k in range(0, n_sur_2_plus_1)) - On a calculé ``n_sur_2_plus_1`` ``1 +`` le plus grand entier ``k`` tel que :math:`2k \leq n` (le ``1 +`` vient de ce que ``range(debut, dernier)`` demande à avoir ``dernier = 1 + fin`` pour inclure ``fin``). - Et on a utilisé :py:func:`range` pour obtenir la liste des :math:`k` tels que :math:`0 \leq 2k \leq n`. q3() Question 3. - On commence par écrire une fonction, très simple aussi, qui calcule :math:`T_n`, en utilisant au choix :py:func:`math.cos` ou :py:func:`numpy.cos`, et :py:data:`math.py` ou :py:data:`numpy.py`, pour calculer :math:`\cos\left(n \frac{\pi}{4}\right)`. Cf. :py:func:`Tn` : :: def Tn(n): return 2.0 ** (n / 2) * np.cos(n * np.pi / 4) - Ensuite, on calcule les valeurs de :math:`S_n` et :math:`T_n` pour :math:`n = 0, \dots, 10`, avec :py:func:`Sn` et :py:func:`Tn` : :: valeurs_n = list(range(0, 10 + 1)) valeurs_Sn = [ Sn(n) for n in valeurs_n ] valeurs_Tn = [ Tn(n) for n in valeurs_n ] - Puis on les affiche, simplement avec :py:func:`matplotlib.pyplot.plot` (``plt.plot``) : :: plt.figure() # Nouvelle figure plt.hold(True) # Plusieurs graphiques sur la même figure plt.plot(valeurs_n, valeurs_Sn, 'b+-', label='$S_n$') plt.plot(valeurs_n, valeurs_Tn, 'r*-', label='$T_n$') plt.title("Valeurs de $S_n$, $T_n$ pour $n = 0 ... 10$.") # Ajoute un titre plt.legend() # Utilise les deux label='...' plus hauts plt.show() # On montre la figure. - Cela devrait donner une figure comme ça : .. image:: PC_Mat2_2015_28__figure1.png - Et on constate que :math:`T_n` et :math:`S_n` sont égaux. C'est ce qu'on va montrer en `Q6 <#PC_Mat2_2015_28.q6>`_ (:eq:`snun`). q4() Question 4. - C'est du cours, ça vient du cours de maths et pas d'informatique. - Si besoin, n'hésitez pas à `relire une fiche de rappels sur les développements entières `_ (ou `sur les développements limités `_). - On se souvient donc que :math:`\exp` et :math:`\cos` ont un développements en série entière, de rayons de convergence :math:`R = +\infty`, donnés par ces formules : .. math:: \exp(x) &= \sum_{k=0}^{+\infty} \frac{x^k}{k!}, \\ \cos(x) &= \sum_{k=0}^{+\infty} (-1)^{k} \frac{x^{2k}}{(2k)!}. .. hint:: Il est absolument VITAL de se souvenir de la formule pour :math:`\exp(x)`, puisqu'elle permet de retrouver plein d'autres développements : - :math:`\cosh` est la partie paire de :math:`\exp`, donc :math:`\cosh(x) = \sum\limits_{k=0}^{+\infty} \frac{x^{2k}}{(2k)!}` en gardant les puissances paires, - :math:`\sinh` est la partie impaire de :math:`\exp`, donc :math:`\sinh(x) = \sum\limits_{k=0}^{+\infty} \frac{x^{2k+1}}{(2k+1)!}` en gardant les puissances impaires, - :math:`\cos` est la partie réelle de :math:`x\mapsto\exp(ix)`, donc :math:`\cos(x) = \sum\limits_{k=0}^{+\infty} \frac{(ix)^{2k}}{(2k)!} = \sum\limits_{k=0}^{+\infty} (-1)^k \frac{x^{2k}}{(2k)!}` en gardant les puissances paires, - :math:`\sin` est la partie imaginaire de :math:`x\mapsto\exp(ix)`, donc :math:`\sin(x) = \frac{1}{i} \sum\limits_{k=0}^{+\infty} \frac{(ix)^{2k+1}}{(2k)!} = \sum\limits_{k=0}^{+\infty} (-1)^k \frac{x^{2k+1}}{(2k)!}` en gardant les puissances impaires. q5() Question 5. - C'est aussi du cours, on prend le produit :math:`x \mapsto \cos(x) \mathrm{e}^x` de deux fonctions :math:`\cos` et :math:`\exp` développables en séries entières, toutes les deux de rayon :math:`R = +\infty`. - Donc la fonction produit est aussi développable en S.E. et de rayon aussi :math:`R = +\infty` (c'est le cas le plus simple du théorème du produit de Cauchy). .. attention:: Le sujet ne demandait PAS de donner ici le développement de :math:`x \mapsto \cos(x) \mathrm{e}^x`, mais ce sera requis à la question suivante... q6() Question 6. - Question purement mathématique, mais elle n'est vraiment pas facile. - J'ai tenté au brouillon un bon moment, et tous les élèves présents au TP ont aussi essayé, sans succès. - **En fait, ça a l'air assez dur**. Nous n'avons pas réussi en TD avec toute la classe. Si vous avez une idée, `contactez-moi svp `_. q7() Question 7. - Ici, le sujet demandait de prouver la même chose qu'à la question précédente, mais sans faire appel aux séries entières, et surtout, *sans indication*. - Il faut savoir être inventif, ou passer à la question suivante si on a aucune idée d'approche. - La démonstration est faite à la question suivante `Q8 <#PC_Mat2_2015_28.q8>`_ ci-dessous. q8() Question 8. - On commence par appliquer, pour un :math:`n \geq 1`, le binôme de Newton à :math:`(1 + i)^n` donne : .. math:: (1 + i)^n &= \sum_{k=0}^{n} 1^{n-k} i^k {n \choose k} \\ &= \sum_{k=0}^{n} i^k {n \choose k} \\ &= \sum_{0 \leq 2k \leq n} (-1)^k {n \choose 2k} + i \sum_{0 \leq 2k+1 \leq n} (-1)^k {n \choose 2k+1}. - Donc :math:`S_n = \mathcal{R}\mathrm{eal}((1+i)^n)`, et cette deuxième somme :math:`U_n := \sum\limits_{0 \leq 2k+1 \leq n} (-1)^k {n \choose 2k+1} = \mathcal{I}\mathrm{mag}((1+i)^n)`. - Mais on peut aussi écrire :math:`(1+i)` en forme polaire, à savoir un module :math:`= \sqrt{2}` et une phase :math:`= \frac{\pi}{4}` : .. math:: (1+i) = \sqrt{2} \mathrm{e}^{i \frac{\pi}{4}} - Donc :math:`(1+i)^n = \sqrt{2}^n \mathrm{e}^{i n \frac{\pi}{4}}`, ce qui prouve directement le résultat demandé en `Q7 <#PC_Mat2_2015_28.q7>`_ et ici en `Q8 <#PC_Mat2_2015_28.q8>`_ : .. math:: :label: snun S_n &= \sum_{0 \leq 2k \leq n} (-1)^k {n \choose 2k} &= 2^{\frac{n}{2}} \cos(n \frac{\pi}{4}) \\ U_n &= \sum_{0 \leq 2k+1 \leq n} (-1)^k {n \choose 2k+1} &= 2^{\frac{n}{2}} \sin(n \frac{\pi}{4}). - Le sujet demandait qu'on vérifie cette dernière formule pour :math:`U_n` par simulation, on fait donc exactement la même chose qu'aux questions `Q2 <#PC_Mat2_2015_28.q2>`_ et `Q3 <#PC_Mat2_2015_28.q3>`_ : :: def Un(n): n_moins_1_sur_2_plus_1 = ((n - 1) // 2) + 1 return sum((-1)**k * binom(n, 2*k+1) for k in range(1, n_sur_2_plus_1)) - Et une deuxième fonction, pour calculer :math:`V_n := 2^{\frac{n}{2}} \sin(n \frac{\pi}{4})` : :: def Vn(n): return (np.sqrt(2) ** float(n)) * np.sin(n * np.pi / 4.0) - Ensuite, on calcule les valeurs de :math:`U_n` et :math:`V_n` pour :math:`n = 0, \dots, 10`, avec :py:func:`Un` et :py:func:`Tn` : :: valeurs_n = list(range(0, 10 + 1)) valeurs_Un = [ Un(n) for n in valeurs_n ] valeurs_Vn = [ Vn(n) for n in valeurs_n ] - Puis on les affiche, simplement avec :py:func:`matplotlib.pyplot.plot` (``plt.plot``), comme en `Q3 <#PC_Mat2_2015_28.q3>`_. - Cela devrait donner une figure comme ça : .. image:: PC_Mat2_2015_28__figure2.png - Et on constate que :math:`U_n` et :math:`V_n` sont égaux. C'est ce qu'on a montré juste avant en `Q8 <#PC_Mat2_2015_28.q8>`_ (:eq:`snun`). DATA division = _Feature((2, 2, 0, 'alpha', 2), (3, 0, 0, 'alpha', 0), 8192... print_function = _Feature((2, 6, 0, 'alpha', 2), (3, 0, 0, 'alpha', 0)...