J-0
00m
00j
00h
00min
00s

Version interactive avec LaTeX compilé

Télécharger PDF

ENS Informatique Fondamentale (Maths Info) MP PC 2008

Notez ce sujet en cliquant sur l'étoile
0.0(0 votes)
Logo ens
🔗 Explorer
Banque
X-ENS
Année
2008
Filière
MP/PC
Matière
Maths Info
X-ENS MP/PCX-ENS 2008MP/PC Maths InfoMaths Info 2008
2025_08_29_9fc0783346904d114586g

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 , muni du produit scalaire usuel. Si est un vecteur de , on note sa -ème composante, pour . Si et , on note leur produit scalaire. Les opérations portant sur des vecteurs sont à comprendre composante par composante : ainsi, signifie pour tout . 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 et une matrice de taille , on note le produit de par étant considéré comme vecteur colonne, et le produit de par étant considéré comme vecteur ligne. Enfin, on utilise les notations ensemblistes suivantes : si et , on note l'ensemble des vecteurs avec l'ensemble des vecteurs avec , et l'ensemble des vecteurs avec et .

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

Un ensemble est convexe si . C'est un cône si . S'il existe une matrice à coefficients réels, de taille , telle que , on dit que est un cône polyédral. S'il existe tels que avec , on dit que est le cône engendré par . Dans ce cas, on peut aussi écrire matriciellement : où cette fois-ci est de taille et les sont les colonnes de .
Question 1.1. Vérifier qu'un cône polyédral (respectivement engendré) est bien un cône. Montrer que est un cône si et seulement s'il est convexe et . Montrer qu'un cône polyédral est intersection de demi-espaces, c'est-à-dire d'ensembles de la forme .
Pour , on définit le polaire de comme l'ensemble .
Question 1.2. Montrer les propriétés suivantes : a) est convexe, b) ; c) si est un cône, est un cône et ; d) si est un cône engendré, est un cône polyédral ; e) si est un cône polyédral, .
Soit une matrice réelle de taille , de rang et de dimension . On note les colonnes de et un ensemble constitué de vecteurs linéairement indépendants parmi ces vecteurs. On effectue les opérations suivantes:
Étape 1 : Écrire (de façon unique) comme .
Étape 2: Choisir, s'il existe, l'indice minimal tel que , sinon STOP.
Étape 3 : Soit tel que pour tout et . Choisir, s'il existe, l'indice minimal tel que , sinon STOP.
Étape 4 : Remplacer par et reprendre à l'étape 1.
Question 1.3. On note le cône engendré par les vecteurs .
  1. Montrer que l'algorithme précédent est bien défini, que s'il stoppe à l'étape 2 alors et que s'il stoppe à l'étape 3 alors il existe tel que et .
  2. Montrer que l'algorithme ne boucle pas. Indication : s'il existe deux itérations pour lesquelles l'ensemble est le même, on pourra considérer le plus grand indice tel que quitte (à l'itération ) et y retourne (à l'itération ) avec et calculer avec exprimé dans la base utilisée à l'étape .
  3. En déduire le lemme de Farkas : de deux choses l'une, soit il existe tel que , soit il existe tel que et pour ( ) vecteurs linéairement indépendants.
On admettra que le lemme de Farkas se généralise au cas où est une matrice quelconque : dans ce cas, la condition portant sur est que est orthogonal à vecteurs linéairement indépendants où est le rang de . On sera également amené à utiliser l'énoncé (légèrement affaibli) suivant : il existe tel que si et seulement si implique .

Question 1.4.

  1. En utilisant le lemme de Farkas, montrer que si un est cône engendré alors et est polyédral. Pour ce deuxième point, utiliser la condition supplémentaire du lemme de Farkas portant sur : " pour vecteurs linéairement indépendants".
  2. Montrer que si est un cône polyédral, il est engendré. On pourra considérer un cône engendré tel que .
Question 1.5. On note la matrice identité de taille . Soit une matrice réelle de taille , et . Montrer, en considérant la matrice ( ), de taille , et le lemme de Farkas, qu'il existe tel que si et seulement si pour tout tel que . Montrer ensuite le théorème de dualité suivant. Si et sont non vides alors :
Pour cela, on montrera, en utilisant la première partie de la question, qu'il existe et tels que :
(Tous les vecteurs sont ici des vecteurs colonnes. On utilise la notation 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 , on définit . On rappelle que pour est une norme.
Question 2.1. Soit la fonction définie par .
  1. Rappeler pourquoi la fonction est bien définie sur et .
  2. Montrer que , par un calcul d'intégrale double et en remarquant que si et seulement si .
Question 2.2. On note le volume de , la boule de rayon en dimension pour la norme . Établir une relation entre et puis entre et et montrer finalement que :
quoi est égal ce volume lorsque ?
Soit . On rappelle que appartient à l'adhérence de , notée , si est limite d'une suite d'éléments de et que appartient à l'intérieur de , noté , s'il existe tel que la boule de centre et de rayon appartient à .
Question 2.3. Montrer que si est convexe, son adhérence et son intérieur sont convexes. Montrer que si, de plus, alors si et si . (Ne pas hésiter à s'aider de dessins pour toutes ces propriétés.)
Un corps convexe est un convexe borné tel que . On lui associe la fonction de jauge définie par pour tout et .
Question 2.4. Montrer que la fonction de jauge d'un corps convexe est bien définie et que :
(i) si ;
(ii) si .
(iii) si et .
Pour démontrer (iii), on commencera par montrer que puis, en utilisant les résultats de la question 2.3, que si et seulement si et si et seulement si .
On remarque que lorsque est symétrique par rapport à , c'est-à-dire si et seulement si , alors sa fonction de jauge vérifie de plus , c'est donc une norme.
Question 2.5. Réciproquement, soit une fonction de dans satisfaisant les propriétés (i), (ii) et (iii) précédentes. Montrer qu'il existe tel que pour tout . En déduire que est continue en , puis sur . Montrer enfin que l'ensemble est un corps convexe dont est la fonction de jauge.
Lorsque est une norme, donc lorsque possède en plus la propriété , il est facile de voir que le corps convexe est symétrique par rapport à . On suppose que c'est le cas dans tout le reste de cette partie.
Question 2.6. Montrer que la fonction de jauge du polaire d'un ensemble est égal à .
Dans la suite, on parlera de volumes sans se préoccuper de questions théoriques d'existence et on notera le volume de . On utilisera en particulier la relation en dimension pour tout .
Question 2.7. On suppose que . Pour , soit le volume de où est le cube . En remarquant que et en considérant les intersections , montrer qu'il existe et tels que .
Question 2.8. En considérant et en utilisant le fait que est symétrique, montrer que si , il existe tel que (premier théorème de Minkowski). Montrer que ceci reste vrai si et est fermé.
Question 2.9. Montrer que où est la fonction de jauge de . En déduire qu'il existe , tel que . Soit une matrice carrée de taille inversible. Montrer, par un changement de variable, qu'il existe , tel que où .
Question 2.10. Soit une matrice carrée de taille inversible. Soit . Montrer qu'il existe tel que vérifie pour tout et donc . En utilisant cette fois la fonction de jauge et une inégalité de convexité, montrer qu'on peut choisir pour que .
Question 2.11. Soit une matrice de taille telle que et des réels de produit égal à 1 . Montrer qu'il existe , tel que pour tout où . En déduire le résultat d'approximation simultanée suivant : pour tous réels et , il existe un entier positif non nul et des entiers tels que, pour tout .

Partie 3. Minima successifs et réseaux admissibles

Soit un corps convexe symétrique par rapport à et sa fonction de jauge associée. On définit les minima successifs , pour , de la façon suivante :
où est la dimension de l'espace vectoriel engendré par les vecteurs de . En d'autres termes, est le plus petit tel que contienne vecteurs entiers linéairement indépendants. On a bien sûr . S'il n'y a pas ambiguïté, on notera simplement au lieu de .
Question 3.1. Montrer qu'on peut définir vecteurs entiers , linéairement indépendants, tels que et est la plus petite valeur de pour dans qui n'est pas combinaison linéaire de .
Soit une base de . L'ensemble des combinaisons linéaires entières de ces vecteurs est appelé réseau engendré par (ou de base) . Matriciellement où est la matrice dont les colonnes sont les . On dira aussi que est une base de .
Question 3.2. Montrer que si et sont deux bases d'un même réseau alors il existe une matrice carrée entière, d'inverse entière, tel que . En déduire que ne dépend pas de la base d'un réseau. On l'appelle le déterminant du réseau, noté .
Soit un corps convexe symétrique par rapport à . On dit qu'un réseau est admissible pour si . On définit admissible pour .
Question 3.3. Montrer que l'inégalité est une reformulation du premier théorème de Minkowski.
Soit tel que . Pour un nombre premier et tel que et pour , on définit le réseau de base .
Question 3.4. Montrer que, pour fixé, pour tout tel que n'est pas un multiple de , il existe un unique réseau contenant . En déduire que n'est pas multiple de est union disjointe de ensembles .
On considère, pour chaque (c'est-à-dire tel que est entier), le cube où est le cube . Ces cubes, tous de volume , forment une partition de et, si représente le nombre d'éléments d'un ensemble fini , on a :
résultat intuitif que l'on admettra.
Question 3.5. Montrer que si est choisi suffisamment grand, il existe un réseau tel que , c'est-à-dire . De plus, si est suffisamment grand pour que pour tout , alors . En déduire qu'il existe un réseau admissible pour de déterminant 1 .
Question 3.6. Soit de volume quelconque. Montrer que .

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

Dans cette partie, est un corps convexe et on note sa fonction de jauge associée. Étant donnée une base ( ) du réseau , on définit fonctions , pour , par . Par définition, .
Question 4.1. Montrer que où est la projection sur l'espace vectoriel engendré par , parallèlement à , et est la fonction de jauge associée à .
Question 4.2. Montrer que si alors atteint le premier minimum successif, c'est-à-dire .
Il est difficile de trouver une base vérifiant les conditions précédentes. On s'intéresse alors à des conditions plus faibles. Soit . On dit que la base ( ) est réduite si pour tout :
(i) quel que soit .
(ii) .
Pour construire une base réduite pour , on applique l'algorithme suivant.
Étape 1 : Soit une base de , par exemple la base canonique, et poser .
Étape 2 : Remplacer par tel que soit minimal.
Étape 3 : Si , échanger et , et remplacer par ; sinon remplacer par .
Étape 4: Si , 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 est de la forme où est une matrice entière de taille et , alors on sait implanter cet algorithme par des techniques reliées aux résultats de la partie 1 .
Question 4.4. En remarquant que , montrer que si ( ) est une base réduite, alors pour tout , puis que .
On dit qu'une base de est propre si, pour tous et tels que , les fonctions définies à partir de cette base vérifient quel que soit .
Question 4.5. Soit est une base de . Montrer que, quels que soient , , la famille ( ) définie par est une base de telle que les fonctions définies à partir de la première base sont les mêmes que celles définies à partir de la seconde. Montrer qu'il existe , tels que la base ( ) soit propre et qu'elle est réduite si la base ( ) l'est.
Dans la suite, on suppose que est une base réduite de .
Question 4.6. On suppose d'abord que ( ) est réduite propre. En s'inspirant de la démonstration de la question 4.4, montrer par une récurrence descendante sur que, pour tout , , puis et enfin . Pourquoi cette dernière relation est-elle vraie même si la base n'est pas propre?
Question 4.7. Soient vecteurs linéairement indépendants tels que . Montrer que pour tout , il existe tels que . En considérant, pour fixé, le plus grand tel que et , montrer que .
On obtient donc un algorithme, basé sur la fonction de jauge d'un corps convexe polyédral , pour l'approximation de ses minima successifs.
ENS Informatique Fondamentale (Maths Info) MP PC 2008 - Version Web LaTeX | WikiPrépa | WikiPrépa