Técnicas probabilísticas aplicadas em algoritmos de aproximação

Abstract

Resumo: Pesquisadores e cientistas têm percebido cada vez mais que a aleatoriedade é um componente essencial na modelagem e análise da natureza. Na ciência da computação não é diferente: o uso da aleatoriedade e de métodos probabilísticos desempenham um papel importante na ciência moderna. No caso da computação, um dos grandes usos da teoria de probabilidade é através de algoritmos de aproximação, uma vez que estamos mais interessados na execução em tempo polinomial do algoritmo do que na necessidade do mesmo em obter a resposta ótima para um certo problema. As formas mais usuais com que a aleatoriedade pode se comportar na ciência da computação são através do uso de algoritmos aleatorizados na resolução de problemas computacionais e nas análises de caso médio dos algoritmos, sejam eles aleatorizados ou não. Os quatro problemas estudados na primeira parte desta dissertação fazem uso de algoritmos aleatorizados, onde o leitor poderá obter uma visão geral sobre como escolhas com base em probabilidades são feitas durante a execução de um algoritmo e também em como se dá a análise de caso médio dos mesmos. Na segunda parte é analisado uma versão do problema da localização de p-hub medianas em que propomos um algoritmo com uma (4a)-aproximação, que apesar de não utilizar técnicas aleatorizadas em sua execução, tem sua análise feita sob aspectos probabilísticos.

Abstract: Researchers and scientists have increasingly realized randomness is an essential component in modeling and analysis of nature. In computer science it is no different: the use of randomness and probabilistic methods play a important role in modern science. In the case of computing, one of the main utilities of probability theory is by approximation algorithms, once we are more interested in a polynomial time algorithm than obtaining the optimal answer to a certain problem. The most usual ways that randomness comes to bear in computer science are by randomized algorithms when solving computational problems and in the average case analysis of algorithms, whether or not randomized. The four problems studied in the first part of this document use randomized algorithms, on that reader will get an overview of how probability-based choices are made during the execution of an algorithm and how is your average case analysis too. In the second part, we analyzed a version of p-hub median problem which we propose an algorithm with an (4a)-approximation, that despite not using randomized techniques during execution, its analysis is based on probabilistic aspects.