[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] Capacitar usuários a contribuir proativamente para projetos de Open Source Software (OSS) através de relatos de problemas de Interação Humano-Computador (IHC) não apenas representa uma alternativa para resolver problemas de IHC em projetos de OSS, mas uma que se enquadra nos valores e ideologia da comunidade OSS. Através de referências às experiências comunicadas através de relatos de problemas de IHC, designers em projetos de OSS podem não apenas fazer suas decisões de design de uma maneira aberta transparente, mas também de uma maneira que os usuários finais possam se relacionar com os valores da comunidade. Esse estudo tem como objetivo explorar (a) como relatos de problemas se encaixam e influenciam as atividades de designers em projetos de OSS, (b) quais são as informações necessárias dos designers em projetos de OSS, e (c) como podemos apoiar os usuários na criação de relatos que estejam alinhados com essas informações. Para endereçar as questões (a) e (b), nós realizamos entrevistas com quatro designers contribuindo para projetos de OSS, e avaliamos qualitativamente um conjunto de 547 bugs reportados com palavras-chave relacionadas à IHC. Com esses dados, nós elaboramos um formulário, com base na Engenharia Semiótica, para usuários relatarem problemas de IHC. Para avaliar quão bem esse formulário comunica as informações que designers em projetos de OSS precisam e, então, endereçar a questão (c), nós conduzimos um estudo onde participantes foram convidados a reportar problemas de IHC através do formulário elaborado. / [en] Empowering end users to proactively contribute to OSS by reporting HCI issues not only represents a potential approach to solving HCI problems in OSS projects, but it also fits the Open Source values and ideology. By referring to the end users personal experiences and feedback reports, designers in OSS communities may build their design rationale not only in an open and transparent manner, but also in such a way that end users relate to the values embedded in the community. This study aims to contribute to the existing literature by exploring (a) how issue reports fit and influence OSS designers activities, (b) what the information needs of designers in OSS projects are, and (c) how to support users on the task of creating HCI issues reports that meet those needs. In order to collect data about questions (a) and (b), we conducted interviews with four designers contributing to OSS projects, and qualitatively evaluated a set of 547 bugs reported under HCI-related keywords. Using this data and based on Semiotic Engineering, we designed a form for users to report HCI issues. To investigate how well this form communicates the information needs of OSS designers and address question (c), we performed a study in which participants were invited to report HCI issues through the designed form.

