Cette thèse présente différents aperçus de problèmes de mathématiques discrètes en lien avec la théorie des graphes. Elle s'intéresse en particulier à la coloration de graphes, i.e. l'assignation de couleurs aux sommets (ou arêtes) d'un graphes sous certaines contraintes locales, notamment l'exclusion de motifs. Pour différents types de coloration (choisissabilité des sommets, des arêtes, coloration acyclique ou linéaire, ...), un état de l'art est présenté, accompagné de résultats d'existence sur les graphes planaires ou leurs sous-classes, ayant pour but de minimiser le nombre de couleurs nécessaires pour un degré maximum ou un degré moyen maximum (Mad) donnés. Cette thèse traite également de décompositions induites de graphes, et démontre qu'il existe pour tout graphe $H$ une suite infinie de graphes denses dont les arêtes peuvent être partitionnées en copies induites de $H$. Cette preuve requiert le formalisme des hypergraphes, pour lesquels un autre résultat de décomposition est démontré, i.e. une décomposition optimale de l'hypergraphe complet 3-régulier en hypergraphes $\alpha$-acycliques. La troisième parti porte sur des questions algorithmiques. Elles consistent en problèmes d'optimisation ou d'existence, motivés par le routage d'information dans les réseaux, analysés par le formalisme classique de complexité algorithmique, ou traitent de la recherche de sous-graphes dans le formalisme de la complexité paramétrée. Dans une quatrième partie sont considérés des problèmes de comptage issus de la chimie, suivis de la présentation de Programmes Linéaires Entiers utilisés dans le logiciel de mathématiques Sage.

