Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, d'une part il le signale au chef de salle, d'autre part il le signale sur sa copie et poursuit sa composition en indiquant les raisons des initiatives qu'il est amené à prendre.

L'usage de calculatrices est interdit.

AVERTISSEMENT

La présentation, la lisibilité, l'orthographe, la qualité de la rédaction, la clarté et la précision des raisonnements entreront pour une part importante dans l'appréciation des copies. En particulier, les résultats non encadrés et non justifiés ne seront pas pris en compte.

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 et une liste d'entiers et renvoyant une liste d'entiers dont la tête est et la queue .
Icons prenant en argument une liste d'entiers et une liste de listes d'entiers et renvoyant une liste de listes d'entiers dont la tête est et la queue .
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

On considère un rationnel

. On note

avec

. On s'intéresse au problème suivant : peut-on trouver des entiers

de sorte que :

Par exemple, on a:

On considère pour cela l'algorithme suivant :

[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

où

désignent le reste et le quotient de la division euclidienne de

par

, [ ] désigne la liste vide et la fonction add permet d'ajouter un élément en tête d'une liste.

Détailler l'exécution de l'algorithme sur les fractions et .
Prouver que l'algorithme ci-dessus termine et majorer sa complexité à l'aide de et .
Prouver que l'algorithme est correct.
On note, pour et et .
(a) Écrire la division euclidienne de par . (On pourra distinguer les cas et .)
(b) Prouver que l'exécution de l'algorithme sur et renvoie une liste de longueur .
(c) En déduire que la décomposition renvoyée par l'algorithme sur et est de longueur .
(d) Que peut-on en déduire quant à la complexité de l'algorithme?

2 Calcul des termes d'une suite double

On considère la suite double (

) définie pour

entiers naturels par :

Proposer un programme récursif prenant et en argument et renvoyant la valeur de . L'usage de variables auxiliaires n'est pas autorisé dans cette question.
On s'intéresse à la complexité en nombre d'additions et de multiplications nécessaires au calcul de par le programme proposé à la question précédente. On note le nombre d'opérations nécessaires au calcul de et .
(a) Déterminer suivant les valeurs de , de et de et en déduire les valeurs de et .
(b) Pour , justifier que est fini et montrer que .
(c) Pour , obtenir l'existence d'une constante telle que .
(d) Comment qualifier la complexité de votre programme?
En vous aidant d'un tableau de longueur , écrire une fonction calculant en opérations.

3 Énumération des parties d'un ensemble

Pour

, on note

l'ensemble

et on pose

. Une partie

de l'ensemble

est représentée par une liste

où :

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

4 Fonctions booléennes

Soit

. On convient de confondre les booléens «vrai» et «faux» avec les entiers 1 et 0 . On appelle fonction booléenne toute application :

4.1 Un opérateur universel

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

Soit . Montrer que toute fonction booléenne de dans peut s'écrire à l'aide des opérateurs et et des variables .
On pose . Montrer que toute fonction booléenne peut s'écrire uniquement à l'aide de l'opérateur et des variables .

4.2 Formules croissantes

On munit

de l'ordre produit :

On dit qu'une fonction booléenne

est croissante lorsque :

Donner un exemple de fonction telle que ni , ni ne soit croissante. (On justifiera soigneusement le contre-exemple.)
Peut-on affirmer que si est croissante alors et sont croissantes? (On donnera une preuve ou un contreexemple.)
Si est croissante, montrer que .
Montrer que la fonction est croissante si et seulement si elle est équivalente à une formule écrite à l'aide des opérateurs et , des variables et des fonctions constantes à 0 et 1 .

5 Préfixes et suffixes

Soit

un alphabet fini. Soit

. Un mot

est un préfixe de

lorsqu'il existe

tel que

et un mot

est un suffixe de

lorsqu'il existe

tel que

. Pour la suite, on pose :

Dresser la liste des préfixes de ainsi que la liste de ses suffixes.
Représenter graphiquement un automate déterministe reconnaissant exactement l'ensemble des préfixes de .
(a) Représenter graphiquement un automate non déterministe simple reconnaissant exactement l'ensemble des suffixes de .
(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.