ENS Informatique Fondamentale (Maths Info) MP 2014Sujet et corrigé

Pas encore noté

Faisable en Sup

Ensembles, parties et cardinaux finis
Combinatoire et coefficients binomiaux
Convexité et enveloppe convexe dans un espace euclidien
Espaces vectoriels euclidiens et produit scalaire
Algorithmique et preuve de terminaison

Explorer les annales

BanqueX-ENS Année2014 FilièreMP MatièreMathématiques-Informatique

Annales X-ENS MP Mathématiques-Informatique X-ENS MP 2014 MP Mathématiques-Informatique Mathématiques-Informatique 2014

Téléchargements

Télécharger le sujet (PDF)

Corrigé

Lire en ligne LaTeX Word

Rapport du jury : non disponible

Présentation du sujet

Dimension de Vapnik-Chervonenkis des hypergraphes et applications à la géométrie convexe

Le sujet introduit la dimension VC d'un hypergraphe, qui mesure sa complexité combinatoire, et démontre une borne polynomiale sur le nombre d'hyperarêtes en fonction de cette dimension. Il applique ensuite cette notion à des hypergraphes définis géométriquement (intervalles, demi-espaces, convexes) puis étudie un algorithme d'approximation utilisant un point central pour construire des ensembles epsilon-fins.

1Partie I : dimension VC d'un hypergrapheOn définit la trace d'un hypergraphe et sa dimension VC, et on démontre une borne (lemme de Sauer-Shelah) sur le nombre d'hyperarêtes d'un hypergraphe de dimension VC bornée.
2Partie II : compression d'hypergraphe et dimension VCOn introduit une opération de décalage sur les hypergraphes qui ne fait pas croître la dimension VC, et on l'utilise pour redémontrer la borne de la partie I.
3Partie III : dimension VC d'hypergraphes géométriquesOn établit des résultats de géométrie convexe (enveloppe convexe, demi-espaces) pour calculer la dimension VC d'hypergraphes définis par des demi-espaces ou des convexes du plan.
4Partie IV : approximation d'une famille d'hypergraphes géométriquesOn étudie la notion de point central d'un ensemble de points et on l'utilise pour construire, via un algorithme, un ensemble epsilon-fin de petite taille relativement aux convexes du plan.

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

ÉCOLES NORMALES SUPÉRIEURES

CONCOURS D'ADMISSION 2014
Filière MP spécialité info

COMPOSITION D'INFORMATIQUE-MATHÉMATIQUES - A - (ULCR)

(Durée : 4 heures)

L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation choisi par le candidat doit être spécifié en tête de la copie.

Dimension VC d'un hypergraphe

Ce sujet comporte six pages et quatre parties.

La partie I introduit la notion de dimension de Vapnik-Chervonenkis, en abrégé dimension

VC

, d'un hypergraphe et établit une borne polynomiale sur la complexité d'un hypergraphe de dimension VC bornée. La partie II étudie l'effet d'une méthode de normalisation d'hypergraphes sur la dimension VC. La partie III détermine la dimension VC de certains hypergraphes définis géométriquement en établissant au préalable quelques résultats classiques de géométrie convexe. La partie IV examine un algorithme d'approximation d'un hypergraphe géométrique de dimension VC non bornée.

Les notions introduites en partie I sont utilisées dans les parties II et III. La partie IV s'appuie sur certains résultats de la partie III. Les résultats d'une question pourront être admis dans la suite du sujet.

Pour tout ensemble

S

on note

P(S)

l'ensemble des parties de

S

, c'est-à-dire :

P(S) = {T|T \subseteq S}.

Un hypergraphe de sommets

S

est un sous-ensemble de

P(S)

. Si

H

est un hypergraphe de sommets

S

alors on appelle hyperarête de

H

tout élément de

H

. Par exemple si

S = {0, 1, 2}

alors

P(S) = {\emptyset, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}}

H = {{0}, {0, 2}, {1, 2}, {0, 1, 2}}

est un hypergraphe de sommets

S;

l'ensemble

{1, 2}

est une hyperarête de

H

Pour tout ensemble fini

X

on note

|X|

son cardinal, c'est-à-dire son nombre d'éléments. En particulier, quand

