[pt] Desde que foram propostos como método de otimização, os algoritmos evolutivos têm sido usados com sucesso para resolver problemas complexos nas mais diversas áreas como, por exemplo, o projeto automático de circuitos e equipamentos, planejamento de tarefas, engenharia de software e mineração de dados, entre tantos outros. Este sucesso se deve, entre outras coisas, ao fato desta classe de algoritmos não necessitar de formulações matemáticas rigorosas a respeito do problema que se deseja otimizar, além de oferecer um alto grau de paralelismo no processo de busca. No entanto, alguns problemas são computacionalmente custosos no que diz respeito à avaliação das soluções durante o processo de busca, tornando a otimização por algoritmos evolutivos um processo lento para situações onde se deseja uma resposta rápida do algoritmo (como por exemplo, problemas de otimização online). Diversas maneiras de se contornar este problema, através da aceleração da convergência para boas soluções, foram propostas, entre as quais destacam-se os Algoritmos Culturais e os Algoritmos Co-Evolutivos. No entanto, estes algoritmos ainda têm a necessidade de avaliar muitas soluções a cada etapa do processo de otimização. Em problemas onde esta avaliação é computacionalmente custosa, a otimização pode levar um tempo proibitivo para alcançar soluções ótimas. Este trabalho propõe um novo algoritmo evolutivo para problemas de otimização numérica (Algoritmo Evolutivo com Inspiração Quântica usando Representação Real - AEIQ- R), inspirado no conceito de múltiplos universos da física quântica, que permite realizar o processo de otimização com um menor número de avaliações de soluções. O trabalho apresenta a modelagem deste algoritmo para a solução de problemas benchmark de otimização numérica, assim como no treinamento de redes neurais recorrentes em problemas de aprendizado supervisionado de séries temporais e em aprendizado por reforço em tarefas de controle. Os resultados obtidos demonstram a eficiência desse algoritmo na solução destes tipos de problemas. / [en] Since they were proposed as an optimization method, the evolutionary algorithms have been successfully used for solving complex problems in several areas such as, for example, the automatic design of electronic circuits and equipments, task planning and scheduling, software engineering and data mining, among many others. This success is due, among many other things, to the fact that this class of algorithms does not need rigorous mathematical formulations regarding the problem to be optimized, and also because it offers a high degree of parallelism in the search process. However, some problems are computationally intensive when it concerns the evaluation of solutions during the search process, making the optimization by evolutionary algorithms a slow process for situations where a quick response from the algorithm is desired (for instance, in online optimization problems). Several ways to overcome this problem, by speeding up convergence time, were proposed, including Cultural Algorithms and Coevolutionary Algorithms. However, these algorithms still have the need to evaluate many solutions on each step of the optimization process. In problems where this evaluation is computationally expensive, the optimization might take a prohibitive time to reach optimal solutions. This work proposes a new evolutionary algorithm for numerical optimization problems (Quantum- Inspired Evolutionary Algorithm for Problems based on Numerical Representation - QIEA-R), inspired in the concept of quantum superposition, which allows the optimization process to be carried on with a smaller number of evaluations. The work presents the modelling for this algorithm for solving benchmark numerical optimization problems, and for training recurrent neural networks in supervised learning and reinforcement learning. The results show the good performance of this algorithm in solving these kinds of problems.

