Modelagem geométrica envolvendo objetos implícitos é um tema de intensa pesquisa em Computação Gráfica. Portanto, obter técnicas eficientes para representar esses objetos é de extrema importância. Dois grupos de objetos implícitos relevantes para Computação Gráfica são as curvas implícitas e superfícies implícitas. As técnicas tradicionais para se aproximar curvas e superfícies implícitas envolvem dividir o domínio e buscar em suas partições partes da curva ou da superfície. Neste projeto propomos um novo métodos de poligonização robusta de curvas implícitas usando uma ferramenta numérica auto-validada chamada de Aritmética Afim. O método consiste na poligonização adaptativa de curvas implícitas em malhas triangulares tridimensionais. / Geometric modeling involving implicit objects is a topic of intense research in Computer Graphics. Thus, obtain efficient techniques for representing these objects is of utmost importance. Two groups of relevant implicit objects for Computer Graphics are implicit curves and implicit surfaces. Traditional techniques for approximating implicit curves and surfaces involve splitting the domain and searching for parts of the curve or the surface. In this project we propose a new methods of robust polygonization of implicit curves using the self-validated numerical tool called Affine Arithmetic. The method consists in the adaptive polygonization of implicit curves in three-dimensional triangular meshes.

Modelos de Markov ocultos (MMOs) são uma ferramenta importante em matemática aplicada e estatística. Eles se baseiam em dois processos estocásticos. O primeiro é uma cadeia de Markov, que não é observada diretamente. O segundo é observável e sua distribuição depende do estado na cadeia de Markov. Supomos que os processos são discretos no tempo e assumem um número finito de estados. Para extrair informações dos MMOs, é necessário estimar seus parâmetros. Diversos algoritmos locais têm sido utilizados nas últimas décadas para essa tarefa. Nosso trabalho estuda a estimação de parâmetros em modelos de Markov ocultos, do ponto de vista da otimização global. Desenvolvemos algoritmos capazes de encontrar, em uma execução bem sucedida, todos os estimadores de máxima verossimilhança globais de um modelo de Markov oculto. Para tanto, usamos aritmética intervalar. Essa aritmética permite explorar sistematicamente o espaço paramétrico, excluindo regiões que não contém soluções. O cálculo da função objetivo é feito através da recursão \\textit, descrita na literatura estatística. Modificamos a extensão intervalar natural dessa recursão usando programação linear. Nossa abordagem é mais eficiente e produz intervalos mais estreitos do que a implementação padrão. Experimentos mostram ganhos de 16 a 250 vezes, de acordo com a complexidade do modelo. Revisamos os algoritmos locais, tendo em vista sua aplicação em métodos globais. Comparamos os algoritmos de Baum-Welch, pontos interiores e gradientes projetados espectrais. Concluímos que o método de Baum-Welch é o mais indicado como auxiliar em otimização global. Modificamos o \\textit{interval branch and bound} para resolver a estimação de modelos com eficiência. Usamos as condições KKT e as simetrias do problema na construção de testes para reduzir ou excluir caixas. Implementamos procedimentos de aceleração da convergência, como o método de Newton intervalar e propagação de restrições e da função objetivo. Nosso algoritmo foi escrito em \\textit{C++}, usando programação genérica. Mostramos que nossa implementação dá resultados tão bons quanto o resolvedor global BARON, porém com mais eficiência. Em média, nosso algoritmo é capaz de resolver $50\\%$ mais problemas no mesmo período de tempo. Concluímos estudando aspectos qualitativos dos MMOs com mistura Bernoulli. Plotamos todos os máximos globais detectados em instâncias com poucas observações e apresentamos novos limitantes superiores da verossimilhança baseados na divisão de uma amostra grande em grupos menores. / Hidden Markov models(HMMs) are an important tool in statistics and applied mathematics. Our work deals with processes formed by two discrete time and finite state space stochastic processes. The first process is a Markov chain and is not directly observed. On the other hand, the second process is observable and its distribution depends on the current state of the hidden component. In order to extract conclusions from a Hidden Markov Model we must estimate the parameters that defines it. Several local algorithms has been used to handle with this task. We present a global optimization approach based on interval arithmetic to maximize the likelihood function. Interval arithmetic allow us to explore parametric space systematically, discarding regions which cannot contain global maxima. We evaluate the objective function and its derivatives by the so called backward recursion and show that is possible to obtain sharper interval extensions for such functions using linear programming. Numerical experiments shows that our approach is $16$ to $250$ times more efficient than standard implementations. We also study local optimization algorithms hidden Markov model estimation. We compare Baum-Welch procedure with interior points and spectral projected gradients. We conclude that Baum-Welch is the best option as a sub-algorithm in a global optimization framework. We improve the well known interval branch and bound algorithm to take advantages on the problem structure. We derive new exclusion tests, based on its KKT conditions and symmetries. We implement our approach in C++, under generic programming paradigm. We show that our implementation is compatible with global optimization solver BARON in terms of precision. We also show that our algorithm is faster than BARON. In average, we can handle with $50\\%$ more problems within the same amount of time. We conclude studying qualitative aspects of Bernoulli hidden Markov models. We plot all global maxima found in small observations instances and show a new upper bound of the likelihood based on splitting observations in small groups.

