CAPES informatique externe 2022, épreuve 2Sujet et rapport du jury

CONCOURS EXTERNE
CAPES ET CAFEP/CAPES CORRESPONDANTS

• -Si vous repérez ce qui vous semble être une erreur d'énoncé, vous devez le signaler très lisiblement sur votre copie, en proposer la correction et poursuivre l'épreuve en conséquence.
• -De même, si cela vous conduit à formuler une ou plusieurs hypothèses, vous devez la (ou les) mentionner explicitement.

Épreuve disciplinaire appliquée

Problème 1 - Gestion des données

1 Introduction à la problématique des données

• 1.Citer un exemple que vous pourriez utiliser devant les élèves pour illustrer l'importance de l'exploitation des données dans leur vie quotidienne. Vous justifierez brièvement votre choix.
• 2.Expliquer, en quelques lignes et comme vous l'expliqueriez à vos élèves, pourquoi le stockage de données sur le << cloud >> (donc dans les datacenters) a bien un impact négatif sur l'environnement. Vous donnerez deux impacts différents sur l'environnement.
• 3.Donner deux conseils concrets que vous pourriez donner à vos élèves pour limiter facilement l'impact de leurs données sur l'environnement.
• 4.Expliquer en quoi disposer de données massives (appelées aussi Big Data) peut être un avantage dans certains enjeux de société. Illustrer votre réponse avec un exemple que vous pourriez proposer à vos élèves.
• 5.Citer un danger (autre que l'impact sur l'environnement) qui est apparu ou peut apparaître avec les données massives. Vous expliquerez, comme vous l'expliqueriez à vos élèves, ce danger en quelques lignes.

2 Utilisation des fichiers csv

• 6.Définir la notion de descripteur d'objet.
• 7.Proposer une activité débranchée que vous pourriez réaliser en classe pour leur faire comprendre la notion de descripteur d'objet. Cette activité devra durer entre 30 min et 1h. On attend une description détaillée du déroulement de l'activité et de ses attendus.

• -Identifiant_capteur (entier) : identifiant unique du capteur.
• -Piece (texte) : pièce dans laquelle se trouve le capteur.
• -Num_mesure (entier) : numéro de la mesure de la journée pour le capteur (1 à minuit et s'incrémente à chaque mesure jusqu'à la fin de la journée).

• -Ouverture (booléen) : vaut True si la porte/fenêtre est ouverte et False sinon.
• -Presence (booléen) : vaut True si le capteur détecte un mouvement et False sinon.
• -Temperature (flottant) : indique la température mesurée à 0.1^∘C près.

• 8.Donner 3 questions que vous pourriez poser aux élèves pour les faire travailler, sur ordinateur, sur le traitement de données structurées, le but étant ici de leur faire découvrir les traitements possibles. Vous expliquerez à chaque fois brièvement l'intérêt de la question pour l'acquisition de compétence des élèves. Chaque question devra faire travailler les élèves sur une opération différente.

• -Donner la température minimale de la cuisine quand le capteur 3 indique la présence de quelqu'un.
• -Afficher toutes les températures de la maison triées de manière croissante.
• 9.Écrire, tel qu'un élève pourrait le faire, le programme permettant de répondre à ces questions à l'aide de la bibliothèque pandas.
• 10.Décrire la structure d'une activité de 1h30 sur machine permettant à vos élèves, qui n'ont jamais utilisé pandas, d'être capables de répondre à ces questions. On ne demande pas ici de rédiger complètement le document qui serait fourni aux élèves mais d'indiquer clairement l'organisation de l'activité en précisant notamment les questions posées aux élèves.

3 Traitement de données sous forme de tables

• 11.Présenter, tel que vous le feriez avec vos élèves, la différence entre le type dictionnaire et le type liste.
• 12.Expliquer brièvement comment les dictionnaires sont implémentés en Python.
• 13.Citer un exemple d'utilisation de dictionnaire pour illustrer votre cours sur les dictionnaires. Vous justifierez votre choix en expliquant notamment pourquoi l'exemple est pertinent pour ce cours de première. Qu'est-ce qui pourrait être un mauvais exemple d'un point de vue pédagogique et pourquoi?

