Exercice

Q1 

def fact(k):
    S = 1
    for i in range(1, k+1):
        S *= i
    return S

Q2

La fonction contient une boucle qui itère k fois, chaque itération est un $O(1)$.
Donc la complexité est $O(k)$

Q3 

def som_fact(n):
    S = 0
    for i in range(n+1):
        S += fact(k)
    return S

Q4 

def liste_fact(L):
    S = []
    for x in L:
        S.append(fact(x))
    return S

Q5 

def existe(x, L):
    return fact(x) in L

Alternativement :

def existe(x, L):
    fact_x = fact(x)
    for e in L:
        if e == fact_x:
            return True
    return False

Q6 

def compte(L, p):
    fact_p = fact(p)
    c = 0
    for x in L:
        if x > fact_p :
            c += 1
    return c

Q7 

def superieure(L, k):
    return compte(L, k) == len(L)

Partie 1-A

Q8

$$ \pi_{nom}\left( \sigma_{chiffre = 5}(images)\right)$$

Q9 

SELECT nom 
FROM images
WHERE chiffre = 5 
OR chiffre = 8
ORDER BY nom ASC

Q10 

SELECT nom
FROM images
WHERE nom LIKE '______%'

Q11 

SELECT COUNT(*)
FROM images

Q12 

SELECT chiffre, COUNT(*) AS compte
FROM images
GROUP BY chiffre
ORDER BY compte DESC

Q13 

SELECT chiffre
FROM images
GROUP BY chiffre
HAVING COUNT(*) > 0.1 * (SELECT COUNT(*) FROM images)

Partie 1-B

Q14 

def distance(A, B):
    S = 0
    for i in range(8):
        for j in range(8):
            S += abs(A[i][j] - B[i][j])
    return S

Q15 

def indices():
    return list(range(len(E)))

Q16

Je choisis d’utiliser le tri a bulle :

def tri_indices(D, X):
    n = len(D)
    for p in range(n):
        for i in range(n-1):
            if distance(E[D[i]], X) > distance(E[D[i+1]], X):
                D[i], D[i+1] = D[i+1], D[i]

Q17 

def plus_proches(X, k):
    D = indices()
    tri_indices(D, X)
    L = []
    for i in range(k):
        L.append(F[D[i]])
    return L

Q18 

def knn(X, k):
    L = plus_proches(X, k)
    D = {}
    for x in L:
        if x in D :
            D[x] += 1
        else :
            D[x] = 1

    chiffre_max = -1
    compte_max = 0
    for cle in D :
        if D[cle] > compte_max :
            chiffre_max = cle
            compte_max = D[cle]
    return chiffre_max

Q19 

def precision(k):
    c = 0
    for t in range(len(T)):
        if knn(T[i], k) == P[i] :
            c += 1
    return c / len(T) * 100

Q20 

K = list(range(3, 16))
prec = []
for k in K :
    prec.append(precision(k))

plt.plot(K, prec, color="blue")
plt.grid()
plt.show()

Partie 1-C

Q21 

def code_postal(M, k):
    M = np.array(M)
    h, w = M.shape
    n = w//8
    
    code = 0
    for i in range(n):
        code *= 10
        code += knn(M[:, i*8 : (i+1)*8], k)
    return code

Partie 2

Q22 

def cout_chemin(M, C):
    cout = 0
    for i in range(len(M)):
        cout += M[i][C[i]]
    return cout

Q23 

def glouton(M, j):
    M = np.array(M)
    h, w = M.shape
    C = [j]
    for i in range(1, h):
        if j == 0:
            L = [0, 1]
        if j == w-1:
            L = [w-2, w-1]
        else :
            L = [j - 1, j, j + 1]
        j = min(L, key = lambda x : M[i][x])
        C.append(j)
    return C

Q24

Non, contre-exemple :

#     0  1  2  3  4  5  6  7
M = [[2, 2, 2, 1, 2, 2, 2, 2],
     [5, 5, 6, 5, 1, 5, 5, 5],
     [5, 1, 5, 5, 5, 4, 5, 5],
     [5, 1, 5, 5, 5, 4, 5, 5],
     [5, 1, 5, 5, 5, 4, 5, 5],
     ]

Avec la solution glouton, a partir de l’indice 3, on obtient le cout 1 + 1 + 4 + 4 + 4 = 14 Alors que la solution optimale est 1 + 6 + 1 + 1 + 1 = 10

Q25 

memo = {}
def cout_min(M, i, j):
    M = np.array(M)
    h, w = M.shape
    if (i, j) in memo : 
        return memo[(i, j)]
    if i == h-1 :
        return M[i][j]
    if j == 0:
        L = [0, 1]
    elif j == w-1:
        L = [w-2, w-1]
    else :
        L = [j - 1, j, j + 1]
    cout_possible = [cout_min(M, i+1, x) for x in L]
    S = min(cout_possible) + M[i][j]
    memo[(i, j)] = S
    return S

Q26 

def couts(M):
    M = np.array(M)
    h, w = M.shape
    R = np.zeros_like(M)

    for i in range(h-1, -1, -1):
        for j in range(w):
            if i == h-1 :
                R[i, j] = M[i][j]
            elif j == 0:
                R[i, j] = M[i][j] + min(R[i+1, j], R[i+1, j+1])
            elif j == w-1:
                R[i, j] = M[i][j] + min(R[i+1, j-1], R[i+1, j])
            else :
                R[i, j] = M[i][j] + min(R[i+1, j-1], R[i+1, j], R[i+1, j+1])
    return R

Q27

Puisque les éléments de R représentent le coûts minimum possible a partir de chaque coordonnées, alors on peut utiliser l’approche glouton sur la matrice R :

def chemin_min(M):
    R = couts(M)
    return glouton(R)

Q28 

def supprime_chemin(M, C):
    for i in range(len(C)):
        del M[i][C[i]]
def supprime_chemin(M, C):
    M = np.array(M)
    h, w = M.shape
    R = np.zeros((h, w-1))
    for i in range(h):
        j = C[i]
        R[i] = np.concatenate((M[i, :j], M[i, j+1:]))
    return R
supprime_chemin(M, chemin_min(M))

Q29 

def gradients(M):
    M = np.array(M)
    h, w = M.shape
    G = np.zeros_like(M)
    for i in range(h):
        for j in range(w):
            if i == 0 :
                A = abs(M[i, j] - M[i+1, j])
            elif i == h-1 :
                A = abs(M[i, j] - M[i-1, j])
            else :
                A = abs(M[i-1, j] - M[i+1, j])
            if j == 0 :
                B = abs(M[i, j] - M[i, j+1])
            elif j == w-1 :
                B = abs(M[i, j] - M[i, j-1])
            else :
                B = abs(M[i, j-1] - M[i, j+1])
            G[i, j] = A + B
    return G

Q30 

def reduction(M, n):
    for i in range(n):
        G = gradients(M)
        c = chemin_min(G)
        supprime_chemin(M, c)