#! /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