Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-02-13T14:54:34Z No. of bitstreams: 2 Dissertação - Jhones C. Coelho.pdf: 3503211 bytes, checksum: 4de205e9176e97055216984a347c55ef (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-02-13T14:55:02Z (GMT) No. of bitstreams: 2 Dissertação - Jhones C. Coelho.pdf: 3503211 bytes, checksum: 4de205e9176e97055216984a347c55ef (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-09-21T18:18:45Z (GMT) No. of bitstreams: 2 Dissertação - Jhones C. Coelho.pdf: 3503211 bytes, checksum: 4de205e9176e97055216984a347c55ef (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-09-21T18:18:45Z (GMT). No. of bitstreams: 2 Dissertação - Jhones C. Coelho.pdf: 3503211 bytes, checksum: 4de205e9176e97055216984a347c55ef (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2016-12-15 / Given a set of points on the plane, we call terminals or regular points, it proves that there is always a minimum tree that connects called "Steiner tree". The terminals may represent hubs to routes, circuit elements, or different networks. That is, the problem in question is to optimize to communication between terminals, if this is represented by a tree of shortest length possible. Not always the "shorter"is optimization. Steiner problem has variations, for example, the tree can only follow the edges of the horizontal and vertical directions, as in the case of electrical circuits. Another variation is when each Steiner point is very expensive, and it is intended to obtain such a tree with the lowest number of such points. It will be "local minimum"for length, but not necessarily globally. A physical and quite simple model for "Steiner tree"is that it can also be performed by soap films, and therefore share minimum surface properties. As an example, consider a soap solution. Getting closer and withdraw two parallel plates connected by pins, a film will connect them. This represents a minimum length graph that interconnects the pins. As is known, the soap films perform the Minimal Surfaces. To view a "Steiner tree"refers to Numerical Algorithms and Graphical Programming, methods are mainly based on the implementation of the algorithms. This present work is divided into three parts: a brief history of optimization problems, highlighted the Steiner problem; theory of the Minimum Tre or Steiner tree and algorithm Melzak; some examples of real cases. / Dado um conjunto de pontos no plano, que denominamos terminais ou pontos regulares, provase que sempre existe uma árvore mínima que os conecta, chamado "árvore de Steiner". Os terminais podem representar centros de conexão para rotas, elementos de circuito elétrico, ou de redes diversas. Ou seja, o problema em questão é otimizar a comunicação entre os terminais, caso isto seja representado por uma árvore de menor comprimento possível. Nem sempre o "menor comprimento"representa a otimização. O Problema de Steiner possui variações, por exemplo, em que as arestas da árvore só podem seguir direções horizontal e vertical, como no caso de circuitos elétricos. Outra variação é quando cada ponto Steiner tem custo muito alto, e pretende-se obter uma tal árvore com o menor número de tais pontos. Ela será "mínimo local"para comprimento, mas não necessariamente global. Um modelo físico e bastante simples para "árvore de Steiner"é que ela pode ser também realizada por películas de sabão, e por isso compartilham propriedades de Superfícies Mínimas. Como exemplo, considere uma solução de sabão. Ao mergulharmos e retirarmos duas placas paralelas ligadas por pinos, uma película irá conectá-los. Esta representa um grafo de comprimento mínimo que interliga os pinos. Como é sabido, as películas de sabão realizam as Superfícies Mínimas. Para visualizar uma "Árvore de Steiner", recorre-se a Algoritmos Numéricos e Programação Gráfica, os métodos baseiam-se principalmente na implementação dos algoritmos. Este presente trabalho está dividido em três partes: breve história dos problemas de otimização, em destaque o problema de Steiner; teoria sobre a Árvore Mínima ou Árvore de Steiner e o Algoritmo de Melzak; alguns exemplos de casos reais.

Submitted by Inês Marinho (bele_ballet@hotmail.com) on 2016-06-20T13:59:26Z No. of bitstreams: 1 Dissertação - Emory Raphael Viana Freitas.pdf: 2084938 bytes, checksum: a6977ea5e3936400c82912e9bafb06ee (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2016-06-23T18:46:40Z (GMT) No. of bitstreams: 1 Dissertação - Emory Raphael Viana Freitas.pdf: 2084938 bytes, checksum: a6977ea5e3936400c82912e9bafb06ee (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2016-06-23T18:47:58Z (GMT) No. of bitstreams: 1 Dissertação - Emory Raphael Viana Freitas.pdf: 2084938 bytes, checksum: a6977ea5e3936400c82912e9bafb06ee (MD5) / Made available in DSpace on 2016-06-23T18:47:58Z (GMT). No. of bitstreams: 1 Dissertação - Emory Raphael Viana Freitas.pdf: 2084938 bytes, checksum: a6977ea5e3936400c82912e9bafb06ee (MD5) Previous issue date: 2015-03-20 / FAPEAM - Fundação de Amparo á Pesquisa do Estado do Amazonas / Planning a trajectory that consider limitations of aircraft maneuvers is an important feature of any Mission Planner. The complexity increases in the presence of multiple aircraft and scenarios with multiple targets. The problem how to decide the number of aircraft launched in order to efficiently cover all necessary points creates an interesting problem to be studied. Runtime mission, resources, and the number of vehicles to be launched are all minimized the Same time. The problem then becomes increasingly critical, when the scenario mission does not allow the aircraft back off or re-plan the path, and the flight plan onboard on autopilot Air Vehicle Unmanned (UAV) probably It will be the last in the case of failure. One of these application scenarios is monitoring both air of a region not explored the Amazon rainforest. The extent of forest, the complete lack of access to its interior and uniform standards of treetops define a mission without success usually means total loss of equipment. In such situations, careful planning for each vehicle is a factor critical to the overall success of the mission. A common problem is to consider limitations side manobas when the route is planned. Although a human pilot can act to radically change the direction of the path, when we consider UAVs, limiting abrupt actions is recommended because without it you can add a instability in both the laterals and longitudinal controls. Therefore, when planning the trajectory, it is desirable that the points that define consectivos a curve with acceptable angles, and acceptance related to the dynamics of aircraft. Another common problem is how to balance the mission runtime Large areas squadron in hazardous areas. This paper presents an approach based on Genetic Algorithms (GA) to solve the routing problem Vehicle (PRV) for multiple UAVs conducting a monitoring mission multiple points in a formulation bi criteria: minimize the amount vehicles air, while the mission time is minimized. / O planejamento de uma trajetória que considere limitações de manobras da aeronave é uma característica importante de qualquer Planejador de Missão. A complexidade aumenta na presença de múltiplas aeronaves e cenários com múltiplos alvos. O problema em como decidir o número de aeronaves lançadas afim de cobrir eficientemente todos os pontos necessários cria um problema interessante para ser estudado. Tempo de execução da missão, recursos, e o número de veículos a ser lançados são todos minimizados ao mesmo tempo. O problema então torna-se cada vez mais crítico, quando o cenário da missão não permite que a aeronave recue ou re-planeje a trajetória, e o plano de voo embarcado no piloto automático do Veículo Aéreo Não-Tripulado (VANT)provavelmente será o último no caso de falha. Um destes cenários de aplicação é o monitoriamento aéreo de uma região não explorada da Floresta Amazônica. A extensão da floresta, a completa falta de acesso ao seu interior e padrões uniformes da copa das árvores definem que uma missão sem sucesso, significa geralmente a perda total do equipamento. Em tais situações, um planejamento cuidadoso para cada veículos é um fator crítico para o sucesso total da missão. Um problema comum é considerar limitações de manobas laterais quando a rota está sendo planejada. Embora um piloto humano possa agir de forma a trocar radicalmente a direção da trajetória, quando consideramos VANTs, é recomendável a limitação de ações bruscas, pois sem isto pode adicionar uma instabilidade em ambos os controles laterias e longitudinais. Portanto, ao planejar a trajetória, é desejável que os pontos consectivos que definem uma curva com ângulos aceitáveis,sendo aceitação relacionada com a dinâmica da aeronave. Outro problema comum é como balancear o tempo de execução da missão em grandes aréas a esquadrilha em aréas perigosas. Este trabalho apresenta um abordagem baseada em Algoritmos Genéticos (AG) para resolver o Problema de Roteamento de Veículos( PRV) para multiplos VANTs realizando uma missão de monitoramento de múltiplos pontos, em uma formulação bi critério: minimizar a quantidade veículos no ar, enquanto o tempo de missão é minimizado.

Este trabalho apresenta a técnica de Algoritmo Genético para apoiar o processo de modelagem e simulação de sistemas complexos. Tal técnica pode ser vista como uma opção as técnicas tradicionais de modelagem e análise dos dados de simulação, simplificando todo esse processo, por suas características de simplicidade e generalidade, não exigindo conhecimento especifico do domínio do problema. É apresentada uma ferramenta computacional - SimAG - baseada em Algoritmo Genético para modelagem e simulação de sistemas dessa natureza. Um exemplo de aplicação e estudado, onde pode ser constatada a viabilidade da utilização da técnica no processo de simulação / This work presents the Genetic Algorithm technique supporting the process of complex systems modeling and simulation. Such technique can be seen as an option to both the traditional modeling and the simulation data analysis techniques. Due to its inherent simplicity and generic application, it simplifies the whole process of simulation, demanding no specific knowledge over the problem domain. A genetic algorithm based computational tool - SimAG - for the modeling and simulation of such systems is here presented, and an example of its use is analyzed, thus demonstrating the feasibility of this new technique application in simulation processes

[pt] Este trabalho está dividido em duas partes. A primeira parte trata das relações entre o problema de otimização d.c. (diferença de duas funções convexas) e o problema de otimização d.c. regularizado por inf-convolução, com núcleo (2 lambda)-1 l l . l l 2 , lambda > 0. Neste sentido se generaliza a relação de TOLAND (1979): inf { g(x) - h(x) } = inf { h(asterístico (y) - g (asterístico(y) }, H H E a relação de GABAY (1982): inf { g(x) - h(x) } = inf { g lambda (x) - h lambda (x) } H H Onde g, h , são funções convexas próprias e semicontínuas inferiormente, g(asterístico), h(asterístico), são conjugadas de g e h, respectivamente, H é um espaço de Hilbert real, e g (lambda), h lambda , são as funções regularizadas respectivas de g e h, por inf-convolução com núcleo (2 lambda)-1 l l . l l 2 , lambda > 0. A segunda parte deste trabalho apresenta um algoritmo novo para tratar com o problema de otimização d.c.. Trata-se de um método de descida do tipo proximal, onde se leva em consideração separadamente as propriedades de convexidade das duas funções convexas. / [en] The work is divided in two parts. The first part is concerned with the relationship between the d.c. optimization problem. In this sence we geralize the TOLAND´s relation (1979): inf { g(x) - h(x) } = inf { h(asteristic)(y) - g (asteristic)(y) }, H H And the GABAY´s relation (1982): inf { g(x) - h(x) } = inf { g lambda (x) - h lambda (x) } H H Where g, h, are l.s.c. convex functions, g(asteristic) and h(asteristic) are their conjugates, H is a real Hilbert space, and g lambda, h lambda, are the inf-convolution of g and h respectively, with the núcleos 8( . ) = (2 lambda)- 1 l l . l l 2 , lambda > 0. In the second part we present a new algorithm for dealing with d.c. functions. It is a descent method of proximal kind which takes in consideration the convex properties of the two convex functions separately

[pt] Apresenta-se nesta dissertação um novo algoritmo para o cálculo de algumas funções distância entre polígonos convexos, no caso geral em que os polígonos podem se interseptar, cuja complexidade linear de pior caso é melhor do que a dos algoritmos até então conhecidos na literatura. O algoritmo é baseado em um algoritmo de complexidade linear originalmente proposto para determinação da distância de Hausdorff entre polígonos convexos disjuntos e utiliza como sua principal componente um algoritmo linear para o cálculo da interseção entre polígonos convexos. A motivação para o estudo de algoritmos eficientes para este problema de cálculo de distâncias decorre de aplicações em reconhecimento de formas e superposição ótima de contornos. Resultados computacionais também são apresentados. / [en] We present in this dissertation a new algorithm for the computation of some distance functions between convex polygons, in the general case where they can intersect, whose worst case time complexity is better than of the previously known algorithms. The algorthm is based on an algorithm originally proposed for the computation of the Hausdorff distance between disjoint polygons and uses as its main component a linear time algorithm for finding the intersection of convex polygons. The motivation for the study of efficient algorithms for this distance computation problem comes from applications in pattern recognition and contour fitting. Computatioal results are also presented.

[pt] Este trabalho é composto do projeto e implementação de um sistema gráfico para uso em microcomputadores do tipo IBM PC visando aplicações em CDA, animação e processamento de imagens. Com várias configurações programáveis destaca-se a capacidade do uso de altas resoluções e grande número de cores, podendo chegar a 16 milhões. Todo o processamento é feito por um microprocessador RISC, o que se traduz em alto desempenho e grande flexibilidade na execução de rotinas e algoritmos gráficos. / [en] The contents of this work are the Project and implementation of a graphic system for IBM PC microcomputers for use in CAD, animation, and image processing. Among its features stand out the display resolution and up to 16 million colors. All the processing are made by a RISC microprocessor, leading to a high performance and great flexibility in routine and graphics algorithm execution.

Doctor en Sistemas de Ingeniería / En este trabajo se estudia la calidad que ofrecen las soluciones óptimas locales para problemas de programación de tareas en máquinas en paralelo. Los ambientes considerados son máquinas idénticas, idénticas restringidas, uniformes restringidas y no-relacionadas. El objetivo considerado es la minimización del tiempo ponderado de completación. Para estudiar la calidad de los óptimos locales se determinan los factores de aproximación para las soluciones localmente óptimas de los vecindarios de inserción (jump) e intercambio (swap). Los resultados indican que para los ambientes de máquinas paralelas uniformes y no-relacionadas, el costo de cualquier óptimo local se encuentra alejado a lo más en un factor 2,618 con respecto al costo del óptimo. Si solo se considera la minimización del tiempo de completación, se tiene que el factor es 2. El mismo resultado se obtuvo para el ambiente de máquinas uniformes con tareas unitarias, para los casos ponderado y no ponderado. Por otra parte, para el problema de máquinas paralelas idénticas restringidas, se determinó que el factor de aproximación se encuentra entre 1,75 y 1,809. Para el caso no ponderado este factor se encuentra entre 1,5333 y 1,618. Para el caso de tareas unitarias, donde el objetivo es la minimización del tiempo ponderado de completación, se determinó que el factor de aproximación se encuentra entre 1,5333 y 1,618. Mientras que para el caso no ponderado se tienen evidencias que indican que el factor de aproximación es 1,5333. / Este trabajo ha sido parcialmente financiado por Universidad del Bío-Bío; Conicyt, Programa de Formación de Capital Humano Avanzado; Núcleo Milenio Información y Coordinación en Redes

Ingeniero Civil Eléctrico / En tiempos modernos la envergadura del contenido multimedia avanza más rápido que el desarrollo de las tecnologías necesarias para su correcta difusión a través de la red. Es por esto que se hacen necesarios nuevos protocolos que sirvan como puente entre ambas entidades para así obtener un máximo de provecho del contenido a pesar de que la tecnología para distribuirlos aún no sea la adecuada. Es así, que dentro de las últimas tecnologías de compresión de video se encuentra Scalable Video Coding (SVC), la cual tiene por objetivo codi car distintas calidades en un único bitstream capaz de mostrar cualquiera de las calidades embebidas en éste según se reciba o no toda la información. En el caso de una conexión del tipo streaming, en donde es necesaria una uidez y delidad en ambos extremos, la tecnología SVC tiene un potencial muy grande respecto de descartar un mínimo de información para privilegiar la uidez de la transmisión. El software utilizado para la creación y manipulación de estos bitstreams SVC es Joint Scalable Video Model (JSVM). En este contexto, se desarrolla el algoritmo de deadline en Matlab, que omite informaci ón del video SVC de acuerdo a qué tan crítico sea el escenario de transmisión. En este escenario se considera la percepción de uidez del usuario como medida clave, por lo cual se prioriza mantener siempre una tasa de 30 fps a costa de una pérdida de calidad mínima. El algoritmo, omite información de acuerdo a qué tan lejos se esté de este deadline de 30 fps, si se está muy lejos, se omite información poco relevante, y si se está muy cerca, información más importante. Los resultados se contrastan con TCP y se evalúan para distintos valores de RTTs, cumpliendo totalmente el objetivo para valores menores a 150 ms que resultan en diferencias de hasta 20 s a favor del algoritmo de deadline al término de la transmisión. Esta mejora en tiempo de arribo no descarta información esencial y sólo degrada ligeramente la calidad del video en pos de mantener la tasa de 30fps. Por el contrario, en escenarios muy adversos de 300 ms en RTT, las omisiones son de gran envergadura y comprometen frames completos, en conjunto con una degradación generalizada del video y la aparición de artefactos en éste. Por tanto la propuesta cumple los objetivos en ambientes no muy adversos. Para toda la simulación se uso un video en movimiento de 352x288 y 150 frames de largo.

O problema de roteamento de dados em rede de computadores consiste em minimizar o tempo médio de atraso na transmissão de mensagens, escolhendo para elas um caminho ótimo, através dos arcos da rede. Em seu trabalho, Luvezute propôs um algoritmo primai de relaxamento para otimizar o problema de roteamento de dados. O algoritmo proposto por Luvezute resolve iterativamente o problema de multifluxo, decompondo-o da forma mais independente possível, em subproblemas de simples fluxo, sendo um subproblema para cada mensagem. Esta independência entre os cálculos permite que a resolução dos subproblemas seja simultânea, admitindo-se assim uma implementação em paralelo. Nesta dissertação apresentamos um algoritmo paralelo, do tipo Fase I para encontrar uma solução inicial factível para o problema de multifluxo. Este algoritmo permite resolver de maneira mais rápida os problemas de grande porte que é o nosso objetivo inicial. O algoritmo de Fase I aqui desenvolvido pode ser utilizado para problemas de Multifluxo em geral, isto é, problemas com função objetivo linear ou não linear. O algoritmo desenvolvido foi escrito em linguagem C e implementado numa rede de microcomputadores, usando o sistema operacional UNIX. Além dos testes computacionais, apresentamos uma análise da eficiência do algoritmo e do seu speedup. / In this thesis a parallel algorithm is presented to find a feasible initial solution for the routing problem. The optimal routing in packet-switched networks consists of minimizing the medium delay time in the transmission of messages. This problem belongs to the class of multicommodity network flow problems. The developed algorithm can be used to solve multicommodity network flow problems with linear or nonlinear objective function. It solves, in fast way, problems of great size. The algorithm was written in C language and implemented in the computers network. The operating system UNIX was used. They are presented experimental results, and an analysis of the efficiency and the speedup.

Segundo uma pesquisa recente realizada junto ao setor de fundições, uma importante preocupação do setor é melhorar seu planejamento de produção. Um plano de produção em uma fundição envolve duas etapas interdependentes: a determinação das ligas a serem fundidas e dos lotes que serão produzidos. Neste trabalho, estudamos o problema de dimensionamento de lotes para fundições de pequeno porte, cujo objetivo é determinar um plano de produção de mínimo custo. Como sugerido na literatura, a heurística proposta trata as etapas do problema de forma hierárquica: inicialmente são definidas as ligas e, posteriormente, os lotes que são produzidos a partir delas. Para a solução do problema, propomos um algoritmo genético que explora um conjunto de possibilidades para a determinação das ligas e utiliza uma heurística baseada em relaxação lagrangiana para determinação dos itens a serem produzidos. Além disso, uma abordagem para o mesmo problema é proposta utilizando o problema da mochila para determinar os itens a serem produzidos. Bons resultados foram obtidos pelos métodos propostos / According to a recent research made by the foundry sector, one of the most concern of the industry is to improve its production planning. A foundry production plan involves two independent stages: the determination of alloys to be merged and the lots that will be produced. In this work, we studied the lot-sizing problem for small foundries, whose purpose is to determine a plan of minimum production cost. As suggested in the literature, the heuristic proposed addresses the problem stages in a hierarchical way: rst we dene the alloys and, subsequently, the lots that are produced from them. We propose a genetic algorithm that explores some possible sets of alloys produced and uses a Lagrangian heuristic to determine the items to be produced. Also, we propose one approach to the same problem that uses the knapsack problem to determine the items to be produced. Good results were obtained by the methods proposed