Máxima subsequência crescente
Em ciência da computação, o problema da maior subsequência crescente, ou máxima subsequência crescente consiste em encontrar um subsequência de números, dada um sequência, na qual seus elementos estão ordenados do menor para o maior, e a sequência é a mais longa possível. Este subsequência não é necessariamente contígua, ou o única. Este problema é estudado no contexto das várias disciplinas relacionadas com a matemática, incluindo algoritmo, teoria da matriz aleatória, teoria de representação e física.[1] O problema pode ser resolvido em tempo O(n log n), onde n denota o comprimento da seqüência de entrada.
Exemplo
[editar | editar código-fonte]Nos 16 primeiros termos da sequência de Van der Corput:
- 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
um maior subsequência crescente é
- 0, 2, 6, 9, 11, 15.
Este subsequência tem tamanho igual a 6, pois a sequência de entrada não contém subsequências de sete elementos ou mais. Porém, esta subsequência não é única e existem outras de mesmo tamanho dentro deste vetor de números. Por exemplo,
- 0, 4, 6, 9, 11, 15 ou
- 0, 2, 6, 9, 13, 15 ou
- 0, 4, 6, 9, 13, 15
são outras subsequências de tamanho igual a 6, na mesma seqüência de entrada.
Relações com outros problemas
[editar | editar código-fonte]O problema da maior subsequência crescente está intimamente relacionado com o problema maior subsequência comum, que tem uma solução por programação dinâmica em tempo quadrático: a maior subsequência comum de uma seqüência S é a maior subsequência comum de S e T, onde T é o resultado de ordenar S. No entanto, para o caso especial em que a entrada é uma permutação dos inteiros 1, 2, ..., n, esta abordagem pode ser muito mais eficiente, levando a uma complexidade de tempo O(n log log n).[2]
O maior clique em num grafo de permutação é definido pela maior subsequência decrescente da permutação que define o grafo; maior subsequência decrescente é equivalente em complexidade computacional, pela negação de todos os números, ao problema da maior subsequência crescente. Portanto, uma solução para o problema da maior subsequência crescente pode ser utilizada para resolver o problema do clique de forma eficiente na permutação gráficos.[3]
Na correspondência de Robinson–Schensted entre permutações e o diagrama de Young, o comprimento da primeira linha do diagrama correspondente a uma permutação é igual ao comprimento da maior subsequência crescente de permutação, e o comprimento da primeira coluna é igual ao comprimento do maior subsequência decrescente.[4]
Algoritmos eficientes
[editar | editar código-fonte]O algoritmo descrito abaixo, resolve o problema da maior subsequência crescente de forma eficiente, utilizando matrizes e busca binária. Ele processa a sequência de elementos em ordem, mantendo o maior subsequência encontrada até então. A sequência é indicada de valores de X[0], X[1], etc. Em seguida, após o processamento X[i], o algoritmo terá valores armazenados em duas matrizes:
- M[j] — armazena o índice k de o menor valor de X[k] tal que existe uma subsequência crescente de comprimento j terminando em X[k] no intervalo k ≤ i. Note que j ≤ (i+1), porque j ≥ 1 representa o comprimento de uma subsequência crescente, e k ≥ 0 representa o índice do seu término.
- P[k] — armazena o índice do predecessor de X[k] na maior subsequência terminando em X[k].
Além disso, o algoritmo armazena uma variável L representando o comprimento do maior subsequência encontrada até então. O algoritmo a seguir utiliza uma numeração iniciada em zero, portanto, para esclarecer, M é preenchido com M[0], que não é utilizado, de modo que M[j] corresponde a uma subsequence de comprimento j. Uma implementação real pode ignorar M[0] e ajustar os índices de acordo.
Observe que, em qualquer ponto do algoritmo, a sequência
- X[M[1]], X[M[2]], ..., X[M[L]]
é crescente. Pois, se há uma subsequência crescente de comprimento j ≥ 2, terminando em X[M[j]], então também existe é uma subsequência de comprimento j-1, terminando em um menor valor: ou seja, um valor terminando em X[P[M[j]]]. Assim, podemos fazer uma busca binária nessa sequência, em tempo logarítmo.
O algoritmo, procede da seguinte forma:
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1d/LISDemo.gif/400px-LISDemo.gif)
P = array of length N M = array of length N + 1
L = 0 for i in range 0 to N-1: // Binary search for the largest positive j ≤ L // such that X[M[j]] < X[i] lo = 1 hi = L while lo ≤ hi: mid = ceil((lo+hi)/2) if X[M[mid]] < X[i]: lo = mid+1 else: hi = mid-1
// After searching, lo is 1 greater than the // length of the longest prefix of X[i] newL = lo
// The predecessor of X[i] is the last index of // the subsequence of length newL-1 P[i] = M[newL-1] M[newL] = i
if newL > L: // If we found a subsequence longer than any we've // found yet, update L L = newL
// Reconstruct the longest increasing subsequence S = array of length L k = M[L] for i in range L-1 to 0: S[i] = X[k] k = P[k]
return S
Pelo fato do algoritmo executar uma busca binária simples por elementos da sequência, o tempo total da complexidade do algoritmo pode ser expresso usando notação Big-O como O(n log n). Fredman (1975) descreve uma variante deste algoritmo, que credita às Donald Knuth; na variante que ele estuda, o algoritmo testa se a cada valor de X[i] pode ser usado para estender o atual maior aumento da seqüência, a constante de tempo, antes de fazer a pesquisa binária. Com esta modificação, o algoritmo usa no máximo n log2 n − n log2log2 n + O(n) comparações no pior caso, que é óptimo para um algoritmo baseado em comparação com o fator constante O(n).[5]
Limites de Comprimento
[editar | editar código-fonte]De acordo com o teorema de Erdős–Szekeres, qualquer seqüência de n2+1 números inteiros distintos tem um subsequência crescente ou decrescente de comprimento n + 1.[1] Para entradas em que cada permutação de entrada é igualmente provável, o tamanho esperado da maior subsequência crescente é 2√n. [6] À medida que n se aproxima do infinito, o limite do comprimento da maior subsequência crescente de uma sequência permutada aleatoriamente contendo n itens tem uma distribuição que se aproxima da distribuição de Tracy–Widom, que é a distribuição do maior autovalor de uma matriz aleatória no conjunto unitário gaussiano.[7]
Algoritmos Online
[editar | editar código-fonte]O problema da maior subsequência crescente também tem sido estudada na definição de algoritmos online, na qual os elementos de uma seqüência de variáveis aleatórias independentes com distribuição contínua F – ou, em alternativa, os elementos de uma permutação aleatória – são apresentadas uma de cada vez para um algoritmo que deve decidir se deseja incluir ou excluir cada elemento, sem o conhecimento dos elementos. Nesta variante do problema, é possível conceber um procedimento óptimo de seleção que, dada uma amostra aleatória de tamanho n como entrada, irá gerar uma sequência crescente com o tamanho máximo esperado √2n. [8] O tamanho da subsequência crescente selecionada por este procedimento ideal tem variação de, aproximadamente √2n/3, e a sua distribuição é assintoticamente normal depois que de centralizar e escalar.[9] Os mesmos resultados assimtóticos mantém limites precisos para o problema correspondente, configurando um processo de Poisson.[10] Um refinamento no processo no processo de configuração da Poisson é dada através da prova de um teorema do limite central para a optimização do processo de seleção que detém, com uma adequada normalização, no mais completo sentido do que seria de esperar. A prova produz não apenas o funcional "correto" teorema do limite mas também produz uma matriz de covariância (singular) do processo tridimensional resumindo todos os outros processos de interação. [11]
Veja também
[editar | editar código-fonte]- Ordenação paciente, uma técnica eficiente para encontrar o comprimento da maior subsequência crescente.
- Monóide Plactico, um sistema algébrico definido por transformações que preservam o comprimento da maior subsequência crescente.
- Anatoly Vershik, um matemático russo que estudou aplicações da teoria dos grupos ao problema da maior subsequência crescente.
- Maior subsequência comum
- Maior subsequência alternada
Referências
[editar | editar código-fonte]- ↑ a b Aldous, David; Diaconis, Persi (1999), «Longest increasing subsequences: from patience sorting to the Baik–Deift–Johansson theorem», Bulletin of the American Mathematical Society, 36 (04), pp. 413–432, doi:10.1090/S0273-0979-99-00796-X.
- ↑ Hunt, J.; Szymanski, T. (1977), «A fast algorithm for computing longest common subsequences», Communications of the ACM, 20 (5), pp. 350–353, doi:10.1145/359581.359603.
- ↑ Golumbic, M. C. (1980), Algorithmic Graph Theory and Perfect Graphs, Computer Science and Applied Mathematics, Academic Press, p. 159.
- ↑ Schensted, C. (1961), «Longest increasing and decreasing subsequences», Canadian Journal of Mathematics, 13, pp. 179–191, MR 0121305, doi:10.4153/CJM-1961-015-3.
- ↑ Fredman, Michael L. (1975), «On computing the length of longest increasing subsequences», Discrete Mathematics, 11 (1), pp. 29–35, doi:10.1016/0012-365X(75)90103-X
|author-link=
e|authorlink=
redundantes (ajuda);|DOI=
e|doi=
redundantes (ajuda) . - ↑ Vershik, A. M.; Kerov, C. V. (1977), «Asymptotics of the Plancheral measure of the symmetric group and a limiting form for Young tableaux», Dokl. Akad. Nauk USSR, 233, pp. 1024–1027.
- ↑ Baik, Jinho; Deift, Percy; Johansson, Kurt (1999), «On the distribution of the length of the longest increasing subsequence of random permutations», Journal of the American Mathematical Society, 12 (4), pp. 1119–1178, doi:10.1090/S0894-0347-99-00307-0
|DOI=
e|doi=
redundantes (ajuda) . - ↑ Samuels, Stephen. M.; Steele, J. Michael (1981), «Optimal Sequential Selection of a Monotone Sequence From a Random Sample», Annals of Probability, 9 (6), pp. 937–947, doi:10.1214/aop/1176994265
|DOI=
e|doi=
redundantes (ajuda) - ↑ Arlotto, Alessandro; Nguyen, Vinh V.; Steele, J. Michael (2015), «Optimal online selection of a monotone subsequence: a central limit theorem», Stochastic Processes and their Applications, 125 (9), pp. 3596-3622, doi:10.1016/j.spa.2015.03.009
|DOI=
e|doi=
redundantes (ajuda) - ↑ Bruss, F. Thomas; Delbaen, Freddy (2001), «Optimal rules for the sequential selection of monotone subsequences of maximum expected length», Stochastic Processes and their Applications, 96 (2), pp. 313–342.
- ↑ Bruss, F. Thomas; Delbaen, Freddy (2004), «A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length», Stochastic Processes and their Applications, 114 (2), pp. 287–311, doi:10.1016/j.spa.2004.09.002
|DOI=
e|doi=
redundantes (ajuda) .