CAPES informatique externe 2024, é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

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

  6

  0

  0

  1

  0

  1

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

  9/3/1/1

Épreuve disciplinaire

Préliminaires

Notes de programmation Python

• -création d'une liste li de taille n dont tous les éléments ont pour valeur v : li = [v]∗n.
• -renvoi de la taille d'une liste li : len(li).
• -insertion (avec décalage à droite) à un indice i dans une liste li:li.insert(i,v).
• -ajout de la valeur v en fin de liste : li.append(v).
• -position du premier élément de la liste égal à v (en comptant à partir de 0 ) : li.index(v).
• -énumération des éléments d'une liste, dans l'ordre : for x in li.
• -construction de listes par compréhension : [x**2 for x in li] est une nouvelle liste construite en mettant au carré chaque élément de la liste li.
• -les fonctions permettant de sélectionner des tranches (slices) : li[start:end] sélectionne la sousliste d'indices de start à end-1.

Notes de complexité

Vocabulaire d'arbres

• -les arbres sont des graphes acycliques connectés, enracinés et étiquetés;
• -un nœud sans enfant est dénommé feuille;
• -on appelle la longueur d'un chemin le nombre de nœuds de ce chemin, extrémités inclues;
• -on appelle arité d'un nœud le nombre d'enfants de ce nœud ; par extension on appelle arité d'un arbre le maximum de l'arité de ses nœuds. Un arbre binaire est d'arité 2.
• -on appelle distance entre deux nœuds A et B la valeur l − 1, où l désigne la longueur du chemin (A, B);
• -on appelle niveau d'un nœud d'un arbre la distance de ce nœud à la racine de l'arbre (la racine d'un arbre est de niveau 0);
• -la hauteur d'un arbre est la longueur du plus grand chemin de la racine à une feuille (en nombre de nœuds);
• -un arbre est équilibré si tous les chemins de la racine aux feuilles ont la même longueur;

Rappel mathématique

1 Arbres Binaires de Recherche

Figure 1 - Un arbre binaire de recherche

class Noeud:
    """
    Noeud d'un arbre
    """
    def __init__(self, clef:int, gauche= None, droite= None):
        """ Initialisation, noeud non vide"""
        self.gauche = gauche
        self.droite = droite
        self.clef = clef

mon_arbre = Noeud(42, Noeud(-15, Noeud(-6000), Noeud(12)), Noeud(177, Noeud(70), None));

Question #1

recherche(root : Noeud, k : int)->bool

Question #2

Question #3

Question #4

def est_ABR_1(self):
"""
renvoie True ssi l’arbre est un ABR
"""
temp = True
val = self.clef
if self.gauche is not None:
    temp = self.gauche.clef < val and self.gauche.est_ABR_1()
if self.droite is not None:
    temp = temp and self.droite.clef > val and self.droite.est_ABR_1()
    return temp

• -Dans le sous-arbre de gauche, le maximum des clefs est inférieur ou égal à k.
• -Dans le sous-arbre de droite, le minimum des clefs est supérieur ou égal à k.

Question #5

Question #6

Question #7

2 B-trees

• « En informatique, un arbre B (appelé aussi B-arbre par analogie au terme anglais « Btree ») est une structure de données en arbre équilibré. Les arbres B sont principalement mis en œuvre dans les mécanismes de gestion de bases de données et de systèmes de fichiers. Ils stockent les données sous une forme triée et permettent une exécution des opérations d'insertion et de suppression en temps toujours logarithmique.
  Le principe est de permettre aux nœuds parents de posséder plus de deux nœuds enfants : c'est une généralisation de la notion d'arbre binaire de recherche. Ce principe minimise la taille de l'arbre et réduit le nombre d'opérations d'équilibrage. De plus un B-tree grandit à partir de la racine, contrairement à un arbre binaire de recherche qui croît à partir des feuilles. »

2.1 Définition, algorithmes élémentaires

