ENS Informatique Fondamentale (Maths Info) MP PC 2008Sujet

Pas encore noté

Explorer les annales

BanqueX-ENS Année2008 FilièreMP/PC MatièreMathématiques-Informatique

Annales X-ENS MP/PC Mathématiques-Informatique X-ENS MP/PC 2008 MP/PC Mathématiques-Informatique Mathématiques-Informatique 2008

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

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
\title{ MATHÉMATIQUES - INFORMATIQUE

}

Durée : 4 heures

Les calculatrices sont inutiles et de ce fait ne sont pas autorisées

Préambule L'objet du sujet est d'étudier quelques propriétés mathématiques et algorithmiques des ensembles convexes : le lemme de Farkas et la programmation linéaire, les fonctions de jauge et le premier théorème de Minkowski, les minima successifs et les réseaux admissibles, une technique de réduction de base. Les applications de ces techniques sont nombreuses, notamment en optimisation combinatoire, mais ne sont pas abordées dans le sujet.

Les deux premières parties sont indépendantes. Les troisième et quatrième parties s'appuient essentiellement sur la deuxième. Le sujet n'est pas de difficulté progressive : chaque partie comporte des questions relativement difficiles et, globalement, le sujet comporte peu de questions élémentaires.

Notations On se place dans l'espace vectoriel euclidien

ℝ^n

, muni du produit scalaire usuel. Si

x⃗

est un vecteur de

ℝ^n

, on note

x_i

i

-ème composante, pour

1 \leq i \leq n

. Si

x⃗ \in ℝ^n

y⃗ \in ℝ^n

, on note

x⃗.y⃗

leur produit scalaire. Les opérations portant sur des vecteurs sont à comprendre composante par composante : ainsi,

x⃗ \geq 0\to

signifie

x_i \geq 0

pour tout

i

. Un vecteur peut être considéré comme vecteur ligne ou vecteur colonne selon le contexte, s'il n'y a pas ambiguïté. Ainsi, pour

x⃗ \in ℝ^n, y⃗ \in ℝ^m

et une matrice

A

de taille

n \times m

, on note

Ay⃗

le produit de

A

par

y⃗, y⃗

étant considéré comme vecteur colonne, et

x⃗A

le produit de

x⃗

par

A, x⃗

étant considéré comme vecteur ligne. Enfin, on utilise les notations ensemblistes suivantes : si

S \subseteq ℝ^n, T \subseteq ℝ^n, λ \in ℝ

x⃗ \in ℝ^n

, on note

x⃗ + S

l'ensemble des vecteurs

x⃗ + y⃗

avec

y⃗ \in S, λS

l'ensemble des vecteurs

λy⃗

avec

y⃗ \in S

, et

S + T

l'ensemble des vecteurs

y⃗ + z⃗

avec

y⃗ \in S

z⃗ \in T

Partie 1. Lemme de Farkas et théorème de dualité

Un ensemble

K \subseteq ℝ^n

est convexe si

\forallx⃗, y⃗ \in K, \forallλ \in ℝ, 0 \leq λ \leq 1, λx⃗ + (1 - λ)y⃗ \in K

. C'est un cône si

\forallx⃗, y⃗ \in K, \forallλ, μ \in ℝ^+, λx⃗ + μy⃗ \in K

. S'il existe une matrice

C

à coefficients réels, de taille

m \times n

, telle que

K = {x⃗ ∈ ℝ^n|Cx⃗ ≤ 0→}

, on dit que

K

est un cône polyédral. S'il existe

a⃗_1, \dots, a⃗_m \in ℝ^n

tels que

K = {x⃗ ∈ ℝ^n|x⃗ = ∑_(i = 1)^m y_i a⃗_i

avec

\foralli, y_i \geq 0}

, on dit que

K

est le cône engendré par

a⃗_1, \dots, a⃗_m

. Dans ce cas, on peut aussi écrire

K

matriciellement :

K = {Ay⃗|y⃗ \geq 0}

où cette fois-ci

A

est de taille

n \times m

et les

a⃗_i

sont les colonnes de

A

Question 1.1. Vérifier qu'un cône polyédral (respectivement engendré) est bien un cône. Montrer que

K

est un cône si et seulement s'il est convexe et

\forallx⃗ \in K, \forallλ \geq 0, λx⃗ \in K

. Montrer qu'un cône polyédral est intersection de demi-espaces, c'est-à-dire d'ensembles de la forme

