CAPES informatique troisième concours 2026, épreuve écriteSujet

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/BIE 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 Section/option Epreuve E|B|F 6/2/0/0/E 1|0/1

  9/3/1/1

Capes NSI

Épreuve disciplinaire

Remarques générales sur le sujet

• -Les fonctions range, len et les fonctions de conversion de types.
• -Les méthodes append, pop et copy sur les listes.
• -Les méthodes keys, values et items sur les dictionnaires.

Partie 1. Ordonnancement de processus

Partie 1.1 - Questions préliminaires

• a)Donner deux commandes Linux permettant de connaître la liste des processus actifs sur le système ainsi que leurs états respectifs.
• b)Si on lance l'une de ces commandes, donner l'état affiché pour le processus déclenché par cette commande, et l'état majoritairement affiché pour les autres processus.

Partie 1.2 — Premiers algorithmes d'ordonnancement

• -executer_durant(self, temps: int) -> int
  Cette méthode prend en entrée le temps alloué pour l'exécution du processus, l'exécute durant ce temps autant que possible, sans que cela ne dépasse la durée restante du processus, et renvoie le temps réellement exécuté par ce processus.
• -est_termine(self) -> bool
  Cette méthode renvoie un booléen permettant de savoir si l'exécution du processus est terminée.

p1 = Processus(1, 7)
p2 = Processus(2, 3)
d_processus = {0: [p1], 4: [p2]}
p3 = Processus(3, 1)
p4 = Processus(4, 9)
a_ajouter = [(4, p3), (2, p4)]
d_processus[a_ajouter[0][0]] += a_ajouter[0][1]
d_processus[a_ajouter[1][0]] += a_ajouter[1][1]

• a)Corriger l'erreur et donner le contenu du dictionnaire après l'exécution de ce code corrigé.
• b)Modifier ces deux dernières lignes afin d'ajouter dans le dictionnaire d_processus l'ensemble des processus se trouvant dans la liste a_ajouter sans connaître le contenu de cette liste.

Premier arrivé, premier servi

Question 6.

• a)Donner une structure de données permettant d'implémenter cette politique. Discuter de la pertinence d'utiliser cette politique dans le cadre de l'ordonnancement des processus.
• b)En suivant cette politique, représenter graphiquement le fil d'exécution des différents processus définis dans le tableau 3, sur une échelle de temps dont l'unité est la milliseconde.
• c)Calculer la moyenne des temps totaux de chaque processus depuis leur arrivée jusqu'à leur terminaison.

• -prend en entrée le dictionnaire des processus défini à la question 5.
• -renvoie une liste dont les indices sont les nombres de millisecondes écoulées depuis le début, et chaque valeur est le numéro du processus qui a été exécuté à l'instant considéré. On considère que la clé de valeur 0 existe nécessairement dans le dictionnaire et que nous n'arriverons jamais dans une situation où un processus arrivera après la fin de l'exécution de tous les processus précédents. Il est possible de ne pas utiliser la structure trouvée à la question 6a pour implémenter cette fonction.

ordonnancement_paps({1: [Processus(1, 2)], 0: [Processus(2, 2)]})

    renvoie [2, 2, 1, 1]

sorted(iterable, /, *, key=None, reverse=False)
    Renvoie une nouvelle liste triée depuis les éléments d'iterable.

Tourniquet

• a)Dans cette question, nous considérons utiliser la mémoire cache du processeur pour l'ordonnancement. Dans le cas où un nouveau processus arrive à la fin d'un quantum et que le processus venant de s'exécuter n'est pas terminé, justifier qu'il est préférable de placer en queue de file d'abord le processus venant de s'interrompre plutôt que celui venant d'arriver.
• b)On suppose que la stratégie de placement décrite à la question 8a est mise en œuvre. En suivant l'algorithme du tourniquet pour un quantum de 1ms, représenter graphiquement le fil d'exécution des différents processus définis dans le tableau 3, sur une échelle de temps dont l'unité est la milliseconde.
• c)Calculer la moyenne des temps totaux de chaque processus depuis leur arrivée jusqu'à leur terminaison.

