DNS Info MP2018

Last updated: May 9th, 20202020-05-09Project preview

Mesures de Houle - Mines Ponts 2018

Simon Landrieux

Stockage interne des données

Q1 Chaque ligne comporte 8 caractères, chacun encodé sur 8 bits, pour un total de 64 bits par ligne, ie 8 octets par mesure. Chaque ligne correspond à une mesure. On réalise 2 mesures par seconde pendant 20 minutes, soit un total de 2 × 60 × 20 = 2400 mesures. La série de mesures pèse donc 19 200 octets.

Q2 On réalise 2 séries de mesures par heures, ie 48 par jours, pendant 15 jours. On réalise ainsi 720 séries de mesures au total. Chacune pesant 19 200 octets, la campagne de mesures représente au total à peu près 13,8 millions d'octets. Cette masse de données représente à peu près 13 Mo, bien moins que la capacité de 1 Go envisagée pour la carte mémoire. Celle-ci est donc suffisante.

Q3 Un chiffre significatif est symbolisé par un caractère sur les 8 que comporte un ligne de donnée. On allègerait donc le poids total de la mesure de 12,5% (=1/8) en retirant l'enregistrement d'un chiffre significatif.

Q4

In [ ]:
fichier = open("donnees.txt", "r")

ligneNumero1 = fichier.readline()

lStr = fichier.readlines()
fichier.close()
#il y a un caractère de retour à la ligne à la fin de chaque élément de lStr, cependant, sa présence n'a pas d'influence sur la lecture de la valeur

liste_niveaux = [str(a) for a in lStr ]

Analyse “vague par vague”

Q5 H1 = 9 m H2 = 9 m H3 = 6 m

T1 = 11 s T2 = 15 s

Q6

In [2]:
def moyenne(L) :
    s = 0
    for h in L :
        s = s + h
    return s/len(L)

#test
L = [1,2,3,4]
print(moyenne(L))
2.5

Q7

In [3]:
def integrale_precise(L) :
    pas = 0.5 #(s) f_mesure = 2 Hz
    p = len(L)
    res = 0
    for i in range(p-1) :
        res= res + (L[i]+L[i+1])/2
    return res*pas

#test
print(integrale_precise(L))
3.75
In [4]:
def moyenne_precise(L) :
    int =  integrale_precise(L)
    T = 20 * 60 #durée en secondes de la série de mesures
    return int/T
#test
print(moyenne_precise(L)) #ne renvoiera pas la bonne valeur, juste pour vérifier la syntaxe
0.003125

Q8

In [5]:
def ind_premier_pzd(L) :
    m = moyenne(L)
    p= len(L)
    cond = L[1]<L[0] and L[0]>m
    i = 0
    while i < (p-2) and not cond :
        i = i+1
        cond = L[i+1]<m and L[i]>m
    if cond :
        return i
    else :
        return -1

#test
Lpzd = [2,2,2,1,0,2,2,2,1,0]
print(ind_premier_pzd(Lpzd))
2

Q9

In [6]:
def ind_dernier_pzd(L) :
    m = moyenne(L)
    p= len(L)
    cond = L[-1]<m and L[-2]>m
    i = p-2
    while i > 0 and not cond :
        i = i-1
        cond = L[i+1]<m and L[i]>m
    if cond :
        return i
    else :
        return -2
#test
print(ind_dernier_pzd(Lpzd))
7

En ce qui concerne la complexité, la question n'est pas très claire. On ne précise par sur quoi la complexité en O(1) porte. On suppose que ça doit être sur le nombre de comparaison par rapport à la taille de la liste. Ainsi, les fonctions "moyenne" ne sont pas prises en compte, et dans le meilleur des cas, on aura toujours le même nombre de comparaisons faites. En effet, si le dernier PZD est l'avant dernier terme, on fera toujours exactement 3 comparaisons.

Q10

In [7]:
def construction_successeurs(liste_niveaux) :
    n=len (liste_niveaux)
    successeurs =[]
    m=moyenne(liste_niveaux)
    for i in range (n-1):
        if liste_niveaux[i+1]<m and liste_niveaux[i]>m :
            successeurs.append(i+1)
    return successeurs

