E3A Option Informatique MP 2005Sujet

Pas encore noté

Explorer les annales

BanqueE3A Année2005 FilièreMP MatièreInformatique

Annales E3A MP Informatique E3A MP 2005 MP Informatique Informatique 2005

Téléchargements

Télécharger le sujet (PDF)

Lire en ligne LaTeX Word

Corrigé : pas encore disponible
Rapport du jury : non disponible

Ces sujets peuvent vous intéresser

Pas encore de corrigé pour ce sujet : voici des sujets proches corrigés.

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.

Sujet en PDF

CONCOURS ENSAM - ESTP - EUCLIDE - ARCHIMEDE

Epreuve d'Informatique MP

durée 3 heures

L'usage de la calculatrice n'est pas autorisé

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

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

Exercice 1
a) Ecrire la procédure

indicesMax donnée T:tableau d'entiers
    l:entier
    résultat m:entier
    n: entier

qui retourne le plus petit et le plus grand des indices correspondant à la valeur maximale d'un tableau de longueur

l

.
b) Ecrire la fonction

moyenneNotesMinorées données $L$ :liste d'entiers
        $a$ : entier
    résultat $x$ : réel

qui retourne la moyenne des notes supérieures ou égales à l'entier a dans une liste de notes. Cette liste contient des notes, qui sont des nombres compris entre 0 et 20 , et se termine par la valeur -1 . Dans le cas où cette liste ne comporte aucune note supérieure ou égale à l'entier

a

, la fonction moyenneNotesMinorées retournera la valeur -1 et affichera un message d'avertissement.

Exercice 2

a) Que calcule le programme suivant :

$u \leftarrow 0$
$v \leftarrow 50$
tant que $v>0$ faire
    $u \leftarrow u+v^{2}$
    $v \leftarrow v-1$
fin tant que
afficher(u)

b) Que calculent les fonctions suivantes :

    A( $n$ : entier )
            si $(n \geq 0) \quad$ faire $\mathrm{A}(n) \leftarrow n$
            sinon faire $\mathrm{A}(n) \leftarrow-n$
P ( $n$ : entier)
    $n \leftarrow \mathrm{~A}(n)$
    si $(n=0) \quad$ faire $\mathrm{P}(n) \leftarrow 0$
    sinon, $\quad$ si $(n=1) \quad$ faire $\mathrm{P}(n) \leftarrow 1$
        sinon $\quad$ faire $\mathrm{P}(n) \leftarrow \mathrm{P}(n-2)$
$\mathrm{S}(m:$ entier $, n:$ entier $)$
        si $(\mathrm{A}(m) \leq \mathrm{A}(n)) \quad$ faire $\mathrm{S}(m, n) \leftarrow \mathrm{A}(m)$
        sinon $\quad$ faire $\mathrm{S}(m, n) \leftarrow \mathrm{A}(n)$

    D( $m:$ entier $, n:$ entier )
si $(m=0) \quad$ faire $\mathrm{D}(m, n) \leftarrow \mathrm{A}(n)$
si $(n=0) \quad$ faire $\mathrm{D}(m, n) \leftarrow \mathrm{A}(m)$
si $(m \neq 0)$ et si $(n \neq 0)$ faire
si $(\mathrm{P}(m)=0)$ et $(\mathrm{P}(n)=0)$ faire $\mathrm{D}(m, n) \leftarrow 2 * \mathrm{D}(m / 2, n / 2)$
si $(\mathrm{P}(m)=0)$ et $(\mathrm{P}(n)=1) \quad$ faire $\mathrm{D}(m, n) \leftarrow \mathrm{D}(m / 2, n)$
si $(\mathrm{P}(m)=1)$ et $(\mathrm{P}(n)=0)$ faire $\mathrm{D}(m, n) \leftarrow \mathrm{D}(m, n / 2)$
si $(\mathrm{P}(m)=1)$ et $(\mathrm{P}(n)=1) \quad$ faire $\mathrm{D}(m, n) \leftarrow \mathrm{D}(\mathrm{A}(n)-\mathrm{A}(m), \mathrm{S}(m, n))$

Exercice 3

Soit

n

un entier naturel. On dit que c'est un 2 -palindrome si son écriture en base 2 est la même qu'elle soit écrite de gauche à droite ou de droite à gauche. Plus précisément, si

n = \sum_(i = 0)^k a_i 2^i

, avec

a_0, \dots, a_k

dans

{0, 1}

a_k = 1, n

est un 2-palindrome si

a_i = a_(k - i)

, pour tout entier

i

dans

{0, \dots, k}

. Par exemple, les entiers 3 (11), 5 (101), 7 (111), 9 (1001), et 15 (1111) sont des 2-palindromes. Ecrire un programme qui calcule les 2-palindromes

n

tels que

n \leq 511

Exercice 4

On considère l'alphabet à deux lettres:

Σ = {a, b}

.
Dans toute la suite, on fixe

ω

un mot non vide sur l'alphabet

