sexta-feira, 6 de setembro de 2013

Descrição indutiva: Busca sequencial recursiva em Java

Neste post, vamos implementar em Java e descrever indutivamente um algoritmo que realiza a busca sequencial em um vetor. Apresentaremos uma implementação recursiva, em outro post trataremos da implementação iterativa.

Descrição indutiva:

  • Caso Base: Trivial, não fazemos busca em listas vazias.
  • Hipótese de Indução: Vamos supor que a hipótese de indução busca um valor em uma lista com n-1 elementos.
  • Caso Geral: Simples, verificamos se o último elemento é o valor procurado, se não for entregamos os n-1 primeiros elementos para a hipótese de indução que se encarrega de fazer a busca no resto da lista.

Agora, apresentaremos uma implementação que decorre da descrição indutiva apresentada acima.
  • Implementação em Java:
public class LinearSearch {

 public static int linearSearch(int vet[], int n, int value) {

  if (n >= 0) {
   if (vet[n] == value)
    return n;
   else
    return linearSearch(vet, n - 1, value);
  }
  return -1;
 }

 public static void main(String[] args) {

  int vet[] = { 10, 2, 43, 14, 25, 6, 37 };
  int value = 14;
  int index = linearSearch(vet, 6, value);

  if (index == -1)
   System.out.println("Elemento não encontrado");
  else
   System.out.println("O índice do elemento " + value + " é: " + index);
 }
}
Complexidade do algoritmo/implementação:
Usando indução não é difícil encontrar uma relação de recorrência que expresse o tempo de execução do algoritmo acima. O raciocínio é simples, basta imaginar que o tempo total do algoritmo é o tempo que gastamos para verificar se o último elemento é o procurado, mais o tempo que a hipótese de indução gastou para procurar nos n-1 elementos restantes, ou seja, T(n) = T(n-1) + O(1). Resolvendo a recorrência, temos
                                                                  T(n) = T(n-1) + O(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 + 1
                                                                  ...
                                                                  T(n) = T(0) + 1 + 1 + 1 + ... + 1
                                                                  T(n) = O(n)

Analisando a relação de recorrência, podemos perceber que a busca sequencial possui complexidade linear, o algoritmo visita cada elemento apenas uma vez.
Como sempre, utilizamos a Indução Matemática para descrever nossos problemas. Para o iniciante que não está acostumado com esta abordagem, pode parecer confuso no início, mas nada que a prática não resolva.

quarta-feira, 4 de setembro de 2013

[EDITORIAL 4] Teoria dos Grafos


Em breve, Inductioncode apresentará uma série de postagens sobre teoria dos grafos. Além da prova indutiva de alguns teoremas, descreveremos indutivamente algoritmos bastante conhecidos, como as buscas em largura e profundidade.

@inductioncode

Prova Indutiva: Soma de uma série geométrica

Neste post, apresentaremos a prova por indução da fórmula que calcula a soma dos termos de uma progressão geométrica. 

                                                $\sum\limits_{i=0}^n r^i = \frac{r^{n + 1} - 1}{r - 1}$

A prova é por indução em n:

  • Caso Base: Para n = 0 temos, $\sum\limits_{i=0}^0 r^i = \frac{r ^ {0 + 1} - 1}{r - 1} = 1$.
  • Hipótese de Indução: Vamos assumir que a fórmula é válida para n-1. Logo, temos $\sum\limits_{i=0}^{n-1}r^i = \frac{r ^ {n -1 + 1} - 1}{r - 1}= \frac{r ^{n} - 1}{r - 1}$.
  • Caso Geral: Para compor o caso geral, vamos somar o elemento r^n a soma dos n-1 elementos da P.G. encontrada na hipótese de indução, temos
                                                                  $\sum\limits_{i=0}^n r^i=( \sum\limits_{i=0}^{n-1} r^i ) + r^n$

                                                                            $=\frac{r ^{n} - 1}{r - 1} + r^n$

                                                                            $=\frac{r ^{n} - 1 + (r-1)r^n}{r - 1}$

                                                                            $=\frac{r ^{n} - 1 + r^{n+1} - r^n}{r - 1}$
                                                                 
                                                                            $=\frac{r ^{n+1} - 1}{r - 1}$             C.Q.D.

terça-feira, 3 de setembro de 2013

Descrição indutiva: Fibonacci implementado em Java

Em 1202 Leonardo Pisano criou uma série de números conhecida como sequência de Fibonacci. Cada elemento na sequência é a soma dos dois elementos imediatamente anteriores:

                                              0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Formalmente, os elementos da sequência são definidos como:

              • F(0) = 0; 
              • F(1) = 1; 
              • Fn = F(n-1) + F(n-2);

Descrição indutiva:

  • Caso Base: Por definição, F(0) = 0 e F(1) = 1.
  • Hipótese de Indução: Vamos assumir que já conhecemos os valores de F(n-2) e F(n-1).
  • Caso Geral: Basta combinar os valores encontrados por hipótese de indução e somá-los para obter o resultado final fazendo F(n) = F(n-1) + F(n-2).

O algoritmo decorre imediatamente da descrição indutiva apresentada acima.

  • Implementação em Java

public class Fibonacci {

 public static int fibRec(int n) {
  if (n <= 1)
   return n;
  else
   return fibRec(n - 1) + fibRec(n - 2);
 }
 // test
 public static void main(String[] args) {
  System.out.println(fibRec(11));

 }
}

Complexidade
Apesar de termos um algoritmo de fácil implementação e enxuto, a versão recursiva para os números de Fibonacci apresentada acima é extremamente ineficiente, sua complexidade é exponencial. Em uma outra postagem traremos uma implementação iterativa e mais eficiente.

@inductioncode

Torres de Hanói: O número mínimo de movimentações é $2^n$-1

Continuando a série de posts sobre torres de Hanói e indução, vamos provar que o número mínimo de movimentações necessárias para resolver o problema é $2^n - 1$.

A prova é por indução em n:

  • Caso Base: Para n = 0, temos $2^0-1 = 0$.
  • Hipótese de Indução: Vamos supor que para mover n-1 discos entre quaisquer 2 pinos sejam necessárias $2^{n-1}-1$ movimentações.
  • Caso Geral: Para compor o caso geral teremos que considerar o custo para mover n-1 discos para um pino auxiliar ($2^{n-1}-1$ movimentações), o custo para mover 1 disco para o pino final (1 movimentação) e o custo para mover os n-1 discos do pino auxiliar para o pino final ($2^{n-1}-1$ movimentações), ou seja
                                                      Nº de movimentações =  $\underbrace{(2^{n-1}-1) + (2^{n-1}-1)}_\text{Hipótese de Indução} + 1$
                                                                                                     
                                                                                    = $2(2^{n-1}-1) + 1$

                                                                                    = $(2^n -2) + 1$

                                                                                    = $2^n -1$     C.Q.D.

segunda-feira, 2 de setembro de 2013

[EDITORIAL 3] Reverse e Append: Uma combinação ineficiente


O Inductioncode trará amanhã uma análise sobre o uso da função append (++) na implementação da função reverse, como mostrada abaixo:

reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]

