[pt] Um dos maiores gargalos do pipeline gráfico hoje é a largura de banda disponível entre a GPU e CPU. Para minimizar esse gargalo funcionalidades programáveis foram inseridas nas placas de vídeo. Com o Geometry Shader é possível criar vértices em GPU, porém, este estágio da pipeline apresenta performance baixa. Com o lançamento das novas APIs gráficas (DirectX11 e OpenGL4) em 2009, foi adicionado o Tessellator, que permite a criação de vértices em massa na GPU. Esta dissertação estuda este novo estágio da pipeline, bem como apresenta algoritmos clássicos (PN-Triangles e Phong Tessellation) que originalmente foram feitos para CPU e propõe novos algoritmos (Renderização de Tubos e Terrenos em GPU) para tirar proveito deste novo paradigma. / [en] One of the main bottlenecks in the graphics pipeline nowadays is the memory bandwidth available between the CPU and the GPU. To avoid this bottleneck, programmable features were inserted into the video cards. With the Geometry Shader launch it is possible to create vertices in the GPU, however, this pipeline stage has a low performance. With the new graphic APIs (DirectX11 and OpenGL4) a Tessellator stage that allows massive vertex generation inside the GPU was created. This dissertation studies this new pipeline stage, as well as presents classic algorithms (PN-Triangles and Phong Tessellation) that were originally designed for CPU and proposes new algorithms (Tubes and Terrain rendering in the GPU) that takes advantage of this new paradigm.

The intent of this thesis is to explore whether any patterns emerge among families or through graph operations regarding the appearance of Weierstrass vertices on graphs. Currently, patterns have been identified and proven on cycles, complete graphs, complete bipartite graphs, and the house and house-x graphs. A Python program developed as part of this thesis to perform the algorithms used in this analysis confirms these findings. This program also revealed a pattern: if v is a Weierstrass vertex, then the vertex v* added to the graph as a pendant vertex to v is also a Weierstrass vertex. The converse is also true: if v is not a Weierstrass vertex, v* will not be either.

No description available.

For a graph G, a set S is a dominating set if every vertex in V-S has a neighbor in S. A vertex contained in some minimum dominating set is called good; otherwise it is bad. A graph G has g(G) good vertices and b(G) bad vertices. The relationship between the order of G and g(G) assigns the graph to one of four classes. Our results include a method of classifying caterpillars. Further, we develop realizability conditions for a graph G given a triple of nonnegative integers representing the domination number of γ(G), g(G), and b(G), respectively, and provide constructions of graphs meeting those conditions. We define the goodness index of a vertex v in a graph G as the ratio of distinct γ(G)-sets containing v to the total number of γ(G)-sets, and provide formulas that yield the goodness index of any vertex in a given path.

This thesis concerns the application of mixed-integer programming techniques to solve special classes of network flow problems and stochastic integer programs. We draw tools from complexity and polyhedral theory to analyze these problems and propose improved solution methods. In the first part, we consider semi-continuous network flow problems, that is, a class of network flow problems where some of the variables are required to take values above a prespecified minimum threshold whenever they are not zero. These problems find applications in management and supply chain models where orders in small quantities are undesirable. We introduce the semi-continuous inflow set with variable upper bounds as a relaxation of general semi-continuous network flow problems. Two particular cases of this set are considered, for which we present complete descriptions of the convex hull in terms of linear inequalities and extended formulations. We also consider a class of semi-continuous transportation problems where inflow systems arise as substructures, for which we investigate complexity questions. Finally, we study the computational efficacy of the developed polyhedral results in solving randomly generated instances of semi-continuous transportation problems. In the second part, we introduce and study the forbidden-vertices problem. Given a polytope P and a subset X of its vertices, we study the complexity of optimizing a linear function on the subset of vertices of P that are not contained in X. This problem is closely related to finding the k-best basic solutions to a linear problem and finds applications in stochastic integer programming. We observe that the complexity of the problem depends on how P and X are specified. For instance, P can be explicitly given by its linear description, or implicitly by an oracle. Similarly, X can be explicitly given as a list of vectors, or implicitly as a face of P. While removing vertices turns to be hard in general, it is tractable for tractable 0-1 polytopes, and compact extended formulations can be obtained. Some extensions to integral polytopes are also presented. The third part is devoted to the integer L-shaped method for two-stage stochastic integer programs. A widely used model assumes that decisions are made in a two-step fashion, where first-stage decisions are followed by second-stage recourse actions after the uncertain parameters are observed, and we seek to minimize the expected overall cost. In the case of finitely many possible outcomes or scenarios, the integer L-shaped method proposes a decomposition scheme akin to Benders' decomposition for linear problems, but where a series of mixed-integer subproblems have to be solved at each iteration. To improve the performance of the method, we devise a simple modification that alternates between linear and mixed-integer subproblems, yielding significant time savings in instances from the literature. We also present a general framework to generate optimality cuts via a cut-generating problem. Using an extended formulation of the forbidden-vertices problem, we recast our cut-generating problem as a linear problem and embed it within the integer L-shaped method. Our numerical experiments suggest that this approach can prove beneficial when the first-stage set is relatively complicated.