• -elle prend en entrée le dictionnaire des processus défini à la question 5.
• -elle renvoie une liste dont les indices sont les nombres de millisecondes écoulées depuis le début, et chaque valeur est le numéro du processus qui a été exécuté à l'instant considéré.

def ordonnancement_tourniquet(d_processus: dict[int, list[Processus]])
                -> list[int]:
    ordonnancement = []
    file = File()
    for processus in ...:
        file.ajouter(processus)
    t = 0
    while ...:
        processus = file.retirer()
        ordonnancement += [...] * processus.executer_durant(1)
        if not ...:
            file.ajouter(processus)
        t += 1
        if t in d_processus.keys():
            for processus in ...:
                file.ajouter(processus)
    return ordonnancement

• a)Compléter les instructions manquantes de cette fonction. Vous pouvez ne recopier que les 5 lignes à compléter, à condition de reporter leur numéro.
• b)Donner sans la justifier la complexité de la fonction complétée à la question a, puis démontrer sa correction totale.
• c)Améliorer la fonction en y ajoutant un paramètre entier quantum définissant le quantum à appliquer à chaque ajout de processus dans la liste finale. Attention à bien prendre en compte le cas où un nouveau processus arrive pendant l'exécution d'un autre processus. Recopier entièrement la fonction.

• a)L'exécution des fonctions des questions 7 et 10 engendre une modification des durées d'exécution des processus. Sans l'implémenter, proposer un attribut ou une méthode à ajouter dans la classe Processus afin de conserver les durées initiales des processus au sein du dictionnaire.
• b)Définir en Python la fonction : moyenne_temps_processus(d_processus: dict[int, list[Processus]], ordonnancement: list[int]) -> float

• • -prend en entrées :
    • -le dictionnaire des processus défini à la question 5.
    • -une liste telle que celles renvoyées par les questions 7 et 10.
  • -renvoie la moyenne des temps d'exécution de chaque processus.

Partie 1.3 — Prise en compte des priorités entre les processus

Priorités exclusives

• a)En suivant cette politique, représenter graphiquement le fil d'exécution des différents processus définis dans le tableau 4, sur une échelle de temps dont l'unité est la milliseconde.
• b)Que remarquez-vous pour le processus n°2? Est-ce raisonnable?

Question 14.

• a)Définir en Python la fonction :
  ordonnancement_termine(l_processus: list[Processus]) -> bool Cette fonction :
  • -prend en entrée une liste d'objets de la classe Processus.
  • -renvoie False s'il reste au moins un processus à exécuter, True sinon.
• b)Définir en Python la fonction :
  priorite_processus(processus: Processus) -> int Cette fonction :
  • -prend en entrée un objet de la classe Processus.
  • -renvoie la valeur de son attribut priorite.

• -elle prend en entrée le dictionnaire des processus défini à la question 5.
• -elle renvoie une liste dont les indices sont les nombres de millisecondes écoulées depuis le début, et chaque valeur est le numéro du processus qui a été exécuté à l'instant considéré.

def ordonnancement_priorite(d_processus: dict[int, list[Processus]])
        -> list[int]:
    ordonnancement = []
    l_processus = d_processus[0].copy()
    t = 0
    while ordonnancement_termine(l_processus):
        l_processus.sort(key=None, reverse=True)
        processus = l_processus[0]
        processus.executer_durant (1)
        ordonnancement.append(processus.pid)
        if processus.est_termine():
            l_processus.pop()
        t += 1
        if t in d_processus.keys():
            l_processus += d_processus[t]
    return ordonnancement

sort(*, key=None, reverse=False)
    Cette méthode trie la liste sur place, en utilisant uniquement des
    comparaisons < entre les éléments. [...]
    sort() accepte deux arguments qui ne peuvent être fournis que nommés :
        - key spécifie une fonction d'un argument utilisée pour extraire une
        clé de comparaison de chaque élément de la liste. [...]
        - reverse, une valeur booléenne. Si elle est True, la liste d'éléments
        est triée comme si toutes les comparaisons étaient inversées.