Q11

In [8]:
def decompose_vagues(L) :
    successeurs = construction_successeurs(L)
    res = []
    p = len(successeurs)
    for i in range(p-1) :
        res.append(L[successeurs[i]:successeurs[i+1]])
    return res

#tests
vagues = [1, -1, -2, 2, -2, -1, 6, 4, -2, -5]
print(decompose_vagues(vagues))
[[-1, -2, 2], [-2, -1, 6, 4]]

Q12

In [9]:
def proprietes(L):
    decomposition = decompose_vagues(L)
    p = len(decomposition)
    res = []
    for i in range(p) :
        H = max(decomposition[i]) - min(decomposition[i])
        T = len(decomposition[i]) * 0.5
        res.append([H,T])
    return res

#test
print(proprietes(vagues))
[[4, 1.5], [8, 2.0]]

Contrôle des données

Q13

In [10]:
def Hmax(liste_niveaux) :
    prop = proprietes(liste_niveaux)
    res = prop[0][0]
    for i in range(1,len(prop)):
        if prop[i][0] > res :
            res = prop[i][0]
    return res
#test
print(Hmax(vagues))
8

Q14

Au premier appel, g = 0 et d = len(liste)-1.

In [11]:
def triRapide(liste, g, d) :
    pivot=liste[d][0]
    i = g
    j = d
    while True :
        while i <= d and liste[i][0] < pivot :
            i = i+1
        while j >= g and liste[j][0] > pivot :
            j = j-1
        if i>j :
            break #le mot tabou
        if i<j :
            liste[i],liste[j] = liste[j],liste[i]
        i = i+1
        j = j-1
    if g<j :
        triRapide(liste, g, j)
    if i<d :
        triRapide(liste, i, d)

#tests
propTest = [[4, 1.5], [8, 2.0],[3, 2.0],[10, 2.0]]
triRapide(propTest, 0, len(propTest)-1)
print(propTest)
[[3, 2.0], [4, 1.5], [8, 2.0], [10, 2.0]]

Q15

In [12]:
def triRapideInser(liste, g, d) :
    if d-g +1 <= 15 :
        triInsertion(liste,g,d)
    else :
        pivot=liste[d][0]
        i = g
        j = d
        while True :
            while i <= d and liste[i][0] < pivot :
                i = i+1
            while j >= g and liste[j][0] > pivot :
                j = j-1
            if i>j :
                break #le mot tabou
            if i<j :
                liste[i],liste[j] = liste[j],liste[i]
            i = i+1
            j = j-1
        if g<j :
            triRapide(liste, g, j)
        if i<d :
            triRapide(liste, i, d)

Q16

In [13]:
def triInsertion(liste,g,d) :
    for i in range(g+1, d+1) :
        j = i-1
        tmp = liste[i]
        while j>=0 and liste[j]>tmp :
            liste[j+1]=liste[j]
            j =j-1
        
        
        liste[j+1]=tmp

#test
l=[2,85,4,8,2,8,3,8,2,6,8]
triInsertion(l,0,len(l)-1)
print(l)
[2, 2, 2, 3, 4, 6, 8, 8, 8, 8, 85]

Q17

In [14]:
def skewness(liste_hauteurs):
    n = len(liste_hauteurs)
    et3 = (ecartType(liste_hauteurs))**3
    m = moyenne(liste_hauteurs) #on calcule une seule fois la moyenne de la liste au lieu de n fois
    S = 0
    for i in range(n) :
        S = S + (liste_hauteurs[i]-m)**3
    S = n/(n-1)/(n-2)*S/et3
    return S

Q18

Non, on peut s'attendre à des complexités analogues pour un fonction évaluant S et une évaluant K, car elle nécessite les mêmes opérations : opérations de base, calcul de moyenne, calcul d'écart type et sommation sur l'ensemble des mesures.

Base de données relationnelle

Q19

