Geometric optimization on visibility problems: metaheuristic and exact solutions

Os problemas de visibilidade têm diversas aplicações a situações reais. Entre os mais conhecidos, e exaustivamente estudados, estão os que envolvem os conceitos de vigilância e ocultação em estruturas geométricas (problemas de vigilância e ocultação). Neste trabalho são estudados problemas de visibilidade em estruturas geométricas conhecidas como polígonos, uma vez que estes podem representar, de forma apropriada, muitos dos objectos reais e são de fácil manipulação computacional. O objectivo dos problemas de vigilância é a determinação do número mínimo de posições para a colocação de dispositivos num dado polígono, de modo a que estes dispositivos consigam “ver” a totalidade do polígono. Por outro lado, o objectivo dos problemas de ocultação é a determinação do número máximo de posições num dado polígono, de modo a que quaisquer duas posições não se consigam “ver”. Infelizmente, a maior parte dos problemas de visibilidade em polígonos são NP-difíceis, o que dá origem a duas linhas de investigação: o desenvolvimento de algoritmos que estabelecem soluções aproximadas e a determinação de soluções exactas para classes especiais de polígonos. Atendendo a estas duas linhas de investigação, o trabalho é dividido em duas partes. Na primeira parte são propostos algoritmos aproximados, baseados essencialmente em metaheurísticas e metaheurísticas híbridas, para resolver alguns problemas de visibilidade, tanto em polígonos arbitrários como ortogonais. Os problemas estudados são os seguintes: “Maximum Hidden Vertex Set problem”, “Minimum Vertex Guard Set problem”, “Minimum Vertex Floodlight Set problem” e “Minimum Vertex k-Modem Set problem”. São também desenvolvidos métodos que permitem determinar a razão de aproximação dos algoritmos propostos. Para cada problema são implementados os algoritmos apresentados e é realizado um estudo estatístico para estabelecer qual o algoritmo que obtém as melhores soluções num tempo razoável. Este estudo permite concluir que as metaheurísticas híbridas são, em geral, as melhores estratégias para resolver os problemas de visibilidade estudados. Na segunda parte desta dissertação são abordados os problemas “Minimum Vertex Guard Set”, “Maximum Hidden Set” e “Maximum Hidden Vertex Set”, onde são identificadas e estudadas algumas classes de polígonos para as quais são determinadas soluções exactas e/ou limites combinatórios.

A study of singular integral operators with shift

Nesta tese, consideram-se operadores integrais singulares com a acção extra de um operador de deslocacamento de Carleman e com coeficientes em diferentes classes de funções essencialmente limitadas. Nomeadamente, funções contínuas por troços, funções quase-periódicas e funções possuíndo factorização generalizada. Nos casos dos operadores integrais singulares com deslocamento dado pelo operador de reflexão ou pelo operador de salto no círculo unitário complexo, obtêm-se critérios para a propriedade de Fredholm. Para os coeficientes contínuos, uma fórmula do índice de Fredholm é apresentada. Estes resultados são consequência das relações de equivalência explícitas entre aqueles operadores e alguns operadores adicionais, tais como o operador integral singular, operadores de Toeplitz e operadores de Toeplitz mais Hankel. Além disso, as relações de equivalência permitem-nos obter um critério de invertibilidade e fórmulas para os inversos laterais dos operadores iniciais com coeficientes factorizáveis. Adicionalmente, aplicamos técnicas de análise numérica, tais como métodos de colocação de polinómios, para o estudo da dimensão do núcleo dos dois tipos de operadores integrais singulares com coeficientes contínuos por troços. Esta abordagem permite também a computação do inverso no sentido Moore-Penrose dos operadores principais. Para operadores integrais singulares com operadores de deslocamento do tipo Carleman preservando a orientação e com funções contínuas como coeficientes, são obtidos limites superiores da dimensão do núcleo. Tal é implementado utilizando algumas estimativas e com a ajuda de relações (explícitas) de equivalência entre operadores. Focamos ainda a nossa atenção na resolução e nas soluções de uma classe de equações integrais singulares com deslocamento que não pode ser reduzida a um problema de valor de fronteira binomial. De forma a atingir os objectivos propostos, foram utilizadas projecções complementares e identidades entre operadores. Desta forma, as equações em estudo são associadas a sistemas de equações integrais singulares. Estes sistemas são depois analisados utilizando um problema de valor de fronteira de Riemann. Este procedimento tem como consequência a construção das soluções das equações iniciais a partir das soluções de problemas de valor de fronteira de Riemann. Motivados por uma grande diversidade de aplicações, estendemos a definição de operador integral de Cauchy para espaços de Lebesgue sobre grupos topológicos. Assim, são investigadas as condições de invertibilidade dos operadores integrais neste contexto.

