Orientador : Prof. Dr. Renato José da Silva Carmo / Coorientador : Prof. Dr. André Luis Vignatti / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 25/11/2016 / Inclui referências : f. 91-94 / Área de concentração: Ciência da computação / 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 (4_)-aproximação, que apesar de não utilizar técnicas aleatorizadas em sua execução, tem sua análise feita sob aspectos probabilísticos. Palavras-chave: problemas de otimização, algoritmos de aproximação, algoritmos aleatorizados, análise de caso médio, análise probabilística de algoritmos. / 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 (4_)-approximation, that despite not using randomized techniques during execution, its analysis is based on probabilistic aspects. Keywords: optimization problems, approximation algorithms, randomized algorithms, average case analysis, probabilistic analysis of algorithms.
| Identifer | oai:union.ndltd.org:IBICT/oai:dspace.c3sl.ufpr.br:1884/46257 |
| Date | January 2016 |
| Creators | Bordini, Camile Frazão |
| Contributors | Vignatti, André Luís, Universidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Informática, Carmo, Renato Jose da Silva, 1965- |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | 94 p. : il., application/pdf |
| Source | reponame:Repositório Institucional da UFPR, instname:Universidade Federal do Paraná, instacron:UFPR |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | Disponível em formato digital |
Page generated in 0.0024 seconds