In this dissertation, we examine specific network connectivity problems, and achieve improved approximation algorithm and integrality gap results for them. We introduce an important new, highly useful and applicable, network connectivity problem - the Vital Core Connectivity Problem (VCC). Despite its many practical uses, this problem has not been previously studied. We present the first constant factor approximation algorithm for VCC, and provide an upper bound on the integrality gap of its linear programming relaxation. We also introduce a new, useful, extension of the minimum spanning tree problem, called the Extended Minimum Spanning Tree Problem (EMST), that is based on a special case of VCC; and provide both a polynomial-time algorithm and a complete linear description for it. Furthermore, we show how to generalize this new problem to handle numerous disjoint vital cores, providing the first complete linear description of, and polynomial-time algorithm for, the generalized problem. We examine the Survivable Network Design Problem (SNDP) with multiple copies of edges allowed in the solution (multi-SNDP), and present a new approximation algorithm for which the approximation guarantee is better than that of the current best known for certain cases of multi-SNDP. With our method, we also obtain improved bounds on the integrality gap of the linear programming relaxation of the problem. Furthermore, we show the application of these results to variations of SNDP. We investigate cases where the optimal values of multi-SNDP and SNDP are equal; and we present an improvement on the previously best known integrality gap bound and approximation guarantee for the special case of SNDP with metric costs and low vertex connectivity requirements, as well as for the similar special case of the Vertex Connected Survivable Network Design Problem (VC-SNDP). The quality of the results that one can obtain for a given network design problem often depends on its integer linear programming formulation, and, in particular, on its linear programming relaxation. In this connection, we investigate formulations for the Steiner Tree Problem (ST). We propose two new formulations for ST, and investigate their strength in terms of their associated integrality gaps.

