VIEIRA, F. B. Controlabilidade de algumas EDPs não lineares, e, densidade e espectro de subvariedades mínimas em espaço forma. 2017. 89 f. Tese (Doutorado em Matemática) – Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2017. / Submitted by Andrea Dantas (pgmat@mat.ufc.br) on 2017-04-19T13:15:27Z No. of bitstreams: 1 2016_tese_fbvieira.pdf: 681898 bytes, checksum: d123b89ff8ddaa52a643807b847421b5 (MD5) / Rejected by Rocilda Sales (rocilda@ufc.br), reason: Para o aluno. Alterar a data e incluir a conclusão, tanto no sumário como no final do texto. Conclusão é capítulo portanto numerado. Rocilda on 2017-04-19T14:54:37Z (GMT) / Submitted by Andrea Dantas (pgmat@mat.ufc.br) on 2017-04-19T16:23:39Z No. of bitstreams: 1 2016_tese_fbvieira.pdf: 683722 bytes, checksum: 8e8575ca8d8e8496b31047d5bc8c68c0 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2017-04-24T11:15:25Z (GMT) No. of bitstreams: 1 2016_tese_fbvieira.pdf: 683722 bytes, checksum: 8e8575ca8d8e8496b31047d5bc8c68c0 (MD5) / Made available in DSpace on 2017-04-24T11:15:25Z (GMT). No. of bitstreams: 1 2016_tese_fbvieira.pdf: 683722 bytes, checksum: 8e8575ca8d8e8496b31047d5bc8c68c0 (MD5) Previous issue date: 2017-05-24 / In the first part of this thesis we deal with the 3D Navier-Stokes and Boussinesq systems in a cube. We prove some results concerning the global approximate controllability by means of boundary controls which act in some part of the boundary. They are generalizations and variants of some previous results by Guerrero, Imanuvilov and Puel. Still in the first part of this Thesis, we prove the internal and boundary local null controllability of a 1D parabolic PDE with nonlinear diffusion. Here, the main tools are Liusternik’s inverse function Theorem and appropriate Carleman estimates. In the second part of this Thesis, we consider M m minimal properly immersed submanifolds in a complete ambient space N n suitably close to a space form N n k of curvature −k ≤ 0. We are interested in the relation between the density function Θ(r) of M m and the spectrum of the Laplace-Beltrami operator. In particular, we prove that if Θ(r) has subexponential growth (when k < 0) or sub-polynomial growth (k = 0) along a sequence, then the spectrum of M m is the same as that of the space form N m k . Notably, the result applies to Anderson’s (smooth) solutions of Plateau’s roblem at infinity on the hyperbolic space H n , independently of their boundary regularity. We also give a simple condition on the second fundamental form that ensures M to have finite density. In particular, we show that minimal submanifolds of H n with finite total curvature have finite density. / Na primeira parte desta tese tratamos dos sistemas 3D de Navier-Stokes e Boussinesq em um cubo. Nós provamos alguns resultados sobre a controlabilidade aproximada global por meio de controles de bordo que agem em uma parte da fronteira. Estes reultados são generalizações e variações de alguns resultados anteriores de Guerrero, Imanuvilov e Puel. Ainda na primeira parte da tese, nós provamos a controlabilidade nula local interna e de bordo de uma EDP parabólica 1D com difusão não linear. Aqui, as ferramentas principais são o teorema da função inversa de Liusternik e desigualdades de Carleman adequadas. Na segunda parte desta tese, consideramos M m subvariedades mínimas propriamente imersas em um espaço ambiente completo N n adequadamente próximo a um espaço forma N n k de curvatura −k ≤ 0. Estamos interessados na relação entre a função densidade Θ(r) de M m e o espectro do operador Laplace-Beltrami. Em particular, provamos que se Θ(r) temum crescimento subexponencial (quando k < 0) ou bubpolinomial (k = 0) ao longo de uma sequência, então o espectro de M m é o mesmo do espaço forma N m k . Notavelmente, o resultado se aplica a soluções Anderson (suaves) do problema de Plateau no infinito sobre o espaço hiperbólico H n , independentemente da regularidade dos seus bordos. Nós também fornecemos uma condição simples sobre a segunda forma fundamental que garante que M tem densidade finita. Em particular, mostramos que subvariedades mínimas de H n com curvatura total finita te densidade finita.

