Orientador: João Meidanis / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-04T09:01:04Z (GMT). No. of bitstreams: 1 Quitzau_JoseAugustoAmgarten_M.pdf: 2854625 bytes, checksum: 4e3e9cbba583ca76e69b4835f14dd8db (MD5) Previous issue date: 2005 / Resumo: A relação evolutiva entre especies de seres vivos e normalmente representada atraves de um diagrama conhecido como arvore filogenetica. Embora existam inumeros metodos de construção deste tipo de diagrama, com base nos mais variados tipos de dados biologicos, nenhum deles garante obter a arvore que melhor representa a relação evolutiva entre as especies de um conjunto. Alguns metodos ainda podem produzir varias arvores distintas para um mesmo conjunto, sendo incapazes de decidir qual a que melhor explica a relação entre os seres representados. Cabe então aos biologos comparar as arvores e decidir qual a melhor entre elas. Uma maneira de estudar semelhanças entre arvores construidas sobre um mesmo conjunto de especies e a utilização de um consenso entre as arvores. Atualmente existem diversos metodos de consenso, cada um enfatizando características diferentes do conjunto de arvores. Esta dissertação destaca a possibilidade de uso de metodos de consenso como metodos de construção, apresentando um teste bastante simples que ressalta a qualidade das arvores consenso em relação a arvores criadas pelos metodos tradicionais de construção de arvores filogeneticas. Alem disso, apresenta um novo metodo de consenso focado não na comparação de arvores, mas na construção de uma arvore filogenetica capaz de se aproximar mais da arvore correta do que a maior parte das arvores presentes no conjunto utilizado para construi-la / Abstract: The evolutionary relationship between species is usually represented by a diagram known as phylogenetic tree. Despite of the existence of a huge number of different methods for building such a diagram, based on the most diverse sorts of biological data, none of these methods guarantees that the reconstructed tree is the tree which represents better the evolutionary relationship between the species in a given set. Some of the methods may even build different trees for the same input set of species. In these cases, they are unable to decide which of the trees represents better the relationship between the considered beings. In such cases, the task of comparing the produced trees and choosing the best one is left to biologists. One way to study the similarity of phylogenetic trees is to build a consensus between them. Nowadays there are different consensus methods, each of them exploring a different characteristic of the set of trees. This work focus on the possibility of use of consensus methods as reconstruction methods, presenting a very simple test, which points out the quality of consensus trees compared to trees built by traditional phylogeny reconstruction methods. After this, we present a consensus method dedicated to reconstructing trees, instead of just comparing them. We also show that trees built by this method are usually closer to the true tree than most trees used to build them / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Dados los avances en la tecnología, la astronomía es capaz de recolectar del orden de terabytes de datos por noche. El análisis manual de ésta es prácticamente imposible, por lo que es constante la necesidad de nuevos y mejores algoritmos para realizar análisis automático. Por otro lado, la computación paralela provee herramientas para realizar análisis de datos masivos, las que incrementan la capacidad total de procesamiento y disminuyen el tiempo requerido. Existe un software para la búsqueda de cúmulos de galaxias, el cual funciona de forma secuencial. Hacer que este software funcione en forma paralela sería de gran utilidad, dada la cantidad de datos que existen y existirán para analizar. El objetivo de esta memoria es diseñar e implementar una solución computacional que permita efectuar la detección de cúmulos de galaxias en forma paralela. La paralelización del algoritmo se hizo sobre el framework Hadoop, utilizando la herramienta Streaming con el lenguaje Python para el desarrollo del software. Se construyó una aplicación que divide los datos de entrada de forma inteligente, ejecuta el algoritmo de detección de cúmulos de galaxias en varias máquinas de forma paralela, y re ensambla los resultados parciales obtenidos. Se estudiaron estrategias para el particionamiento de los datos, utilizando celdas con distintas geometrías. También se estudiaron e implementaron estrategias para el re ensamblado de los resultados. En base a conocimientos astronómicos y experimentación se determinó la utilidad, dado el contexto, de cada estrategia, y los valores límites para sus parámetros. Los resultados son los siguientes: (1) un software paralelo para la detección de cúmulos de galaxias; (2) al correr el programa paralelo con dos particiones, el tiempo de ejecución se reduce a la mitad; (3) el software secuencial de detección de cúmulos se observa altamente dependiente de las particiones utilizadas, encontrándose para una partición de 2 celdas sólo un 11% de los cúmulos que se detectaban en la versión secuencial. Como trabajo futuro se propone: (1) modificar el software secuencial de búsqueda de cúmulos de galaxias para que detecte cúmulos sin miembros repetidos; (2) ejecutar este software en un clúster de computadores o con cloud computing, para medir las mejoras en tiempo; (3) la ejecución de este software con sets de datos más grandes, para medir la escalabilidad de éste; (4) crear una partición ad-hoc al set de datos.

Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadas / En este trabajo se estudia una versión en línea del problema de Cubrimiento de Máquinas Paralelas. En este problema buscamos asignar trabajos a una cierta cantidad de máquinas idénticas, maximizando la carga de la máquina menos cargada. En el problema en linea los trabajos son revelados uno a uno sucesivamente, y ante la llegada de cada trabajo el programador debe decidir a qué máquina asignar el trabajo. A diferencia del modelo clásico, donde las decisiones son irrevocables, se considera un modelo dinámico introducido por Sanders et al. \cite{SSS09}. En este modelo, ante la llegada de un trabajo nuevo, algunos trabajos anteriores pueden ser reasignados. Sin embargo la carga total de trabajos migrados debe ser a lo más proporcional al tamaño del trabajo entrante. La constante de proporcionalidad se denomina \emph{factor de migración} del algoritmo, y mide la robustez de las soluciones construidas. En primer lugar se estudian algoritmos de búsqueda local, ya que gran parte de estos algoritmos pueden ser adaptados de manera sencilla al contexto en línea con migración. Se demuestra que para la vecindad de \emph{Saltos} e \emph{Intercambios}, el factor de aproximación de una solución localmente óptima yace en el intervalo $[1.691, 1.723]$. Además, usando técnicas de sensibilidad para programación entera, se da una vecindad para la cual las soluciones localmente óptimas son $(1+\e)$-aproximadas y pueden ser halladas en una cantidad polinomial de iteraciones, obteniéndose un PTAS basado exclusivamente en búsqueda local. Posteriormente se analizan y diseñan algoritmos para el problema en línea con migración. El primer resultado es una mejora en la cota inferior del factor de competitividad alcanzable con migración constante de $\frac{20}{19}$ obtenida por Skutella y Verschae \cite{SV10} a $\frac{17}{16}$. Luego, utilizando un procedimiento de redondeo para la instancia distinto al usado en trabajos anteriores, denominado redondeo a múltiplos, se diseña una versión en línea de optimalidad local respecto a saltos con factor de migración $O\left(\frac{1}{\e}\log\frac{1}{\e}\right)$. Modificando esta propiedad levemente, se obtiene un algoritmo $\left(\frac{3}{2} + \e\right)$-competitivo usando factor de migración $O\left(\frac{1}{\e}\log\frac{1}{\e}\right)$. Finalmente, explotando la simetría otorgada por el redondeo a múltiplos, se diseña una versión en línea de $\LPT$, que es una $(\frac{4}{3}+\e)$-aproximación para el problema de Cubrimiento de Máquinas, con factor de migración $O\left(\frac{1}{\e^3}\log\frac{1}{\e}\right)$. Usando la intuición generada por esta simetría junto a las técnicas de programación entera y \emph{configuraciones} de máquinas, se obtiene un nuevo programa entero para el problema que es más simple y abre las puertas a obtener un PTAS para el problema de Minimización de Makespan en línea cuyo factor de migración tenga dependencia polinomial en $\frac{1}{\e}$, lo que aún es un problema abierto.

