Search

A complexidade dos dados armazenados em grandes bases de dados aumenta cada vez mais, criando a necessidade de novas operações de consulta. Uma classe de operações que tem apresentado interesse crescente são as chamadas Consultas por Similaridade, sendo as mais conhecidas as consultas por Abrangência (\'R IND. q\') e por k-Vizinhos mais Proximos (kNN), sendo que esta ultima obtem quais são os k elementos armazenados mais similares a um dado elemento de referência. Outra consulta que é interessante tanto para consultas diretas quanto como parte de operações de análises mais complexas e a operação de consulta aos k-Vizinhos mais Próximos Reversos (RkNN). Seu objetivo e obter todos os elementos armazenados que têm um dado elemento de referência como um dos seus k elementos mais similares. Devido a complexidade de execução da operação de RkNN, a grande maioria das soluções existentes restringem-se a dados representados em espaços multidimensionais euclidianos (nos quais estão denidas tambem operações cardinais e topológicas, além de se considerar a similaridade como sendo a distância Euclidiana entre dois elementos), ou então obtém apenas respostas aproximadas, sujeitas a existência de falsos negativos. Várias aplicações de análise de dados científicos, médicos, de engenharia, financeiros, etc. requerem soluções eficientes para o problema da operação de RkNN sobre dados representados em espaços métricos, onde os elementos não podem ser considerados estar em um espaço nem Euclidiano nem multidimensional. Num espaço métrico, além dos próprios elementos armazenados existe apenas uma função de comparação métrica entre pares de objetos. Neste trabalho, são propostas novas podas de espaço de busca e o algoritmo RkNN-MG que utiliza essas novas podas para solucionar o problema de consultas RkNN exatas em espaços métricos sem limitações. Toda a proposta supõe que o conjunto de dados esta em um espaço métrico imerso isometricamente em espaço euclidiano e utiliza propriedades da geometria métrica válida neste espaço para realizar podas eficientes por lei dos cossenos combinada com as podas tradicionais por desigualdade triangular. Os experimentos demonstram comparativamente que as novas podas são mais eficientes que as tradicionais podas por desigualdade triangular, tendo desempenhos equivalente quando comparadas em conjuntos de alta dimensionalidade ou com dimensão fractal alta. Assim, os resultados confirmam as novas podas propostas como soluções alternativas eficientes para o problema de consultas RkNN Data stored in large databases present an ever increasing complexity, pressing for the development of new classes of query operators. One such class, which is enticing an increasing interest, is the so-called Similarity Queries, where the most common are the similarity range queries (\'R IND. q\') and the k-nearest neighbor queries (kNN). A k-nearest neighbor query aims at retrieving the k stored elements nearer (or more similar) to a given reference element. Another important similarity query is the reverse k-nearest neighbor (RkNN), useful both for queries posed directly by the analyst and for queries that are part of more complex analysis processes. The objective of a reverse k-nearest neighbor queries is obtaining the stored elements that has the query reference element as one of their k-nearest neighbors. As the RkNN operation is a rather expensive operation, from the computational standpoint, most existing solutions only solve the query when applied over Euclidean multidimensional spaces (as these spaces also define cardinal and topological operations besides the Euclidean distance between pairs of elements) or retrieve only approximate answers, where false negatives can occur. Several applications, like the analysis of scientific, medical, engineering or financial data, require efficient and exact answers for the RkNN queries over data which is frequently represented in metric spaces, that is where no other property besides the similarity measure exists. Therefore, for applications handling metrical data, the assumption of Euclidean metric or even multidimensional data cannot be used. In this work, we propose new pruning rules based on the law of cosines, and the RkNN-MG algorithm, which uses them to solve RkNN queries in a way that is exact, faster than the existing approaches, that is not limited for any value of k, and that can be applied both over static and over dynamic datasets. The new pruning rules assume that the data set is in a metric space that can be embedded into an Euclidean space and use metric geometry properties valid in this space to perform effective pruning based on the law of cosines combined with the traditional pruning based on the triangle inequality property. The experiments show that the new pruning rules are alkways more efficient than the traditional pruning rules based solely on the triangle inequality. The experiments show that for high high dimensionality datasets, or for metric datasets with high fractal dimensionality, the performance improvement is smaller than for for lower dimensioinality datasets, but it\'s never worse. Thus, the results confirm that the our pruning rules are efficient alternative to solve RkNN queries in general

O problema da descontinuidade semântica tem sido um dos principais focos de pesquisa no desenvolvimento de sistemas de recuperação de imagens baseada em conteúdo (CBIR). Neste contexto, as pesquisas mais promissoras focam principalmente na inferência de pesos de características contínuos e na seleção de características. Entretanto, os processos tradicionais de inferência de pesos contínuos são computacionalmente caros e a seleção de características equivale a uma ponderação binária. Visando tratar adequadamente o problema de lacuna semântica, este trabalho propõe dois métodos de transformação de espaço de características métricos baseados na inferência de funções de transformação por meio de algoritmo genético. O método WF infere funções de ponderação para ajustar a função de dissimilaridade e o método TF infere funções para transformação das características. Comparados às abordagens de inferência de pesos contínuos da literatura, ambos os métodos propostos proporcionam uma redução drástica do espaço de busca ao limitar a busca à escolha de um conjunto ordenado de funções de transformação. Análises visuais do espaço transformado e de gráficos de precisão vs. revocação confirmam que TF e WF superam a abordagem tradicional de ponderação de características. Adicionalmente, foi verificado que TF supera significativamente WF em termos de precisão dos resultados de consultas por similaridade por permitir transformação não lineares no espaço de característica, conforme constatado por análise visual. The semantic gap problem has been a major focus of research in the development of content-based image retrieval (CBIR) systems. In this context, the most promising research focus primarily on the inference of continuous feature weights and feature selection. However, the traditional processes of continuous feature weighting are computationally expensive and feature selection is equivalent to a binary weighting. Aiming at alleviating the semantic gap problem, this master dissertation proposes two methods for the transformation of metric feature spaces based on the inference of transformation functions using Genetic Algorithms. The WF method infers weighting functions and the TF method infers transformation functions for the features. Compared to the existing methods, both proposed methods provide a drastic searching space reduction by limiting the search to the choice of an ordered set of transformation functions. Visual analysis of the transformed space and precision. vs. recall graphics confirm that both TF and WF outperform the traditional feature eighting methods. Additionally, we found that TF method significantly outperforms WF regarding the query similarity accuracy by performing non linear feature space transformation, as found in the visual analysis.

CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior Nesta dissertação, vamos fazer um estudo de homeomorfismos topologicamente Gromov- Hausdorff (GH) estáveis. Nesta linha, estudamos a relação entre a estabilidade GH e a estabilidade topológica usual, como no artigo de Arbieto e Morales [2]. Na sequência, apresentamos alguns resultados inéditos sobre a regularidade da entropia e a densidade de pontos peri´odicos para dinâmicas topologicamente GH-estáveis. In this text, we study homeomorphisms Gromov-Hausdorff (GH) topologically stable. In this sense, we study the relation between GH stability and the usual topological stability, as in the paper of Arbieto and Morales [2]. Also, we present some new results about regularity of the entropy and density of periodic points for dynamics GH stable. Dissertação (Mestrado)

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) The expansion of different areas of knowledge through many types of information brought the necessity to support complex data (images, sounds, videos, strings, DNA chains, etc.), that do not have a Total Order Relationship and need other management mechanisms, like the contentbased retrieval. In general, they are represented in metric space domains, where we have only the elements and the distances between them. Through the characteristics extracted from them, we perform the similarity search. Considering the necessity to associate temporal information on these data in many applications, this work aims to analyze the temporal evolve of metric data. One alternative for this is embedding them into a multidimensional space to allow trajectories estimates. We studied different methods of embedding and analyzed how this affected the data’s distribution and, consequently, the estimates. Two new methods were purposed to estimate an element’s status on a different time from that available in database, in order to reduce the number of non-relevant elements on search results. These methods are based on radius search reduction (range) and evaluation of retrieved element’s proximity by using an approximation of reverse k- NN. We performed experiments which showed that purposed methods could improve the estimate’s result, that used to be performed only using k-NN searches. A expansão de diferentes áreas do conhecimento com os diversos tipos de informação tornou necessário o suporte a dados complexos (imagens, sons, vídeos, cadeias de DNA, entre outros), que por não possuírem uma Relação de Ordem Total (ROT), necessitam de outros mecanismos de gerenciamento, como a recuperação por conteúdo. Em geral, esses dados são representados em domínios de espaços métricos, onde apenas se tem os elementos e as distâncias entre eles. Através das características extraídas dos mesmos, realiza-se consultas por similaridade. Considerando a necessidade de associar a informação temporal a esses dados em muitas aplicações, este trabalho visa analisar a evolução temporal dos dados métricos. Para isso, uma alternativa é mapeá-los para um espaço multidimensional, a fim possibilitar a estimativa de trajetórias. Neste trabalho, foram estudados diferentes métodos de mapeamento, sendo também analisado como o mapeamento afetou a distribuição dos mesmos e, por conseguinte, a realização das estimativas. Foram propostos dois novos métodos para estimar o estado de um elemento em um tempo diferente daqueles disponíveis na base de dados, com o objetivo de reduzir no conjunto resposta a quantidade de elementos não relevantes. Os métodos propostos são baseados na redução do raio de consulta na região estimada pela delimitação do raio de consulta (range) e a avaliação da proximidade dos elementos retornados utilizando verificação (aproximação) do k-NN reverso. Foram realizados experimentos que mostraram que os métodos propostos melhoraram o resultado final das estimativas, que anteriormente eram realizadas apenas com consultas aos vizinhos mais próximos.