Made available in DSpace on 2015-05-15T11:45:59Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 715500 bytes, checksum: d95f1a0101cba7f4f31b21e2b0da1bb3 (MD5) Previous issue date: 2011-07-22 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The present work has the distributed control v applied to the linear wave's equation. We seek to reach two objective, one of the kind Controllability and another the not system state distance to a state y2 (x; t) predefined. This is an problem of multicriteria optimization, and to solves him, introduce the notion Stackelberg's Optimal Control (classical in economy), in which we divide v into two, tell v1 and v2, and each one will act in the respective part from the Boundary 1;2 with a hierarchy between the same. This way, we take over that v1 is the control leader and v1 will be the follower. To leave of this terminogy, we use the idea of the hierarchical control, that is, admit that given a right v1, optimize the second goal concerning v2 and find a relation such that v2 = F (v1). So, the first goal became function of v1, belonging to the kind approximate controlability that will be proved through a density criterion and a Holmgren's uniqueness theorem. Finally, proved for controlability close, from unicidade of the solution, find Optimality system for the control leader. / O presente trabalho tem o controle distribuído v aplicado á fronteira da Equação da Onda Linear. Buscamos atingir dois objetivos: um do tipo controlabilidade, e outro o não distanciamento do estado do sistema a um estado y2 (x; t) predefinido. Esse é um problema de otimização multicritério, e para solucioná-lo, introduzimos a noção de controle ótimo de Stackelberg (clássico em economia), no qual dividimos v em dois, digamos v1 e v2; e cada um atuará na respectiva parte da fronteira -1; -2, com uma hierarquia entre os mesmos. Assim, assumimos que v1 é o controle líder e v2 será o seguidor. A partir dessa terminologia, usamos a ideia do controle hierárquico, isto é, admitimos que dado um certo v1, otimizamos o segundo objetivo com respeito a v2 e encontramos uma relação tal que v2 = F (v1). Então, o primeiro objetivo tornou-se função de v1; sendo do tipo controlabilidade aproximada que será provado através de um critério de densidade e do teorema de unicidade de Holmgren. Por último, provada a controlabilidade aproximada e a partir da unicidade da solução, encontramos o sistema de otimalidade para o controle líder.

Made available in DSpace on 2015-05-15T11:46:05Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 674722 bytes, checksum: eb17d5816a0fce98d1def5be593711f1 (MD5) Previous issue date: 2011-09-29 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / We have as main issue in this work the Hierarchical Control, which consists in a leader-followers system. We studied in special the heat equation approximate controllability under Stackelberg-Nash&#146;s strategy, which is directed in controlling every system from local controls choices with the minimum possible costs. / Temos como principal tema neste trabalho o Controle Hierárquico, que consiste em um sistema de líder e seguidores. Estudamos em especial a controlabilidade aproximada da equação do Calor sob a estratégia de Stackelberg-Nash, estratégia esta direcionada em controlar todo sistema a partir de escolhas de controles locais com o mínimo de custos possíveis.