Cálculo das variações fraccional generalizado

Nesta tese de doutoramento apresentamos um cálculo das variações fraccional generalizado. Consideramos problemas variacionais com derivadas e integrais fraccionais generalizados e estudamo-los usando métodos directos e indirectos. Em particular, obtemos condições necessárias de optimalidade de Euler-Lagrange para o problema fundamental e isoperimétrico, condições de transversalidade e teoremas de Noether. Demonstramos a existência de soluções, num espaço de funções apropriado, sob condições do tipo de Tonelli. Terminamos mostrando a existência de valores próprios, e correspondentes funções próprias ortogonais, para problemas de Sturm- Liouville.

Minimal state-space realizations of 2D convolutional codes

In this thesis we consider two-dimensional (2D) convolutional codes. As happens in the one-dimensional (1D) case one of the major issues is obtaining minimal state-space realizations for these codes. It turns out that the problem of minimal realization of codes is not equivalent to the minimal realization of encoders. This is due to the fact that the same code may admit different encoders with different McMillan degrees. Here we focus on the study of minimality of the realizations of 2D convolutional codes by means of separable Roesser models. Such models can be regarded as a series connection between two 1D systems. As a first step we provide an algorithm to obtain a minimal realization of a 1D convolutional code starting from a minimal realization of an encoder of the code. Then, we restrict our study to two particular classes of 2D convolutional codes. The first class to be considered is the one of codes which admit encoders of type n 1. For these codes, minimal encoders (i.e., encoders for which a minimal realization is also minimal as a code realization) are characterized enabling the construction of minimal code realizations starting from such encoders. The second class of codes to be considered is the one constituted by what we have called composition codes. For a subclass of these codes, we propose a method to obtain minimal realizations by means of separable Roesser models.

Numerical and combinatorial applications of generalized Appell polynomials

This thesis studies properties and applications of different generalized Appell polynomials in the framework of Clifford analysis. As an example of 3D-quasi-conformal mappings realized by generalized Appell polynomials, an analogue of the complex Joukowski transformation of order two is introduced. The consideration of a Pascal n-simplex with hypercomplex entries allows stressing the combinatorial relevance of hypercomplex Appell polynomials. The concept of totally regular variables and its relation to generalized Appell polynomials leads to the construction of new bases for the space of homogeneous holomorphic polynomials whose elements are all isomorphic to the integer powers of the complex variable. For this reason, such polynomials are called pseudo-complex powers (PCP). Different variants of them are subject of a detailed investigation. Special attention is paid to the numerical aspects of PCP. An efficient algorithm based on complex arithmetic is proposed for their implementation. In this context a brief survey on numerical methods for inverting Vandermonde matrices is presented and a modified algorithm is proposed which illustrates advantages of a special type of PCP. Finally, combinatorial applications of generalized Appell polynomials are emphasized. The explicit expression of the coefficients of a particular type of Appell polynomials and their relation to a Pascal simplex with hypercomplex entries are derived. The comparison of two types of 3D Appell polynomials leads to the detection of new trigonometric summation formulas and combinatorial identities of Riordan-Sofo type characterized by their expression in terms of central binomial coefficients.

