Rappelons qu'une partie de Rn est dite minimale si sa mesure de Hausdorff d-dimensionnelle ne peut être rendue plus petite par déformation dans une classe de compétiteurs adaptée. On peut citer comme exemple le problème de Plateau standard, pouvant se réécrire comme celui de trouver un ensemble minimal pour les déformations à support relativement compact dans un domaine, la frontière du domaine jouant alors le rôle d'une condition topologique de bord. Un ensemble quasiminimal au sens d'Almgren n'est pas forcément minimal puisque sa mesure peut décroître après déformation, mais seulement de manière contrôlée relativement à la mesure des points qui ont été déformés. Par exemple le graphe d'une application lipschitzienne de Rd dans Rn-d est quasiminimal et de façon générale, on sait (voir [A]) que les ensembles quasiminimaux sont rectifiables. Lorsqu'on considère la réduction E* d'un ensemble quasiminimal E, qui consiste à prendre le support de la mesure de Hausdorff k-dimensionnelle restreinte à E — en gros en enlevant les points dont la contribution à la mesure de E est nulle — on sait en outre (voir [DS]) que E* contient de grandes images lipschistziennes et est uniformément rectifiable. Une autre propriété remarquable concerne les limites de Hausdorff de suites d'ensembles quasiminimaux réduits. Dans ce contexte, non seulement la limite est quasiminimale et réduite, mais en outre la mesure de Hausdorff est semi-continue inférieurement (voir par exemple [D1]), ce qui n'est généralement pas le cas. Cette propriété fait des limites de suites minimisantes d'ensembles quasiminimaux les candidates idéales à la résolution de problèmes d'existence sous contrainte topologique stable par déformation. On propose ici, dans le cadre d'un problème sur un ouvert en dimension et codimension quelconques, un premier résultat d'existence utilisant une méthode systématique pour construire une suite minimisante d'ensembles quasiminimaux, par minimisation finie sur les sous-faces d-dimensionnelles de grilles polyédrales adaptées. La construction de telles grilles est assez délicate, puisqu'on s'impose à la fois de faire l'approximation polyédrale d'un ensemble rectifiable le long de certains plans tangents pour contrôler l'augmentation de mesure correspondante, tout en gardant un contrôle uniforme sur la régularité des polyèdres de façon à éviter qu'ils ne soient trop plats. Des bornes uniformes sur la forme des polyèdres sont en effet utilisées lors de la discrétisation polyédrale des compétiteurs du problème — mettant en jeu des projections radiales successives sur la frontière des sous-faces de dimension décroissante de n à d — et permettent d'obtenir automatiquement une constante de quasiminimalité ne dépendant que de n et d. La suite d'ensembles quasiminimaux obtenue converge alors en distance de Hausdorff sur tout compact du domaine vers un ensemble minimal — ou presque-minimal dans le cas d'une fonctionnelle Jd h(E) = R hdHd avec une fonction h continue à valeurs dans [1,M]. L'existence de rétractions lipschitziennes sur la limite obtenue (donnée par le théorème de Jean Taylor dans [T] pour le cas d = 2, n = 3) devrait alors permettre d'affirmer que la limite fait encore partie de la classe topologique initiale considérée. Le résultat d'existence pourrait encore se généraliser à certains problèmes sur des variétés sans bord, ou dans une certaine mesure à des domaines fermés pour lesquels on connait une rétraction lipschitzienne d'un voisinage sur le bord.

.

