CAPES informatique troisième concours 2023, épreuve écriteSujet 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

  E

  6

  2

  0

  0

  1

  0

  1

  9

  3

  1

  1

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

  E

  IV

  6

  2

  0

  0

  1

  0

  1

  9

  3

  1

• -
  Concours externe du CAFEP/CAPES de l'enseignement privé :
  Concours Section/option Epreuve Matière

  E

  F

  6

  2

  0

  0

  E

  1

  落

  3

  1

Épreuve disciplinaire

• -On peut créer une liste de taille n remplie avec la valeur x avec li = [x] ★ n.
• -On peut obtenir la taille d'une liste li avec len(li).
• -Si li est une liste de n éléments, on peut accéder au k-ème élément (pour 0 ≤ k < len(li) ) avec li[k]. On peut définir sa valeur avec li[k] = x.
• -On peut ajouter un élément x dans une liste li à l'aide de li.append(x), et on considèrera qu'il s'agit d'une opération élémentaire.
• -Les matrices sont des listes de listes, chaque sous-liste étant considérée comme une ligne de la matrice. Si mat est une matrice, elle possède len(mat) lignes et len(mat[0]) colonnes.
• -On peut créer une matrice de n lignes et p colonnes, dont toutes les cases contiennent x avec mat = [[x for j in range(p)] for i in range(n)].
• -On accède (resp. modifie) l'élément de mat dans la i-ème ligne et j-ème colonne avec mat[i][j] (resp. mat[i][j] = x).
• -On peut concaténer deux listes en utilisant l'opération li1 + li2. On utilisera aussi cette opération dans des expressions mathématiques.
• -li [a:b] désigne la liste des éléments d'indice compris entre a et b − 1 dans li. On utilisera aussi cette opération dans des expressions mathématiques.

Problème 1 Programmation en Python

Partie I Programmes divers

• Question 1 Écrire une fonction fibonacci (n) qui prend en argument un entier n supérieur ou égal à 2 et renvoie la liste des n premiers termes de la suite de Fibonacci (F_n)_(n ∈ ℕ) définie par F_0 = 0 et F_1 = 1 et ∀n ≥ 2, F_n = F_(n − 1) + F_(n − 2) (chaque terme est la somme des deux précédents).
• Question 2 Écrire une fonction indice_min(li) qui prend en argument une liste d'entiers li et renvoie l'indice d'un de ses minimums.
• Question 3 Que renverra indice_min([1, 0, 2, 0]) avec votre programme ?
• Question 4 Écrire une fonction zero_sur_lignes(mat) qui prend en argument une matrice (c'est-à-dire une liste de listes) contenant des 0 et des 1, renvoie True lorsque chaque ligne contient au moins un zéro, et False sinon.

• Question 5 Écrire une fonction lettre_majoritaire(ch) qui prend en argument une chaîne de caractères non vide et renvoie le caractère qui apparait le plus fréquemment. Ainsi, lettre_majoritaire('abcdedde') devrait renvoyer 'd'.

Partie II Saut de valeur maximale

A. Introduction

• Question 6 Écrire une fonction valeur(li, saut) qui prend en argument une liste et un saut et renvoie la valeur du saut.
• Question 7 Donner un exemple de liste avec exactement deux sauts de valeur maximale et préciser ces sauts.
• Question 8 À l'aide d'un contre-exemple, montrer qu'on ne peut pas se contenter de chercher le minimum et le maximum d'une liste pour trouver un saut de valeur maximale.
• Question 9 Écrire une fonction saut_max_naif(li) qui renvoie un saut de valeur maximale en testant tous les couples (i, j) tels que 0 ≤ i ≤ j < len(li).

B. Programmation dynamique

• Question 10 Pour k < len(li), expliquer comment on peut calculer efficacement m_(k + 1) à partir de m_k et des valeurs dans li.
• Question 11 Justifier que la relation suivante est correcte.

• Question 12 Écrire une fonction saut_max_dynamique(li) qui renvoie un saut de valeur maximale en utilisant la relation de la question 11.
• Question 13 Déterminer la complexité de votre programme dans le pire cas, puis comparer cette complexité avec celle du programme donné en question 9.

C. Méthode diviser pour régner

• - (i_g, j_g) un saut de valeur maximale lorsque j_g < ⌊n/2⌋,
• - (i_d, j_d) un saut de valeur maximale lorsque i_d ≥ ⌊n/2⌋,
• -et (i_m, j_m) un saut de valeur maximale lorsque i_m < ⌊n/2⌋ ≤ j_m.

• Question 14 Justifier qu'un saut de valeur maximale de li est nécessairement un des trois ci-dessus.
• Question 15 Avec les notations précédentes, justifier que i_m est nécessairement l'indice d'une valeur minimale dans la moitié gauche de li (on admettra que, de même, j_m est nécessairement l'indice d'une valeur maximale dans la moitié droite de li).
• Question 16 Écrire une fonction récursive saut_max_aux(li, a, b) qui prend en argument une liste li et deux indices a < b de cette liste et renvoie le quadruplet constitué d'un saut de valeur maximale dans li entre les indices a et b − 1 (deux valeurs), des indices d'un minimum et d'un maximum de li entre les indices a et b − 1 (deux valeurs).

• Question 17 En déduire une fonction saut_max(li) qui renvoie un saut de valeur maximale d'une liste li.

Problème 2 Résolution de logigrammes

Partie III Cases, blocs et indications

A. Indications

Dans toute cette partie, on notera |χ(li)| le nombre d'éléments dans son indication.

ligne_ex = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0]
indication_ex = [3, 5, 1]