O planejamento operacional de um sistema de transporte de longa distância implica resolver um problema de otimização de rede dinâmica, visando a efetuar, de forma eficaz e eficiente, o atendimento às demandas de cargas, utilizando a capacidade de transporte disponível. A metodologia de solução proposta utiliza a abordagem de Rede de Filas Logísticas, a qual substitui o processo de otimização global da rede (usualmente utilizando Programação Linear Inteira) por um modelo de Programação Dinâmica Estocástica, Aproximada e Adaptativa, que permite a resolução de uma série de subproblemas delimitados no tempo, reduzindo sensivelmente a quantidade de variáveis envolvidas. Este método permite a utilização de modelos matemáticos mais realistas em horizontes de planejamento mais amplos. O presente trabalho estende os modelos encontrados na Literatura, aplicando o método a problemas de maior complexidade, incluindo a consideração de frotas heterogêneas de veículos, janelas de início de atendimento, utilização de terceiros transportadores e penalidades pelo não atendimento das demandas. São apresentados exemplos de problemas experimentais submetidos com sucesso à técnica desenvolvida. O trabalho inclui ainda o delineamento de um Sistema de Apoio à Decisão incorporando a metodologia proposta. / Operational planning of a long haul transportation system implies to solve a dynamic network optimization problem, aiming to perform the freight movements in an efficient and effective way, while utilizing the available transportation capacity. The proposed solution methodology utilizes the Logistic Queueing Network approach, replacing the network global optimization process through Integer Linear Programming by a model of Stochastic, Approximate and Adaptive Dynamic Programming, which allows the resolution of a sequence of sub- problems delimited in time, strongly reducing the quantity of variables involved. This method allows the utilization of more realistic mathematical models in a broader planning horizon. The research extends models found in the literature to solve more complex problems, including the consideration of heterogeneous fleet of vehicles, time windows, third party vehicles and penalties for not attendance of demands. Experimental problems solved successfully with the developed technique are presented. The work also presents the delineation of a Decision Support System incorporating the proposed methodology.

Neste trabalho propomos o uso de um método Bayesiano para estimar o parâmetro de memória de um processo estocástico com memória longa quando sua função de verossimilhança é intratável ou não está disponível. Esta abordagem fornece uma aproximação para a distribuição a posteriori sobre a memória e outros parâmetros e é baseada numa aplicação simples do método conhecido como computação Bayesiana aproximada (ABC). Alguns estimadores populares para o parâmetro de memória serão revisados e comparados com esta abordagem. O emprego de nossa proposta viabiliza a solução de problemas complexos sob o ponto de vista Bayesiano e, embora aproximativa, possui um desempenho muito satisfatório quando comparada com métodos clássicos. / In this work we propose the use of a Bayesian method for estimating the memory parameter of a stochastic process with long-memory when its likelihood function is intractable or unavailable. Such approach provides an approximation for the posterior distribution on the memory and other parameters and it is based on a simple application of the so-called approximate Bayesian computation (ABC). Some popular existing estimators for the memory parameter are reviewed and compared to this method. The use of our proposal allows for the solution of complex problems under a Bayesian point of view and this proposal, although approximative, has a satisfactory performance when compared to classical methods.

Neste trabalho, estudamos o problema de corte bidimensional multiperíodo com sobras aproveitáveis, que consiste em cortar objetos grandes visando a produção de um conjunto de itens menores. Supomos um horizonte de planejamento finito com uma quantidade finita de períodos entre os tempos inicial e final. Primeiramente consideramos uma versão determinística em que conhecemos, à priori, os itens solicitados em uma ordem de trabalho e o custo dos objetos a cada período. Algumas das sobras geradas durante o processo de corte dos itens solicitados em um período podem ser utilizadas como objetos no futuro. As sobras que podem ser usadas no futuro são denominadas sobras aproveitáveis. De forma geral, uma sobra é considerada aproveitável se possui dimensões iguais ou superiores as de algum item de uma lista pré-definida para o período. O objetivo é minimizar o custo total dos objetos utilizados para satisfazer a ordem de trabalho dos itens solicitados de todo o horizonte considerado. Havendo soluções com o mesmo custo, desejamos encontrar aquela que, no fim do horizonte de tempo considerado, maximize o valor das sobras aproveitáveis remanescentes. Apresentamos uma modelagem matemática do problema usando uma formulação em dois níveis, que é transformada em um modelo de programação linear inteira mista, devido às características do problema. Considerando a dificuldade em resolver o modelo desenvolvido, apresentamos uma proposta de uma abordagem heurística baseada em Programação Dinâmica Aproximada (PDA) para lidar com o problema proposto. Outras opções baseadas em estratégias do tipo horizonte rolante e relax-and-fix também são consideradas. Consideramos também o cenário onde não conhecemos de antemão os itens da ordem de trabalho e o custo dos objetos, mas temos informações das distribuições de probabilidade de ambos. Nesse caso, apresentamos uma abordagem baseada em programação dinâmica aproximada para estimar a melhor estratégia a ser seguida em cada período. Comparamos os resultados obtidos pela PDA com os resultados encontrados por um método guloso. Em cenários adequados, os resultados mostram que a PDA consegue soluções superiores ao método guloso. / In this research, we study the multi-period two-dimensional cutting problem with usable leftover, which consists of cutting objects to produce a set of items. We assume a finite planning horizon with a finite amount of periods between the initial and final times. First we consider a deterministic version in which we know, a priori, the set of ordered items and the cost of the objects at each period. Some of the leftovers generated during the cutting process of the ordered items in a period may be used as objects in the future. The leftovers that can be used in the future are called usable leftovers. In general, a leftover is considered usable if it has dimensions equal to or greater than that of some item from a predefined list for the period. The goal is to minimize the total cost of the objects used to cut the set of ordered items of the entire considered horizon. If there are solutions with the same cost, we wish to find one that, at the end of the considered time horizon, maximizes the value of the remaining usable leftovers. We present a mathematical model of the problem using a bilevel formulation, which is transformed into a mixed integer linear programming model, due to the characteristics of the problem. Considering the difficulty in solving the developed model, we propose a heuristic approach based on approximate dynamic programming (ADP) to deal with the proposed problem. Other options based on the rolling horizon and relax-and-fix strategies are also considered. We also consider the scenario where we do not know in advance the set of ordered items and the cost of the objects, but we have information about the probability distributions of both. In this case, we present an approach based on approximate dynamic programming to estimate the best strategy to be followed at each period. We compared the results obtained by the ADP with the results found by a greedy method. In suitable scenarios, the results show that the ADP achieves superior solutions to the greedy method.

