CAPES informatique externe 2025, épreuve 1Sujet et rapport du jury

INFORMATION AUX CANDIDATS

CAPES EXTERNE NUMÉRIQUE ET SCIENCES INFORMATIQUES

• -
  Concours externe du CAPES de l'enseignement public :
  Concours Section/option Epreuve Matière E|B|E 6|2|0|0|E 1|0|1

  9/3/1/1

• -
  Troisième concours du CAPES de l'enseignement public :
  Concours Section/option Epreuve Matière E|B|V 6|2|0|0|E 1|0|1

  9/3/1/1

• -
  Concours externe du CAFEP/CAPES de l'enseignement privé :
  Concours Section/option Epreuve Matière E|B|F

  6

  0

  0

  1

  0

  9

  3/

  1

Autour du problème de la couverture par ensembles

1. Un exemple introductif

• -La table ProgrammeCapes qui liste les thèmes au programme du CAPES de NSI. Cette table contient un seul champ Theme.
• -La table Enonce qui liste les énoncés disponibles. Cette table contient cinq champs : Id, Concours, Discipline, Annee et Epreuve.
• -La table Balise qui associe aux énoncés des mots-clés. Cette table a deux champs Id et MotCle. On suppose que tous les identifiants Id apparaissant dans cette table sont des identifiants d'énoncés de la table Enonce.
• -La table Ancrage qui associe à un mot-clé le thème du programme auquel il se rapporte. Cette table a deux champs MotCle et Theme. On suppose que tous les thèmes apparaissant dans cette table sont des thèmes au programme figurant dans la table ProgrammeCapes.

• Q.1 Quelle requête SQL permet d'obtenir la liste des thèmes au programme du CAPES ?
• Q.2 Quelle requête donne le nombre d'années d'épreuve de CAPES présentes dans la base? Le résultat de la requête doit être réduit à ce nombre.

• Q.3 Quelle requête SQL permet d'obtenir la liste, triée par ordre alphabétique, des mots-clés associés au thème Algorithmique qui apparaissent dans au moins un énoncé de la base?
• Q.4 Quelle requête SQL permet d'obtenir la liste des thèmes couverts par les énoncés de la base de données?
• Q.5 Quelle requête SQL permet de lister les thèmes au programme qui ne sont pas couverts par au moins un énoncé de la base de données?

• Q.6 Quelle requête SQL permet d'obtenir la liste qui associe aux identifiants d'énoncés du CAPES les thèmes qu'ils couvrent? On veillera à éviter les doublons dans la liste résultat, par exemple si un énoncé couvre le thème Algorithmique parce qu'il est à la fois annoté par le mot-clé glouton et le mot-clé programmation dynamique, l'association de ce sujet au thème Algorithmique ne doit apparaître qu'une seule fois dans le résultat.

2. Présentation du problème

Figure 1 - L'exemple (X_e, ℱ_e)

• -Pour le problème CouvEns sur l'instance (X_e, F_e), une solution peut être l'ensemble {P_2, P_3, P_4} qui est bien une couverture de cardinal minimal. C'est en fait la seule solution possible.
• -Pour le problème CouvEnsTaille sur l'instance (X_e, ℱ_e), l'unique solution est 3.
• -Pour le problème CouvEnsSeuil sur l'instance (X_e, ℱ_e, 4), l'unique solution est vrai (True) tandis que sur l'instance (X_e, F_e, 2), l'unique solution est faux (False).

• Q_0 = {0, 1, 3, 4, 6, 7},
• Q_2 = {7, 8},
• Q_4 = {0, 1, 3, 4, 5}.
• Q_1 = {1, 2, 4, 5, 7},
• Q_3 = {6, 8},
  Donner des sorties pour les problèmes CouvEns et CouvEnsTaille sur l'entrée (X, ℱ) ainsi que pour CouvEnsSeuil sur l'entrée (X, F, 2).
  \end{itemize}

2.1. Manipulation des problèmes

