Modelo de árvore de decisão

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em complexidade computacional e complexidade de comunicação o modelo de árvore de decisão é o modelo de computação ou comunicação no qual um algoritmo ou processo de comunicação é considerado basicamente uma árvore de decisão, ou seja, uma sequência de operações ramificadas baseadas em comparações de quantidades, sendo as comparações atribuidas uma unidade de custo computacional.

As operações ramificadas são chamadas de "testes" ou "pedidos". Nesta configuração, o algoritmo em questão pode ser visto como uma computação de uma Função Booleana f: \{0,1\}^n \rightarrow \{0,1\} onde a entrada é uma série de pedidos e a saída é uma decisão final. Cada pedido é dependente de pedidos anteriores.

Várias variações de modelos de árvores de decisão podem ser utilizados dependendo da complexidade das operações permitidas na computação de uma única comparação e também pelo modelo de ramificação.

Modelos de árvore de decisão são instrumentos de estabelecimento do limite inferior para a complexidade computacional de certas classes de problemas computacionais e algoritmos: o limite inferior para análise de pior caso é proporcional a maior profundidade das árvores de decisão para todas as entradas possíveis de um certo problema computacional. A complexidade computacional de um problema ou um algoritmo em termos da árvore de decisão é chamado de complexidade da árvore de decisão ou complexidade do pedido'.

Classificação por complexidade de pedido computacional[editar | editar código-fonte]

Árvore de decisão simples[editar | editar código-fonte]

O modelo no qual toda decisão é baseada na comparação de dois números emum tempo constante é chamado simplesmente de modelo de árvore de decisão. Foi introduzido para estabelecer a complexidade computacional de Ordenação e busca.[1]

A ilustração mais simples desta técnica de limite inferior é para o problema do menor número entre n números usando apenas comparações. Neste caso o modelo de árvore de decisão é uma árvore binária. Algoritmos para este problema de busca pode resultar em n saídas diferentes (porque qualquer um dos n números podem ser o menor). Sabe-se que a profundidade de uma árvore binária com n folhas é pelo menos \log n, o que nos dá um limite inferior de \Omega(\log n) para o problema da busca. Porém este limite inferior é flexível, desde que o argumento seguinte mostre que pelo menos n - 1 comparações sejam necessárias: Antes que o menor número possa ser determinado, todo número exceto o menor deve "perder" (neste caso, ser maior na comparação) em pelo menos uma comparação.

Da mesa forma podemos provar o limite inferior \Omega(n \log n) para ordenação. Neste caso, a existência de vários algoritmos de ordenação por comparação tendo esta complexidade de tempo, como o mergesort e o heapsort, mostram que o limite é pouco flexível.

Árvore de decisão linear[editar | editar código-fonte]

Árvores de decisão lineares, assim como as árvores de decisão simples, fazem uma decisão ramificada baseada em uma série de valores dados como entrada. Oposto à forma como árvores binárias funcionam, as árvores de decisão lineares têm três ramos de saída. A função linear f(x_1, \dots, x_i) é testada e as decisões ramificadas são feitas baseadas no sinal da funão (negativo, positivo ou 0).

Geometricamente, f(x) define um hiperplano em Rn. Uma série de valores de entrada que alcançam qualquer nó representa a interseção dos meio-planos definidos pelos nós.

Árvore de decisão algébrica[editar | editar código-fonte]

Árvores de decisão algébricas são uma generalização da árvore de decisão linear para permitir funções polinomiais de grau d. Geometricamente, o espaço é dividido em séries semi-algébricas (uma generalização do hiperplano). A avaliação da complexidade é mais difícil.

Classificação por modelo de computação de pedido[editar | editar código-fonte]

Árvore de decisão determinística[editar | editar código-fonte]

Se a saída de uma árvore de decisão é f(x), para todo x\in \{0,1\}^n , então a árvore de decisão computa f. A profundidade de uma árvore é o número máximo de edidos que podem acontecer antes que uma folha seja alcançada e um resultado seja obtido. D(f), a complexidade de f na ávore de decisão determinística é a menor profundidade de todas as árvores de decisão determinísticas que computam f.

Árvore de decisão randomizada[editar | editar código-fonte]

Um meio de definir uma árvore de decisão randomizada é adicionando novos nós a uma árvore, cada um controlado por uma certa probabilidade p_i. Outra definição equivalente é selecionar uma árvore de decisão completa pelo começo dentre um conjunto de árvores de decisão baseando-se em uma distribuição de probabilidade. De acordo com essa segunda definição, a complexidade das árvores randomizadas é definida como a maior profundidade entre todas as árvores associadas à probabilidade maior que 0. R_2(f) é definido como a complexidade da árvore de menor profundidade cujo resultado é f(x) com probabilidade de pelo menos 2/3 para todos os x\in \{0,1\}^n (ou seja, com erro delimitado bilateralmente).

R_2(f) é conhecido como complexidade de árvore de decisão randomizada de Monte Carlo, porque sue resultado pode ser errado de acordo com o erro limitado bilateralmente. A complexidade da árvore de Las Vegas R_0(f) mede a profundidade esperada de uma certa árvore que deve ser correta (ou seja, contém zero erro). Também há a versão de erro unilateralmente delimitado conhecido como R_1(f).

