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.

Indiquer en tête de copie ou de chaque exercice le langage utilisé

Quel que soit le langage utilisé, le candidat pourra supposer qu'il dispose d'une fonction test_liste_vide qui prend en entrée une liste et renvoie le booléen 1 si la liste est vide et 0 sinon.

Le candidat pourra, s'il le juge utile, supposer que chaque liste se termine par un élément de marquage de fin de liste appelé

Exercice 1

a) Ecrire la fonction :

Tri_denombrement
    données N:entier naturel
        L: liste d'entiers tous compris entre 1 et N
    résultat M:tableau de longueur N

qui prend en entrée un entier naturel non nul

et une liste

d'entiers tous compris entre 1 et

et renvoie le tableau de longueur

, dans lequel la

-ième case contient le nombre d'éléments égaux à

dans la liste

, pour tout entier

compris entre 1 et

.
b) Calculer en fonction de

étant la longueur de la liste

, et de

, le coût de ce tri dans le meilleur des cas, dans le pire des cas et en moyenne. On supposera que le temps d'accès à la

-ième case du tableau est linéaire en

, le reste des opérations ayant un coût négligeable.

Exercice 2
(les questions a et b sont indépendantes.)
a) Ecrire la fonction :

Matrice
    données L:liste
        n: entier
    résultat M: tableau à deux entrées de taille n,n

qui prend en entrée une liste

et l'entier

et renvoie le tableau des coefficients d'une matrice carrée de taille

remplie ligne par ligne de gauche à droite par les coefficients de la liste

. La liste contient des entiers relatifs. Si la liste

n'est pas suffisamment longue, la matrice est complétée par des 0 . Si la liste

est trop longue, le programme s'arrête lorsque la matrice est remplie.
b) Soit

un tableau rempli avec des entiers naturels. Un plateau de

de valeur

et de longueur

est une suite de

indices consécutifs

sur lesquels

prend la valeur

). Par exemple, le tableau

posséde un plateau de valeur 3 et de longueur 3 , un plateau de valeur 6 et de longueur 2 , deux plateaux de valeur 1 et de longueur 1 et deux plateaux de valeur 2 et de longueur 1 .
Ecrire la fonction :

LongueurMaxPlateau
    données T:tableau
        N: entier naturel
    résultat l:entier naturel

qui prend en entrée un tableau d'entiers naturels et sa longueur

et renvoie la plus grande longueur de ses plateaux.

Exercice 3

(les questions

et c sont indépendantes.)
a) Qu'effectue le programme ci-dessous :

$P R O G$ ( $L$ : liste d'entiers)
$L_{2} \leftarrow$ liste_vide
$E \leftarrow$ premier_element $(L)$
tant que ( $E<>N I L$ ) faire
    $E_{2} \leftarrow$ premier_element $(L 2)$
    $S W \leftarrow 0$
    tant que $\left(E_{2}<>N I L\right.$ et $\left.S W=0\right)$ faire
        $\operatorname{si}\left(E=E_{2}\right)$ alors $S W \leftarrow 1$
        sinon $E_{2} \leftarrow$ element_suivant $\left(L_{2}\right)$
        fin si
    fin faire
    si ( $S W=0$ ) alors $L_{2} \leftarrow$ ajouter_element $(E)$
    fin si
    $E \leftarrow$ element_suivant $(L)$
fin faire
retourner $L_{2}$

On remarquera que les listes considérées par ce programme se terminent par un élément de marquage de fin de liste appelé NIL.
b) Décrire l'exécution du programme

ci-dessous sur l'entrée

$N B S(N:$ entier strictement positif, $p:$ entier strictement positif))
si $(N<p)$ alors $S \leftarrow 0$
sinon si ( $p=1$ ) alors $S \leftarrow 1$
sinon $S \leftarrow N B S(N-1, p-1)+N B S(N-p, p)$
fin si
retourner $(S)$

Que calcule ce programme ?
c) Que calcule la procédure suivante :

$M S(N:$ entier, $T:$ tableau d'entiers de longueur $N$,
    $U \leftarrow-1$
    $m \leftarrow-1$
    $n \leftarrow-1$
    $S \leftarrow-1$
    $b \leftarrow 0$
pour $k$ de 1 à $N$ faire
        si $(b=0)$ et $(T[k] \geqslant 0)$ alors faire
                $b \leftarrow 1$
                $i \leftarrow k$
                $j \leftarrow i$
                $S \leftarrow T[k]$
            fin faire
        si ( $b=1$ )et ( $T[k] \geqslant 0$ ) alors faire
                $j \leftarrow k$
                $S \leftarrow S+T[k]$
            fin faire
        si $(T[k]<0)$ alors $b \leftarrow 0$
        fin si
        si $(k=N)$ alors $b \leftarrow 0$
        fin si
        si ( $b=0$ )et ( $S>U$ ) alors faire
                $U \leftarrow S$
                $m \leftarrow i$
                $n \leftarrow j$
            fin faire
        fin si
fin faire
retourner $(U, m, n)$

Exercice 4

Un nombre d'Armstrong est un nombre qui est égal à la somme des cubes des chiffres de son écriture en base 10 ; par exemple 153 est un nombre d'Armstrong puisque

. Ecrire un programme qui calcule tous les nombres d'Armstrong à trois ou quatre chiffres.

Exercice 5

Une liste d'entiers est dite convenable si elle se compose d'un nombre pair d'éléments

tels que

. On représente une réunion finie de

intervalles fermés disjoints dont les extrémités sont des entiers relatifs par la liste ordonnée de leurs extrémités, selon l'ordre croissant. On admet que cette liste est alors convenable. Par exemple,

est représentée par la liste

. L'ensemble vide est représenté par la liste vide.
a) Ecrire la procédure :