L'électro- et la magnéto-encéphalographie sont deux techniques très utiles pour observer l'activité électrique du cerveau de par leur résolution temporelle et leur caractère non invasif. Les mesures sont faites sur la surface extérieure de la tête (électrodes pour l'EEG et magnétomètres pour la MEG); afin de retrouver les sources responsables du signal mesuré, un problème inverse de localisation doit être résolu. Celui-ci requiert une bonne résolution du problème direct, ce qui demande une bonne modélisation des tissus de la tête, ainsi qu'une représentation fidèle de ce modèle électro-physiologique par une méthode numérique comme la FEM ou la BEM. Dans cette thèse, nous nous intéressons au choix critique d'un modèle et de sa représentation par une méthode numérique notamment pour prendre en compte l'inhomogénéité de la conductivité du crâne et celle de la matière blanche qui est proche des sources. Après avoir mis en évidence les avantages et inconvénients des méthodes courantes, nous exposons une méthode duale de résolution du problème direct: c'est la méthode adjointe applicable quel que soit la méthode numérique choisie. Puis en utilisant une approche de décomposition de domaine nous formulons plusieurs méthodes de couplage de méthodes numériques visant à tirer parti de leurs avantages dans des sous domaines. Cela permet de coupler la BEM avec la FEM, et implique de nombreux aspects intéressants notamment pour une bonne prise en compte du crâne. Finalement, nous proposons une nouvelle méthode permettant de traiter des conductivités localement anisotropes ou inhomogènes avec la BEM.

Il existe deux stratégies principales pour fabriquer des engrenages, liées à l'ordre d'enchaînement de l'usinage de finition et du traitement thermique. Dans le cas qui nous occupe ici chez Renault, la majorité des pièces produites adopte un processus où le traitement thermique termine la gamme de fabrication, ce qui n'autorise aucune modification de la géométrie de la denture en sortie de trempe. Il est donc primordial d'analyser les déformations qui apparaissent lors de cette étape. Indépendamment de ces stratégies de fabrication, la vie d'une pièce peut être divisée en deux phases : la mise au point et la vie série. Chaque période génère des problématiques séparées. Pour la première, il est utile de connaître au préalable la déformation de la pièce lors du traitement thermique, voire des autres opérations de la gamme. Un état de l'art des modélisations phénoménologiques actuelles est donc dressé, ainsi qu'une liste des données nécessaires au calcul. L'applicabilité de la simulation numérique à ce problème est alors étudiée. Une bonne corrélation qualitative a été observée entre simulation et données expérimentales. Cependant, étant donné la complexité des donnée nécessaires et la détermination des conditions aux limites, une autre possibilité a également été développée, structurée autour d'une base de données recensant les déformations des engrenages de chaque site. Cette méthodologie a été implémentée dans une application qui est maintenant utilisée sur tous les sites de mécanique Renault. Une fois cette mise au point terminée, la pièce entre dans la deuxième phase, la vie série. Celle-ci voit apparaître alors un second type de problème : la dérive du processus nominal. Cette dérive peut être occasionnée par exemple par une matière légèrement modifiée, des conditions d'usinage optimisées ou une variation du traitement thermique qui échappe aux contrôles classiques mis en place. Nous nous attachons ici principalement aux dérives qui provoquent une variation dimensionnelle de la pièce mais le principe peut être appliqué à d'autres variations. Retrouver le plus rapidement possible l'origine d'une telle dérive et la corriger alors que la production est arrêtée est impératif. Nous proposons donc ici les fondements d'une méthode permettant de reconnaître l'origine d'une dérive identifiée à partir de la seule mesure de la déformation de la pièce. Une base des dérives possibles est créée en réalisant une décomposition modale (POD) des simulations numériques représentant les variations du process. En projetant la mesure réelle sur cette base, nous sommes ainsi capables d'identifier l'origine de la dérive et donc de réduire les délais d'analyse du problème.

La vulnérabilité des systèmes électriques est l'un des problèmes liés à leur complexité. Il a fait l’objet d’une attention croissante des chercheurs au cours des dernières décennies. Malgré cela, les phénomènes fondamentaux qui régissent la vulnérabilité du système ne sont pas encore bien compris.Comprendre comment la vulnérabilité des réseaux électriques émerge de leur topologie est la motivation principale du présent travail. Pour cela, le présent travail de recherché propose une nouvelle méthode pour évaluer la vulnérabilité des systèmes électriques et identifier leurs éléments les plus critiques. La méthode permet d’avoir une bonne compréhension des liens entre la topologie d’un réseau et sa vulnérabilité à des pertes d’ouvrages (lignes ou transformateurs).La première partie de ce travail consiste en une analyse critique des approches rencontrées dans la littérature, s’appuyant sur la théorie des graphes, pour analyser la vulnérabilité des réseaux électriques. Les résultats fournis par ces approches pour quatre réseaux IEEE sont comparés à ceux fournis par une analyse de contingence de référence, basée sur une résolution d’un load-flow AC. Des avantages et inconvénients de chaque approche est tirée une méthode améliorée pour l'évaluation de la vulnérabilité des réseaux électriques aux pertes d’ouvrage. Cette méthode est basée sur une approximation courant continue du load flow.La deuxième partie propose une nouvelle approche basée sur la théorie spectrale des graphes et son utilisation pour la résolution d’un load flow DC. Elle permet de mieux comprendre comment la vulnérabilité des réseaux électriques et leurs composants critiques émergent de la topologie du graphe sous-jacent au réseau. / The vulnerability of electrical systems is one of the problems related to their complexity. It has received increasing attention from researchers in recent decades. Despite this, the fundamental phenomena that govern the vulnerability of the system are still not well understood.Understanding how the vulnerability of power systems emerges from their complex organization is, therefore, the main motivation of the present work. It proposes the definition of a standard method to assess the vulnerability of power systems and identify their most critical elements. The method enables a better understanding of the links between the topology of the grid and the line outage vulnerabilities.The first part of this research work offers a critical review of literature approaches used to assess system vulnerability. The results provided by these approaches for four IEEE test systems are confronted to a reference contingency analysis using AC power flow calculations. From these analyses, pros and cons of each approach are outlined. An improved method for assessment of system vulnerability to line outages is defined from this confrontation. It is based on DC load flow and graph theory.The second part proposes a new approach based on spectral graph theory and solving of DC power flow to identify how system vulnerability and critical components emerge from the power network topology.

L'imagerie médicale échographique présente plusieurs avantages comme son innocuité, sa facilité d'emploi, la diversité des organes concernés et le faible coût de ce mode d'imagerie. Cependant les images obtenues par échographique souffrent d'une résolution plutôt faible comparées à celle que l'on peut obtenir avec un appareil d'IRM ou en utilisant des rayons X. Le défi majeur de l'échographie médicale est donc de réussir à produire des images avec une résolution beaucoup plus fine, à fréquence nominale fixe.Des travaux ont été entrepris dans ce sens depuis longtemps. Plusieurs pistes ont été explorées. La majorité des travaux effectués jusqu'à présent a consisté à travailler sur l'échographe et particulièrement sur les sondes ultrasonores, avec principalement pour objectif d'augmenter la fréquence des ultrasons utilisés. Cette approche a conduit à l'existence de l'échographie haute résolution, avec cependant une limite importante qui est celle de la profondeur d'exploration.Une autre approche consiste à traiter numériquement des images échographiques classiques pour améliorer leur résolution. Cette méthode a plusieurs avantages, elle permet notamment de contourner la difficulté causée par la réduction de profondeur de champ liée à l'augmentation de la fréquence ultrasonore.Dans cette thèse, nous présentons une méthode permettant d'améliorer la résolution des images échographiques. Le travail de thèse à consister à adapter cette méthode à l'imagerie échographique et à proposer une estimation de la résolution théorique maximale atteinte par cette méthode en fonction de paramètres de l'image dont le SNR, et la largeur de bande de la PSF. Nous avons également proposé une méthode de superrésolution adaptée aux ultrasons. Par son apport sur l'amélioration théorique de la superrésolution et par l'adaptation au cas particulier de l'imagerie ultrasonore, ce travail de thèse ouvre des perspectives sur l'amélioration de la résolution des images échographiques par traitement du signal et de l'image. / Medical Imaging Ultrasound has several advantages such as its safety, ease of use, the diversity of organs that can be imaged and the low cost of this imaging mode. However, the images obtained by ultrasound suffer from relatively low resolution compared to others than can be obtain with an MRI or using X-rays. The major challenge of medical ultrasound is the ability to produce images with a resolution much finer, without modifying the nominal frequency.Work has been undertaken in this direction for some time. Several approaches have been explored. Most of the work done so far has been to work on the ultrasound acquiring device and particularly on ultrasonic probes, with main objective to increase the frequency of ultrasound used. This approach has led to the existence of high-resolution ultrasound, but with the reduction of the depth of exploration as an important limitation.Another approach is to treat numerically conventional ultrasound images to improve resolution. This method has several advantages, it allows to circumvent such difficulties caused by the reduction of depth of field due to the increase in the ultrasonic frequency.In this thesis, we present a method to improve the resolution of ultrasound images. The thesis to be to adapt this method to ultrasound imaging and to provide an estimate of the maximum theoretical resolution achieved by this method based on image parameters including SNR and the bandwidth of the PSF. We also proposed a method of superresolution suitable for ultrasound. By providing on improving theoretical superresolution and adaptation to the particular case of ultrasound, this thesis opens up on improving the resolution of ultrasound images by processing the signal and the image.

Dans cette thèse, on considère des revêtements séparables à deux ouverts de la droite projective sur un corps fini k de caractéristique p>0 et on donne un calcul explicite de la matrice du Frobenius divisé sur le premier espace de cohomologie de Rham de X_k, fibre spéciale du revêtement X étudié. On fournit également un procédé algorithmique permettant d'obtenir la décomposition de Jordan-Hölder du φ-module filtré associé à cette matrice. / We consider X some separable covering with two open set of the projective line on a finite field k of caracteristic p>0 and we give an explicit computation of the matrix of the divided Frobenius on the first de Rham cohomology space of X_k the special fiber of X. We also explain an algorithmic process to get the Jordan-Hölder decomposition of the φ-module associated to this matrix.

No description available.

Les décompositions de graphes, lorsqu’elles sont de petite largeur, sont souvent utilisées pour résoudre plus efficacement des problèmes étant difficiles dans le cas de graphes quelconques. Dans ce travail de thèse, nous nous intéressons aux limites liées à ces décompositions, et à la construction d’obstructions certifiant leur grande largeur. Dans une première partie, nous donnons un algorithme généralisant et unifiant la construction d’obstructions pour différentes largeurs de graphes, en temps XP lorsque paramétré par la largeur considérée. Nous obtenons en particulier le premier algorithme permettant de construire efficacement une obstruction à la largeur arborescente en temps O(ntw+4). La seconde partie de notre travail porte sur l’étude du problème ENSEMBLE [σ, ρ]-DOMINANT, une généralisation des problèmes de domination sur les graphes et caractérisée par deux ensembles d’entiers σ et ρ. Les diverses études de ce problème apparaissant dans la littérature concernent uniquement les cas ou le problème est FPT, lorsque paramétré par la largeur arborescente. Nous montrons que ce problème ne l’est pas toujours, et que pour certains cas d’ensembles σ et ρ, il devient W[1]-difficile lorsque paramétré par la largeur arborescente. Dans la dernière partie, nous étudions la complexité d’un nouveau problème de coloration appelé k-COLORATION ADDITIVE, combinant théorie des graphes et théorie des nombres. Nous montrons que ce nouveau problème est NP-complet pour tout k ≥ 4 fixé, tandis qu’il peut être résolu en temps polynomial sur les arbres pour k quelconque et non fixé. / Graphs decompositions of small width are usually used to solve efficiently problems which are difficult in general. In this thesis, we focus on some limits of these decompositions, and the construction of some obstructions certifying a large width. First, we give a generic algorithm unifying obstructions’ construction for several graph widths, in XP time when parameterized by the considered width. In particular, it gives the first algorithm computing efficiently an obstruction to tree-width in time O(ntw+4). Secondly, we study the parameterized complexity of [σ, ρ]-DOMINATING SET, a generalization of some domination problems characterized by two sets of integers σ and ρ. All known studies focused only on cases where this problem is FPT when parameterized by tree-width. In this work, we show that there are some cases where the problem is no longer FPT, and become W[1]-hard instead. Finally, we study the computational complexity of a new coloration problem, named k-ADDITIVE COLORING, which combines both graph theory and number theory. We show that this new problem is NP-complete for any fixed number k ≥ 4, while it can be solved in polynomial time on trees for any k.

Les besoins industriels en simulation numérique de milieux granulaires sont de plus en plus conséquents pour des systèmes de grande dimension. Le cas d'interactions entre grains de type contact unilatéral avec frottement présente des difficultés supplémentaires pour de telles simulations. Dans ce mémoire une approche par décomposition de domaine est proposée. Les méthodes de sous structuration ont été initialement développées pour des milieux continus généralement discrétisés en mécanique des solides en éléments finis. La plateforme LMGC90 (Logiciel de Mécanique Gérant le Contact en Fortran 90) constitue le cadre d'implantation d'algorithmes dédiés. Ainsi des algorithmes de décomposition de domaine, reposant sur les méthodes LArge Time Increment  et Gauss Seidel Non Linéaire, adaptés à un système de type granulaire sont définis, implantés et comparés.Pour exploiter le potentiel en calcul parallèle des méthodes ci-dessus, les procédures d'échange de message par MPI (Message Passing Interface) sont ajoutées au code. Ensuite,  l'amélioration de l'extensibilité des approches multidomaines par l'ajout d'une échelle macroscopique est testée.  Enfin, dans la perspective d'un dialogue entre modèles discret (échelle microscopique) et continu (échelle macroscopique), une version enrichie de la méthode GSNL-DD (Gauss Seidel Non Linéaire en Décomposition de domaine) est proposée. L'accélération de convergence attendue est ensuite étudiée théoriquement sur des exemples de taille réduite, avant quelques tests sur échantillons plus conséquents. / Industrial demand for numerical simulation of granular media is increasing for large systems. The case of interactions between grains such as unilateral contact with friction involves additional difficulties to these simulations. This study investigates a domain decomposition approach. The sub-structuration methods were originally developed for continuous media usually discretized by finite elements for solid mechanics. The LMGC90 platform (software to manage contact with distinct elements) provides a framework for the implementation of algorithms. Thus, domain decomposition algorithms, based on the LArge Time INcrement and Non Linear Gauss Seidel methods, ans suited to a granular problem are defined, implemented and compared. To exploit the potential for parallel computing of the aforementioned methods, the exchanging messages with MPI (Message Passing Interface) is added to the code. Then, the improvement of the scalability of multi-domain approaches through the addition of a macroscopic scale is tested. Finally, in order to implement a dialogue between the discrete (microscopic scale) and continuous (macroscopic scale) models, an enhanced version of the NLGS-DD method (Non Linear Gauss Seidel with domain decomposition) is proposed. The expected acceleration of the convergence is studied theoretically on reduced-size samples, prior to performing some tests on larger samples.

La lithographie par double impression est une solution potentielle proposée pour l'impression des circuits des nœuds technologiques avancés (22nm et au-delà) en attendant que la lithographie Extrême Ultraviolet soit prête pour la production en masse. La technique de double impression est basée sur la décomposition en deux masques d'exposition des motifs d'un niveau donné du circuit intégré. Deux motifs voisins ayant un pas inférieur au pas minimal résolu en un procédé lithographique sont affiliés simultanément à deux masques différents. Les motifs ayant des pas supérieurs au pas critique, motifs non critiques, sont mis sur un masque ou sur un autre dans le but de générer une densité de motifs équivalente entre les deux masques d'exposition. Dans cette thèse, nous avons développé une nouvelle méthode de décomposition dite « décomposition optique ». Cette dernière est basée sur l'analyse de l'interaction des ordres de diffraction dans le plan de la pupille du système optique de projection. La décomposition optique permet d'améliorer l'affiliation des motifs non critiques à l'un des deux masques dans le but d'améliorer le contraste des deux masques lors de la double impression. Afin de valider cette nouvelle méthode de décomposition, nous l'avons appliqué au niveau contacts d'un circuit de logique du nœud 22nm. / As the lithography EUV is not yet ready to be used for semi-conductor business needs, the double patterning lithography is a promising solution to print sub 22nm node features. The principle of the double patterning is the pitch splitting also named as the coloring of a given circuit layer's features. Two adjacent features must be assigned opposite masks or opposite colors corresponding to different exposures, if their pitch is less than the minimum resolvable pitch. However, features with pitches larger than the critical one are not critical and could be assigned to one of the two masks for density balance. In this thesis, we developed a new split called “optical split” based on the diffractive orders analysis in the pupil plane. The optical split optimizes the non critical contacts affiliation to one of the two exposure masks. The goal of the optical split is to enhance the lithographic performances of the generated masks in order to improve the double patterning process printing. In order to validate the optical split, we apply it on contact layer of the 22nm node logic.