Submitted by HELBA ALEXANDRA HERMINI null (helba.alexandra@uol.com.br) on 2017-04-06T23:13:08Z No. of bitstreams: 2 Dissertacao_Helba.pdf: 794862 bytes, checksum: 72e4f5b0a4b660c7dce8983313d39876 (MD5) Dissertacao_Helba.pdf: 794862 bytes, checksum: 72e4f5b0a4b660c7dce8983313d39876 (MD5) Approved for entry into archive by LUIZA DE MENEZES ROMANETTO (luizamenezes@reitoria.unesp.br) on 2017-04-07T17:48:24Z (GMT) No. of bitstreams: 1 hermini_al_me_rcla.pdf: 794862 bytes, checksum: 72e4f5b0a4b660c7dce8983313d39876 (MD5) Made available in DSpace on 2017-04-07T17:48:24Z (GMT). No. of bitstreams: 1 hermini_al_me_rcla.pdf: 794862 bytes, checksum: 72e4f5b0a4b660c7dce8983313d39876 (MD5) Previous issue date: 2017-03-09 Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) Este trabalho consiste em estudar a continuidade de funções do ponto de vista topológico. Além disso, exploramos as diferentes métricas em R² e através de transformações geométricas neste espaço analisamos qual tipo de ação exerce em bolas abertas usando métricas diferentes no domínio e contradomínio. In this work we study the continuity of maps from the topological point of view. In addition, we explore di erent metrics in R² and by using geometric transformations we analyze what kind of action carries in open balls using di erent metrics in the domain and in the codomain.

Submitted by GIVANILDO DONIZETI DE MELO null (givadonimelo@hotmail.com) on 2016-05-12T02:56:09Z No. of bitstreams: 1 Dis. Mestrado.pdf: 1055550 bytes, checksum: 47636418da76c9ad7d114b45ea3e96c1 (MD5) Approved for entry into archive by Felipe Augusto Arakaki (arakaki@reitoria.unesp.br) on 2016-05-13T16:57:01Z (GMT) No. of bitstreams: 1 melo_gd_me_sjrp.pdf: 1055550 bytes, checksum: 47636418da76c9ad7d114b45ea3e96c1 (MD5) Made available in DSpace on 2016-05-13T16:57:01Z (GMT). No. of bitstreams: 1 melo_gd_me_sjrp.pdf: 1055550 bytes, checksum: 47636418da76c9ad7d114b45ea3e96c1 (MD5) Previous issue date: 2016-03-23 Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) Neste trabalho nós estudamos o seguinte resultado: para um espaço métrico compacto X, de dimensão n, o subespaço dos mergulhos de X em R2n é denso no espaço das funções contínuas de X em R2n se, e somente se, dim(X x X)