• Question 18 Donner un exemple d'une ligne distincte de ligne_ex (donné en figure 1) mais ayant la même taille et la même indication.
• Question 19 Écrire une fonction valeur_ligne(li) qui prend en argument une ligne li et renvoie sa valeur v(li) comme définie ci-dessus.
• Question 20 Écrire une fonction indication(li) qui prend en argument une ligne li et renvoie son indication χ (li). La fonction proposée devra avoir une complexité en O(|li|).
• Question 21 Justifier que pour toute ligne li, on a v(li) ≤ |li| + 1 − |χ(li)|, et donner un exemple où il y a égalité.

B. Lignes réduites

• -on réduit la taille de chaque bloc de li à 1 en supprimant autant de cases noires qu'il le faut,
• -puis, dans chaque intervalle de cases blanches entre deux blocs, on supprime exactement une case blanche. On ne modifie pas les intervalles de cases blanches aux extrémités.
• -Question 22 Donner la ligne réduite φ (ligne_ex) de la ligne de la figure 1.
• -Question 23 Écrire une fonction ligne_reduite(li) qui prend en argument une ligne li et renvoie la ligne réduite φ(li).
• -Question 24 Pour une ligne li quelconque, exprimer la taille de la ligne réduite |φ(li)| en fonction de | li | et de v( li ). Vous justifierez votre réponse.
• -Question 25 Soient k un entier, I une indication, et li_r une ligne de taille k possédant exactement |I| cases noires. Montrer que li_r est la ligne réduite d'une ligne de taille k + v(I) − 1 et d'indication I.
• -Question 26 Écrire une fonction reconstruire_ligne(li_r, indic) qui prend en argument une ligne réduite li_r et une indication indic, et renvoie une ligne dont la ligne réduite est li_r et dont l'indication est indic, lorsqu'une telle ligne existe. Si aucune ligne ne convient, aucun comportement particulier n'est exigé.
• -Question 27 Soient deux lignes l_1 et l_2 de même taille (|l_1| = |l_2|), même indication (χ(l_1) = χ(l_2)), et même ligne réduite (φ(l_1) = φ(l_2)). Montrer que l_1 = l_2.
• -Question 28 Soient n un entier et I une indication. On note E l'ensemble des lignes de taille n et d'indication I. Déduire des questions précédentes que la fonction φ réalise une bijection entre E et un autre ensemble que l'on précisera, et en conclure que E est de cardinal ((n − v(I) + 1)/(|I|)), où (n/p) désigne le nombre de combinaisons de p éléments parmi n (à savoir (n!)/(p!(n − p) !) ).

C. Énumeration de lignes

def next(li):
    """Renvoie la ligne réduite suivant li dans l'ordre
    d'énumération des lignes réduites."""
    k = len(li)
    for i in range(k-1, 0, -1):
        if li[i] == 1 and li[i-1] == 0:
            return li[0:i-1] + [1, 0] + li[k-1:i:-1]
    return []

• Question 29 Que renvoie next([0, 0, 1, 1, 1]) ? Que renvoie next([1, 1, 1, 0, 0]) ?
• Question 30 Compléter la fonction liste_lignes_reduites(nb_noires, k), donnée ci-dessous, qui renvoie la liste des lignes réduites de taille k ayant nb_noires cases noires.

