#! /usr/bin/env python3
# -*- coding: utf-8; mode: python -*-
""" Correction du DS#4 du vendredi 05 février (2016).
Voici ci-dessous la documentation de la correction complète du sujet d'écrit d'informatique.
Ce sujet d'écrit a été posé en devoir écrit (DS) pour le cours d'informatique pour tous en prépa MP au Lycée Lakanal.
Veuillez `consulter le code source pour tous les détails <_modules/DS2_info.html>`_ svp.
Ci dessous se trouve simplement la *documentation* de ce programme.
- *Date :* Mercredi 03 février 2016,
- *Auteur :* Lilian Besson, pour le cours d'informatique pour tous en prépa MP (http://perso.crans.org/besson/infoMP/),
- *Licence :* MIT Licence (http://lbesson.mit-license.org).
-----
.. note:: Cette correction vient en grande partie de la correction PDF faite par Arnaud Basson.
**Correction :**
(le barème est indiqué pour chaque question)
"""
from __future__ import print_function # Python 2 compatibility
import numpy as np
import matplotlib.pyplot as plt
if __name__ == '__main__':
print(__doc__)
# %% Partie I : Numérisation du signal
print("\n\nPartie I : Numerisation du signal")
[docs]def I_Q1_a():
r""" Réponse à la question **I.1.a)** (0.5 pt). *C'est du cours.*
On peut coder sur :math:`10` bits les entiers de :math:`-2^9` à :math:`2^9 - 1` (bornes *incluses*), c'est-à-dire de :math:`-512` à :math:`511`.
"""
pass
[docs]def I_Q1_b():
r""" Réponse à la question **I.1.b)** (0.5 pt).
La plage de valeurs du signal a une largeur de 10 V, et on peut coder 1024 valeurs, donc la précision est de 10/1024 V, soit environ 0.01 V.
"""
pass
#: Valeur typique de :math:`N = 1000` points.
N = 1000
[docs]def I_Q2():
r""" Réponse à la question **I.2)** (0.5 pt). *C'est encore du cours.*
Un nombre flottant à 32 bits occupe 4 octets (rappel : **1 octet = 8 bits**, c'est d'ailleurs l'origine de ce nom *"octet"* : octet pour huit),
donc pour stocker 1000 nombres flottants à 32 bits il faut 4 ko (= 4 kilo-octets, au sens de 4 fois 1000 octets, et pas KiO qui serait 1024 octets).
.. seealso::
Il est crucial de connaître les bases du codage des nombres flottants sur un ordinateur :
au moins la définition `d'un octet <https://fr.wikipedia.org/wiki/Octet#Bits_et_octets>`_, et des `"bits" <https://fr.wikipedia.org/wiki/Bit>`_ informatique (sur Wikipédia).
.. note:: Dans toute la suite, on dispose de la bibliothèque `Numpy <http://www.numpy.org/>`_, importée par ``import numpy as np`` (et donc disponible via le nom ``np``, e.g., ``np.sum`` ou ``np.sin``).
"""
pass
# %% Partie II : Filtrage du signal
print("\n\nPartie II : Filtrage du signal")
#: Variable globale pour la pulsation de coupure du filtre.
#: Sa valeur réelle n'a pas d'importance ici.
omegac = 1
#: Valeur de la période d'échantillonage :math:`T_e` (i.e., le pas de temps auquel on échantillone le signal).
#: Sa valeur réelle n'a pas non plus d'importance ici.
Te = 1
[docs]def II_Q3_a():
r""" Réponse à la question **II.3.a)** (1 pt). C'est (presque) du cours.
On effectue deux approximations, :eq:`approx1` est une approximation de la dérivée par une pente de longueur :math:`T_e`, et :eq:`approx2` est la même approximation pour la dérivée seconde, en utilisant ensuite :eq:`approx1` deux fois.
.. math::
:label: approx1
\forall n \in \mathbb{N}^{\star},\;\;\; \dot{U}_f(n T_e) \simeq \frac{U_f(n T_e) - U_f((n-1) T_e)}{T_e}.
.. math::
:label: approx2
\forall n \in \mathbb{N}^{\star},\;\;\; \ddot{U}_f(n T_e) & \simeq \frac{\dot{U}_f(n T_e) - \dot{U}_f((n-1) T_e)}{T_e} \\
& \simeq \frac{U_f(n T_e) - 2 U_f((n-1) T_e) + U_f((n-2) T_e)}{T_e^2}.
"""
pass
[docs]def II_Q3_b():
r""" Réponse à la question **II.3.b)** (1 pt).
On rappelle qu'on étudie l'équation différentielle suivante :
.. math::
:label: eqdiff
\frac{1}{\omega_c^2} \ddot{U}_f(t) + \frac{\sqrt{2}}{\omega_c} \dot{U}_f(t) + U_f(t) = U_e(t).
Une fois qu'on dispose de ces deux approximations :eq:`approx1` et :eq:`approx2`, on peut **discrétiser** l'équation différentielle :eq:`eqdiff` :
.. math::
:label: discretisation0
\frac{U_f(n T_e) - 2 U_f((n-1) T_e) + U_f((n-2) T_e)}{\omega_c^2 T_e^2} \\
+ \sqrt{2}\frac{U_f(n T_e) - U_f((n-1) T_e)}{T_e} + U_f(n T_e) = U_e(n T_e).
Soit donc, en isolant le terme :math:`U_f(n T_e)` (d'après l'énoncé), on obtient précisément la relation demandée, avec :math:`\alpha := \frac{1}{\omega_c T_e}` :
.. math::
:label: discretisation
U_f(n T_e) &= \frac{U_e(n T_e) + (\alpha \sqrt{2} + 2 \alpha^2) U_f((n-1) T_e) - \alpha^2 U_f((n-2) T_e)}{\alpha^2 + \alpha \sqrt{2} + 1}. \\
U_f^{n} &\leftarrow \frac{U_e^{n} + (\alpha \sqrt{2} + 2 \alpha^2) U_f^{n-1} - \alpha^2 U_f^{n-2}}{\alpha^2 + \alpha \sqrt{2} + 1}.
.. attention::
Lorsqu'on écrit cette égalité, c'est vrai pour la *relation de récurrence* que l'on définit alors pour les valeurs successives de :math:`\left( U_F^{n} \right)_{n\in\mathbb{N}}` (avec :math:`U_f^{n} := U_f(n T_e)`), mais *attention*, tout cela n'est qu'une approximation (discrète) de la solution (continue) de l'équation différentielle :eq:`eqdiff` du filtre.
"""
pass
[docs]def II_Q4():
r""" Réponse à la question **II.4)** (1.5 pt).
- En suivant l'énoncé, on prend comme conditions initiales :math:`U_f(0) = 0` et :math:`\dot{U}_f(0) = 0`. Attention, il faut vraiment utiliser les initialisations demandées.
- D'après :eq:`approx1`, en approchant :math:`\dot{U}_f(0) \simeq \frac{1}{T_e} (U_f(T_e) - U_f(0))`, on discrétise les conditions initiales en posant :math:`U_f(0) = U_f(T_e) = 0`.
Cela amène au code suivant, qui ressemble dans sa structure à un schéma d'Euler :
.. code-block:: python
def filtrage(Ue, Te):
N = len(Ue)
alpha = 1/(omegac*Te)
beta = alpha*np.sqrt(2) + 2*alpha**2
gamma = alpha**2 + alpha*np.sqrt(2) + 1
Uf = [0.]*N
for n in range(2,N):
Uf[n] = ( Ue[n] + beta*Uf[n-1] - (alpha**2)*Uf[n-2] ) / gamma
return Uf
Ce code calcule les :math:`N` premiers termes de la suite :math:`U_f^{n}` (i.e., :math:`U_f(n T_e))`),
et les renvoie dans une liste de même format que ``Ue =`` :math:`[U_e^{0}, U_0^{1}, \dots, U_0^{N-1}]`.
"""
pass
[docs]def filtrage(Ue, Te):
r""" Fonction de filtrage du signal discrétisé, par résolution approchée de l'équation différentielle :eq:`eqdiff`, via la relation de récurrence :eq:`discretisation`.
- Complexité en mémoire : :math:`\mathcal{O}(n)`,
- Complexité en temps : :math:`\mathcal{O}(n)`.
- Remarque : on pensera à être malin, et à calculer les différentes constants qui interviennent dans la récurrence (:math:`\alpha = \frac{1}{\omega_c T_e}`, :math:`\beta := \sqrt{n}\alpha + 2 \alpha^2`, et :math:`\gamma := \alpha^2 + \alpha \sqrt{2} + 1`) une seule fois, avant la boucle ``for``.
"""
N = len(Ue)
alpha = 1/(omegac*Te)
beta = alpha*np.sqrt(2) + 2*alpha**2
gamma = alpha**2 + alpha*np.sqrt(2) + 1
Uf = [0.] * N # Tableau plein de 0., de taille N
for n in range(2, N):
Uf[n] = (Ue[n] + beta*Uf[n-1] - (alpha**2)*Uf[n-2]) / gamma
return Uf
# %% Partie III : Détermination de la fréquence de vibration
print("\n\nPartie III : Determination de la frequence de vibration")
[docs]def III_Q5():
r""" Réponse à la question **III.5)** (2 pts).
- On rappelle que le nombre complexe :math:`i` est noté `1j`` en Python, et que la fonction ``abs`` calcule le module :math:`|\cdot|` d'un nombre complexe.
- Attention au décalage d'indice entre la description mathématique et l'implémentation Python : le :math:`j^{\text{eme}}` élément du tableau à calculer est le module de :math:`\mathcal{T}(U_f)(j - \frac{N}{2})`.
- Voici une solution assez basique :
.. code-block:: python
def fourier(Uf):
N = len(Uf) # Supposé pair
P = N//2
TUf = [0.]*N
for k in range(-P,P):
for n in range(N):
TUf[k+P] += Uf[n] * np.exp(2j*np.pi*k*n/N)
TUf[k+P] = abs(TUf[k+P])
return TUf
"""
pass
[docs]def fourier(Uf):
r""" Calcule la transformée de Fourier discrète du signal ``Uf``, selon les formules données dans l'énoncé, et avec le code montré plus haut.
- ``N = len(Uf)`` est supposé pair. Un message peut être affiché si ce n'est pas le cas, mais ce n'était pas attendu par l'énoncé (et c'est très rarement demandé dans les sujets de concours).
- Le nombre :math:`\pi` est obtenu par ``np.pi`` (ou bien ``math.pi`` mais il faut alors penser à importer la bibliothèque ``math``).
- Complexité en temps : :math:`\mathcal{O}(N^2)` (deux boucles ``for`` imbriquées, de taille ``N``),
- Complexité en mémoire : :math:`\mathcal{O}(n)`.
"""
N = len(Uf) # Supposé pair
# Si on veut, on peut afficher un message...
if N % 2 != 0:
print("ATTENTION: fonction fourier(..), N n'est pas pair (il faut %i)." % N)
P = N//2
TUf = [0.] * N # Tableau plein de 0., de taille N
for k in range(-P, P): # On utilise la notation la plus mathématique possible
for n in range(N):
TUf[k+P] += Uf[n] * np.exp(2j * np.pi * k * n / N)
TUf[k+P] = abs(TUf[k+P])
return TUf
[docs]def fourier2(Uf):
r""" Le sujet n'interdisait ni ne demandait l'utilisation des tableaux Numpy, mais on peut montrer ici comment les utiliser pour économiser une boucle :
.. code-block:: python
def fourier2(Uf):
N = len(Uf) # Supposé pair
P = N//2
Uf = np.array(Uf) # Transformation de liste en tableau numpy
nn = np.array(range(N)) # = [0,1, ..., N-1]
# Note : np.arange(0, N, 1) fait pareil.
TUf = [0.]*N
for k in range(-P,P):
# for n in range(N):
# TUf[k+P] += Uf[n] * np.exp(2j*np.pi*k*n/N)
# TUf[k+P] = abs(TUf[k+P])
# Ces trois lignes sont faites en une seule :
TUf[k+P] = abs(np.sum(Uf * np.exp(2j*np.pi*k/N*nn)))
return TUf
- Complexité en temps : :math:`\mathcal{O}(N^2)` dans tous les cas (que la boucle interne soit explicite ou qu'elle soit implicitement contenue dans une instruction numpy ne change pas l'ordre de grandeur, cela améliore seulement la constante cachée dans le grand :math:`\mathcal{O}(...)`),
- Complexité en mémoire : :math:`\mathcal{O}(n)`.
"""
N = len(Uf) # Supposé pair
P = N // 2
Uf = np.array(Uf) # Transformation de liste en tableau numpy
nn = np.array(list(range(N))) # = [0,1, ..., N-1]
# Note : np.arange(0, N, 1) fait pareil.
TUf = [0.] * N # Tableau plein de 0., de taille N
for k in range(-P, P): # On utilise la notation la plus mathématique possible
# for n in range(N):
# TUf[k+P] += Uf[n] * np.exp(2j*np.pi*k*n/N)
# TUf[k+P] = abs(TUf[k+P])
# Ces trois lignes sont faites en une seule :
TUf[k+P] = abs(np.sum(Uf * np.exp(2j*np.pi*k/N*nn)))
return TUf
[docs]def III_Q6():
r""" Réponse à la question **III.6)** (2 pts).
- On utilise la transformée de Fourier discrète (calculée avec la fonction :py:func:`fourier` écrite juste avant), pour calculer une valeur approchée de la fréquence.
- En suivant les indications de l'énoncé, cela donne un code qui devrait ressembler à ça (au nom près des variables !) :
.. code-block:: python
def frequence(Uf, Te):
N = len(Uf)
TUf = fourier(Uf) # = [|T(Uf)(-N/2)|, ..., |T(Uf)(0)|, ..., |T(Uf)(N/2-1)|]
Tmax = TUf[0] # Valeur du maximum
kmax = N/2
# Valeur De |k| correspondante (-N/2 <= k < N/2)
for i in range(1, N):
if TUf[i] > Tmax:
Tmax = TUf[i]
kmax = abs(i-N/2) # Car TUf[i] = T(Uf)(i-N/2)
elif TUf[i] == Tmax and abs(i-N/2) < kmax:
kmax = abs(i-N/2)
return kmax/(N*Te)
"""
pass
[docs]def frequence(Uf, Te):
r""" Calcule la période approchée du signal ``Uf``.
- Complexité en temps : :math:`\mathcal{O}(N^2)`, à cause de l'appel à la fonction :py:func:`fourier` (la détermination du maximum a en fait un coût négligeable devant le calcul de la transformée de Fourier !),
- Complexité en mémoire : :math:`\mathcal{O}(n)`.
"""
N = len(Uf)
TUf = fourier(Uf) # = [|T(Uf)(-N/2)|, ..., |T(Uf)(0)|, ..., |T(Uf)(N/2-1)|]
Tmax = TUf[0] # Valeur du maximum
kmax = N/2
# Valeur De |k| correspondante (-N/2 <= k < N/2)
for i in range(1, N):
if TUf[i] > Tmax:
Tmax = TUf[i]
kmax = abs(i-N/2) # Car TUf[i] = T(Uf)(i-N/2)
elif TUf[i] == Tmax and abs(i-N/2) < kmax:
kmax = abs(i-N/2)
return kmax/(N*Te)
# %% Partie IV : Détection d'une modification de la fissure
print("\n\nPartie IV : Detection d'une modification de la fissure")
[docs]def IV_Q7_a():
r""" Réponse à la question **IV.7.a)** (1 pt).
Si :math:`m` désigne la moyenne de :math:`n` valeurs :math:`f_0, \dots, f_{n-1}`, alors la moyenne :math:`m'` avec une valeur :math:`f_n` supplémentaire est donnée par :
.. math::
:label: nvlmoyenne
m' := \frac{f_0 + \dots + f_n}{n + 1} = \frac{n}{n+1}\frac{f_0 + \dots + f_{n-1}}{n} + \frac{f_n}{n+1} = \frac{nm + f_n}{n + 1}.
(C'est en fait une astuce très classique, à retenir.)
"""
pass
[docs]def moyenne_optimisee(f, moy, n):
r""" Calcule la nouvelle moyenne, de façon optimisée, en utilisant :eq:`nvlmoyenne`.
- *Arguments* :
- la nouvelle mesure ``f`` :math:`= f_n`,
- la valeur précédente de la moyenne ``moy`` :math:` = m`,
- et le nombre ``n`` de mesures précédentes (``n = len(liste_freq)``).
- Complexité en temps : :math:`\mathcal{O}(1)`, alors qu'un calcul standard de la nouvelle moyenne aurait coûté :math:`\mathcal{O}(n)`,
- Complexité en mémoire : :math:`\mathcal{O}(1)`.
"""
return (moy * n + f) / (n + 1)
[docs]def IV_Q7_b():
r""" Réponse à la question **IV.7.b)** (1.5 pt).
On procède de façon similaire. Il est commode d'utiliser la somme des carrés des :math:`f_k` comme variable auxiliaire pour la mise à jour :
.. math:: \texttt{somme_carres} := \sum_{k=0}^{n-1} f_k^2.
Et cela donne donc cette seconde formule :
.. math::
:label: nvlecarttype
\begin{cases}
\texttt{somme_carres} \; \texttt{+=} f_{n}^2, \\
e' = \sqrt{ \frac{\texttt{somme_carres}}{n+1} - m'^2 }
\end{cases}
"""
pass
[docs]def ecart_type_optimise(f, moy, somme_carres, n):
r""" Calcule le nouvel écart-type, de façon optimisée, en utilisant :eq:`nvlecarttype`.
- *Arguments* :
- la nouvelle mesure ``f`` :math:`= f_n`,
- la nouvelle moyenne ``moy`` :math:` = m'` (après la mise à jour via la fonction précédente :py:func:`moyenne_optimisee`),
- l'ancienne somme des carrées, ``somme_carres``,
- et le nombre ``n`` de mesures précédentes (``n = len(liste_freq)``).
- Complexité en temps : :math:`\mathcal{O}(1)`, alors qu'un calcul standard de la nouvelle moyenne aurait coûté :math:`\mathcal{O}(n)`,
- Complexité en mémoire : :math:`\mathcal{O}(1)`.
"""
somme_carres += f**2
ec = np.sqrt(somme_carres/(n+1) - moy**2)
return somme_carres, ec
[docs]def acquisition():
r""" Le sujet sopposait qu'on dispose d'une fonction ``acquisition()`` qui renvoit, à un instant donné, la valeur d'un échantillonage ``Ue, Te``.
- Comme le code de cette modélisation ne sera pas exécutée, inutile de chercher à avoir une fonction :py:func:`acquisition` cohérente.
- L'énoncé ne demandait *pas* d'écrire cette fonction soi-même.
"""
raise ValueError("acquisition(...): Non implementee !")
#: Variable **globale** de l'état de l'alarme.
#: Initialement le système va bien et donc l'alarme n'est pas déclenchée.
alarme = False
[docs]def IV_Q8():
r""" Réponse à la question **IV.8)** (3.5 pts).
La fonction analyse initialise les différentes variables (``liste_freq``, ``moy``, ``somme_carres``,
``n``), puis elle lance une boucle qui toutes les 10 secondes calcule une nouvelle fréquence ``f``
(grâce aux fonctions des parties précédentes), fait le test de déclenchement de l'alarme puis
met à jour les variables.
.. code-block:: python
def analyse():
global alarme
liste_freq = []
n = 0
moy = somme_carres = ec = 0.0
while not alarme:
# Mesure et calcul d'une nouvelle fréquence
Ue, Te = acquisition()
Uf = filtrage(Ue, Te)
f = frequence(Uf, Te)
# Test de déclenchement de l'alarme
if n > 10 and abs(f-moy) > 5*ec:
alarme = True
# Mise à jour des variables
moy = moyenne_optimisee(f, moy, n)
somme_carres, ec = ecart_type_optimise(f, moy, somme_carres, n)
liste_freq.append(f)
n += 1
.. attention:: Il y a deux subtilités.
1. (*exigible*) Pour qu'une fonction puisse modifier la valeur d'une variable globale,
celle-ci doit explicitement être déclarée globale (première ligne de la fonction, avec le mot clé ``global``),
sinon Python la considèrera comme une variable locale, et la variable globale ne sera pas modifiée.
2. (*bonus*) Lors de la première itération, la moyenne et l'écart type ne sont pas définis
(il n'y a encore eu aucune mesure de faite);
lors de l'itération suivante, l'écart type est nul (il n'y a qu'une seule mesure),
il n'est donc pas possible ou pas souhaitable de faire le test
:math:`f \in [m − 5e, m + 5e]` (en Python ``moy - 5 * ec <= f <= moy + 5 * ec``)
(sinon l'alarme sera toujours déclenchée à la 2 e mesure, sauf si par hasard elle est exactement égale à la première).
On a choisi ci-dessus de faire une dizaine d'itérations sans faire le test,
afin d'avoir une initialisation convenable de la moyenne et de l'écart type,
avant de commencer à faire les tests de déclenchement de l'alarme
(*non exigible* dans les copies, mais un *bonus* sera accordé à ceux qui ont vu la difficulté).
"""
pass
[docs]def analyse():
r""" Implémentation décrite plus haut (:py:func:`IV_Q8`).
- Complexité en temps : :math:`\mathcal{O}(N_{\max}^2 n_{\max})`, avec :math:`N_{\max}` la plus grande taille d'échantillonage reçu au cours des itérations (e.g., ils peuvent être tous de même taille ``N = 1000``), et :math:`n_{\max}` le nombre d'itérations avant que l'alarme se déclenche (potentiellement infini !).
- Complexité en mémoire : :math:`\mathcal{O}(N_{\max}) + \mathcal{O}(1) + \mathcal{O}(\log_2(n_{\max})`, car il faut stocker les échantillonages, les constantes, et l'entier ``n`` (qui prendra une taille logarithmique en sa valeur la plus grande à la fin).
"""
global alarme
liste_freq = []
n = 0
moy = somme_carres = ec = 0.0
while not alarme:
# Mesure et calcul d'une nouvelle fréquence
Ue, Te = acquisition()
Uf = filtrage(Ue, Te)
f = frequence(Uf, Te)
# Test de déclenchement de l'alarme
if n > 10 and abs(f-moy) > 5*ec:
alarme = True
# Mise à jour des variables
moy = moyenne_optimisee(f, moy, n)
somme_carres, ec = ecart_type_optimise(f, moy, somme_carres, n)
liste_freq.append(f)
n += 1
# %% Partie V : Transformation de Fourier rapide
print("\n\nPartie V : Transformation de Fourier rapide")
[docs]def V_Q9():
r""" Réponse à la question **V.9)** (1 pt).
Soit :math:`k \in \{ 0, \dots, P - 1 \}`. On a visiblement :
.. math:: T(a)(k) = T(b)(k) + \mathrm{e}^{i \pi k / P} T(c)(k)
Ainsi que
.. math::
T(a)(k + P) &= T(b)(k + P) + \mathrm{e}^{i \pi (k + P) / P} T(c)(k + P) \\
&= T(b)(k) - \mathrm{e}^{i \pi k / P} T(c)(k)
Car par constructions les deux suites :math:`T(b)` et :math:`T(a)` sont :math:`P-` périodiques.
"""
pass
[docs]def V_Q10():
r""" Réponse à la question **V.10)** (3 pts).
- On prend pour cas de base le cas où la liste :math:`a` est de longueur :math:`N = 1` : on a alors :math:`T(a)(0) = a_0`.
- Cela donne le code suivant :
.. code-block:: python
def TFR(a):
N = len(a)
P = N // 2
if N == 1:
return a
b = a[0:N:2] # Extraction des termes de 2 en 2 à partir de 0
c = a[1:N:2] # Extraction des termes de 2 en 2 à partir de 1
Tb = TFR(b)
Tc = TFR(c)
Ta = [0.0] * N
for k in range(P):
z = np.exp(1j * np.pi * k / P) * Tc[k]
Ta[k] = Tb[k] + z
Ta[k+P] = Tb[k] - z
return Ta
"""
pass
[docs]def TFR(a):
r""" Implémentation assez naïve de la transformée de Fourier discrète rapide, en suivant les indications détaillées et les notations de l'énoncé.
- Complexité en temps : analysée plus bas.
- Complexité en mémoire : :math:`\mathcal{O}(N)`.
"""
N = len(a)
P = N // 2
if N == 1:
return a
b = a[0:N:2] # Extraction des termes de 2 en 2 à partir de 0
c = a[1:N:2] # Extraction des termes de 2 en 2 à partir de 1
Tb = TFR(b)
Tc = TFR(c)
Ta = [0.0] * N
for k in range(P):
z = np.exp(1j * np.pi * k / P) * Tc[k]
Ta[k+0] = Tb[k] + z
Ta[k+P] = Tb[k] - z
return Ta
[docs]def V_Q11_a():
r""" Réponse à la question **V.11.a)** (0.5 pt).
Le coût du calcul de :math:`T(a)` s'obtient en *additionnant* le coût du calcul de :math:`T(b)` et :math:`T(c)`,
à savoir :math:`2C(i-1)`, et les coûts auxiliaires : l'extraction de :math:`b` et :math:`c`,
et la boule ``for k in range(P)``, de l'ordre de :math:`2^i`.
On a donc bien :math:`C(i) = 2 C(i - 1) + \mathcal{O}(2^i), \;\; \forall i \in \mathcal{O}(2^i)`.
"""
pass
[docs]def V_Q11_b():
r""" Réponse à la question **V.11.b)** (1 pt).
En appliquant répétitivement l'inéquation de récurrence, et en précisant ce que ce :math:`\mathcal{O}(2^i)` signifie, il vient :
.. math::
C(i) &\leq 2 C(i - 1) + A \cdot 2^i \\
&\leq 4 C(i - 2) + 2 A \cdot 2^{i-1} + A \cdot 2^{i} = 4 C(i-2) + 2 A \cdot 2^i \\
&\leq 8 C(i - 3) + 4 A \cdot 2^{i-2} + 2 A \cdot 2^{i} = 2^3 C(i-3) + 3 A \cdot 2^i \\
& \dots \\
&\leq 2^i C(0) + i A \cdot 2^i = \mathcal{O}(i 2^i).
.. tip:: Ce genre ce calcul est assez classique, entraînez-vous bien !
Sachant que :math:`i = \log_2(N) = \ln(N) / \ln(2)`, la complexité de l'algorithme TFR (Transformée de Fourier rapide) est donc bien en :math:`\mathcal{O}(N \ln N)`.
C'est **bien meilleur** que l'algorithme quadratique (i.e., en :math:`\mathcal{O}(n^2)`) de la `question 5 <#III_Q5>`_, et la fonction :py:func:`TFR` sera en pratique bien plus rapide que la fonction :py:func:`fourier` (ou :py:func:`fourier2`).
.. note::
- Beaucoup considèrent que l'invention de cet algorithme de la transformée de Fourier rapide (TFR, *FFT* en anglais) est une des plus inventions informatiques les plus géniales du XXème siècle,
- Pour plus de détails sur l'utilisation de la FFT (dans des domaines très variés, mais notamment en télé-communication), veuillez lire `cette page <https://fr.wikipedia.org/wiki/Transformation_de_Fourier_rapide#overview>`_.
.. note::
- Pour information, l'article de recherche original (par James W. Cooley et John W. Tukey) qui a introduit la FFT en 1965 est un des articles d'algorithmique *les plus cités de tout les temps*, voir `par exemple cette page <https://scholar.google.com/scholar?cluster=13287177530111192423&hl=fr&as_sdt=0,39>`_, avec plus de 11000 citations (11319 le 17-02-16).
- En comparaison, un bon article récupère de l'ordre de 15 citations par an, soit environ 800 s'il a été écrit dans les années 60...
- Voir `cet article <http://citeseer.ist.psu.edu/stats/articles>`_ qui montre que les articles ou livres les cités en informatique dépasse très rarement 10000 citations.
"""
pass
# %% Partie VI : Stockage et exploitation des résultats
print("\n\nPartie VI : Stockage et exploitation des resultats")
[docs]def VI_Q12():
r""" Réponse à la question **VI.12)** (2 pts).
- La requête SQL n'était pas trop dure, on la montre simplement ici.
- Pour plus de détails sur ces notions, si vous vous sentez encore largués, relisez la feuille de cours et d'exercice fournie par Mr Basson.
- Et n'hésitez pas à poser des questions !
.. code-block:: SQL
SELECT
capteurs.num, localisation, COUNT(*), MAX(depl)
FROM
capteurs JOIN mesures
ON capteurs.num = mesures.num
GROUP BY
capteurs.num
HAVING
COUNT(*) >= 50
.. attention:: Il ne faut pas confondre ici ``HAVING`` et ``WHERE`` (il fallait utiliser ``HAVING``).
"""
pass
# Déjà importé plus haut.
# import matplotlib.pyplot as plt
[docs]def traitement_requete(requete):
r""" Fausse fonction qui traiterait une requête SQL, donnée sous forme de chaîne de caractères.
"""
print("traitement_requete appele avec :", requete)
raise ValueError("traitement_requete(...): Non implementee !")
[docs]def VI_Q13():
r""" Réponse à la question **VI.13)** (2.5 pts).
- Bien faire attention ici à construire la requête dans le programme Python sous forme d'une chaîne de caractères, en convertissant les valeurs numériques en chaînes de caractères.
.. attention::
- L'approche consistant à faire une première requête pour les dates et une deuxième pour les déplacements n'est pas correcte, car rien ne garantit que les résultats des deux requêtes seront ordonnés de façon cohérente (l'ordre des résultats est imprévisible en SQL, à moins de l'imposer avec une clause ``ORDER BY``).
- Il est donc impératif de récupérer toutes les données en effectuant une seule requête.
"""
pass
[docs]def evol_fissure(num, t1, t2):
r""" Récupère les donneés (par une requête SQL), et les affiche via ``plt.plot`` (``plt`` étant la bibliothèque ``matplotlib.pyplot`` importées au préalable).
- On ne sanctionnait pas l'oubli d'importer ``import matplotlib.pyplot as plt``, mais c'est mieux d'y penser !
Si la base de données était disponible et si toutes les fonctions précédentes sont bien implémentées, alors on devrait être capable de produire un graphique de ce genre :
.. image:: DS2_figure_3.png
:width: 125%
**(Fin de la correction)**
"""
requete = "SELECT time, depl FROM mesures WHERE num = " + str(num)
requete += " AND time BETWEEN " + str(t1)
requete += " AND " + str(t2)
resultat = traitement_requete(requete) # C'est un tableau 2D
time = [ligne[0] for ligne in resultat] # Extraction de la colonne 0
depl = [ligne[1] for ligne in resultat] # Extraction de la colonne 1
plt.figure()
plt.plot(time, depl)
plt.show()
# %% Fin de la correction.
if __name__ == '__main__':
from doctest import testmod
print("\nTest automatique de toutes les doctests écrites dans la documentation (docstring) de chaque fonction :")
testmod(verbose=True)
testmod()
print("\nPlus de détails sur ces doctests sont dans la documentation de Python:\nhttps://docs.python.org/3/library/doctest.html (en anglais)")
# Fin de DS2_info.py