E3A Option Informatique MP 2012Sujet

CONCOURS ARTS ET MÉTIERS ParisTech - ESTP - ARCHIMEDE

Durée 3 h

L'usage de calculatrices est interdit.

AVERTISSEMENT

Indiquer en tête de copie le langage de programmation, Caml ou Pascal, choisi pour l'ensemble du sujet.

• L'épreuve est constituée de cinq exercices totalement indépendants.
• Pour les candidats composant avec Pascal, on suppose disposer de deux types de listes : le type listes d'entiers Liste et le type liste de liste d'entiers Lliste. La liste vide sera représentée pour les deux types par nil et on suppose disposer des fonctions suivantes:
• cons prenant en argument un entier x et une liste d'entiers l et renvoyant une liste d'entiers dont la tête est x et la queue l.
• Icons prenant en argument une liste d'entiers x et une liste de listes d'entiers l et renvoyant une liste de listes d'entiers dont la tête est x et la queue l.
• tete (resp. Itete) qui renvoie la tête d'une liste d'entiers (resp. d'une liste de listes d'entiers).
• queue (resp. Iqueue) qui renvoie la queue d'une liste d'entiers (resp. d'une liste de listes d'entiers).

1 Décompositions rationnelles

[decompose p q=
    res:= []
    fonction aux a b=
        reste:=b mod a
        quotient:=b/a
            si reste=0 alors add (quotient,res)
                sinon add (quotient +1 ,res);aux (a-reste) (b*(quotient +1 ))
            fin si
    fin fonction
    aux p q
    renvoyer res

1. Détailler l'exécution de l'algorithme sur les fractions 5/8 et 3/7.
2. Prouver que l'algorithme ci-dessus termine et majorer sa complexité à l'aide de p et q.
3. Prouver que l'algorithme est correct.
4. On note, pour n ⩾ 1 et k ⩾ 1, α_n = n! + 1 et β_(k, n) = k(n!) + 1.
   (a) Écrire la division euclidienne de β_(k, n) par n. (On pourra distinguer les cas n = 1 et n ≠ 1.)
   (b) Prouver que l'exécution de l'algorithme sur p = n et q = β_(k, n) renvoie une liste de longueur n.
   (c) En déduire que la décomposition renvoyée par l'algorithme sur p = n et q = α_n est de longueur n.
   (d) Que peut-on en déduire quant à la complexité de l'algorithme?

2 Calcul des termes d'une suite double

1. Proposer un programme récursif prenant n et p en argument et renvoyant la valeur de S_n^p. L'usage de variables auxiliaires n'est pas autorisé dans cette question.
2. On s'intéresse à la complexité en nombre d'additions et de multiplications nécessaires au calcul de S_n^p par le programme proposé à la question précédente. On note C(n, p) le nombre d'opérations nécessaires au calcul de S_n^p et C_n = sup_(p ∈ ℕ)C(n, p) ∈ ℕ ∪ { + ∞}.
   (a) Déterminer suivant p ∈ ℕ les valeurs de C(0, p), de C(1, p) et de C(2, p) et en déduire les valeurs de C_0, C_1 et C_2.
   (b) Pour n ∈ ℕ, justifier que C_n est fini et montrer que C_n ⩽ 2^(n + 1).
   (c) Pour p ⩾ n ⩾ 1, obtenir l'existence d'une constante β > 1 telle que C(n, p) ⩾ β^n.
   (d) Comment qualifier la complexité de votre programme?
3. En vous aidant d'un tableau de longueur p + 1, écrire une fonction calculant S_n^p en O(np) opérations.

3 Énumération des parties d'un ensemble

1. (a) Soit A une partie de E_n représentée par une liste l et soit x ∈ E_n. Écrire des fonctions add et sub prenant en argument l et x et qui renvoient respectivement les listes représentant les parties A ∪ {x} et A∖{x}.
   (b) Écrire des fonctions récursives reunion et intersection prenant en argument deux listes l_1 et l_2 représentant deux parties A_1 et A_2 de l'ensemble E_n et renvoyant respectivement la réunion et l'intersection de A_1 et A_2.
2. (a) Écrire une fonction récursive parties prenant n et p en arguments et renvoyant la liste de toutes les parties à p éléments de l'ensemble E_n. Par exemple, lorsque n = 2 et p = 1, le résultat renvoyé est : [[1], [2]]; lorsque n = 2 et p = 0, le résultat renvoyé est [[]]. On pourra remarquer que l'ensemble des parties à p éléments se partitionne en l'ensemble des parties à p éléments contenant n et l'ensemble des parties à p éléments ne contenant pas n.
   (b) Détailler l'exécution de votre algorithme sur les entiers n = 3 et p = 2.

4 Fonctions booléennes

4.1 Un opérateur universel

1. Soit f une fonction booléenne. Justifier l'égalité :

2. Soit n ∈ ℕ^∗. Montrer que toute fonction booléenne de {0, 1}^n dans {0, 1} peut s'écrire à l'aide des opérateurs ¬, ∧ et ∨ et des variables x_1, x_2, …, x_n.
3. On pose A↑B = (¬A) ∨ (¬B). Montrer que toute fonction booléenne peut s'écrire uniquement à l'aide de l'opérateur ↑ et des variables x_1, x_2, …, x_n.

4.2 Formules croissantes

1. Donner un exemple de fonction f telle que ni f, ni ¬f ne soit croissante. (On justifiera soigneusement le contre-exemple.)
2. Peut-on affirmer que si f : {0, 1}^n → {0, 1} est croissante alors f_0 : (x_1, …, x_(n − 1)) ↦ f(x_1, …, x_(n − 1), 0) et f_1 : (x_1, …, x_(n − 1)) ↦ f(x_1, …, x_(n − 1), 1) sont croissantes? (On donnera une preuve ou un contreexemple.)
3. Si f est croissante, montrer que f_1 = f_0 ∨ f_1.
4. Montrer que la fonction f est croissante si et seulement si elle est équivalente à une formule écrite à l'aide des opérateurs ∧ et ∨, des variables x_1, x_2, …, x_n et des fonctions constantes à 0 et 1 .

5 Préfixes et suffixes

1. Dresser la liste des préfixes de u ainsi que la liste de ses suffixes.
2. Représenter graphiquement un automate déterministe reconnaissant exactement l'ensemble des préfixes de u.
3. (a) Représenter graphiquement un automate non déterministe simple reconnaissant exactement l'ensemble des suffixes de u.
   (b) Représenter graphiquement le résultat de l'application de l'algorithme de déterminisation sur l'automate obtenu à la question précédente.