def liste_lignes_reduites(nb_noires, k):
    # Première ligne réduite
    li = [0] * (k-nb_noires) + [1] * nb_noires
    # Liste des lignes réduites
    res = []
    while ...:
        res.append(...)
        li = ...
    return res

• Question 31 Écrire une fonction liste_lignes(indic, n) qui renvoie la liste des lignes de longueur n et d'indication indic.

Partie IV Jeu du logigramme

Figure 2: Exemple de puzzle et sa résolution pour le jeu du logigramme.

Figure 3: Exemple du puzzle puzzle_ex et sa représentation en Python.

• Question 32 Donner un exemple de puzzle avec n = p = 2 qui n'admette aucune solution.
• Question 33 Donner un exemple de puzzle avec n = p = 2 qui admette plusieurs solutions, et donner toutes ses solutions.

• -un 0 si la case est blanche ;
• -un 1 si la case est noire ;
• -et -1 enfin si la couleur de la case n'est pas encore déterminée.

• Question 34 Écrire une fonction grille_vide(puzzle) qui prend en argument un puzzle et renvoie une grille ayant la bonne taille, mais ne contenant que des -1 (toutes les cases sont indéterminées).
• Question 35 Écrire une fonction nb_cases_ind(grille) qui prend en argument une grille et renvoie le nombre de cases indéterminées dans la grille.
• Question 36 Écrire une fonction est_valide(puzzle, grille) qui prend en entrée un puzzle et une grille de dimension adaptée dont toutes les cases sont déterminées, et renvoie True si la grille est une solution du puzzle, et False sinon.
• Question 37 Donner la complexité de la fonction est_valide en fonction de n et p, les dimensions de la grille.

Partie V Remplissage

• Question 38 Écrire une fonction liste_lignes_compatibles(indic, ligne_partielle) qui prend en arguments une indication, une ligne partiellement remplie d'une grille, et renvoie la liste de toutes les lignes ayant comme indication indic et compatibles avec les cases déjà remplies dans ligne_partielle.

>>> liste_lignes_compatibles([2, 2], [-1]*6)
[[1, 1, 0, 1, 1, 0],
    [1, 1, 0, 0, 1, 1],
    [0, 1, 1, 0, 1, 1]]
>>> liste_lignes_compatibles([2, 2], [1, -1, 0, -1, -1, -1])
[[1, 1, 0, 1, 1, 0],
    [1, 1, 0, 0, 1, 1]]

Figure 4: Liste des lignes compatibles avec l'indication [2, 2] et une ligne partielle. Les points d'interrogation sont les cases indéterminées.

• Question 39 Écrire une fonction remplir_ligne(indic, ligne) qui prend en argument une indication, une ligne partiellement remplie, et renvoie une copie de ligne complétée au maximum, comme dans l'exemple ci-dessous :

>>> remplir_ligne([2, 2], [-1]*6)
[-1, 1, -1, -1, 1, -1]
>>> remplir_ligne([2, 2], [1, -1, 0, -1, -1, -1])
[1, 1, 0, -1, 1, -1]

• Question 40 Écrire une fonction completer_lignes(puzzle, grille) qui applique cette méthode sur chaque ligne et modifie grille en fonction. Cette fonction ne renvoie rien.
• Question 41 On exécute le programme suivant (puzzle_ex est donné dans la figure 3) :

grille = grille_vide(puzzle_ex)
completer_lignes(puzzle_ex, grille)

• Question 42 On suppose qu'on dispose d'une fonction completer_colonnes(puzzle, grille) au fonctionnement similaire à la fonction completer_lignes. Écrire une fonction completer(puzzle, grille) qui applique ces deux fonctions sur la grille, jusqu'à ce que la grille ne soit plus modifiée.

Partie VI Retour sur trace

• Question 43 Que donnerait la fonction completer sur le puzzle ([[1, 1], [2]], [[1], [1], [1], [1]]) et avec une grille vide ? Donner sans justification l'unique solution de ce puzzle.
• Question 44 La méthode du retour sur trace (ou backtracking) consiste, quand la méthode précédente (implémentée par la fonction completer) ne permet pas de résoudre une grille, à faire une hypothèse sur une case indéterminée de la grille : on essaye de terminer la résolution en supposant cette case blanche, puis en supposant cette case noire. Il est possible que cette hypothèse ne suffise pas, on formulera alors une autre hypothèse sur une autre case. Il est possible qu'une suite d'hypothèses aboutisse à une impasse, ce qui se traduira par la fonction remplir_ligne qui renvoie une liste vide. Dans ce cas, il convient d'abandonner cette suite d'hypothèses et d'en tester une autre.