• -le numéro de sécurité social du contaminé (descripteur : num_SS ; type : entier),
• -son âge (descripteur : age ; type : entier),
• -le jour du test positif (descripteur : jour_test ; type : entier),
• -le mois du test positif (descripteur : mois_test ; type : entier),
• -son sexe (descripteur : sexe; type : caractère),
• -s'il a été vacciné ou non (descripteur : vaccine ; type : booléen).

• -l'identifiant de l'enregistrement (descripteur : id_enregistrement ; type : entier),
• -l'identifiant du restaurant (descripteur : id_restaurant ; type : entier),
• -le jour du repas (descripteur : jour_repas ; type : entier),
• -le mois du repas (descripteur : mois_repas ; type : entier),

• -la tranche horaire du repas (descripteur : tranche_horaire ; type : entier),
• -le numéro de la table (descripteur : num_table; type : entier),
• -le numéro de sécurité social du client (descripteur : num_SS ; type : entier).

• 14.Écrire le programme Python commenté qui permettrait à vos élèves de récupérer sous forme de liste de dictionnaires, nommée positifs, les informations contenues dans le fichier « positifs.csv ». Chaque élément de la liste est un dictionnaire comprenant les valeurs d'une ligne de la table et dont les clés sont les descripteurs de la table. On utilisera pour cela notamment la fonction readlines.
• 15.Quels sont pour vous les points importants à aborder avec vos élèves et/ou ceux qui risquent de leur poser problème lorsque vous abordez pour la première fois le programme de la question 14 avec vos élèves?

• 16.Vous rédigez maintenant une partie de cet exercice.
  • (a)Proposer 3 questions de difficulté croissante (dont au moins une nécessitant la fusion des tables) où les élèves doivent rédiger des programmes en Python. On suppose ici que les listes de dictionnaires positifs et restaurants sont déjà construites.
  • (b)Proposer pour chaque question une correction. Décrire brièvement les points sur lesquels vous serez vigilant lors de la correction de ces questions.

4 Utilisation des bases de données

• 17.Expliquer tel que vous le feriez avec vos élèves l'intérêt des bases de données par rapport à ce que les élèves ont fait en première (avec les tables sous forme de fichiers csv).

• 18.Voici l'exercice que vous avez donné aux élèves pour travailler sur les requêtes en SQL :
  • (a)Écrire la requête SQL permettant d'ajouter le film suivant à la base de données : « Wicked » un film réalisé aux USA et sorti en 2021. Son identifiant est 20356.
  • (b)Écrire la requête SQL permettant d'indiquer que la facture d'identifiant 2564 a été payée.
  • (c)Écrire la requête SQL permettant d'obtenir la liste des identifiants de facturation qui sont en attente et qui ont un montant strictement supérieur à 5 euros.

• • (d)Écrire la requête SQL permettant d'obtenir la liste, par ordre alphabétique, des pays d'origine des films de la plateforme de l'année 2015. Chaque pays ne sera bien sûr indiqué qu'une seule fois.
  • (e)Écrire la requête SQL permettant d'obtenir la liste des noms, prénoms et adresses mails des clients ayant une facturation en attente.
  • (f)Écrire la requête permettant de déterminer le temps moyen de visionnage du film Titanic.
  • (g)Écrire la requête permettant de donner la liste des identifiants des clients qui ont regardé Titanic plus longtemps que la moyenne des utilisateurs.

• 19.Des élèves peinent à rédiger la requête d'interrogation de données de la question 18(e). Quelle aide leur proposezvous?
• 20.Donner un barème pour la correction de la question 18(g) Vous détaillerez les différentes compétences qu'il vous semble important d'évaluer.
• 21.Proposer, à l'aide de cette base de données, 3 questions qui vous permettraient de valider les compétences de vos élèves sur les requêtes SQL lors d'une interrogation. Vous justifierez, pour chaque question, en quoi elle est pédagogiquement intéressante en indiquant notamment la (ou les) compétence(s) évaluée(s).

Problème 2 - Algorithmes de tri

5 Tris naïfs