Implementação em hardware reconfigurável de método de separação de dados hiperespetrais

Relatório do Trabalho Final de Mestrado para obtenção do grau de Mestre em Engenharia de Electrónica e Telecomunicações

Análise dinâmica de rotores de grupos turbo e hidrogeradores com o método das matrizes de transferência

Conhecer o comportamento vibratório de rotores de máquinas rotativas, já durante a fase de projeto, é uma necessidade cada vez maior nos dias atuais, quando modificações corretivas, após o início da operação, já não são mais aceitáveis, devido aos altos custos de material e execução empregados, se comparados com os lucros que são cada vez mais reduzidos, em função das regras impostas pelo mercado, e devido também ao tempo necessário para tais modificações, que implica em manter a máquina parada, sem gerar lucros nesse penodo, acarretando em mu1tas contratuais para o fabricante. o presente trabalho visa dar subsídiosà análise dinâmicadas linhas de eixos de turbo e hidrogeradores (conjuntos formados pela turbina mais o gerador, usados respectivamentenas centraistermelétricase hidrelétricas). Inicialmente é feita uma breve explanação sobre formas construtivas de hidrogeradores e tipos de turbinas hidráu1icas utilizados atualmente. O trabalho prossegue apresentando as propriedades dos mancais com filme de óleo, os fenômenos do empuxo magnético no rotor do gerador e do efeito giroscópico, bem como a norma ISO 1940, que define os níveis admissíveis de desbalanceamentos residuais para rotores de máquinas É apresentada uma formulação matemática pelo Método das Matrizes de Transferência para as análises das vibrações livres, bem como das vibrações forçadas com carregamentos cíclicos devido aos desbalanceamentos residuais das linhas de eixos. A análise das vibrações livres é feita para a obtenção das fteqüências naturais torcionais e das fteqüências tlexionais críticas em um plano. A análise das vibrações forçadas é elaborada para fornecer as respostas dinâmicas em dois planos ortogonais, devido ao desbalanceamento residual. Para aplicação da metodologia de cálculo apresentada, são elaboradas rotinas computacionais de cálculos, utilizando como plataforma o software MATLAB. Para testar o Método das Matrizes de Transferência, bem como os programas de computador elaborados, faz-se algumas análises com soluções analíticas exatas e comparam-se resultados obtidos. Como aplicação prática, faz-se um estudo aprofundado dos comportamentos dinâmicos algumas linhas de eixos de hidrogeradores, para variações de configurações de construção dessas, bem como para as diversas condições de operação.

Desenvolvimento teórico e análise numérica de uma plataforma de forças extensométrica com aplicação específica na impulsão para o salto em distância

Na realização de atividades físicas o corpo humano exerce forças contra o solo. Em atividades tais como correr e saltar as forças são exercidas através dos pés. Atualmente, sabe-se que estudos da magnitude e direção destas forças, e das maneiras de suas mudanças no tempo, fornecem valiosas informações sobre a performance alcançada no movimento, podendo indicar medidas corretivas que possam aprimorá-la. Na obtenção destas variáveis determinantes no desempenho do movimento utilizam-se instrumentos denominados plataformas de forças, capazes de medir a força de ação realizada sobre sua superfície de contato, e o respectivo momento, permitindo a determinação das três componentes ortogonais de força (Fx, Fy, Fz) e os momentos em torno dos três eixos ortogonais (Mx, My, Mz) simultaneamente. Este trabalho descreve o desenvolvimento teórico de uma plataforma de forças específica para aplicação na decolagem do salto em distância, bem como as alternativas de projeto geradas neste desenvolvimento. Foram buscadas soluções para a realização dos experimentos sob condições naturais de treinamento, visando a construção do instrumento e sua instalação na pista de saltos atléticos. Para isso é proposta a substituição da tábua de impulsão original pela plataforma de forças desenvolvida. Nas alternativas geradas foi utilizado o princípio extensométrico resistivo de medição de forças, que representa uma diminuição substancial no custo de manufatura estimado frente às unidades comercialmente avaliadas. Nestas alternativas, os sensores resistivos “strain gages” são localizados estrategicamente em estruturas metálicas que sustentam uma tampa de material composto com a função de superfície de contato Para a análise estrutural das alternativas estudadas foi utilizado o Método dos Elementos Finitos. Para comparar e escolher a melhor entre as diversas alternativas, foram propostos índices de desempenho. Ao final do trabalho são apresentadas conclusões sobre a metodologia empregada no estudo realizado e sobre o novo modelo de plataforma de forças desenvolvido.

