info-nf

Exercice

Q1

def puiss(x, n):
    p = 1
    while n != 0 :
        if n % 2 == 1 :
            p = p * x
        x = x * x
        n = n // 2
    return p

Q2

L = [10, 0, 7, -3, -2, 0, -1]

Q3

def valeur(x, L):
    v = 0
    for i in range(len(L)):
        v += puiss(x, i) * L[i]
    return v

Q4

la fonction puiss a une complexité $O(log(n))$

On pose $n = len(L) =$ dégrée du polynôme
donc : $$C(n) = O(\sum_{i=0}^{n-1} log(i)) = O(nlog(n))$$

voir plus de detail ici

Q5

def images(X, L):
    Y = []
    for x in X:
        Y.append(valeur(x, L))
    return Y

Q6

Version iterative

def compose(x, L, n):
    v = x
    for i in range(n):
        v = valeur(v, L)
    return v

Version recursive

def compose(x, L, n):
    if n == 0: return x
    return valeur(compose(x, L, n-1), L)

Version optimisee (WIP)

def compose_opti(x, L, n):
    v = x
    while n != 0 :
        if n%2 == 1 :
            pass
            # TODO
        n = n//2
    return p

Partie 1

import numpy as np

Q7

def minProduit(T, i, j):
    if i == j-1 :
        return 0
    R = []
    for k in range(i+1, j):
        c = minProduit(T, i, k) + minProduit(T, k, j) + T[i]*T[k]*T[j]
        R.append(c)
    return min(R)

Q8

D = {}
def minPrd(T, i, j):
    if (i, j) in D:
        return D[(i, j)]
    if i == j-1 :
        D[(i, j)] = 0
        return 0
    R = []
    for k in range(i+1, j):
        c = minPrd(T, i, k) + minPrd(T, k, j) + T[i]*T[k]*T[j]
        R.append(c)
    D[(i, j)] = min(R)
    return D[(i, j)]

T = [20, 10, 35, 8, 12]
# minPrd(T, 0, len(T)-1)
# print(D)

Q9

def matriceC(T):
    n = len(T)-1
    C = [[0]*n for i in range(n)]

    for d in range(1, n):
        for i in range(n-d):
            j = i + d
            R = []
            for k in range(i, j):
                R.append(C[i][k] + C[k+1][j] + T[i]*T[k+1]*T[j+1])
            C[i][j] = min(R)
    return C
# print(matriceC(T))

Q10

def matriceP(T, C):
    n = len(T)-1
    P = [[0]*n for i in range(n)]

    for d in range(1, n):
        for i in range(n-d):
            j = i + d
            for k in range(i, j):
                if C[i][k] + C[k+1][j] + T[i]*T[k+1]*T[j+1] == C[i][j]:
                    P[i][j] = k
                    break
    return P

Q11

def produit_matriciel(M):
    n = len(M)
    T = [len(m) for m in M]
    T.append(len(M[-1][0]))

    C = matriceC(T)
    P = matriceP(T, C)

    def produit(M, i, j):
        if i == j: return M[i]
        if i == j-1 : return numpy.dot(M[i][j])
        return produit(M, i, P[i][j]) * produit(M, P[i][j] + 1, j)

    return produit(M, 0, n-1)

Partie 2

Q12

8 bits, car $2^8 = 256$ états, de 0 a 255

Q13

On a 1000 lignes et 1800 colonnes, donc $ 18 \times 10^5 $ pixels, donc $ 3 \times 18 \times 10^5 $ entiers sur 1 octet, donc la taille totale est $ 5273,43 $ ko

Q14

def histogramme(M):
    H = [[0]*256 for c in range(3)]

    for i in range(len(M)):
        for j in range(len(M[0])):
            for c in range(3):
                val = M[i][j][c] 
                H[c][val] += 1
    return H
import matplotlib.pyplot as plt

Q15

def representation(H):
    t = list(range(256))
    plt.plot(t, H[0], color="red", label="rouge")
    plt.plot(t, H[1], color="green", label="vert")
    plt.plot(t, H[2], color="blue", label="bleu")
    plt.legend()
    plt.show()

M = plt.imread("Iris_versicolor_3.jpg")

# H = histogramme(M)
# representation(H)

Q16

def distance(X, Y):
    d = 0
    for c in range(3):
        d += abs(X[c] - Y[c])
    return d

Q17

from random import randint
def init_centroides(M, k):
    n, m, _ = M.shape
    C = []
    for i in range(k):
        x, y = randint(0, n-1), randint(0, m-1)
        C.append(M[x][y])
    return C

Q18

def proche_centroide(P, C):
    m = np.inf
    i_min = 0
    for i in range(len(C)):
        if distance(P, C[i]) < m :
            i_min = i
            m = distance(P, C[i])
    return i_min

Q19

def segmentation(M, C):
    n, m, _ = M.shape
    R = np.zeros((n, m))
    for i in range(n):
        for j in range(m):
            R[i][j] = proche_centroide(M[i][j], C)
    return R

Q20

def nv_centroide(M, R, g):
    n, m, _ = M.shape
    c0, c1, c2 = 0, 0, 0
    total = 0
    for i in range(n):
        for j in range(m):
            if R[i][j] == g :
                c0 += M[i][j][0]
                c1 += M[i][j][1]
                c2 += M[i][j][2]
                total += 1
    return [c0/total, c1/total, c2/total]

Q21

def maj_centroides(M, R, k):
    C = []
    for i in range(k):
        C.append(nv_centroide(M, R, i))
    return C

Q22

def kmeans(M, k, n):
    C = init_centroides(M, k)
    for i in range(n):
        R = segmentation(M, C)
        new_C = maj_centroides(M, R, k)
        if new_C == C : 
            break
        C = new_C
    return R, C

Q23

def calcul_inertie(M, R, C):
    n, m, _ = M.shape
    inertie = 0
    for i in range(n):
        for j in range(m):
            cluster = R[i][j]
            inertie += distance(M[i][j], C[cluster])
    return inertie

Q24

def inerties(M, n):
    D = {}
    for k in range(1, 10):
        R, C = kmeans(M, k, n)
        D[k] = calcul_inertie(M, R, C)
    return D

SQL

Q25

La clé primaire est le couple (ligne, colonne), car pour déterminer un unique pixel il faut la ligne et la colonne, tandis qu’utiliser uniquement la ligne ou la colonne ne donne pas l’unicité

Q26

$$ \pi_{ligne, colonne, rouge, vert, bleu} \left(\sigma_{\begin{subarray}{c} cluster=0 \\ or \\ cluster=2 \end{subarray}} \left(Segmentation\right)\right)$$

Q27

SELECT ligne, colonne, rouge, vert, bleu 
FROM Segmentation
WHERE cluster = 1 or cluster = 2
ORDER BY ligne, colonne ASC

Q28

SELECT cluster, COUNT(*) AS compte, AVG(rouge) AS intensite_rouge_centroide
FROM Segmentation
GROUP BY cluster
HAVING intensite_rouge_centroide BETWEEN 100 AND 200
ORDER BY compte DESC

Q29

SELECT AVG(compte)
FROM (
    SELECT COUNT(*) AS compte 
    FROM Segmentation
    GROUP BY cluster
    )