5.1 Tri par insertion

• 22.Quatre élèves de première NSI vous ont rendu leur implémentation du tri par insertion. Pour chaque production, rédiger une appréciation concise, donnant les erreurs éventuelles et les améliorations possibles afin que les élèves puissent se corriger par elles-mêmes.

def tri_eleve1(t) :
    n = len(t)
    for i in range(n) :
        for k in range(i,1,-1) :
            if t[k]<t[k-1] :
                t[k]=t[k-1]
                t[k-1]=t[k]
def tri_eleve3(t):
    n = len(t)
    def insere_eleve3(i) :
        k = i
        while t[k]<t[k-1] :
            t[k],t[k-1]=t[k-1],t[k]
            k = k-1
    for i in range(n) :
        t = insere_eleve3(i)

        def insere_eleve2(t,k):
def insere_eleve2(t,k):
        if t[k]<t[k-1] :
            t[k],t[k-1]=t[k-1],t[k]
            insere_eleve2(t,k-1)
    def tri_eleve2(t,i=0) :
        insere_eleve2(t,i)
        tri_eleve2(t,i+1)
    def tri_eleve4(t) :
        n = len(t)
        i = 0
        while i < n :
            k = i
            while k > 0 or t[k]<t[k-1] :
                t[k],t[k-1]=t[k-1],t[k]
            i = i + 1

23. Pour que chacune puisse apprendre des erreurs des autres, rédiger une synthèse succincte à destination des élèves de première NSI dont vous venez de corriger les productions. L'idée est de s'appuyer sur les erreurs observées pour faire des rappels généraux sur les points clés à vérifier dans un programme afin qu'il fonctionne correctement et efficacement.
24. Une élève vous demande pourquoi on n'utilise pas un algorithme de dichotomie pour améliorer la complexité de l'insertion des éléments. Que lui répondez-vous?

5.2 Tri par sélection

25. On rappelle succinctement le fonctionnement du tri par sélection au travers du pseudo-code suivant :

def tri_sel(t) :
    pour k de 0 à n-1
        sélectionner l’indice iO du minimum des éléments entre les indices de k à n-1
        échanger t[k] et t[i0]

• • -découvrir cet algorithme,
  • -l'implémenter,
  • -prouver sa correction,
  • -estimer sa complexité en nombre de comparaisons.

6 Tris par fusion

6.1 Tri partition-fusion

def fus1(t1,t2):
n1,n2 = len(t1),len(t2)
if n1 = 0 : return t2
if n2 = 0 : return t1
if t1[0]<t2[0] :
    return [t1[0]]+fus1(t1[1:],t2)
else :
    return [t2[0]]+fus1(t1,t2[1:])

def tri_f1(t):
    if len(t) <2 :
        return t
    else :
        m = len(t)//2
        return fus1(tri_f1(t[:m]),tri_f1(t[m:]))

def fus2(t1,t2):
n1,n2 = len(t1),len(t2)
while i1 < n1 and i2 < n2 :
    if t1[i1]<t2[i2] :
    res.append(t1[i1])
    i1 = i1 + 1
    else :
        res.append(t2[i2])
        i2 = i2 + 1
if i1 == n1 : res.extend(t2[i2:])
else : res.extend(t1[i1:])
return res

def tri_f2(t):
    if len(t) <2 :
        return t
    else :
        m = len(t)//2
        t1,t2 = t[:m],t[m:]
        tri_f2(t1)
        tri_f2(t2)
    return fus2(t1,t2)

def fus3(t,g,m,d):
    aux = []
    i1,i2 = g,m
    while i1<m and i2<d :
        if t[i1]<t[i2] :
        aux.append(t[i1])
        i1 = i1 + 1
        else :
            aux.append(t[i2])
            i2 = i2 + 1
    if i1<m : aux.extend(t[i1:m])
    for i in range(len(aux)):
        t[i+g] = aux[i]

    def tri_f3(t):
        def aux(g,d):
            if g < d-1 :
            m = (g+d)//2
            aux (g,m)
            aux (m,d)
            fus3(t,g,m,d)
        aux(0,len(t))