[pt] Consideramos, nesta dissertação, a questão de determinar se um grafo tem uma propriedade P, tal como G é livre de triângulos ou G é 4- colorível. Em particular, consideramos para quais propriedades P existe um algoritmo aleatório com probabilidades de erro constantes que aceita grafos que satisfazem P e rejeita grafos que são epsilon-longe de qualquer grafo que o satisfaça. Se, além disso, o algoritmo tiver complexidade independente do tamanho do grafo, a propriedade é dita testável. Discutiremos os resultados de Alon, Fischer, Newman e Shapira que obtiveram uma caracterização combinatória de propriedades testáveis de grafos, resolvendo um problema em aberto levantado em 1996. Essa caracterização diz informalmente que uma propriedade P de um grafo é testável se e somente se testar P pode ser reduzido a testar a propriedade de satisfazer uma das finitas partições Szemerédi. / [en] We consider, in this thesis, the question of determining if a graph has a property P such as G is triangle-free or G is 4-colorable. In particular, we consider for which properties P there exists a random algorithm with constant error probabilities that accept graphs that satisfy P and reject graphs that are epsilon-far from any graph that satisfies it. If, in addition, the algorithm has complexity independent of the size of the graph, the property is called testable. We will discuss the results of Alon, Fischer, Newman, and Shapira that obtained a combinatorial characterization of testable graph properties, solving an open problem raised in 1996. This characterization informally says that a graph property P is testable if and only if testing P can be reduced to testing the property of satisfying one of finitely many Szemerédi-partitions.

[pt] Atualmente as Unidades de Saúde, em um grande número de países do mundo, apresentam demandas de serviços que superam suas capacidades reais. Por esta razão, o surgimento das listas de espera é inevitável. Preparar o planejamento das mesmas, de modo otimizado resulta, portanto, em um grande desafio, devido à quantidade de recursos que devem ser considerados. O caso particular dos procedimentos cirúrgicos é particularmente crítico pela quantidade de recursos que se precisam para a realização do mesmo. Poucos projetos têm sido desenvolvidos para a gestão completa dessas listas. O trabalho desenvolvido nesta Dissertação propõe o uso de um modelo, baseado em algoritmos genéticos com inspiração quântica, para a automatização e otimização do planejamento de procedimentos cirúrgicos eletivos. Este modelo, denominado Algoritmo Evolucionário com Inspiração Quântica para a Área de Saúde (AEIQ-AS), além de alocar os pacientes e os recursos necessários para que o processo cirúrgico seja exitoso, procura reduzir o tempo total para que todas as cirurgias sejam realizadas. Este trabalho apresenta também uma ferramenta que permite a modelagem, de modo simplificado, de uma Unidade Cirúrgica de Saúde. Esta ferramenta possibilita a realização de simulações com o objetivo de ver o efeito de diferentes configurações dos recursos nas Unidades de Saúde. Para a validação do modelo proposto foi criada, de modo artificial e fazendo uso da ferramenta de simulação, uma lista de espera de 2000 cirurgias. Caso as cirurgias fossem realizadas seguindo a ordem de chegada, seriam necessárias pouco mais de 37 semanas e teria 1066 operações fora do prazo. Foram feitos vários experimentos onde se buscava a otimização destes valores. Esta busca foi feita, primeiramente, tomando em consideração só um dos parâmetros e a continuação eles em conjunto. Na primeira abordagem o AEIQ-AS consegue a realização das mesmas cirurgias em aproximadamente 31 semanas. Assim, observa se que há uma redução de aproximadamente 16,25 porcento do tempo. O número de operações fora do prazo, por sua vez, foi reduzido pelo modelo para 927 (13,04 porcento). Na abordagem simultânea, o AEIQ-AS, consegue uma diminuição do tempo total de alocação em 16,22 porcento e o número de operações fora do prazo em 9,76 porcento. Foram feitas, também, várias simulações da Unidade de Saúde mantendo as caraterísticas da lista de cirurgias para ver seu efeito no tempo total de alocação de todos os processos cirúrgicos. / [en] Currently, Health Units in a large number of countries in the world present service demand that exceed their real capacities. For this reason, is inevitable the emergence of the waiting lists. To prepare the planning of this in an optimized manner results in a substantial challenge due to the number of resources that should be considered. The case of chirurgical procedures is particularly critical by the number of resources needed for their realization. A small quantity of projects has been developed to fully manage these lists. The work developed in this Dissertation proposes the use of a model based on evolutionary algorithms with quantum inspiration for the automation and optimization of the planning of elective chirurgical procedures. This model, denominated Evolutionary Algorithm with Quantum Inspiration for the Health Field (AEIQ-AS), beyond patients and necessary resources for the successful completion of the chirurgical procedure allocation, pursue the reduction of the total time of realization of all the surgeries. The work presents also a tool that allows the modeling, in a simplified manner, of a Chirurgical Health Unit. This tool enables the realization of simulations with the objective of seeing the effect of different configurations of the resources in the Health Units. To validate the proposed model was created, in artificial mode and employing the simulation tool, a waiting list of 2000 surgeries. In case that the surgeries were realized following the arrival order, will be needed a little more than 37 weeks and will have 1066 surgeries out of time. Several experiments were conducted in order to optimize these values. This search was executed, firstly, considering only one of the parameters and, in continuation, all together. In the first approach, the AEIQ-AS obtains the realization of the same surgeries in approximately 16,25 percent of the time. The number of operations out of time was reduced by the model to 927 (13,04 percent). In the simultaneous approach, the AEIQAS achieves a decrease of the allocation total time in 16,22 percent and the number of operations out of time in 9,76 percent. It were done, also, several simulations of the Health Unit maintaining the characteristics of the surgeries list in order to look the effect in the allocation total time of all the chirurgical procedures.

