T.P. n°7 Révisions - corrigé
from time import time
1. Système solaire (d'après Centrale)¶
À partir de mesures régulièrement effectuées par différents observatoires, une base de données des caractéristiques et des états des corps célestes de notre Système solaire est maintenue à jour. L’objectif de cette partie est d’extraire de cette base de données les informations nécessaires à la mise en œuvre des fonctions développées dans les parties précédentes, puis de les utiliser pour prévoir les positions futures des différentes planètes. Les données à extraire sont les masses des corps étudiés et leurs états (position et vitesse) à l’instant 𝑡min du début de la simulation. Une version simplifiée, réduite à deux tables, de la base de données du Système solaire est donnée figure 3. Les masses sont exprimées en kilogrammes, les distances en unités astronomiques (1 au = 1,5×1011 m) et les vitesses en kilomètres par seconde. Le référentiel utilisé pour exprimer les composantes des positions et des vitesses est galiléen, orthonormé et son centre est situé à proximité du Soleil.
La table CORPS
répertorie les corps étudiés, elle contient les colonnes
- id_corps (clé primaire) entier identifiant chaque corps ;
- nom, chaine de caractères, désigne le nom usuel du corps ;
- masse de type flottant, contient la masse du corps.
La table ETAT
rassemble l’historique des états successifs (positions et vitesses) des corps étudiés. Elle est constituée de huit colonnes :
- id_corps de type entier, identifie le corps concerné ;
- datem est la date de la mesure, sous forme d’un entier donnant le nombre de secondes écoulées depuis un instant d’origine ;
- trois colonnes de type flottant pour les composantes de la position x, y et z ;
- trois colonnes de type flottant pour les composantes de la vitesse vx, vy, vz.
Question
Écrire une requête SQL qui renvoie la liste des masses de tous les corps étudiés.
Réponse
SELECT masse FROM CORPS;
Les états des différents corps ne sont pas forcément tous déterminés exactement au même instant. Nous allons assimiler l’état initial (à la date $t_{min}$) de chaque corps à son dernier état connu antérieur à $t_{min}$. Dans toute la suite, on supposera que la valeur de $t_{min}$, sous le format utilisé dans la table ETAT
, est accessible à toute requête SQL via l’expression tmin()
.
On souhaite d’abord vérifier que tous les corps étudiés disposent d’un état connu antérieur à $t_{min}$.
Question
Écrire une requête SQL qui renvoie le nombre de corps présents dans la base.
Réponse
SELECT COUNT(id_corps) FROM CORPS
Question
Écrire une requête SQL qui renvoie le nombre de corps qui ont au moins un état connu antérieur à $t_{min}$.
Réponse
SELECT COUNT(id_corps) FROM ETAT
WHERE datem < tmin();
Question
Écrire une requête SQL qui renvoie, pour chaque corps, son identifiant et la date de son dernier état antérieur à $t_{min}$.
Réponse
SELECT id_corps, MAX(datem) FROM etat
WHERE datem < tmin()
GROUP BY id_corps
Le résultat de la requête précédente est stocké dans une nouvelle table date_mesure
à deux attributs :
- id_corps de type entier, contient l’identifiant du corps considéré ;
- date_der de type entier, correspond à la date du dernier état connu du corps considéré, antérieur à $t_{min}$.
Pour simplifier la simulation, on décide de négliger l’influence des corps ayant une masse strictement inférieure à une valeur fixée masse_min()
et de ne s’intéresser qu’aux corps situés dans un cube, centré sur l’origine du référentiel de référence et d’arête arete()
donnée. Les faces de ce cube sont parallèles aux plans formés par les axes du référentiel de référence.
Question
Écrire une requête SQL qui renvoie la masse et l’état initial (sous la formemasse, x, y, z, vx, vy, vz
) de chaque corps retenu pour participer à la simulation. Classez les corps dans l’ordre croissant par rapport à leur distance à l’origine du référentiel.
Réponse
SELECT masse,x,y,z,vx,vy,vz FROM corps AS c
JOIN etat AS e
ON c.id_corps = e.id_corps
JOIN date_mesure AS d
ON (datem = date_der AND e.id_corps = d.id_corps)
WHERE
masse >= masse_min()
AND ABS(x) < arete()/2
AND ABS(y) < arete()/2
AND ABS(z) < arete()/2
ORDER BY x*x+y*y+z*z
2. Polynôme et dictionnaire¶
On considère un polynôme $P=\sum_{k=0}^n a_k X^k$ représenté par un dictionnaire p
tel que, pour tout entier naturel $k \leqslant n$, si $\alpha_k \neq 0$ alors p[k]
vaut
$\alpha_k$ (on ne stocke pas les coefficients nuls de $P$).
Dit autrement, p[k]
contient le coefficient de degré $k$ de $P$ .
Question
Définir les dictionnairesp1
,p2
, etp3
représentant les polynômes :
- $P_1=7 + 3X^2 - X^5$,
- $P_2=-7 - 3X^2 + X^5$,
- $P_3=-7 + 21X +5X^3 + 7X^4$.
p1 = {0 : 7, 2 : 3, 5 : -1}
p2= {0 : -7, 2 : -3, 5 : 1}
p3= {0:-7,1 : 21, 3 : 5, 4 : 7}
Question
Écrire une fonctiondegre(p)
renvoyant le degré d’un polynôme.
def degre(p):
maxi = 0
for k in p:
if k > maxi:
maxi = k
return maxi
def degre2(p):
return max(p.keys())
degre(p1)
5
Question
Écrire une fonctionderive(p)
qui renvoie la dérivée $P'$ d’un polynôme $P$.
def derive(p):
dp = {}
for k in p:
# le terme constant disparaît
if k != 0:
dp[k - 1] = k*p[k]
return dp
p1,derive(p1)
({0: 7, 2: 3, 5: -1}, {1: 6, 4: -5})
Question
Définir une fonctionsomme(p, q)
renvoyant un dictionnaire représentant la somme des deux polynômesp
etq
.
Quelle est sa complexité ?
On propose ici une version de la fonction utilisant la méthode del
pour supprimer les 0 du dictionnaire. On pourrait aussi coder une fonction évitant d'ajouter ces valeurs au cours de la construction.
def somme2(p, q):
r = p.copy()
for kq in q:
if kq in r:
r[kq] += q[kq]
else:
r[kq] =q[kq]
for kr in r.copy():
if r[kr]==0:
del r[kr]
return r
somme(p1,p1),somme(p1,p2),somme(p1,p3)
(None, None, None)
Réponse
La complexité de la fonction précédente est en $\mathcal{O}(n_1 + n_2 )$ (en considérant que les opération de dictionnaire sont de coût constant, ce qui est normalement le cas en coût amorti).
Question
Faire de même avec une fonctionproduit(p, q).
Chaque terme $a_i X^i$ de P multiplié avec un terme $b_j X^j$ de $Q$ va donner un terme $a_i b_j X^{i+j}$ dans le produit.
La complexité est clairement en $\mathcal{O}\left(n_1 \times n_2 \right)$. On enlève les termes nuls a posteriori comme à la question précédente.
def produit(p, q):
r = {}
for i in p:
for j in q:
if i + j in r:
r[i + j] += p[i]*q[j]
else:
r[i + j] = p[i]*q[j]
for kr in r.copy():
if r[kr]==0:
del r[kr]
return r
produit(p1,p1),produit(p1,p2),produit(p1,p3)
({0: 49, 2: 42, 5: -14, 4: 9, 7: -6, 10: 1}, {0: -49, 2: -42, 5: 14, 4: -9, 7: 6, 10: -1}, {0: -49, 1: 147, 3: 98, 4: 49, 2: -21, 5: 22, 8: -5, 9: -7})
Question
Écrire une fonctionevalue(x, p)
renvoyant $P(x)$ dont la complexité est en $\mathcal{O}\left(\text{deg}(P)\right)$.
On rappelle que le calcul de $x^n$ demande $\mathcal{O}(\log(n))$ multiplications avec l’algorithme d’exponentiation rapide.
Pour avoir une complexité $\mathcal{O}(n)$, on peut utiliser la méthode de Horner.
Une autre possibilité est de calculer et stocker toutes les puissances, pour éviter de les recalculer en totalité.
def evalue(x, p):
n = degre(p)
puissances = [1]
for i in range(n):
puissances.append(puissances[-1]*x)
res = 0
for k in p:
res += p[k]*puissances[k]
return res
evalue(3,p1)
-209