CAPES informatique externe 2021, épreuve 1Sujet et rapport du jury

INFORMATION AUX CANDIDATS

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

  Concours	Section/option	Epreuve	Matière
  E|B|E	620|0|E	1|0|1	0|5|4|0

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

  Concours	Section/option	Epreuve	Matière

• -
  Troisième concours du CAPES de l'enseignement public :

  Concours	Section/option	Epreuve	Matière
  E|B|V	6/2/ODIE	1|0/1	0|5|40

• -
  Troisième concours CAFEP/CAPES de l'enseignement privé :

  Concours	Section/option	Epreuve	Matière
  E[B] W	6/2/0/01E	1|0/1	0|5|4|0

• -Création d'une liste de taille n remplie avec la valeur x : li = [x]∗n.
• -Obtention de la taille d'une liste li : len(li).
• -Si li est une liste de n éléments, on peut accéder au k^e élément (pour 0 ≤ k < len(li)) avec li[k]. On peut définir sa valeur avec li [k] = x.
• -Un élément x peut être ajouté dans une liste li à l'aide de li.append(x). 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.
• -Création d'une matrice de n lignes et p colonnes, dont toutes les cases contiennent x : 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^e ligne et j^e colonne avec mat [i] [j] (resp. mat[i][j] = x).

Problème 1 : Points proches dans le plan

1 Approche exhaustive

• Question 1 Écrire une fonction distance (i, j) qui renvoie la distance entre les points M_i et M_j. On utilisera la fonction sqrt après l'avoir importée.
• Question 2 Rappeler sommairement comment sont stockés les flottants en mémoire. Quelle conséquence cela peut-il avoir sur le calcul de la distance ? On ignorera par la suite les problèmes d'approximation.
• Question 3 Écrire une fonction plus_proche() qui renvoie, à l'aide d'une recherche exhaustive, le couple d'entiers des indices i et j des deux points les plus proches du nuage de points.
• Question 4 Donner, en la justifiant sommairement, la complexité de la fonction précédente en fonction de n.

2 Quelques outils pour s'améliorer

def tri(liste):
    n = len(liste)
    for i in range(n):
        pos = i
        while pos > 0 and liste[pos] < liste[pos-1]:
            liste[pos], liste[pos-1] = liste[pos-1], liste[pos]
            pos -= 1

• Question 5 Que renvoie cette fonction ? Que fait-elle ? Le démontrer soigneusement en exhibant un invariant de boucle.
• Question 6 Donner, en la démontrant, la complexité de la fonction tri en fonction de la taille de la liste donnée en paramètre.
• Question 7 On souhaite trier une liste contenant des indices de points suivant l'ordre des abscisses croissantes. Que faudrait-il changer à la fonction tri ci-dessus pour qu'elle réalise cette opération?
• Question 8 Indiquer le nom d'un autre algorithme de tri plus efficace dans le pire des cas, ainsi que sa complexité. On ne demande pas de le programmer.
  On admettra que l'on dispose de deux listes de n entiers liste_x (resp. liste_y) contenant les indices des points du nuage triés par abscisses croissantes (resp. par ordonnées croissantes). On supposera désormais que deux points quelconques ont des abscisses et des ordonnées distinctes.

Figure 1 - Représentation en Python de deux clusters

• Question 9 Écrire une fonction sous_cluster(cl, x_min, x_max) qui prend en arguments un cluster cl et deux flottants x_min et x_max, et renvoie le sous-cluster des points dont l'abscisse est comprise entre x_min et x_max (au sens large). Cette fonction doit avoir une complexité linéaire en la taille du cluster.
• Question 10 Écrire une fonction mediane(cl) qui prend en entrée un cluster cl contenant au moins 2 points et renvoie une abscisse médiane, c'est-à-dire que la moitié (au moins) des points a une abscisse inférieure ou égale à cette valeur, et la moitié (au moins) des points a une abscisse supérieure ou égale à cette valeur. Cette fonction doit avoir une complexité en O(1).

3 Méthode sophistiquée

• 1.Si le cluster contient deux ou trois points, on calcule la distance minimale en calculant toutes les distances possibles.
• 2.Sinon, on sépare le cluster en deux parties G et D qu'on supposera de tailles égales (éventuellement à un point près) suivant la médiane des abscisses, qu'on notera x_0.
• 3.Les deux points les plus proches sont soit tous les deux dans G, soit tous les deux dans D, soit un dans G et un dans D.
• 4.On calcule récursivement le couple le plus proche dans G et le couple le plus proche dans D. On note d_0 la plus petite des deux distances obtenues.
• 5.On cherche s'il existe une paire de points ( M_1, M_2 ) telle que M_1 est dans G, M_2 dans D, et d(M_1, M_2) < d_0.
• 6.
  Si on en trouve une (ou plusieurs), on renvoie la plus petite de ces distances. Sinon, on renvoie d_0.
  

  Figure 2 - Illustration du diviser pour régner

