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:

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 log₂ n − n log₂log₂ 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 n²+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) .

Ligações externas[editar | editar código-fonte]

[Não_nomeado-y0ci-1-1] 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 .

[2] 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.

[3] Golumbic, M. C. (1980), Algorithmic Graph Theory and Perfect Graphs, Computer Science and Applied Mathematics, Academic Press, p. 159 .

[schensted-4] 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 .

[5] 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) .

[vk-6] 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 .

[7] 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) .

[ss81-8] 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)

[ans2015-9] 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)

[10] 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 .

[11] 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) .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]