Mostrando postagens com marcador Particionamento de Dados. Mostrar todas as postagens
Mostrando postagens com marcador Particionamento de Dados. Mostrar todas as postagens

quinta-feira, 12 de setembro de 2013

Particionando dados: implementação em Haskell

Em uma postagem anterior, que pode ser vista aqui, abordamos indutivamente a construção de um algoritmo que realiza a separação de dados em um vetor. Agora apresentamos uma implementação em Haskell para solucionar o mesmo problema. 
Por se tratar de uma linguagem funcional, Haskell possibilita uma implementação clara e enxuta na maioria dos casos.

Vamos a descrição indutiva do problema:
  • Caso Base: Uma lista vazia está particionada em pares e ímpares por definição.
  • Hipótese de Indução: Vamos assumir que uma lista com n-1 elementos já está particionada em pares e ímpares.
  • Caso Geral: Basta verificar a paridade do elemento que ficou de fora, se ele for par então basta colocá-lo no início da lista com n-1 elementos obtida por hipótese de indução, caso contrário ele será colocado no final da lista obtida por hipótese de indução.

E mais uma vez derivaremos o algoritmo a partir da descrição indutiva. A boa notícia é que o algoritmo decorre imediatamente da descrição indutiva e podemos chegar até ele sem esforço. A seguir apresentamos a solução para a descrição indutiva implementada em Haskell.

  • Implementação em Haskell

partition :: [Int] -> [Int]
partition [] = []
partition (x:xs)
  | x `mod` 2 == 0 = x : (partition xs)
  | otherwise      = (partition xs) ++ [x]


Complexidade do algoritmo:
Apesar de simples, a implementação apresentada em Haskell não é eficiente. Em nosso editorial, discutiremos uma implementação mais eficiente também em Haskell.

@inductioncode

sábado, 7 de julho de 2012

Particionando em pares e ímpares

Agora, vamos utilizar indução para resolver um problema fácil, que com indução ficou mais fácil ainda.
Problema:
  • Dada uma sequência de n valores inteiros, rearranjar os elementos de forma que os valores pares apareçam antes dos ímpares.
Idéia indutiva:
  • Caso Base: uma lista com 1 elemento já está particionada em pares e ímpares.
  • Hipótese de Indução: podemos assumir que o problema já foi resolvido para n-1 elementos, e que sabemos onde termina a lista de pares.
  • Caso Geral: basta verificar se o último elemento é par ou ímpar, se ele for par basta inseri-lo no final da lista de pares, caso contrário, não fazemos nada.  
Agora, vamos ilustrar o problema com um exemplo:
  • Situação inicial: Um vetor com valores pares e ímpares misturados.
  • Hipótese de indução: agora vamos "imaginar" que o problema já foi resolvido para os primeiros n - 1 elementos, e que sabemos onde termina a lista de pares.


  • Caso Geral: Pronto! Agora ficou muito fácil, podemos perceber que o último elemento é par, então vamos incrementar o final da lista de pares e trocar o último  elemento da lista de pares com o último elemento do vetor.


  • E assim chegamos a solução do problema.


O algoritmo segue exatamente a idéia apresentada acima. Vamos assumir que o problema já foi resolvido para os primeiros n - 1 elementos, e dentro do loop só escreveremos código para trocar o último elemento do vetor (caso ele seja par) com o último elemento da lista de pares. E não podemos esquecer do caso base!
  • Implementação em C++ (versão iterativa)
fimPares = -1; // caso base
for(int i = 0; i < tamVetor; i++)
  if(vetor[i] % 2 == 0){  // passo indutivo
    fimPares++;
    troca(vetor[i], vetor[fimPares]);
  }

Complexidade do algoritmo: A relação de recorrência da nossa solução é T(n) = T(n - 1) + 1, ou seja, o tempo gasto pela hipótese de indução para separar os n - 1 elementos mais o tempo gasto para colocar o último elemento no final da lista de pares. Derivando T(n) temos:

$T(n) = T(n - 1) + 1$
$T(n) = T(n - 2) + 1 + 1$
$T(n) = T(n - 3) + 1 + 1 + 1$
$T(n) = T(n - 4) + 1 + 1 +1 +1$
...
$T(n) = 1 + 1 + 1 + 1 + 1 + 1 + ... + 1 + 1$
$T(n) = O(n)$

Logo, concluímos que o nossa solução tem complexidade linear.