We consider continuous free semigroup actions generated by a family $(g_y)_{y \,\in \, Y}$ of continuous endomorphisms of a compact metric space $(X,d)$ , subject to a random walk $\mathbb P_\nu =\nu ^{\mathbb N}$ defined on a shift space $Y^{\mathbb N}$ , where $(Y, d_Y)$ is a compact metric space with finite upper box dimension and $\nu $ is a Borel probability measure on Y. With the aim of elucidating the impact of the random walk on the metric mean dimension, we prove a variational principle which relates the metric mean dimension of the semigroup action with the corresponding notions for the associated skew product and the shift map $\sigma $ on $Y^{\mathbb {N}}$ , and compare them with the upper box dimension of Y. In particular, we obtain exact formulas whenever $\nu $ is homogeneous and has full support. We also discuss several examples to enlighten the roles of the homogeneity, of the support and of the upper box dimension of the measure $\nu $ , and to test the scope of our results.

Seja M um espaço métrico e P um subconjunto de M. O conhecido problema k vizinhos mais próximos (k-neareast neighbors, KNN) consiste em encontrar, dado q 2 M, os k elementos de P mais próximos de q conforme a métrica de M. Abordamos uma variação do problema KNN para uma classe particular de espaços pseudo-métricos, descrita a seguir. Seja m 2 N um natural e seja d a distância euclidiana em Rm. Dado um vetor p 2 Rm: p := (p1; : : : ; pm) seja C (p) o conjunto das m rotações das coordenadas de p: C (p) := f(p1; : : : ; pm); (p2; : : : ; pm; p1); : : : ; (pm; p1; : : : ; pm1)g definimos a distância especial de como: de(p;q) := min p02C (p) d(p0;q): de é uma pseudo-métrica, e (Rm;de) é um espaço pseudo-métrico. A classe de espaços pseudo-métricos abordada é (Rm;de) j m 2 N: A solução por força bruta é cara demais para instâncias de tamanho prático. Nós apresentamos uma solução mais eficiente empregando paralelismo, a FFT (transformada rápida de Fourier) e a eliminação rápida de vetores de treinamento desfavoráveis. Desenvolvemos um programa—chamado CyclicKNN—que implementa essa solução. Reportamos o speedup desse programa em comparação com a força bruta sequencial, processando bases de dados de referência. Let M be a metric space and let P be a subset of M. The well known k-nearest neighbors problem (KNN) consists in finding, given q 2 M, the k elements of P with are closest to q according to the metric of M. We discuss a variation of KNN for a particular class of pseudo-metric spaces, described as follows. Let m 2 N be a natural number and let d be the Euclidean distance in Rm. Given p 2 Rm: p := (p1; : : : ; pm) let C (p) be the set of the m rotations of p’s coordinates: C (p) := f(p1; : : : ; pm); (p2; : : : ; pm; p1); : : : ; (pm; p1; : : : ; pm1)g we define the special distance de as: de(p;q) := min p02C (p) d(p0;q): de is a pseudo-metric, and (Rm;de) is a pseudo-metric space. The class of pseudo-metric spaces under discussion is f(Rm;de) j m 2 N:g The brute force approach is too costly for instances of practical size. We present a more efficient solution employing parallelism, the FFT (fast Fourier transform) and the fast elimination of unfavorable training vectors.We describe a program—named CyclicKNN —which implements this solution.We report the speedup of this program over serial brute force search, processing reference datasets. Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES

Dissertação de mestrado em Ciências - Formação Contínua de Professores (área de especialização em Matemática), A distância de Hausdorff definida sobre os subconjuntos compactos de R2 tem provado ser um conceito muito útil no reconhecimento de imagens, justificando que se faça algum investimento na compreensão desta ferramenta e na demonstração de resultados que envolvam esta distância. Nesta dissertação, dado um espaço métrico (X,d), definindo H(X) como o conjunto dos compactos não vazios de X, pretendemos estudar algumas propriedades do espaço métrico (H(X); dH), em que dH é a distância de Hausdor . Para "educar" a nossa intuição sobre esta distância, achamos relevante dispor de um ambiente gráfico em que se possam manipular objetos simples em R2 e explorar situações relacionadas com este conceito. Nesta tese, apresentam-se duas defnições alternativas de distância de Hausdorff em H(X). Uma das definições utiliza o conceito de salsicha-ε de Minkowsky ou de vizinhança- -ε de um conjunto. Restringindo-nos a R2 e para ajudar a compreensão do conceito de convergência de sucessões de conjuntos, introduz-se a definição de convergência segundo de Kuratowski. Prova-se que, quando os conjuntos são convexos, a convergência segundo Kuratowski é equivalente à convergência no espaço métrico em estudo. São abordados aspetos computacionais que permitem ilustrar o conceito de distãncia de Hausdor , sendo possível manipular objetos de R2 de forma simples e construir as suas vizinhanças-ε . Os objetos considerados são pontos, segmentos de reta e linhas poligonais. Constrói-se uma função que permite determinar a distância de Hausdorff entre dois objetos usando o conceito de salsicha-ε de Minkowsky. O algoritmo usado para a construção desta função é fundamentado num conjunto de resultados enunciados e demonstrados nesta tese., The Hausdorff distance, defined in the compact subsets of R2, has proven to be a very useful concept in image recognition, justifying some investment in the understanding of this tool and in the proof of results involving this distance. In this dissertation, given a metric space (X; d), de ning H(X) as the set of compact and nonempty subsets of X, we intend to study some properties of the metric space (H(X); dH), where dH is the Hausdorff distance. In order to "educate" our intuition about this distance, we recognized it would be relevant to have a graphical user interface in which we can manipulate simple objects of R2 and explore situations related to this concept. In this thesis we present two alternative definitions of the Hausdorff distance in H(X). One of the definitions uses the concept of Minkowski ε-sausage or ε-neighborhoud of a set. We restrict ourselves to R2 and, to help in the comprehension of the concept of convergence of sequences of sets, we introduce the definition of Kuratowski convergence. We prove that, when the sets are convex, the Kuratowski convergence is equivalent to the convergence in the metric space under study. Computational aspects that allow to illustrate the Hausdorff distance are discussed, being possible to manipulate objects in R2 in an easy way and to construct their ε- neighbourhoods. The objects considered are points, line segments and polygonal lines. We construct a function that allows us to compute the Hausdorff distance between two objects, using the concept of Minkowski ε-sausage. The algorithm used in the construction of this function is justified by a set of results stated and proved in this thesis.