• 27.Élaborer un barème détaillé pour cette question.
• 28.Corriger ces trois productions, c'est-à-dire donner la note détaillée selon le barème et l'appréciation associée pour chacune des productions d'élèves. Les corrections seront données directement sur les productions d'élèves fournies dans le document réponse 1 (Annexe E). Ce document réponse est à rendre avec votre copie.

6.2 Tri Timsort simplifié

def f1(l,a):
    i = a
    while i<len(l)-1 and l[i]<=l[i+1] :
        i += 1
    return i+1
def f2(1):
    i = 0
    res = [0]
    while i<len(l) :
        i = f1(l,i)
        res.append(i)
    return res
def f3(t, debut, milieu, fin) :
    i = debut
    j = milieu
    lt = []
    while i < milieu and j < fin :
        if t[i] < t[j] :
            lt.append(t[i])
            i += 1
        else :
            lt.append(t[j])
            j += 1
    for k in range (i, milieu) : lt.append(t[k])
    for k in range (debut, j) : t[k] = lt[k-debut]
def f4(t,rc):
    nrc = []
    i = 0
    n = len(rc)
    while i < n :
        nrc.append(rc[i])
        if i+2 < n :
            f3 (t, rc[i], rc[i+1], rc[i+2])
            i += 2
        else : i += 1
    return nrc
def f5(t):
    rc = f2(t)
    while len(rc) > 2 :
        rc = f4 (t, rc)

• 29.(a) Proposer des noms explicites pour ces fonctions.
  • (b)Présenter le fonctionnement général de ces fonctions tel que vous le feriez à vos élèves.
  • (c)Illustrer le principe de ce tri sur un ou plusieurs exemples pour que les élèves puissent l'implémenter par ellesmêmes.
• 30.Quelle est la complexité, dans le pire cas, en nombre de comparaisons de cet algorithme de tri ?

7 Tris sans comparaison

7.1 Tri par dénombrement

• -2 occurrences de 1
• -3 occurrences de 3
• -2 occurrences de 5
• -4 occurrences de 7

def compte_occu(t,elt):
    c = 0
    for x in t :
        if x == elt : c = c+1
    return c
def tri_den_el(t):
    occ = [0]*10000
    res = []
    for elt in range(10000):
        occ[elt] = compte_occu(t,elt)
        res = res + [elt]*occ[elt]
    return res

• 31.Lister les indications à lui donner pour qu'elle puisse répondre correctement à votre question.
• 32.Écrire, sans commenter, le programme que vous espérez qu'elle écrive.
• 33.La complexité temporelle de cet algorithme contredit-elle la borne de complexité admise en introduction de ce sujet? Pourquoi?
• 34.Cet algorithme de tri est-il toujours plus efficace, en termes de complexité temporelle, que le tri fusion dont la complexité temporelle est en O(nlogn) ? Justifier.

7.2 Tri par baquets

• -on travaille avec des baquets numérotés de 0 à 9 (ces baquets sont implémentés par une liste de 10 listes);
• -pour débuter, chaque élément de la liste initiale est placé dans le baquet numéroté par son chiffre des unités ;
• -à chaque étape, les éléments sont parcourus baquet par baquet en partant de l'indice 0 du baquet 0 et rangés à nouveau dans les baquets en utilisant le chiffre suivant;
• -l'algorithme est terminé lorsque tous les éléments sont dans le baquet 0.

• -au départ, les éléments sont rangés dans les baquets par chiffres des unités :
  [[6200], [7971, 6231, 6131], [1112, 3832], [1203, 1813, 6863], [], [8295, 1905], [8806, 2916], [], [538], [9449, 1749]]

• -puis on les place par chiffre des dizaines en préservant l'ordre sur les unités dans chaque baquet grâce à l'ordre de parcours des éléments :
  [[6200, 1203, 1905, 8806], [1112, 1813, 2916], [], [6231, 6131, 3832, 538], [9449, 1749], [], [6863], [7971], [], [8295]]