Raízes polinomiais em corpos finitos

Este trabalho é um estudo sobre propriedades de decomposição de polinômios em corpos finitos. Em particular fazemos um estudo sobre métodos de fatoração e cálculos de raízes. Procedemos inicialmente com um apanhado de conceitos e teoremas que embasam o trabalho. Com o objetivo de determinar raízes de polinômios em corpos finitos, alguns tópicos tornam-se pré-requisitos. O primeiro deles é a própria representação dos elementos dos corpos finitos. O outro é o estudo de métodos determinísticos ou probabilísticos para fatorar polinômios sobre corpos finitos. Os métodos estudados são o de Berlekamp, Cantor-Zassenhaus e Lidl-Niederreiter. Fazemos finalmente o estudo de métodos que podem ser empregados para determinarmos as raízes de polinômios pertencentes a corpos finitos. Métodos estes que apresentam variações de acordo com o tamanho do corpo.

Estudo de um atuador planar

Um novo atuador planar eletromagnético multifase foi investigado. Este tipo de atuador pode ser utilizado em sistemas que requeiram movimento bidirecional sobre o plano como, por exemplo, em máquinas operatrizes industriais. O dispositivo em estudo possui uma armadura plana, estacionária, sem ranhuras e um carro com mobilidade planar. O núcleo da armadura é composto de uma chapa de material ferromagnético macio, em torno da qual estão montados os dois enrolamentos da armadura, que são ortogonais entre si. Cada enrolamento está dividido em seções ou fases. O carro, que possui dois ímãs permanentes de NdFeB de alto produto energético, está mecanicamente conectado a um sistema de suspensão, composto de rolamentos lineares e de trilhos, que permitem o seu deslocamento sobre a superfície da armadura, com dois graus de liberdade. Quando os ímãs permanentes estão localizados sobre as fases do enrolamento da armadura energizado com corrente, uma força eletromagnética planar de propulsão atuará sobre o carro, provocando seu deslocamento paralelamente à superfície da armadura. O atuador planar foi modelado analítica e teoricamente, com vistas a prever seu comportamento estático. O primeiro protótipo construído foi testado com a finalidade de avaliar suas características estáticas de funcionamento e de validar os modelos analítico e numérico. Os valores de densidade de fluxo no entreferro, de força normal e de força planar de propulsão, obtidos através dos ensaios, apresentaram uma boa aproximação em relação aos valores obtidos através dos modelos teóricos Tanto nos modelos teóricos, como no protótipo construído, foram avaliados dois casos distintos: no caso 1 foram utilizados no carro ímãs permanentes de 6,0 mm de comprimento axial e no caso 2, ímãs permanentes de 8,0 mm de comprimento axial. Os testes indicaram que a sensibilidade média do atuador planar para o caso 1 é de 3,61 N/A e para o caso 2 é de 5,37 N/A, quando as duas fases do enrolamento x localizadas sob os ímãs permanentes, foram percorridas por corrente.

Navegação exploratória baseada em problemas de valores de contorno

