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

INFORMATION AUX CANDIDATS

CAPES EXTERNE NUMÉRIQUE ET SCIENCES INFORMATIQUES

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

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

Préambule

Partie A

• 1.En vous aidant de la documentation de la bibliothèque Python Pillow donnée dans l'annexe 1, écrivez un programme Python permettant de transformer une image couleur au format JPEG (nom : "photo.jpg" ; définition de l'image en pixels : 800 x 600) en image en niveaux de gris de même format puis de l'afficher.
• 2.Proposez une activité destinée à vos élèves de seconde leur permettant d'écrire (ou de compléter) un programme Python ayant pour but de modifier "une image pour la transformer en agissant sur les trois composantes de ses pixels."
• 3.Proposez une correction, à destination des élèves, de l'activité que vous aurez rédigée à la question 2.

Partie B

• 4.Vous trouverez dans l'annexe 2 un exercice donné à des élèves de première NSI dans le cadre d'une évaluation. Proposez une correction de cet exercice à destination de vos élèves.
• 5.Expliquez le principe de la représentation en machine des nombres à virgule flottante, par exemple en vous appuyant sur la norme IEEE-754.
• 6.Expliquez la phrase suivante du programme : "0.2 + 0.1 n'est pas égal à 0.3".

Partie C

• 7.Voici l'énoncé de l'exercice 1 d'un sujet tiré de la banque 2022 :
  Écrire une fonction maxi qui prend en paramètre une liste tab de nombres entiers et qui renvoie un couple donnant le plus grand élément de cette liste ainsi que l'indice de la première apparition de ce maximum dans la liste.
  Exemple : >>> maxi([1,5,6,9,1,2,3,7,9,8])
  (9, 3)
  Proposez un corrigé de cet exercice.
• 8.
  Voici l'énoncé de l'exercice 2 d'un sujet tiré de la banque 2022 :
  La fonction recherche prend en paramètres deux chaines de caractères gene et seq_adn et renvoie True si on retrouve gene dans seq_adn et False sinon. Compléter le code Python ci-dessous pour qu'il implémente la fonction recherche.

  def recherche(gene, seq_adn):
      n = len(seq_adn)
      g = len(gene)
      i = ...
      trouve = False
      while i < ... and trouve == ... :
          j = 0
          while j < g and gene[j] == seq_adn[i+j]:
              ...
          if j == g:
              trouve = True
          ...
      return trouve
  

  Proposez un corrigé de cet exercice.
• 9.Dans le cadre de la préparation de vos élèves de première à cette épreuve pratique, vous élaborez le contenu d'une séance de Travaux Pratiques qui s'appuiera sur la résolution d'un sujet. Rédigez un sujet type « épreuve pratique », pour vos élèves de première NSI en respectant les préconisations de la note de service dont l'extrait est en annexe 3.
  Le premier exercice devra porter sur la partie suivante du programme de première de l'enseignement de spécialité NSI. Rédigez un exercice de type "Exercice I". Cet exercice devra porter sur la recherche dichotomique.

• 10.Proposez une correction pour l'exercice proposé à la question 9
• 11.Rédigez un exercice de type "Exercice II". Cet exercice devra porter sur la partie "dictionnaire" du programme de première.

12. Proposez une correction pour l'exercice rédigé à la question 11.

Partie D

• 13.Expliquez, comme vous le feriez devant une classe de première, le principe du tri par insertion.
• 14.Expliquez, comme vous le feriez devant une classe de première, le principe du tri par sélection.
• 15.Montrez que la complexité en temps dans le pire des cas de l'algorithme du tri par insertion est quadratique.
• 16.Démontrez la correction de l'algorithme du tri par insertion à l'aide d'un invariant de boucle.
• 17.Écrivez une fonction Python tri_selection qui prend en paramètre une liste d'entiers L. Cette fonction devra trier la liste passée en paramètre en utilisant l'algorithme du tri par sélection.

