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

CAPES
CONCOURS EXTERNE
ET CAFEP CORRESPONDANTS

Section : NUMERIQUE ET SCIENCES INFORMATIQUES

SECONDE ÉPREUVE D'ADMISSIBILITÉ

INFORMATION AUX CANDIDATS

• -
  Concours externe du CAPES de l'enseignement public :

  Concours	Section/option	Epreuve	Matière
  E|B|E	6/2/O/O/E	1|0|2	0|5|3|0

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

  Concours	Section/option	Epreuve	Matière
  E|B|F	6/2/0/01E	1|0|2	0|5|3|0

Partie I. Le trésor et la fausse pièce

Vous avez proposé à vos classes de première en spécialité NSI, le projet ci-dessous.
Vous êtes un ou une pirate qui vient de récupérer sa part du trésor constitué d'un beau tas de pièces d'or. Hélas, vous avez vent d'une supercherie : l'une des pièces n'est pas en or massif, mais en un alliage plus léger que l'or et est simplement plaquée or, pour qu'on ne puisse pas la distinguer visuellement des autres pièces. Le seul signe distinctif est qu'elle est plus légère que les autres. Vous n'avez pas à votre disposition un atelier de chimiste ni un laboratoire scientifique vous permettant d'étudier très précisément ces pièces, mais simplement une balance à plateaux sans aucun poids, comme celle donnée ci-dessous :

• I.1. L'une de vos classes a été beaucoup plus rapide que les autres et les élèves ont très rapidement proposé une réponse utilisant une approche par dichotomie. Pour alimenter leur curiosité et leur créativité, vous voulez les amener à une solution, dite par trichotomie, utilisant un découpage en 3 ensembles (contrairement à 2 ensembles utilisés avec l'approche dichotomique). Afin de les aider, vous préparez un énoncé donné ci-dessous (partie en italique) et que vous comptez leur distribuer. Rédiger un corrigé de cet énoncé, tel que vous le proposeriez à vos élèves.

• 1.Expliquer comment procéder avec 2 pièces pour retrouver la fausse pièce.
• 2.Expliquer comment procéder en une seule pesée quand il y a 3 pièces.
• 3.Expliquer comment conclure en deux pesées quand il y a 4 pièces.

Figure 1 - Exemple avec 9 pièces.

• 4.Dans le cas où n est une puissance de 3(n = 3^k, k entier naturel) : écrire un algorithme itératif qui permet d'identifier, parmi n pièces, la pièce fausse qui est plus légère que les autres.
• 5.Expliquer comment votre algorithme fonctionne avec 27 pièces.
  Aide : on devrait obtenir le résultat en 3 pesées.
• 6.Dans le cas d'un nombre quelconque de pièces, adapter l'algorithme précédent pour identifier la fausse pièce.
• 7.Afin de comparer avec la recherche dichotomique, remplir le tableau suivant, en indiquant, pour chaque méthode et pour différentes valeurs de n, le nombre maximal de pesées.

Partie II. Mastermind : le joueur humain devine

• -le joueur (humain) tente de découvrir une configuration de pions cachée par la machine (le joueur est alors appelé le décodeur et la machine le codificateur);
• -le joueur (humain) cache une configuration de pions à la machine qui doit la découvrir (le joueur est alors appelé le codificateur et la machine le décodeur).

1. La configuration choisie par le codificateur est générée aléatoirement.

• (a)Écrire une fonction Python itérative calculant et retournant le nombre de pions bien placés entre deux configurations, c'est-à-dire les pions de même couleur et de même position entre les deux configurations (nombre de fiches noires). On l'appellera n_bien_places et son en-tête est :
  def n_bien_places(configuration_1,configuration_2)