{x⃗ ∈ ℝ^n|c⃗ ⋅ x⃗ ≤ 0}

Pour

K \subseteq ℝ^n

, on définit le polaire de

K

comme l'ensemble

K^∗ = {z⃗ ∈ ℝ^n|∀x⃗ ∈ K, z⃗ ⋅ x⃗ ≤ 1}

.
Question 1.2. Montrer les propriétés suivantes : a)

K^*

est convexe, b)

K \subseteq (K^*)^*

; c) si

K

est un cône,

K^*

est un cône et

K^∗ = {z⃗ ∈ ℝ^n|∀x⃗ ∈ K, z⃗ ⋅ x⃗ ≤ 0}

; d) si

K

est un cône engendré,

K^*

est un cône polyédral ; e) si

K

est un cône polyédral,

K = (K^*)^*

Soit

A

une matrice réelle de taille

n \times m, n \leq m

, de rang

n

b⃗

de dimension

n

. On note

a⃗_1, \dots, a⃗_m

les colonnes de

A

D = {a⃗_(i_1), …, a⃗_(i_n)}

un ensemble constitué de

n

vecteurs linéairement indépendants parmi ces

m

vecteurs. On effectue les opérations suivantes:
Étape 1 : Écrire

b⃗

(de façon unique) comme

b⃗ = \sum_(j = 1)^n μ_(i_j)a⃗_(i_j)

.
Étape 2: Choisir, s'il existe, l'indice minimal

h ∈ {i_1, …, i_n}

tel que

μ_h < 0

, sinon STOP.
Étape 3 : Soit

c⃗

tel que

c⃗ \cdot a⃗_(i_j) = 0

pour tout

i_j \neq h

c⃗ \cdot a⃗_h = 1

. Choisir, s'il existe, l'indice minimal

k \in {1, \dots, m}

tel que

c⃗ \cdot a⃗_k < 0

, sinon STOP.
Étape 4 : Remplacer

D

par

D∖{a⃗_h} ∪ {a⃗_k}

et reprendre à l'étape 1.

Question 1.3. On note

K

le cône engendré par les vecteurs

(a⃗_i)_(1 \leq i \leq m)

