Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como calcular a maior variação positiva de uma sequência?

+1 voto
84 visitas
perguntada Mai 25 em Ciência da Computação por João Gabriel Souza (76 pontos)  

Implemente a versão força bruta do problema e a versão divisão e conquista.

Compartilhe

2 Respostas

+1 voto
respondida Mai 25 por João Gabriel Souza (76 pontos)  
editado Jul 6 por João Gabriel Souza

Introdução
Seja uma sequência \(S\) de \(x\) pontos. Apresenta-se os índices da sequência \(S\), os pontos \(x\), que geram a maior variação positiva nessa sequência.

Para ilustrar apresenta-se o seguinte exemplo:

Suponha que \(x_{0} = 3\), \(x_{1} = 5\), \(x_{2} = 2\), \(x_{3} = 9\) e \(x_{4} = 10\). Logo pode-se observar que o resultado procurado é índice 2 \((x_{2} = 2)\) e o índice 4 \((x_{4}=10)\), com variação positiva de 8.

Força Bruta

A força bruta é um procedimento direto para resolver um problema tendo como base a definição deste problema e os conceitos diretamente envolvidos. Na ciência da computação, busca por força bruta ou busca exaustiva, também conhecido como gerar e testar, é uma técnica de solução de problemas trivial, porém muito geral que consiste em enumerar todos os possíveis candidatos da solução e checar cada candidato para saber se ele satisfaz o enunciado do problema.

Para aplicar busca por força bruta para uma classe específica de problemas, é preciso implementar quatro procedimentos, sendo estes: primeiro, próximo, válido, e saída. Estes procedimentos devem ter como parâmetro os dados \(P\) para a instância do problema que será resolvido, e deve fazer o seguinte:

  1. primeiro \((P)\): gera o primeiro candidato à solução de \(P\).
  2. próximo \((P, C)\): gera o próximo candidato de \(P\) depois de \(C\).
  3. válido \((P, C)\): checa se o candidato \(C\) é a solução de \(P\).
  4. saída \((P, C)\): usa a solução \(C\) de \(P\) como for conveniente para a aplicação.

O procedimento próximo também deve dizer quando não há mais candidatos à \(P\), após o \(C\) atual. Uma maneira conveniente de fazer isto é retornando um "candidato nulo", um valor de dados comum \(Λ\) que é distinto de qualquer outro candidato real. Da mesma maneira primeiro deve retornar \(Λ\) se não houver nenhum candidato para a instância \(P\).

O código força bruta para encontrar a maior variação positiva de uma sequência implementado em Python segue abaixo.

Em primeiro plano importa-se a biblioteca \(numpy\) para gerar uma distância máxima de números infinitamente pequenos, como critério de começo do algorítimo.

import numpy as np

Posteriormente, defini-se a função \(diff\_max\) e parâmetros que irão compor a iteração do processo.

def diff_max(x):
n = len(x)
dist_max = -np.inf
diff =[]

A função \(diff\_max\) possui apenas um parâmetro que corresponde a \(x\) a lista que compõe a sequência de números analisados.

Em seguida utiliza-se da iteração ao longo da sequência, um \(for\) de \(i\) que vai do primeiro elemento até o penúltimo e um \(for\) de \(j\) que vai de \(i+1\) até o último elemento. Esse intervalo garante que a iteração não ultrapasse os limites da sequência, pois realiza-se a diferença positiva entre um a um dos elementos. A primeira condicionante atribui ao \(dist\_max\) a variação do momento da iteração. Nesta condicionante cria-se uma lista de índices \(i\) e \(j\) e uma valor atribuído a diferença. A segunda condicionante encontra o máximo dessas diferenças positivas e posteriormente armazena o valor de \(diff\). No final retorna \(diff\) que é uma lista de uma lista de índices e do valor máximo encontrado.

for i in range(0,n-1):
    for j in range(i+1, n):
        if x[j] - x[i] == dist_max:
            diff.append([[i,j], dist_max])
        if x[j] - x[i] > dist_max:
            dist_max = x[j] - x[i]
            diff = [[i,j], dist_max]
return (diff)

A última parte do código define a lista e chama a função que calcula a distância positiva máxima entre os números \(x\) que compõem a lista que contem a sequência \(S\).

if __name__ == '__main__':
  x = [5, 3, 8, 1, 9, 7, 2, 4, 6, 7, 2, 4, 6, 8, 9, 8, 7]
  print(diff_max(x))

O resultado encontrado para este exemplo é:

[[3, 4], 8, [[3, 14], 8]]

O resultado mostra que a diferença entre o índice 4 e o índice 3 resultou em um valor de 8 unidades, assim como a diferença entre os índices 14 e 3.

Observa-se que o algoritmo acima tem complexidade na ordem de \(O(n^2)\), pois há uma comparação de \(n\) com \(n-1\), devido aos dois \(for\) do código. Sendo a complexidade \(O(n^2)\) assintótica.