• -(S1) Tous les chemins de la racine à une feuille ont la même longueur (le même nombre de nœuds), appelée hauteur de l'arbre et dénotée par h.
• -(S2) La racine est une feuille ou bien a au moins 2 enfants.
• -(S3) Chaque nœud qui n'est ni racine ni feuille possède au moins t + 1 enfants.
• -(S4) Chaque nœud a au plus 2t + 1 enfants.
• -(C1) Les nœuds contiennent des clefs : la racine contient de 1 à 2t clefs; et les autres nœuds, entre t et 2t clefs.
• -(C2) Dans chaque nœud, les éléments sont stockés par ordre croissant.
• -(C3) Chaque nœud qui contient ℓ clefs (et qui n'est pas une feuille) a ℓ + 1 enfants.
• -(C4) Considérons un nœud P contenant ℓ clefs x_0…x_(ℓ − 1). Soient P_0, …P_ℓ ses enfants, et K(P_i)_(0 ⩽ i ⩽ ℓ) l'ensemble des clefs du sous-arbre dont la racine est P_i. Alors :
  • - ∀y ∈ K(P_0), y ⩽ x_0;
  • - ∀1 ⩽ i ⩽ ℓ − 1, ∀y ∈ K(P_i), x_(i − 1) ⩽ y ⩽ x_i;
  • - ∀y ∈ K(P_ℓ), x_(ℓ − 1) ⩽ y;

Figure 2 - Un exemple de B-tree d'ordre 2. Les nœuds contiennent un ensemble de clefs, triées par ordre croissant.

Figure 3 - Quelques arbres.

class BTreeNode:
    def __init__(self, t:int, f=False):
        self.feuille = f # True si le noeud est une feuille
        self.clefs = [] # Les valeurs des clefs du noeud
        self.enfants = [] # les enfants du noeud (qui sont des BTreeNode)
        self.ordre = t # l'ordre du noeud
        self.n = 0 # nombre de clefs du noeud

class BTree:
    def __init__(self, t):
        self.root = BTreeNode(t,True)
        self.ordre = t # l'ordre du btree

• -Rien ne garantit les invariants de la définition d'un B-tree. Il faut donc bien faire attention à les maintenir.
• -La numérotation des enfants et celle des clefs commencent à 0.

Niveau 0 2:2 5
Niveau 1 2:0 1
Niveau 1 2:3 4
Niveau 1 4:6 7 8 9

2.2 Recherche dans un B-tree

Figure 4 - Exemple de B-tree (d'ordre 2) pour la recherche

2.3 Insertion dans un B-tree

Figure 5 - Illustration (partielle) de l'insertion de 8 dans le nœud y avec « split » : lors de l'insertion, le nœud y possède temporairement 5 clefs, ce qui n'est pas permis pour un B-tree d'ordre 2. La procédure de découpage ("split") va donc créer le nouveau nœud z et éjecter la valeur 8. Cette valeur sera retournée au parent à la fin de l'appel récursif d'insertion.

Figure 6 - B-tree résultant de l'insertion de la clef 9 dans le B-tree de la Figure 4

def insert(self, k): # Version bottom-up de l'insertion dans un Btree
    val, newnode = self.root.insert(k)
    if newnode is not None:
        self.root = self.root.make_new_root(val, newnode)

3 Application : Indexation dans les Bases de Données

3.1 Schéma relationnel et requêtes

• R1 : Rechercher toutes les informations décrites dans la table 'Characters', concernant le personnage désigné par l'identifiant '2musician-rj'.
• R2 : Rechercher le nombre de mots prononcés (attribut SpeechCount) par le personnage désigné par l'identifiant '2musician-rj'.
• R3 : Lister tous les titres longs des oeuvres de Shakespeare écrites entre 1589 et 1600.
• R4 : Lister l'ensemble des titres longs des oeuvres où apparaissent des musiciennes ou des musiciens (dont l'attribut CharName contient Musician).

3.2 Stockage des enregistrements

CREATE TABLE IF NOT EXISTS 'Characters' (
    'CharID' varchar(50) NOT NULL DEFAULT '',
    'CharName' varchar(75) NOT NULL DEFAULT '',
    'Abbrev' varchar(10) NOT NULL DEFAULT '',
    'WorkID' varchar(50) NOT NULL DEFAULT '',
    'SpeechCount' mediumint unsigned NOT NULL DEFAULT 0,
    PRIMARY KEY ('CharID')
) DEFAULT CHARSET=latin1;

3.3 Recherche dans une table

• -Seules les feuilles contiennent des couples (clef/ numéro de bloc) : les clefs seront les identifiants
• -Les nœuds qui ne sont pas des feuilles ne contiennent que des clefs (et un lien vers leurs enfants). Ces clefs sont des recopies de certaines clefs apparaissant dans les feuilles ; elles servent de balises lors des parcours du B-tree, afin d'orienter la recherche vers le sous-arbre adéquat.

• 1.Un B-tree d'ordre 3 et de taille 8 et
• 2.Un B-tree d'ordre 6 et de hauteur 6 permettent de stocker l'index de T.