Cette thèse s'inscrit dans la vérification automatique de propriétés <br />numériques de programmes, principalement des logiciels embarqués. Lors de la <br />vérification on doit représenter de façon finie des ensembles éventuellement <br />infinis de valeurs, pour cela une solution possible est l'utilisation de <br />polyèdres convexes. Cette <br />représentation est précise mais coûteuse ce qui limite le nombre de variables <br />qu'il est possible de manipuler. Le but de cette thèse est d'augmenter le <br />nombre maximal de variables qu'il est possible de représenter. Deux approches <br />ont été envisagées puis testées. Dans un premier temps on a voulu tirer <br />profit de la présence d'équations affines pour éliminer une variable par <br />équation. Cette approche s'est révélée, expérimentalement, assez décevante. <br />Une autre approche, bien plus prometteuse, est l'utilisation du produit <br />cartésien. L'idée est alors de représenter indépendamment les variables dont <br />l'évolution n'est pas liée. Cette décomposition peut être améliorée grâce à <br />un changement de base. Un analyseur a été réalisé afin de <br />tester ces deux approches.

Ce travail de thèse de doctorat traite de l'étude d'un problème d'ordonnancement NP-difficile au sens fort à contraintes de ressource : le problème de la programmation des déplacements de processus. Ce problème, issu de l'industrie des télécommunications, est lié à l'opérabilité de certains systèmes temps réel répartis à haute disponibilité tels le BSCe3, un autocommutateur pour la téléphonie cellulaire commercialisé par Nortel.<br />En quelques mots, ce problème consiste, étant donnée une répartition arbitraire admissible de processus sur les processeurs d'un système réparti, à trouver une séquence d'opérations (migrations de processus sans effet sur le service ou arrêts temporaires) de moindre impact par le biais de laquelle une autre répartition arbitraire, et fixée à l'avance, peut être obtenue. La principale contrainte réside dans le fait que la capacité des processeurs du système ne doit pas être dépassée durant la reconfiguration.<br />Nous avons abordé ce problème d'ordonnancement sous différents angles. Tout d'abord, nous avons établi son caractère NP-difficile au sens fort et exhibé quelques cas particuliers polynomiaux. Puis, sur le plan de la résolution exacte dans le cas général, nous avons conçu deux algorithmes de recherche arborescente : le premier trouve ses fondements dans l'étude de la structure combinatoire du problème, le second dans des considérations polyédrales. De nombreux résultats expérimentaux illustrent la pertinence pratique de ces deux algorithmes. Enfin, en raison des contraintes imposées par le caractère temps réel de notre application industrielle, nous avons mis au point un algorithme efficace de résolution approchée basé sur la métaheuristique du recuit simulé et, en capitalisant sur nos travaux en résolution exacte, empiriquement vérifié sa capacité pratique à produire des solutions acceptables, en un sens bien défini.

