Análise competitiva

Conceito

Em computação, a análise de complexidade de um algoritmo trata do estudo sobre os recursos consumidos pelos algoritmos ao executar sob diversas situações, como análise de pior cenário. Análise competitiva é um método criado para analisar algoritmos onlineen:online algorithm (que deve satisfazer uma sequencia imprevisível de requisitos, completando cada requisição sem prever o futuro). Nesta análise, a performance de um algoritmo online, é comparada à performance de um algoritmo ótimo offline que pode ver as sequencias de requisitos que seguirão. Um algoritmo é competitivo se sua razão de competitividade - a razão entre sua performance e da performance do algoritmo offline - é delimitado. Diferente da análise do pior caso, onde a performance de um algoritmo é medida apenas por entradas "difíceis", análise competitiva requer que um algoritmo desempenhe bem em entradas fáceis e difíceis, onde "difícil" e "fácil" são definidos pela performance do algoritmo ótimo offline.

Para muitos algoritmos, a performance depende não apenas do tamanho das entradas, mas também dos seus valores. Um exemplo disso é o algoritmo Quick sort, onde ordena uma cadeia de elementos. Esses algoritmos que dependem de dados são analisados por casos médios e pior caso. Análise competitiva é uma forma de fazer a análise de pior caso para um algoritmo online e algoritmos aleatorizados, que tipicamente dependem da entrada.

Algoritmos aleatorizados

Basicamente temos dois grandes grupo de algoritmos aleatorizados, algoritmo Monte Carlo e algoritmo Las Vegas. Basicamente, algoritmos Monte Carlo são algoritmos randomizados que nem sempre retornam a resposta correta, enquanto que o Las Vegas sempre retornam a resposta correta. Por exemplo, algoritmos I.A. para otimização que trazem bons resultados, mas não necessariamente o perfeito são categorizados como Monte Carlo, enquanto que, o que tem aleatoriedade mas são determinísticos quanto ao resultado final são considerados Las Vegas. Algoritmos genéticos em geral representam bem algoritmos do "grupo" Monte Carlo, enquanto que o Quicksort os algoritmos Las Vegas, onde pode ter a escolha do pivô de forma aleatória (como podemos ver no exemplo específico de quicksort abaixo).

Conceito de adversário

Em análise competitiva, imagina-se um "adversário" que deliberadamente escolhe a dificuldade da entrada, para maximizar a razão entre o custo do algoritmo em estudo e o custo de algum algoritmo ótimo. Adversários variam no poder do entre dois tipo que seguem nos sub-tópicos a seguir:

Adversário alheio

Adversário alheio, é aquele que não tem conhecimento das escolhas aleatórias feitas pelo algoritmo que está sendo comparado. Logo mais fraco, pois não consegue gerar, com garantias, que a entradas que dificultará o algoritmo em análise.

Adversário adaptativo

Adversário adaptativo, que tem total conhecimento de como o algoritmo funciona e seus estados internos em qualquer ponto da execução. Note que essa distinção é apenas significativa para algoritmos aleatorizados. Para um algoritmo determinístico, o adversário pode simplesmente computar em quais estados o algoritmo deve estar em qualquer momento no futuro, e escolher a dificuldade de acordo.

Exemplos

Podemos encontrar facilmente uma gama enorme de algoritmos aleatorizados na área de computação inteligência artificial, principalmente na área de Computação bioinspirada, onde um dos principais componentes é a aleatoriedade. Normalmente, esta aleatoriedade, é utilizada intencionalmente para simular algum evento da natureza ou comportamento de seres vivos, como seleção natural ou comportamento de enxames. No entanto, estes, precisam de uma certa bagagem, para quesitos didáticos, vamos utilizar algoritmos e problemas mais simples, assim podemos focar em entender a análise competitiva ao invés de se gastar muito esforço para entender os algoritmos em análise.

Quicksort

Por exemplo, o algoritmo quicksort escolhe um elemento chamado pivô, que é, em média, não tão distante do valor central dos dados sendo ordenados. Então o algoritmo separa os dados em duas pilhas, cada uma contém todos os elementos com valores menores que o pivô, e a outra contém o restante dos elementos. Se o algoritmo escolhe o pivô em de uma determinística (por exemplo, sempre escolhe o primeiro elemento da lista), então é fácil do adversário configurar dados de antemão de forma que o quicksort performará sobre o tempo do pior caso. Se, no entanto, o algoritmo escolhe de forma aleatória um elemento para ser o pivô, então um adversário sem conhecimento dos valores aleatórios que virão não pode configurar uma entrada que garanta a execução no tempo do pior caso.

Problema da atualização de lista

O primeiro problema clássico analisado com análise competitiva (Sleator & Tarjan 1985) é a en:list update problem: Dado uma lista de item e uma sequencia das requisições para os vários itens, minimize o custo de acessar a lista onde os elementos mais perto do começo da lista custam menos para serem acessados. Tipicamente, o custo de acessar um item é igual para sua posição lista, visto que por padrão utilizamos uma indexação crescente. Após um acesso, a lista pode ser configurada. A maioria das configurações tem um custo. O algoritmo move-para-frente simplesmente move o item requisitado para a frente da lista após o acesso, sem custo. O algoritmo de transposição troca o item acessado com o item imediatamente antes dele, também sem custo. Métodos clássicos de análise mostraram que transposição é ótima em alguns contextos. Na prática, o algoritmomove-para-frente, executa mal, de certa forma, comparado ao algoritmo ótimo, considerando o move-para-frente não pode nunca ser que o dobro do custo de um algoritmo ótimo.

No caso de uma requisição online de um servidor, algoritmos competitivos são usados para superar as incertezas do futuro. Que é, o algoritmo não sabe que o futuro, enquanto o adversário imaginário (o "competidor") sabe. De forma semelhante, algoritmos competitivos foram desenvolvidos para sistemas distrivuidos, onde o algoritmo tem que reagir para uma requisição que chega em um local, sem saber o que aconteceu em um local remoto. Essa configuração foi apresentada em (Awerbuch, Kutten & Peleg 1992).

Leia também

• (algoritmo online)
• Amortized analysis
• k-server
• online
• Problema da atualização de lista

Referências

• S., Michael. Introdução a teoria da computação. São Paulo: Cengage Learning. p. 261–348. ISBN 978-85-221-0499-4. Consultado em 7 de julho de 2015 
• Sleator, D.; Tarjan, R. (1985). Amortized efficiency of list update and paging rules. Communications of the ACM. 28. [S.l.: s.n.] pp. 202–208. doi:10.1145/2786.2793 .
• Aspnes, James (1998). «Competitive analysis of distributed algorithms». In: Fiat, A.; Woeginger, G. J. Online Algorithms: The State of the Art. Col: Lecture Notes in Computer Science. 1442. [S.l.: s.n.] pp. 118–146. doi:10.1007/BFb0029567 .
• Borodin, A.; El-Yaniv, R. (1998). Online Computation and Competitive Analysis. [S.l.]: Cambridge University Press. ISBN 0-521-56392-5 .
• Awerbuch, B.; Kutten, S.; Peleg, d. (1992). «Competitive Distributed Job Scheduling». ACM STOC, Victoria, BC, Canada. [S.l.: s.n.] .