CCINP Informatique Commune TSI 2026Sujet

ÉPREUVE SPÉCIFIQUE - FILIÈRE TSI

INFORMATIQUE

• -Utiliser uniquement un stylo noir ou bleu foncé non effaçable pour la rédaction de votre composition ; d'autres couleurs, excepté le vert, bleu clair ou turquoise, peuvent être utilisées, mais exclusivement pour les schémas et la mise en évidence des résultats.
• -Ne pas utiliser de correcteur.
• -Écrire le mot FIN à la fin de votre composition.

Autour de jeux

Partie I - Des algorithmes pour résoudre le problème des n reines

• -les sous-parties I. 4 et I. 5 nécessitent d'admettre la question Q11 si elle n'a pas été traitée;
• -la sous-partie I. 6 nécessite d'admettre la question Q17 si elle n'a pas été traitée;
• -la sous-partie I. 7 nécessite d'admettre la question Q10 si elle n'a pas été traitée.

Figure 1 - Diagonales dans le cas n = 4

Figure 2 - Une reine a été placée : les cases qu'elle contrôle et qui ne peuvent pas être occupées par d'autres reines sont figurées par le symbole *

I. 1 - Introduction

Figure 3 - Cas n = 3 : deux reines contrôlent toutes les cases

Figure 4 - Deux exemples de configurations pour n = 4

Figure 5 - Un exemple de configuration gagnante pour n = 5

I. 2 - Mise en place d'un affichage

• Q3.Écrire une fonction ligne prenant pour paramètre un entier naturel n et qui renvoie une liste de taille n constituée uniquement de 0.
  Par exemple, pour n = 5, l'appel ligne(5) renverra [0, 0, 0, 0, 0].
  Remarque : l'utilisation de structures de données du module numpy comme array n'est pas autorisée.
• Q4.Écrire une fonction grille prenant pour paramètre un entier n et qui renvoie une liste de n listes distinctes, chacune contenant n fois l'entier 0.
  Parexemple, pour n = 3, l'appel grille (3) renverra [ [0, 0, 0 ], [0, 0, 0], [0, 0, 0]].