Orientador: Orlando Lee Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Nesta dissertação consideramos o problema do k-Servidor. Neste problema temos k servidores em um espaço métrico e nosso objetivo e atender a uma seqüência de requisições, de modo a minimizar a distancia total percorrida pelos servidores. Dedicamos especial atenção a conjectura do k-Servidor: qualquer espaço métrico admite um algoritmo k-competitivo para o problema do k-Servidor. Este e um dos problemas mais importantes em aberto da area de computação online. O algoritmo da função trabalho, proposto por Chrobak e Larmore, e especialmente relevante para a conjectura. Isto porque foi provado que este algoritmo e k-competitivo para diversos casos particulares do problema do k-Servidor. Alem disso, acredita-se que este algoritmo e de fato k-competitivo para todo espaço métrico. Por isto, o entendimento deste algoritmo e central neste trabalho. Para analisar o algoritmo da função trabalho são utilizados diversos resultados auxiliares desenvolvidos por vários autores. Neste trabalho tentamos apresentar de forma coesa uma coletânea destes resultados. A partir desta mostramos uma prova do teorema de Koutsoupias e Papadimitriou: o algoritmo da função trabalho e (2k - 1)-competitivo para todo espaço métrico. Este e o resultado mais importante relacionado ao problema do k-Servidor. Alem disso, mostramos que a conjectura do k-Servidor vale para alguns casos particulares do problema Abstract: In this work we study the k-server problem. In this problem, we have k servers on a metric space that must attend a sequence of requests with the goal of minimizing the total distance moved by the servers. We dedicate special attention to the k-server conjecture: any metric space allows for a k-competitive k-server algorithm. This is one of the most important open problems in online computing. The work function algorithm, proposed by Chrobak and Larmore, is very relevant to the conjecture. It has been proved that this algorithm is k-competitive for several special cases of the k-server problem. Furthermore, most researchers believe that the algorithm is indeed k-competitive for any metric space. Thus, a deeper understanding of this algorithm plays a special role in this work. To analyze the work function algorithm, we use many auxiliary results developed by several authors. In this work we tried to present a collection of these results in a concise way. From this, we present a proof of Koutsoupias and Papadimitriou's theorem: the work function algorithm is (2k - 1)-competitive for any metric space. This is the most important result related to the k-server problem. Moreover, we show that the k-server conjecture holds in some special cases Mestrado Otimização Combinatória Mestre em Ciência da Computação

Submitted by (ana.araujo@ufrpe.br) on 2016-08-03T13:41:09Z No. of bitstreams: 1 Luis Henrique Gama Dore de Araujo.pdf: 1262882 bytes, checksum: 228850aa4903df4934951d776241b9de (MD5) Made available in DSpace on 2016-08-03T13:41:09Z (GMT). No. of bitstreams: 1 Luis Henrique Gama Dore de Araujo.pdf: 1262882 bytes, checksum: 228850aa4903df4934951d776241b9de (MD5) Previous issue date: 2008-02-27 In this work, the k-means algorithm proposed by Hartigan and Wong is adapted to the case of random element observations in general metric space. Simulation results show that the performance of the algorithm in the case when the metric space is the shape space of the plane configurations, is independent on the choice of the usual shape metrics, more precisely the regular, complete and partial Procrustes distance. Besides, this modified version of the algorithm, applied to the shape space with any of the three metrics, exhibits the same performance as the original algorithm applied to the partial tangent Procrustes coordinates. The current study was motivated by the problem of identification of species of half-beak fish Hemiramphus balao and Hemiramphus brasiliensis.Currently, the parameters used for identification of these species are subject to certain operational difficulties, which often result in erroneous classification of the specimens. The algorithm was used to perform clustering of shape configuration samples, and two groups with statistically distinct shapes have been identified. These groups exhibit a pronounced difference regarding position of the head in relation to the body: for one group the head is slightly inclined upwards, while for the other group the head is slightly inclined downwards. Observation of these characteristics on the photos of fish specimens on which the two species were correctly classified, leads to identification of group 1 as Hemirapmphus balao and group 2 as species Hemiramphus brasiliensis. Therefore, head position with relation to body (which represents information entirely on the specimen shape) represents a rather robust parameter for identification of species. Neste trabalho, o algoritmo k-médias proposto por Hartigan e Wong foi adaptado para o caso no qual se tem observações de um elemento aleatório sobre um espaço métrico arbitrário. Resultados de simulações indicam que o desempenho do algoritmo, no caso em que o espaço métrico é o espaço das formas de configurações planas, é invariante com relação às três métricas de forma usuais a saber, as distâncias de Procrustes completa e parcial e a distância de Procrustes. Além disso, a versão modificada do algoritmo, quando aplicada no espaço das formas com qualquer uma destas três métricas, apresenta o mesmo desempenho do algoritmo original aplicado às coordenadas de Procrustes tangentes parciais. Um problema na identificação das espécies de peixes-agulhas Hemiramphus balao e Hemiramphus brasiliensis motivou este estudo. Atualmente, os parâmetros de identificação utilizados apresentam alguns problemas operacionais os quais permitem, em muitos casos, que peixes-agulha de uma espécie sejam classificados como da outra. O algoritmo foi utilizado para agrupar uma amostra das formas de configurações destes peixes e dois grupos com padrões de forma estatisticamente distintos foram encontrados. Estes grupos apresentaram uma diferença marcante na posição da cabeça com relação ao resto do corpo: no grupo 1 a cabeça é levemente inclinada para cima enquanto que no grupo 2 a cabeça é levemente inclinada para baixo. A observação destas características em fotos de peixes-agulha nas quais as duas espécies foram corretamente identificadas, permitiu constatar que o grupo 1 corresponde à espécie Hemirapmphus balao e o grupo 2 à espécie Hemiramphus brasiliensis. Dessa maneira, a posição da cabeça com relação ao resto do corpo (a qual é uma informação totalmente baseada na forma do peixe), pode ser utilizada como um parâmetro bastante robusto para identificação de sua espécie.