• (b)Donner un algorithme qui calcule le nombre de pions communs entre deux configurations (l'ordre des pions dans la configuration n'a pas d'importance). Si nécessaire, vous pourrez utiliser une structure de données auxiliaire en expliquant votre choix. La fonction Python qui implante cet algorithme sera appelé n_pions_communs et son en-tête est :
  def n_pions_communs(configuration_1,configuration_2)
  L'implantation de cette fonction n'est pas demandée.
• (c)En déduire une fonction Python renvoyant le nombre de fiches blanches et de fiches noires qui sont déterminées lorsque deux configurations sont comparées. Pour rappel, le nombre de fiches noires correspond au nombre de pions étant bien placés (et donc de la même couleur) et le nombre de fiches blanches correspond au nombre de pions de la bonne couleur qui ne sont pas bien placés. On appellera la fonction n_noirs_blancs et son en-tête est :
  def n_noirs_blancs(configuration_1,configuration_2)

def joueur_devine(n_couleurs=6,n_positions=4,n_essais=10):
configuration_cachee =
        genere_configuration(n_couleurs,n_positions)
print("Taille de la configuration cachée: ",n_positions)
i = ... # nombre d'essais déja réalisés
trouve = ... # variable booléenne qui indique si la
        # configuration a été trouvée
while ... :
        m = input("Essai "+str(i)+" : ")
            # le joueur entre une configuration
        ... # conversion de la configuration entrée
            # dans le bon type
    print(" "+str(...)+" bien placés - "
                +str(...)+" mal placés")
    trouve = ...
if trouve :
    return "Bravo vous avez trouvé en "
                + str(...) + " essais"
else :
    return "Perdu vous avez épuisé vos " + str(...)
        + " tentatives, bonne réponse = "
            + str(configuration_cachee)

• II.3. L'année précédente, vous aviez aussi proposé, en TP, à une classe de terminale, de programmer le jeu du Mastermind avec 5 couleurs, 5 positions et un nombre maximal de 10 essais pour le décodeur, mais vous ne leur aviez pas fourni l'énoncé précédent que vous avez préparé cette année. Un groupe d'élèves vous a rendu la fonction donnée en annexe 4. Analyser cette production, en se référant aux numéros de ligne si nécessaire.
  (Répondre en 20 lignes maximum.)
• II.4. Proposer une remédiation pour ce groupe d'élèves sur les points qui vous paraissent importants.
  (Répondre en 10 lignes maximum.)

Partie III. Mastermind : la machine devine

• III.1. Étude de l'ensemble de toutes les configurations
• III.1.a. Donner la formule du nombre de configurations possibles en fonction des paramètres N et P du jeu.
• III.1.b. Avec les valeurs habituelles pour le jeu, qui sont N = 6 et P = 4 pour les plus jeunes joueurs et joueuses, et dans la version classique N = 8 et P = 5, combien y a-t-il de configurations possibles? Vous pourrez vous aider de la table de calculs donnée en annexe 3.
• III.1.c. Est-il envisageable et raisonnable de créer et de mémoriser toutes les configurations dans ces deux cas de figures?
  Quelle comparaison pourriez-vous proposer à vos élèves pour qu'ils puissent arriver à la même conclusion que vous? Vous pourrez supposer qu'un entier est codé sur 64 bits.
• III.2. Vous avez trouvé sur le Web un projet, traitant du Mastermind, déjà réalisé. Pour savoir si vous pouvez vous en inspirer, vous l'analysez. Que fait la fonction Python suivante ? Prouver qu'elle n'omet aucune configuration.

def mystere(n_couleurs = 6,n_positions = 4) :
    if ( n_positions == 0) :
        return [[]]
    else :
        l = []
        for element in mystere(n_couleurs,n_positions-1):
            for couleur in range(1,n_couleurs+1) :
                l.append(element + [couleur])
        return l

• III.4.a. Vous supposez que la machine a proposé une configuration, nommée tentative, et a reçu du codificateur, en retour, le nombre de fiches noires, noté n_bien_places, et le nombre de fiches blanches, noté n_mal_placés.
  Vous comptez demander à vos élèves un algorithme qui commence avec l'ensemble des configurations qui étaient encore candidates avant la proposition de la configuration tentative (ensemble qui sera appelé configurations_possibles) et qui le modifie pour qu'il ne contienne plus que l'ensemble des configurations qui pourront être candidates au tour suivant, une fois les fiches noires et blanches reçues du codificateur suite à la proposition de tentative. Écrire cet algorithme pour pouvoir donner un corrigé à vos élèves. La fonction Python correspondante s'appellera reduction_configurations_possibles. Il ne vous est pas demandé d'écrire cette fonction, mais seulement de donner son en-tête avec ses paramètres d'entrée.
• III.4.b. Quel(s) argument(s) donneriez-vous à vos élèves pour qu'ils choisissent la liste, parmi les structures linéaires de type liste, pile et file, afin de stocker l'ensemble des configurations possibles?
• III.4.c. Quel argument donneriez-vous à vos élèves pour qu'ils comprennent que n'importe quelle configuration peut être choisie dans l'ensemble configurations_possibles pour le tour suivant?
• III.4.d. Écrire le corrigé de la fonction Python interactive, demandée à vos élèves, permettant d'effectuer une partie où c'est la machine qui devine la configuration choisie par le joueur. Ce programme comprend la génération de toutes les configurations possibles par la machine, les propositions successives de la machine et les réponses correspondantes du joueur.
  Voici son en-tête :
  def machine_devine(n_couleurs=6,n_positions=4,n_essais=10)

Partie IV. Mastermind : évaluation et analyse d'un projet

Partie V. Enjeu sociétal

Annexe 1 : Règles du Mastermind

• -le nombre de pions de la bonne couleur bien placés en utilisant le même nombre de fiches noires à côté de la rangée proposée par le décodeur;
• -puis le nombre de pions de la bonne couleur, mais mal placés, en insérant le même nombre de fiches blanches à côté des fiches noires.

Figure 2 - Exemples de Mastermind.

Annexe 2 : Bibliothèque random

import random
print random.randint(1, 5)

Annexe 3 : Table de calculs

Annexe 4 : Production d'élèves

def verification():
    # definit le nombre de couleurs justes
    # et de couleurs qui ne sont pas dans la combinaison a trouver
    bon=0
    mauvais=0
    tour=tour+1
    if a==aa:
        bon=bon+1
    if aa!=a and aa!=b and aa!=c and aa!=d and aa!=e:
        mauvais=mauvais+1
    if b==bb:
        bon=bon+1
        if bb!=b and bb!=a and bb!=c and bb!=d and bb!=e:
            mauvais=mauvais+1
    if c==cc:
        bon=bon+1
    if cc!=c and cc!=b and cc!=a and cc!=d and cc!=e:
        mauvais=mauvais+1
    if d==dd:
        bon=bon+1
    if dd!=d and dd!=b and dd!=c and dd!=a and dd!=e:
        mauvais=mauvais+1
    if e==ee:
        bon=bon+1
    if ee!=e and ee!=b and ee!=c and ee!=d and ee!=a:
        mauvais=mauvais+1
    if a==aa and b==bb and c==cc and d==dd and e==ee:
        # Si la combinaison est la méme que celle é trouver,
        # ouvre une fenétre de victoire
        fen_gagne=Toplevel()
        fen_gagne.title("Mastermind")
        text=Label(fen_gagne,text="Vous avez gagné !
                Félicitations !")
        text.pack()
        global fen_gagne
    if tour==10 :
        # Si au 10eme tour, la combinaison n'a pas encore ete
        # trouvée, défaite
        if aa!=a or bb!=b or cc!=c or dd!=d or ee!=e :
                fen_perdu=Toplevel()
                fen_perdu.title("Mastermind")
                text=Label(fen_perdu,text=
                    "C est la 10e tentative sans succés,
                    vous avez donc perdu la partie")
                text.pack()
                global fen_perdu
    bon=str(bon)
    mauvais=str(mauvais)
    global tour,bon,mauvais

Annexe 5 : Analyse d'un projet d'élève sur le Mastermind

4. Analyse des résultats

4.1. Le nombre de coups pour gagner

Graphique correspondant au tableau ci-dessus

Annexe 6

Documents pour la partie V.

Impacts sur les pratiques humaines

Les données et l'information

Article tiré du site The Conversation

THE CONVERSATION
L'expertise universitaire, l'exigence journalistique

Dans le métro. Photo by Martin Adams on Unsplash

Données anonymes… bien trop faciles à identifier

Matière première

Auteur

Ré-identification

Traitement d'échantillons viraux. Les données personnelles de santé sont parmi les plus sensibles. James Gathany/CDC

Un algorithme qui remet en question l'anonymat

Un guide pour protéger les données en Australie. Australian Government, CC BY