Esta dissertação de mestrado aborda formulações computacionais e algoritmos para a busca e extração de padrões em cadeias biológicas. Em particular, o presente texto concentra-se nos dois problemas a seguir, considerando-os sob as distâncias de Hamming e Levenshtein: a) como determinar os locais nos quais um dado padrão ocorre de modo aproximado em uma cadeia fornecida; b) como extrair padrões que ocorram de modo aproximado em um número significativo de cadeias de um conjunto fornecido. O primeiro problema, para o qual já existem diversos algoritmos polinomiais, tem recebido muita atenção desde a década de 60, e ganhou novos ares com o advento da biologia computacional, nos idos dos anos 80, e com a popularização da Internet e seus mecanismos de busca: ambos os fenômenos trouxeram novos obstáculos a serem superados, em razão do grande volume de dados e das bastante justas restrições de tempo inerentes a essas aplicações. O segundo problema, de surgimento um pouco mais recente, é intrinsicamente desafiador, em razão de sua complexidade computacional, do tamanho das entradas tratadas nas aplicações mais comuns e de sua dificuldade de aproximação. Também é de chamar a atenção o seu grande potencial de aplicação. Neste trabalho são apresentadas formulações adequadas dos problemas abordados, assim como algoritmos e estruturas de dados essenciais ao seu estudo. Em especial, estudamos a extremamente versátil árvore dos sufixos, assim como uma de suas generalizações e sua estrutura irmã: o vetor dos sufixos. Grande parte do texto é dedicada aos filtros baseados em q-gramas para a busca aproximada de padrões e algumas de suas mais recentes variações. Estão cobertos os algoritmos bit-paralelos de Myers e Baeza-Yates-Gonnet para a busca de padrões; os algoritmos de Sagot para a extração de padrões; os algoritmos de filtragem de Ukkonen, Jokinen-Ukkonen, Burkhardt-Kärkkäinen, entre outros. / This thesis deals with computational formulations and algorithms for the extraction and search of patterns from biological strings. In particular, the present text focuses on the following problems, both considered under Hamming and Levenshtein distances: 1. How to find the positions where a given pattern approximatelly occurs in a given string; 2. How to extract patterns which approximatelly occurs in a certain number of strings from a given set. The first problem, for which there are many polinomial time algorithms, has been receiving a lot of attention since the 60s and entered a new era of discoveries with the advent of computational biology, in the 80s, and the widespread of the Internet and its search engines: both events brought new challenges to be faced by virtue of the large volume of data usually held by such applications and its time constraints. The second problem, much younger, is very challenging due to its computational complexity, approximation hardness and the size of the input data usually held by the most common applications. This problem is also very interesting due to its potential of application. In this work we show computational formulations, algorithms and data structures for those problems. We cover the bit-parallel algorithms of Myers, Baeza-Yates-Gonnet and the Sagots algorithms for patterns extraction. We also cover here the oustanding versatile suffix tree, its generalised version, and a similar data structure: the suffix array. A significant part of the present work focuses on q-gram based filters designed to solve the approximate pattern search problem. More precisely, we cover the filter algorithms of Ukkonen, Jokinen-Ukkonen and Burkhardt-Kärkkäinen, among others.