Neste trabalho, estendemos o método desenvolvido em (SALARINOGHABI, 2016),(SALARINOGHABI; TARI, 2017) para curvas no plano Minkowski. Tal método propõe um modo de estudar deformações de curvas planas levando em consideração a geometria das mesmas juntamente com suas singularidades. Abordamos detalhadamente todos os fenômenos locais que ocorrem genericamente em famílias de curvas a 2-parâmetros. Em cada caso, obtemos a geometria da curva deformada, ou seja, informações a respeito de inflexões, vértices e pontos lightlike. Obtemos também o comportamento da evoluta/cáustica de uma curva em pontos especiais e as bifurcações que podem aparecer ao deformá-la. Além disso, a fim de obter as deformações genéricas em uma inflexão lightlike de ordem 2, também classificamos submersões de R3 em R por meio de difeomorfismos na fonte que preservam a swallowtail e, utilizando tal classificação, estudamos a geometria plana da swallowtail, a qual provém de seu contato com planos, o qual por sua vez é medido pelas singularidades da função altura sobre a swallowtail. / In this work, we extend the method developed in (SALARINOGHABI, 2016),(SALARINOGHABI; TARI, 2017) to curves in the Minkowski plane. The method proposes a way to study deformations of plane curves taking into consideration their geometry as well as their singularities. We deal in detail with all local phenomena that occur generically in 2-parameters families of curves. In each case, we obtain the geometry of the deformed curve, that is, information about inflections, vertices and lightlike points. We also obtain the behavior of the evolute/caustic of a curve at special points and the bifurcations that can occur when the curve is deformed. Moreover, in order to obtain the generic deformations at a lightlike inflection point of order 2, we also classify submersions from R3 to R by diffeomorphisms in the source that preserve the swallowtail and, using such classification, we study the flat geometry of the swallowtail, which comes from its contact with planes, which in turn is measured by the singularities of the height function on the swallowtail.

O objetivo deste trabalho é analisar o comportamento dos expoentes críticos do modelo de Oito Vértices através de cotas superior e inferior para sua função de partição na vizinhança de modelos solúveis. O método é ilustrado pelo modelo de Heisenberg quântico unidimensional também denominado modelo XYZh. Aplica-se igualmente ao modelo de Ising bidimensional (com interação quártica e segundos vizinhos). Assim, propomos um modo alternativo de abordar universalidade nos modelos de Heisenberg unidimensional quântico e Ising bidimensional clássico por desigualdades satisfeitas por suas funções de partição. Dentre os métodos que utilizamos para a obtenção das cotas destacam-se: a interação Gaussiana nas variáveis reais e nas variáveis de Grassmann; o mapeamento de um modelo unidimensional em um bidimensional através do auxílio da fórmula Trotter; a representação da função de partição pelo Pfaffiano de uma matriz; e, para a obtenção da cota superior, a técnica de positividade por reflexão, estendida ao acaso de variáveis que anti-comutam. / The aim of this work is to analyze the behavior of critical exponents in the eight-vertex model starting from the upper and lower bound obtained for its partition function. We studied the quantum onedimensional Heisenberg model also denominated XYZh model. We propose na alternative way of approaching universality in Heisenberg and Ising models using inequalities satisfied for their partition functions.Among the methods that we used in the solutions of the models atand out the integration on the Grassmann variables, the mapping of a onedimensional model in a two-dimensional one through the aid of the Trotter formula and, finally, the representation of the partition function as Pfaffian of a matrix. To obtain na upper bound, the positivity reflection technique was used, extended to the case of variables that, anticomute, and the method of thechess board estimate.