Magíster en Gestión de Operaciones / Dada una colección de ciudades y el costo de viajar entre cualquier par de ella, el problema del vendedor viajero, que denotaremos como TSP (traveling salesman problem en inglés), consiste en encontrar el tour menos costoso que visita todas las ciudades al menos una vez retornando al punto inicial. En su forma métrica este problema es NP-duro, y por lo tanto no existe un algoritmo en tiempo polinomial que lo resuelva, salvo que P=NP. Para el caso métrico, Christofides diseñó en el año 1976 un 3/2-algoritmo de aproximación, el cual despertó una gran curiosidad con respecto a la aproximabilidad del problema. Sin embargo, y pese a los grandes esfuerzos efectuados en investigación, el algoritmo de Christofides es el de mejor garantía hasta el día de hoy. Recientemente han habido varios mejoras importantes con respecto a la aproximabilidad en casos especiales de TSP métrico. En el año 2011 Oveis Gharan et al. diseñaron un (3/2-ε)-algoritmo de aproximación para el caso graph-TSP, donde la distancia métrica entre cada par de ciudades está dada por el menor número de arcos necesarios para conectarlas por un camino dentro de un grafo sin pesos. En el mismo año Mömke y Svensson mejoran el resultado a 1.461, mientras Mucha en el 2012 mejora la garantía del algoritmo a 13/9. En el caso de que el grafo es cúbico de n vértices y 2-conexo, el algoritmo de Mömke y Svensson entrega un tour de largo menor a (4/3)n, resultado obtenido también por Boyd et al. en el año 2011. En este trabajo estudiamos el problema graph-TSP en distintas variantes de grafos cúbicos. Primero estudiamos el caso en que el grafo es planar, cúbico, bipartito y 3-conexo, el cual es un caso interesante desde el punto de vista de teoría de grafos ya que, según la conjetura de Barnette de hace más de 40 años estos grafos serían Hamiltonianos. En esta clase de grafos, conocidos como grafos de Barnette, mostramos que en un grafo de n vértices existe un tour de largo a lo más (4/3-1/18)n. Luego relajamos las condiciones sobre el grafo, quitando la hipótesis de planaridad e imponiendo que sea cúbico, bipartito y 2-conexo, caso en el cual mostramos que existe un tour de largo a lo más (4/3-1/108)n. Finalmente, estudiamos el caso en que el grafo es solamente cúbico y 2-conexo. En este caso nos basamos en las técnicas de Boyd et al. para mostrar que existe un tour de largo a lo más (4/3-1/61236)n. En cada caso mostramos que el tour se puede encontrar en tiempo polinomial, y como n es naturalmente una cota inferior del valor de graph-TSP, cada uno de los resultados obtenidos se traduce en un algoritmo de aproximación. Además, como n es una cota inferior de la relajación de Held & Karp, que es una conocida formulación para TSP como programa lineal, obtenemos como consecuencia que el gap de integralidad de TSP con respecto a esta relajación es acotado superiormente por (4/3-1/18) para el caso de Barnette, (4/3-1/108) para el caso cúbico, bipartito y 2-conexo, y (4/3-1/61236) para el caso cúbico y 2-conexo.