Montrer que l'algorithme précédent est bien défini, que s'il stoppe à l'étape 2 alors $b⃗ \in K$ et que s'il stoppe à l'étape 3 alors il existe $c⃗$ tel que $c⃗ \cdot b⃗ < 0$ et $- c⃗ \in K^*$ .
Montrer que l'algorithme ne boucle pas. Indication : s'il existe deux itérations $i < j$ pour lesquelles l'ensemble $D$ est le même, on pourra considérer le plus grand indice $r$ tel que $a⃗_r$ quitte $D$ (à l'itération $p$ ) et y retourne (à l'itération $q$ ) avec $i \leq p < q < j$ et calculer $c⃗_q \cdot b⃗$ avec $b⃗$ exprimé dans la base utilisée à l'étape $p$ .
En déduire le lemme de Farkas : de deux choses l'une, soit il existe $y⃗ \geq 0\to$ tel que $b⃗ = Ay⃗$ , soit il existe $c⃗$ tel que $c⃗ \cdot b⃗ < 0, c⃗A \geq 0\to$ et $c⃗ \cdot a⃗_i = 0$ pour ( $n - 1$ ) vecteurs $a⃗_i$ linéairement indépendants.

On admettra que le lemme de Farkas se généralise au cas où

A

est une matrice quelconque : dans ce cas, la condition portant sur

c⃗

est que

c⃗

est orthogonal à

t - 1

vecteurs

a⃗_i

linéairement indépendants où

t

est le rang de

(a⃗_1, \dots, a⃗_m, b⃗)

. On sera également amené à utiliser l'énoncé (légèrement affaibli) suivant : il existe

y⃗ \geq 0\to

tel que

b⃗ = Ay⃗

si et seulement si

c⃗A \leq 0\to

implique

c⃗ \cdot b⃗ \leq 0

Question 1.4.

En utilisant le lemme de Farkas, montrer que si $K$ un est cône engendré alors $(K^*)^* = K$ et $K$ est polyédral. Pour ce deuxième point, utiliser la condition supplémentaire du lemme de Farkas portant sur $c⃗$ : " $c⃗ \cdot a⃗_i = 0$ pour $t - 1$ vecteurs $a⃗_i$ linéairement indépendants".
Montrer que si $K$ est un cône polyédral, il est engendré. On pourra considérer un cône engendré $J$ tel que $J^* = K$ .

Question 1.5. On note

I_n

la matrice identité de taille

n

. Soit

A

une matrice réelle de taille

n \times m

b⃗ \in ℝ^n

c⃗ \in ℝ^m

. Montrer, en considérant la matrice (

A - A I_n

), de taille

n \times (2m + n)

, et le lemme de Farkas, qu'il existe

x⃗

tel que

Ax⃗ \leq b⃗

si et seulement si

y⃗ \cdot b⃗ \geq 0

pour tout

y⃗ \geq 0\to

tel que

y⃗A = 0\to

. Montrer ensuite le théorème de dualité suivant. Si

{x⃗|Ax⃗ \leq b⃗}

{y⃗|y⃗ \geq 0\to, y⃗A = c⃗}

sont non vides alors :

max{c⃗ \cdot x⃗|Ax⃗ \leq b⃗} = min{y⃗ \cdot b⃗|y⃗ \geq 0\to, y⃗A = c⃗}

Pour cela, on montrera, en utilisant la première partie de la question, qu'il existe

x⃗

y⃗

tels que :

(A, 0; 0, ^t A; 0, - ^t A; - ^t c⃗, ^t b⃗; 0, - I_n)((x⃗)/(y⃗)) \leq (b⃗; c⃗; - c⃗; 0)

(Tous les vecteurs sont ici des vecteurs colonnes. On utilise la notation

^t

pour les transposer.) On sera amené à distinguer deux cas selon qu'une certaine variable réelle, introduite par l'application du lemme de Farkas, est nulle ou pas.

Partie 2. Corps convexes, normes et premier théorème de Minkowski

Pour

x⃗ \in ℝ^n

, on définit

‖x⃗‖_r = (\sum_(i = 1)^n|x_i|^r)^(1/r)

. On rappelle que pour

r \geq 1, ‖ \cdot ‖_r

est une norme.
Question 2.1. Soit la fonction

Γ

définie par

Γ(x) = \int_0^(+ \infty)e^(- t)t^(x - 1)dt

Rappeler pourquoi la fonction $Γ$ est bien définie sur $ℝ^(+ *)$ et $Γ(x + 1) = xΓ(x)$ .
Montrer que $Γ(p)Γ(q) = Γ(p + q)\int_0^1(1 - t)^(p - 1)t^(q - 1)dt$ , par un calcul d'intégrale double et en remarquant que $0 \leq t < + \infty, t \leq u < + \infty$ si et seulement si $0 \leq u < + \infty, 0 \leq t \leq u$ .

Question 2.2. On note

V_(r, n)(R)

le volume de

{x⃗ ∈ ℝ^n|‖x⃗‖_r ≤ R}

, la boule de rayon

R

en dimension

n

pour la norme

‖.‖_r

. Établir une relation entre

V_(r, n)(R)

V_(r, n)(1)

puis entre

V_(r, n)(1)

V_(r, n - 1)(1)

et montrer finalement que :

V_(r, n)(1) = ({2Γ(1/r + 1)}^n)/(Γ(n/r + 1))

A^‵

quoi est égal ce volume lorsque

r = 1, r = 2

?
Soit

K \subseteq ℝ^n

. On rappelle que

x⃗

appartient à l'adhérence de

K

, notée

K¯

, si

x⃗

est limite d'une suite d'éléments de

K

et que

x⃗

appartient à l'intérieur de

K

, noté

K^\circ

, s'il existe

r > 0

tel que la boule de centre

x⃗

et de rayon

r

appartient à

K

Question 2.3. Montrer que si

K

est convexe, son adhérence

K¯

et son intérieur

K^\circ

sont convexes. Montrer que si, de plus,

0\to \in K^\circ

alors

λK \subseteq K^\circ

0 \leq λ < 1

K¯ \subseteq λK

λ > 1

. (Ne pas hésiter à s'aider de dessins pour toutes ces propriétés.)

Un corps convexe est un convexe borné

K

tel que

0\to \in K^\circ

. On lui associe la fonction de jauge

f

définie par

f(x⃗) = inf{λ|λ \geq 0, x⃗ \in λK}

pour tout

x⃗ \neq 0\to

f(0\to) = 0

Question 2.4. Montrer que la fonction de jauge

f

d'un corps convexe

K

est bien définie et que :
(i)

f(x⃗) > 0

x⃗ \neq 0\to

;
(ii)

f(αx⃗) = αf(x⃗)

α > 0

.
(iii)

f(x⃗ + y⃗) \leq f(x⃗) + f(y⃗)

x⃗ \in ℝ^n

y⃗ \in ℝ^n

Pour démontrer (iii), on commencera par montrer que

x⃗/f(x⃗) \in K¯

puis, en utilisant les résultats de la question 2.3, que

x⃗ \in K^\circ

si et seulement si

f(x⃗) < 1

x⃗ \in K¯

si et seulement si

f(x⃗) \leq 1

On remarque que lorsque

K

est symétrique par rapport à

0\to

, c'est-à-dire

x⃗ \in K

si et seulement si

- x⃗ \in K

, alors sa fonction de jauge

f

vérifie de plus

f(αx⃗) = |α|f(x⃗)

, c'est donc une norme.

Question 2.5. Réciproquement, soit

f

une fonction de

ℝ^n

dans

ℝ

satisfaisant les propriétés (i), (ii) et (iii) précédentes. Montrer qu'il existe

M > 0

tel que pour tout

x⃗ \in ℝ^n, f(x⃗) \leq M\sum_i|x_i|

. En déduire que

f

est continue en

0\to

, puis sur

ℝ^n

. Montrer enfin que l'ensemble

K = {x⃗ ∈ ℝ^n|f(x⃗) ≤ 1}

est un corps convexe dont

f

est la fonction de jauge.

Lorsque

f

est une norme, donc lorsque

f

possède en plus la propriété

f(αx⃗) = |α|f(x⃗)

, il est facile de voir que le corps convexe

K = {x⃗|f(x⃗) \leq 1}

est symétrique par rapport à

0\to

. On suppose que c'est le cas dans tout le reste de cette partie.

Question 2.6. Montrer que la fonction de jauge

f^*

du polaire

K^∗ = {z⃗|∀x⃗ ∈ K, z⃗ ⋅ x⃗ ≤ 1}

d'un ensemble

K

est égal à

f^∗(z⃗) = sup{z⃗ ⋅ x⃗|x⃗ ∈ K}

Dans la suite, on parlera de volumes sans se préoccuper de questions théoriques d'existence et on notera

Vol(K)

le volume de

K

. On utilisera en particulier la relation

Vol(λK) = λ^n Vol(K)

en dimension

n

pour tout

λ > 0

Question 2.7. On suppose que

Vol(K) > 1

. Pour

x⃗ \in ℤ^n

, soit

V_(x⃗)

le volume de

K \cap (x⃗ + C)

où

C

est le cube

{y⃗ ∈ ℝ^n|0 ≤ y_i < 1, ∀i}

. En remarquant que

Vol(K) = \sum_(x⃗ \in ℤ^n)V_(x⃗)

et en considérant les intersections

C \cap (K - x⃗)

, montrer qu'il existe

z⃗_1 \in K

z⃗_2 \in K

tels que

z⃗_1 - z⃗_2 \in ℤ^n

Question 2.8. En considérant

1/2K

et en utilisant le fait que

K

est symétrique, montrer que si

Vol(K) > 2^n

, il existe

x⃗ \neq 0\to

tel que

x⃗ \in ℤ^n \cap K

(premier théorème de Minkowski). Montrer que ceci reste vrai si

Vol(K) \geq 2^n

K

est fermé.

Question 2.9. Montrer que

inf{λ > 0|(λK ∩ ℤ^n) ≠ {0→}} = min{f(x⃗)|x⃗ ∈ ℤ^n∖{0→}}

où

f

est la fonction de jauge de

K

. En déduire qu'il existe

x⃗ \in ℤ^n, x⃗ \neq 0\to

, tel que

f(x⃗) \leq 2Vol(K)^(- 1/n)

. Soit

A

une matrice carrée de taille

n

inversible. Montrer, par un changement de variable, qu'il existe

y⃗ \in ℤ^n, y⃗ \neq 0\to

, tel que

f(x⃗) \leq 2Vol(K)^(- 1/n)|det(A)|^(1/n)

où

x⃗ = Ay⃗

Question 2.10. Soit

A

une matrice carrée de taille

n

inversible. Soit

K = {x⃗ ∈ ℝ^n||x_i|≤1, ∀i}

. Montrer qu'il existe

y⃗ \in ℤ^n, y⃗ \neq 0\to

tel que

x⃗ = Ay⃗

vérifie

|x_i| \leq |detA|^(1/n)

pour tout

i

et donc

|x_1\dotsx_n| \leq |det(A)|

. En utilisant cette fois la fonction de jauge

f(x⃗) = \sum_i|x_i|/n

et une inégalité de convexité, montrer qu'on peut choisir

y⃗ ∈ ℤ^n∖{0→}

pour que

|x_1\dotsx_n| \leq |det(A)|n!/n^n

Question 2.11. Soit

A

une matrice de taille

n

telle que

|det(A)| = 1

c_1, \dots, c_n

des réels de produit égal à 1 . Montrer qu'il existe

y⃗ \in ℤ^n, y⃗ \neq 0\to

, tel que pour tout

i, |x_i| \leq c_i

où

x⃗ = Ay⃗

. En déduire le résultat d'approximation simultanée suivant : pour tous réels

α_1, \dots, α_n

N > 1

, il existe un entier positif non nul

q \leq N

et des entiers

p_1, \dots, p_n

tels que, pour tout

i, |α_i - (p_i)/q| \leq N^(- 1 - 1/n)

Partie 3. Minima successifs et réseaux admissibles

Soit

K \subset ℝ^n

un corps convexe symétrique par rapport à

0\to

f

sa fonction de jauge associée. On définit les minima successifs

λ_i(K)

, pour

1 \leq i \leq n

, de la façon suivante :

λ_i(K) = inf{λ|dim(λK ∩ ℤ^n) ≥ i}

où

dim(E)

est la dimension de l'espace vectoriel engendré par les vecteurs de

E

. En d'autres termes,

λ_i(K)

est le plus petit

λ

tel que

λK

contienne

i

vecteurs entiers linéairement indépendants. On a bien sûr

λ_1(K) \leq \dots \leq λ_n(K)

. S'il n'y a pas ambiguïté, on notera simplement

λ_i

au lieu de

λ_i(K)

Question 3.1. Montrer qu'on peut définir

n

vecteurs entiers

x⃗_1, \dots, x_n^(\to-)

, linéairement indépendants, tels que

f(x⃗_i) = λ_i

f(x⃗_i)

est la plus petite valeur de

f(x⃗)

pour

x⃗

dans

ℤ^n

qui n'est pas combinaison linéaire de

x⃗_1, \dots, x⃗_(i - 1)

Soit

a⃗_1, \dots, a⃗_n

une base de

ℝ^n

. L'ensemble

Λ

des combinaisons linéaires entières de ces vecteurs est appelé réseau engendré par (ou de base)

a⃗_1, \dots, a⃗_n

. Matriciellement

Λ = {x⃗|x⃗ = Ay⃗, y⃗ ∈ ℤ^n}

où

A

est la matrice dont les colonnes sont les

a⃗_i

. On dira aussi que

A

est une base de

Λ

Question 3.2. Montrer que si

A

B

sont deux bases d'un même réseau

Λ

alors il existe une matrice carrée

Q

entière, d'inverse entière, tel que

B = AQ

. En déduire que

|det(A)|

ne dépend pas de la base

A

d'un réseau. On l'appelle le déterminant du réseau, noté

det(Λ)

Soit

K

un corps convexe symétrique par rapport à

0\to

. On dit qu'un réseau

Λ

est admissible pour

K

K \cap Λ = {0\to}

. On définit

Δ(K) = inf{det(Λ)|Λ

admissible pour

K}

Question 3.3. Montrer que l'inégalité

2^n Δ(K) \geq Vol(K)

est une reformulation du premier théorème de Minkowski.

Soit

K

tel que

Vol(K) < 1

. Pour un nombre premier

p

u⃗ \in ℤ^n

tel que

u_1 = 1

0 \leq u_i < p

pour

2 \leq i \leq n

, on définit le réseau

Λ(p, u⃗)

de base

u⃗, (0, p, 0, \dots, 0), (0, 0, p, 0, \dots, 0), \dots, (0, \dots, 0, p)

Question 3.4. Montrer que, pour

p

fixé, pour tout

v⃗ \in ℤ^n

tel que

v_1

n'est pas un multiple de

p

, il existe un unique réseau

Λ(p, u⃗)

contenant

v⃗

. En déduire que

Y = {v⃗ ∈ ℤ^n|v_1

n'est pas multiple de

p}

est union disjointe de

p^(n - 1)

ensembles

Λ(p, u⃗) \cap Y

On considère, pour chaque

x⃗ \in p^(- (n - 1)/n)ℤ^n

(c'est-à-dire tel que

p^((n - 1)/n)x⃗

est entier), le cube

C_(x⃗) = x⃗ + p^(- (n - 1)/n)C

où

C

est le cube

{y⃗ ∈ ℝ^n|0 ≤ y_i < 1, ∀i}

. Ces cubes, tous de volume

p^(- (n - 1))

, forment une partition de

ℝ^n

et, si

#S

représente le nombre d'éléments d'un ensemble fini

S

, on a :

lim_(p → + ∞)p^(− (n − 1))#{x⃗ ∈ p^(− (n − 1)/n)ℤ^n|K ∩ C_(x⃗) ≠ ∅} = Vol(K) < 1

résultat intuitif que l'on admettra.

Question 3.5. Montrer que si

p

est choisi suffisamment grand, il existe un réseau

Λ(p, u⃗)

tel que

#(K \cap p^(- (n - 1)/n)(Λ(p, u⃗) \cap Y)) < 1

, c'est-à-dire

(p^((n - 1)/n)K) \cap (Λ(p, u⃗) \cap Y) = \emptyset

. De plus, si

p

est suffisamment grand pour que

|x_i| < p^(1/n)

pour tout

x⃗ \in K

, alors

(p^((n − 1)/n)K) ∩ Λ(p, u⃗) ⊆ {0→}

. En déduire qu'il existe un réseau admissible pour

K

de déterminant 1 .

Question 3.6. Soit

K

de volume quelconque. Montrer que

Δ(K) \leq Vol(K)

Partie 4. Réduction de base de Lovász et Scarf

Dans cette partie,

K \subset ℝ^n

est un corps convexe et on note

f

sa fonction de jauge associée. Étant donnée une base (

b⃗_1, \dots, b⃗_n

) du réseau

ℤ^n

, on définit

n

fonctions

f_i

, pour

1 \leq i \leq n

, par

f_i(x⃗) = inf{f(x⃗ + α_1 b⃗_1 + …α_(i − 1)b⃗_(i − 1))|α_1 ∈ ℝ, …, α_(i − 1) ∈ ℝ}

. Par définition,

f_1 = f

Question 4.1. Montrer que

f_i(x⃗) = g_i(π_i(x⃗))

où

π_i

est la projection sur l'espace vectoriel engendré par

b⃗_i, \dots, b⃗_n

, parallèlement à

b⃗_1, \dots, b⃗_(i - 1)

, et

g_i

est la fonction de jauge associée à

π_i(K)

Question 4.2. Montrer que si

f_1(b⃗_1) \leq f_2(b⃗_2) \leq \dots \leq f_n(b_n^(\to-))

alors

b⃗_1

atteint le premier minimum successif, c'est-à-dire

f(b⃗_1) = λ_1(K)

Il est difficile de trouver une base vérifiant les conditions précédentes. On s'intéresse alors à des conditions plus faibles. Soit

ε \in ℝ, 0 < ε < 1/2

. On dit que la base (

b⃗_1, \dots, b⃗_n

) est réduite si pour tout

i, 1 \leq i < n

:
(i)

f_i(b⃗_(i + 1) + μb⃗_i) \geq f_i(b⃗_(i + 1))

quel que soit

μ \in ℤ

.
(ii)

f_i(b⃗_(i + 1)) \geq (1 - ε)f_i(b⃗_i)

Pour construire une base réduite pour

n \geq 2

, on applique l'algorithme suivant.
Étape 1 : Soit

(b⃗_1, \dots, b⃗_n)

une base de

ℤ^n

, par exemple la base canonique, et poser

i = 1

.
Étape 2 : Remplacer

b⃗_(i + 1)

par

b⃗_(i + 1) + μb⃗_i

tel que

f_i(b⃗_(i + 1) + μb⃗_i)

soit minimal.
Étape 3 : Si

f_i(b⃗_(i + 1)) < (1 - ε)f_i(b⃗_i)

, échanger

b⃗_i

b⃗_(i + 1)

, et remplacer

i

par

max(1, i - 1)

; sinon remplacer

i

par

i + 1

.
Étape 4: Si

i < n

, aller à l'étape 2 sinon STOP.

Question 4.3. Montrer que cet algorithme finit par s'arrêter et construit bien une base réduite.
On admettra que lorsque

K

est de la forme

{x⃗ ∈ ℝ^n|Ax⃗ ≤ b⃗}

où

A

est une matrice entière de taille

n \times m

b⃗ \in ℤ^m

, alors on sait implanter cet algorithme par des techniques reliées aux résultats de la partie 1 .

Question 4.4. En remarquant que

f_(i + 1)(b⃗_(i + 1)) = min{f_i(b⃗_(i + 1) + αb⃗_i)|α ∈ ℝ}

, montrer que si (

b⃗_1, \dots, b⃗_n

) est une base réduite, alors pour tout

i, 1 \leq i < n, f_(i + 1)(b⃗_(i + 1)) \geq (1/2 - ε)f_i(b⃗_i)

, puis que

λ_1(K) \leq f(b⃗_1) \leq λ_1(K)(1/2 - ε)^(1 - n)

On dit qu'une base

(c⃗_1, \dots, c⃗_n)

ℤ^n

est propre si, pour tous

i

j

tels que

j < i

, les fonctions

f_i

définies à partir de cette base vérifient

f_j(c⃗_i + μc⃗_j) \geq f_j(c⃗_i)

quel que soit

μ \in ℤ

Question 4.5. Soit

(b⃗_1, \dots, b⃗_n)

est une base de

ℤ^n

. Montrer que, quels que soient

μ_(i, j) \in ℤ^n

j < i

, la famille (

c⃗_1, \dots, c⃗_n

) définie par

c⃗_i = b⃗_i + \sum_(j = 1)^(i - 1)μ_(i, j)b⃗_j

est une base de

ℤ^n

telle que les fonctions

f_i

définies à partir de la première base sont les mêmes que celles définies à partir de la seconde. Montrer qu'il existe

μ_(i, j), j < i

, tels que la base (

c⃗_1, \dots, c⃗_n

) soit propre et qu'elle est réduite si la base (

b⃗_1, \dots, b⃗_n

) l'est.

Dans la suite, on suppose que

(b⃗_1, \dots, b⃗_n)

est une base réduite de

ℤ^n

.
Question 4.6. On suppose d'abord que (

b⃗_1, \dots, b⃗_n

) est réduite propre. En s'inspirant de la démonstration de la question 4.4, montrer par une récurrence descendante sur