Orientador: Maria Sueli Marconi Roversi Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica Resumo: Estudamos um tipo especial de função denominada função ponto a conjunto, que associa a cada elemento de um espaço métrico um único subconjunto não vazio de outro espaço métrico. A noção de continuidade das funções usuais caracterizada por propriedades equivalentes, enun-ciadas em termos de vizinhanças ou em termos de seqüências, deram origem a versões corres-pondentes para as funções ponto a conjunto. As propriedades adaptadas, não mais equivalentes, são conhecidas como semicontinuidade superior e semicontinuidade inferior, respectivamente. Uma condição do tipo Lipschitz e um tipo de continuidade propriamente, obtido munindo-se o contradomínio da métrica de Hausdorff, foram relacionados à semicontinuidade. Algumas propriedades algébricas ou topológicas dos conjuntos imagem foram essenciais para os resulta-dos obtidos. Abordamos adaptações de alguns resultados clássicos da análise funcional como os teoremas da limitação uniforme, da aplicação aberta e do gráfico fechado para as funções ponto a conjunto caracterizadas como processos convexos, que são os análogos dos operadores lineares. Estabelecemos também uma versão do teorema de Schauder sobre pontos fixos para funções ponto a conjunto e também para as do tipo contração Abstract: We study a mapping called a set-valued map which associates with each point of a metric space a non empty subset of another metric space. In the case of single-valued maps, contin-uous functions are characterized by two equivalent properties: one in terms of neighborhood and other in terms of sequences. These two properties can be adapted to the case of set-valued maps, are no longer equivalent and are called upper semi continuity and lower semi continuity, respectively. We adapt to the set-valued case the concept of Lipschitz applications and also a type of continuity when the range is enjoyed with the Hausdorff metric. We related them with the conditions of semi continuity. Some of the results depends on algebraic or topological prop-erties of the images. We adapt to closed convex process the principIe of uniform boundedness, the Banach open mapping and closed graph theorems. The closed convex processes are the set-valued analogues of continuous linear operators. We also establish two fixed point result for set-valued maps: the first generalizes the Schauder fixed point theorem and the second considers that of contraction type Mestrado Matemática Mestre em Matemática

This work intends to publicize the already well-known Cantor set. The idea is to show a more detailed demonstration of some important properties that it has, in a certain way being not very common to find in texts in Portuguese. We will also see that, except for homeomorphism, the Cantor Set is the only one, as metric space, with all the indicated properties. Este trabalho tem por intenção divulgar o já conhecido Conjunto de Cantor. A ideia é exibir uma demonstração mais detalhada de algumas propriedades importantes que ele possui, não sendo, de certa forma, tão comum encontrá-las em textos em português. Também veremos que, a menos de homeomorfismo, o Conjunto de Cantor é o único, como espaço métrico, com todas as propriedades indicadas.

BARRETO, J. B. Uso da Divergência Generalizada na Clusterização Aplicada à Segmentação de Imagens. 2021. 79f. Dissertação (Mestrado em Engenharia Elétrica e Computação) – Programa de Pós-Graduação em Engenharia Elétrica e de Computação - Campus de Sobral, Universidade Federal do Ceará, Sobral, 2021. Image segmentation is a fundamental process in applications involving image analysis, as it is responsible for defining the regions of interest for the problem. A widely used technique for image segmentation is clustering. Clustering is based on a measure of similarity between objects to group them into regions. The use of dissimilarity measures in the metric space is quite common in pattern recognition systems, mainly in clustering algorithms. However, some studies have observed limitations with conventional distance functions in the search for similarity. In view of this, research focused on the use of non-metric divergences in the search for similarity between objects in clustering algorithms has attracted the attention of researchers. This work presents an alternative path for image segmentation using a generalized divergence as a measure of dissimilarity in Bregman hard clustering algorithm. This divergence is obtained by generalizing the relative entropies of Shannon and Tsallis, and defined in relation to a deformed exponential j. The work is developed using three deformed exponential functions, called j1, j2 and j3, and comparing their results with the classic K- textit means clustering technique and for some images with the Otsu’s method. The tests were performed for 5 groups of images, in which 2 groups are grayscale images divided into binary segmentation and segmentation in more than two regions, and 3 groups of color images, for tests in the RGB, HSV color space and with enhancement of the RGB levels. In order to analyze the segmentation results, in addition to the metrics accuracy, precision and sensitivity, the Sørensen – Dice similarity coefficient (CSD), and a qualitative evaluation obtained through the average of grades empirically attributed were used. The results showed a good performance of the proposed method with accuracy above 0.9 in all images using the j1 deformed exponential, CSD> 0.7 for 23 of the 25 images tested using the j1 and j2 deformed exponentials and average grade above 7 for 24 of the 25 images for the j1 and j2 deformed exponentials. In view of the results obtained, it is possible to conclude that the proposed method was not only shown to be applicable but also, depending on the application, it may present a better performance than methods already established in the literature. A segmentação de imagens é um processo fundamental em aplicações envolvendo análise de imagens, pois é responsável por definir as regiões de interesse para o problema. Uma técnica bastante utilizada para segmentação de imagens é a clusterização. A clusterização baseia-se em uma medida de similaridade entre objetos para agrupá-los em regiões. A utilização de medidas de dissimilaridade no espaço métrico é bem frequente em sistemas de reconhecimento de padrões, principalmente em algoritmos de clusterização. Contudo, alguns estudos tem observado limitações com funções de distância convencionais na etapa de busca por similaridade. Em vista disso, pesquisas voltadas para o uso de divergências não métricas na busca por semelhança entre objetos em algoritmos de clusterização tem atraído a atenção de pesquisadores. Este trabalho apresenta um caminho alternativo para segmentação de imagens utilizando uma divergência generalizada como medida de dissimilaridade no algoritmo de clusterização hard de Bregman. Essa divergência é obtida pela generalização das entropias relativas de Shannon e Tsallis, e definida em relação a uma exponencial deformada j. O trabalho é desenvolvido utilizando três funções exponenciais deformadas, denominadas j1, j2 e j3, e comparando seus resultados com a técnica de clusterização K-means clássica e para algumas imagens com o método de Otsu. Os testes foram realizados para 5 grupos de imagens, em que 2 grupos são de imagens em escala de cinza divididos em segmentação binária e segmentação em mais de duas regiões, e 3 grupos de imagens coloridas, para testes no espaço de cor RGB, HSV e com realce dos níveis RGB. Para analisar os resultados das segmentações são utilizados, além das métricas acurácia, precisão e sensibilidade, o coeficiente de similaridade Sørensen–Dice (CSD), e uma avaliação qualitativa obtida através da média de notas atribuídas empiricamente foram utilizadas. Os resultados apresentaram uma boa performance do método proposto com acurácia acima de 0,9 em todas as imagens utilizando a exponencial deformada j1, CSD > 0,7 para 23 das 25 imagens testadas utilizando as exponenciais deformadas j1 e j2 e nota média acima de 7 para 24 das 25 imagens para as exponenciais deformadas j1 e j2. Diante dos resultados obtidos é possível concluir que o método proposto não só se mostrou aplicável como também, dependendo da aplicação, pode apresentar um melhor desempenho que métodos já estabelecidos na literatura.