[pt] Neste trabalho estudamos os algoritmos de Pontos Interiores para programação Linear. Publicados após o Algoritmo de Karmarkar. Que seguem, de algum modo, a Trajetória Central. São considerados tanto algoritmos Primais quanto Primais-Duais e também verificadas a eficácia da aplicação da metodologia de busca bidirecional. Estes métodos foram implementados e testados resolvendo um conjunto de problemas gerados aleatoriamente. Através da comparação dos resultados analisamos o desempenho das diferentes metodologias. / [en] We study here the Interior Points Algorithms for Linear Programming, developed after Karmarkar s Algorithm, which follow the Central Path. Both Primal and Primal-dual Algorithms are considered and also the efficiency of applying a bidirecional Search procedure is verified. These methods were implemented and tested solving a set of randomly generated problems. Comparing these results we analyze the performance of the methodologies.

[pt] O desenvolvimento de ambientes femto-celulares traz um considerável aumento geral na capacidade de sistemas heterogêneos, porque a distância entre o transmissor e receptor é pequena em comparação ao clássico desenvolvimento macro-celular. Mas as aplicações e serviços que estão vindo, precisam de ainda mais capacidade. Na procura desse ganho na capacidade, se criam técnicas e procedimentos que trabalham principalmente na camada física e MAC. Entre elas temos o reuso de frequência unitário, o qual não se logra explodir toda a capacidade do sistema, por isso implementamos o reuso de frequência fracionário que encara diretamente os problemas de interferência co-layer (entre femto-estações) e cross-layer (entre macro e femto estações). Este reuso fracionário de frequência se da só a nível de femto-estações, deixando à macro-estação que utilize toda a banda de frequência atribuída para a macro-célula. Os claros resultados obtidos no nível do SINR, mostram as melhoras. Tomando como base a plataforma anterior de reuso fracionário, analisamos as estrategias de programação do recurso frente a uma aplicação de vídeo. As estrategias pesquisadas são classificadas em: aquelas que tomam em consideração a qualidade do canal e aquelas que além da qualidade do canal consideram dentro da sua métrica requerimentos QoS, em especial o retardo máximo. Estas ultimas são as mais adequadas quando se opera com aplicações de tempo real (vídeo conferência e VoIP). Para contemplar a faixa de funcionamento das melhoras obtidas, todos os cenários de simulação foram sometidos a três intensidades de trafego (leve, médio e pesado). Medidas feitas da vazão, retardo, perda de pacotes e níveis de justiça na repartição mostram os benefícios do efeito combinado do reuso fracionário como o algoritmo de programação utilizado. Com os resultados obtidos fazemos uma escolha do padrão de reuso mais adequado junto com o algoritmo que proporcionam o melhor rendimento, dependendo do cenário (familiares ou empresariais) e da aplicação a utilizar. / [en] The development of femtocells environments brings a considerable increase in the capacity of the heterogeneous systems, because the distance between the transmitter and the receptor is smaller than the classic macrocell development. But the applications and services that are coming need more capacity yet. Looking for that gain of capacity, has been created techniques and methods that work mainly in the physical and MAC layer. Among them, the unitary frequency reuse, that does not achieve to exploit all the system s capacity. Hence we have implemented the fractional frequency reuse that aim directly the problems of co-layer interference (Between femto base stations) and cross-layer interference (Between macro and femto base stations). This fractional reuse of frequency is only among femto-stations, leaving the macro-station that use all the frequency band given for the macro cell. The bright results obtained in the SINR level show the improvements. Based on previous platform of fractional reuse, we analyze the scheduling strategies of the resource with a video application. The studied strategies are classified in: those that consider the quality of the channel and those that beyond the quality of channel consider QoS requirements in its metric, specially the maximum delay time. The last are more adequate when operating with video applications in real time (Video conference, VoIP). To see the operating range of the obtained improvements, all the simulation scenarios were submitted to three intensities of traffic (light, medium and heavy). Measurements of throughput, delay, packet loss ratio and fair levels in the distribution show the benefits of the joint effects of the fractional reuse as the scheduling algorithm used. With the obtained results, we do a selection of the more adequate reuse pattern together with the algorithm that provides the best performance, depending of the scenario (home or business environment) and the applications to use.

