info-nf

Exercice

Q1

def divStrict(x):
    for d in range(1, x):
        if x % d == 0:
            print(d)

Q2

La boucle fait $x-1$ itérations, la condition du if ainsi que le print étant $O(1)$ donc la complexité de divStrict(x) est $O(x)$

Q3

def somDivStrict(x):
    S = 0
    for d in range(1, x):
        if x % d == 0:
            S += d
    return S

Q4

def amis(x, y):
    return x == somDivStrict(y) and y == somDivStrict(x)

Q5

def liste_amis(n):
    L = []
    for i in range(1, n+1):
        for j in range(i, n+1):
            if amis(i, j):
                L.append((i,j))
    return L

Q6

Soit $C(n)$ la complexité de liste_amis(n).
La fonction amis(x, y) fait appel a somDivStrict deux fois,
donc sa complexité est $O(x+y)$

Donc $$ \begin{split} C(n) &= \sum_{i=1}^n \sum_{j=1}^n O(i+j) \\ &= \sum_{i=1}^n O(n\times i + n\times(n+1)/2) \\ &= O(n^2\times(n+1)/2 + n^2\times(n+1)/2) \\ &= O(n^3) \\ \end{split} $$

Partie 1: SQL

Q1

INSERT INTO Personnes
VALUES (123, 'GUISSI', 'MARYAM', 'F'),
       (138, 'FORA', 'AHMED', 'M')

Q2

$$ \pi_{code, nom, prénom}(\sigma_{codeC=394}(Personnes \underset{code = codeP}{\bowtie} Votes))$$

Q3

SELECT Personnes.code, Personnes.nom, Personnes.prénom
FROM Personnes
INNER JOIN Votes ON Personnes.code = Votes.codP
WHERE Votes.codC = 394
ORDER BY Personnes.code ASC

Q4

SELECT P.code, P.nom, P.prénom, P.genre
FROM Personnes AS P
INNER JOIN Votes ON P.code = Votes.codC
WHERE nom LIKE "_A___%"
ORDER BY nom, prénom ASC

Q5

SELECT P.code, P.nom, P.prénom
FROM Personnes AS P
WHERE genre = 'M'
AND P.code NOT IN (SELECT codP FROM Votes)

Q6

SELECT P.code, P.nom, P.prénom, P.genre
FROM Personnes AS P
INNER JOIN (
    SELECT codC, COUNT(*) AS compte
    FROM Votes
    GROUP BY codC
) AS V
ON P.code = V.codC
WHERE V.compte > (SELECT COUNT(*) / 2 FROM Votes);

Q7

SELECT MAX(compte), MIN(compte), AVG(compte)
FROM (
    SELECT COUNT(*) AS compte
    FROM Votes
    GROUP BY codC
) AS V

Partie 2 : Calcul numérique

Q1

def decoupe(P):
    X = []
    Y = []
    for p in P:
        X.append(p[0])
        Y.append(p[1])
    return X, Y

Q2

def matrice(X):
    n = len(X)
    M = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(i+1):
            n_j = 1
            for k in range(j):
                n_j *= (X[i] - X[k])
            M[i][j] = n_j
    return M

Q3

def solution(M, Y):
    n = len(Y)
    A = [0 for _ in range(n)]
    for i in range(n):
        S = 0
        for j in range(i):
            S += M[i][j] * A[j]
        A[i] = 1/M[i][i] * Y[i] - S

Q4

def valeur(x, A, X):
    n = len(X)
    S = 0
    for i in range(n):
        P = 1
        for j in range(i):
            P *= (x-X[j])
        S += A[i] * P
    return S

Q5

import numpy as np
import matplotlib.pyplot as plt

def courbe(P):
    n = len(P)
    X, Y = decoupe(P)
    A = solution(matrice(X), Y)

    t = np.linspace(min(X), max(X), 500)
    images = [valeur(x, A, X) for x in t]

    plt.plot(t, images, color="black")
    plt.scatter(X, Y)
    plt.show()

Partie 3 : Problème

Q1

def NON(X):
    Z = ""
    for x in X:
        if x == "":
            Z += "1"
        else :
            Z += "0"
    return Z

Q2