O Princípio Variacional para entropia estabelece que a entropia topológica de uma aplicação contínua definida num espaço métrico compacto é igual ao supremo das entropias de medidas invariantes. Uma extensão deste resultado é apresentada para aplicações próprias definidas em espaços separáveis localmente compactos. É apresentada a definição de coberturas e métricas admissíveis e também de versões estendidas das entropias topológicas de Adler-Konheim-McAndrew e de Bowen. O resultado principal é obtido ao relacionar as versões estendidas das entropias da aplicação própria com as entropias usuais da extensão da aplicação própria, sendo esta última definida na compactificação por um ponto do espaço separável localmente compacto. Palavras-chave: Entropia. Princípio Variacional. Espaços localmente compactos. The Variational Principle for entropy establishes that the topological entropy of a continuous application defined in a compact metric space is equal to the supreme of the entropy of invariant measures. An extension of this result is presented for proper applications defined in separable locally compact spaces. The definition of admissible coverages and metrics is presented, as well as extended versions of the topological entropies of Adler-Konheim-McAndrew and of Bowen. The main result is obtained by relating the extended versions of the entropies of the proper application with the usual entropies of the extension of the proper application defined in the compactification by a point of the separable locally compact space. Keywords: Entropy. Variational Principle. Locally compact spaces.

Orientadores: Verónica Andrea González-López, Jesus Enrique Garcia Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica Resumo: Nesta tese, aplicamos a métrica ds e noções correlatas (propostas em (GARCÍA; GHOLIZADEH; GONZÁLEZ-LÓPEZ, 2018a) e (FERNÁNDEZ et al., 2019)), derivadas a partir do BIC. Usamos tais noções para classificar realizações de processos estocásticos Markovianos, definidos num mesmo alfabeto A e possuindo uma ordem o e espaço de estados S Ao (o, |A|, |S| 8), doravante apenas chamados de cadeias de Markov (CM). O processo de construção e algumas propriedades de ds (e noções correlatas) são descritos. Assim, ordenamos, em relação a sua representatividade quanto às leis de formação, sequências de DNA provenientes de dados genômicos do vírus da Dengue tipo 1 (CORDEIRO et al., 2019a) e do vírus da Zika (GARCÍA et al., 2018), sendo que tais sequências foram tratadas como realizações de CM com alfabeto A ta, c, g, tu e o 3. Portanto, apontamos em cada caso qual sequência poderia ser usada como um "padrão-ouro" do conjunto das sequências, podendo esta ser usada em comparações com outras sequências de modo a, por exemplo, detectar novas cepas do vírus. No entanto, este procedimento tem por característica ignorar, a informação contida nas sequências não escolhidas. De modo a preencher esta lacuna, desenvolvemos uma extensão da métrica ds (proposta em (GARCÍA; GHOLIZADEH; GONZÁLEZ-LÓPEZ, 2018a)). Para tal é proposta uma nova noção (vide (CORDEIRO et al., 2020)) definida num conjunto M t1, ..., pu Ao, onde t1, ..., pu é um conjunto de indexadores para cada uma das p realizações independentes de CM disponíveis. Na modelagem particionamos o conjunto M usando uma relação de equivalência e, mostramos como esta métrica pode ser utilizada na obtenção do Modelo de Markov de Partições (MMP), proposto em (CORDEIRO et al., 2020). Na sequência, mostramos também algumas das propriedades teóricas da métrica, dentre elas: (i) a prova de que ela é, de fato uma métrica e, portanto, M um espaço métrico (ii) a consistência estatística da métrica na estimação do MMP (CORDEIRO et al., 2020). Adiante, trouxemos duas aplicações da métrica na obtenção de MMP, para coleções de dados genômicos dos vírus Epstein-Bar (CORDEIRO et al., 2019b) e da Zika (CORDEIRO et al., 2020). Em ambas as aplicações, um modelo único que descreve de forma parcimoniosa, a lei de formação de todas as sequências, foi obtido. Como na primeira situação, este modelo único poderia ser comparado a outras sequências não utilizadas na estimação do modelo e, assim, identificar possíveis novas cepas do vírus sob investigação Abstract: In this thesis, we apply the ds metric and related notions (proposed in (GARCÍA; GHOLIZADEH; GONZÁLEZ-LÓPEZ, 2018a) and (FERNÁNDEZ et al., 2019)), derived from the BIC. We use these notions to classify realizations of Markovian stochastic processes, defined in the same alphabet A and having an order o and state space S Ao (o, |A|, |S| 8), hereinafter referred to as Markov chains (CM). The construction process and some properties of ds (and related notions) are described. Thus, we ordered, in relation to their representativeness regarding the formation laws, DNA sequences from genomic data of the Dengue virus type 1 (CORDEIRO et al., 2019a) and the Zika virus (GARCÍA et al., 2018), and such sequences were treated as CM realizations with alphabet A ta, c, g, tu and o 3. Therefore, we indicate in each case which sequence could be used as a "gold standard" of the set of sequences, which can be used in comparisons with other sequences in order, for example, to detect new strains of the virus. However, this procedure has the characteristic of ignoring, the information contained in the non-chosen sequences. In order to fill this gap, we developed an extension of the ds metric (proposed in (GARCÍA; GHOLIZADEH; GONZÁLEZ-LÓPEZ, 2018a)). To this end, a new notion is proposed (see (CORDEIRO et al., 2020)) defined in a set M t1, ..., pu Ao, where t1, ..., pu is a set of indexers for each of the available p independent CM realizations. In the modeling we partition the set M using an equivalence relation and, we show how this metric can be used to obtain the Partition Markov Model (MMP), proposed in (CORDEIRO et al., 2020). In the sequence, we also show some of the theoretical properties of the metric, among them: (i) the proof that it is, in fact, a metric and, therefore, M a metric space (ii) the statistical consistency of the metric in the estimation of the MMP (CORDEIRO et al., 2020). Lastly, we brought two applications of the metric in obtaining MMP, for collections of genomic data of the Epstein-Bar (CORDEIRO et al., 2019b) and Zika (CORDEIRO et al., 2020) viruses. In both applications, a unique model that sparingly describes the law of formation of all sequences was obtained. As in the first situation, this unique model could be compared to other sequences not used in the estimation of the model and, thus, to identify possible new strains of the virus under investigation Doutorado Estatística Doutor em Estatística CAPES 0