Our current understanding of matter and its interactions is summarised in the Standard Model (SM) of particle physics. Many experiments have tested the predictions of the SM with great success, but others have brought our ignorance into focus by showing us there are new phenomena that we can not describe within the framework of the SM. These include the experimental observations of neutrino masses and dark matter, which confirms there must be new physics. What this new physics may look like at colliders motivates the original work in this thesis, which comprises three studies: the prospects of future electron-positron colliders in testing a model with an extended Higgs sector with a scalar triplet, doublet and singlet; the discovery potential at the Large Hadron Collider (LHC) of a non-minimal Supersymmetric model via conventional sparticle searches and via searches for displaced vertices; and the experimental search for long-lived massive particles via a displaced vertex signature using data of proton-proton collisions collected at a collider center of mass energy of 8 TeV in 2012 by the ATLAS detector operating at the LHC.

We propose in this thesis a way to study deformations of plane curves that take into consideration the geometry of the curves as well as their singularities. We deal in details with local phenomena that occur generically in two-parameter families of curves. We obtain information on the inflections and vertices appearing on the deformed curves. We also obtain the configurations of the evolutes of the curves and of their deformations, and apply our results to orthogonal projections of space curves. Finally, we consider the profile (outline, apparent contour) of a smooth surface in the Euclidian 3-space. This is the image of the singular set of an orthogonal projection of the surface. The profile is a plane curve and may have singularities. We study the changes in the geometry of the profile as the direction of projection changes locally in the unit sphere. / Propomos nesta tese um método para estudar deformações de curvas planas que leva em consideração a geometria delas, bem como as suas singularidades. Consideramos em detalhes os fenômenos locais que ocorrem genericamente em famílias de curvas com dois parâmetros. Obtemos informações sobre as inflexões e vértices que aparecem nas curvas deformadas. Obtemos também as configurações das evolutas das curvas e das suas deformações e aplicamos os nossos resultados nas projeções ortogonais de curvas espaciais. Finalmente, consideramos o perfil de uma superfície regular no espaço Euclidiano R3. O perfil é a imagem do conjunto singular de uma projeção ortogonal da superfície, esta é uma curva plana e pode ter singularidades. Estudamos as alterações na geometria do perfil quando a direção de projeção muda localmente na esfera unitária.

O objetivo deste trabalho é analisar o comportamento dos expoentes críticos do modelo de Oito Vértices através de cotas superior e inferior para sua função de partição na vizinhança de modelos solúveis. O método é ilustrado pelo modelo de Heisenberg quântico unidimensional também denominado modelo XYZh. Aplica-se igualmente ao modelo de Ising bidimensional (com interação quártica e segundos vizinhos). Assim, propomos um modo alternativo de abordar universalidade nos modelos de Heisenberg unidimensional quântico e Ising bidimensional clássico por desigualdades satisfeitas por suas funções de partição. Dentre os métodos que utilizamos para a obtenção das cotas destacam-se: a interação Gaussiana nas variáveis reais e nas variáveis de Grassmann; o mapeamento de um modelo unidimensional em um bidimensional através do auxílio da fórmula Trotter; a representação da função de partição pelo Pfaffiano de uma matriz; e, para a obtenção da cota superior, a técnica de positividade por reflexão, estendida ao acaso de variáveis que anti-comutam. / The aim of this work is to analyze the behavior of critical exponents in the eight-vertex model starting from the upper and lower bound obtained for its partition function. We studied the quantum onedimensional Heisenberg model also denominated XYZh model. We propose na alternative way of approaching universality in Heisenberg and Ising models using inequalities satisfied for their partition functions.Among the methods that we used in the solutions of the models atand out the integration on the Grassmann variables, the mapping of a onedimensional model in a two-dimensional one through the aid of the Trotter formula and, finally, the representation of the partition function as Pfaffian of a matrix. To obtain na upper bound, the positivity reflection technique was used, extended to the case of variables that, anticomute, and the method of thechess board estimate.