Un polyèdre fuchsien de l'espace hyperbolique est une surface polyédrale invariante sous l'action d'un groupe fuchsien d'isométries (c.a.d. un groupe d'isométries qui laissent globalement invariante une surface totalement géodésique et sur laquelle il agit de manière cocompacte). La métrique induite sur un polyèdre fuchsien convexe est isométrique à une métrique hyperbolique avec des singularités coniques de courbure singulière positive sur une surface compacte de genre $>1$. On démontre que ces métriques sont en fait réalisées par un unique polyèdre fuchsien convexe (modulo les isométries globales). Ce résultat étend un théorème célèbre de A.D. Alexandrov. <br />On montre aussi que chaque métrique à courbure constante avec des courbures singulières négatives sur une surface compacte de genre $>1$ peut-être réalisée par un unique polyèdre ``fuchsien'' convexe dans un espace modèle lorentzien.<br />Finalement on présente des extensions possibles de ces résultats, ce qui amène à des énoncés généraux sur la réalisation de métriques sur les surfaces.

Agrégation de l'enseignement supérieur, Orientation sciences / Thèse d'agrégation / info:eu-repo/semantics/nonPublished

Cette thèse porte sur la modélisation morphologique de matériaux cimentaires, et sur l'analyse de leurs propriétés linéaires élastiques. Dans cet objectif, des images 3D, obtenues par micro-tomographie, de matériaux cimentaires (mortier et béton) sont étudiées. Dans un premier temps, l'image de mortier est segmentée afin d'obtenir une image de microstructure réelle pour des calculs en élasticité linéaire. L'image de béton est utilisée, après traitement, pour la détermination des caractéristiques morphologiques du matériau. Un modèle aléatoire de béton est ensuite développé et validé par des données morphologiques. Ce modèle comporte trois phases qui correspondent à la matrice, les granulats et les pores. La phase des granulats est modélisée par implantation sans recouvrement de polyèdres de Poisson. Pour cela, un algorithme de génération vectorielle de polyèdres de Poisson est mis en place et validé par des mesures morphologiques. Enfin, les propriétés linéaires élastiques effectives de la microstructure de mortier et de microstructures simulées sont déterminées par méthode FFT (Fast-Fourier Transform), pour différents contrastes entre le module de Young des granulats et de la matrice. Cette étude des propriétés effectives est complétée par une analyse locale des champs dans la matrice, afin de déterminer l'arrangement spatial entre les zones de concentration de contraintes dans la matrice, et les différentes phases de la microstructure (granulats et pores). Une caractérisation statistique des champs est de plus réalisée, avec notamment le calcul du Volume Élémentaire Représentatif (VER). Une comparaison des propriétés élastiques effectives et locales obtenues d'une part sur une microstructure simulée contenant des polyèdres et d'autre part sur une microstructure contenant des sphères est de plus effectuée.

Dans le premier chapitre on précise les définitions et notations utilisées par la suite et on rappelle certains résultats nécessaires ultérieurement. Dans le deuxième chapitre on définit à partir de deux ensembles convexes K1 et K2, le produit tensoriel direct note K1 cercle X K2 et polaire K1 d'Alemb. K2. Au troisième chapitre on étudie quelques propriétés faciales de K1 cercle x K2 et de K1d'alemb. K2. Au quatrième chapitre on étudie la relation entre K1 cercle X K2 et K1d'Alemb. K2. Enfin on étudie le produit tensoriel direct et le produit tensoriel polaire dans les cas suivants : K1 et k2 sont des hypersphères, K1 et K2 sont des polaires d'hypercubes, K1 et K2 sont des hypercubes.

No description available.

Cette thèse s'inscrit dans le domaine de l'optimisation combinatoire. Elle utilise l'approche polyèdrale pour résoudre des problèmes combinatoires qui se posent dans le contexte des réseaux de télécommunications. Nous introduisons et étudions le problème de synthèse de réseaux à composantes connexes unicycliques. Après avoir rappelé que le problème est facile à résoudre en absence d'autres contraintes, nous étudions de nouvelles variantes en intégrant de nouvelles contraintes techniques. Nous commençons par une contrainte portant sur la taille des cycles. Nous souhaitons interdire tous les cycles contenant au plus p sommets. Le problème est alors NP-Difficile. Des inégalités valides sont alors proposées pour ce problème. On montre sous des conditions bien précises que ces inégalités peuvent être des facettes. Plusieurs algorithmes polynomiaux ont été proposés pour la séparation des inégalités valides. Ces algorithme sont mis en oeuvre et des résultats numériques sont donnés. Nous nous focalisons par la suite sur un nouveau problème dit de Steiner consistant à partitionner un réseau en composantes unicycliques tout en imposant que certains sommets soient sur les cycles. On montre alors que ce problème est facile au sens de la complexité algorithmique en proposant un algorithme polynomial et une formulation étendue du problème. On présente également une description partielle de l'enveloppe convexe des vecteurs d'incidence de ces réseaux. La séparation des inégalités est également étudiée. Nous proposons notamment une généralisation de l'algorithme de Padberg-Rao pour séparer les inégalités Blossom. D'autres contraintes techniques sont prises en compte : contraintes de degrés, contrainte sur le nombre de composantes connexes, appartenance de certains sommets à une même composante connexe et enfin la séparation de certains sommets qui doivent être sur des composantes différentes. Enfin, nous faisons une étude spectrale de deux classes spécifiques de graphes unicycliques. Mots clés : Optimisation Combinatoire, Polyèdres, Algorithme à Plans Coupants, Graphes