[pt] Uma filogenia é uma árvore que relaciona unidades taxonômicas, baseada na similaridade de seus conjuntos de características. O problema da filogenia consiste em encontrar uma filogenia com o número mínimo de passos evolutivos. O principal objetivo deste trabalho é desenvolver heurísticas híbridas para este problema. Duas estratégias são propostas. A primeira combina a metaheurística GRASP baseada em uma nova estrutura de vizinhança (k-SPR) proposta neste trabalho com um procedimento VND de busca local. A segunda estratégia híbrida combina algoritmos genéticos com uma estratégia de cruzamento inovadora, a qual é uma extensão da técnica de intensificação denominada reconexão por caminhos que foi originalmente aplicada no contexto de outras metaheurísticas, tais como busca tabu e GRASP. Os experimentos computacionais realizados sobre instâncias geradas aleatoriamente e instâncias da literatura científica mostram que os novos algoritmos são bastante robustos e que superaram os outros algoritmos existentes na literatura em termos de qualidade de solução e tempos computacionais obtidos. / [en] A phylogeny is a tree that relates taxonomic units, based on their similarities over a set of characters. The phylogeny problem consists in finding a phylogeny with the minimum number of evolutionary steps. The main goal of this work is to develop hybrid heuristics for this problem. Two strategies are proposed. The first combines the GRASP metaheuristic using a new neighborhood structure (k-SPR) proposed in this work with a VND local search procedure. The second hybrid strategy combines genetic algorithms with an innovative optimized crossover strategy which is an extension of the path-relinking intensification technique originally applied in the context of other metaheuristics such as tabu search and GRASP. Computational results on randomly generated and benchmark instances are reported, showing that the new heuristics are quite robust and outperform the others algorithms in the literature in terms of solution quality and computational time.

[pt] Nesta dissertação é apresentado um framework para desenvolver critérios de split para lidar com atributos nominais multi-valorados em árvores de decisão. Critérios gerados por este framework podem ser implementados para rodar em tempo polinomial no número de classes e valores, com garantia teórica de produzir um split próximo do ótimo. Apresenta-se também um estudo experimental, utilizando datasets reais, onde o tempo de execução e acurácia de métodos oriundos do framework são avaliados. / [en] In this dissertation we propose a framework for designing splitting criteria for handling multi-valued nominal attributes for decision trees. Criteria derived from our framework can be implemented to run in polynomial time in the number of classes and values, with theoretical guarantee of producing a split that is close to the optimal one. We also present an experimental study, using real datasets, where the running time and accuracy of the methods obtained from the framework are evaluated.

[pt] Estudamos aproximações amostrais de problemas com restrições probabilísticas através da aproximação pela média amostral (SAA) e demonstramos as propriedades de convergência relacionadas. Utilizamos SAA para obter bons candidatos à solução e cotas estatísticas para o valor ótimo do problema original. Para ajustar corretamente parâmetros, aplicamos o método a dois problemas com restrições probabilísticas. O primeiro é um problema de seleção de portfolio linear com retornos seguindo uma distribuição lognormal multivariada. O segundo é uma versão com restrições probabilísticas conjuntas de um problema da mistura simplificado. Concluímos com uma aplicação mais exigente ao problema de se determinar a provisão mínima que um agente econômico deve ter de forma a satisfazer uma série de obrigações futuras com probabilidade suficientemente alta. / [en] We study sample approximations of chance constrained problems through the sample average approximation (SAA) approach and prove the related convergence properties. We discuss how to use the SAA method to obtain good candidate solutions and bounds for the optimal value of the original problem. In order to tune the parameters of SAA, we apply the method to two chance constrained problems. The first is a linear portfolio selection problem with returns following a multivariate lognormal distribution. The second is a joint chance constrained version of a simple blending problem. We conclude with a more demanding application of SAA methodology to the determination of the minimum provision an economic agent must have in order to meet a series of future payment obligations with sufficiently high probability.