def ET(X, Y):
    n = len(X)
    Z = ""
    for i in range(n):
        if X[i] == "1" and Y[i] == "1":
            Z += "1"
        else:
            Z += "0"
    return Z

Q3

def XOR(X, Y):
    n = len(X)
    Z = ""
    for i in range(n):
        if X[i] == Y[i]:
            Z += "1"
        else :
            Z += "0"
    return Z

Q4

def decal_droite(X, p):
    return "0" * p + X[:-p]

Q5

def rotation_droite(X, p):
    return X[:p] + X[:-p]

Q6

def addition(X, Y):
    n = len(X)
    c = 0
    Z = ""
    for i in range(n):
        if X[i] + Y[i] + c == 0:
            Z += "0"
            c = 0
        elif X[i] + Y[i] + c == 1:
            Z += "1"
            c = 0
        elif X[i] + Y[i] + c == 2:
            Z += "0"
            c = 1
        else :
            Z += "1"
            c = 0
    return Z

Q7

def bin_fract(x, n):
    s = ""
    x = x**(1/n)
    x -= int(x)
    for i in range(32):
        x *= 2
        s += str(int(x))
        x -= int(x)
    return s

Q8

def liste_init(t, n):
    return [bin_fract(L[i], n) for i in range(t)]

Q9

l’énonce semble comporter une erreur; on parle de 8 variables, de h0 a h7, pas de variable h8

h0, h1, h2, h3, h4, h5, h6, h7 = liste_init(8, 2)
K = liste_init(64, 3)

Q10

def binaire(x, t):
    s = ""
    for i in range(t):
        s = str(x % 2) + s
        x //= 2
    return s

Q11

def binaire_txt(T):
    s = ""
    for x in T:
        s += binaire(x, 8)
    return s

Q12

def remplissage(B):
    n = len(B)
    B += '1'
    B += '0' * ((448 - len(B)) % 512)
    B += binaire(n, 64)
    return B

Q13

def decoupe(B):
    n = len(B)
    W = []
    for x in range(len(B)//512):
        w = [B[32*k:32*k+32] for k in range(16)]
        W.append(w)
    return W

Q14

def compression(W):
    global h0, h1, h2, h3, h4, h5, h6, h7
    for w in W:
        w += ['0'*32 for _ in range(48)]
        for i in range(16, 64):
            S0 = XOR(rotation_droite(w[i-15], 7), XOR(rotation_droite(w[i-15], 18), decal_droite(w[i-15], 3)))
            S1 = XOR(rotation_droite(w[i-2], 17), XOR(rotation_droite(w[i-2], 19), decal_droite(w[i-2], 10)))
            w[i] = w[i-16] + S0 + w[i-7] + S1
        a, b, c, d, e, f, g, h = h0, h1, h2, h3, h4, h5, h6, h7
        for i in range(0, 64):
            S0 = XOR(rotation_droite(e, 6), XOR(rotation_droite(e, 11), rotation_droite(e, 25)))
            ch = XOR(ET(e, f), ET(NON(e), g))
            tmp1 = h + S0 + ch + K[i] + w[i]
            S1 = XOR(rotation_droite(a, 2), XOR(rotation_droite(a, 13), rotation_droite(a, 22)))
            maj = XOR(ET(a, b), XOR(ET(a, c), ET(b, c)))
            tmp2 = S1 + maj
            h, g, f, e, d, c, b, a = g, f, e, d + tmp1, c, b, a, tmp1 + tmp2
        h0 += a
        h1 += b
        h2 += c
        h3 += d
        h4 += e
        h5 += f
        h6 += g
        h7 += h

Q15

def hex(s):
    x = s[0] + 2*s[1] + 4*s[2] + 8*s[3]
    if x == 10: return 'a'
    if x == 11: return 'b'
    if x == 12: return 'c'
    if x == 13: return 'd'
    if x == 14: return 'e'
    if x == 15: return 'f'
    return str(x)
def hache_final():
    hache = ""
    H = h0 + h1 + h2 + h3 + h4 + h5 + h6 + h7
    n = len(H)
    for i in range(n//4):
        hache += hex(H[4*i: 4*i+4])
    return hache