• -puis par chiffre des centaines en respectant l'ordre précédent dans chaque baquet :
  [[], [1112, 6131], [6200, 1203, 6231, 8295], [], [9449], [538], [], [1749], [8806, 1813, 3832, 6863], [1905, 2916, 7971]]
• -puis par chiffre des milliers :
  [[538], [1112, 1203, 1749, 1813, 1905], [2916], [3832], [], [], [6131, 6200, 6231, 6863], [7971], [8295, 8806], [9449]]
• -à la dernière étape, tous les éléments se retrouvent dans le baquet 0 :
  [[538, 1112, 1203, 1749, 1813, 1905, 2916, 3832, 6131, 6200, 6231, 6863, 7971, 8295, 8806, 9449], [], [], [], [], [], [], [], [], []]
• 35.Écrire une fonction Python ch qui prend en paramètre deux entiers et telle que l'appel ch(k,i) renvoie le i-ème chiffre de l'entier k. Par exemple, ch(1345, 2) = 4, ch(1345, 4) = 1 et ch(1345, 5) = 0. Cette fonction pourra être utilisée par vos élèves pour l'implémentation du tri par baquets.
• 36.
  Vous avez fourni une implémentation à trous de l'algorithme de tri par baquets à vos élèves. En particulier, la fonction Python tri_baquets prend en paramètre une liste t, applique le tri par baquets à t et renvoie une liste triée contenant les mêmes éléments que t.

  def etape(bacs1,bacs2,i):
      for b in bacs1 :
          for x in b :
              bacs2[...........].append(...........)
  def vider(bacs):
      for i in range(10):
          bacs[i] = ............
  def tri_baquets(t) :
      n = len(t)
      bacs1 = [[] for i in range(10)]
      bacs2 = [[] for i in range(10)]
      for x in t:
          bacs1[...........].append(...........)
      i = 2
      while len(bacs1[0]) != n :
          etape(bacs1,bacs2,i)
          bacs1,bacs2 = ............
          vider(............)
          i += 1
      return ............
  

  Compléter ce que vous attendez que les élèves écrivent dans les trous sans commenter. Vous compléterez cet algorithme à trous fourni dans le document réponse 2 (Annexe F ). Ce document réponse est à rendre avec votre copie.
• 37.Quelle est la complexité temporelle de ce tri ?
• 38.Dans quels cas utiliser cet algorithme plutôt que le tri par dénombrement ?
• 39.Cet algorithme de tri est-il toujours plus efficace, en termes de complexité temporelle, que le tri fusion dont la complexité temporelle est en O(nlogn) ?

A Extrait du fichier Donnees_capteurs_22_09_21.csv (ouvert dans un tableur)

B Description de fonctions utiles de la bibliothèque pandas

• -pandas.read_csv(nom,sep=...) prend en argument une chaîne contenant l'adresse du fichier csv à lire et un chaîne contenant le séparateur du fichier csv, et retourne une instance de type dataframe, initialisée avec l'ensemble des données présentes dans le fichier. Lors de la création du dataframe, un index est associé à chacune des lignes du fichier (en commençant à partir de 0).

• -df.loc(index_ligne,index_colonne) retourne, sous forme d'un objet de type dataframe, certaines lignes et colonnes du dataframe df. L'index des colonnes est le nom des colonnes dans le fichier csv, et l'index des lignes est l'index créé lors de l'initialisation du dataframe à la lecture du fichier.
  Par exemple, print(df.loc[0,'Temperature']) affichera la température de la 1ère ligne du fichier.
  Il est également possible d'effectuer des tests sur le contenu d'un dataframe.
  Par exemple, print(df['Piece']'Salon') affichera, sous forme de booléens, pour chaque ligne du fichier, si la pièce mentionnée est un salon.
  Ces deux techniques peuvent être conjointement utilisées pour filtrer des lignes à partir de tests.
  Par exemple, print(df.loc[df['Piece']'Salon', :]) affichera toutes les lignes qui concernent le salon.
  Il est possible de combiner plusieurs facteurs de filtrage en utilisant un "et" (&) ou un "ou" (|).
  Par exemple, print(df.loc[(df['Piece']'Salon')|(df['Piece']'Cuisine'), 'Presence']) affichera la colonne présence pour les lignes correspondant au salon ou à la cuisine.