[pt] Problemas de design decorrem de violações de princípios de design em um sistema de software. Tais problemas podem prejudicar a manutenção de sistemas e, logo, devem ser identificados e eliminados sempre que possível. Porém, identificar problemas de design não é trivial. Isso pois a documentação de design desses sistemas é em geral obsoleta ou inexistente. Assim, o desenvolvedor de um sistema tende a analisar o código-fonte em busca de problemas de design. Estudos sugerem anomalias de código-fonte como indicadores úteis desses problemas. Porém, outros estudos recentes mostram que uma única anomalia não é indicador suficiente. De fato, em torno de 80 por cento dos problemas de design estão associadas com múltiplas anomalias. Estas inter-relacionam-se na forma de aglomerações de anomalias. Embora as aglomerações de anomalias possam ajudar o desenvolvedor a identificar problemas de design, certas aglomerações contêm muitas anomalias. Isso então dificulta o raciocínio sobre a existência de um problema de design. Além disso, mesmo as propostas mais recentes de abordagens para a visualização de aglomerações de anomalias provêm suporte bastante limitado à identificação de problemas de design. Essa limitação é evidente quando um problema de design afeta múltiplos elementos na implementação de um sistema. Esta dissertação objetiva tratar essa limitação ao propor uma abordagem inovadora para a visualização de aglomerações de anomalias. Tal abordagem baseia-se em evidências coletadas a partir de vários experimentos propostos e conduzidos por nós. Contamos com a participação de desenvolvedores da academia e da indústria em cada experimento. Nossos resultados de estudo sugerem que vários desenvolvedores podem utilizar nossa abordagem de visualização para identificar de forma precisa problemas de design, especialmente aqueles que afetam múltiplos elementos de programa. Nossos resultados também apontam melhorias necessárias à abordagem com base na percepção dos desenvolvedores. / [en] Design problems are characterized by violations of design principles affecting a software system. Because they often hinder the software maintenance, developers should identify and eliminate design problems whenever possible. Nevertheless, identifying design problems is far from trivial. Due to outdated and scarce design documentation, developers not rarely have to analyze the source code for identifying these problems. Past studies suggest that code smells are useful hints of design problems. However, recent studies show that a single code smell might not suffice to reveal a design problem. That is, around 80 percent of design problems are realized by multiple code smells, which interrelate in the so-called smell agglomerations. Thus, developers can explore each smell agglomeration to identify a design problem in the source code. However, certain smell agglomerations are formed by several code smells, which makes it hard reasoning about the existence of a design problem. Visualization approaches have been proposed to represent smell agglomerations and guide developers in identifying design problems. However, those approaches provide a very limited support to the identification of specific design problems, especially the ones affecting multiple design elements. This dissertation aims to address this limitation by proposing a novel approach for the visualization of smell agglomerations. We rely on evidence collected from multiple empirical studies to design our approach. We evaluate our approach with developers from both academy and industry. Our results suggest that various developers could use our visualization approach to accurately identify design problems, in particular those affecting multiple program elements. Our results also point out to different ways for improving our visualization approach based on the developers perceptions.

[pt] Um problema de projeto é a manifestação de uma ou mais decisões de projeto inadequadas que afetam negativamente requisitos não funcionais. Por exemplo, Fat Interface, um problema que indica quando uma interface expõe serviços não coesos, no qual dificulta a extensibilidade e a manutenibilidade de um sistema de software. Apesar de problemas de projeto serem prejudiciais aos sistemas, identificá-los é uma tarefa difícil, especialmente quando o código-fonte é o único artefato disponível. Embora pesquisadores venham investigando técnicas para ajudar os desenvolvedores a identificar problemas de projeto, há pouco conhecimento sobre o processo de identificar problemas de projeto. Por exemplo, anomalias de códigos, um indicador de problemas de projeto, têm sido usadas para ajudar desenvolvedores a identificar problemas de projeto. No entanto, ainda não sabemos se elas são suficientes para ajudá-los ou não. Em particular, nenhum estudo tentou entender como os desenvolvedores identificam problemas de projeto. Nesse contexto, nós realizamos alguns estudos para entender a identificação de problemas de projeto. Em nossos dois primeiros estudos, nós investigamos o papel que as anomalias de código desempenham durante a identificação de problemas de design. Nossos resultados indicam que as anomalias de código são relevantes para os desenvolvedores na prática, por exemplo, eles são relevantes para indicar elementos a serem refatorados. Apesar da relevância, descobrimos que as anomalias de código não são suficientes para ajudar os desenvolvedores a identificar problemas de projeto. Nesse sentido, conduzimos outro estudo para investigar quais outros indicadores os desenvolvedores usam na prática e como eles são usados. Este estudo resultou em uma teoria sobre como os desenvolvedores identificam problemas de projeto na prática. A teoria revela quais são os indicadores que os desenvolvedores usam, como eles usam esses indicadores e as características de tais indicadores que os desenvolvedores consideram úteis. Os resultados encontrados nos forneceram uma melhor compreensão do processo de identificação de problemas de projeto, abrindo caminho para a elaboração de técnicas mais eficazes em ajudar os desenvolvedores a identificar problemas de projeto. / [en] A design problem is the manifestation of one or more inappropriate design decisions that negatively impact non-functional requirements. For example, the Fat Interface, a problem that indicates when an interface exposes non-cohesive services, hampers the extensibility and maintainability of a software system. Despite its harmfulness, identifying a design problem in a system is difficult, especially when the source code is the only available artifact. Although researchers have been investigating techniques to help developers in identifying design problems, there is little or no knowledge about the process of identifying design problems. For instance, code smells, microstructures that are a surface indication of design problems, have been used in several techniques to support developers during the design problem identification. However, there is no knowledge if code smells suffice to help developers to identify design problems. In particular, no study has tried to understand how developers identify design problems in practice. Thus, in this thesis, we have conducted a series of studies to understand design problem identification. In our two first studies, we investigated the role that code smells play in supporting developers during the design problem identification. Our results indicate that code smells are relevant for developers in practice; for instance, they are relevant to indicate elements that need to be refactored. However, we found that code smells, despite their relevance, do not suffice in helping developers to identify design problems. In this vein, we conducted another study to investigate what indicators developers use in practice, and how they use them. This study resulted in a theory about how developers identify design problems in practice. For instance, the theory reveals the indicators that developers use, how they use these indicators, and the characteristics of such indicators that are perceived as helpful by developers. The results found by our studies provided us with a better understanding of the process of identifying design problems thitherto nonexistent. Moreover, our findings pave the way for the elaboration of more effective techniques to identify design problems in the source code.