Ordonnancement par tirage au sort

somme_priorites(l_processus: list[Processus]) -> int

• -prend en entrée une liste d'objets de la classe Processus.
• -renvoie la somme des priorités des processus de cette liste.

• -elle prend en entrée le dictionnaire des processus défini à la question 5.
• -elle renvoie une liste dont les indices sont les nombres de millisecondes écoulées depuis le début, et chaque valeur est le numéro du processus qui a été exécuté à l'instant considéré.

from random import randint
def ordonnancement_au_sort(d_processus: dict[int, list[Processus]])
            -> list[int]:
    ordonnancement = []
    l_processus = d_processus[0].copy()
    t = 0
    while not ordonnancement_termine(l_processus):
        rand = randint(...)
        cumul_priorites = 0
        i = 0
        processus = None
        while processus is None:
            cumul_priorites += priorite_processus(...)
            if rand <= cumul_priorites:
                ...
            i += 1
        processus.executer_durant(1)
        ordonnancement.append(processus.pid)
        if processus.est_termine():
            l_processus.pop(...)
        t += 1
        if t in d_processus.keys():
            l_processus += d_processus[t]
    return ordonnancement

random.randint(a, b)
Renvoie un entier aléatoire N tel que a <= N <= b.

Partie 1.4 - Les tas binaires

• -Un arbre binaire complet : tous les niveaux de l'arbre binaire sauf le dernier doivent être totalement remplis et si le dernier ne l'est pas totalement, alors il doit être rempli de gauche à droite.
• -Un tas : la clé de chaque nœud doit être supérieure ou égale aux clés de chacun de ses fils.

Arbre 1

Arbre 2

Arbre 3

Arbre 4

• -La racine se situe à l'indice 0
• -Étant donné un nœud à l'indice i, son fils gauche est à l'indice 2i + 1 et son fils droit à l'indice 2i + 2
• -Étant donné un nœud à l'indice i > 0, son père est à l'indice (i − 1)/2 (arrondi à l'entier inférieur).

Figure 1 - Liste implémentant un tas binaire de 7 nœuds

• a)En suivant cette implémentation, représenter la liste du tas binaire de la question 18 .
• b)À quel parcours de l'arbre correspond l'ordre des valeurs de la liste ?

• -On insère x à la prochaine position libre, soit la position libre la plus à gauche possible sur le dernier niveau ;
• -Puis, tant que x n'est pas la racine de l'arbre et que x est strictement supérieur à son père, on échange les positions de x et de son père.

• a)En dessinant l'arbre à chaque étape de l'algorithme, l'appliquer en insérant la valeur 50 dans le tas binaire de la question 18.
• b)De même, donner l'état de la liste à chaque étape de l'algorithme lors de l'insertion de la valeur 50.

• a)Définir en Python la fonction récursive :
  percolation_haut(tas: list[int], i: int) -> None
  Cette fonction :
  • -prend en entrées :
    • -un tas binaire sous forme de liste Python.
    • -l'indice de la valeur à remonter dans l'arbre.
  • -effectue la deuxième partie de l'algorithme d'insertion dans un tas binaire, c'est-à-dire les échanges successifs de x et de son père.

• b)
  Définir en Python la fonction :

  insertion_tas_binaire(tas: list[int], valeur: int) -> None
  

  Cette fonction :
  • -prend en entrées :
    • -un tas binaire sous forme de liste Python.
    • -une valeur entière.
  • -insère la valeur au bon endroit de la liste en appliquant l'algorithme d'insertion dans un tas binaire.

• a)Donner en justifiant la complexité de la fonction insertion_tas_binaire.
• b)Démontrer la correction totale de la fonction percolation_haut, puis en déduire celle de insertion_tas_binaire.