Orientador: Douglas Eduardo Zampieri / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Mecanica / Made available in DSpace on 2018-07-13T22:00:49Z (GMT). No. of bitstreams: 1 Heuberger_CarlosFlorian_M.pdf: 1946496 bytes, checksum: f93c90df350c4163c0b11544703eab99 (MD5) Previous issue date: 1990 / Resumo: Neste trabalho propõe-se um algoritmo para a determinação automática de caminhos para um manipulador com duas juntas rotacionais, na presença de obstáculos conhecidos e fixos. A detecção de colisão é simplificada tranformando-se os obstáculos para o espaço de configuração do manipulador. A determinação do caminho consiste então, em achar a linha de menor comprimento no espaço de configuração, ligando os pontos referentes às posições inicial e final, evitando as regiões de colisão. Esta linha serádeterminada pelo algoritmo de procura em grafos A *, que sempre encontra o caminho ótima segundo um critério adotado, neste caso, o de menor movimento das juntas. O simulador foi implementado em um computador compatível ao IBM AT, permitindo a apresentação de resultados práticos / Abstract: A method for automatically planning a path for a two link manipulator in the presence of fixed and known obstacles is presented. The transformation of the Cartesian workspace into the manipulator joint coordinates (configuration maps) simplify the colision detection. 80 the find-path problem is solved finding the shortest line which connects starting and final manipulator configurations in this map without traversing a colision region. The graph-search A * algorithm is used to calculate this line because it always finds the optimal path, which we define as being the one with the least joint movement. To show some paths obtained by this method, a simulator was implemented on an IBM AT / Mestrado / Mestre em Engenharia Mecânica

Orientador: Hermano Medeiros Ferreira Tavares / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia / Made available in DSpace on 2018-07-15T13:06:39Z (GMT). No. of bitstreams: 1 Souza_CarlosRodriguesde_M.pdf: 2041617 bytes, checksum: daca38d2468e7ace0fd34682817c19ac (MD5) Previous issue date: 1977 / Resumo: Algoritmos de programação linear e de programação linear por partes foram preparados para a aplicação em alguns aspectos do planejamento da expansão dos sistemas de potência e, no que diz respeito a operação desses sistemas, em remanejamento de geração de potência ativa associado, quando neces¬sário, a corte nas demandas (load shedding) ou à utilização da inércia térmica das linhas de transmissão, visando obter um modo de operação satisfatório / Abstract: Upper bounded variables linear programming and piecewise linear programming algorithms have been prepared for application in some system planning aspects and for use in real power generation rescheduling related, if necessary, to load shedding or to the utilization of heat capacity of some transmission lines in order to get to a satisfactory operating condition / Mestrado / Mestre em Engenharia Elétrica