[pt] Uma facilidade é qualquer centro que presta serviços a um conjunto de clientes. Pode ser, dentre outros, uma escola, uma fabrica ou um armazém. Problemas de localização de facilidades são problemas de otimização combinatória que tratam da tomada de decisão relativa ao posicionamento destes serviços, que devem otimizar algum critério pré-definido. As medidas que usualmente são utilizadas para quantificar a qualidade de uma solução para esta classe de problemas tem seus cálculos baseados em que clientes são servidos por que facilidade. Uma conseqüência imediata é a forte relação entre os problemas de localização e os problemas de classificação de dados (clusterização). Dentre os problemas de localização de facilidades amplamente estudados esta o problema das p-Medianas (PMNC), objeto de pesquisa desta dissertação. O PMNC tem como objetivo determinar quais p facilidades devem ser abertas com o intuito de minimizar a soma das distancias de cada cliente a facilidade aberta mais próxima do mesmo. O PMNC é classificado como um problema NP - Difícil e é um dos problemas centrais na classificação automática de dados (clusterização). Esta dissertação apresenta algoritmos primais, duais e exatos para tratamento do PMNC, focando no desenvolvimento de algoritmos duais e exatos. Foram implementadas cinco heurísticas construtivas e um método de busca local. Além disto, foram propostos três novos métodos duais e um método exato. Como resultado, analisamos um conjunto de técnicas para o tratamento do problema. A escolha da melhor técnica é fortemente dependente da configuração da instancia tratada. Foi obtido o ótimo para algumas instancias e para as demais a diferença entre o valor dos limites inferior e superior nos melhores casos não ultrapassam 3%. / [en] A facility is any center that offers services to a set of clients. It may be, among others, a school, a factory or a depot. Facility location problems are combinatorial optimization problems that handle decisionmaking in respect to the positioning of those services, optimizing some defined criteria. The measures often used to assess the quality of a solution for this class of problems relate to which clients are served by which facility. An immediate consequence is the strong relationship between location problems and data clustering. One of the widely studied facility location problems is the uncapacited p-median problem (UPM), the main subject of this thesis. Given a set of possible facility locations, the UPM consists in determining a subset of locations at which the facilities shall be established, minimizing the sum of distances from each client to its closest open facility. The UPM belongs to the class of NP-hard problems and is a central problem of data clustering. This thesis presents primal, dual and exact algorithms for approaching the UPM, focusing on the development of dual and exact algorithms. Five constructive heuristics and one local search method were implemented. Furthermore, three new dual methods and one exact method were proposed. The result is the analysis of a set of techniques to solve the problem. The choice of best technique is strongly dependent of the configuration of the treated instance. We obtained the optimum for some instances and for others the difference between the value of the lower and upper bounds in the best cases do not exceed 3%.

