Corrigé CCMP 2020

Sujet CCMP IPT 2020

Partie SQL⚓

Q1. Proposez une requĂȘte SQL permettant de compter le nombre de maillages que contient le modĂšle du bateau.

SQL
1
2
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
1
2
3
4
5
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
1
2
3
4
5
6
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
1
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
1
2
3
-  [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
1
2
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
1
2
3
4
5
6
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
1
2
3
4
5
6
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
1
2
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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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
1
2
3
4
5
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
1
2
3
4
5
6
7
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
1
2
3
4
5
6
7
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
1
2
3
4
5
6
7
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
1
2
3
4
5
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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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
1
2
3
4
5
6
7
8
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
1
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
    1
    posG = posG + dt * vitG
  2. Mise à jour de la vitesse en fonction des forces appliquées :
    Python
    1
    vitG = vitG + dt * (1 / m * resultante(facettes_immergees) - g)

Dans ces expressions :

Text Only
1
2
3
4
5
6
7
- `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).