Aller au contenu

ITC CCMP 2025 - Corrigé

Sujet CCMP 2025

Partie SQL⚓︎

Q1

Écrire une requête permettant de retourner la liste des identifiants de conteneurs et leur ratio tarification/longueur trié par ordre décroissant, partant de Marseille et devant aller à Barcelone, avec une mise à disposition avant le 01/01/2025.

SQL
1
2
3
4
5
6
SELECT idC, (val * 1.0 / taille) AS ratio
FROM CONTENEURS
WHERE portDepC = 'Marseille' 
  AND portDestC = 'Barcelone'
  AND dateDisp < '2025-01-01'
ORDER BY ratio DESC;

Remarques :

La multiplication par 1.0 sert à convertir la valeur entière de val pour ne pas obtenir le quotient de la division entière qui serait obtenu sans cette conversion.

Il est possible de vérifier que sans cette conversion le ratio est toujours 0 ici.

Les dates s'écrivent avec des guillemets comme les chaînes de caractères.

Q2

SQL
1
2
3
4
SELECT idN, COUNT(idC) AS nb_conteneurs
FROM NAVIRES
NATURAL JOIN CONTENEURS
GROUP BY idN;

Remarque :

Le NATURAL JOIN est ici possible car les deux relations NAVIRES et CONTENEURS seront jointes par le couple clé primaire / clé étrangère avec le même nom : idN.

Il est aussi possible d'écrire : JOIN CONTENEURS ON NAVIRES.idN = CONTENUERS.idN

Q3

Le profit est obtenu à partir de la somme des profits de chaque objet d'indice i pour lesquels \(x_i = 1\).

Il est possible de répondre avec une boucle ou avec une liste par compréhension.

Avec une boucle:

Python
1
2
3
4
5
6
def profit(obj:[(int)], S: [int]) -> int:
    profit = 0 # initialisation du profit à 0
    n = len(obj)
    for i in range(n):
        profit += obj[i][1] * S[i] # si S[i] vaut 0, profit n'est pas incrémenté
    return profit

Avec une liste par compréhension, et la fonction sum (somme)

Python
1
2
def profit(obj:[(int)], S: [int]) -> int:
    return sum([obj[i][1] * S[i] for i in range(len(obj))])

Q4

Le problème du sac à dos, est un problème d'optimisation,

Nous cherchons le profit maximum, parmi les instances qui vérifient la contrainte de capacité.

Voici la fonction contrainte

Python
1
2
3
def contrainte(obj:[(int)], S: [int], b: int) -> bool:
    poids_total = sum([obj[i][0] * S[i] for i in range(len(obj))])
    return poids_total <= b

Q5 Avec la représentation de l'espace des solutions avec un arbre binaire, les feuilles correspondent chacune à une solution.

Dans le cas où \(n = 3\), et où pour chaque noeud, le fils gauche correspond au choix de sélectionner l'objet, les feuilles bet c correspondent à :

  • b : la solution [1, 1, @] le premier et le deuxième objets sont sélectionnés mais pas le troisème

  • c : la solution [1, 0, 1], le premier et le troisème objets sont sélectionner mais pas le deuxième.

Q6

Pour \(n = 3\), il y a 8 feuilles, ce qui correspond à \(2^3\).

Comme chaque feuille, correspond à une solution \([x_9,x_1,...,x_n]\) et que pour chaque \(x_i\) il y a deux choix possibles.

Pour une instance de n objets, il y a \(2^n\) choix possibles.

Un algorithme de force brute envisage d'étudier toutes les solutions pour trouver celle (ou celles) qui vérifiant la contrainte de capacité optimise(nt) le profit.

Comme les fonctions de calculs du profit et de vérification de la contrainte sont toutes les deux en \(O(n)\), l'algorithme de type force brute exécute une boucle de \(2^n\) tours avec pour chaque tour une complexité en \(O(n)\).

La complecité totale temporelle est alors en \(O(n.2^n)\).

Et donc, en effet, lorsque \(n\) devient grand, le temps de calcul devient démuséremment grand.

4. Résolution approchée par un algorithme glouton⚓︎

Q7

Nous commençons par calculer les ratio :

  • \( q_0 = \frac{3}{2} = 1.5 \)
  • \( q_1 = \frac{4}{1} = 4.0 \)
  • \( q_2 = \frac{4}{4} = 1.0 \)

Donc les valeurs initiales de Liste initiale des rapports : Lqi = [1.5, 4.0, 1.0]
Liste des indices : Li = [0, 1, 2]

Nous trions Lqi en décroissant et on réorganise simultanément Li :

  • Lqi trié : [4.0, 1.5, 1.0]
  • Li trié : [1, 0, 2]

Puis nous choisissons les objets avec un choix glouton :

Initialisation: b = 5, S = []

  1. (1,4) est sélectionné car \( 1 \leq 5\)

b = 5 - 1 = 4

S = [1]

  1. (2,3) est sélectionné car son \(2 \leq 4\)

b = 4 - 2 = 2

S = [1, 0]

  1. (4,4) n'est pas sélectionné car \( 4 > 2\)

Le profit total est de \(4+3=7\), et le poids total de \(1+2 = 3\) .

Q8

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def construitLi(obj):
    Lqi = []
    Li = []
    for i in range(len(obj)):
        Lqi.append(obj[i][1] / obj[i][0])  # ligne 5, ajout des ratio, non triés
        Li.append(i)
    for i in range(1, len(Lqi)):
        x = Lqi[i]
        j = i
        while j > 0 and Lqi[j - 1] < x:
            Lqi[j] = Lqi[j - 1]
            Li[j] = Li[j - 1]              # ligne 12, décalage du tri par insertion
            j -= 1
        Lqi[j] = x
        Li[j] = i                          # ligne 15, insertion
    return Li