• 18.Expliquez, comme vous le feriez devant une classe de terminale, le principe du trifusion.
• 19.Expliquez, comme vous le feriez devant une classe de terminale, le coût en n.log_2(n) dans le pire des cas du tri-fusion.
• 20.À la suite d'une activité sur le tri-fusion, une élève vient vous dire qu'elle a regardé une vidéo consacrée au tri-rapide (quicksort) et qu'elle a l'impression que cet algorithme ressemble au tri-fusion étudié en classe, comment lui expliquez-vous les points communs et les différences entre ces deux algorithmes ?

Partie E

• 21.Écrivez une fonction Python récursive fib qui prend en paramètre un entier n et qui renvoie le terme F_n de la suite de Fibonacci.
• 22.Un élève a réussi à écrire la fonction fib et s'interroge sur le fait que l'exécution de fib(120) "fasse planter l'ordinateur", que pouvez-vous lui répondre ?

• 23.Expliquez, en quelques lignes, le principe de la programmation dynamique.
• 24.Utilisez la programmation dynamique afin d'améliorer l'efficacité de la fonction écrite à la question 21 . Vous écrirez deux programmes Python : un premier programme qui utilisera l'approche ascendante (bottom-up) et un deuxième programme qui utilisera l'approche descendante (top-down).

• 25.Expliquez, en quelques lignes, le principe d'un algorithme glouton.

26. Voici une fonction Python rendu proposée par un élève de terminale permettant de résoudre le problème du rendu de monnaie en utilisant une méthode gloutonne. Cette fonction prend en paramètre la somme à rendre (en euro) et renvoie le nombre minimum de pièces qu'il est possible de rendre. Quel est, selon vous, le problème qui risque de se poser lors de l'exécution de ce programme ? Proposez une modification afin de supprimer ce problème.

def rendu(s):
    index = 0
    tab_piece = [2, 1, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01]
    somme_rendu = 0
    nbre_piece = 0
    while somme_rendu != s :
        somme_a_rendre = s - somme_rendu
        if somme_a_rendre < tab_piece[index]:
            index = index + 1
        else :
            somme_rendu = somme_rendu + tab_piece[index]
            nbre_piece = nbre_piece + 1
    return nbre_piece

• 27.Pour les questions suivantes, on supprime la pièce de 1 centime du tableau tab_piece (valeur 0.01). Donnez une valeur de s (paramètre de la fonction rendu) pour laquelle la méthode gloutonne ne permet pas de trouver une solution alors que cette solution existe.
• 28.Suite aux constatations faites à la question 27, vous décidez d'abandonner la méthode gloutonne pour résoudre le problème du rendu de monnaie et d'écrire à la place une fonction récursive rendu_rec qui prend en paramètre la somme à rendre s (en centimes) et qui renvoie le nombre minimum de pièces qu'il est possible de rendre (cette fonction doit trouver la solution, si cette solution existe). Écrivez cette fonction en Python.
• 29.En utilisant la programmation dynamique, améliorer l'efficacité du programme écrit à la question 28.

Partie F

• 30.Proposez un corrigé de cet exercice à destination de vos élèves.
• 31.Proposez un barème sur 10 points pour cet exercice en expliquant vos choix.
• 32.On donne dans l'annexe 5 un extrait d'une copie d'élève. Corrigez cet extrait de copie, la copie corrigée sera rendue à l'élève.
• 33.Globalement, cet exercice est difficile. Proposez, en les justifiant, au moins deux modifications permettant de le rendre plus accessible.

ANNEXES

Annexe 1

from PIL import Image
img = Image.open("chat.jpg")

from PIL import Image
img = Image.open("chat.jpg")
res = img.size
# le contenu de la variable res est le tuple (800,600) pour une image de
# taille 800 pixels par 600 pixels

from PIL import Image
img = Image.open("chat.jpg")
r, v, b = img.getpixel((100,150))
# si le pixel de coordonnées (100,150) est rouge
# on obtiendra r = 255, v = 0, b = 0

from PIL import Image
img = Image.open("chat.jpg")
img.putpixel((100,150), (0,255,0))
# le pixel de coordonnées (100,150) est désormais vert

from PIL import Image
img = Image.open("chat.jpg")
img.putpixel((100,150), (0,255,0))
img.show()

Annexe 2

Exercice 2