• -On déplace à la place de la racine le nœud qui était en dernière position de l'arbre, que l'on note x;
• -Puis, tant que x n'est pas une feuille de l'arbre et que x est strictement inférieur à son fils de plus grande valeur, on échange les positions de x et de son fils de plus grande valeur.

• a)En dessinant l'arbre à chaque étape de l'algorithme, l'appliquer en supprimant la racine du tas binaire de la question 18.
• b)De même, donner l'état de la liste à chaque étape de l'algorithme lors de la suppression de la racine.

• a)
  Définir en Python la fonction récursive :

  percolation_bas(tas: list[int], i: int) -> None
  

  Cette fonction :
  • -prend en entrées :
    • -un tas binaire sous forme de liste Python qui vérifie la propriété de tas max sauf éventuellement en un nœud dont la valeur est inférieure à celle de son éventuel père, mais n'est pas nécessairement supérieure à celle de ces éventuels enfants.
    • -l'indice i du nœud x éventuellement problématique qu'il faut alors descendre.
  • -effectue la deuxième partie de l'algorithme de suppression de la racine dans un tas binaire, c'est-à-dire les échanges successifs de x et de son fils de plus grande valeur.

• b)Définir en Python la fonction :
  sup_racine_tas_binaire(tas: list[int]) -> int|None
  Cette fonction :
  • -prend en entrée un tas binaire sous forme de liste Python.
  • -supprime la racine de la liste en appliquant l'algorithme de suppression de la racine dans un tas binaire.
  • -renvoie la racine ainsi supprimée, ou None si le tas est vide.

• a)Donner en justifiant la complexité de la fonction sup_racine_tas_binaire.
• b)Démontrer la correction totale de la fonction percolation_bas, puis en déduire celle de la fonction sup_racine_tas_binaire.

Partie 2. Gestion des index des bases de données

Partie 2.1 - Niveau logique : utilisation d'un SGBD

• -Film(id : int, titre : text, année : int, durée : int, genre : text, pays : text)
• -Personne(id : int, nom : text, prénom : text)
• -Réalise(#film_id : int, #personne_id : int)

• a)créer la relation Réalise. On suppose que les autres relations sont créées. Votre réponse doit inclure la définition de la clé primaire et des clés étrangères ;
• b)ajouter à la relation Film le film de genre documentaire réalisé en France en 2025, d'une durée de 130 minutes et d'identifiant 128 dont le titre est "Le sujet";
• c)remplacer dans la relation Personne le prénom de la réalisatrice 64 par Alyssa;
• d)afficher les titres et les durées des films produits entre les années 2000 et 2020 (incluses) réalisés par la personne d'identifiant 32 ;
• e)afficher la durée moyenne des films réalisés par Quentin Tarantino.

Partie 2.2 - Hachage de données

Index et tables de hachage

Fonction de hachage

def h(x, N):
    return hash(x) % N

• b)Indiquer l'intérêt d'une telle fonction dans le contexte des tables de hachage.

Hachage de chaînes de caractères

• a)Donner le résultat de la fonction de hachage d'addition des valeurs correspondantes à chaque caractère pour les mots suivants :
  • -"isn"
  • -"nids"
  • -"nsi"
• b)Que remarquez-vous? Pourquoi?

• a)Appliquer ce correctif sur les chaînes de caractères de la question 33 en donnant leur résultat avec la nouvelle fonction de hachage présentée ci-dessus.
• b)Définir en Python la fonction :
  somme_caracteres(chaine: str) -> int
  Cette fonction :
  • -prend en entrée une chaîne de caractères.
  • -renvoie la somme des représentations décimales de chaque caractère de la chaîne, pondérée par les positions non nulles de chaque caractère.

ord(c)
    Renvoie le nombre entier représentant le code [...] du caractère
    représenté par la chaîne donnée. Par exemple, ord('a') renvoie le
    nombre entier 97.
chr(i)
    Renvoie la chaîne représentant un caractère dont le code de caractère
    [...] est le nombre entier i. Par exemple, chr(97) renvoie la chaîne
    de caractères 'a'.

Partie 2.3 - Modélisation du hachage des index en Python

