Corrigé CCMP 2020

Partie SQL

Q1. Proposez une requête SQL permettant de compter le nombre de maillages que contient le modèle du bateau.

SQL

SELECT COUNT(*) AS nombre_de_maillages
FROM maillages_bateau;

Q2. Proposez une requête SQL permettant de récupérer la liste des numéros des facettes (numero) du maillage nommé « gouvernail ».

SQL

SELECT f.numero
FROM faces AS f
JOIN maillages_bateau AS m
ON f.maillage = m.id
WHERE m.nom = 'gouvernail';

Q3. Expliquez ce que renvoie la requête SQL suivante :

SQL

SELECT (MAX(x) - MIN(x))
FROM sommets AS s
JOIN faces AS f
JOIN maillages_bateau AS m
ON (s.id = f.s1 OR s.id = f.s2 OR s.id = f.s3) AND f.maillage = m.id
WHERE m.nom = "coque";

Cette requête calcule l'écart maximal (étendue) entre les abscisses \(x\) des sommets qui composent les facettes appartenant au maillage nommé « coque ».

Q4 – À partir de la variable maillage_tetra, écrire une expression Python permettant de récupérer la coordonnée y du premier sommet de la première facette.

Pour récupérer la coordonnée \(y\) du premier sommet de la première facette :

Python

maillage_tetra[0][0][1]

Cette expression accède à la première facette (maillage_tetra[0]), puis au premier sommet de cette facette ([0]), et enfin à la coordonnée \(y\) de ce sommet ([1]).

Q5 – À quel élément, sur la figure 2(a), correspond maillage_tetra[1] ?

maillage_tetra[1] correspond à la facette définie par les trois sommets suivants :

Text Only

-  [0., 0., 0.]  (point A)
-  [0., 1., 0.]  (point D)
-  [1., 0., 0.]  (point B)

Cette facette représente le triangle formé par les sommets A, B et D sur la figure 2(a). C'est à dire la face \(S_4\)

Q6 – On souhaite utiliser les fonctions de ce module depuis un autre fichier Python. Complétez le code ci-dessous afin qu’il fournisse le résultat attendu :

Pour importer la fonction prod_scalaire, le nom du module qui la précise est nécéssaire. as permet l'abréviation (renommage).

voici la syntaxe: from operations_vectorielles import prod_scalaire as ps

Q7 – Que fait la fonction mystere1 ?

La fonction mystere1 calcule le produit scalaire V.V. Elle renvoie donc la norme de V.

Q8 – Créer la fonction multiplie_scalaire, prenant comme argument un flottant a et un vecteur V et renvoyant un nouveau vecteur correspondant à a \(\vec{V}\) .

Il faut multiplier chacune des coordonnées par le scalaire.

Python

def multiplie_scalaire (a , V ):
    return [ a * V [0] , a * V [1] , a * V [2]]

Q9 – Compléter les lignes 4 et 5 permettant de calculer le barycentre.

Voici la fonction complétée

Python

def barycentre ( F ):
    G = [0 ,0 ,0]
    for i in range (3): #Pour chaque point de F
        point = F[i]
        G = [ G[i] + point[i] / 3 for i in range(3)] # Chaque point de la face compte pour 1/3 dans le calcul du barycentre.
    return G

Il est aussi possible d'utiliser les fonctions du module operations_vectorielles pour trouver les coordonnées du barycentre.

Q10 – Pour une facette F=(A,B,C) d’aire non-nulle, proposer une fonction normale, prenant comme argument une facette F et renvoyant le vecteur unitaire normal

Python