• Q.8 On suppose fourni, pour cette question seulement, un algorithme couv_ens_taille résolvant CouvEnsTaille, c'est-à-dire, prenant en arguments un ensemble X et un ensemble F de parties de X et renvoyant le cardinal d'une couverture de X de cardinal minimal. Proposer le pseudo-code d'un algorithme utilisant couv_ens_taille et résolvant CouvEnsSeuil. Donner le nombre d'appels à couv_ens_taille effectués en fonction des valeurs d'entrées X, F et K.
• Q.9 On suppose fourni, pour cette question seulement, un algorithme couv_ens_seuil résolvant CouvEnsSeuil, c'est-à-dire prenant en arguments un ensemble X, un ensemble F de parties de X et un entier K et renvoyant un booléen indiquant s'il existe une couverture de X par F de cardinal ⩽ K.
  • a)Proposer le pseudo-code d'un algorithme utilisant couv_ens_seuil, résolvant le problème CouvEnsTaille. Cet algorithme devra effectuer un nombre le plus faible possible d'appels à couv_ens_seuil.
  • b)Donner, sans justifier, en fonction de X et F, un ordre de grandeur du nombre d'appels à couv_ens_seuil effectués par cet algorithme.
  • c)Proposer un invariant de boucle, qui justifierait la correction de cet algorithme.

2.2. Représentation en machine

• -Étant donné que l'on se restreint au cas où X = [ [0, n − 1] ] pour un certain n, l'entrée X sera représentée par un entier n.
• -
  Une partie de X sera représentée par la liste de ses éléments. Bien que dans tous les exemples les éléments d'une partie P ∈ F soient listés dans l'ordre croissant, ceci n'est pas requis. On n'utilisera pas cette hypothèse par la suite. L'ensemble F des parties de X autorisées pour la couverture sera alors représenté par la liste de ses éléments, de type List[List[int]]. Aussi dans la suite, on suppose défini le type ci-dessous.

  Parties = List[List[int]]
  

  Ainsi les données X_e et ℱ_e de l'exemple seront représentées en Python par les valeurs n_ex et f_ex du code ci-dessous.

  p0_ex = [6, 7, 8, 9, 10, 11]
  p1_ex = [4, 5, 7, 8]
  p2_ex = [0, 3, 6, 9]
  p3_ex = [1, 3, 4, 7, 10]
  p4_ex = [2, 5, 8, 11]
  

    p5_ex = [0, 1]
    f_ex = [p0_ex, p1_ex, p2_ex, p3_ex, p4_ex, p5_ex]
    n_ex = 12

• -Pour manipuler les couvertures, on s'autorisera deux encodages :
  • -Un sous-ensemble C de f = [P_0, P_1, …, P_(m − 1)] pourra être représenté au moyen d'une liste des indices dans la liste F des parties présentes dans C. Un tel objet est alors de type List[int]. On dira alors que C est représenté par liste d'indices. Par exemple le sous-ensemble C_1 = {P_0, P_3, P_4, P_2} de l'exemple pourra être représenté par la liste [0, 4, 3, 2] ou encore [2, 3, 4, 0].
  • -Un sous-ensemble C de f = [P_0, P_1, …, P_(m − 1)] pourra aussi être représenté par un tableau de booléens t, de taille m = |F|, indiquant dans chaque case d'indice i si P_i est présent ou non dans C. Un tel objet est alors de type List[bool]. On dira alors que C est représenté par sa fonction indicatrice. Par exemple le sous-ensemble C_1 = {P_0, P_3, P_4, P_2} de l'exemple sera représenté par le tableau [True, False, True, True, True, False].
• Q.
  10 Définir une fonction card1 prenant en argument un sous-ensemble , représenté par liste d'indices, et renvoyant son cardinal.

  card1(c: List[int]) -> int
  

• Q.
  11 Définir une fonction card2 prenant en argument un sous-ensemble C, représenté par fonction indicatrice, et renvoyant son cardinal.

  card2(c: List[bool]) -> int
  

