ENS Informatique MP PC 2004Sujet et corrigé

Pas encore noté

Explorer les annales

BanqueX-ENS Année2004 FilièreMP/PC MatièreInformatique

Annales X-ENS MP/PC Informatique X-ENS MP/PC 2004 MP/PC Informatique Informatique 2004

Téléchargements

Télécharger le sujet (PDF)

Corrigé

Lire en ligne LaTeX Word

Rapport du jury : non disponible

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

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

Sujet en PDF

Filière MP (groupes MPI/MI)
Épreuve commune aux ENS de Paris et Cachan

Filière MP (groupe I)Épreuve commune aux ENS de Paris, Lyon et Cachan

Filière PC (groupe I)Épreuve commune aux ENS de Paris et Lyon

INFORMATIQUE

Durée : 4 heures

L'usage de calculatrices électroniques de poche à alimentation autonome, non imprimantes et sans document d'accompagnement, est autorisé. Cependant, une seule calculatrice à la fois est admise sur la table ou le poste de travail, et aucun échange n'est autorisé entre les candidats.

Le problème comporte 13 questions. Il est conseillé de traîter les questions dans l'ordre de l'énoncé, cependant on pourra aborder une question en admettant les résultats des précédentes. Les algorithmes demandés pourront être écrits dans un langage aux choix du candidat, en utilisant les structures de contrôle usuelles. On pourra par exemple utiliser un langage semblable à celui qui est décrit dans l'annexe A.

Un graphe

ET/OUG

est un triplet (

V, E, f

) où

V

est un ensemble fini (les sommets),

E

est un sous-ensemble de

V \times V

(les arêtes) et

f

est une application de

V

dans

{ \land, \lor }

. La taille

|G|

d'un graphe

ET/OU

est la somme du nombre de sommets

|V|

et du nombre d'arêtes

|E|

. La taille d'une liste est sa longueur. On pourra supposer que les sommets sont numérotés et donc que

V = {1, \dots, N}

. Les éléments de

V

sont de taille 1 .

S

est un ensemble, on note

2^S

l'ensemble des sous-ensembles de

S

. On pourra choisir de représenter un ensemble

S

d'éléments de

V

par une liste de taille

|S|

ou par un tableau de booléens de taille

|V|

On utilisera la structure de donnée des tableaux indicés par

V

à valeurs dans un type de donnée

Y

(tableaux de

Y

en abrégé) qui représentent les applications de

V

dans

Y

. On dispose pour de telles données

d'une fonction d'accès : $t(x)$ est la valeur de $t$ en $x$ si $t$ est un tableau de $Y$ et $x \in V$ . Un tel accès s'effectue en temps unitaire
d'une fonction d'initialisation init qui, étant donné $y \in Y$ , renvoie un tableau représentant la fonction constante égale à $y$ . Le coût de cette fonction est $|V|$ .
de primitives de modification : $t(x):=y$ modifie le tableau $t$ en remplaçant sa valeur en $x$ par $y$ . Cette opération a un coût unitaire. (Dans un langage fonctionnel, on pourra supposer l'existence d'une fonction de coût unitaire qui renvoie le tableau modifié).
Le temps nécessaire à l'exécution d'un algorithme sur la donnée $d$ sera supposé être le nombre d'opérations élémentaires effectuées : accès à un tableau, test d'égalité sur les données atomiques (éléments de $V$ ), test de vide d'une liste, accès au premier élément d'une liste (car), accès au reste d'une liste (cdr), ajout d'un élément à une liste (cons, : :), ajouter ou retrancher 1 à un entier, test à 0 d'un entier, or, and sur des données Booléennes. On utilisera la notation $O$ : par exemple, la complexité d'un algorithme est $O(1)$ si son temps d'exécution ne dépend pas de la donnée; il est $O(|d|)$ si son temps d'exécution est, dans le cas le pire, linéaire dans la taille $|d|$ de la donnée $d$ .

1 Accessibilité dans les graphes ET/OU

Dans cette partie,

G = (V, E, f)