• Q5.
  Compléter la fonction remplir prenant pour paramètre une liste L de taille n représentant une configuration. Cette fonction crée une grille de taille n × n ne contenant que des zéros. Puis, elle remplace G[i][j] par la valeur 1 lorsque L[i] = j. Enfin, elle renvoie la grille ainsi obtenue.
  Remarque : une fonction ayant une complexité temporelle en O(len(L)) (c'est-à-dire linéaire en la taille de la liste) sera valorisée.
  Par exemple, pour n = 4 :

  >>> G = remplir([1, 3, 0, 2])
  >>> G
  [[0, 1, 0, 0], [0, 0, 0, 1], [1, 0, 0, 0], [0, 0, 1, 0]]
  

• Q6.
  La représentation des grilles produite par l'interpréteur n'est pas visuellement satisfaisante (pour l'utilisateur). Écrire une fonction affiche qui prend pour paramètre une grille G, qui ne renvoie rien mais affiche la grille G ligne par ligne.
  Par exemple :

  >>> G = remplir([1, 3, 0, 2])
  >>> G
  [[0, 1, 0, 0], [0, 0, 0, 1], [1, 0, 0, 0], [0, 0, 1, 0]]
  >>> affiche(G)
  [0, 1, 0, 0]
  [0, 0, 0, 1]
  [1, 0, 0, 0]
  [0, 0, 1, 0]
  

I. 3 - Tester si une configuration est valide

• -(a) tous les L[i] sont distincts;
• -(b) tous les L[i]+i sont distincts;
• -(c) tous les L[i]-i sont distincts;
• -(d) cette liste L est de taille n.
• Q7.Expliquer ce que traduit d'une part le respect de (a) et d'autre part le respect de (b) et (c) pour le problème considéré.

• Q8.Écrire une fonction tous_distincts prenant en paramètre une liste L de positions et renvoyant True si tous ses éléments sont distincts, False sinon. Cette fonction procède comme suit :
  • -on initialise un dictionnaire presents vide;
  • -on parcourt la liste L. Si on rencontre un élément x non encore présent parmi les clés du dictionnaire, on insère la clé x dans le dictionnaire avec comme valeur le booléen True (par exemple). Si par contre cet élément est déjà présent, on quitte la fonction en renvoyant le booléen False ;
  • -si le parcours complet de la liste n'a pas repéré de doublon, on renvoie True.

def tous_distincts2(L):
    n = len(L)
    for i in range(n):
        for j in range(i,n):
            if L[i] == L[j]:
                return True
    return False

• Q9.Écrire une version corrigée de la fonction tous_distincts2. Comparer la complexité temporelle des codes tous_distincts et tous_distincts2 (corrigé) dans le pire des cas, ceci pour une liste L de taille n donnée en paramètre. On justifiera en s'aidant des rappels sur la complexité donnés en annexe 2.
• Q10.Écrire une fonction est_possible prenant en paramètre une liste L de positions et qui renvoie un booléen indiquant si L satisfait simultanément les trois conditions (a), (b) et (c), ou pas. On pourra utiliser plusieurs appels à la fonction tous_distincts. Par exemple, est_possible([2, 4, 1, 7, 0, 6, 3, 5]) renvoie True et est_possible([3, 4, 1, 7, 0, 6, 2, 5]) renvoie False.
• Q11.Écrire une fonction est_solution prenant en paramètres une liste L de positions, un entier n représentant la taille de la grille et renvoyant un booléen indiquant si L satisfait simultanément les quatre conditions (a), (b), (c) et (d), ou pas.
  On part du principe que L contient uniquement des entiers de {0, 1, …, n − 1}, il est donc inutile de le vérifier.

I. 4 - Une première approche par recherche aléatoire

[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0].

• Q12.La fonction sample du module random peut renvoyer une permutation aléatoire d'une liste L. II y a plusieurs manières d'importer cette fonction. Sur le DR, compléter les codes pour utiliser sample comme indiqué.

• Q13.Écrire une fonction recherche_aleatoire prenant en paramètres deux entiers naturels non nuls n et N.
  Cette fonction crée d'abord la liste L = [0, 1, …, n − 1]. Ensuite, elle crée au maximum N permutations de L et teste si elles sont solutions du problème des n reines.
  Dès qu'une liste solution est trouvée, elle est renvoyée. En cas d'échec après N essais, la liste vide [] est renvoyée.

I. 5 - Déterminer toutes les permutations de L = [0, 1, …, n − 1]

• Q14.Écrire une fonction insertion prenant pour paramètres un entier x, une liste L, un indice i et renvoyant une nouvelle liste obtenue en :
  • -recopiant les termes de la liste L d'indices 0 à i-1 inclus;
  • -puis en ajoutant x à la position i;
  • -enfin, en recopiant les termes de la liste L depuis l'indice i jusqu'à l'indice len(L)-1 inclus.
  On renvoie donc une liste avec un élément de plus que la liste L : l'élément x inséré à l'indice i. Par exemple, l'appel insertion(5, [2, 3, 6, 4], 1) renvoie la liste [2, 5, 3, 6, 4] et l'appel insertion(5, [2, 3, 6, 4], 4) renvoie la liste [2, 3, 6, 4, 5].
  Attention : l'usage d'une quelconque fonction Python faisant cette insertion est bien sûr interdit ici.

L = [[0, 1], [1, 0]]
v = 2
P = []
for l1 in L:
    for i in range(v+1):
        p1 = insertion(v, l1, i)
        P.append(p1)

• Q15.Quel est le contenu de P à l'issue du premier passage dans la première boucle?
  Donner le contenu de P après l'exécution complète du code ci-dessus.
  (On demande à chaque fois de respecter l'ordre des différents éléments de P).
  Expliquez exactement ce que fait ce code.

• Q16.Compléter le code de la fonction permutations prenant en paramètre un entier n supérieur ou égal à 2 et renvoyant la liste de toutes les permutations possibles des entiers de 0 à n-1. (c'est-à-dire toutes les listes possibles contenant les entiers de 0 à n-1 une fois et une seule). Par exemple, permutations(3) renverra une liste de sous-listes de la forme suivante (les sous-listes n'étant pas forcément dans cet ordre) :
  [[0, 1, 2], [0, 2, 1], [2, 0, 1], [2, 1, 0], [1, 0, 2], [1, 2, 0]].
• Q17.En déduire une fonction configurations prenant en paramètre un entier n et renvoyant la liste de toutes les configurations satisfaisant les conditions imposées par le jeu.

I. 6 - Classer les configurations similaires

Figure 6 - Un exemple de symétrie horizontale, un exemple de rotation vers la droite

• Q18.On se place dans une grille de taille 5 × 5 et on considère la configuration initiale représentée par la liste L = [2, 4, 1, 3, 0] (figure 6).
  Donner, sous forme d'une liste d'entiers de 0 à 4, la liste L1 correspondant à une symétrie horizontale de la grille et la liste L2 correspondant à une rotation d'un quart de tour vers la droite de la grille.
  De façon générale, comment obtient-on la liste L1 correspondant à une symétrie horizontale à partir d'une liste L initiale?
• Q19.Écrire une fonction symetrie prenant en paramètre une liste L représentant une configuration et renvoyant la liste correspondant à une symétrie horizontale de la grille.
  Par exemple, cette fonction appliquée à [1, 0, 2] renvoie [2, 0, 1].
  Attention : l'usage de la méthode reverse, de la fonction reversed ou du slicing L[::-1] est interdit ici.
• Q20.Écrire une fonction rotation prenant en paramètre une liste L représentant une configuration et renvoyant la liste correspondant à la configuration obtenue par rotation d'un quart de tour vers la droite : chaque reine à la position ligne i/colonne L[i] se retrouve, après rotation, à la position ligne L[i]/colonne n-1-i.
  Par exemple, cette fonction appliquée à [2, 5, 3, 1, 7, 4, 6, 0] renvoie [0, 4, 7, 5, 2, 6, 1, 3].

def partition(n):
    C = configurations(n)
    P = []
    for c in C:
        test = False
        for elt in P:
            if similaires(elt[0],c):
                elt.append(c)
                test = True
        if test == False:
            P.append([c])
    return P

1.7 - Des graphes pour aller plus vite et plus loin

• -dès que l'on trouve une solution au problème, on arrête le parcours et on renvoie cette solution;
• -on revient en arrière (c'est-à-dire à l'étape précédente) quand on obtient une grille invalide ;
• -en cas de parcours complet du graphe sans avoir trouvé de solution, on renvoie la valeur -1 ;
• -on ne visite a priori pas la totalité des sommets du graphe, ce qui est un facteur de rapidité.

Figure 7 - Un extrait du graphe des coups pour une grille 4 × 4

• Q22.Une fonction resout_graphe prend en paramètre un entier n ⩾ 4 correspondant à la taille de la grille et renvoie une liste gagnante de positions ou -1 si aucune solution n'a été trouvée. Elle utilise une fonction explore.
  Compléter les zones en pointillés dans la fonction explore pour que la fonction resout_graphe effectue le travail demandé.

• Q23.L'exploration du graphe de la question Q22 s'arrête dès qu'une solution est trouvée. On peut décider de continuer l'exploration du graphe pour déterminer les autres solutions au problème. On se propose ici de seulement compter le nombre de solutions grâce à une fonction compte prenant en paramètre un entier n ⩾ 4 correspondant à la taille de la grille.
  Compléter les zones en pointillés dans la fonction explore2 pour que la fonction compte effectue le travail demandé.

Partie II - Base de données d'un serveur de jeu en ligne

• -la table Clients contient des informations sur les utilisateurs du site. Elle est constituée des attributs suivants :
  • -id_client (clé primaire) : identifiant unique du client, nombre entier ;
  • -nom : nom du client, chaîne de caractères ;
  • -prenom : prénom du client, chaîne de caractères ;
  • -email : email du client, chaîne de caractères;
  • -date_inscription : date d'inscription du client au format 'JJ-MM-AAAA';
  • -anniversaire : jour anniversaire du client au format 'JJ-MM'.
• -la table Jeux contient des informations sur les jeux disponibles. Elle est constituée des attributs suivants :
  • -id_jeu (clé primaire) : identifiant unique du jeu, nombre entier;
  • -nom_jeu : nom du jeu, chaîne de caractères ;
  • -description : brève description du jeu, chaîne de caractères;
  • -prix : prix du jeu, nombre flottant.
• -la table Factures enregistre les transactions des achats de jeux. Elle est constituée des attributs suivants :
  • -id_facture (clé primaire) : identifiant unique de la facture, nombre entier;
  • -id_client (clé étrangère) : référence vers la table Clients, nombre entier;
  • -id_jeu (clé étrangère) : référence vers la table Jeux, nombre entier;
  • -date_achat : date d'achat du jeu au format 'JJ-MM-AAAA';
  • -montant : montant de la facture, nombre flottant.
• -la table Records qui enregistre les records ou scores des différents utilisateurs dans les jeux qu'ils ont achetés. Elle est constituée des attributs suivants :
  • -id_record (clé primaire) : identifiant unique du record, nombre entier;
  • -id_client (clé étrangère) : référence vers la table Clients, entier;
  • -id_jeu (clé étrangère) : référence vers la table Jeux, entier;
  • -score : score du joueur pour ce jeu, nombre entier;
  • -date_record : date du record au format 'JJ-MM-AAAA'.
• Q24.Le gestionnaire veut souhaiter leur anniversaire à ses clients et leur proposer un bon d'achat à cette occasion. Écrire une requête SQL permettant de récupérer le nom, le prénom et l'email des clients ayant leur anniversaire le 3 juillet.
• Q25.Le gestionnaire souhaite faire le récapitulatif des achats d'un client particulier. Écrire une requête SQL affichant le nom, le prénom et les dates des achats effectués par le client ayant pour email '[email protected]'.
• Q26.Le gestionnaire du site veut pouvoir identifier ses meilleurs clients. Écrire une requête SQL affichant le nom, l'email et le montant total dépensé pour chaque client du site. Attention, un client peut avoir fait plusieurs achats, il faudra donc faire la somme de tous ses achats.

• Q27.Le gestionnaire du site veut mettre à l'honneur les meilleurs scores pour chaque jeu, ceci sur la page d'accueil du site. Écrire une requête SQL affichant chaque nom de jeu avec le meilleur score pour ce jeu.

ANNEXE 1 - Base de données d'un site de jeux

ANNEXE 2 - Rappels de syntaxe Python