A agricultura foi responsável por transformar os modos de vida há milhares de anos atrás. Mais recentemente, a transformação desencadeada pela agricultura ocorreu através da modernização de seus processos produtivos. Em território brasileiro, a modernização agrícola possibilitou amplamente o cultivo de soja. A alta demanda e os bons preços no mercado internacional incitaram a promoção de políticas de incentivo ao cultivo de soja, principalmente no bioma Cerrado. Ademais os benefícios econômicos, a sojicultura realizada nos moldes da modernização agrícola brasileira, com grandes aportes mecânicos e químicos, e manutenção da estrutura fundiária causa impactos ambientais e sociais. Desmatamento, poluição de cursos d’água, erosão, compactação de solos, intoxicação e concentração de terra são alguns desses problemas. No presente trabalho, procurou-se traçar o perfil e verificar as percepções e práticas de um grupo de produtores de soja, isto é, sojicultores, atores sociais envolvidos com o cultivo de soja, em torno de sua atividade produtiva e do meio ambiente. A pesquisa se realizou no município maior produtor de soja de Goiás, Rio Verde, cuja vegetação nativa é típica de Cerrado. Também se procurou verificar a existência e a situação dos problemas ambientais mais percebidos pelo grupo de sojicultores em Rio Verde. Para alcançar tais objetivos, aplicou-se questionário a um grupo de 50 sojicultores em 3 grandes lojas revendedoras de produtos agropecuários de Rio Verde. Posteriormente, os dados foram processados pelo programa computacional EPI INFO e analisados. De forma geral, os questionários revelaram que o grupo pesquisado cultivava soja nos padrões verificados no Cerrado, isto é, em grandes propriedades e intensivo em mecanização e agrotóxicos. Em relação às percepções e às práticas, constatou-se que de uma forma geral, a percepção ambiental dos sojicultores entrevistados não necessariamente influenciava na adoção de práticas agrícolas sustentáveis. A adoção do plantio direto, que apregoa a mitigação de impactos da agricultura no ambiente, é sinal de uma agricultura mais sustentável, apesar da exigência de maiores quantidades de herbicidas. Desmatamento, poluição das águas, erosão e intoxicação foram os problemas ambientais mais percebidos pelos entrevistados. A verificação da existência e situação desses problemas ocorreu através de mapas de uso do solo de Rio Verde dos anos 1975, 1989 e 2005, dos autos de infração emitidos por órgãos de fiscalização ambiental, dos resultados das análises de resíduos de agrotóxicos na água destinada ao abastecimento público do município e dos casos de intoxicação por agrotóxico de uso agrícola no município. Por falta de dados não foi possível conferir a presença de erosão. A presença e gravidade do desmatamento, que ocorreu entre 1975 e 2005, puderam ser detectadas pelos dados analisados. Já os dados sobre intoxicação, por possivelmente estarem subnotificados, revelaram um problema de saúde pública. Concluiu-se a necessidade de ações pelo poder público para que haja uma verdadeira fiscalização ambiental em Rio Verde, a tomada de medidas que melhorem a notificação de casos de intoxicação, e a promoção de incentivos àqueles agricultores que respeitam as leis ambientais. Também se faz necessário o desenvolvimento de técnicas agrícolas mais sustentáveis dos pontos de vista econômico, produtivo, social e ambiental. / Agriculture was responsible for transforming the ways of life millions of years ago. More recently, the transformation promoted by agriculture happened through the modernization of its productive processes. In Brazilian territory, the agricultural modernization made possible soybean growing. The strong demand and the good prices at the international market motivated incentive policies for soybean growing, mainly at the Cerrado biome. Besides the economic benefits, soybean growing conducted through Brazilian agriculture modernization, with huge mechanical and chemical inputs, and the maintenance of the land distribution structure caused environmental and social impacts. Deforestation, pollution of waters, soil erosion and depletion, intoxication and land concentration are some of these problems. In the present work, the aim was to outline the profile and verify the perceptions and practices of a group of soybean-planters, social actors involved with the growing of soybean, along its productive activity and the environment. The research was done at the largest soybean grower municipality of Goiás, Rio Verde, with native vegetation typical of Cerrado. It also aimed to verify the existence and the situation of the most perceived environmental problems by the group of soybean-planters in Rio Verde. To reach those objectives, a questionnaire was applied to a group of 50 soybean-planters at 3 big agricultural products reselling stores of Rio Verde. Data obtained was processed by EPI INFO computer program and analyzed. Broadly speaking, the questionnaire revealed that the investigated group grew soybean into the Cerrado patterns, which means, on large properties with intensive use of mechanization and pesticides. About the perceptions and practices, it was verified that, broadly speaking, the environmental perception of the interviewed soybean-planters not necessarily influenced the adoption of sustainable agricultural practices. The no-till system adoption, that reduces agricultural impacts on the environment, is a signal of a more sustainable agriculture, although it demands greater amounts of herbicides. Deforestation, water pollution, soil erosion and intoxication were the most perceived environmental problems by the interviewees. The verification of the existence and situation of these problems was done through maps of Rio Verde’s land use of the years 1975, 1989 and 2005; by illegal deforestation infractions issued by environmental control offices, by the results of pesticides remains analyses in the drinking water of the city, and by the intoxication cases by pesticides of agricultural use at the municipality. Soil erosion couldn’t be checked due to lack of data. The deforestation presence, that took place between 1975 e 2005, and its seriousness, could be detected by the analyzed data. The intoxication data, that were probably under notified, revealed a public health problem. As conclusion it was emphasized the need of public actions in order to promote a better environmental control in Rio Verde, the adoption of measures that would improve the notification of intoxication cases, and the promotion of incentives for those planters that respect the environmental laws. It is also necessary to devise more sustainable agricultural techniques according to the economic, productive, social and environmental points of view.