Divisão e Conquista

A estratégia de dividir para conquistar transforma o problema em subproblemas que são similares ao problema original, então resolva-os de forma recursiva. Como a estratégia de dividir para conquistar resolve subproblemas recursivamente, cada problema deve ser menor que o problema original. O algoritmo de divisão e conquista possui três partes:

  1. Divida o problema em subproblemas que são menores do que problema original.
  2. Conquiste os subproblemas resolvendo-os recursivamente. Se estes subproblemas são menores o suficiente resolva-os como caso básico.
  3. Combine, concatene as soluções dos subproblemas em uma solução do problema original.

Para encontrar a maior diferença positiva entre dois números de uma sequência utilizando a estratégia de divisão e conquista. Fazer-á um código que gere um merge sort e ordena a sequência, depois o código irá comparar os primeiros números com os últimos da lista. Assim gerando a mair diferença positiva entre dois números de uma sequência.

Merge Sort

Como neste exercício usa-se divisão e conquista para ordenar, precisamos decidir quais serão nossos subproblemas. O problema completo é ordenar um array inteiro. Vamos dizer que um subproblema é ordenar um subarray. Em particular, iremos pensar em um subproblema como ordenar o subarray começando de um índice \(p\) e continuamos através do índice \(r\). Isso será conveniente para termos uma notação para um subarray, então vamos dizer que \(array[p..r] \) denota o subarray de array.

A figura abaixo Ilustra o problema:

A imagem será apresentada aqui.

Fonte: Khanacademy

O código em Python segue abaixo:

Em primeiro plano importa-se a biblioteca \(numpy\).

import numpy as np

Na segunda parte do código defini-se a função que irá mergiar (concatenar os subproblemas). Nessa função o algoritmo concatena os subarrays mencionados na figura acima.

def merge(x, y):
nx = len(x)
ny = len(y)
z = np.empty([nx + ny], int)
i = 0
j = 0
cont = -1;
while ((i <= nx - 1) and (j <= ny - 1)):
    cont = cont + 1
    if (x[i] < y[j]):
        z[cont] = x[i]
        i = i + 1
    else:
        z[cont] = y[j]
        j = j + 1

if (cont < nx + ny - 1):
    if (i <= nx - 1):
        for k in range(cont + 1, nx + ny):
            z[k] = x[i]
            i = i + 1
    else:
        for k in range(cont + 1, nx + ny):
            z[k] = y[j]
            j = j + 1
    return z

A função abaixo realiza-se a divisão recursivamente dos subproblemas, transformando a sequência em partes cada vez menores. Observa-se a recursividade ao ver que a função chama ela mesma, transformando uma sequência maior em pequenas subsequências, como pode ser visto na ilustração acima.