2.3. Vérification des solutions

• Q.
  12 Définir une fonction verification1 prenant en arguments n et f représentant une instance (X, F) et c représentant un sous-ensemble C de F par liste d'indices, et renvoyant si C est une couverture de X par F.

  verification1(n: int, f: Parties, c: List[int]) -> bool
  

• Q.13 En utilisant les notations X = [ [0, n − 1] ], F = {P_0, P_1, …P_(m − 1)}, pour tout i ∈ [ [0, m − 1] ], n_i = |P_i|, l = ∑_(i = 0)^(m − 1)n_i, et finalement q = |C|, donner la complexité algorithmique pire cas de la fonction verification1 proposée à la question précédente (Q. 12). On attend une justification succincte.
• Q.
  14 Définir une fonction verification2 prenant en arguments n et f représentant une instance (X, F) et c représentant un sous-ensemble C de F par sa fonction indicatrice, et renvoyant si C est une couverture de X par F.

  verification2(n: int, f: Parties, c: List[bool]) -> bool
  

• Q.15 En utilisant les notations de la Q. 13 donner la complexité algorithmique pire cas de la fonction verification2 (Q. 14). On attend une justification succincte.
• Q.
  16 Définir une fonction est_couvrable prenant en arguments n et f représentant une instance (X, ℱ) et testant si X est couvrable par F.

  est_couvrable(n: int, f: Parties) -> bool
  

2.4. Obtenir des instances en Python

assoc_id_theme.csv
9,Algorithmique
3,Algorithmique
5,Algorithmique
9,Bases de données

oeufs.csv
brouillés, au plat, au plat, miroir
bénédicte, au plat, coque, parfait, mollet

>>> import csv
>>> with open('oeufs.csv', newline='') as csvfile:
... filereader = csv.reader(csvfile, delimiter=',')
... for row in filereader:
... for i in range(len(row)):
... print(row[i], end=" / ")
... print()
brouillés / au plat / au plat / miroir /
bénédicte / au plat / coque / parfait / mollet /

cree_instance (dico: Dict[int, List[str]], num: Dict[str, int]) ->
→ Tuple[int, Parties]

3. Un algorithme par brute force

3.1. Version naïve

• Q.19 Définir une fonction suivant prenant en argument un tableau de m booléens représentant la décomposition en base 2 d'un entier e de [ [0, 2^m − 1] ] (les bits de poids faibles sont à droite), et modifiant le tableau pour :
  • -qu'il contienne la décomposition en base 2 de l'entier e + 1, dans le cas où e < 2^m − 1;
  • -qu'il contienne uniquement des False sinon.

    suivant(cand: List[bool]) -> bool

• Q.
  20 Définir une fonction couv_ens_naif prenant en arguments n et f représentant une instance (X, F) et renvoyant un couple (q, c) tel que c est la représentation par fonction indicatrice d'une couverture de cardinal minimal de X par F et q est le cardinal de cette couverture.

  couv_ens_naif(n: int, f: Parties) -> Tuple[int, List[bool]]
  

3.2. Énumération par cardinal croissant

• Q.
  21 Définir une fonction binomiaux prenant en argument un entier m et renvoyant une matrice b, indicée par les entiers [ [0, m] ] × [ [0, m] ], telle que pour tout p ∈ [ [0, m] ] et tout k ∈ [ [0, m] ], b [p] [ k ] contient le coefficient (p/k). On précisera, sans la justifier, la complexité algorithmique pire cas de la fonction implémentée.

  binomiaux(m: int) -> List[List[int]]
  

• a)former un ensemble à k − 1 éléments de {0, 1, …, m − 2} et y ajouter l'élément m − 1;
• b)ou bien former un ensemble à k éléments de {0, 1, …, m − 2}.

Figure 2 - Numérotation des sous-ensembles à 3 éléments de [ [0, 4] ].