Este trabalho apresenta e discute uma estratégia e discute uma estratégia inédita para o problema de exploração e mapeamento de ambientes desconhecidos usandoo robô NOMAD 200. Esta estratégia tem como base a solução numéricqa de problemas de valores de contorno (PVC) e corresponde ao núcleo da arquitetura de controle do robô. Esta arquitetura é similar à arquitetura blackboard, comumente conhecida no campo da Inteligência Artificial, e é responsável pelo controle e gerenciamento das tarefas realizadas pelo robô através de um programa cleinte. Estas tarefas podem ser a exploração e o mapeamento de um ambiente desconhecido, o planejamento de caminhos baseado em um mapa previamente conhecido ou localização de um objeto no ambiente. Uma características marcante e importante é que embora estas tarefas pareçam diferentes, elas têm em comum o mesmo princípio: solução de problemas de valores de contorno. Para dar sustentabilidade a nossa proposta, a validamos através de inúmeros experimentos, realizados e simulação e diretamente no robô NOMAD 200, em diversos tipos de ambientes internos. Os ambientes testados variam desde labirintos formados por paredes ortogonais entre si até ambientes esparsos. Juntamente com isso, introduzimos ao longo do desenvolvimento desta tese uma série de melhorias que lidam com aspectos relacionados ao tempo de processamento do campo potencial oriundo do PVC e os ruídos inseridos na leitura dos sensores. Além disso, apresentamos um conjunto de idéias para trabalhos futuros.

Modelos estatísticos de segmentação da estrutura a Termo: testes empíricos de ajustes e previsões

Neste trabalho é proposta uma classe de modelos paramétricos para estrutura a termo de taxa de juros (ETTJ) em que diferentes segmentos possam ter características próprias, porém não independentes, o que é condizente com a teoria de preferências por Habitat. O modelo baseia-se em Bowsher & Meeks (2006) onde a curva é determinada por um spline cúbico nas yields latentes, mas difere no sentido de permitir diferentes funções de classe C2 entre os segmentos, ao invés de polinômios cúbicos. Em particular usa-se a especi cação de Nelson & Siegel, o que permite recuperar o modelo de Diebold & Li (2006) quando não há diferenciação entre os segmentos da curva. O modelo é testado na previsão da ETTJ americana, para diferentes maturidades da curva e horizontes de previsão, e os resultados fora da amostra são comparados aos modelos de referência nesta literatura. Adicionalmente é proposto um método para avaliar a robustez da capacidade preditiva do modelos. Ao considerar a métrica de erros quadráticos médios , os resultados são superiores à previsão dos modelos Random Walk e Diebold & Li, na maior parte das maturidades, para horizontes de 3, 6 , 9 e 12 meses.

A metodologia de análise de dados espaciais aplicada a plantas forrageiras

Dois experimentos e um levantamento por amostragem foram analisados no contexto de dados espaciais. Os experimentos foram delineados em blocos completos casualizados sendo que no experimento um (EXP 1) foram avaliados oito cultivares de trevo branco, sendo estudadas as variáveis Matéria Seca Total (MST) e Matéria Seca de Gramíneas (MSGRAM) e no experimento dois (EXP 2) 20 cultivares de espécies forrageiras, onde foi estudada a variável Percentagem de Implantação (%IMPL). As variáveis foram analisadas no contexto de modelos mistos, sendo modelada a variabilidade espacial através de semivariogramas exponencias, esféricos e gaussianos. Verificou-se uma diminuição em média de 19% e 14% do Coeficiente de Variação (CV) das medias dos cultivares, e uma diminuição em média de 24,6% e 33,3% nos erros padrões dos contrastes ortogonais propostos em MST e MSGRAM. No levantamento por amostragem, estudou-se a associação espacial em Aristida laevis (Nees) Kunth , Paspalum notatum Fl e Demodium incanum DC, amostrados em uma transecção fixa de quadros contiguos, a quatro tamanhos de unidades amostrais (0,1x0,1m; 0,1x0,3m; 0,1x0,5m; e 0,1x1,0m). Nas espécies Aristida laevis (Nees) Kunth e Paspalum notatum Fl, existiu um bom ajuste dos semivariogramas a tamanhos menores das unidades amostrais, diminuíndo quando a unidade amostral foi maior. Desmodium incanum DC apresentou comportamento contrario, ajustando melhor os semivariogramas a tamanhos maiores das unidades amostrais.

