Cette thèse présente une nouvelle classe de schémas de discrétisation spatiale sur maillages polyédriques, nommée Compatible Discrete Operator (CDO) et en étudie l'application aux équations elliptiques et de Stokes. La préservation au niveau discret des caractéristiques essentielles du système continu sert de fil conducteur à la construction des opérateurs. Les opérateurs de de Rham définissent les degrés de liberté en accord avec la nature physique des champs à discrétiser. Les équations sont décomposées de manière à différencier les relations topologiques (lois de conservation) des relations constitutives (lois de fermeture).Les relations topologiques sont associées à des opérateurs différentiels discrets et les relations constitutives à des opérateurs de Hodge discrets. Une particularité de l'approche CDO est l'utilisation explicite d'un second maillage, dit dual, pour bâtir l'opérateur de Hodge discret. Deux familles de schémas CDO sont ainsi considérées : les schémas vertex-based lorsque le potentiel est discrétisé aux sommets du maillage (primal), et les schémas cell-based lorsque le potentiel est discrétisé aux sommets du maillage dual (les sommets duaux étant en bijection avec les cellules primales).Les schémas CDO associés à ces deux familles sont présentés et leur convergence est analysée. Une première analyse s'appuie sur une définition algébrique de l'opérateur de Hodge discret et permet d'identifier trois propriétés clés : symétrie, stabilité et $mathbb{P}_0$-consistance. Une seconde analyse s'appuie sur une définition de l'opérateur de Hodge discret à l'aide d'opérateurs de reconstruction pour lesquels sont identifiées les propriétés à satisfaire. Par ailleurs, les schémas CDO fournissent une vision unifiée d'une large gamme de schémas de la littérature (éléments finis, volumes finis, schémas mimétiques…).Enfin, la validité et l'efficacité de l'approche CDO sont illustrées sur divers cas tests et plusieurs maillages polyédriques / This thesis presents a new class of spatial discretization schemes on polyhedral meshes, called Compatible Discrete Operator (CDO) schemes and their application to elliptic and Stokes equations. In CDO schemes, preserving the structural properties of the continuous equations is the leading principle to design the discrete operators. De Rham maps define the degrees of freedom according to the physical nature of fields to discretize. CDO schemes operate a clear separation between topological relations (balance equations) and constitutive relations (closure laws).Topological relations are related to discrete differential operators, and constitutive relations to discrete Hodge operators. A feature of CDO schemes is the explicit use of a second mesh, called dual mesh, to build the discrete Hodge operator. Two families of CDO schemes are considered: vertex-based schemes where the potential is located at (primal) mesh vertices, and cell-based schemes where the potential is located at dual mesh vertices (dual vertices being in one-to-one correspondence with primal cells).The CDO schemes related to these two families are presented and their convergence is analyzed. A first analysis hinges on an algebraic definition of the discrete Hodge operator and allows one to identify three key properties: symmetry, stability, and $mathbb{P}_0$-consistency. A second analysis hinges on a definition of the discrete Hodge operator using reconstruction operators, and the requirements on these reconstruction operators are identified. In addition, CDO schemes provide a unified vision on a broad class of schemes proposed in the literature (finite element, finite element, mimetic schemes...).Finally, the reliability and the efficiency of CDO schemes are assessed on various test cases and several polyhedral meshes

The thesis deals with subsemigroups of (Nm 0 , +), a special discussion is later devoted to the cases m = 1, m = 2 and m = 3. We prove that a subsemigroup of Nm 0 is finitely generated if and only if its generated cone is finitely generated (equivalently polyhedral) and we describe basic topological properties of such cones. We give a few examples illustrating that conditions sufficient for finite generation in N2 0 can not be easily trans- ferred to higher dimensions. We define the Hilbert basis and the related notion of Carathéodory's rank. Besides their basic properties we prove that Carathédory's rank of a subsemigroup of Nm 0 , m = 1, 2, 3, is less than or equal to m. A particular attention is devoted to the subsemigroups containing non-trivial subsemigroups of "subtractive" elements.