[pt] A exploração e desenvolvimento de um campo de petróleo é permeada de incertezas de diferentes naturezas. A incerteza mais básica que o gestor de um portfolio exploratório enfrenta é aquela relativa à existência (ou não) de petróleo em determinado prospecto. Tipicamente, incertezas técnicas tendem a ser reduzidas com investimentos em aquisição de informação, que são exercícios de opções de aprendizagem. Decorrente da estrutura de correlações presentes nos prospectos de um portfolio exploratório, o resultado da perfuração de um poço pioneiro potencialmente irá revelar informações adicionais sobre a probabilidade de existência (ou não) de petróleo em outros prospectos deste mesmo portfolio. Cada poço a ser perfurado pode ser entendido como uma opção de aprendizagem a ser exercida (ou não) a depender da sua probabilidade de sucesso. Neste contexto, um dos fatores determinantes na otimização da campanha exploratória é a escolha da sequência ideal de perfuração de poços. Tal escolha é mais complexa, quão maior for a quantidade e diversidade de prospectos no portfolio. Diante dessa realidade, este trabalho propõe uma modelagem que busca, através de Algoritmos Genéticos, otimizar a sequência de perfurações dos poços e, portanto, o valor do portfolio. O modelo proposto considera as interdependências e as especificidades de cada prospecto e usa como função objetivo, a ser maximizada, o valor presente do líquido (VPL). Opções e aprendizagem são os aspectos-chave por trás do modelo de otimização. O modelo foi avaliado em dez diferentes portfolios exploratórios e, em todos os casos, foi capaz de propor pelo menos uma sequência que apresentasse expressivos ganhos de VPL em relação ao caso-base. / [en] An oil field exploration and development campaign is bounded with different kinds of uncertainty. The most basic one that an E and P portfolio manager deals with is the one related to the existence (or not) of oil in a given prospect. Typically, technical uncertainties are related to learning, and tend to be reduced with investments on information acquisition. From the correlation pattern on the prospects in a given exploratory portfolio, follows that the results from one initial wildcat drilling will, potentially, reveal, additional information about the oil existence (or not) in other prospects in the same geological play. This way, each prospect to be drilled might be understood as a learning option to be exercised (or not) depending on its respective success probability. In such case, one of the main factors on optimizing the exploratory campaign is choosing the ideal drilling sequence. Such choice is more complex, as the quantity and diversity of the prospects increases. Given such background, the present work proposes a model that intends, using Genetic Algorithms, to optimize the drilling sequence and, as a consequence, the total portfolio value. The proposed model considers the interdependencies and each prospect specific aspects and has as an objective function (to be maximizes) the portfolio net present value (NPV). Options and learning are the main aspects underlying the optimization model. The model was evaluated on ten different exploratory portfolios and, in every case, was able to deliver at least one sequence that could represent expressive NPV gains compared to the basic scenario.