j

que, pour tout

j < i

f_j(b⃗_i) \leq f_i(b_i\to) + 1/2(f_(i - 1)(b⃗_(i - 1)) + \dots + f_j(b⃗_j))

, puis

f_1(b⃗_i) \leq f_i(b⃗_i)(1/2 - ε)^(1 - i)

et enfin

λ_i(K) \leq f_i(b⃗_i)(1/2 - ε)^(1 - i)

. Pourquoi cette dernière relation est-elle vraie même si la base n'est pas propre?

Question 4.7. Soient

x⃗_i = \sum_(j = 1)^n x_(i, j)b⃗_j, 1 \leq i \leq n, n

vecteurs linéairement indépendants tels que

f(x⃗_i) = λ_i(K)

. Montrer que pour tout

i

, il existe

j \leq i \leq k

tels que

x_(j, k) \neq 0

. En considérant, pour

i

fixé, le plus grand

k

tel que

x_(j, k) \neq 0

j \leq i \leq k

, montrer que

λ_i(K) \geq λ_j(K) \geq f_i(b⃗_i)(1/2 - ε)^(n - i)

On obtient donc un algorithme, basé sur la fonction de jauge d'un corps convexe polyédral

K

, pour l'approximation de ses minima successifs.

Pas de description pour le moment

Commentaires• ENS Informatique Fondamentale (Maths Info) MP PC 2008

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 (groupe I) Épreuve commune aux ENS de Paris, Lyon et Cachan Filière PC (groupe I) Épreuve commune aux ENS de Paris et Lyon \title{ MATHÉMATIQUES - INFORMATIQUE

Les calculatrices sont inutiles et de ce fait ne sont pas autorisées

Partie 1. Lemme de Farkas et théorème de dualité

Question 1.4.

Partie 2. Corps convexes, normes et premier théorème de Minkowski

Partie 3. Minima successifs et réseaux admissibles

Partie 4. Réduction de base de Lovász et Scarf

Commentaires• ENS Informatique Fondamentale (Maths Info) MP PC 2008

Commentaires• ENS Informatique Fondamentale (Maths Info) MP PC 2008

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
\title{ MATHÉMATIQUES - INFORMATIQUE