“Quels sont le numéro d’identification et le nom de site des bouées localisées en Méditerranée ?”
SELECT idBouee, nomSite
FROM Bouee
WHERE localisation = 'Mediterranee'

“Quel est le numéro d’identification des bouées où il n’y a pas eu de tempêtes ?”
SELECT idBouee FROM Bouee
EXCEPT SELECT idBouee FROM Tempete

“Pour chaque site, quelle est la hauteur maximale enregistrée lors d’une tempête ?”
SELECT b.localisation, MAX(t.Hmax)
FROM Bouee as b JOIN Tempete as t ON b.idBouee = t.idBouee
GROUP BY b.localisation

Analyse “spectrale”

Q20

On doit calculer N/2 facteurs Pk et N/2 facteur Ik, et chaque calcul de facteur nécessite la sommation de N/2 facteurs. Le calcul des Pk nécessite ainsi N/2×N/2 = N²/4 calculs "élémentaires". À partir de ceux-ci, N calculs "élémentaires" sont nécessaires pour avoir la transformée de Fourier.
La complexité est donc de O(N²)+O(N) = O(N²)

Si j'ai bien compris, l'intérêt de cet algorithme est que, même s'il a la même complexité que le premier, il est asymptotiquement 2 fois plus rapide que le premier.

Q21

On va scinder la liste en 2 (youpi, c'est une puissance de 2), pairs et impairs, jusqu'à obtenir une liste de 2 termes, on réalise une TFD sur ce duplet, ce qui revient à faire :
(x0,x1) -> (X0 = x0+x1 , X1 = x0-x1)
On "assemble" ensuite les différents morceaux de transformée de Fourier selon la technique décrite.

In [15]:
#on importe ce qui est nécessaire pour les calculs en complexe
j = complex(0,1)
from cmath import exp, pi

def DIT(x) :
    N = len(x)
    if N == 2 :
        X0 = x[0]+x[1]
        X1 = x[0]-x[1]
        return [X0,X1] #TFD à 2 termes
    else : # on fait l'assemblage
        P = DIT(x[::2]) #on prend la TFD des pairs
        I = DIT(x[1::2]) #on prend la TFD des impairs
        X = N*[0] #on crée la liste de la TFD (le résultat)
        w = exp(-2*pi/N*j)
        Wk = 1
        for k in range(int(N/2)) :
            X[k] = P[k] + Wk*I[k]
            X[k+int(N/2)] = P[k] - Wk*I[k]
            Wk = Wk*w
        return X    

On va maintenant tester la fonction avec un signal de transformée de Fourier connue, une superposition de sinus. On utilise numpy pour aller plus vite.

In [16]:
import numpy as np
import matplotlib.pyplot as plt

N = 2**6

t = np.linspace(0,2,N)

s = np.sin(2*2*pi*t) + np.sin(4*2*pi*t)/2 
#on a un signal s qui est composé de la somme de 2 sinus de fr
plt.plot(t,s)
plt.xlabel("temps $t$")
plt.ylabel("amplitude")
plt.show()
In [17]:
X=DIT(s)

Je me suis un peu renseigné pour pouvoir exploiter la transformée de Fourier afin d'obtenir la décomposition en fréquence du signal d'entrée.

In [18]:
fe = N/(t[-1]-t[0]) #on calcule la fréquence d'échantillonnage
freq = np.linspace(0,fe/2,N//2) #on crée l'axe des abscisses en fréquence, qui correspond au domaine permis par le théorème de Shannon
Xpos = np.abs(X[:N//2]) # on sélectionne la partie du résultat qui correspond aux fréquences positives, et on en prend le module
plt.plot(freq,Xpos)

plt.xlabel("fréquence $f$")
plt.ylabel("amplitude")
plt.show()

On reconnaît bien le spectre en fréquence du signal : on retrouve 2 pics au niveau des fréquences des 2 sinus superposés dans le signal d'entrée, et la hauteur des pics est proportionnelle à l'amplitude des composantes.

Notebooks AI
Notebooks AI Profile20060