def normale(F):
    A, B, C = F # designent les points A,B,C et les vecteurs OA,OB,OC
    AB = soustraction(B,A)
    AC = soustraction(C,A)
    pv = prod_vectoriel(AB,AC)
    return multiplie_scalaire((sum([c** 2 for c in pv])**0.5,pv)

Q11 – Compte tenu de la représentation limitée des nombres réels en machine, deux sommets S1 et S2 supposés être au même endroit peuvent avoir des coordonnées légèrement di↵érentes. Proposer une fonction sont_proches, prenant comme arguments deux sommets S1 et S2 (représentés par leur vecteur position) et un flottant positif eps, et qui renvoie True si S1 et S2 sont proches (i.e. si leur distance au sens de la norme Euclidienne est inférieure à eps) et False sinon.

En utiliasant la fonction mystere1 :

Python

def sont_proches ( S1 , S2 , eps ):
    return mystere1 ( soustraction ( S1 , S2 )) <= eps

Q12 – Sous quelle condition la fonction mystere2 renvoie-t-elle True ?

La fonction mystere2 teste la distance du sommet S1 à tous les sommets de la liste L.

Elle retourne Truedès que l'un des sommets est proche (à \(10^{-7}\) près) de S1. Elle retourne False sinon.

Q13 – Donner (sans justification) ce que renvoie mystere3(maillage_tetra), dans le cas où maillage_tetra est la variable définie précédemment.

Elle retourne : [[0.0, 0.0, 0.0], [0.0, 0.0, 1.0], [0.0, 1.0, 0.0], [1.0, 0.0, 0.0]]

Q14 – Pour une liste L de longueur n, discuter la complexité de la fonction mystere2. En déduire la complexité de mystere3, pour un maillage contenant m facettes triangulaires. On distinguera le meilleur et le pire des cas.

• La complexité est proportionnelle au nombre de passages dans la boucle.
• Chaque itération de la boucle s'effectue en \(\mathcal{O}(1)\) (complexité constante pour la fonction sont_proches). Le reste du traitement est négligeable.

Meilleur cas :

• Si S1 est proche du premier élément de L, il n'y a qu'un seul passage dans la boucle.
• Complexité : \(\mathcal{O}(1)\).

Pire cas :

• Si S1 n'est proche d'aucun élément de L ou seulement du dernier élément de L, on parcourt la liste entière.
• Complexité : \(\mathcal{O}(n)\).

Complexité de mystere3 (pour un maillage contenant m facettes triangulaires)

Meilleur cas :

• Tous les sommets sont identiques.
• Le test de la ligne 12 s'effectue toujours en \(\mathcal{O}(1)\). Ce test est répété \(3m\) fois (3 sommets par facette).
• La ligne 13 n'est exécutée qu'une seule fois lors du premier passage dans les boucles.
• Complexité : \(\mathcal{O}(m)\).

Pire cas :

• Aucun sommet n'est proche d'un autre.
• La liste res croît à chaque itération, et la complexité de chaque itération dépend de mystere2 (pire cas : \(\mathcal{O}(n)\) où \(n\) est la longueur de res).
• Il y a \(3m\) itérations au total.
• Complexité : \(\mathcal{O}(m^2)\).

Calcul du pire cas :

Complexité = \(sum_{k=1}^{3m} k\) = \({3m(3m + 1)}/{2}\) \(\mathcal{O}(m^2)\)

Quel est l’espace occupé en mémoire vive par l’ensemble des données (en Mo).

Formule de calcul

Mémoire = (350 × 200 × 200 × 64) / (8 × 1024²) ≈ 107 Mo

Q16 – Écrire une fonction mat2str qui prend en argument une liste de listes (représentant un mat_h) et renvoie les données qu’elle contient sous forme d’une chaı̂ne de caractères qui respecte le format suivant :

Python

def mat2str(mat_h):
    ch = ""
    for i in range(len(mat_h)): # Parcours des lignes
        for j in range(len(mat_h[i])): # Parcours des colonnes
            ch += str(mat_h[i][j]) # conversion au format str de hij et concaténation à ch
            if j != len(mat_h[i]) - 1: # si avant fin de ligne
                ch += "; " # ajout ;
            else:
                ch += "\n" # sinon ajout retour à la ligne
    return ch

Q17 – En s’appuyant sur mat2str, proposer un code Python qui permet de sauvegarder le contenu de liste_vagues dans un fichier nommé fichier_vagues.txt (dans le répertoire courant), en séparant la représentation de chaque mat_h par deux sauts de lignes consécutifs.

Python

fichier = open("fichiers_vagues.txt", "w")
for mat_h in liste_vagues:
    fichier.write(mat2str(mat_h))
    fichier.write("\n\n") # Deux lignes séparent chaque mat_h
fichier.close()

Q18 – Après avoir défini judicieusement les types des éléments contenus dans I, J puis N, estimer la taille (en octets) que prendra une matrice ayant p éléments non-nuls, au format « Coordinate Format », dans le fichier.

• Les éléments de I et J sont des entiers, ceux de N sont des flottants.
• Hypothèse : les entiers entre 0 et 199 sont codés en moyenne sur 2,45 caractères : (10 x 1 + 90 x 2 + 100 x 3) / 200

Calcul du nombre de caractères :

• Pour I et J : 3.45p (avec les séparateurs et retours à la ligne).
• Pour N : 16p.
• total : 22.90p

Taille en octets (ASCII) :

22.90p

Q19 – En déduire à partir de combien d’éléments non-nuls il devient moins avantageux d’enregistrer une matrice creuse qu’une matrice complète classique.

La matrice classique occupe 320000 octets ( \(200^2\) x 8 octets) La matrice creuse occupe 22.90p

Ainsi dès que p est supérieur à 13973, la matrice creuse n'est plus avantageuse.

Cela corrspond à environ 35 % de la matrice (200 x 200).

Q20 – Proposer un code permettant de construire, pour un tableau mat_h donné, les listes Python I,J et N. On considérera nulles les hauteurs inférieures à \(10^{-3}\) (en valeur absolue).

Python

I, J, N = [], [], []
for i in range(len(mat_h)):
    for j in range(len(mat_h[i])):
        if abs(mat_h[i][j]) > 1e-3:
            I.append(i)
            J.append(j)
            N.append(mat_h[i][j])

Q21 – Proposer une fonction lister_FI prenant comme argument un maillage M et renvoyant la liste des facettes immergées (i.e dont le centre de gravité est sous la surface définie par hauteur). On pourra utiliser les fonctions de la partie I.

Python

def lister_FI(M):
    L = []
    for facette in M:
        x, y, z = barycentre(facette)
        if z < hauteur(x, y):
            L.append(facette)
    return L

Q22 – Proposer une fonction force_facette prenant en argument une facette F, et renvoyant le vecteur force appliqué par l’eau sur cette facette. On pourra utiliser les fonctions définies précédemment.

Python

def force_facette(F):
    rho, g = 1000, 9.81
    S = aire(F)
    n = normale(F)
    x, y, z = barycentre(F)
    p = rho * g * (hauteur(x, y) - z)
    return multiplie_scalaire(-S * p, n)

Q23 – Définir la fonction resultante prenant comme argument une liste L de facettes (supposées immergées), renvoyant la somme des forces sur l’axe ! \(\vec{z}\) de l’eau, appliquée sur l’ensemble des surfaces.

Python

def resultante(L):
    res = 0.0
    for F in L:
        res += force_facette(F)[2] # le 3ème elt de force_facette(F) est selon l'axe z
    return res

Q24 – Compléter la fonction fusion, prenant comme argument deux listes de facettes L1 et L2 (supposée chacune triée par aire décroissante) et renvoyant une nouvelle liste composée des facettes de L1 et L2 triées par aire décroissante.

Python

def fusion(L1, L2):
    L = []
    while len(L1) != 0 and len(L2) != 0:
        if aire(L1[0]) > aire(L2[0]):
            L.append(L1.pop(0))
        else:
            L.append(L2.pop(0))

    L += L1 + L2 # pour concaténer le reste de la liste non vide
    return L

Q25 – Compléter la fonction récursive trier_facettes, prenant comme argument une liste de facettes L, et renvoyant une nouvelle liste de facettes triées dans l’ordre des aires décroissantes, par la méthode du tri-fusion.

La fonction trier_facettes est une implémentation récursive de l’algorithme de tri fusion (“mélange”). Voici le code avec des explications :

Python

def trier_facettes(L):
    if len(L) <= 1:
        return L
    else:
        m = len(L) // 2
        L1 = trier_facettes(L[:m])  # Tri de la première moitié
        L2 = trier_facettes(L[m:])  # Tri de la deuxième moitié
        return fusion(L1, L2)  # Fusion des deux listes triées

Cet algorithme divise la liste en deux parties jusqu'à ce qu’elles contiennent un seul élément, puis les fusionne en respectant l’ordre croissant. La fonction fusion est supposée être prédéfinie.

Q26 – A↵ecter à une nouvelle variable grandesFacettes la liste des facettes de maillageG, privée de la moitié des facettes les plus petites (en cas de nombre impair d’éléments, on inclura la facette médiane).

Pour obtenir les grandes facettes à partir du maillage maillageG, on suppose que les facettes sont triées par ordre décroissant selon leur taille. Le code suivant permet d'extraire les plus grandes facettes :

Python

grandesFacettes = trier_facettes(maillageG)[:(len(maillageG) + 1) // 2]

Ce code divise par deux la liste triée des facettes (en prenant la moitié supérieure).

Q27 – Compléter les lignes 4 et 5 du code précédent conformément à la méthode d’Euler.

Les équations suivantes mettent à jour la position et la vitesse d'un objet soumis à des forces extérieures :

1. Mise à jour de la position en fonction de la vitesse :
   Python

   posG = posG + dt * vitG
   

2. Mise à jour de la vitesse en fonction des forces appliquées :
   Python

   vitG = vitG + dt * (1 / m * resultante(facettes_immergees) - g)
   

Dans ces expressions :

Text Only

- `dt` est le pas de temps.

- `m` est la masse de l'objet.

- `resultante(facettes_immergees)` représente la somme des forces appliquées par les facettes immergées.

- `g` est l'accélération gravitationnelle (vecteur).