Neste trabalho, estudamos o problema a recoloração convexa de grafos, denotado por RC. Dizemos que uma coloração dos vértices de um grafo G é convexa se, para cada cor tribuída d, os vértices de G com a cor d induzem um subgrafo conexo. No problema RC, é dado um grafo G e uma coloração de seus vértices, e o objetivo é recolorir o menor número possível de vértices de G tal que a coloração resultante seja convexa. A motivação para o estudo deste problema surgiu em contexto de árvores filogenéticas. Sabe-se que este problema é NP-difícil mesmo quando G é um caminho. Mostramos que o problema RC parametrizado pelo número de mudanças de cor é W[2]-difícil mesmo se a coloração inicial usa apenas duas cores. Além disso, provamos alguns resultados sobre a inaproximabilidade deste problema. Apresentamos uma formulação inteira para a versão com pesos do problema RC em grafos arbitrários, e então a especializamos para o caso de árvores. Estudamos a estrutura facial do politopo definido como a envoltória convexa dos pontos inteiros que satisfazem as restrições da formulação proposta, apresentamos várias classes de desigualdades que definem facetas e descrevemos os correspondentes algoritmos de separação. Implementamos um algoritmo branch-and-cut para o problema RC em árvores e mostramos os resultados computacionais obtidos com uma grande quantidade de instâncias que representam árvores filogenéticas reais. Os experimentos mostram que essa abordagem pode ser usada para resolver instâncias da ordem de 1500 vértices em 40 minutos, um desempenho muito superior ao alcançado por outros algoritmos propostos na literatura. / In this work we study the convex recoloring problem of graphs, denoted by CR. We say that a vertex coloring of a graph G is convex if, for each assigned color d, the vertices of G with color d induce a connected subgraph. In the CR problem, given a graph G and a coloring of its vertices, we want to find a recoloring that is convex and minimizes the number of recolored vertices. The motivation for investigating this problem has its roots in the study of phylogenetic trees. It is known that this problem is NP-hard even when G is a path. We show that the problem CR parameterized by the number of color changes is W[2]-hard even if the initial coloring uses only two colors. Moreover, we prove some inapproximation results for this problem. We also show an integer programming formulation for the weighted version of this problem on arbitrary graphs, and then specialize it for trees. We study the facial structure of the polytope defined as the convex hull of the integer points satisfying the restrictions of the proposed ILP formulation, present several classes of facet-defining inequalities and the corresponding separation algorithms. We also present a branch-and-cut algorithm that we have implemented for the special case of trees, and show the computational results obtained with a large number of instances. We considered instances which are real phylogenetic trees. The experiments show that this approach can be used to solve instances up to 1500 vertices in 40 minutes, comparing favorably to other approaches that have been proposed in the literature.

L'objet de cette étude est la gravure par plasma de matériaux hybrides SiOC(H) qui sont de nouveaux composés émergents. Leurs propriétés ajustables entre composés organiques et inorganiques leurs donnent de grandes potentialités. Ce travail est dédié à deux applications particulières en microélectronique.<br />Dans un premier temps, notre étude s'est portée sur leurs applications en lithographie optique dans le cadre d'un projet européen (157 CRISPIES n° 2000 30-143) où sont développés de nouveaux polymères contenant un nanocomposé, la molécule POSS (Si8O12) (Polyhedral oligomeric silsesquioxane). Ces polymères pourraient être utilisés dans un procédé de lithographie bicouche car ils sont faiblement absorbants pour les futurs rayonnements, UV à 157 nm, ou X à 13,5 nm. L'analyse de leur surface avant gravure a été particulièrement poussée grâce à une utilisation avancée des mesures XPS. Ce travail a mis en évidence la ségrégation en surface de la molécule POSS. Afin de caractériser la phase de développement plasma du procédé bicouche, ces matériaux ont été gravés en plasma d'oxygène. Des analyses XPS et ellipsométriques montrent le rôle joué par la couche d'oxyde qui se forme à la surface de ces matériaux. Une corrélation est faite entre l'épaisseur de l'oxyde mesurée par XPS et la consommation totale du polymère mesurée par ellipsométrie. L'ensemble de ces résultats nous a amené à développer un modèle cinétique permettant de comprendre les mécanismes de gravure de ces nouveaux composés en plasmas oxydants.<br />Dans un deuxième temps, nous avons étudié l'utilisation de SiOC(H) comme isolant d'interconnexion. En effet, ces matériaux présentent une permittivité électrique plus faible que celle de l'oxyde de silicium classiquement utilisé en microélectronique, on les appelle low-k. Ils permettent d'améliorer les vitesses de transmission des informations au sein des puces. Les plasmas fluorocarbonés (C2F6) avec différents additifs (O2, Ar, H2) ont été utilisés à la fois pour obtenir une vitesse de gravure élevée mais aussi une sélectivité importante avec la couche d'arrêt SiC(H). L'addition d'hydrogène permet d'augmenter la sélectivité tout en conservant une vitesse de gravure élevée. Les caractérisations de surface par XPS quasi in situ montrent tout d'abord que la composition du matériau est modifiée sur quelques nanomètres, avec une diminution de la quantité de carbone. Ensuite, pour les plasmas de C2F6/H2 et C2F6/Ar, une couche fluorocarbonée se superpose à cette couche modifiée et son épaisseur est corrélée aux vitesses de gravure. Des mesures du flux ionique et de la quantité de fluor atomique permettent de mieux appréhender les mécanismes de gravure qui régissent ces matériaux.

