Code source de PC_Mat2_2015_28

#! /usr/bin/env python3
# -*- coding: utf-8; mode: python -*-
r""" Correction d'un exercice de maths avec Python, issu des annales pour les oraux du concours Centrale-Supélec.

- *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).

-----------------------------------------------------------------------------

"""

from __future__ import print_function, division  # Python 2 compatibility

import numpy as np
import matplotlib.pyplot as plt


# %% Question 0.
[docs]def q0(): r""" Préliminaires : - Comme pour tous ces exercices, on commence par **importer** les modules requis, ici `numpy <https://docs.scipy.org/doc/numpy/>`_ et `matplotlib <http://matplotlib.org/users/beginner.html>`_ : >>> import numpy as np >>> import matplotlib.pyplot as plt """ pass
# %% Question 1.
[docs]def q1(): r""" Question 1. On commence par écrire une fonction pour calculer :math:`{n \choose k}`, `plusieurs approches <https://en.wikipedia.org/wiki/Binomial_coefficient#Binomial_coefficient_in_programming_languages>`_ 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 """ pass
[docs]def binom(n, k): r""" 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 """ 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 !
from math import factorial
[docs]def binom_factorial(n, k): r""" 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 """ return factorial(n) // (factorial(k) * factorial(n - k))
# %% Question 2.
[docs]def q2(): r""" 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`. """ pass
[docs]def Sn(n): r""" 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}. """ 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))
[docs]def Tn(n): r""" 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). """ return (np.sqrt(2) ** float(n)) * np.cos(n * np.pi / 4.0)
# %% Question 3.
[docs]def q3(): r""" 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`). """ # Calculs 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] # Affichage plt.figure() # Nouvelle figure plt.hold(True) # Plusieurs graphiques sur la même figure plt.plot(valeurs_n, valeurs_Sn, 'b+-', label='$S_n$', ms=10) plt.plot(valeurs_n, valeurs_Tn, 'r*:', label='$T_n$', ms=14) plt.title("Valeurs de $S_n$, $T_n$ pour $n = 0 ... 10$.") # Ajoute un titre plt.legend(loc='upper left') # Utilise les deux label='...' plus hauts plt.savefig("PC_Mat2_2015_28__figure1.png", dpi=180) # On sauvegarde la figure ! plt.show() # On montre la figure.
# %% Question 4.
[docs]def q4(): r""" 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 <http://mp.cpgedupuydelome.fr/cours.php?id=12996>`_ (ou `sur les développements limités <http://mp.cpgedupuydelome.fr/cours.php?id=3993>`_). - 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. """ pass
# %% Question 5.
[docs]def q5(): r""" 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... """ pass
# %% Question 6.
[docs]def q6(): r""" 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 <http://perso.crans.org/besson/contact/>`_. """ # FIXME la faire moi-même ! pass
# %% Question 7.
[docs]def q7(): r""" 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. """ pass
# %% Question 8.
[docs]def q8(): r""" 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`). """ # Calculs 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] # Affichage plt.figure() # Nouvelle figure plt.hold(True) # Plusieurs graphiques sur la même figure plt.plot(valeurs_n, valeurs_Un, 'b+-', label='$U_n$', ms=10) plt.plot(valeurs_n, valeurs_Vn, 'r*:', label='$V_n$', ms=14) plt.title("Valeurs de $U_n$, $V_n$ pour $n = 0 ... 10$.") # Ajoute un titre plt.legend(loc='upper left') # Utilise les deux label='...' plus hauts plt.savefig("PC_Mat2_2015_28__figure2.png", dpi=180) # On sauvegarde la figure ! plt.show() # On montre la figure.
[docs]def Un(n): r""" 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``). """ n_moins_1_sur_2_plus_1 = ((n - 1) // 2) + 1 return sum((-1)**k * binom(n, 2 * k + 1) for k in range(0, n_moins_1_sur_2_plus_1))
[docs]def Vn(n): r""" 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). """ return (np.sqrt(2) ** float(n)) * np.sin(n * np.pi / 4.0)
# %% Fin de la correction. if __name__ == '__main__': from doctest import testmod print("Test automatique de toutes les doctests ecrites dans la documentation (docstring) de chaque fonction :") testmod(verbose=True) # testmod() print("\nPlus de details sur ces doctests peut etre trouve dans la documentation de Python:\nhttps://docs.python.org/3/library/doctest.html (en anglais)") # Fin de PC_Mat2_2015_28.py