A crescente disponibilidade de dados em diferentes domínios tem motivado o desenvolvimento de técnicas para descoberta de conhecimento em grandes volumes de dados complexos. Trabalhos recentes mostram que a busca em dados complexos é um campo de pesquisa importante, já que muitas tarefas de mineração de dados, como classificação, detecção de agrupamentos e descoberta de motifs, dependem de algoritmos de busca ao vizinho mais próximo. Para resolver o problema da busca dos vizinhos mais próximos em domínios complexos muitas abordagens determinísticas têm sido propostas com o objetivo de reduzir os efeitos da maldição da alta dimensionalidade. Por outro lado, algoritmos probabilísticos têm sido pouco explorados. Técnicas recentes relaxam a precisão dos resultados a fim de reduzir o custo computacional da busca. Além disso, em problemas de grande escala, uma solução aproximada com uma análise teórica sólida mostra-se mais adequada que uma solução exata com um modelo teórico fraco. Por outro lado, apesar de muitas soluções exatas e aproximadas de busca e mineração terem sido propostas, o modelo de programação em CPU impõe restrições de desempenho para esses tipos de solução. Uma abordagem para melhorar o tempo de execução de técnicas de recuperação e mineração de dados em várias ordens de magnitude é empregar arquiteturas emergentes de programação paralela, como a arquitetura CUDA. Neste contexto, este trabalho apresenta uma proposta para buscas kNN de alto desempenho baseada numa técnica de hashing e implementações paralelas em CUDA. A técnica proposta é baseada no esquema LSH, ou seja, usa-se projeções em subespac¸os. O LSH é uma solução aproximada e tem a vantagem de permitir consultas de custo sublinear para dados em altas dimensões. Usando implementações massivamente paralelas melhora-se tarefas de mineração de dados. Especificamente, foram desenvolvidos soluções de alto desempenho para algoritmos de descoberta de motifs baseados em implementações paralelas de consultas kNN. As implementações massivamente paralelas em CUDA permitem executar estudos experimentais sobre grandes conjuntos de dados reais e sintéticos. A avaliação de desempenho realizada neste trabalho usando GeForce GTX470 GPU resultou em um aumento de desempenho de até 7 vezes, em média sobre o estado da arte em buscas por similaridade e descoberta de motifs / The increasing availability of data in diverse domains has created a necessity to develop techniques and methods to discover knowledge from huge volumes of complex data, motivating many research works in databases, data mining and information retrieval communities. Recent studies have suggested that searching in complex data is an interesting research field because many data mining tasks such as classification, clustering and motif discovery depend on nearest neighbor search algorithms. Thus, many deterministic approaches have been proposed to solve the nearest neighbor search problem in complex domains, aiming to reduce the effects of the well-known curse of dimensionality. On the other hand, probabilistic algorithms have been slightly explored. Recently, new techniques aim to reduce the computational cost relaxing the quality of the query results. Moreover, in large-scale problems, an approximate solution with a solid theoretical analysis seems to be more appropriate than an exact solution with a weak theoretical model. On the other hand, even though several exact and approximate solutions have been proposed, single CPU architectures impose limits on performance to deliver these kinds of solution. An approach to improve the runtime of data mining and information retrieval techniques by an order-of-magnitude is to employ emerging many-core architectures such as CUDA-enabled GPUs. In this work we present a massively parallel kNN query algorithm based on hashing and CUDA implementation. Our method, based on the LSH scheme, is an approximate method which queries high-dimensional datasets with sub-linear computational time. By using the massively parallel implementation we improve data mining tasks, specifically we create solutions for (soft) realtime time series motif discovery. Experimental studies on large real and synthetic datasets were carried out thanks to the highly CUDA parallel implementation. Our performance evaluation on GeForce GTX 470 GPU resulted in average runtime speedups of up to 7x on the state-of-art of similarity search and motif discovery solutions