As reações químicas que resultam da expressão de genes são complexas e ainda não são total- mente compreendidas. Sabe-se que os genes enviam, recebem, e processam informações formando uma complexa rede de comunicação, mas a arquitetura e dinâmica destas redes não são totalmente conhecidas. Dessa forma, um problema importante é determinar como os genes se relacionam dentro da célula. Esse processo de determinar o relacionamento entre os genes é conhecido como inferência de redes gênicas. Uma das formas para representar o relacionamento entre os genes é usar modelos matemáticos e computacionais de Redes Gênicas. Em especial, um dos modelos de grande interesse é o de Redes Booleanas (BN - do inglês Boolean Networks), no qual os genes podem assumir dois estados, ativo ou inativo, se estão, respectivamente, expressos ou não. Estes estados podem variar ao longo do tempo, dependendo de como os genes se relacionam. Nosso interesse está em estudar um caso particular deste modelo, conhecido como Redes Booleanas Limiarizadas, onde apenas uma classe de funções booleanas é utilizada para construir as BNs. Para inferir as Redes Booleanas Limiarizadas, usamos um algoritmo constituído de dois passos. Primeiro, usamos o arcabouço do Problema de Satisfação de Restrições (CSP - do inglês Constraint Satisfaction Problem) para inferir conjuntos de soluções consistentes com uma dada série temporal de um conjunto de genes. Em seguida analisamos o comportamento dinâmico das soluções encon- tradas , filtrando conjuntos de soluções de maior interesse para testes práticos em laboratório. Usando o arcabouço do CSP, construímos um solver, usando a biblioteca Gecode,1 para inferência de redes consistentes, usando como entrada uma série temporal oriunda de dados de microarrays. Em seguida, através da simulação da dinâmica de uma amostra das redes encontradas no passo anterior, fomos capazes de determinar algumas restrições interessantes para filtrar o conjunto de redes. Aplicamos o nosso método para três conjuntos de dados: dois artificiais, e para validação, usamos uma série temporal de uma rede artificial conhecida na literatura. Com isso fomos capazes de inferir conjuntos de redes gênicas de possível interesse para testes em laboratório. / The chemical reactions that result in gene expression are complex and not yet fully understood. It is known that genes send, receive and process information to form a complex network of com- munication, but the architecture and dynamics of these networks are not fully known. Thus, one major problem is to determine how genes are linked within the cell. This process of determining the relationship between genes is known as inference of genetic networks. One way to represent the relationship between genes is to use mathematical and computer models of genetic networks. In particular, one of the models of great interest are Boolean Networks (BN), in which genes can take two states, active or inactive, if they are, respectively, expressed or not. These states may vary over time, depending on how genes are related. Our interest is in studying a case of this particular model, known as thresholded Boolean networks, where only one class of Boolean functions is used to build the GNs. To infer the thresholded Boolean networks, we use an algorithm that consists of two steps. First, we use the framework of Constraint Satisfaction Problem (CSP) to infer sets of solutions consistent with a time series of a given set of genes. Then analyze the dynamic behavior of the solutions, filtering sets of solutions with interest for practical tests in the laboratory. Using the framework of the CSP, we constructed a solver, using the library Gecode, 2 for in- ference of consistent networks, using as input a time series arising from microarrays data. Then, by simulating the dynamics of a sample of networks found in the previous step, we were able to determine some interesting constraints to filter the set of networks. We apply our method to three datasets: two artificial, and for validation, we use a time series of an artificial network known from literature. Thus we were able to infer genetic networks sets of possible interest for laboratory tests.