[pt] Esta dissertação investiga um sistema baseado em algoritmos genéticos e algoritmos culturais, aplicado ao processo de desenvolvimento de um campo de petróleo. O desenvolvimento de um campo de petróleo consiste, neste caso, da disposição de poços num reservatório petrolífero, já conhecido e delimitado, que permita maximizar o Valor Presente Líquido. Uma disposição de poços define a quantidade e posição de poços produtores e injetores e do tipo de poço (horizontalou vertical) a serem empregados no processo de exploração. O objetivo do trabalho é avaliar o desempenho de Algoritmos Genéticos e Algoritmos Culturais como métodos de apoio à decisão na otimização de alternativas de produção em reservatórios petrolíferos. Determinar a localização de novos poços de petróleo em um reservatório é um problema complexo que depende de propriedades do reservatório e critérios econômicos, entre outros fatores. Para que um processo de otimização possa ser aplicado nesse problema, é necessário definir uma função objetivo a ser minimizada ou maximizada pelo processo. No problema em questão, a função objetivo a ser maximizada é o Valor Presente Líquido (VPL). Para se estabelecer o VPL, subtrai-se os gastos com a exploração do valor correspondente ao volume de petróleo estimado da reserva. Devido à complexidade do perfil de produção de petróleo, exige-se a utilização de simuladores de reservatório para esta estimativa. Deste modo, um simulador de reservatórios é parte integrante da função de avaliação. O trabalho de pesquisa foi desenvolvido em quatro etapas: um estudo sobre a área de exploração de petróleo; um estudo dos modelos da inteligência computacional empregados nesta área; a definição e implementação de um modelo genético e cultural para o desenvolvimento de campo petrolífero e o estudo de caso. O estudo sobre a área de exploração de campo de petróleo envolveu a teoria necessária para a construção da função objetivo. No estudo sobre as técnicas de inteligência computacional definiu-se os conceitos principais sobre Algoritmo Genético e Algoritmo Cultural empregados nesta dissertação. A modelagem de um Algoritmo Genético e Cultural constitui no emprego dos mesmos, para que dado um reservatório petrolífero, o sistema tenha condições de reconhecê-lo e desenvolvê-lo, ou seja, encontrar a configuração (quantidade, localização e tipo de poços) que atinja um maior Valor Presente Líquido. Os resultados obtidos neste trabalho indicam a viabilidade da utilização de Algoritmos Genéticos e Algoritmos Culturais no desenvolvimento de campos de petróleo. / [en] This dissertation investigates a system based in genetic algorithms and cultural algorithms, applied to the development process of a petroleum field. The development of a petroleum field consists in the placement of wells in an already known and delimited petroleum reservoir, which allows maximizing the Net Present Value. A placement of wells defines the quantity and position of the producing wells, the injecting wells, and the wells type (horizontal or vertical) to be used in the exploration process. The objective of this work is to evaluate the performance of Genetic Algorithms and Cultural Algorithms as decision support methods on the optimization of production alternatives in petroleum reservoirs. Determining the new petroleum wells location in a reservoir is a complex problem that depends on the properties of the reservoir and on economic criteria, among other factors. In order to an optimization process to be applied to this problem, it s necessary to define a target function to be minimized or maximized by the process. In the given problem, the target function to be maximized is the Net Present Value (NPV). In order to establish the NPV, the exploration cost correspondent to the estimated reservoir petroleum volume is deducted. The complexity of the petroleum s production profile implies on the use of reservoirs simulators for this estimation. In this way, a reservoir simulator is an integrant part of the evaluation function. The research work was developed in four phases: a study about the petroleum exploration field; a study about the applied computational intelligence models in this area; the definition and implementation of a genetic and cultural model for the development of petroliferous fields and the case study. The study about the petroleum exploration field involved all the necessary theory for the building of the target function. In the study about the computational intelligence techniques, the main concepts about the Genetic Algorithms and Cultural Algorithms applied in this dissertation were defined. The modeling of Genetic and Cultural Algorithms consisted in applying them so that, given a petroleum reservoir, the system is capable of evolve and find configurations (quantity, location and wells type) that achieve greater Net Present Values. The results obtained in this work, indicate that the use of Genetic Algorithms and Cultural Algorithms in the development of petroleum fields is a promising alternative.