Modelos de Markov ocultos (MMOs) são uma ferramenta importante em matemática aplicada e estatística. Eles se baseiam em dois processos estocásticos. O primeiro é uma cadeia de Markov, que não é observada diretamente. O segundo é observável e sua distribuição depende do estado na cadeia de Markov. Supomos que os processos são discretos no tempo e assumem um número finito de estados. Para extrair informações dos MMOs, é necessário estimar seus parâmetros. Diversos algoritmos locais têm sido utilizados nas últimas décadas para essa tarefa. Nosso trabalho estuda a estimação de parâmetros em modelos de Markov ocultos, do ponto de vista da otimização global. Desenvolvemos algoritmos capazes de encontrar, em uma execução bem sucedida, todos os estimadores de máxima verossimilhança globais de um modelo de Markov oculto. Para tanto, usamos aritmética intervalar. Essa aritmética permite explorar sistematicamente o espaço paramétrico, excluindo regiões que não contém soluções. O cálculo da função objetivo é feito através da recursão \\textit, descrita na literatura estatística. Modificamos a extensão intervalar natural dessa recursão usando programação linear. Nossa abordagem é mais eficiente e produz intervalos mais estreitos do que a implementação padrão. Experimentos mostram ganhos de 16 a 250 vezes, de acordo com a complexidade do modelo. Revisamos os algoritmos locais, tendo em vista sua aplicação em métodos globais. Comparamos os algoritmos de Baum-Welch, pontos interiores e gradientes projetados espectrais. Concluímos que o método de Baum-Welch é o mais indicado como auxiliar em otimização global. Modificamos o \\textit{interval branch and bound} para resolver a estimação de modelos com eficiência. Usamos as condições KKT e as simetrias do problema na construção de testes para reduzir ou excluir caixas. Implementamos procedimentos de aceleração da convergência, como o método de Newton intervalar e propagação de restrições e da função objetivo. Nosso algoritmo foi escrito em \\textit{C++}, usando programação genérica. Mostramos que nossa implementação dá resultados tão bons quanto o resolvedor global BARON, porém com mais eficiência. Em média, nosso algoritmo é capaz de resolver $50\\%$ mais problemas no mesmo período de tempo. Concluímos estudando aspectos qualitativos dos MMOs com mistura Bernoulli. Plotamos todos os máximos globais detectados em instâncias com poucas observações e apresentamos novos limitantes superiores da verossimilhança baseados na divisão de uma amostra grande em grupos menores. / Hidden Markov models(HMMs) are an important tool in statistics and applied mathematics. Our work deals with processes formed by two discrete time and finite state space stochastic processes. The first process is a Markov chain and is not directly observed. On the other hand, the second process is observable and its distribution depends on the current state of the hidden component. In order to extract conclusions from a Hidden Markov Model we must estimate the parameters that defines it. Several local algorithms has been used to handle with this task. We present a global optimization approach based on interval arithmetic to maximize the likelihood function. Interval arithmetic allow us to explore parametric space systematically, discarding regions which cannot contain global maxima. We evaluate the objective function and its derivatives by the so called backward recursion and show that is possible to obtain sharper interval extensions for such functions using linear programming. Numerical experiments shows that our approach is $16$ to $250$ times more efficient than standard implementations. We also study local optimization algorithms hidden Markov model estimation. We compare Baum-Welch procedure with interior points and spectral projected gradients. We conclude that Baum-Welch is the best option as a sub-algorithm in a global optimization framework. We improve the well known interval branch and bound algorithm to take advantages on the problem structure. We derive new exclusion tests, based on its KKT conditions and symmetries. We implement our approach in C++, under generic programming paradigm. We show that our implementation is compatible with global optimization solver BARON in terms of precision. We also show that our algorithm is faster than BARON. In average, we can handle with $50\\%$ more problems within the same amount of time. We conclude studying qualitative aspects of Bernoulli hidden Markov models. We plot all global maxima found in small observations instances and show a new upper bound of the likelihood based on splitting observations in small groups.