[pt] Um resultado clássico no âmbito de equações diferenciais parciais e de geometria diferencial é o seguinte: Dada uma constante a existe uma condição da fronteira do domínio (Omega) de maneira que o problema de Dirichlet para a equação da curvatura média a no espaço Euclidiano é sempre solúvel. Este é um teorema devido a Serrin (1969). Além disso, se a condição de Serrin não for satisfeita, há um resultado de não-existência. A partir disso foi perguntado se um resultado similar valeria no espaço Hiperbólico. A finalidade desta tese é dar uma resposta afirmativa a esta pergunta, exibindo uma condição tipo Serrin. De maneira que obtém-se existência de superfícies cujo gráfico tenha curvatura média hiperbólica pré-determinada H(x) no espaço hiperbólico. O resultado é sharp no sentido que se tal condição for negada então não-existência pode ser estabelecida. O ponto central é uma estimativa a priori do gradiente de uma tal solução. / [en] A classical result in Partial Differential Equations and Differential Geometrydue to Serrin (1969) is the following: Given a constant (alfa) there exists a condition on the boundary of the domain (omega)such that the Dirichlet problem for the mean equation (alfa)is solvable. Besides, if Serrin's condition fails there is a non-existence result. Taking into account this classical result one may ask if a similar theorem holds in hyperbolic space. The goal of this thesis is to give a positive answer to this question establishing a certain Serrin type condition. Thus we obtain existence of surfaces whose graphs has prescribed mean curvature H(x) in hyperbolic space. This result is sharp because if the condition is not satisfied then a non- existence result can be inferred. The main point of the argument is some a priori gradient estimate and degree theory.