[pt] Narração interativa é uma forma de entretenimento digital em que os usuários participam do processo de compor e dramatizar uma história. Nesse contexto, a determinação do comportamento dos personagens de acordo com as suas preferências individuais pode ser uma maneira interessante de gerar histórias plausíveis, onde os personagens agem de forma crível. Diversidade de histórias e oportunidades de interação são requisitos fundamentais a serem considerados ao se projetar tais aplicações. Esta tese propõe a criação de uma arquitetura e de um protótipo para a geração e dramatização de enredos interativos não determinísticos, utilizando um modelo de emoções que não só sirva para guiar as ações dos personagens apresentadas pelo algoritmo de geração de planos, mas que também influencie a participação dos usuários. Além disso, para melhorar a qualidade e nível de diversidade das histórias, os personagens devem ser capazes de evoluir em termos de seus traços de personalidade durante o desenrolar da trama, como um reflexo dos eventos que realizam ou a que são expostos. / [en] Interactive storytelling is a form of digital entertainment in which users participate in the process of composing and dramatizing a story. In this context, determining the characters behaviour according to their individual preferences can be an interesting way of generating plausible stories where the characters act in a believable manner. Diversity of stories and opportunities for interaction are key requirements to be considered when designing such applications. This thesis proposes the creation of an architecture and a prototype for the generation and dramatization of interactive nondeterministic plots, using a model of emotions that not only serves to guide the actions of the characters presented by the plan generation algorithm, but also influences the participation of the users. Also, to improve the quality and diversity level of the stories, characters must be able to evolve in terms of their personality traits as the plot unfolds, as a reflection of the events they perform or are exposed to.

[pt] Este trabalho se concentra no desenvolvimento de mecanismos de leilões reveladores aleatorizados que buscam maximizar simultaneamente a receita e a eficiência econômica, ou função social, de leilões de demanda unitária. Em um leilão de demanda unitária, um conjunto de k bens é leiloado para um conjunto de n consumidores, com a restrição de que nenhum consumidor pode comprar mais de um bem. É apresentado um arcabouço para o desenvolvimento de mecanismos reveladores aleatorizados de complexidade polinomial derivados do mecanismo de Vickrey-Clarke- Groves, ou VCG. Ao invés de utilizar preços de reserva, estas variantes do VCG utilizam como parâmetro o número de bens que devem ser efetivamente vendidos. Os mecanismos se diferenciam entre si pela maneira como é feito o cálculo do número de bens que devem ser vendidos e permitem um balanço interessante entre receita e eficiência econômica, ao mesmo tempo que melhoram os resultados teóricos alcançados para o problema de Leilões de Demanda Unitária. / [en] This work focuses on the development of randomized truthful mechanisms that seek to maximize both the revenue and the economic efficiency, or social welfare, of unit-demand auctions. In a unit-demand auction a set of k items is auctioned to a set of n consumers and no consumer can purchase more than one item. A framework is presented for devising polynomial-time randomized truthful mechanisms that are based on a new variant of the Vickrey-Clarke-Groves (VCG) mechanism. Instead of using reserve prices, this variant of VCG uses the number of objects that we wish to sell as a parameter. The mechanisms obtained differ er from each other in the way they select the number of items to be sold and allow an interesting trade-off between revenue and economic effciency, while improving upon the stateof- the-art results for the Unit-Demand Auction problem (09).