La loi de Moore sur semi-conducteurs approche de sa fin. L'evolution de l'architecture de von Neumann à travers les 40 ans d'histoire du microprocesseur a conduit à des circuits d'une insoutenable complexité, à un très faible rendement de calcul par transistor, et une forte consommation énergetique. D'autre-part, le monde du calcul parallèle ne supporte pas la comparaison avec les niveaux de portabilité, d'accessibilité, de productivité et de fiabilité de l'ingénérie du logiciel séquentiel. Ce dangereux fossé se traduit par des défis passionnants pour la recherche en compilation et en langages de programmation pour le calcul à hautes performances, généraliste ou embarqué. Cette thèse motive notre piste pour relever ces défis, introduit nos principales directions de travail, et établit des perspectives de recherche.

This thesis focuses on the use of biomolecular assemblies for creating materials with novel properties. Several aspects of biomimetic materials have been investigated, from fundamental studies on membrane shaping molecules to the integration of biomolecules with inorganic materials. Triply periodic minimal surfaces (TPMS) are mathematically defined surfaces that partition space and present a large surface area in a confined space. These surfaces have analogues in many physical systems. The endoplasmic reticulum (ER) can form intricate structures and it acts as a replica for the wing scales of the butterfly C. rubi, which is characterized by electron microscopy and reflectometry. It was shown to contain a photonic crystal and an analogue to a TPMS. These photonic crystals have been replicated in silica and titania, leading to blue scales with replication on the nanometer scale. Replicas analyzed with left and right handed polarized light are shown be optically active. A macroporous hollow core particle was synthesized using a double templating method where a swollen block copolymer was utilized to create polyhedral nanofoam. Emulsified oil was used as a secondary template which gave hollow spheres with thin porous walls. The resulting material had a high porosity and low thermal conductivity. The areas of inorganic materials and functional biomolecules were combined to create a functional nanoporous endoskeleton. The membrane protein ATP synthase were incorporated in liposomes which were deposited on nanoporous silica spheres creating a tight and functional membrane. Using confocal microscopy, it was possible to follow the transport of Na+ through the membrane. Yop1p is a membrane protein responsible for shaping the ER. The protein was purified and reconstituted into liposomes of three different sizes. The vesicles in the 10-20 nm size range resulted in tubular structures. Thus, it was shown that Yop1p acts as a stabilizer of high curvature structures. / <p>At the time of the doctoral defense, the following papers were unpublished and had a status as follows: Paper 2: Manuscript. Paper 3: Submitted. Paper 4: Submitted. Paper 5: Submitted.</p>