Vamos discutir a complexidade dessa solução e apresentar uma outra implementação assintoticamente mais eficiente.

@inductioncode

Prova Indutiva: 2 + 5 + 8 + ... + 3n-1 = $\frac{n(3n + 1)}{2}$

Neste post, apresentaremos a prova indutiva de que a soma 2 + 5 + 8 + ... + 3n-1 vale $\frac{n(3n + 1)}{2}$.

                                   $S{\tiny n} = 2 + 5 + 8 + ... + 3n-1 = \frac{n(3n + 1)}{2}$

A prova é por indução em n:

  • Caso Base: Para n = 1, temos que $\frac{1(3\times1 + 1)}{2} = 2$.
  • Hipótese de Indução: Vamos assumir que a fórmula vale para n-1, ou seja,
                                     $S{\tiny n-1} =\frac{(n-1)(3(n-1) + 1)}{2} = \frac{3n^2 - 5n + 2}{2}$.
  • Caso Geral: Vamos estender a solução adicionando o elemento (3n-1) a soma dos n-1 primeiros elementos que assumimos ser verdadeira na hipótese de indução, logo
                                                              $S{\tiny n} = S{\tiny n-1} + (3n-1)$

                                                              $S{\tiny n} = \frac{3n^2 - 5n + 2}{2}+ (3n-1)$

                                                              $S{\tiny n} = \frac{3n^2 - 5n + 2 + 6n - 2}{2}$

                                                              $S{\tiny n} = \frac{3n^2 + n}{2}$

                                                              {Colocando n em evidência}
                                                              $S{\tiny n} = \frac{n(3n + 1)}{2}$   C.Q.D.

@inductioncode