• Question 11 Écrire une fonction gauche(cl) qui prend en argument un cluster cl contenant au moins deux points et renvoie le cluster constitué uniquement de la moitié (éventuellement arrondie à l'entier supérieur) des points les plus à gauche du cluster cl.

• Question 12 Justifier que l'on peut se contenter de chercher les points M_1 et M_2 de l'étape 5 de l'algorithme dans l'ensemble des points dont l'abscisse appartient à I_0 = [x_0 − d_0, x_0 + d_0].
• Question 13 Écrire une fonction bande_centrale(cl, d0) qui prend en argument un cluster cl et un réel d0, et renvoie le cluster des points dont l'abscisse est dans I_0. Cette fonction doit avoir une complexité linéaire en la taille du cluster.
• Question 14 Montrer que deux points M_1 et M_2 (de l'étape 5 de l'algorithme) situés à une distance inférieure à d_0 se trouvent, dans la deuxième ligne du cluster (c'est-à-dire la ligne triée par ordonnées croissantes), séparés d'au plus 6 éléments.
  On pourra montrer par l'absurde qu'un rectangle, à préciser, de dimensions 2d_0 × d_0 contient au plus 8 points.
• Question 15 En déduire une fonction fusion(cl, d0) qui prend en entrée un cluster de points dont toutes les abscisses sont dans un intervalle [x_0 − d_0, x_0 + d_0], et renvoie la distance minimale entre deux points du cluster si elle est inférieure à d_0, ou d_0 sinon. Cette fonction doit avoir une complexité linéaire en la taille du cluster cl. Vous justifierez cette complexité.
• Question 16 Écrire une fonction récursive distance_minimale(cl) qui prend en argument un cluster et utilise l'algorithme décrit plus haut pour renvoyer la distance minimale entre deux points du cluster.
• Question 17 Si on note n la taille du cluster cl, et C(n) le nombre d'opérations élémentaires réalisées par la fonction distance_minimale(cl), justifier que l'on a :

• Question 18 En déduire, en la démontrant, la complexité C(n). On pourra se limiter au cas où n est une puissance de 2.

Problème 2 : Composantes connexes et biconnexes

4 Site Internet et bases de données

• Question 19 Expliquer sommairement la différence entre Internet et le web.
• Question 20 Expliquer deux conséquences du règlement général sur la protection des données (RGPD) sur le site Internet.

• -La table comptes possède un enregistrement par utilisateur ou utilisatrice, et ses attributs sont :
  • -id, un identifiant numérique, unique pour chaque compte ;
  • -nom, le nom de la personne possédant le compte ;
  • -et d'autres informations, concernant le mot de passe, l'adresse mail, des préférences sur le site, etc., que nous ne détaillons pas ici.
• -La table ressources possède un enregistrement par document téléversé sur le site. Ses attributs sont :
  • -id, un identifiant numérique, unique pour chaque ressource ;
  • -owner, l'identifiant de la personne ayant créé la ressource ;
  • -titre, une chaine de caractères décrivant la ressource ;
  • -type, chaine de caractères pouvant être cours, ds, tp ou td.
• -La table chargement mémorise chaque fois qu'un utilisateur télécharge une ressource sur le site. Ses attributs sont :
  • -date, date du téléchargement, par exemple '2021-02-28' pour le 28 février 2021 (on peut utiliser des opérations de comparaison classiques avec ce format) ;
  • -id_u, identifiant de l'utilisateur qui télécharge la ressource ;
  • -id_r, identifiant de la ressource téléchargée.

• Question 21 Écrire une requête SQL permettant de connaitre le nombre total de ressources de type cours présentes sur le site.
• Question 22 Que fait la requête suivante : ?

SELECT ressource.titre, comptes.nom
FROM chargement
    JOIN ressources ON ressouces.id = chargement.id_r
    JOIN comptes ON comptes.id = chargement.id_u
ORDER BY chargement.date DESC
LIMIT 1

• Question 23 Écrire une requête SQL qui permet de déterminer la liste des triplets (x, y, n), signifiant que la personne possédant l'identifiant x a téléchargé n fois des documents téléversés par la personne possédant l'identifiant y.

• Question 24 Écrire une requête SQL qui renvoie la table des couples (x, y) de E.

5 Composantes connexes

Figure 3 - Un graphe G_(ex)

g_ex_a = [
    (0, 1), (0, 2), (0, 3), (1, 0), (1, 4), (1, 8),
    (2, 0), (2, 3), (3, 0), (3, 2), (3, 6),
    (4, 1), (5, 6), (6, 3), (6, 5),
    (7, 9), (8, 1), (9, 7)
    ]

g_ex_b = [ [1, 2, 3], [0, 4, 8], [0, 3],
    [0, 2, 6], [1], [6], [3, 5] [9], [1], [7]
    ]

• Question 25 Écrire une fonction adjacences(n, li) qui prend en argument un entier n correspondant à |V| et li, une liste de couples correspondant à un ensemble E (comme par exemple g_ex_a) dans un ordre quelconque, et renvoyant la représentation du graphe G(V, E) sous forme de listes d'adjacences (comme par exemple g_ex_b).

class Arbre():
    def __init__(self, sommet):
        self.sommet = sommet
        self.children = []
    def add_child(self, child):
        self.children.append(child)
def parcours(listes_adjacences):
    n = len(listes_adjacences)
    deja_vu = [False] * n
    def explorer(i):
        arbre = Arbre(i)
        voisins = listes_adjacences[i]
        for s in voisins:
            if not deja_vu[s]:
                deja_vu[s] = True
                arbre.add_child(explorer(s))
        return arbre
    res = []
    for i in range(n):
        if not deja_vu[i]:
            deja_vu[i] = True
            res.append(explorer(i))
    return res

• Question 26 Quel est le type de la valeur renvoyée par la fonction parcours ? Appliquer à la main cette fonction sur la liste d'adjacence g_ex_b du graphe G_(ex) de la figure 3, et représenter la valeur de retour de cette fonction. Quel est le nom de ce parcours ?
• Question 27 Montrer que la complexité de la fonction parcours est en O(|V| + |E|). Dans toute la suite, on dira qu'un algorithme ayant cette complexité est linéaire.
• Question 28 Rappeler la définition de la connexité d'un graphe.
• Question 29 Écrire une fonction connexe(listes_adjacences) qui renvoie True si le graphe décrit par les listes d'adjacences listes_adjacences est connexe et False sinon.
• Question 30 Écrire une fonction composantes_connexes(p_graphe) prenant en argument p_graphe le graphe obtenu avec la fonction parcours et renvoie les composantes connexes sous forme de liste de listes de sommets.
• Question 31 Quelle est la limitation liée au fait que la fonction explorer, programmée en Python, est récursive ?

6 Graphes biconnexes

• - |V| = 1;
• - |V| = 2, V = {a, b} et (a, b) ∈ E;
• -ou |V| ≥ 3 et pour toute paire (x, y) ∈ V^2, il existe un cycle élémentaire contenant x et y.

• Question 32 Montrer qu'un graphe biconnexe est également connexe.
• Question 33 Donner un exemple de graphe connexe mais pas biconnexe.

• Question 34 Sur le graphe G_(ex)^′ de la figure 4, donner les points d'articulations.

Figure 4 - Le graphe connexe G_(ex)^′

• Question 35 Soit G(V, E) possédant un point d'articulation. Montrer que G n'est pas biconnexe.
• Question 36 Inversement, supposons G(V, E) un graphe sans point d'articulation, et tel que |V| ⩾ 3. Considérons deux sommets x et y.

• 1.Justifier qu'il existe une chaine ( x_0 = x, x_1, …, x_k = y ) dans le graphe.
• 2.Montrer qu'il existe un cycle élémentaire contenant x_0 et x_1.
• 3.Pour i ⩾ 1, on suppose qu'il existe un cycle élémentaire C contenant x_0 et x_i. Montrer qu'il existe alors un cycle élémentaire contenant x_0 et x_(i + 1). On pourra distinguer deux cas selon que C contient ou non x_(i + 1).
• 4.En déduire que G est biconnexe.

• Question 37 Expliquer comment on peut déterminer si un sommet particulier est un point d'articulation à l'aide d'un parcours en profondeur.
• Question 38 En déduire un algorithme qui prend en entrée un graphe connexe décrit par ses listes d'adjacences, et détermine si ce graphe est biconnexe en utilisant la propriété précédente. On ne demande pas de programmer cet algorithme en Python. Quelle serait sa complexité en fonction des caractéristiques |E| et |V| du graphe ?

7 Algorithme efficace pour déterminer les points d'articulation

def parcours(listes_adjacences):
    n = len(listes_adjacences)
    deja_vu = [False] * n
    prefixe = [-1] * n
    count = 1
    def explorer(i):
        nonlocal count
        prefixe[i] = count
        count += 1
        arbre = Arbre(i)
        voisins = listes_adjacences[i]
        for s in voisins:
            if not deja_vu[s]:
                deja_vu[s] = True
                arbre.add_child(explorer(s))
        return arbre
    deja_vu[0] = True
    return explorer(0), prefixe

• Question 39 Donner les valeurs de la liste prefixe renvoyée par le programme ci-dessus si on l'applique sur le graphe G_(ex)^′ de la figure 4. On supposera que les voisins sont rangés par ordre croissant de leur numéro dans les listes d'adjacences.
• Question 40 Soit G un graphe connexe dans lequel on réalise le parcours avec la fonction ci-dessus, et soit (i, j) une arête de G telle que prefixe[i] < prefixe[j]. Montrer que j est un descendant de i dans l'arbre.

• Question 41 Sur le graphe G_(ex)^′ de la figure 4, donner pour chaque sommet les valeurs de ord[i], en se basant sur les valeurs obtenues à la question 39.

• Question 42 Écrire une fonction points_articulation(listes_adjacences) qui renvoie la liste des points d'articulation d'un graphe. On fera attention à traiter la racine de l'arbre comme un cas particulier.

• Question 43 Sur le graphe G_(ex)^′ de la figure 4, donner la liste des composantes biconnexes.
• Question 44 Décrire un algorithme qui renvoie les composantes biconnexes d'un graphe avec une complexité linéaire. On ne demande pas de programmer cet algorithme.