Σ

; on note

n

la longueur de

ω

(c'est à dire son nombre de lettres) et

a_1, \dots, a_n

ses

n

lettres lues de gauche à droite, c'est à dire que

ω = a_1 a_2\dotsa_n

.
Soit

A_ω = (Q, Δ, 1, {n + 1})

un automate sur l'alphabet

Σ

défini par :

$Q$ , l'ensemble des états de $A_ω$ , est l'ensemble ${1, 2, \dots, n, n + 1}$ ,
$Δ$ , l'ensemble des transitions de $A_ω(Δ \subset Q \times Σ \times Q)$ , est l'ensemble :
${(1, a, 1), (1, b, 1), (i, a_i, i + 1), ∀i ∈ {1, …, n}};$
1 est l'état initial de $A_ω$ ,
$n + 1$ est l'unique état final de $A_ω$ .

On note

L(A_ω)

le langage reconnu par l'automate

A_ω

On suppose que $ω$ est la lettre $a$ . Donc $n = 1$ .
(a) Représenter l'automate $A_a$ et justifier que $L(A_a)$ est le langage des mots se terminant par un $a$ .
(b) Donner une expression rationnelle de $L(A_a)$ .
(c) On considère l'automate $B$ représenté sur la figure 1 .

Figure 1: Automate

B

i. Démontrer que l'automate

B

est déterministe.
ii. Démontrer que le langage reconnu par l'automate

B

est égal à

L(A_a)

.
2. On suppose ici que

n > 1

et que les lettres de

ω

sont toutes égales à

a

(

∀i ∈ {1, …, n}, a_i = a

).
(a) Représenter l'automate

A_ω

et décrire le langage

L(A_ω)

dans ce cas.

On se propose de déterminiser l'automate

A_ω :

On applique à

A_ω

l'algorithme de déterminisation et on note

C_ω

l'automate ainsi obtenu.
(b) Montrer que les états de

C_ω

sont :

{1}, {1, 2}, {1, 2, 3}, \dots, {1, 2, \dots, i - 1, i}, \dots, {1, 2, \dots, n}{1, 2, \dots, n, n + 1}

, et que les transitions de

C_ω

sont alors :

({1}, $b, {1}$ ),
({1}, $a, {1, 2})$ ,
$- ({1, 2, \dots, i - 1, i}, b, {1})$ , pour tout $i$ dans ${2, \dots, n + 1}$ ,
$- ({1, 2, \dots, i - 1, i}, a, ({1, 2, \dots, i, i + 1})$ , pour tout $i$ dans ${2, \dots, n + 1}$ ,
$- ({1, 2, \dots, n, n + 1}, a, ({1, 2, \dots, n, n + 1})$ .
(c) Quel est l'état initial de $C_ω$ ?
(d) Quels sont les états finaux de $C_ω$ ?
(e) Représenter $C_ω$ .

On suppose que $n$ est pair et que $a_i = a$ lorsque $i$ est impair, $a_i = b$ lorsque $i$ est pair, c'est à dire que $ω = abab\dotsab$ . Construire un automate déterministe qui reconnait l'ensemble des mots finis sur l'alphabet $Σ$ qui se terminent par $ω$ .

Exercice 5

Soient $g_1, g_2, g_3$ trois fonctions booléennes. Justifier l'égalité : $g_1 + g_2 g_3 = (g_1 + g_2)(g_1 + g_3)$ .
Une fonction booléenne est dite affine si elle se décompose comme une somme de variables. Par exemple, $x + y + u$ et $x + v$ sont des fonctions affines des variables $x, y, u, v$ . On considère la fonction booléenne $f$ des 5 variables $u, v, x, y, z$ , définie par :

f(u, v, x, y, z) = uv + vxy + vxz + uyz.

Décomposer

f

comme un produit de fonctions booléennes affines (on pourra utiliser la question 1.).
3. Le directeur d'une banque souhaite, qu'en son absence, certains de ses collaborateurs, regroupés par deux ou trois selon un protocole établi précisément, puissent ouvrir le coffre. Pour cela, la porte du coffre est munie de

n

serrures et les

n

clés correspondantes sont nécessaires à l'ouverture de la porte. Le directeur dispose des clés des serrures en nombre suffisant et il en distribue certaines à ses collaborateurs de façon à ce que les seules possibilités soient :

Ulysse et Victoire peuvent à eux deux ouvrir le coffre
Victoire, Xavier et Yves peuvent à eux trois ouvrir le coffre,
Victoire, Xavier et Zoé peuvent à eux trois ouvrir le coffre,
Ulysse, Yves et Zoé peuvent à eux trois ouvrir le coffre.

Déterminer le nombre minimal de serrures du coffre et une distribution convenable des clés.

Pas de description pour le moment

Commentaires• E3A Option Informatique MP 2005

Connectez-vous pour participer aux discussions

Partagez vos avis, posez des questions et échangez avec la communauté

Chargement des commentaires...