Q9

La fonction construitLi utilise un tri par insertion appliqué à la liste Lqi.

Dans le meilleur des cas, les éléments sont déjà triés (en ordre décroissant).

Pour chaque \( i \), la condition Lqi[j-1] < x est toujours fausse et donc la boucle ẁhile` n'effectue aucun tour.

Comme les instructions des lignes 8,9, 14 et 15 sont en \(O(1)\), la fonction construitLi a alors une complexité temporelle en \(n . O(1)\) = \(O(n)\).

Dans le pire des cas, les éléments de Lqi sont triés en ordre croissant (le contraire de l'ordre désiré).

Chaque nouvel élément doit être déplacé au début de la liste déjà triée.

Pour l'élément en position \( i \), il faut effectuer \( i \) comparaisons et déplacements.

Pour \(i\) variant de 1 à \(n - 1\), nous avons donc : \(\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2}\). Donc une complexité temporelle en \(O(n^2)\).

Q10

Python
1
2
3
4
5
6
7
8
S = len(obj) * [0]
Li = construitLi(obj)
j = 0
while j < len(obj):
    if obj[Li[j]][0] <= b:              # Ligne 4,si le poids de l’objet est ≤ b
        S[Li[j]] = 1                    # Ligne 5, sélection de l’objet
        b = b - obj[Li[j]][0]           # Ligne6, mise à jour la capacité restante
    j += 1                              # Ligne 7, pour objet suivant

Q11

On reprend le cas particulier où obj=[(2,3),(1,4),(4,4)] et b=5 .

La solution optimale est avec un profit de 8 avec le choix des objets (1,4),(4,4).

Or la solution gloutonne nous donnes un profit de 7, ce qui n'est pas optimal.

La solution gloutonne ne donne pas toujours la soltuion optimale mais permet d'obtenir rapidement une approximation de la soltuion optimale.

5 Résolution exacte par un algorithme de programmation dynamique⚓︎

Q12

Si on prend le cas où obj=[(2,3),(1,4),(4,4)] et b=5, n sera donc initialisé à 3.

Et les lignes 2 à 8, vont donc initialisé une matrice de 4 ([n + 1) lignes et 6 (\(b + 1\)] colonnes.

T = [ [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0] ]

Le premier tour de boucle for, ligne 9, modifie T[1].

À la fin du tour, T[1] = [0, 0, 3, 3, 3, 3]

Le deuxième tour de boucle for, ligne 9, modifie T[2].

À la fin du tour, T[2] = [0, 4, 4, 7, 7, 7]

Le troisième tour de boucle for, ligne 9, modifie T[3].

À la fin du tour, T[3] = [0, 4, 4, 7, 7, 8]

Donc après les 3 tours de la boucle for, T=

[[0, 0, 0, 0, 0, 0], [0, 0, 3, 3, 3, 3], [0, 4, 4, 7, 7, 7], [0, 4, 4, 7, 7, 8]]

L'algorithme retourne T[n][b], ici 8, cela correspond au profit optimal obtenu avec le choix parmi les \(n\) objets pour une quantité de ressources disponibles de \(b\) .

Q13

L'algorithme se déroule en deux étapes :

1. Initialisation du tableau T (lignes 4–8)

  • Deux boucles imbriquées :

  • \( k \in [0, n] \) : \( n+1 \) itérations

  • \( r \in [0, b] \) : \( b+1 \) itérations

  • À chaque itération, on ajoute une valeur 0 dans une sous-liste.

Complexité de cette partie : O(n × b)

2. Remplissage du tableau T (lignes 9–14)

  • Deux boucles imbriquées :

  • \( i \in [0, n-1] \)

  • \( r \in [0, b] \)

  • Chaque itération réalise des comparaisons et des affectations simples :

  • Accès à des cases de tableau

  • Calcul d’un maximum
  • Somme d’entiers

Complexité : O(n × b)

Ainsi a complexité asymptotique temporelle de la fonction KPprogDynamique(obj,b) est en \(O(n.b)\) .

Q14

On part du tableau T construit par programmation dynamique (lignes 2–14).

  • Données : obj = [(2,3), (1,4), (4,4)], donc n = 3, b = 5
  • Résultat optimal précédemment trouvé : T[3][5] = 8
  • Initialisation :
Python
1
2
3
S = [0, 0, 0]
k = 2
r = 5

1ère itération

  • T[3][5] = 8, T[2][5] = 7 → T[3][5] ≠ T[2][5]
  • On entre directement dans la suite :
    S[2] = 1, r = 5 - 4 = 1, k = 1
Python
1
2
3
S = [0, 0, 1]
k = 1
r = 1

2e itération

  • T[2][1] = 4, T[1][1] = 0 → T[2][1] ≠ T[1][1]
  • Donc :
    S[1] = 1, r = 1 - 1 = 0, k = 0
Python
1
2
3
S = [0, 1, 1]
k = 0
r = 0

3e itération

La condition r > 0 devient fausse → boucle terminée.

La solution reconstruite est :

Python
1
S = [0, 1, 1]  # objets 1 et 2 sélectionnés

Ce qui correspond bien à la solution optimale (profit total = 8).

Complexité temporelle de la reconstruction

  • La boucle while en ligne 8 remonte de k = n-1 à 0.
  • Chaque itération sélectionne ou ignore un objet (au plus n fois).

Complexité de la reconstruction :
\(\mathcal{O}(n)\)

La phase de reconstruction ne modifie pas la complexité asymptotique de l’algorithme qui reste en \(O(n.b)\) .