[pt] Neste trabalho, apresentamos algoritmos aproximativos para dois problemas de otimização em árvores. Na primeira parte, consideramos o Problema de Atribuição de k-Hotlinks. Seja G= (V,E) um grafo direcionado acíclico representando um web site, onde nós correspondem a páginas e arcos correspondem a hyperlinks. Nesse contexto, hotlink são definidos como atalhos (novos arcos) adicionados às páginas de G de modo a reduzir o tempo gasto pelos usuários para alcançarem as informações desejadas. Neste trabalho consideramos o problema onde G é uma árvore enraizada e o objetivo é minimizar o tempo médio gasto pelos usuários atribuindo no máximo k hotlinks a cada nó. Para a versão mais estudada desse problema onde no máximo um hotlink pode ser atribuído a cada nó, provamos a existência de um FPTAS. Isso representa uma significante melhora em relação ao algoritmo com aproximação constante obtido recentemente em [Jacobs, WADS 2007]. Além disso, desenvolvemos o primeiro algoritmo com aproximação constante para a versão mais geral onde k hotlinks podem ser atribuídos a cada nó. Na segunda parte deste trabalho, consideramos o problema de computar estratégias eficientes para realizar buscas em árvores. Como uma generalização da tradicional busca binária em listas ordenadas, suponha que se deseja encontrar um nó específico (porém desconhecido) de uma árvore realizando consultas em seus arcos, onde cada consulta indica a extremidade do arco mais próxima ao nó desejado. Dada a probabilidade de cada nó ser aquele procurado, o objetivo é computar uma estratégia de busca que minimize o número esperado de consultas. Aplicações práticas desse problema incluem sincronização de file systems e testes de software. Apresentamos um algoritmo linear que obtém a primeira aproximação constante para esse problema. Isso representa uma melhora significativa em relação à O(log n)-aproximação anterior. / [en] Here we present a study on two optimization problems in trees: the k- Hotlink Assignment Problem and the problem of Binary Searching in Trees. As a result, we obtain improved approximation algorithms for both problem. The k-Hotlink Assignment Problem can be defined as follows. Let G = (V,E) be a directed acyclic graph representing a web site, where nodes correspond to pages and arcs to hyperlinks. In this context, hotlinks are defined as shortcuts (new arcs) added to web pages of G in order to reduce the time spent by users to reach their desired information. Here we consider the problem where G is a rooted directed tree and the goal is minimizing the expected time spent by users by assigning at most k hotlinks to each node. For the most studied version of this problem where at most one hotlink can be assigned from each node, we prove the existence of an FPTAS, improving upon the constant factor algorithm recently obtained in [Jacobs, WADS 2007]. In addition, we develop the first constant factor approximation algorithm for the most general version where k hotlinks can be assigned from each node. In the second part of this work, we consider the problem of computing efficient strategies for searching in trees. As a generalization of the classical binary search for ordered lists, suppose one wishes to find a (unknown) specific node of a tree by asking queries to its arcs, where each query indicates the endpoint closer to the desired node. Given the likelihood of each node being the one searched, the objective is to compute a search strategy that minimizes the expected number of queries. Practical applications of this problem include file system synchronization and software testing. Here we present a linear time algorithm which is the first constant factor approximation for this problem. This represents a significant improvement over previous O(log n)-approximation.