[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.

Submitted by Maykon Nascimento (maykon.albani@hotmail.com) on 2015-10-19T19:19:50Z No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Modelo matematico e meta heuristica simulated annealing para elaboração de roteiros turísticos com base no tourist trip design problem.pdf: 2271247 bytes, checksum: faaad9e85f6978197ce7c7b03933a2ca (MD5) / Approved for entry into archive by Elizabete Silva (elizabete.silva@ufes.br) on 2015-11-03T19:59:38Z (GMT) No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Modelo matematico e meta heuristica simulated annealing para elaboração de roteiros turísticos com base no tourist trip design problem.pdf: 2271247 bytes, checksum: faaad9e85f6978197ce7c7b03933a2ca (MD5) / Made available in DSpace on 2015-11-03T19:59:38Z (GMT). No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Modelo matematico e meta heuristica simulated annealing para elaboração de roteiros turísticos com base no tourist trip design problem.pdf: 2271247 bytes, checksum: faaad9e85f6978197ce7c7b03933a2ca (MD5) Previous issue date: 2015 / O turismo é um importante setor para economia mundial e vem crescendo consistentemente nos últimos anos. Porém, um fator determinante para escolha do destino de um turista é a existência de pontos de interesse que ele deseja visitar na região e, para tanto, as informações dos pontos de interesse de uma região devem estar disponíveis. Dada às limitações de tempo do turista, não é possível para ele visitar todos os atrativos e, por essa razão, se faz necessário a criação de roteiros turísticos. Muito embora existam diversos pacotes de viagens com destinos predefinidos, contemplando locais mais populares, nos últimos anos tem crescido a procura por soluções que criem roteiros personalizados voltados às necessidades de cada turista. Para suprir essa nova demanda, Van Oudheusden e Vansteenwegen (2007) propuseram o Tourist Trip Design Problem (TTDP) e sugeriram o uso do Orienteering Problem (OP) e suas extensões para resolução do TTDP. Esta dissertação tem por objetivo o desenvolvimento de um modelo matemático e de uma meta-heurística Simulated Annealing (SA) para resolução do TTDP. O objetivo considerado consiste em gerar roteiros que maximizem a soma das notas atribuídas aos atrativos em função do grau de interesse do turista, levando em conta o período que ele tem disponível na localidade e o horário que cada atrativo está disponível para ser visitado. / Tourism is an important sector for the world economy and has been growing steadily over recent years. However, a decisive factor for the choice of a tourist destination is the existence of points of interest in the region he wants to visit and, therefore, the information from points of interest in a region should be available. Given the tourist time constraints, it is not possible for him to visit all the attractions and, therefore, it is necessary the creation of tourist routes. Although there are several packages with predefined destinations contemplating most popular locations in recent years has increased the demand for solutions that create custom tours for the needs of each tourist. To meet this new demand Van Oudheusden and Vansteenwegen (2007) proposed the Tourist Trip Design Problem (TTDP) and they suggested that the use of the Orienteering Problem (OP) and its extensions is the best approach to the TTDP. This thesis proposes the development of a mathematical model and a Simulated Annealing (SA) metaheuristic to solve the TTDP. The objective considered is to generate routes that maximize the sum of scores awarded to the attractions based on the degree of interest of the tourist taking into account the time that he has in the locality and the time that each attraction is available to be visited.

Submitted by Maykon Nascimento (maykon.albani@hotmail.com) on 2015-10-19T19:19:50Z No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Modelo matematico e meta heuristica simulated annealing para elaboração de roteiros turísticos com base no tourist trip design problem.pdf: 2271247 bytes, checksum: faaad9e85f6978197ce7c7b03933a2ca (MD5) / Approved for entry into archive by Elizabete Silva (elizabete.silva@ufes.br) on 2015-11-03T19:59:38Z (GMT) No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Modelo matematico e meta heuristica simulated annealing para elaboração de roteiros turísticos com base no tourist trip design problem.pdf: 2271247 bytes, checksum: faaad9e85f6978197ce7c7b03933a2ca (MD5) / Made available in DSpace on 2015-11-03T19:59:38Z (GMT). No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Modelo matematico e meta heuristica simulated annealing para elaboração de roteiros turísticos com base no tourist trip design problem.pdf: 2271247 bytes, checksum: faaad9e85f6978197ce7c7b03933a2ca (MD5) Previous issue date: 2015 / Modelo Matemático e Meta-Heurística Simulated Annealing para Elaboração de Roteiros Turísticos com base no Tourist Trip Design Problem / Modelo Matemático e Meta-Heurística Simulated Annealing para Elaboração de Roteiros Turísticos com base no Tourist Trip Design Problem

In this dissertation, we examine specific network connectivity problems, and achieve improved approximation algorithm and integrality gap results for them. We introduce an important new, highly useful and applicable, network connectivity problem - the Vital Core Connectivity Problem (VCC). Despite its many practical uses, this problem has not been previously studied. We present the first constant factor approximation algorithm for VCC, and provide an upper bound on the integrality gap of its linear programming relaxation. We also introduce a new, useful, extension of the minimum spanning tree problem, called the Extended Minimum Spanning Tree Problem (EMST), that is based on a special case of VCC; and provide both a polynomial-time algorithm and a complete linear description for it. Furthermore, we show how to generalize this new problem to handle numerous disjoint vital cores, providing the first complete linear description of, and polynomial-time algorithm for, the generalized problem. We examine the Survivable Network Design Problem (SNDP) with multiple copies of edges allowed in the solution (multi-SNDP), and present a new approximation algorithm for which the approximation guarantee is better than that of the current best known for certain cases of multi-SNDP. With our method, we also obtain improved bounds on the integrality gap of the linear programming relaxation of the problem. Furthermore, we show the application of these results to variations of SNDP. We investigate cases where the optimal values of multi-SNDP and SNDP are equal; and we present an improvement on the previously best known integrality gap bound and approximation guarantee for the special case of SNDP with metric costs and low vertex connectivity requirements, as well as for the similar special case of the Vertex Connected Survivable Network Design Problem (VC-SNDP). The quality of the results that one can obtain for a given network design problem often depends on its integer linear programming formulation, and, in particular, on its linear programming relaxation. In this connection, we investigate formulations for the Steiner Tree Problem (ST). We propose two new formulations for ST, and investigate their strength in terms of their associated integrality gaps.

As the the number of cores on a single chip continue to grow, communication increasingly becomes the bottleneck to performance. Networks on Chips (NoC) is an interconnection paradigm showing promise to allow system size to increase while maintaining acceptable performance. One of the challenges of this paradigm is in constructing the network of inter-core connections. Using the traditional wire interconnect as long range links is proving insufficient due to the increase in relative delay as miniaturization progresses. Novel link types are capable of delivering single-hop long-range communication. We investigate the potential benefits of constructing networks with many link types applied to heterogeneous NoCs and hypothesize that a network with many link types available can achieve a higher performance at a given cost than its homogeneous network counterpart. To investigate NoCs with heterogeneous links, a multiobjective evolutionary algorithm is given a heterogeneous set of links and optimizes the number and placement of those links in an NoC using objectives of cost, throughput, and energy as a representative set of a NoC's quality. The types of links used and the topology of those links is explored as a consequence of the properties of available links and preference set on the objectives. As the platform of experimentation, the Complex Network Evolutionary Algorithm (CNEA) and the associated Complex Network Framework (CNF) are developed. CNEA is a multiobjective evolutionary algorithm built from the ParadisEO framework to facilitate the construction of optimized networks. CNF is designed and used to model and evaluate networks according to: cost of a given topology; performance in terms of a network's throughput and energy consumption; and graph-theory based metrics including average distance, degree-, length-, and link-distributions. It is shown that optimizing complex networks to cost as a function of total link length and average distance creates a power-law link-length distribution. This offers a way to decrease the average distance of a network for a given cost when compared to random networks or the standard mesh network. We then explore the use of several types of constrained-length links in the same optimization problem and find that, when given access to all link types, we obtain networks that have the same or smaller average distance for a given cost than any network that is produced when given access to only one link type. We then introduce traffic on the networks with an interconnect-based packet-level shortest-path-routed traffic model. We find heterogeneous networks can achieve a throughput as good or better than the homogeneous network counterpart using the same amount of link. Finally, these results are confirmed by augmenting a wire-based mesh network with non-traditional link types and finding significant increases the overall performance of that network.

Due to its economic importance engineering design as a creative design problem solving has been the research subject of psychologists and design engineers for several years. Observations of designer's thinking and action processes show that especially in the early stages of the design process, in which requirements are clarified and ideas are developed, generating solutions is largely associated with the use of simple external representations such as sketches and material (physical) models. In the represented thesis the use and functions of such external aids were investigated at first with a questionnaire study consulting designers (N = 106) of different industries. The results demonstrate the dominance of sketches as well as the increasing use of CAD already in the early stages of product development. In contrast models are applied to a lesser extent. Thereby simple external aids are not only used as memory-relieving external information storages, but do also support solution development and testing, serve as an analysis aid and contribute helpfully to documentation and communication. Further in an experimental study the use and functions of sketching and manual modelling applied by engineering students and designers (N = 61) while working on two design problems of different complexity with free choice of the support form were analysed. The results verify the essential importance of sketching for the design process, since almost all subjects used sketches to deal with the two design problems, while material models were hardly applied. Again the sketches fulfil different functions, so besides documentation they mainly support solution development. These statement based findings that sketches in addition to their function as external storages for memory relief serve also as thinking aids, thus support the generating and further developing of solution concepts, could be confirmed by observation data based on the analysis of the individual design processes. Finally recommendations for the design of new and advanced computer-assisted design aids could be given. / Das Konstruieren als schöpferisch-entwerfendes Problemlösen (design problem solving) ist aufgrund seiner wirtschaftlichen Bedeutung seit längerem Gegenstand der Forschung von Psychologen und Konstruktionswissenschaftlern. Beobachtungen des Vorgehens des Konstrukteurs zeigen, daß insbesondere in den frühen Phasen des konstruktiven Entwurfsprozesses, in denen Anforderungen geklärt und Ideen generiert werden, die Lösungsentwicklung in hohem Maße durch einfache externe Hilfsmittel, wie Skizzen und gegenständliche Modelle, unterstützt wird. In der dargestellten Dissertation wurde Einsatz und Nutzen dieser Hilfsmittel zunächst anhand einer Befragung von Konstrukteuren (N = 106) verschiedener Branchen untersucht. Die Ergebnisse belegen die Dominanz von Skizzen sowie die Zunahme der Nutzung von CAD bereits in den frühen Phasen der Produktentwicklung. Modelle finden dagegen weniger häufig Verwendung. Einfache externe Hilfsmittel werden dabei nicht nur als gedächtnisentlastende externe Speicher eingesetzt, sondern unterstützen ebenso die Lösungsentwicklung und -überprüfung, dienen als Analysehilfe und tragen hilfreich zur Dokumentation und Kommunikation bei. Weiterhin wurde in einer experimentellen Studie der Einsatz und die Funktionen des Skizzierens und manuellen Modellierens bei der Bearbeitung zweier Konstruktionsprobleme unterschiedlicher Komplexität durch Maschinenbaustudenten und Konstrukteure (N = 61) bei freier Wahl der Unterstützungsform näher untersucht. Die Ergebnisse verifizieren die essentielle Bedeutung des Skizzierens für den konstruktiven Entwurfsprozeß, da nahezu alle Probanden die beiden Konstruktionsprobleme von Anfang an skizzierend bearbeiteten, während einfache Modelle so gut wie gar nicht eingesetzt wurden. Die Skizzen erfüllten wiederum verschiedene Funktionen, neben der Dokumentation wurden sie v.a. zur Lösungsentwicklung verwendet. Dabei konnten diese auf Aussagen beruhenden Erkenntnisse, daß Skizzen neben der Gedächtnisentlastung auch eine Denkhilfe bieten, durch aus der Analyse der Entwurfsprozesse gewonnene Beobachtungsdaten bestätigt werden. Abschließend wurden Gestaltungsempfehlungen für die Neu- und Weiterentwicklung computergestützter Hilfsmittel des konstruktiven Entwurfsprozesses formuliert.

[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.

No description available.