H

est un hypergraphe,

|H|

désigne le nombre d'hyperarêtes de

H

Tout au long du sujet,

n

d

désignent des entiers strictement positifs. Pour tous entiers

p \geq 0

q \geq 0

on note

(p/q)

le nombre de sous-ensembles distincts de cardinal

q

d'un ensemble de cardinal

p

. En particulier

(p/0) = 1

pour tout

p

Partie I. Dimension VC d'un hypergraphe

Question 1 Soit

S = {0, 1, \dots, n - 1}

l'ensemble des entiers compris entre 0 et

n - 1

.
a. Quel est, en fonction de

n

, le nombre maximum d'hyperarêtes que peut avoir un hypergraphe de sommets

S

? On justifiera la réponse.
b. Combien d'hypergraphes de sommets

S

différents existe-t-il? On justifiera la réponse.
c. Démontrer :

\forallp \geq q \geq 1, (p/q) = ((p - 1)/q) + ((p - 1)/(q - 1))

H

est un hypergraphe de sommets

S

U

est un sous-ensemble de

S

, on définit la trace de

H

sur

U

, notée

H_(|U)

, par :

H_(|U) = {U ∩ α|α ∈ H}

Question 2 Soient

S

un ensemble fini,

H

un hypergraphe de sommets

S

U \subseteq V \subseteq S

.
a. Donner un exemple de

S, H, U

V

pour lesquels

H_(|U)⊈H_(|V)

.
b. Démontrer que pour toutes hyperarêtes

α, β \in H

, on a :

α \cap U \neq β \cap U \Rightarrow α \cap V \neq β \cap V.

c. En déduire que

|H_(|U)| \leq |H_(|V)|

Soit

H

un hypergraphe de sommets

S

. On dit qu'un sous-ensemble

U

S

est pulvérisé par

H

H_(|U) = P(U)

. Si

S

est fini, on définit la dimension

VC

H

, notée dimvc

(H)

, comme le cardinal maximum d'un sous-ensemble

U \subseteq S

pulvérisé par

H

, augmenté de 1 :

dim_(VC)(H) = 1 + max{|U||U ⊆ S et H_(|U) = P(U)}

On ne définit pas de notion de dimension VC pour les hypergraphes dont l'ensemble de sommets est infini.

Question 3 Dans cette question on suppose

n \geq 3

.
a. Soient

S

un ensemble de

n

réels deux à deux distincts et

H

l'hypergraphe de sommets

S

défini par

H = {S \cap [a, b]|a, b \in ℝ}

. Calculer

dim_(VC)(H)

.
b. On note

𝕊 = {(x, y) ∈ ℝ^2|x^2 + y^2 = 1}

. Soit

S^' \subseteq 𝕊

un sous-ensemble de

𝕊

de cardinal

n

. On définit :