def merge_sort(a):
n = a.size
if (n > 1):
    b = a[0:n // 2]
    c = a[n // 2:n]
    b = merge_sort(b)
    c = merge_sort(c)
    a = merge(b, c)
return a

Após a ordenação dos vetores, realizada pela estratégia de divisão e conquista pelo merge sort, a última função armazena os primeiros números em um vetor que se chama \(lista1\) e os últimos números em um vetor que se chama \(lista2\). Ao fazer a diferença dos vetores na \(lista2\) com os da \(lista1\) obtemos a maior diferença. Observa-se que se os números iniciais são iguais aos finais o código os armazena nas lista determinadas.

 def order_diff_max(d):
    control = list(d)
    n = len(d)
    lista1 = []
    lista2 = []
    classificado = merge_sort(d)
    dif = classificado[n-1] - classificado[0]
    for i in range(0, n):
        if classificado[0] == d[i]:
            lista1.append(i)
        if classificado[n - 1] == d[i]:
            lista2.append(i)
    return [lista1, lista2, dif]  

Abaixo é chamada as funções e demonstrado o resultado.

if __name__ == '__main__':
  x = np.array([5, 3, 8, 1, 9, 7, 2, 4, 6, 7, 2, 4, 6, 8, 9, 8, 7])

  print "Merge sort:"

  print merge_sort(x)

  print "order_diff_max:"

  print order_diff_max(x)

Resultado:

Merge sort:
[1 2 2 3 4 4 5 6 6 7 7 7 8 8 8 9 9]
order_diff_max:
[[3], [4, 14], 8]

Observa-se que o resultado é o mesmo do encontrado no problema de força bruta, a diferença entre os índices 4 e 3 e os índices 14 e 3 da sequência apresentam 8 unidades.

A diferença deste algoritmo para o de força bruta é que como o de força bruta compara cada elemento da sequência este possui complexidade na ordem de \(O(n^2)\), já o algoritmo que usa ordenação possui menor complexidade. Observa-se que o algoritmo merge sorte possui complexidade \(O(n\ log\ n)\). Note que a relação de recorrência é :

\[T(n) = 2T\left( \frac{n}{2}\right) + O(n)\]

Com \(T(1) = 0\), sendo esse o caso 2 do Teorema Mestre. Como o código apresenta mais uma operação linear para guardar os primeiros e últimos valores da sequência e depois tirar a diferença este código possui mais uma complexidade de ordem \(n\), porém a complexidade assintótica continua a mesma que é de \(O(n\ log\ n)\).

Referências
Força Bruta .
Divisão e Conquista.
Merge Sort.

comentou Jul 5 por Caue (226 pontos)  
A explicação do exercício está excelente.
Em relação ao código, farei dois comentários:
1 - Se a gente testar a lista [40, 76, 95, 15, 7, 6, 26, 92, 5, 77], vai dar pra ver que os dois métodos acham valores diferentes: Enquanto o força bruta busca variação apenas do menor para o maior índice, o order_diff verifica nos dois sentidos. Qual das duas interpretações queremos?
2 - No order_diff, o método merge_sort(d) é chamado diversas vezes. Isto compromete a complexidade. Que tal atribuir o resultado a alguma variável?
comentou Jul 5 por João Gabriel Souza (76 pontos)  
Olá Cauê! Obrigado pelas observações!
Fiz as alterações sugeridas no seu comentário 2.
Quanto ao comentário 1 eu havia observado que se o menor número da sequência original está a frente do maior número da sequência original, os dois códigos darão resultados diferentes. Conforme foi colocado na sequência que você apresentou. Isso ocorre, pois foi pedido no exercício a maior variação positiva. Porém, para que não fique diferente os valores, pode-se forçar o código força bruta colocando os absolutos nas diferenças entre \(j\) e \(i\). Abaixo segue o código alterado. Não alterei em cima, pois o exercício cobra a maior variação positiva.
Obrigado pelos comentários!
0 votos
respondida Jul 5 por João Gabriel Souza (76 pontos)  

Segue código alterado do método Força Bruta:

import numpy as np

def diff_max(x):
    n = len(x)
    dist_max = -np.inf
    diff =[]
    for i in range(0,n-1):
        for j in range(i+1, n):
            if abs(x[j] - x[i]) == dist_max:
                diff.append([[i,j], dist_max])
            if abs(x[j] - x[i]) > dist_max:
                dist_max = abs(x[j] - x[i])
                diff = [[i,j], dist_max]
    return (diff)

if __name__ == '__main__':
   x = [40, 76, 95, 15, 7, 6, 26, 92, 5, 77]
   print(diff_max(x))

Resposta - Força Bruta:

[2, 8], 90]

Resposta - Divisão e Conquista:

Merge sort:
[ 5  6  7 15 26 40 76 77 92 95]
order_diff_max:
[[8], [2], 90]

Observa-se que o resultado é o mesmo para a sequência sugerida.

[40, 76, 95, 15, 7, 6, 26, 92, 5, 77]
comentou Jul 6 por Pedro Antero (26 pontos)  
Ótima explicação! O código também está funcionado perfeitamente.
Percebi um pequeno *typo* no texto:

*Logo pode-se observar que o resultado procurado é o índice 2 (\(x_2=2\)) e o índice 4 (\(x_4=4\), com variação positiva de 8*. Na verdade, seria \(x_4 = 10 \), correto?

Concordo parcialmente com a sua explicação sobre a questão colocada pelo Cauê. Se a pergunta fosse sobre a maior variação de um conjunto de números, a implementação "Força Bruta" utilizando o módulo resolveria o problema. Como a questão trata de uma sequência, não se pode esquecer da ordem dos elementos!

Entretanto, nesse caso, o código para o método "Divisão e Conquista" deveria ser modificado para considerar a questão do ordenamento. Ou seja, se entendi bem a questão colocada pelo Cauê, o código que deveria ser alterado é o de "Divisão e Conquista" e não o de "Força Bruta". O que você acha?

Abs.!
comentou Jul 6 por João Gabriel Souza (76 pontos)  
Olá Pedro! Obrigado pelas contribuições.

Alterei o erro de digitação comentado.

Quanto ao segundo comentário, acredito que alterar o código de divisão e conquista não resolveria o problema,pois se você dividir a sequência ao máximo deixando apenas um número, como na figura acima, você teria que comparar um a um do mesmo jeito que o força bruta. Não alterando a complexidade. A única forma que eu vi foi ordená-lo e depois comparar o maior com o menor número, sendo assim uma variação positiva da sequência ordenada. Pois sempre que ele ordenar ele irá pegar o menor valor com o maior.

Caso tenha alguma dica de como alterar o código, algo que eu não tenha visto, podemos alterá-lo.

Abraços.
...