Essa dissertação apresenta o desenvolvimento métodos para caracterização da conectividade entre séries temporais neurofisiológicas. Utilizam-se metodologias provenientes da Teoria da Informação Entropias Aproximada e Amostral para representar a complexidade da série no tempo, o que permite inferir como sua variabilidade se transfere a outras sequências, através do uso da coerência parcial direcionada. Para cada sistema analisado: (1) Faz-se uma transformação em outro, relacionando-o às medidas de entropia, (2) Estima-se a conectividade pela coerência parcial direcionada e (3) Avalia-se a robustez do procedimento via simulações de Monte Carlo e análise de sensibilidade. Para os exemplos simulados, a técnica proposta é capaz de oferecer resultados plausíveis, através da correta inferência da direção de conectividade em casos de acoplamento não-linear (quadrático), com número reduzido de amostras temporais dos sinais, em que outras abordagens falham. Embora de simples implementação, conclui-se que o processo mostra-se como uma extensão da causalidade de Granger para o caso não-linear. / The purpose of this work is to present the development of methods for characterizing the connectivity between nonlinear neurophysiological time series. Methodologies from Information Theory Approximate and Sample Entropies are used to represent the complexity of the series in a period of time, which allows inferring on how its variability is transferred to other sequences, using partial directed coherence. Methods: For each system under consideration, (1) It is done a transformation in another, relating it to measures of entropy, (2) The connectivity is estimated by the use of partial directed coherence and (3) The robustness of the procedure is analyzed via Monte Carlo simulations and sensitivity analysis. Results: For the simulated examples, the proposed technique is able to offer plausible results, through the correct inference of the connectivity direction, in cases of nonlinear coupling (quadratic), with a reduced number of signals samples, where other approaches fail. Conclusion: The process proves to be an extension of the Granger causality to the nonlinear case.

Essa dissertação apresenta o desenvolvimento métodos para caracterização da conectividade entre séries temporais neurofisiológicas. Utilizam-se metodologias provenientes da Teoria da Informação Entropias Aproximada e Amostral para representar a complexidade da série no tempo, o que permite inferir como sua variabilidade se transfere a outras sequências, através do uso da coerência parcial direcionada. Para cada sistema analisado: (1) Faz-se uma transformação em outro, relacionando-o às medidas de entropia, (2) Estima-se a conectividade pela coerência parcial direcionada e (3) Avalia-se a robustez do procedimento via simulações de Monte Carlo e análise de sensibilidade. Para os exemplos simulados, a técnica proposta é capaz de oferecer resultados plausíveis, através da correta inferência da direção de conectividade em casos de acoplamento não-linear (quadrático), com número reduzido de amostras temporais dos sinais, em que outras abordagens falham. Embora de simples implementação, conclui-se que o processo mostra-se como uma extensão da causalidade de Granger para o caso não-linear. / The purpose of this work is to present the development of methods for characterizing the connectivity between nonlinear neurophysiological time series. Methodologies from Information Theory Approximate and Sample Entropies are used to represent the complexity of the series in a period of time, which allows inferring on how its variability is transferred to other sequences, using partial directed coherence. Methods: For each system under consideration, (1) It is done a transformation in another, relating it to measures of entropy, (2) The connectivity is estimated by the use of partial directed coherence and (3) The robustness of the procedure is analyzed via Monte Carlo simulations and sensitivity analysis. Results: For the simulated examples, the proposed technique is able to offer plausible results, through the correct inference of the connectivity direction, in cases of nonlinear coupling (quadratic), with a reduced number of signals samples, where other approaches fail. Conclusion: The process proves to be an extension of the Granger causality to the nonlinear case.