[pt] A análise de fluxo em solos parcialmente saturados exige o conhecimento das propriedades hidráulicas do solo: a curva característica, q(y), e a curva de permeabilidade, k(y). Entre os problemas geotécnicos que envolvem fluxo em meios parcialmente saturados pode-se citar a instabilização de encostas, muitas vezes associada a variações de sucção, e o transporte de contaminantes, pois, freqüentemente, a fonte contaminante está acima do nível d`água. O principal objetivo deste trabalho é a implementação numérica de um programa, baseado num código de elementos finitos, para a realização da retroanálise de parâmetros de fluxo em solos parcialmente saturados a partir de ensaios de campo, e que forneça também informações sobre a qualidade da estimativa obtida. O método de retroanálise utilizado permite a determinação simultânea da curva característica e da curva de permeabilidade a partir de dados de fluxo transiente. O programa desenvolvido foi utilizado para determinar os parâmetros de fluxo de um ensaio realizado no campo experimental II da PUC - Rio. Com base na análise dos resultados obtidos neste ensaio e na análise de sensibilidade foi proposto um ensaio de configuração mais simples que pode fornecer resultados satisfatórios na determinação das propriedades hidráulicas de solos parcialmente saturados. / [en] Flow analysis in partially saturated soils requires the determination of soil hydraulic properties: its characteristic curve, q(y), and its permeability curve k (y). The instabilization of slopes, often associated with suction variations, and the transport of contaminants, where the source of contaminants is often above water leve, are some of the geotechnical problems involving flows in partially saturated media. The main objective of this work is the numerical implementation of a program, based on finite element coding, for the back analysis of flow parameters in partially saturated soils, based on field experiments, capable of providing information on the quality of the estimates obtained. The back analysis method used here allows the simultaneous determination of the characteristic and permeability curves from transient flow data. The program was used to determine flow parameters of a field experiment conducted in Experimental Field II (PUC- Rio). A simpler configuration test is proposed based on the analysis of the results obtained in this field experiment and on a sensitivity analysis. This test may provide satisfactory results in the determination of hydraulic properties of partially saturated soils. / [es] El análisis de flujo en suelos parcialmente saturados exige el conocimiento de las propiedades hidráulicas del suelo: la curva característica, q(y), y la curva de permeabilidade, k(y). Entre los problemas geotécnicos que consideran flujos en medios parcialmente saturados se puede citar la inestabilidad de pendientes, muchas veces asociada a la variaciones de succión; y el transporte de contaminantes, ya que frecuentemente la fuente contaminante está encima del nível de agua. El principal objetivo de este trabajo es la implementación numérica de un programa, basado en un código de elementos finitos, para la realización del retroanálisis de parámetros de flujo en suelos parcialmente saturados a partir de ensayos de campo, y que brinde también informaciones sobre la calidad de la estimatición obtenida. El método de retroanálisis utilizado permite la determinación simultánea de la curva característica y de la curva de permeabilidad a partir de datos de flujo transitorio. El programa desarrollado fue utilizado para determinar los parámetros de flujo de un ensayo realizado en el campo experimental II de la PUC - Rio. Analizando los resultados obtenidos en este ensayo y el análisis de sensibilidad, se propone un ensayo de configuración más simple que puede dar resultados satisfactorios en la determinación de las propiedades hidráulicas de suelos parcialmente saturados.

[pt] Problemas de projeto afetam quase todo sistema de software, fazendo com que a sua manutenção seja cara e impeditiva. Como documentos de projeto raramente estão disponíveis, desenvolvedores frequentemente precisam identificar problemas de projeto a partir do código fonte. Entretanto, a identificação de problemas de projeto não é uma tarefa trivial por diversas razões. Por exemplo, a materialização de problemas de projeto tende a ser espalhada por diversos elementos de código anômalos na implementação. Infelizmente, trabalhos prévios assumiram erroneamente que cada anomalia de código individual – popularmente conhecida como code smell – pode ser usada como um indicador preciso de problema de projeto. Porém, evidências empíricas recentes mostram que diversos tipos de problemas de projeto são frequentemente relacionados a um conjunto de anomalias de código inter-relacionadas, conhecidas como aglomerações de anomalias de código. Neste contexto, esta dissertação propõe uma nova técnica para a síntese de aglomerações de anomalias de código. A técnica tem como objetivo: (i) buscar formas variadas de aglomeração em um programa, e (ii) sumarizar diferentes tipos de informação sobre cada aglomeração. A avaliação da técnica de síntese baseou-se na análise de diversos projetos de software da indústria e em um experimento controlado com desenvolvedores profissionais. Ambos estudos sugerem que o uso da técnica de síntese ajudou desenvolvedores a identificar problemas de projeto mais relevantes do que o uso de técnicas convencionais. / [en] Design problems affect almost all software projects and make their maintenance expensive and impeditive. As design documents are rarely available, programmers often need to identify design problems from the source code. However, the identification of design problems is not a trivial task for several reasons. For instance, the reification of a design problem tends to be scattered through several anomalous code elements in the implementation. Unfortunately, previous work has wrongly assumed that each single code anomaly - popularly known as code smell - can be used as an accurate indicator of a design problem. There is growing empirical evidence showing that several types of design problems are often related to a set of inter-related code anomalies, the so-called code-anomaly agglomerations, rather than individual anomalies only. In this context, this dissertation proposes a new technique for the synthesis of code-anomaly agglomerations. The technique is intended to: (i) search for varied forms of agglomeration in a program, and (ii) summarize different types of information about each agglomeration. The evaluation of the synthesis technique was based on the analysis of several industry-strength software projects and a controlled experiment with professional programmers. Both studies suggest the use of the synthesis technique helped programmers to identify more relevant design problems than the use of conventional techniques.

[pt] A gestão de ativos é uma abordagem crucial para o desempenho das organizações uma vez que buscam alinhar aspectos técnicos de engenharia com conceitos financeiros para otimizar o ciclo de vida de uma máquina. O Problema de Substituição de Equipamentos é uma das questões tratadas dentro dos estudos de gestão de ativos que visa decidir a melhor opção entre manter ou substituir o equipamento em um determinado intervalo de tempo. Uma das metodologias que vêm sendo utilizadas na literatura para solucionar este problema é a Programação Dinâmica, que se baseia em encontrar soluções parciais em uma série de estágios do problema até alcançar a ótima global. Este trabalho teve como objetivo determinar uma curva de substituição para um conjunto de locomotivas de uma empresa do setor ferroviário, considerando um limite de idade para poderem circular e seus históricos de receitas e custos ao longo dos anos. Os resultados alcançados permitiram que a empresa conhecesse a melhor forma de otimizar seu capital, levando em consideração os impactos financeiros caso opte por antecipar ou postergar o momento ótimo para substituição dos ativos. / [en] Asset management is a crucial approach for the performance of organizations as they seek to align technical aspects of engineering with financial concepts to optimize the life cycle of a machine. The Equipment Replacement Problem is one of the issues addressed within asset management studies that aims to decide the best option between maintaining or replacing equipment in a given time interval. One of the methodologies that have been used in the literature to solve this problem is Dynamic Programming, which is based on finding partial solutions in a series of stages of the problem until reaching the global optimum. This work aimed to determine a substitution curve for a set of locomotives of a company in the railway sector, considering an age limit for them to circulate and their revenue and cost history over the years. The results achieved allowed the company to know the best way to optimize its capital, taking into account the financial impacts if it chooses to anticipate or postpone the optimal moment for the replacement of assets.