• -Comme l'indique la Figure 2, il y a (4/2) = 6 ensembles à 3 éléments de [ [0, 4] ] qui contiennent le nombre 4. Autrement dit, en choisissant de construire un ensemble de type a ), on obtiendrait un ensemble de numéro entre (0) et (5). Aussi choisit-on de construire un ensemble de type b ), c'est-à-dire ne contenant pas 4. On cherche donc l'ensemble de numéro 8 − 6 = 2 parmi les ensembles à 3 éléments de [ [0, 3] ].
• -Comme l'indique la Figure 2, il y a (3/2) = 3 ensembles à 3 éléments de [ [0, 3] ] qui contiennent le nombre 3. Autrement dit, en choisissant de construire un ensemble de type a ), on obtiendrait un ensemble de numéro entre 0 et 2 . Aussi choisit-on ici de construire un ensemble de type a ), c'est-à-dire contenant 3 . On cherche donc l'ensemble de numéro 2 parmi les ensembles à 2 éléments de [0, 2], sachant qu'on lui ajoutera 3.

• -Comme l'indique la Figure 2, il y a (2/1) = 2 ensembles à 2 éléments de [ [0, 2] ] qui contiennent le nombre 2. Autrement dit, en choisissant de construire un ensemble de type a ), on obtiendrait un ensemble de numéro entre 0 et 1 . Aussi choisit-on de construire un ensemble de type b ), c'est-à-dire ne contenant pas 2. On cherche donc l'ensemble de numéro 2 − 2 = 0 parmi les ensembles à 2 éléments de [ [0, 1] ].
• -Il y a (1/1) = 1 ensemble à 2 éléments de [ [0, 1] ] qui contient le nombre 1 . Aussi choisit-on de construire un ensemble de type a ), c'est-à-dire contenant 1 . On cherche donc l'ensemble de numéro 0 parmi les ensembles à 1 éléments de [ [0, 0] ], sachant qu'on lui ajoutera 1.
• -Il y a (1/1) = 1 ensemble à 1 élément de [ [0, 0] ] qui contient le nombre 0. Aussi choisit-on de construire un ensemble de type a ), c'est-à-dire contenant 0 . Il reste donc à trouver l'ensemble de numéro 0 parmi les ensembles à 0 élément de [ [0, 0] ], sachant qu'on lui ajoutera 0 . Un tel ensemble est l'ensemble vide.

• • -trois entiers naturels i, k et m vérifiant k ⩽ m et i ∈ [ [0, (m/k) − 1] ] et
  • -une matrice b suffisamment grande pour contenir les coefficients binomiaux (r/s) pour tout couple (r, s) de [ [0, m] ]^2.

ensemble_num_i(i: int, k: int, m: int, b: List[List[int]]) -> List[int]

couv_ens_binom(n: int, f: Parties) -> Tuple[int, List[int]]

4. Un algorithme glouton

• -On initialise l'ensemble C à l'ensemble vide.
• -Tant qu'il reste des éléments de X qui ne sont pas couverts par C :
• -on choisit dans F l'ensemble P ayant le plus d'éléments non encore couverts par C,
• -on ajoute P à C.

Algorithme 1 : Glouton
    Entrée : Une instance 
(X, J).
    Sortie : Calcule une couverture de 
X par 
F
    
E ← ∅; // La solution en cours de construction
    
R ← X; // 
R pour Reste à couvrir
    tant que 
R ≠ ∅ faire
        Choisir 
P ∈ F tel que 
|P ∩ R| soit maximal ;
        
e ← {P} ∪ e;
        
R ← R∖P;
    renvoyer 
C

4.1. Non optimalité de l'algorithme glouton

• -l'ensemble X_k = {0, 1, …, 2^(k + 1) − 3};
• -les parties E_k = {0, 2, …, 2^(k + 1) − 4} et O_k = {1, 3, …, 2^(k + 1) − 3}^o;
• -et finalement A_k = {2^k − 2, 2^k − 1, 2^k, …, 2^(k + 1) − 3}.