This work discusses the position-dependent translation operator in the Schrödinger and Heisenberg formulation of quantum mechanics. In both representations, we discuss the importance of sufficient conditions for the moment operator to be hermitian in the metric space to which it is defined. After that, we see that in the Schrödinger's wave formulation we find a Schrödinger equation that governs the temporal evolution of wave functions. Likewise, in Heisenberg's matrix formulation we find a Heisenberg equation that governs the temporal evolution of the operators. Finally, as an application of the Heisenberg formalism we calculate the temporal evolution of the uncertainty in time and the broadening of wave packets of a particle in a one-dimensional space under null potential for a Euclidean metric and also for a metric with a first order term in its power series . On the other hand, we solve the one-dimensional space free particle for metrics with first and second term of its expansion in series of power in Schrödinger's formulation. Neste trabalho é discutido o operador de translação dependente da posição na formulação de Schrödinger e Heisenberg da mecânica quântica. Nas duas representações, discutimos a importância de condições suficientes para que o operador momento seja hermitiano no espaço de métrica ao qual ele é definido. Após isso, vemos que na formulação ondulatória de Schrödinger encontramos uma equação tipo equação de Schrödinger que governa a evolução temporal das funções de onda. De igual modo, na formulação matricial de Heisenberg encontramos uma equação tipo equação de Heisenberg que governa a evolução temporal dos operadores. Por fim, como aplicação do formalismo de Heisenberg calculamos a evolução temporal da incerteza no tempo e o alargamento de pacotes de onda de uma partícula em um espaço unidimensional sob potencial nulo para uma métrica euclidiana e também para uma métrica com termo de primeira ordem em sua série de potência. Por outro lado, resolvermos a partícula livre em um espaço unidimensional para métricas com primeiro e segundo termo de sua expansão em série de potência na formulação de Schrödinger.