désignera un graphe

ET/OU

. Si

g

est une application de

V

dans

2^V

, on dira que

g

est compatible avec

G

si, pour tout

s \in V

ou bien $f(s) = \lor$ et

g(s) = {s} ∪ ⋃_((s, s^′) ∈ E)g(s^′)

ou bien $f(s) = \land$ et

g(s) = {s} ∪ ⋂_((s, s^′) ∈ E)g(s^′)

Question 1

Montrer que l'application qui à tout sommet de

G

associe

V

est compatible avec

G

Question 2

Montrer que, si

g_1

g_2

sont deux applications compatibles avec

G

, l'application

g_1 \cap g_2

définie par :

g_1 \cap g_2(s) = g_1(s) \cap g_2(s)

est compatible avec

G

Question 3

Montrer qu'il existe une unique application

A_G

compatible avec

G

telle que pour toute application

g

compatible avec

G

et pour tout sommet

s

G, A_G(s) \subseteq g(s)

L'application

A_G

est appelée relation d'accessibilité de

G

. L'objet de cette partie est de construire des algorithmes qui permettent de calculer

A_G

On représente les graphes ET/OU à l'aide de deux tableaux G et f indicés par les sommets du graphe :

G(s)

est l'ensemble des sommets

s^'

G

tels que