Árvore de Decisão não-determinística[editar | editar código-fonte]

A complexidade da árvore de decisão não-determinística é conhecida como complexidade de certificado (certificado é uma cadeia que certifica uma resposta à computação, ou a associação da cadeia a uma linguagem). Ela mede o número de bits de entrada que um algoritmo não-determinístico precisaria olhar para avaliar uma função com certeza.

Árvore de decisão quântica[editar | editar código-fonte]

A complexidade de uma árvore de decisão quântica Q_2(f) é a profundidade da árvore quântica de menor profundidade que dá o resultado f(x) com a probabilidade de pelo menos 2/3 para todo x\in \{0,1\}^n . Outra quantidade, Q_E(f), é definida como a profundidade da árvore de menor profundidade que dá o resultado f(x) com probabilidade 1 em todos os casos (ou seja, computa f exatamente. Q_2(f) e Q_E(f) são comumente conhecidas como complexidades de pedidos quânticos, porque a definição direta de uma árvore de decisão quântica é mais complicada do que o caso clássico. Da mesma forma que o caso randomizado, definimos Q_0(f) e Q_1(f).

Relação entre diferentes modelos[editar | editar código-fonte]

Segue imediatamente as definições de que todas as funções f Booleanas de n-bits, Q_2(f) \leq R_2(f) \leq R_1(f) \leq R_0(f) \leq D(f) \leq n, eQ_2(f) \leq Q_E(f) \leq D(f) \leq n.

Blum and Impagliazzo,[2] Hartmanis and Hemachandra,[3] e Tardos[4] descobriram que D(f) \leq R_0(f)^2. Noam Nisan descobriu que a árvore randomizada de Monte Carlo também é polinomialmente relacionada à complexidade da árvore de decisão determinística: D(f) = O(R_2(f)^3).[5] (Nisan também mostrou que D(f) = O(R_1(f)^2).) Um corolário deste resultado é que R_0(f) = O(R_2(f)^3). Essa inequalidade pode ser flexível, porém; não há nenhum exemplo conhecido de uma separação super-linear entre R_0(f) eR_2(f).[6]

A complexidade da árvore de decisão Q_2(f) também é polinomialmente relacionada à D(f). Midrijanis mostrou que D(f) = O(Q_E(f)^3),[7] [8] improving a quartic bound due to Beals et al.[9] Beals et al. também mostrou que D(f) = O(Q_2(f)^6), e isto ainda é o melhor limite conhecido. Porém, a maior lacuna entre pedidos determinísticos e quânticos é apenas quadrático. Uma lacuna quadrática é atingida para o Algoritmo de Grover; D(OR_n) = n enquanto Q_2(OR_n) = \Theta(\sqrt{n}).

É importante perceber que estas relacões polinomiais são válidas apenas para funções Booleanas totais. Para For funções booleanas parciais, que contêm um subconjunto de \{0,1\}^n, uma separação exponencial entre Q_E(f) e D(f) é possível; o primeiro exemplo de tal problema foi descoberto por Deutsch and Jozsa. O mesmo exemplo também dá uma separação exponencial entre R_2(f) e D(f).

Essas relações podem ser sumarizadas pelas seguintes inequalidades, das quais são verdadeiras até fatores constantes:[8]

Referências

  1. "Data structures and algorithms, por Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman
  2. a b Blum, M.; Impagliazzo, R. (1987). "Generic oracles and oracle classes". Proceedings of 18th IEEE FOCS: 118–126. 
  3. a b Hartmanis, J.; Hemachandra, L. (1987), "One-way functions, robustness, and non-isomorphism of NP-complete sets", Technical Report DCS TR86-796, Cornell University 
  4. a b Tardos, G.. (1989). "Query complexity, or why is it difficult to separate NPA ∩ coNPA from PA by random oracles A?". Combinatorica 9: 385–392 pp.. DOI:10.1007/BF02125350.
  5. a b c Nisan, N. (1989). "CREW PRAMs and decision trees". Proceedings of 21st ACM STOC: 327–335. 
  6. Santha, Miklos (1995), On the Monte Carlo Boolean Decision Tree Complexity of Read-Once Formulae, http://www.lri.fr/~santha/Papers/s95.ps.gz  (ps format)
  7. Midrijanis, Gatis (2004), "Exact quantum query complexity for total Boolean functions", arXiv:quant-ph/0403168 
  8. a b c d Midrijanis, Gatis (2005), "On randomized and quantum query complexities", arXiv:quant-ph/0501142 
  9. a b c Beals, R.; Buhrman, H.; Cleve, R.; Mosca, M.; de Wolf, R.. (2001). "Exact quantum query complexity for total Boolean functions". Journal of ACM 47: 778–797 pp..
  10. H. Buhrman, R. Cleve, R. de Wolf, and Ch. Zalka. Bounds for Small-Error and Zero-Error Quantum Algorithms. In 40th IEEE Symposium on Foundations of Computer Science (FOCS'99), pp.358-368. cs.CC/9904019, 1999.
  11. S. Aaronson. Quantum Certificate Complexity. IEEE Conference on Computational Complexity, pp. 171-178, 2003.

Ver também[editar | editar código-fonte]