• Q.25 a) Donner les cardinaux des ensembles X_k, E_k, O_k et A_k.
  • b)Quel est le comportement de l'algorithme glouton sur l'instance ( X_k, {E_k, O_k, A_k} )?
• Q.26 a) Proposer un ensemble ℱ_k contenant au moins E_k, O_k, A_k, tel que l'algorithme glouton renvoie, sur l'instance (X_k, F_k), une solution de cardinal k. Expliciter le déroulé de l'algorithme sur l'instance proposée.
  • b)Conclure.
• %. E pour Even : pair en anglais, et O pour Odd_– : impair en anglais

4.2. Correction de l'algorithme glouton

5. Notion de solution partielle

• -sélectionne-t-on P_1 dans la solution?
• -Si oui, sélectionne-t-on P_2 dans la solution?
  • -Si oui, ...
  • -Si non, ...
• -Si non, sélectionne-t-on P_2 dans la solution?
  • -Si oui, ...
  • -Si non, ...

• - O représente l'ensemble des parties que l'on a sélectionnées dans la solution en construction,
• - n représente l'ensemble des parties que l'on a rejetées pour cette solution.

Partiel = List[Optional[bool]]

6. Graphe associé à une solution partielle

• - S est l'ensemble des éléments de X non couverts par O (autrement dit, S = X∖⋃_(P ∈ Θ)P ) et
• - A est l'ensemble des arêtes reliant deux sommets dès lors qu'ils sont contenus dans un même ensemble encore autorisé (autrement dit, {x, y} ∈ A si et seulement s'il existe P ∈ F∖n tel que x ∈ P et y ∈ P ).

Figure 3 - Graphe G_e associé à la solution partielle ({P_3}, {P_0}) de l'instance (X_e, ℱ_e)

Graph = Dict[int, Set[int]]

{0: {9, 6}, 2: {8, 11, 5}, 5: {8, 2, 11},
6: {0, 9}, 8: {2, 11, 5}, 9: {0, 6}, 11: {8, 2, 5}}

• Q.
  29 Définir une fonction fabrique_graphe prenant en arguments une instance (X, ℱ) du problème CouvEns et une solution partielle sol_partielle et calculant le graphe associé à cette solution partielle.

  fabrique_graphe(n: int, f: Parties, sol_partielle: Partiel) -> Graph
  

6.1. Utilisation du graphe pour la décomposition en sous-problèmes

• Q.
  30 Définir une fonction Python composantes_connexes prenant en argument un graphe et renvoyant la liste de ses composantes connexes. Une composante connexe sera représentée au moyen d'un ensemble.

  composantes_connexes(g: Graph) -> List[Set[int]]
  

  Dans le reste de cette sous-section, on fixe une instance (X, ℱ) du problème CouvEns. On considère le graphe G = (S, A) associé à la solution partielle vide (∅, ∅). Connaissant X = X_1 ∪ X_2 ∪ … ∪ X_p la décomposition en composantes connexes de G, on cherche à décomposer F en ℱ_1, 𝒥_2, …, 𝒥_p, de sorte que résoudre les instances ( X_i, ℱ_i ) permet de résoudre l'instance initiale.
• Q.31 a) Proposer une définition des ℱ_i.
  • b)Justifier succinctement que les ℱ_i sont disjoints.
  • c)Expliquer comment recomposer une solution C à l'instance ( X, F ) à partir des solutions C_i aux instances (X_i, F_i).
• Q.32 On s'intéresse ici à l'algorithme qui consiste à décomposer une instance comme proposé en Q. 31 et à résoudre chaque petite instance ( X_i, ℱ_i ) au moyen de l'algorithme par brute force naïf étudié précédemment. Comparer le nombre de cas que doit traiter l'algorithme par brute force appliqué directement sur l'instance initiale, au nombre de cas que doit traiter l'algorithme décrit ci-avant.

6.2. Utilisation du graphe pour l'obtention d'un minorant