f : {ℝ, → 𝕊; θ, ↦ (cosθ, sinθ) et H^′ = {S^′ ∩ f([a, b])|a, b ∈ ℝ}

H^'

est donc un hypergraphe de sommets

S^'

. Calculer

dim_(VC)(H^')

Question 4 Soient

S

un ensemble fini de cardinal

n

H

un hypergraphe de sommets

S

.
a. Montrer que si

dim_(VC)(H) = 1

alors

|H| \leq 1

.
b. Soit

x \in S

. On définit deux hypergraphes de sommets

S∖{x}

H^′ = H_(|S∖{x}) et H^(′′) = {α ∈ H^′|α ∈ H et α ∪ {x} ∈ H}

Montrer que

|H| = |H^'| + |H^('')|

.
c. On considère à nouveau les hypergraphes

H^'

H^('')

définis à la question

4(b)

. Montrer que

dim_(VC)(H^') \leq dim_(VC)(H)

et que

dim_(VC)(H^('')) \leq dim_(VC)(H) - 1

.
d. Montrer que si

dim_(VC)(H) = d

, alors :

|H| \leq \sum_(i = 0)^(d - 1)(n/i)

e. Donner, pour tout

n \geq d

, un exemple d'hypergraphe à

n

sommets pour lequel l'inégalité de la question

4(d)

devient une égalité. On justifiera la réponse.

Partie II. Compression d'hypergraphe et dimension VC

Soit

H

un hypergraphe de sommets

S

. Pour tout

x \in S

, on définit l'hypergraphe décalé de

H

par

x

, noté

D_x(H)

, par :

D_x(H) = {α∖{x}|α ∈ H} ∪ {α|α ∈ H et α∖{x} ∈ H}

Par exemple, si

S = {0, 1, 2}

H = {{0}, {0, 2}, {1, 2}, {0, 1, 2}}

, alors :

D_0(H) = {∅, {2}, {1, 2}, {0, 1, 2}}

Dans le reste de cette partie on suppose que

S = {0, 1, \dots, n - 1}

et que

H

est un hypergraphe de sommets

S

Question 5 Montrer que pour tout

x \in S

on a

|D_x(H)| = |H|

. Indication : on pourra chercher à expliciter une bijection entre

H

D_x(H)

Question 6 Soient

U \subseteq S

x \in S

.
a. Montrer que si

x \notin U

alors

(D_x(H))_(|U) \subseteq D_x(H_(|U))

.
b. Montrer que si

x \in U

alors

(D_x(H))_(|U) \subseteq D_x(H_(|U))

Question 7 Montrer que pour tout

x \in S

on a

dim_(VC)(D_x(H)) \leq dim_(VC)(H)

Question 8 Pour tout

i \in ℕ

on note

imodn

le reste de la division entière de

i

par

n

, c'est-à-dire que

imodn

est l'unique entier

r \in {0, 1, \dots, n - 1}

tel qu'il existe

q \in ℕ

satisfaisant

i = qn + r

. On considère la suite

(H_i)_(i \in ℕ)

d'hypergraphes définie par :

{H_0 = H; H_i = D_(imodn)(H_(i − 1)) pour tout i ≥ 1

a. Démontrer qu'il existe un entier

i_0 \in ℕ

et un hypergraphe

H^*

de sommets

S

tel que :

\foralli \geq i_0, H_i = H^*

b. Démontrer que

max_(α \in H^*)|α| \leq dim_(VC)(H) - 1

.
c. En déduire une nouvelle preuve de l'identité établie à la question

4(d)

ù |H| \leq \sum_(i = 0)^(d - 1)(n/i), où d = dim_(VC)(H)

Partie III. Dimension VC d'hypergraphes géométriques

On munit l'espace vectoriel

ℝ^d

du produit scalaire usuel :

(x_1, x_2, \dots, x_d) \cdot (y_1, y_2, \dots, y_d) = \sum_(i = 1)^d x_i y_i

et on rappelle que

ℝ^d

muni de ce produit scalaire est un espace euclidien. Un ensemble

A \subseteq ℝ^d

est dit convexe si et seulement si :

\forallx, y \in A, \forallλ \in [0, 1], λx + (1 - λ)y \in A

Par convention, l'ensemble vide est convexe. On définit l'enveloppe convexe d'un ensemble

A \subseteq ℝ^d

, notée

conv(A)

, comme l'intersection de tous les sous-ensembles convexes de

ℝ^d

qui contiennent

A

conv(A) = ⋂_(B \subseteq ℝ^d; A \subseteq B; B convexe)B

On note

C_d

l'ensemble des sous-ensembles convexes de

ℝ^d

Question 9

a. Montrer que toute intersection de sous-ensembles convexes de

ℝ^d

est convexe.
b. Démontrer que pour tout sous-ensemble

A \subseteq ℝ^d

les trois propositions suivantes sont équivalentes :
(1)

A

est convexe,
(2)

A = conv(A)

,
(3)

\foralln \geq 2, \forallx_1, x_2, \dots, x_n \in A, \forallλ_1, λ_2, \dots, λ_n \in ℝ^+

tels que

\sum_(i = 1)^n λ_i = 1, \sum_(i = 1)^n λ_i x_i \in A

.
c. Démontrer que pour tout sous-ensemble

A \subseteq ℝ^d

on a :

conv(A) = {∑_(i = 1)^n λ_i x_i|n ∈ ℕ^∗, x_1, x_2, …, x_n ∈ A, λ_1, λ_2, …, λ_n ∈ ℝ^+tels que ∑_(i = 1)^n λ_i = 1}

Un sous-ensemble

D \subseteq ℝ^d

est un demi-espace fermé (resp. demi-espace ouvert) s'il existe

c \in ℝ^d

t \in ℝ

tels que

D = {x ∈ ℝ^d|x ⋅ c ≤ t}

(resp.

D = {x ∈ ℝ^d|x ⋅ c < t}

). On note

D_d

l'ensemble des demi-espaces fermés de

ℝ^d

Question 10

a. Montrer que tout demi-espace fermé de

ℝ^d

est convexe.
b. Montrer que pour tout sous-ensemble

X

ℝ^d

et tout demi-espace fermé

D

ℝ^d

D \cap conv(X) \neq \emptyset \Leftrightarrow D \cap X \neq \emptyset

Une partition d'un ensemble

S

en deux parties est un ensemble

{I_1, I_2}

de sous-ensembles de

S

qui sont disjoints et dont l'union égale

S : I_1 \cap I_2 = \emptyset

I_1 \cup I_2 = S

Question 11 Soient

x_1, x_2, \dots, x_n \in ℝ^d

des vecteurs deux à deux distincts.
a. Montrer que si

n \geq d + 2

alors il existe

n

réels

λ_1, λ_2, \dots, λ_n \in ℝ

non tous nuls tels que

\sum_(i = 1)^n λ_i x_i = 0\to

\sum_(i = 1)^n λ_i = 0

.
b. En déduire que si

n \geq d + 2

alors l'ensemble

{x_1, x_2, …, x_n}

admet une partition en deux sous-ensembles non-vides

V_1

V_2

tels que

conv(V_1) \cap conv(V_2)

est non vide.

Question 12 Soit

S

un sous-ensemble fini de

ℝ^d

et soit

H

l'hypergraphe de sommets

S

défini par

H = {S ∩ D|D ∈ D_d}

. Montrer que

dim_(VC)(H) \leq d + 2

Question 13 Soit

n \geq 2

. Soit

S = {x_1, x_2, …, x_n}

où

x_1, x_2, \dots, x_n \in ℝ^2

sont des vecteurs de norme 1 deux à deux distincts. Calculer la dimension VC de l'hypergraphe

H

de sommets

S

défini par

H = {S ∩ C|C ∈ C_2}

. On justifiera la réponse.

Partie IV. Approximation d'une famille d'hypergraphes géométriques

Dans cette partie,

ε

désigne un réel strictement compris entre 0 et 1 .

Soient

S \subseteq ℝ^d

un ensemble de cardinal

n

R

un ensemble (éventuellement infini) de sous-ensembles de

ℝ^d

. Un ensemble

T \subset ℝ^d

est

ε

-fin pour

S

relativement à

R

\forallR \in R tel que |R \cap S| \geq ε|S|, R \cap T \neq \emptyset

Les ensembles

ε

-fins jouent un rôle important dans les algorithmes d'approximation en géométrie algorithmique. Quand la dimension VC de l'hypergraphe

{S \cap R|R \in R}

est bornée indépendamment de

|S|

, il existe toujours un ensemble

ε

-fin de petite taille et des méthodes simples et générales permettent d'en calculer un efficacement. Dans le cas

R = C_d

, la dimension VC de cet hypergraphe n'est pas bornée indépendamment de

|S|

(cf question 13) et il faut recourir à des méthodes spécialisées. L'objectif de cette partie est d'étudier l'une de ces méthodes.

Question 14 Soient

C_1, C_2, \dots, C_n \in C_d

.
a. On suppose que

n \geq d + 2

et que pour tout sous-ensemble

I \subseteq {1, 2, \dotsn}

de cardinal

n - 1

, l'ensemble

\cap _(i \in I)C_i

est non vide. En déduire que l'ensemble

\cap _(i = 1)^n C_i

est non-vide.

Indication : on pourra fixer, de manière arbitraire, pour tout

1 \leq k \leq n

, un vecteur

x_k ∈ ∩ _(i ∈ {1, 2, …, n}∖{k})C_i

et utiliser la question 11 (b).
b. Montrer que si

n \geq d + 2

et que pour tout sous-ensemble

I \subseteq {1, 2, \dotsn}

de cardinal

d + 1

, l'ensemble

\cap _(i \in I)C_i

est non vide, alors l'ensemble

\cap _(i = 1)^n C_i

est non-vide.

Question 15 Soit

S \subseteq ℝ^d

un ensemble de cardinal

n

. Un point central de

S

est un élément

c \in ℝ^d

(pas nécessairement dans

S

) tel que tout demi-espace fermé contenant

c

contient au moins

n/(d + 1)

éléments de

S

.
a. Montrer qu'un vecteur

c \in ℝ^d

est un point central de

S

si et seulement si

c

appartient à tout demi-espace ouvert

D

contenant strictement plus de

(dn)/(d + 1)

vecteurs de

S

.
b. On définit

C(S) = {conv(D \cap S)|D demi-espace ouvert tel que |D \cap S| > (dn)/(d + 1)}

c'est-à-dire que les éléments de

C(S)

sont les enveloppes convexes de sous-ensembles de

S

contenus dans un demi-espace ouvert

D

contenant strictement plus que

(dn)/(d + 1)

vecteurs de

S

. Montrer que pour tous

C_1, C_2, \dots, C_(d + 1) \in C(S)

l'intersection

\cap _(i = 1)^(d + 1)C_i

est non-vide.
c. Montrer que tout ensemble fini

S \subseteq ℝ^d

de cardinal

n \geq d + 1

admet un point central.

Un principe général de construction d'un ensemble

ε

-fin relativement à

C_2

est le suivant :

Entrée : un sous-ensemble fini $S \subseteq \mathbb{R}^{2}$ et $0<\varepsilon<1$.
Sortie : $T \subseteq \mathbb{R}^{2}$ qui est $\varepsilon$-fin pour $S$ relativement à $\mathcal{C}_{2}$.
$T \leftarrow \emptyset$
Tant qu'il existe $C \in \mathcal{C}_{2}$ tel que $|C \cap S| \geq \varepsilon|S|$ et $C \cap T=\emptyset$,
| Calculer un point central $c$ de $C \cap S$
| Ajouter $c$ à $T$
Retourner $T$.

Soit

S \subseteq ℝ^2

un ensemble de cardinal

n

et soit

c

un point central de

S

. On suppose que

c \notin S

. Un triangle de

S

est un sous-ensemble de

S

de cardinal 3 . On dit qu'un triangle

T

S

entoure un vecteur

x

x \in conv(T)

. La profondeur simpliciale d'un vecteur

x

par rapport à

S

est le nombre de triangles de

S

qui entourent

x

Question 16 On admet le résultat suivant.
Lemme de sélection : si

S \subseteq ℝ^2

est de cardinal

n

c

est un point central de

S

alors la profondeur simpliciale de

c

par rapport à

S

est supérieure ou égale à

2/9(n/3)

. Montrer que la méthode

(M)

termine et majorer le cardinal de l'ensemble

T

retourné.

Questions fréquentes

4 questions

Sur quels chapitres porte ce sujet d'informatique-mathématiques MP ENS 2014 ?

Il porte sur la combinatoire des ensembles, la géométrie convexe et l'algorithmique, réunis autour de la notion de dimension de Vapnik-Chervonenkis d'un hypergraphe.

Quelles parties sont indépendantes dans ce sujet ?

L'énoncé précise que les notions de la partie I sont utilisées dans les parties II et III, et que la partie IV s'appuie sur certains résultats de la partie III ; le sujet est donc progressif plutôt que composé de parties indépendantes.

Qu'est-ce que la dimension VC étudiée dans ce sujet ?

C'est une mesure de la complexité combinatoire d'un hypergraphe, définie comme la plus grande taille d'un sous-ensemble de sommets dont l'hypergraphe réalise toutes les parties possibles, augmentée de 1.

Ce sujet demande-t-il de programmer ?

Le sujet est essentiellement démonstratif (mathématiques et informatique théorique), avec une seule question qui présente un algorithme en pseudo-code à analyser plutôt qu'à écrire.

Pas de description pour le moment

Commentaires• ENS Informatique Fondamentale (Maths Info) MP 2014

Connectez-vous pour participer aux discussions

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

Chargement des commentaires...