En aquesta tesi es solucionen problemes de visibilitat i proximitat sobre superfícies triangulades considerant elements generalitzats. Com a elements generalitzats considerem:punts, segments, poligonals i polígons. Les estrategies que proposem utilitzen algoritmesde geometria computacional i hardware gràfic. Comencem tractant els problemes de visibilitat sobre models de terrenys triangulats considerant un conjunt d'elements de visió generalitzats. Es presenten dos mètodes per obtenir, de forma aproximada, mapes de multi-visibilitat. Un mapa de multi-visibilitat és la subdivisió del domini del terreny que codifica la visibilitat d'acord amb diferents criteris. El primer mètode, de difícil implementació, utilitza informació de visibilitat exacte per reconstruir de forma aproximada el mapa de multi-visibilitat. El segon, que va acompanyat de resultats d'implementació, obté informació de visibilitat aproximada percalcular i visualitzar mapes de multi-visibilitat discrets mitjançant hardware gràfic. Coma aplicacions es resolen problemes de multi-visibilitat entre regions i es responen preguntessobre la multi-visibilitat d'un punt o d'una regió. A continuació tractem els problemes de proximitat sobre superfícies polièdriques triangulades considerant seus generalitzades. Es presenten dos mètodes, amb resultats d'implementació, per calcular distàncies des de seus generalitzades sobre superfícies polièdriques on hi poden haver obstacles generalitzats. El primer mètode calcula, de forma exacte, les distàncies definides pels camins més curts des de les seus als punts del poliedre. El segon mètode calcula, de forma aproximada, distàncies considerant els camins més curts sobre superfícies polièdriques amb pesos. Com a aplicacions, es calculen diagrames de Voronoi d'ordre k, i es resolen, de forma aproximada, alguns problemes de localització de serveis. També es proporciona un estudi teòric sobre la complexitat dels diagrames de Voronoi d'ordre k d'un conjunt de seus generalitzades en un poliedre sense pesos. / In this thesis, we solve visibility and proximity problems on triangulated surfaces concerning generalized elements. As generalized elements, we consider: points, segments, polygonal chains and polygonal regions. The proposed strategies use algorithms of Computational Geometry and Graphics Hardware. We start by studying multi-visibility problems on triangulated terrain models concerning a set of generalized view elements. We present two methods to obtain approximate multi-visibility maps. A multi-visibility map is a subdivision of the terrain domain encoding visibility according to different criteria. The first method, of complex implementation, uses exactly computed visibility information to approximately reconstruct the unknown multi-visibility map. The second, from which implementation results are provided, uses approximate visibility information to compute and visualize discrete multi-visibility maps by exploiting graphics hardware capabilities. As applications, we compute multi-visibility maps, solve inter-region multi-visibility problems and approximately answer point and polygonal region multi-visibility queries. Next, we tackle proximity problems on triangulated polyhedral surfaces, where generalized obstacles are allowed, considering generalized sources. We present two methods, with implementation results, to compute distances on polyhedral surfaces from a generalized source. The first method computes exact shortest path distances from generalized sources. The second provides approximate weighted shortest path distances from generalized sites on weighted polyhedral surfaces. Both methods are posteriorly extended to handle the multiple-site problem where the corresponding distance field is obtained. As applications, we compute discrete order-k Voronoi diagrams and approximately solve some facility location problems. We also provide a theoretical study on the order-k Voronoi diagram complexity of a set of generalized sources for the non-weighted case.

The high level of realism and interaction in many computer graphic applications requires techniques for processing complex geometric models. First, we present a method that provides an accurate low-resolution approximation from a multi-chart textured model that guarantees geometric fidelity and correct preservation of the appearance attributes. Then, we introduce a mesh structure called Compact Model that approximates dense triangular meshes while preserving sharp features, allowing adaptive reconstructions and supporting textured models. Next, we design a new space deformation technique called *Cages based on a multi-level system of cages that preserves the smoothness of the mesh between neighbouring cages and is extremely versatile, allowing the use of heterogeneous sets of coordinates and different levels of deformation. Finally, we propose a hybrid method that allows to apply any deformation technique on large models obtaining high quality results with a reduced memory footprint and a high performance. / L’elevat nivell de realisme i d’interacció requerit en múltiples aplicacions gràfiques fa que siguin necessàries tècniques pel processament de models geomètrics complexes. En primer lloc, presentem un mètode de simplificació que proporciona una aproximació precisa de baixa resolució d'un model texturat que garanteix fidelitat geomètrica i una correcta preservació de l’aparença. A continuació, introduïm el Compact Model, una nova estructura de dades que permet aproximar malles triangulars denses preservant els trets més distintius del model, permetent reconstruccions adaptatives i suportant models texturats. Seguidament, hem dissenyat *Cages, un esquema de deformació basat en un sistema de caixes multi-nivell que conserva la suavitat de la malla entre caixes veïnes i és extremadament versàtil, permetent l'ús de conjunts heterogenis de coordenades i diferents nivells de deformació. Finalment, proposem un mètode híbrid que permet aplicar qualsevol tècnica de deformació sobre models complexes obtenint resultats d’alta qualitat amb una memòria reduïda i un alt rendiment.