Projeto, construção e validação de transdutores para medição de esforços em semeadoras-adubadoras

A mecanização agrícola tem sido um importante fator que vem contribuindo para atender o aumento na demanda por alimentos. Porém, o desenvolvimento de máquinas e implementos com maior desempenho operacional ainda carecem de uma base de informações tecnológicas sistematizadas para a implementação em novos projetos de produtos. Desta forma, o principal objetivo deste trabalho foi o de implementar um sistema capaz de gerar informações para auxiliar no desenvolvimento de novos projetos de produtos, ou mesmo na melhoria das máquinas e implementos já existentes. Para tanto, foi construído um conjunto de transdutores de força – dinamômetros do tipo anel octogonal estendido, capazes de medir solicitações em duas direções ortogonais e o momento associado a estes dois esforços. Associados a estes transdutores foram utilizados outros recursos para a formação de uma instrumentação embarcada, a fim de possibilitar os registros, em tempo real, dos dados gerados para serem armazenados em bancos de dados para posterior análises e avaliações. Com o sistema implementado foram realizados diversos conjuntos de testes de campo, onde se ensaiou uma semeadora adubadora comercial com seus elementos ativos e/ou seus componentes isolados da máquina. No primeiro teste, foi avaliada uma linha completa de uma semeadora-adubadora, onde foram medidos os esforços no disco de corte da palha, na haste sulcadora para deposição do adubo e na unidade de semeadura. Nos testes seguintes, foram realizadas avaliações em dois modelos de hastes sulcadoras, trabalhando com diversos parâmetros distintos, a fim de comparar os respectivos desempenhos entre os dois modelos estudados. Também, verificaram-se avaliações das solicitações dos esforços de tração para sulcadores de adubo tipo disco duplo e, para tracionar somente os discos de corte. Finalmente, mediram-se os esforços para o arraste do chassi durante o deslocamento em campo. Os resultados dos sensores de força combinados com a instrumentação embarcada foram considerados satisfatórios durante as medições nos testes de campo, visto a sua repetibilidade tendo como referência um sistema de calibrações prévias. Desta forma, confirmouse que os registros dos testes de campo podem servir de referência para a análise de projeto de máquinas semeadoras-adubadoras, uma vez que os mesmos foram obtidos em condições reais durante as operações de campo.

Estudo experimental das características do escoamento turbulento nas primeiras fileiras de bancos de tubos

Este trabalho apresenta um estudo experimental das características do escoamento turbulento nas primeiras fileiras de bancos de tubos. São estudados os escoamentos sobre três geometrias de arranjos de tubos: dois tubos posicionados lado a lado normais ao escoamento, uma fileira de tubos transversal ao escoamento e bancos de tubos de configuração quadrangular, com três razões de espaçamento diferentes. O objetivo é entender o comportamento das instabilidades e fenômenos aleatórios e transientes que ocorrem nas primeiras fileiras de bancos de tubos e se propagam para o seu interior. Os resultados experimentais são obtidos através de medições em túnel de vento e visualizações em canal de água. Para a obtenção dos campos de velocidade é utilizada a técnica de anemometria de fio quente e para as medições de pressão é utilizado um transdutor de pressão piezo resistivo. Os dados experimentais obtidos são analisados por ferramentas estatísticas, espectrais e de ondaletas. As visualizações são feitas através da técnica de injeção de tinta diretamente no escoamento. Os resultados mostram a presença de instabilidades geradas a partir da segunda fileira do banco de tubos, que se propagam para o interior, gerando um comportamento onde as três componentes ortogonais do escoamento são igualmente importantes. O comportamento tridimensional do escoamento é responsável por uma redistribuição de massa dentro do banco de tubos que leva a valores de velocidade e números de Strouhal não esperados para a geometria estudada.