Modelagem geométrica envolvendo objetos implícitos é um tema de intensa pesquisa em Computação Gráfica. Portanto, obter técnicas eficientes para representar esses objetos é de extrema importância. Dois grupos de objetos implícitos relevantes para Computação Gráfica são as curvas implícitas e superfícies implícitas. As técnicas tradicionais para se aproximar curvas e superfícies implícitas envolvem dividir o domínio e buscar em suas partições partes da curva ou da superfície. Neste projeto propomos um novo métodos de poligonização robusta de curvas implícitas usando uma ferramenta numérica auto-validada chamada de Aritmética Afim. O método consiste na poligonização adaptativa de curvas implícitas em malhas triangulares tridimensionais. / Geometric modeling involving implicit objects is a topic of intense research in Computer Graphics. Thus, obtain efficient techniques for representing these objects is of utmost importance. Two groups of relevant implicit objects for Computer Graphics are implicit curves and implicit surfaces. Traditional techniques for approximating implicit curves and surfaces involve splitting the domain and searching for parts of the curve or the surface. In this project we propose a new methods of robust polygonization of implicit curves using the self-validated numerical tool called Affine Arithmetic. The method consists in the adaptive polygonization of implicit curves in three-dimensional triangular meshes.

Orientador: Silvio Ferraz Mello Filho / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Artes / Made available in DSpace on 2018-08-20T10:18:14Z (GMT). No. of bitstreams: 1 Ferreira_GuilhermeAntonioCelso_D.pdf: 12287973 bytes, checksum: b45cb51a780101bcbd8a10396b9a29ca (MD5) Previous issue date: 2012 / Resumo: Esse trabalho se situa na área de Composição Assistida por Computador, CAC. Mais especificamente, na geração de material pré-composicional em nível simbólico. Nosso uso e apropriação desse recurso tecnológico foram, no entanto influenciados pela filosofia de Vilém Flusser, especialmente pela sua obra Filosofia da Caixa Preta. Tivemos como objetivos dessa pesquisa tanto uma contribuição (via Flusser) para o debate em torno do ambiente de composição atual, quanto o uso do recurso computacional notadamente característico desse ambiente para solucionar um problema de organização de alturas e ordenação de eventos musicais. O tratamento dado ao espaço de alturas na música pós-tonal privilegia, na sua generalidade e abstração, abordagens mais analíticas do que práticas. Dessa forma, introduzimos o conceito de Tabela de Diferenças Intervalares, TDI, como uma fotografia das relações intervalares em uma sequência temporal que incorpora tanto intervalos entre eventos sucessivos quanto intervalos entre eventos não adjacentes, de certa maneira retomando uma proposta de Ernest Ansermet (1987). Apartir desse conceito (TDI) formalizamos um algoritmo capaz de gerar novas ordenações temporais com relações intervalares semelhantes a inicial em um contexto não-tonal. Esse procedimento se revelou como um recurso prático para a composição capaz de introduzir no cálculo intervalar uma dimensão de organização temporal. Ao testarmos a viabilidade desse procedimento em nossa prática composicional descobrimos ser ele também capaz de ser desenvolvido como procedimento de organização rítmica e harmônica. Apresentamos nesse trabalho quatro obras compostas usando esse algoritmo que esperamos contribuir para os recursos disponíveis para tratamento harmônico na música contemporânea / Abstract: This work is in the field of Computer Aided Composition (CAC), more specifically in the generation of pre-compositional material in the symbolic level. Our use and ownership of this technological capability were however influenced by the philosophy of Vilém Flusser, "Towards a Philosophy of Photography". We had as goals of this research both a contribution, via Flusser, to the debate on the current composition environment, and the use of compositional resource most notedly characteristic (computer) of that environment to resolve an issue of pitch structure and the ordering of musical events. The treatment of pitch structures in post tonal music favours in its generality and abstraction, approaches more analytical than practical. Hence, we have introduced the concept of Interval Difference Table (IDT) like photography of intervallic relations in a timeline that incorporates both intervals between successive event and between nonadjacent events, somewhat reviving a proposal of Ernest Ansermet (1987). From this concept (IDT) we formalized and algorithm capable of generating new temporal ordinations with the same intervallic content in a non-tonal context. This procedure has proved to be a practical resource for composition capable of introducing into the intervallic calculation a dimension of temporal organization. In testing the feasibility of this procedure in our compositional practice we found that it was also able to be developed as rhythmic and harmonic organization strategy. We pesent in this work four compositions using this algorithm which we hope will contribute as ressources available to contemporary music composers / Doutorado / Processos Criativos / Doutor em Música