• -Il est possible de retourner le maximum (méthode max), le minimum (méthode min) et la moyenne (méthode mean) d'une donnée d'une dataframe.
  Par exemple, print(df.loc[ :,'Temperature'].mean()) affichera la température moyenne mesurée sur l'ensemble des lignes du fichier.
• -Pour retourner le contenu trié d'un dataframe, on utilise la méthode dataframe.sort_values(column,ascending=…). column est une chaîne indiquant la colonne utilisée pour le tri. Si ascending vaut True (valeur par défaut), le tri est croissant, s'il vaut False, il est décroissant.
  Par exemple, df.sort_values(by=["Piece"], ascending=False) affiche les lignes du fichier triées par Piece dans l'ordre alphabétique inversé (en commençant par Z ).

num_SS;age;jour_test;mois_test;sexe;vaccine
1630580265006;58;2;7;H;True
2750846580156;46;2;7;F;False
1950412410023;26;3;7;H;False
2570235820132;64;3;7;F;False

id_enregistrement;id_restaurant;jour_repas;mois_repas;tranche_horaire;num_table;num_SS
1;324;30;6;2;5;1850659240032
2;324;30;6;2;5;2860372541115
3;796;1;7;1;8;1950412410023
4;796;1;7;1;8;1951012410056
5;796;1;7;1;8;1951232564031

INFORMATION AUX CANDIDATS

• Concours externe du CAPES de l'enseignement public :

• Concours externe du CAFEP/CAPES de l'enseignement privé :

Matière 9/3/1/2

Tous les documents réponses sont à rendre, même non complétés.

E Document Réponse 1 : Correction de trois productions d'élèves

def fus1(t1,t2):
n1,n2 = len(t1),len(t2)
if n1 = 0 : return t2
if n2 = 0 : return t1
if t1[0]<t2[0] :
    return [t1[0]]+fus1(t1[1:],t2)
else :
    return [t2[0]]+fus1(t1,t2[1:])

def tri_f1(t):
    if len(t) <2 :
        return t
    else :
        m = len(t)//2
        return fus1(tri_f1(t[:m]),tri_f1(t[m:]))

def fus2(t1,t2):
n1,n2 = len(t1),len(t2)
while i1 < n1 and i2 < n2 :
    if t1[i1]<t2[i2] :
        res.append(t1[i1])
        i1 = i1 + 1
    else :
        res.append(t2[i2])
        i2 = i2 + 1
if i1 == n1 : res.extend(t2[i2:])
else : res.extend(t1[i1:])
return res

def tri_f2(t):
    if len(t) <2 :
        return t
    else :
        m = len(t)//2
        t1,t2 = t[:m],t[m:]
        tri_f2(t1)
        tri_f2(t2)
    return fus2(t1,t2)

def fus3(t,g,m,d):
    aux = []
    i1,i2 = g,m
    while i1<m and i2<d :
        if t[i1]<t[i2] :
            aux.append(t[i1])
            i1 = i1 + 1
        else :
            aux.append(t[i2])
            i2 = i2 + 1
    if i1<m : aux.extend(t[i1:m])
    for i in range(len(aux)):
    t[i+g] = aux[i]

    def tri_f3(t):
        def aux(g,d):
            if g < d-1 :
            m = (g+d)//2
            aux (g,m)
            aux (m,d)
            fus3(t,g,m,d)
        aux(0,len(t))

F Document Réponse 2 : Algorithme de tri par baquets à trous à compléter

def etape(bacs1,bacs2,i):
    for b in bacs1 :
        for x in b :
            bacs2[...........].append(...........)
def vider(bacs):
    for i in range(10):
        bacs[i] = ............
def tri_baquets(t) :
    n = len(t)
    bacs1 = [[] for i in range(10)]
    bacs2 = [[] for i in range(10)]
    for x in t:
        bacs1[...........].append(...........)
    i = 2
    while len(bacs1[0]) != n :
        etape(bacs1,bacs2,i)
        bacs1,bacs2 = ...........
        vider(............)
        i += 1
    return ............