Figure 2 - Exemple de structure de table de hachage linéaire indexant l'attribut titre

• -l'alvéole 00 pointe vers une liste chaînée contenant un unique bloc et l'enregistrement 0000 ;
• -l'alvéole 01 pointe vers une liste chaînée contenant deux blocs et les enregistrements 1011, 0101 et 0001;
• -l'alvéole 10 pointe vers une liste chaînée contenant un unique bloc et les enregistrements 1010 et 0110.

Figure 3 - Exemple de répertoire pointant vers des blocs chaînés

• -capacite: int : nombre maximum d'enregistrements que le bloc peut contenir.
• -enregistrements: list[Enregistrement] : séquence d'enregistrements. Initialement la séquence est vide et vaudra [].
• -suivant: None | Bloc : lien vers le bloc suivant auquel il est éventuellement chaîné. Lors de sa création, ce lien est vide et vaudra None.

CAPACITE_MAX = 2
blocs = [Bloc(CAPACITE_MAX) for _ in range(3)]
blocs[0].suivant = Bloc(CAPACITE_MAX)
blocs[0].ajouter('110')
blocs[0].ajouter('010')
blocs[0].ajouter('000')
blocs[1].ajouter('001')
assert blocs[2].capacite == ...
assert blocs[0].enregistrements[1] == ...
assert blocs[1].suivant == ...
assert len(blocs[0].enregistrements) == ...
assert len(blocs) == ...

• a)Le constructeur de la classe Bloc.
• b)La méthode récursive taille.
• c)La méthode récursive ajouter.

• a)Justifier la correction partielle de la méthode taille.
• b)Justifier la terminaison de la méthode ajouter.

Partie 2.4 - Tables de hachage linéaires

def taux(repertoire: list[Bloc]) -> float:
    n_enregistrements = 0
    for i in range(len(repertoire)):
        n_enregistrements += repertoire[i].taille()
    n_total = len(repertoire) * CAPACITE_MAX
    return n_enregistrements/n_total

• -qui ne contient initialement aucun enregistrement et qui se remplit;
• -qui manipule des blocs de capacité maximale 2 ;
• -qui a pour constante N = 2 (nombre initial d'alvéoles) et pour variable p = 00 (marqueur qui identifie la première alvéole et qui va évoluer au fur et à mesure du remplissage afin de marquer successivement les alvéoles).

Figure 4 - Exemple de hachage linéaire pour N = 2

1ère série d'éclatement :

Fin de la 1ère série d'éclatement

Les fonctions de hachages

Insertion avec un hachage linéaire

• -la fonction de hachage h_i.
• -la fonction eclater qui modifie la structure en éclatant un bloc donné et en répartissant les enregistrements dans les bonnes alvéoles.
• -et pour finir la fonction inserer qui insère dans la structure un nouvel enregistrement.

• a)h_i(i, x) : en utilisant la fonction hash de la bibliothèque standard et en confondant pour simplifier l'enregistrement x et sa clé;
• b)eclater(table, i, p) : en utilisant la classe Bloc définie dans la sous-partie 2.3 et dont l'interface est disponible dans le tableau 7.

• 1.L'indice de l'alvéole associée à la clé de l'enregistrement est déterminé par la fonction de hachage. Pour cela l'indice est calculé par h_i(x) et si l'indice obtenu est inférieur au marqueur p alors il est recalculé par la fonction h_(i + 1)(x).
• 2.L'enregistrement est ajouté à la structure.
• 3.Si le taux de remplissage de la table est supérieur ou égal au seuil, alors l'alvéole p éclate et p est mis à jour.
• 4.Suite à l'éventuel éclatement, si p marque l'alvéole 2^i, c'est que la taille du répertoire a doublé durant cette série d'éclatement. C'est donc la fin de la série i. La variable i est incrémentée et le marqueur p est réinitialisé à l'indice de la première alvéole.
• 5.Enfin, pour transmettre l'état de la structure les valeurs i et p sont renvoyées.