Atualmente, podemos perceber que uma grande dependência dos sistemas desenvolvidos sob a seara da criptografia foi instaurada em todos nós. Principalmente no tocante dos sistemas criptográficos de chave pública, que são vastamente utilizados na Internet. No entanto, a criptografia de chave pública viu-se ameaçada e começou a investigar novas fontes de problemas para seus sistemas quando Shor em 1997 desenvolveu um algoritmo de tempo polinomial para fatorar inteiros e para calcular o logaritmo discreto em um computador quântico. Neste contexto, Patarin propõe a função alçapão HFE (Hidden Field Equations), uma trapdoor baseada nos Problemas MQ (Multivariate Quadratic) e IP (Isomorfismo de Polinômios). Tais problemas não são afetados pelo algoritmo de Shor, além disto o Problema MQ foi demonstrado por Patarin e Goubin como sendo NP-completo. Apesar do HFE ter sua versão básica quebrada, ele apresenta variações -- obtidas através de modificadores genéricos -- resistentes aos principais ataques da atualidade. O Quartz -- esquema de assinatura digital baseado no HFEv-, com escolha especial de parâmetros -- é um bom exemplo desta resistência a ataques algébricos que visem a recuperação da chave privada, pois até hoje permanece seguro. Além de também se destacar por gerar assinaturas curtas. Todavia, Joux e Martinet -- baseados em axiomas do Ataque pelo Paradoxo de Aniversário -- provaram que o Quartz é maleável, demonstrando que caso o adversário possua um par (mensagem, assinatura) válido, ele conseguirá obter uma segunda assinatura com 2^(50) computações e 2^(50) chamadas ao oráculo de assinatura, logo muito abaixo dos padrões de segurança atuais que são de, no mínimo, 2^(112). Desta forma, baseado no Quartz, apresentamos um novo esquema de assinatura digital resistente a ataques adaptativos de mensagem escolhida que realizem chamadas ao oráculo aleatório, com um nível de segurança estimado em 2^(112). Nosso criptossistema proporciona, ainda, um ganho de eficiência no algoritmo de verificação de assinatura e na inicialização dos vetores que serão utilizados pelos algoritmos de assinatura e verificação. Além de, também, disponibilizarmos uma implementação do Quartz Original e do Quartz Aprimorado, na linguagem de programação Java. / Today, we can see that a large dependence of the systems developed under the cryptography was introduced in all of us. Especially in terms of public key cryptosystems, which are widely used on the Internet. However, public key cryptography was threatened and began to investigate new sources of problems for their systems when Shor in 1997 developed a polynomial time algorithm for factoring integers and to compute the discrete logarithm in a quantum computer. In this context, Patarin proposed Hidden Field Equations (HFE), a trapdoor based on MQ (Multivariate Quadratic) and IP (Isomorphism of Polynomials) problems. Such problems are not affected by the Shor algorithm, moreover MQ Problem was demonstrate by Patarin and Goubin as NP-complete. Despite the basic HFE has broken, it varies secure, obtained by generic modification. The Quartz -- digital signature scheme based on HFEv-, with special choice of parameters -- is a good example of this resistance to algebraic attacks aimed at the recovery of the private key, because even today remains secure. Furthermore, it also generates short signatures. However, Joux and Martinet -- based on axioms of Birthday Paradox Attack -- proved that Quartz is malleable, showing that if the adversary has a pair (message, signature) valid, he can get a second signature with 2^(50) computations and 2^(50) calls to the signing oracle, so far the current security standards that are at least 2^(112). Thus, based on Quartz, we present a new digital signature scheme, achieving the adaptive chosen message attacks that make calls to the random oracle, with a secure level estimated at 2^(112). Our cryptosystem also provides an efficiency gain in signature verification algorithm and initialization vectors that will be used for signing and verification algorithms. Further we provide an implementation of Original Quartz and Enhanced Quartz in the Java programming language.

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

[pt] A teoria dos Jogos Combinatórios é o estudo de jogos com informação completa. Isso é, todos os jogadores conhecem todos os possíveis movimentos, além disso, temos que não há sorte ou a habilidade de realizar um movimento, então, em teoria jogar perfeitamente é possível. Exemplos de jogos assim são jogo da velha, xadrez, damas, Nim... a lista continua. Nessa dissertação focamos no jogo Maker-Breaker. Ele tem dois jogadores que sequencialmente escolhem um vértice de um hipergrafo. O objetivo de Maker é escolher todos os vértices de uma aresta e o objetivo de Breaker é prevenir isso. Para entender em quais tipos de hipergrafos Maker ou Breaker ganha e quais são as estratégias de vitória utilizamos SAT, probabilidade, teoria dos grafos em geral e mais. / [en] The theory of Combinatorial Games is the study of games with perfect information. This means that all players have knowledge of all possible moves, also there isn t luck or skill to perform a move, so, in theory perfect play is possible. Examples of games like these are tic-tac-toe, chess, checkers, Nim... the list goes on. In this dissertation we focus on the Maker-Breaker game. It has two players that pick a vertex from a hypergraph. The goal of Maker is to claim all vertices of an edge and the goal of Breaker is to prevent it. To understand in which types of hypergraphs does Maker or Breaker win and what are the winning strategies, we make use of SAT, Probability, general Graph Theory and more.