Submitted by isabela.moljf@hotmail.com (isabela.moljf@hotmail.com) on 2016-08-12T12:40:39Z No. of bitstreams: 1 biancamariacostaaraujo.pdf: 4585632 bytes, checksum: 78f37e18164b9b5f82a0867bf14ee884 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-08-15T13:32:18Z (GMT) No. of bitstreams: 1 biancamariacostaaraujo.pdf: 4585632 bytes, checksum: 78f37e18164b9b5f82a0867bf14ee884 (MD5) / Made available in DSpace on 2016-08-15T13:32:18Z (GMT). No. of bitstreams: 1 biancamariacostaaraujo.pdf: 4585632 bytes, checksum: 78f37e18164b9b5f82a0867bf14ee884 (MD5) Previous issue date: 2016-02-03 / Estudos de fluxo de potência são tipicamente utilizados para determinar as condições de operação em estado permanente de um sistema de energia elétrica, avaliadas para um determinado conjunto de valores de geração e carga. Quando os dados de entrada são incertos, vários cenários precisam ser analisados para cobrir a faixa de incerteza. Sob tais condições, torna-se necessária a utilização de algoritmos que incorporem o efeito da incerteza dos dados de geração e carga na análise do fluxo de potência. Como uma alternativa para este problema, um novo metódo de solução é proposto com base na utilização da aritmética afim, que é um modelo melhorado para análise numérica de auto-validação. Nesta aritmética, as quantidades de interesse são representadas como combinações afim de certas variáveis primitivas, que representam as fontes de incerteza nos dados ou aproximações feitas durante o cálculo. Esta técnica é incorporada ao fluxo de potência expresso em termos das equações de injeção de corrente, com as tensões escritas na forma retangular. Posteriomente, os resultados obtidos aplicando-se a aritmética intervalar e a Simulação de Monte Carlo na resolução do problema de incertezas no fluxo de potência em redes de energia elétrica são comparados. / Power flow analysis typically uses a given set of generation and loading profiles to determine steady state operating conditions of electric power systems. When the input data are imprecise, several scenarios need to be analysed to cover the range of uncertainties. Under these conditions, it is necessary to utilise algorithms to incorporate the effect of the uncertainties within the power flow analysis. As an alternative solution to this issue, a new method has been proposed, based on the use of affine arithmetic. This alternative technique has been developed to improve the self-validated numerical analysis. Within affine arithmetic, the quantities of interest are represented by affine combinations of certain primitive variables. The affine combinations can signify both the source of the uncertainties in the data and the approximations during calculations. This technique is incorporated at the power flow which is expressed in terms of current injection equations, with the voltages represented in the rectangular form. The proposed results are later compared with the Monte Carlo Simulation and interval arithmetic, both of which solve the same issue: uncertainties in the power flow analysis of electric power grids.

Orientador: Edvaldo Assunção / Resumo: Neste trabalho estudamos problemas de controle ótimo intervalar e intervalar fuzzy. Em particular, propomos problemas de controle ótimo via teoria de incerteza generalizada e teoria dos conjuntos fuzzy. Dentre os vários tipos de incerteza generalizada utilizamos apenas a intervalar. Embora as abordagens do processo de solução dos problemas de controle ótimo intervalar e intervalar fuzzy sejam similares, as premissas iniciais para o uso e identificação de aplicação delas em problemas práticos são distintas assim como é distinto o processo de tomada de decisão. Assim, propomos inicialmente o problema de controle ótimo intervalar em tempo discreto. A primeira proposta de solução para o problema de controle ótimo intervalar em tempo discreto é construída usando a aritmética intervalar restrita de níveis simples juntamente com a técnica de programação dinâmica. As respostas do problema de controle ótimo intervalar contêm as possibilidades de soluções viáveis, e para implementar uma solução viável para o usuário final usamos a solução que minimiza o arrependimento máximo nos exemplos numéricos. A segunda proposta de solução para o problema de controle ótimo intervalar em tempo discreto é realizada com a aritmética intervalar restrita uma vez que essa aritmética intervalar é mais geral do que a aritmética intervalar restrita de níveis simples pois não considera os intervalos envolvidos nas operações variando de forma dependente. Exemplos numéricos também foram construídos e ilustram... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: In this work we study the interval optimal control problem and fuzzy interval optimal control problem. In particular, we propose optimal control problems via theory of generalized uncertainty and fuzzy set theory. Among the various types of generalized uncertainty we use only the interval uncertainty. Although the approaches to solve the interval optimal control problem and fuzzy interval optimal control problem are similar, the input data for problems with generalized uncertainty and flexibility are distinct as is distinct the decision-making process. Thus, we initially propose the discrete-time interval optimal control problem. The first solution method to solve the discrete-time interval optimal control problem is constructed using single-level constrained interval arithmetic coupled with a dynamic programming technique. The optimal interval solution contains the real-valued optimal solutions, and to implement a feasible solution to the user we use the minimax regret criterion in numerical examples. The second solution method to solve the discrete-time interval optimal control problem is done with the constrained interval arithmetic since this interval arithmetic is more general than the single-level constrained interval arithmetic because it does not have its intervals varying of dependent form in interval operations. Numerical examples have also been constructed and illustrate the method of solution. Finally, we study the discrete-time fuzzy interval optimal control prob... (Complete abstract click electronic access below) / Doutor