Deslocamentos de tipo finito são uma classe de sistemas, com entropia topológica conhecida, definidos em determinados subespaços invariantes de {1,... d}k, onde K = N ou Z. No presente texto, substituimos o alfabeto finito por um métrico compacto X para estudar deslocamentos com transições dadas por um conjunto fechado Γ C X x X. Em geral, tais deslocamentos terão entropia infinita, conduzindo ao estudo da sua dimensão métrica média. Provamos que a dimensão de sistemas unilaterais e bilaterais induzidos por um mesmo T coincidem, como é o caso da entropia, calculamos explicitamente o seu valor em uma classe de exemplos e mostramos uma aplicação do modelo em ações de semi-grupos finitamente gerados. Para mostrar tais resultados, antes obtemos uma prova simples e análoga ao caso da entropia de que para qualquer f : X -> X contínua num métrico compacto, sua restrição a \1 n=0fn(X) tem dimensão métrica média total. Os resultados originais do texto são: Corolário 5.6, Teorema 6.2, Teorema 6.5, Corol ario 6.6 e o Teorema 7.2. Subshifts of nite type are a class of systems, with known topological entropy, de ned on certain invariant subspaces of {1,...d}k, where K= N or Z. In the present text, we replace the nite alphabet by a compact metric one X in order to study subshifts with transitions described by a closed subset Γ C X x X. In general, such systems will have in nite topological entropy, leaning towards the study of its metric mean dimension. We prove that the dimension of unilateral and bilateral systems induced by the same Γ coincide, as it is the case of entropy, calculate its value explicitly on a class of examples and show an application of the model to nitely generated semi-group actions. To show such results, before we obtain a simple proof, analogous to the entropy case, that for any continuous f : X -> X on a compact metric space, its restriction to \1 n=0fn(X) has full metric mean dimension. The original results of the text are Corollary 5.6, Theorem 6.2, Theorem 6.5, Corollary 6.6 and Theorem 7.2.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES O problema dos k-servos em um grafo ponderado (ou espaço métrico) é definido pela necessidade de mover eficientemente k servos para atender uma sequência de requisições que surgem de maneira online em cada nó do grafo. Este é talvez o problema mais influente de computação online cuja solução continua em aberto servindo de abstração para diversas aplicações, como a compra e venda de moedas, reatribuição de processos em processamento paralelo para balanceamento de carga, serviços de transporte online, gerenciamento de sondas de produção de petróleo, dentre outros. Sua simplicidade conceitual contrasta com sua complexidade computacional que cresce exponencialmente com o aumento do número de nós e servos. Anteriormente a este trabalho, o algoritmo Q-learning foi utilizado na solução de pequenas instâncias do problema dos k-servos. A solução ficou restrita à pequenas dimensões do problema pois sua estrutura de armazenamento cresce exponencialmente com o aumento do número de nós e servos. Este problema, conhecido como maldição de dimensionalidade, torna ineficiente ou até impossibilita a execução do algoritmo para certas instâncias do problema. Para lidar com maiores dimensões, o Qlearning em conjunto com o algoritmo guloso foi aplicado a um número reduzido de nós separados por um processo de agrupamento (abordagem hierárquica). A política local obtida em cada agrupamento, em conjunto com a política gulosa, foi utilizada na formação de uma política global, abordando de maneira satisfatória grandes instâncias do problema. Os resultados foram comparados a importantes algoritmos da literatura, o Work function, o Harmonic e o guloso. As soluções até então propostas dão ênfase ao aumento do número de nós, porém se analisarmos o crescimento da estrutura de armazenamento definida por Cn,k ' O(nk), é possível perceber que o aumento do número de servos pode torná-la rapidamente limitada pelo problema da maldição da dimensionalidade. Para contornar esta barreira, o problema dos k-servos foi modelado como um problema de aprendizagem por reforço profundo cuja a função de valor estado-ação foi definida por uma rede neural perceptron de múltiplas camadas capaz de extrair as informações do ambiente a partir de imagens que codificam a dinâmica do problema. A aplicabilidade do algoritmo proposto foi ilustrada em um estudo de caso no qual diferentes configurações do problema foram consideradas. O comportamento dos agentes foi analisado durante a fase de treinamento e sua performance foi avaliada a partir de testes de desempenho que quantificaram a qualidade das políticas de deslocamento dos servos geradas. Os resultados obtidos fornecem uma visão promissora de sua utilização como solução alternativa ao problema dos k-servos. The k-server problem in a weighted graph (or metric space) is defined by the need to efficiently move k servers to fulfill a sequence of requests that arise online at each graph node. This is perhaps the most influential online computation problem whose solution remains open, serving as an abstraction for a variety of applications, as buying and selling of currencies, reassign processes in a parallel processing for load balancing, online transportation service, probe management of oil production rigs, among others. Its conceptual simplicity contrasts with its computational complexity that grows exponentially with the increasing number of nodes and servers. Prior to this work, the Q-learning algorithm was used to solve small instances of the k-server problem. The solution was restricted to small dimensions of the problem because its storage structure grows exponentially with the increase in the number of nodes and servers. This problem, known as the curse of dimensionality, makes the algorithm inefficient or even impossible to execute for certain instances of the problem. To handle with larger dimensions, Q-learning together with the greedy algorithm were applied to a small number of nodes separated into different clusters (hierarchical approach). The local policy obtained from each cluster, together with greedy policy, were used to form a global policy satisfactorily addressing large instances of the problem. The results were compared to important algorithms in the literature, as the Work function, Harmonic and greedy. The solutions proposed so far emphasize the increase in the number of nodes, but if we analyze the growth of the storage structure defined by Cn,k ' O(nk) It can be seen that the increase in the number of servers can be quickly limited by the problem of the curse of dimensionality. To circumvent this barrier, the k-server problem was modeled as a deep reinforcement learning task whose state-action value function was defined by a multilayer perceptron neural network capable of extracting environmental information from images that encode the dynamics of the problem. The applicability of the proposed algorithm was illustrated in a case study in which different problem configurations were considered. The behavior of the agents was analyzed during the training phase and their performance was evaluated from performance tests that quantified the quality of the displacement policies of the servers generated. The results provide a promising insight into its use as an alternative solution to the k-servers problem.

This master's thesis aims to study the centered version of the Fractional Maximal Operator, primarily its regularity in L^p(R^n) spaces along with the Riesz Potential. Next, we will define both operators in measures of R^n in order to prove the B.Muckenhoupt-R.L.Wheeden Theorem. Then we will study two theorems of Juha Kinnunen about the behavior of the operator in Sobolev spaces. We will also present point estimates for the operator's weak gradient, where one of them provides a control of function oscillation. We will analyze the regularity in Sobolev spaces of the local version of the operator {M}_{alpha,omega} in open ended with finite measure. In addition, we will give a punctual estimate of the weak gradient of the operator, which unlike the non-local case, we will have the addition of an extra term containing the Fractional Local Maximal, then we will mention some examples that will show the optimization of the presented results. Finally, we will study the action of the Fractional Maximal Operator on Campanato spaces {L}^{p,beta}(X), where X is a measurable metric space equipped with a regular positive Borel measure satisfying the property "Doubling Property Means Condition" . A presente dissertação de mestrado tem como objetivo estudar a versão centrada do Operador Maximal Fracionário, primeiramente sua regularidade nos espaços L^p(R^n) junto com o Potencial de Riesz. Na sequência, definiremos ambos os operadores em medidas do R^n com o intuito de provar o Teorema de B.Muckenhoupt-R.L.Wheeden. Depois estudaremos dois teoremas de Juha Kinnunen sobre o comportamento do operador nos Espaços de Sobolev. Apresentaremos também estimativas pontuais para o gradiente fraco do operador, onde uma delas fornece um controle da oscilação de funções. Analisaremos a regularidade em espaços de Sobolev da versão local do operador {M}_{alfa,omega} em abertos com medida finita. Além disso, daremos uma estimativa pontual do gradiente fraco do operador, que diferentemente do caso não local, teremos o acréscimo de um termo extra contendo o Maximal Local Fracionário, em seguida mencionaremos alguns exemplos que evidenciarão a otimização dos resultados apresentados. Ao final, estudaremos a ação do Operador Maximal Fracionário em espaços de Campanato {L}^{p,beta}(X), onde X é espaço métrico mensuravél munido com uma medida positiva regular de Borel satisfazendo a propriedade "Doubling Property Means Condition".