Convenable
    données L:liste d'entiers
    résultat b:booléen

qui prend en entrée une liste d'entiers

et retourne la valeur 1 si elle est convenable et 0 sinon.
b) On admet que l'intersection de deux réunions finies d'intervalles fermés disjoints dont les extrémités sont des entiers relatifs est aussi une réunion finie d'intervalles fermés disjoints dont les extrémités sont des entiers relatifs. Par exemple, l'intersection de

, représenté par la liste convenable

et de

, représenté par la liste convenable

, est

représenté par la liste convenable

. Ecrire la procédure :

Intersection
    données }\quad\mp@subsup{L}{1}{}\mathrm{ :liste convenable d'entiers
        L2:liste convenable d'entiers
    résultat L':liste convenable d'entiers

qui prend en entrée deux listes convenables d'entiers représentant chacune une réunion finie d'intervalles fermés disjoints, respectivement

, et retourne la liste convenable d'entiers représentant la décomposition en réunion finie d'intervalles fermés disjoints de l'ensemble

.
c) On admet que la réunion de deux réunions finies d'intervalles fermés disjoints dont les extrémités sont des entiers relatifs est aussi une réunion finie d'intervalles fermés disjoints dont les extrémités sont des entiers relatifs. Par exemple, la réunion de

, représenté par la liste convenable

et de

, représenté par la liste convenable

, est

représenté par la liste convenable

. Ecrire la procédure :

Reunion
    données Li:liste convenable d'entiers
        L2:liste convenable d'entiers
    résultat L':liste convenable d'entiers

qui prend en entrée deux listes convenables d'entiers représentant chacune une réunion finie d'intervalles fermés disjoints, respectivement

, et retourne la liste convenable d'entiers représentant la décomposition en réunion finie d'intervalles fermés disjoints de l'ensemble

Exercice 6

est un langage sur un alphabet fini

et si

est un entier naturel non nul, on note

le langage formé par les mots de

qui sont de longueur

Justifier que le langage est de cardinal fini.

Dans la suite, on note

le cardinal du langage

.
2. Dans cette question, l'alphabet

désigne l'alphabet à trois lettres

est le langage des mots finis sur

qui contiennent au moins un

. Ce langage est donné par l'expression rationnelle :

a) Dessiner un automate déterministe à deux états qui reconnait exactement le langage

.
b) Soit

un entier naturel non nul.
i) Dessiner un automate qui reconnait exactement le langage

.
ii) On suppose

. Soit

le langage

. Démontrer que

est la réunion disjointe des langages

. En déduire la relation de récurrence :

iii) Exprimer

en fonction de

.
3. Dans cette question, on suppose que

est le langage reconnu par un automate déterministe

où :

est l'ensemble fini des états de . On note son cardinal et on suppose que est un entier naturel . Les états dans sont numérotés de 1 à .
1 est le numéro de l'état initial de ,
est le numéro de l'unique état final de ,
est la fonction de transition de définie d'une partie de dans .

On considère la matrice

définie par :

est le nombre de transitions de source l'état

et de but l'état

dans l'automate

. On note

le polynôme caractéristique de la matrice

.
Pour tout état

, on note

le langage reconnu par l'automate (

); ainsi défini,

. Pour tout entier

, soit

le vecteur de coordonnées

où

est le cardinal du langage

, pour tout

dans

.
a) Expliciter les coordonnées du vecteur

en fonction de

.
b) Démontrer que, pour tout entier

et pour tout

dans

est la réunion disjointe des langages

pour tout (

) dans

tel que

.
c) En déduire, pour tout entier

, l'égalité

.
d) En utilisant le théorème de Cayley-Hamilton, démontrer que la suite

vérifie la relation de récurrence :

Dans le cas où

racines distinctes

, que peut-on en déduire pour la suite

?
4. Soit

le langage sur l'alphabet

reconnu par l'automate

ci-dessous :

Figure 1: Automate

a) Donner une expression rationnelle de

.
b) Expliciter la suite

Exercice 7

Soit

un entier naturel

. Soit

une fonction booléenne à

variables. On dit que

définit implicitement sa

-ième variable si pour tout

-uplet (

) de

, il existe un unique

dans

tel que

Dans cette question, . Soit la fonction boolénne définie par ses valeurs présentées dans la table ci-dessous :


0	0	1
0	1	0
1	0	0
1	1	1

Démontrer que

définit implicitement sa seconde variable. Expliciter toutes les fonctions booléennes sur

qui définissent implicitement leur seconde variable.

Soit

une fonction booléenne à

variables.
2. Démontrer que

définit implicitement sa

-ième variable si et seulement si

vérifie la propriété suivante :

Soit la fonction booléenne définie par :

Démontrer que

définit implicitement sa

-ième variable. Démontrer plus précisément qu'il existe une fonction booléenne

sur

, telle que

Préciser