CCINP Option Informatique MP 2026Sujet

ÉPREUVE MUTUALISÉE AVEC E3A-POLYTECH ÉPREUVE SPÉCIFIQUE - FILIÈRE MP

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.

PROBLÈME 1
Multiplication de grands entiers

• Q1.Quelle est la conséquence de cette contrainte matérielle sur l'ensemble des entiers que peut manipuler un programme ? Est-ce le cas en Python?

• Q2.Donner le code d'une fonction bit_to_int(bit_lst) prenant en argument une liste de bits et renvoyant la valeur de l'entier correspondant. Cette fonction devra avoir une complexité linéaire en la taille de la liste qu'il n'est pas nécessaire de justifier.
• Q3.Expliquer en français les grandes lignes d'un algorithme pour réaliser la somme de deux entiers représentés sous forme de listes de bits.
• Q4.Donner le code d'une fonction sum_bits(b_lst_1, b_lst_2) réalisant l'addition de deux entiers encodés par liste de bits. Cette fonction prendra en argument deux listes de bits et renverra une nouvelle liste de bits correspondant à la somme des deux entiers encodés par les arguments. Il est interdit de convertir ces listes de bits en entiers, de faire la somme avec + et de reconvertir vers une liste de bits. On pourra supposer que les deux listes sont de même longueur.

• Q5.Implémenter une fonction complement(lst_bits, size) qui complémente la liste de bits de manière à lui donner la taille size sans changer la valeur représentée. Votre programme vérifiera que l'entier size est supérieur à la taille de la liste des bits passée en argument et si cette assertion n'est pas vérifiée, interrompra l'exécution du programme. Votre fonction ne modifiera pas la liste passée en argument, mais en renverra une nouvelle.
• Q6.Donner le code d'une fonction int_to_bit permettant d'obtenir la liste des chiffres de la décomposition en base b = 2 d'un entier passé en argument. On pourra s'appuyer sur la valeur de n modulo b dans l'expression de sa décomposition et regarder l'effet d'une division entière de n par b avec cette expression.

• a)décomposant les listes de bits de u et v en ( d_u, f_u ) et ( d_v, f_v ) respectivement,
• b)calculant récursivement les 4 produits d_u × d_v, f_u × d_v, f_v × d_u et f_u × f_v,
• c)faisant les multiplications par les puissances de b : b^(k/2)(f_u × d_v + f_v × d_u) et b^k(f_u × f_v),
• d)additionnant les trois termes obtenus pour respecter l'égalité (1).

• Q9.Indiquer ce à quoi correspond la multiplication par b^i d'un nombre vis-à-vis de sa représentation sous forme de la liste de chiffres en base b (étape c ).
• Q10.Implémenter une fonction shift(lst_bits, i) qui réalise cette opération sur une liste de bits passée en argument. Cette fonction renverra une nouvelle liste sans modifier celle passée en argument.

def karatsuba(lst1, lst2):
    n = max (len(lst1), len(lst2))
    lst1 = complement(lst1, n)
    lst2 = complement(lst2, n)
    if n == 0:
        # A : compléter ici
    if n == 1:
        # B : compléter ici
    else:
        h = n//2
        d1 = lst1[0:h]
        f1 = lst1[h:]
        d2 = lst2[0:h]
        f2 = lst2[h:]
        # C : compléter ici

• Q11.Compléter les parties A, B et C du code proposé pour qu'il implémente la méthode de Karatsuba. Plusieurs lignes peuvent être nécessaires pour compléter certaines parties.

PROBLÈME 2 Ensembles de mots implémentés par tries

• Q13.Comment pourrait-on utiliser un dictionnaire pour représenter des ensembles de mots lorsque l'objectif est de vérifier si un mot appartient à un ensemble?

Figure 1 - Un exemple de trie

• Q15.Implémenter une fonction string_to_list : string -> char list qui s'évalue en la liste des caractères de la chaîne passée en argument. Par exemple, string_to_list "lettre" s'évaluera en ['l'; 'e'; 't';'t';'r';'e']. On pourra s'appuyer sur une fonction auxiliaire si besoin, mais dans ce cas on prendra soin d'expliquer le rôle de cette fonction. La fonction aura une complexité linéaire en la taille de la chaîne qu'on justifiera.

type trie = Node of bool * (char * trie) list

Node (false,
    [(']',
        Node (false,
            [('e', Node (true, [('s', Node (true, []))])); ('a', Node (true,
    []))]))])

Figure 2 - Un exemple de petit trie

