11 |
[en] ANALYSIS OF MORSE MATCHINGS: PARAMETERIZED COMPLEXITY AND STABLE MATCHING / [pt] ANÁLISE DE CASAMENTOS DE MORSE: COMPLEXIDADE PARAMETRIZADA E CASAMENTO ESTÁVEL16 December 2021 (has links)
[pt] A teoria de Morse relaciona a topologia de um espaço aos elementos críticos de uma função escalar definida nele. Isso vale tanto para a teoria clássica quanto para a versão discreta proposta por Forman em 1995. Essas teorias de Morse permitem caracterizar a topologia do espaço a partir de funções definidas nele, mas também permite estudar funções a partir de construções tipológicas derivadas dela, como por exemplo o complexo de Morse-Smale. Apesar da teoria de Morse discreta se aplicar para complexos celulares gerais de forma inteiramente combinatória, o que torna a teoria particularmente bem adaptada para o computador, as funções usadas na teoria não são amostragens de funções contínuas, mas casamentos especiais no grafo que codifica as adjacências no complexo celular, chamadas de casamentos de Morse. Quando usar essa teoria para estudar um espaço topológico, procura- se casamentos de Morse ótimos, i.e. com o menor número possível de elementos críticos, para obter uma informação topológica do complexo sem redundância. Na primeira parte desta tese, investiga-se a complexidade parametrizada de encontrar esses casamentos de Morse ótimos.
Por um lado, prova-se que o problema ERASABILITY, um problema fortemente relacionado à
encontrar casamentos de Morse ótimos, é W [P ]-completo. Por outro lado, um algoritmo é proposto para calcular casamentos de Morse ótimos em triangulações de 3-variedades, que é FPT no parâmetro do tree- width de seu grafo dual. Quando usar a teoria de Morse discreta para estudar uma função escalar definida no espaço, procura-se casamentos de Morse que capturam a informação geométrica dessa função. Na segunda parte é proposto uma construção de casamentos de Morse baseada em casamentos estáveis. As garantias teóricas sobre a relação desses casamentos com a geometria são elaboradas a partir de provas surpreendentemente simples que aproveitam da caracterização local do casamento estável. A construção e as suas garantias funcionam em qualquer dimensão. Finalmente, resultados mais fortes são obtidos quando a função for suave discreta, uma noção definida nesta tese. / [en] Morse theory relates the topology of a space to the critical elements of a
scalar function defined on it. This applies in both the classical theory and
a discrete version of it defined by Forman in 1995. Those Morse theories
permit to characterize a topological space from functions defined on it, but
also to study functions based on topological constructions it implies, such as
the Morse-Smale complex. While discrete Morse theory applies on general
cell complexes in an entirely combinatorial manner, which makes it suitable
for computation, the functions it considers are not sampling of continuous
functions, but special matchings in the graph encoding the cell complex
adjacencies, called Morse matchings.
When using this theory to study a topological space, one looks for optimal
Morse matchings, i.e. one with the smallest number of critical elements, to
get highly succinct topological information about the complex. The first
part of this thesis investigates the parameterized complexity of finding such
optimal Morse matching. On the one hand the Erasability problem, a
closely related problem to finding optimal Morse matchings, is proven to be
W[P]-complete. On the other hand, an algorithm is proposed for computing
optimal Morse matchings on triangulations of 3-manifolds which is fixed parameter
tractable in the tree-width of its dual graph.
When using discrete Morse theory to study a scalar function defined on
the space, one looks for a Morse matching that captures the geometric
information of that function. The second part of this thesis introduces a
construction of Morse matchings based on stable matchings. The theoretical
guarantees about the relation of such matchings to the geometry are
established through surprisingly simple proofs that benefits from the local
characterization of the stable matching. The construction and its guarantees
work in any dimension. Finally stronger results are obtained if the function
is discrete smooth on the complex, a notion defined in this thesis.
|
12 |
[pt] DINHEIRO, DERIVATIVOS, REDES SOCIOTÉCNICAS: UM ENSAIO SOBRE CARTOGRAFIAS DAS FINANÇAS CONTEMPORÂNEAS / [en] MONEY, DERIVATIVES, SOCIOTECHNICAL NETWORKS: AN ESSAY ON THE CARTOGRAPHIES OF CONTEMPORARY FINANCE06 July 2020 (has links)
[pt] Percorrendo as linhas de interseção que conectam e separam as disciplinas economia política internacional, sociologia política internacional e geografia humana, a presente pesquisa se propõe a investigar derivativos financeiros como tanto forma de dinheiro quanto instituição e práticas monetárias. Para tanto, o estudo busca inspiração, de modo geral, no que foi cunhado virada prática nas ciências sociais, e de modo particular, nas abordagens teórico-metodológicas associadas à Teoria do Ator-Rede (TAR). Por meio do desempacotamento da noção de financeirização bem como de um descentramento das finanças, a pesquisa intenta capturar ações, práticas, objetos e estratégias que reúnem, sustentam, autorizam e dão forma à ordenamentos monetários e financeiros sistemáticos – muito embora restando contingentes e instáveis. À luz do mercado de hipotecas subprime dos Estados Unidos da América, o estudo pretende, de um lado, desvelar mecanismos de assemblagem de redes sociotécnicas monetárias e financeiras e, de outro lado, lançar luz sobre dinâmicas topológicas que deslocam e amplificam linhas de exclusão/expropriação raciais e de gênero. Este trabalho de mapeamento, no nosso entendimento, abre espaço para engajamento político e crítico com uma temática pretensamente técnica, ao passo que sinaliza limites e possibilidades que derivam de modos e formas de dissenso. / [en] Running across the intersecting lines that bind and separate the domains of international political economy, international political sociology and human geography, this research sets out to investigate derivatives as both money-form and monetary institutions and practices. To this end, the study draws inspiration, in general, from what has been termed in the social sciences as the practical turn and, in particular, from theoretical and methodological approaches associated with the Actor-Network Theory. By unpacking the notion of financialization and decentering finance, this investigation seeks to grasp actions, practices, objects, strategies that bring together, sustain, authorize and give form to systematic, albeit contingent and unstable, financial and monetary orderings. In the light of the subprime mortgage market of the United States of America, the study will, on the one hand, shed light to mechanisms of assembly of sociotechnical monetary and financial networks, and, on the other hand, unveil the topological workings that dislocate and amplify racial and gendered lines of exclusion. This work of mapping, so I argue, shall open up spaces for critical engagement and shall indicate the limits and possibilities deriving from multiple modes of dissent.
|
13 |
[en] ASPECTS OF TOPOLOGY AND FIXED POINT THEORY / [pt] ASPECTOS DA TOPOLOGIA E DA TEORIA DOS PONTOS FIXOSLEONARDO HENRIQUE CALDEIRA PIRES FERRARI 17 August 2017 (has links)
[pt] Esse trabalho tem como objetivo reunir os teoremas topológicos de ponto fixo clássicos e seus corolários, além de teoremas de ponto fixo provenientes da teoria do grau e algumas importantes aplicações desses teoremas a variadas áreas - desde as clássicas aplicações à teoria de EDOs e EDPs à uma aplicação à teoria dos jogos. Um exemplo é o Teorema do Ponto Fixo de Schauder-Tychonoff, para aplicações compactas em convexos de espaços localmente convexos, do qual segue como corolário que todo compacto convexo de
um espaço vetorial normado (não necessariamente de dimensão finita) possui a propriedade do ponto fixo. No que se refere à teoria dos jogos em particular, foi deduzido o Teorema de Nash, que determina condições sobre as quais certos jogos possuem equilíbrios nos seus espaços das estratégias. Toda a topologia geral necessária nas demonstrações foi desenvolvida extensiva e detalhadamente a partir de topologia elementar, seguindo algumas das referências bibliográficas. O Teorema de Extensão de Dugundji - uma extensão do Teorema de Extensão de Tietze a fechados de espaços métricos sobre espaços localmente convexos -, por exemplo, é demonstrado com detalhes e usado diversas vezes
ao longo da dissertação. / [en] The goal of the present work is to gather the classical fixed-point theorems and their corollaries, as well as other fixed-point theorems arising from degree theory, and some important applications to diverse fields -
from the classical applications to ODEs and PDEs to an application to the game theory. An example is the Schauder-Tychonoff Fixed-Point Theorem, 1 concerning compact mappings in convex subsets of locally convex spaces, from which it follows as a corollary that every compact convex subset of a normed
vector space is a fixed-point space. In regard to game theory in particular, we obtained Nash s theorem, 2 which ascertains conditions over which certain games have equilibria in their strategy spaces. All general topology necessary in the proofs was developed extensively and in details from a basic topology
starting point, following some of the bibliographic references. Dugundji s Extension Theorem 3 - an extension of Tietze s Extension Theorem 4 for closed subsets of metric spaces into locally convex spaces-, for instance, is obtained with detais and used throughout the dissertation.
|
Page generated in 0.029 seconds