The quadratic traveling salesman problem (QTSP) is an extension of the (classical) Traveling Salesman Problem (TSP) where the costs depend on each two nodes that are traversed in succession, i. e., on the edges in the symmetric (STSP) and on the arcs in the asymmetric case (ATSP). The QTSP is motivated by an application in bioinformatics. It can be used in the solution of certain Permuted Markov models that are set up for the recognition of transcription factor binding sites and of splice sites in gene regulation. Important special cases are the Angular-Metric TSP used in robotics and the TSP with Reload Costs used in the planning of telecommunication and transport networks. The SQTSP and the AQTSP can be formulated as integer optimization problems over the polytope associated with the STSP resp. ATSP together with a quadratic cost function. We study the polytopes arising from a linearization of the respective quadratic integer programming formulations. Based on the proof of the dimension of the polytopes using the so called direct method we can prove the facetness of several valid inequalities. These facets and valid inequalities can be divided into three large groups. Some are related to the Boolean quadric polytope. Furthermore we introduce the conflicting edges/arc inequalities that forbid certain configurations of edges and 2-edges resp. of arcs and 2-arcs. Finally, we strengthen valid inequalities of STSP and ATSP in order to get stronger inequalities in the quadratic case. We present two general lifting approaches. One is applicable to all inequalities with nonnegative coefficients and the second allows to strengthen clique tree inequalities. Applying these approaches to the subtour elimination constraints leads to facets in most cases, but in general facetness is not preserved. In addition, the complexity of the separation problems for some of the facet classes is studied. Finally, we present some computational results using a branch-and-cut framework, which is improved by some of the newly derived cutting planes. The tested instances from biology could be solved surprisingly well. Instances with up to 100 nodes could be solved in less than 700 seconds improving the results in the literature by several orders of magnitude. For most of the randomly generated instances using some additional separators allowed to reduce the root gaps and the numbers of nodes in the branch-and-cut tree significantly, often even the running times.

This thesis presents cutter swept volume generation, in-process workpiece modeling and Cutter Workpiece Engagement (CWE) algorithms for finding the instantaneous intersections between cutter and workpiece in milling. One of the steps in simulating machining operations is the accurate extraction of the intersection geometry between cutter and workpiece. This geometry is a key input to force calculations and feed rate scheduling in milling. Given that industrial machined components can have highly complex geometries, extracting intersections accurately and efficiently is challenging. Three main steps are needed to obtain the intersection geometry between cutter and workpiece. These are the Swept volume generation, in-process workpiece modeling and CWE extraction respectively. In this thesis an analytical methodology for determining the shapes of the cutter swept envelopes is developed. In this methodology, cutter surfaces performing 5-axis tool motions are decomposed into a set of characteristic circles. For obtaining these circles a concept of two-parameter-family of spheres is introduced. Considering relationships among the circles the swept envelopes are defined analytically. The implementation of methodology is simple, especially when the cutter geometries are represented by pipe surfaces. During the machining simulation the workpiece update is required to keep track of the material removal process. Several choices for workpiece updates exist. These are the solid, facetted and vector model based methodologies. For updating the workpiece surfaces represented by the solid or faceted models third party software can be used. In this thesis multi-axis milling update methodologies are developed for workpieces defined by discrete vectors with different orientations. For simplifying the intersection calculations between discrete vectors and the tool envelope the properties of canal surfaces are utilized. A typical NC cutter has different surfaces with varying geometries and during the material removal process restricted regions of these surfaces are eligible to contact the in-process workpiece. In this thesis these regions are analyzed with respect to different tool motions. Later using the results from these analyses the solid, polyhedral and vector based CWE methodologies are developed for a range of different types of cutters and multi-axis tool motions. The workpiece surfaces cover a wide range of surface geometries including sculptured surfaces.