Orientador: Secundino Soares Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia de Campinas / Made available in DSpace on 2018-07-16T08:48:51Z (GMT). No. of bitstreams: 1 Ohishi_Takaaki_M.pdf: 3691965 bytes, checksum: 62773bcad5de67c388043d7119f0c5e2 (MD5) Previous issue date: 1981 / Resumo: Um problema clássico em sistemas de potência é a alocação da geração entre as diversas unidades geradoras. Muitas abordagens têm sido sugeridas nos anos recentes, tais como os métodos variacionais, programação dinâmica, princípio de máximo de Pontryagin, técnicas de programação matemática em geral, e técnicas de decomposição e coordenação. Na área de Sistema do Departamento de Engenharia Elétrica da FEC - UNICAMP tem-se pesquisado nos últimos anos a resolução deste utilizando-se técnicas de programação matemática, programação dinâmica e técnicas de decomposição e coordenação. Este trabalho apresenta um estudo de uma proposta de resolução através de técnicas de decomposição e coordenação. Desenvolve-se um algoritmo para a sua implementação computacional e apresenta a resolução de três sistemas hidroelétricos hipotéticos. Faz-se também uma discussão da variação na configuração das usinas hidroelétricas a serem consideradas na otimização em função do horizonte de otimização. / Abstract: Not informed. / Mestrado / Mestre em Engenharia Elétrica

Orientador: Jose Mario Martinez / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica / Made available in DSpace on 2018-07-16T15:26:50Z (GMT). No. of bitstreams: 1 Santos_RitaFilomenaAlvesdos_M.pdf: 978640 bytes, checksum: 2e2df1568dc14b0909895f5db851f895 (MD5) Previous issue date: 1989 / Resumo: Não informado. / Abstract: Not informed. / Mestrado / Mestre em Matemática Aplicada

Orientador: Walter de Lazaro / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia de Campinas / Made available in DSpace on 2018-07-17T00:23:33Z (GMT). No. of bitstreams: 1 Yamakami_Akebo_D.pdf: 2084670 bytes, checksum: db9f26d6a2d936c43b2d57b704184b48 (MD5) Previous issue date: 1977 / Resumo: Este trabalho tem como objetivo estudar os modelos mais conhecidos de alocação de viagens. São estudadas as principais variáveis envolvidas nos problemas de alocação de viagens, como também são desenvolvidos algoritmos de procura de caminhos mínimos que consideram as penalizações de conversão. São feitas as formulações matemáticas dos problemas de alocação de viagens que verificam os princípios de Wardrop, e são apresentados diversos métodos de alocação, tanto iterativos como de carregamento progressivo, derivados do princípio "egoísta". É apresentado também o modelo probabilístico desenvolvido por R.B. Dia1. São feitas aplicações dos modelos a uma rede não saturada da região de Augusta da cidade de são Paulo, e a uma rede hipotética saturada. Frente aos resultados obtidos os algoritmos de alocação de viagens e os algoritmos de procura de caminhos mínimos que consideram as penalizações de conversão são ana1izados e comparados. / Abstract: Not informed. / Doutorado / Doutor em Engenharia Elétrica

Orientador : Manuel de Jesus Mendes / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia de Campinas / Made available in DSpace on 2018-07-17T02:00:38Z (GMT). No. of bitstreams: 1 Bruno_PaulodeTarsoMartins_M.pdf: 1851397 bytes, checksum: e4163e65201b889c962b8fe6046de839 (MD5) Previous issue date: 1976 / Resumo: O problema da estimação do estado de um sistema dinâmico estocásticos, a partir de observações na saída, é de grande importância em engenharia. A partir de 1960 grandes impulso tem sido dado na solução das mais diferentes situações, encontrando-se atualmente grande serie de algoritmos de filtragem seqüencial. No presente trabalho estudam-se os quatro filtros de segunda ordem citados na literatura, analisando suas vantagens e desvantagens na aplicação a um sistema escalar; um desses algoritmos é aplicado a um problema pra tico e os resultados são comentados / Abstract: Not informed / Mestrado / Mestre em Engenharia Elétrica