• 1.Convertissez 27_(10) en base 2.
• 2.Convertissez 1000101_2 en base 10.
• 3.Convertissez 44_(10) en base 16.
• 4.Convertissez A 1_(16) en base 10.
• 5.Convertissez 100110_2 en base 16.
• 6.Convertissez F3_(16) en base 2.
• 7.En utilisant le complément à 2 sur 8 bits, convertissez − 9_(10) en base 2 .
• 8.En utilisant le complément à 2 sur 8 bits, convertissez 10010110_2 en base 10.
• 9.Convertissez 1, 0100_2 en base 10.
• 10.Convertissez 3, 125_(10) en base 2.

• -Premier exercice

• -Deuxième exercice

Arbre 1

• 1.Quelle est la taille de l'arbre 1 ?
• 2.Quelle est la hauteur de l'arbre 1 ?
• 3.L'arbre 1 est-il un arbre binaire de recherche ? Justifiez votre réponse.
• 4.Parcourir l'arbre 1 dans l'ordre suffixe

class ArbreBinaire:
    def __init__(self, valeur):
        self.valeur = valeur
        self.enfant_gauche = None
        self.enfant_droit = None
    def insert_gauche(self, valeur):
        if self.enfant_gauche == None:
            self.enfant_gauche = ArbreBinaire(valeur)
        else:
            new_node = ArbreBinaire(valeur)
            new_node.enfant_gauche = self.enfant_gauche
            self.enfant_gauche = new_node

def insert_droit(self, valeur):
    if self.enfant_droit == None:
        self.enfant_droit = ArbreBinaire(valeur)
    else:
        new_node = ArbreBinaire(valeur)
        new_node.enfant_droit = self.enfant_droit
        self.enfant_droit = new_node
def get_valeur(self):
    return self.valeur
def get_gauche(self):
    return self.enfant_gauche
def get_droit(self):
    return self.enfant_droit

• 5.
  En utilisant la classe ArbreBinaire, implémenter en Python l'arbre binaire donné cidessous (arbre 2)
  

  arbre 2
• 6.Écrire la fonction taille qui prend en paramètre une instance T de la classe ArbreBinaire et qui renvoie la taille de l'arbre T.
• 7.Écrire la fonction hauteur qui prend en paramètre une instance T de la classe ArbreBinaire et qui renvoie la hauteur de l'arbre T.
• 8.Écrire la fonction parcours_infixe qui prend en paramètre une instance T de la classe ArbreBinaire et qui permet d'afficher dans la console le parcours de l'arbre binaire T dans l'ordre infixe
• 9.Écrire la fonction arbre_recherche qui prend en paramètres une instance T de la classe ArbreBinaire (cette instance représentant un arbre binaire de recherche dont les valeurs des nœuds sont des entiers) et un entier k. Cette fonction renvoie True si k appartient à T et False dans le cas contraire.

Annexe 5 (À RENDRE AVEC LA COPIE)

• 1.9
• 2.3
• 3.Oui, cet arbre binaire est bien un arbre binaire de recherche, car tous les nœuds situés à gauche de la racine sont plus petits que 22 et tous les nœuds situés à droite de la racine sont plus grands que 22.
• 4.22-17 - 12-8 - 21-30 - 34 - 24-25

• 5.
  ```
  arbre = ArbreBinaire(53)
  arbre.insert_gauche(20)
  arbre.insert_droit(85)
  n_20 = arbre.get_gauche()
  n_85 = arbre.get_droit()
  n_20.insert_gauche(19)
  n_20.insert_droit(21)
  n_85.insert_gauche(68)
  n_85.insert_droit(89)

def taille(T):
    if T==None:
        return 0
    else :
        return 1 + taille(T-1)

def hauteur(T):
    if T == None:
        return 0
    else :
        return 1 + hauteur(T.get_gauche()) + hauteur(T.get_droit())

def parcours_infixe(T):
    if T == None:
        return 0
    else :
        print(T)
        parcours_infixe(T.get_gauche())
        parcours_infixe(T.get_droit())

def arbre_recherche(T,k):
    while T != None:
        if T.get_valeur() == k:
            return True
        elif T.get_valeur() < k:
            T = T.get_gauche()
        else :
            T = T.get_droit()
    return False