• Q16.Implémenter une fonction empty_trie : unit -> trie qui renvoie le trie vide ayant le moins de nœuds possible.
• Q17.Implémenter une fonction récursive max_list : int list -> int qui renvoie le plus grand élément d'une liste supposée non vide.
• Q18.Implémenter une fonction récursive list_map : ('a -> 'b) -> 'a list -> 'b list qui prend en argument une fonction f et une liste lst et renvoie la liste des images par f des éléments de lst, dans le même ordre. Il est interdit d'utiliser la fonction List.map dans cette question.
• Q19.Implémenter une fonction height : trie -> int qui calcule la hauteur d'un trie (la définition de la hauteur d'un trie est la même que pour un arbre quelconque). On pourra s'appuyer sur les deux fonctions précédentes.

let rec f t =
    match t with
    |Node (true, []) -> 1
    |Node (false, []) -> 0
    |Node (b, (letter,child)::tail) -> (f child) + (f (Node (b, tail)))

• -( q et q^′ sont tous deux finaux) ou ( q et q^′ sont tous deux non finaux),
• - ∀c ∈ Σ, soit c est un blocage pour q et q^′, soit δ(q, c)Eδ(q^′, c).

PROBLÈME 3
Logique implicationnelle

• -une syntaxe S, qui décrit la façon dont il faut écrire les formules du système,
• -une sémantique M, qui explique le sens à leur donner,
• -un système de déduction D, qui établit les règles syntaxiques permettant de faire des preuves.

• - S_P est l'ensemble des formules définies inductivement à partir de ⊤, ⊥ et des variables propositionnelles à l'aide des connecteurs classiques ∧, ∨, ¬ et →,
• - M_P est la sémantique standard construite à partir des tables de vérité pour ∧, ∨, ᄀ et →,
• - D_P est la déduction naturelle, dont les règles sont rappelées en annexe 1.

• -Les formules de S_I sont définies par induction de la façon suivante :
  • -les symboles ⟂, T et les variables propositionnelles sont des formules de S_I,
  • -si A et B sont des formules de S_I, alors A → B également.

• -La sémantique M_I est la sémantique standard.
• -Le système de déduction D_I est donné par les règles de déduction suivantes :
  (Γ, A⊢A^–)/(Γ⊢((A → B) → A) → A), Peirce; (Γ⊢A → B Γ⊢A)/(Γ⊢B), elim- →, (Γ, A⊢B)/(Γ⊢A → B) intro- →

• 1. A⊢(A → B) → B
• 2. A → B, B → C⊢A → C
• 3. (A → B) → C, A → C⊢C. On pourra utiliser l'instance suivante de la loi de Peirce : ((C → B) → C) → C.

• Q40.On note D le système de déduction constitué des règles de D_P auxquelles on a enlevé le raisonnement par l'absurde et ajouté la loi de Peirce. Montrer réciproquement que la règle du raisonnement par l'absurde est dérivable dans D. On pourra utiliser l'instance suivante de la loi de Peirce : ((A→⊥) → A) → A.
• Q41.Que peut-on dire de D ? Justifier brièvement.

Annexe 1
Règles de la déduction naturelle

• -Axiome :
  Γ, A⊢A^–^(ax)
• -Affaiblissement :
  (Γ⊢A)/(Γ, B⊢A) aff
• -Introduction et élimination de l'implication :
  (Γ, A⊢B)/(Γ⊢A → B) intro- → (Γ⊢A → B Γ⊢A)/(Γ⊢B) elim- →
• -Introduction et éliminations du et :
  (Γ⊢A Γ⊢B)/(Γ⊢A ∧ B) intro- ∧ (Γ⊢A ∧ B)/(Γ⊢A) elim- ∧ (Γ⊢A ∧ B)/(Γ⊢B) elim- ∧
• -Introductions et élimination du ou :
  (Γ⊢A)/(Γ⊢A ∨ B) intro- ∨ (Γ⊢B)/(Γ⊢A ∨ B) intro- ∨ (Γ⊢A ∨ B)/(Γ, A⊢C) Γ, B⊢C elim- ∨
• -Introdution et élimination du non :
  (Γ, A⊢⊥)/(Γ⊢¬A) intro-¬ (Γ⊢A Γ⊢¬A)/(Γ⊢⊥) elim-¬
• -Élimination du ⊥ :
  (Γ⊢⊥)/(Γ⊢A) elim-⟂
• -Raisonnement par l'absurde :
  (Γ, ¬A⊢⊥)/(Γ⊢A)ra