(s, s^') \in E

f(s)

est égal à

f(s)

Les ensembles de sommets seront représentés par des listes sans répétition ou des tableaux de Booléens, au choix du candidat.

Question 4

Donner des algorithmes (ou programmes) qui réalisent les fonctions suivantes :

le test d'appartenance à un ensemble de sommets
le test d'égalité de deux ensembles de sommets
l'union de deux ensembles de sommets
étant donné un ensemble de sommets $S$ et un tableau $g$ indicé par $V$ à valeurs dans les ensembles de sommets, calcule l'union des $g(s)$ pour $s \in S$ .
étant donné un tableau $g$ indicé par $V$ , à valeurs dans les ensembles de sommets, et un graphe $ET/OUG$ (donné par G et f ), le test de compatibilité de $g$ avec $G$ .
Dans chaque cas, justifier brièvement la correction de l'algorithme et donner sa complexité.

Question 5

On définit la suite d'applications

A_n(s)

qui associent à chaque sommet un ensemble de sommets :

$A_0(s) = (s)$ pour tout $s$
Si $f(s) = \lor, A_(n + 1)(s) = A_n(s) \cup ⋃_((s, s^') \in E)A_n(s^')$
Si $f(s) = \land, A_(n + 1)(s) = A_n(s) \cup ⋂_((s, s^') \in E)A_n(s^')$

Calculer la suite $A_n(s)(n \leq 6)$ pour chacun des 9 sommets du graphe $G$ donné dans la figure 1 , dans lequel $f(s) = \lor$ pour les sommets représentés par des cercles et $f(s) = \land$ pour les sommets représentés par des carrés.
Montrer que, pour tout graphe $ET/OUG$ , il existe un entier $M$ que l'on précisera tel que, pour tout $n \geq M$ , pour tout $s, A_(n + 1)(s) = A_n(s)$ . On notera alors $A(s)$ la limite ainsi obtenue.
Montrer que $A = A_G$
En déduire un algorithme de calcul de $A_G$ dont on précisera la complexité.

Question 6

S

est un ensemble de sommets de

G

, on note

A_G^(− 1)(S) = {t ∈ V|S ∩ A_G(t) ≠ ∅}

(ensemble des sommets desquels on peut accéder à un sommet de

S

). Donner un algorithme qui, étant donnés

G

S

, calcule

A_G^(- 1)(S)

et préciser sa complexité.

Question 7

On associe à chaque sommet

s

la liste de ses prédecesseurs prec(

s

) et le nombre

n(s)

qui est égal au nombre de successeurs de

s

f(s) = \land

et égal à 1 sinon.

Soient

S, T

des listes de sommets. Initialement

T

est vide et

S = {s_0}

. On considère l'algorithme donné dans la figure 2.

Montrer que la complexité de cet algorithme est $O(|G|)$
Montrer que, après éxecution, $T = A_G^(− 1)({s_0})$ . (Ind : on pourra montrer que, si $f(s) = \land$ , $n(s) = |G(s)| - |G(s) \cap T|$ à chaque entrée dans la boucle externe).
Donner un algorithme qui calcule toutes les listes sans répétitions prec $[s]$ et tous les entiers $n(s)$ , pour $s \in V$ , en temps (total) $O(|G|)$ .
En déduire qu'il existe un algorithme linéaire qui résoud le problème d'accessibilité : étant donnés $G$ et $s, t \in V$ , l'algorithme répond true si $t \in A_G(s)$ et false sinon.

Fig. 1 - Un graphe ET/OU

Pour

s \in S

faire

n(s):=0

Tant que non vide

(S)

faire

s:=car(S); S:=cdr(S); L:=prec(s); T:=cons(s, T)

Tant que non vide

(L)

faire

s_1:=car(L); L:=cdr(L); n(s_1):=n(s_1) - 1; Si n(s_1) = 0 alors S:=cons(s_1, S)

Fin Tq
Fin Tq

Fig. 2 - Un algorithme sur les graphes ET/OU

2 Automates alternants

Un automate alternant est donné par un ensemble fini d'états

Q

, un état initial

q_0 \in Q

, un ensemble d'états finaux

Q_f \subseteq Q

, un alphabet d'entrée

A

, une fonction de transition

δ : Q \times A \to 2^Q

et une fonction de type

τ : Q \times A \to { \land, \lor }

. On écrira en abrégé

δ(q, a) = q_1 \lor \dots \lor q_m

(resp.

δ(q, a) = q_1 \land \dots \land q_m

) si

τ(q, a) = \lor (

resp.

τ(q, a) = \land)

. On écrira de plus

δ(q, a) =

false (resp.

δ(q, a) =

true ) lorsque

δ(q, a) = \emptyset

τ(q, a) = \lor

(resp.

τ(q, a) = \land

). Dans toute la suite, on supposera que

A \subseteq {0, 1}

ε

désignera le mot vide,

w_1 \cdot w_2

la concaténation des mots

w_1

w_2, w(i)

la ième lettre du mot

w

(si elle est définie) et

|w|

la longueur de

w

Un calcul de l'automate

A = (Q, q_0, A, δ, τ)

sur le mot

w

est un arbre étiqueté par

Q

et tel que:

La racine de l'arbre est étiquetée par $q_0$ . (C'est le noeud de l'arbre de profondeur 0 ).
Si un noeud $n$ de l'arbre, de profondeur $k$ , est étiqueté par $q$ et si $τ(q) = \lor, |w| \geq k + 1$ , $w(k + 1) = a$ et $δ(q, a) = {q_1, …, q_m}$ , alors $n$ a exactement un fils (de profondeur $k + 1$ ) étiqueté par l'un des états $q_1, \dots, q_m$ . Noter que l'on doit avoir $m > 0$ et donc qu'un calcul ne peut pas utiliser de transition $δ(q, a) =$ false .
Si un noeud $n$ de l'arbre, de profondeur $k$ , est étiqueté par $q$ et si $τ(q) = \land, |w| \geq k + 1$ , $w(k + 1) = a$ et $δ(q, a) = {q_1, …, q_m}$ , alors $n$ a exactement $m$ fils (de profondeur $k + 1$ ), étiquetés respectivement par $q_1, \dots, q_m$ . Noter que, si $m = 0$ (c'est à dire $δ(q, a) =$ true ), $n$ est une feuille.
Tous les noeuds de $T$ sont de profondeur inférieure ou égale à $|w|$ .

Un calcul de

A

sur

T

est réussi si, toute feuille

n

T

de profondeur

|u^'|

est étiquetée par un état final. (Noter que, si le calcul ne comprend aucune feuille de profondeur

|w|

, il est toujours réussi). Le langage accepté par

A

est l'ensemble des mots

w

A^*

tels qu'il existe un calcul réussi de

A

sur

w

Question 8

On considère l'automate alternant dont la fonction de transition est donnée par :

$δ$	0	1
$q_0$	$q_1 \land q_0$	$q_2 \lor q_3$
$q_1$	true	$q_0 \lor q_1$
$q_2$	false	true
$q_3$	$q_2$	false

$τ$	0	1
$q_0$	$\land$	$\lor$
$q_1$	$\land$	$\lor$
$q_2$	$\lor$	$\land$
$q_3$	$\land$	$\lor$

L'état initial est

q_0

. Il n'y a pas d'état final.
Donner des calculs réussis de l'automate sur les mots 0101, 0110, 0111.
La taille d'un automate non-déterministe est égale à la somme de son nombre d'états et de son nombre de transitions. La taille d'un automate alternant est la somme, pour tous les états

q

et pour toutes les lettres de l'alphabet

a

, du cardinal de

δ(q, a)

et du nombre d'états :

|A| = |Q| + \sum_(q \in Q)\sum_(a \in A)|δ(q, a)|

Question 9

Montrer que tout langage reconnu par un automate fini non-déterministe

A_1

est aussi reconnu par un automate alternant

A_2

de taille

O(|A_1|)

Question 10

Démontrer que, étant donné un automate alternant

A

, on peut calculer en temps

O(|A|)

un automate alternant

A^c

qui accepte le complémentaire du langage accepté par

A

. (Ind : on pourra considérer l'automate dual obtenu en échangeant

\lor

\land

d'une part et les états finaux et non finaux d'autre part)

Question 11

Donner un algorithme de complexité

O(|w| \times |A|)

qui, étant donnés un mot

w

et un automate alternant

A

détermine si

w

est accepté par

A

Question 12

Montrer que tout langage reconnu par un automate alternant

A_1

est aussi reconnu par un automate non-déterministe

A_2

Quelle est la complexité d'un algorithme calculant

A_2

à partir de

A_1

Question 13

On considère le langage $L_n$ qui contient le mot unique $1^(2^n)$ . Montrer que tout automate non-déterministe acceptant $L_n$ comporte au moins $2^n + 1$ états.
Donner un automate alternant qui accepte $L_n$ , et de taille $O(n^2)$ . (Ind : on pourra considérer les états $q_i$ à partir desquels sont acceptés les mots de la forme $1^(2k + 1)$ où le ième bit dans l'écriture en base 2 de $k$ est 0 .).

A Exemple d'un petit langage algorithmique

instructions élémentaires : l'affectation

e:=e^'

, l'affichage print

e

, les appels de procédures

p(e_1, \dots, e_n)

, l'identité skip .
structures de contrôle :

i; i^'

: composition séquentielle des instructions
begin

i

end : parenthèsage (on peut aussi utiliser une indentation)
if

e

then

i

else

i^'

: conditionnelle
if

e

then

i

: abréviation de if

e

then

i

else skip.
for

x = e

e^'

i

: itération (dont les bornes sont calculées avant entrée dans la boucle;

x, e, e^'

sont de type entier)
Tant que

e

faire

i

Fin Tq : boucle, le test d'arrêt

e

étant évalué à chaque itération.

Pas de description pour le moment

Commentaires• ENS Informatique MP PC 2004

Connectez-vous pour participer aux discussions

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

Chargement des commentaires...

Explorer les annales

Téléchargements

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

Filière MP (groupes MPI/MI) Épreuve commune aux ENS de Paris et Cachan

INFORMATIQUE

1 Accessibilité dans les graphes ET/OU

Question 1

Question 2

Question 3

Question 4

Question 5

Question 6

Question 7

2 Automates alternants

Question 8

Question 9

Question 10

Question 11

Question 12

Question 13

A Exemple d'un petit langage algorithmique

Commentaires• ENS Informatique MP PC 2004

Commentaires• ENS Informatique MP PC 2004

Filière MP (groupes MPI/MI)
Épreuve commune aux ENS de Paris et Cachan