sábado, 21 de setembro de 2013

Torres de Hanói: Computando o número de movimentações


Em posts anteriores, apresentamos a descrição indutiva para o problema das Torres de Hanói e provamos que o número mínimo de movimentações necessárias para resolver o problema é $2^n - 1$, onde n é o número de discos. Agora, vamos usar a descrição indutiva já discutida para calcular o número de movimentações necessárias, mas com um detalhe, o número de movimentações será calculado no momento em que as movimentações forem feitas. Nosso objetivo é apresentar o significado de "fortalecimento da hipótese de indução".

Fortalecer uma hipótese, significa assumir que ela realiza algo a mais quando comparada à hipótese original. Ou seja, além de assumirmos que a proposição P(n-1) é válida, também assumiremos uma condição C(n-1) e em seguida estenderemos nossa solução para P(n) e C(n).

Para um pleno entendimento do tema tratado aqui, não deixem de ler os posts:
Siga o Inductioncode no Twitter: 

Descrição indutiva:

  • Caso Base: para n = 0, temos que o número de movimentações é 0.
  • Hipótese de Indução: vamos assumir que sabemos como mover n-1 discos, e como condição extra vamos assumir que o número de movimentações está armazenado em uma variável que chamaremos de numMoves.
  • Caso Geral: No passo indutivo, vamos estender a solução para o caso geral. Para isso, após realizar uma movimentação, basta incrementar a variável numMoves.
A implementação que apresentaremos em Java, segue exatamente a ideia apresentada acima.

  • Implementação em Java
public static int numMoves = 0;
static void hanoi(int n, char A, char B, char C) {
  if (n > 0) {
    hanoi(n - 1, A, C, B);
    System.out.println("Mova o disco " + n + " de " + A + " para " + B);
    numMoves++;
    hanoi(n - 1, C, B, A);
  }
}

Em breve, falaremos mais sobre o fortalecimento da hipótese de indução. Aguardem.
@inductioncode

quinta-feira, 19 de setembro de 2013

Prova indutiva: n! > $2^n$ para n $\geq$ 4

Provaremos agora a desigualdade n! > $2^n$ para n $\geq$ 4. Mostraremos que a função fatorial cresce mais rápido que a função exponencial.

A prova é por indução em n:

  • Caso Base: Para n = 4, temos que $4! > 2^4$.
  • Hipótese de Indução: Vamos supor que $(n-1)! > 2^{n-1}$.
  • Caso Geral: Agora basta utilizar o resultado obtido na hipótese de indução e estender a solução para o caso geral, assim temos que
                               $2*(n-1)! > 2*2^{n-1}$
                       $2*(n-1)! > 2^n$  
         {como 2*(n-1)! é menor que n!, para n = 4, podemos substituí-lo por n! e mantemos a desigualdade}
                   $n! > 2^n$   C.Q.D.

segunda-feira, 16 de setembro de 2013

Descrição Indutiva: Busca Binária recursiva em Java

Neste post, vamos descrever indutivamente e discutir a complexidade da busca binária. Como veremos,    a busca binária é mais eficiente que a busca sequencial discutida no post Descrição indutiva: Busca sequencial recursiva em Java. No entanto, para que possamos aplicar a busca binária em um vetor (lista) é necessário que ele esteja ordenado.

Descrição Indutiva:
  • Caso Base: Para um vetor com apenas um elemento, basta verificar se o elemento procurado é o elemento armazenado no vetor.
  • Hipótese de Indução: Vamos assumir que a hipótese de indução sabe procurar o elemento desejado em um vetor com $\frac{n}{2}$ elementos.
  • Caso Geral: Vamos procurar um elemento K no vetor. Para compor o caso geral, vamos dividir o vetor ao meio e verificar se o elemento central é maior ou menor que K. Caso o elemento central seja menor que K, então K poderá ser encontrado na segunda parte do vetor, caso contrário, o elemento K poderá ser encontrado na primeira parte do vetor.
A implementação em Java (ou em sua linguagem predileta) segue exatamente a descrição indutiva do problema.
  • Implementação em Java
public class BinarySearch {

  public static int binarySearch(int vet[], int value, int left, int rigth) {
    int middle;
    if (left <= rigth) {
      middle = left + (rigth - left) / 2;
      if (vet[middle] == value)
      return middle;
    else if (vet[middle] > value)
      return binarySearch(vet, value, left, middle - 1);
    else
      return binarySearch(vet, value, middle + 1, rigth);
    }
    return -1;
}
  public static void main(String[] args) {
    int vet[] = { 1, 3, 4, 6, 78, 90 };
    System.out.println(binarySearch(vet, 3, 0, 5));
  }
}

Complexidade
A busca binária é muito eficiente, pois a cada passo descarta a metade do espaço de busca. A relação de recorrência que expressa a complexidade do algoritmo é: $T(n) = T(\frac{n}{2}) + 1$. Resolvendo a recorrência temos que a busca binária é O(log n).


Gostou da publicação? Sim? Então curta nossa fan page no Facebook e acompanhe nossas postagens.
@inductioncode

sexta-feira, 13 de setembro de 2013

Exponenciação Rápida: Descrição indutiva e implementação em Java

Neste post, apresentaremos uma implementação eficiente para o problema da exponenciação. Faremos a descrição indutiva do problema e em seguida implementaremos uma solução em Java. No  post anterior (ver post), utilizamos a indução fraca, agora vamos usar a indução forte para descrever o mesmo problema. Para revisar os conceitos básicos referentes ao uso da indução matemática na construção de algoritmos, veja o post: Indução Matemática - Visão Geral.

Matematicamente, temos o seguinte:

                                                                  $a^n = (a^{\frac{n}{2}})^2$     , se n for par
                                                                  $a^n = a * a^{n-1}$ , se n for ímpar

Descrição indutiva:

  • Caso Base: Para n = 0, temos que $a^0 = 1$.
  • Hipótese de Indução: Vamos assumir que temos o valor de $a^{\frac{n}{2}}$.
  • Caso Geral: Simples, basta elevar ao quadrado o resultado encontrado na hipótese de indução.
A implementação em Java (ou sua linguagem predileta) segue exatamente a descrição indutiva do problema.
  • Implementação em Java:
public class Potenciacao {

  public static int fastExp(int base, int exp) {
    if (exp == 0)
      return 1;
    else if (exp % 2 == 0)
      return (int) Math.pow(fastExp(base, exp / 2), 2);
    else
      return (int) (Math.pow(fastExp(base, exp - 1), 2) * base);
  }

  public static void main(String[] args) {
    System.out.println(fastExp(2, 3));
  }
}

Complexidade
A solução apresentada acima é mais eficiente que a solução utilizada no post anterior. A relação de recorrência $T(n) = T(\frac{n}{2}) + 1$ mostra que o algoritmo possui complexidade O(log n).

@inductioncode

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

segunda-feira, 9 de setembro de 2013

Exponenciação: Descrição indutiva e implementação em Java

Neste post, vamos descrever indutivamente um algoritmo que realiza a exponenciação. Em seguida, apresentaremos uma implementação em Java. Matematicamente, para calcular a exponencial $a^n$, fazemos:

                                                                   $\underbrace{a * a * a * ... * a * a}_\text{n termos} = a^n$

Descrição indutiva:

  • Caso Base: Para n = 0, temos que $a^0 = 1$.
  • Hipótese de Indução: Vamos assumir que a hipótese de indução sabe como calcular $a^{n-1}$.
  • Caso Geral: Trivial, basta pegar a resposta que a hipótese de indução nos deu e multiplicar por a. E assim teremos:                                                                   $\underbrace{\overbrace{(a^{n-1})}^\text{Hipótese de Indução}*a}_\text{Caso Geral} = a^n$.
A implementação em Java segue exatamente a descrição indutiva apresentada acima.

  • Implementação em Java
public class Potenciacao {
  public static int slowExp(int a, int n) {
    if (n == 0)
      return 1;
    else
      return slowExp(a, n - 1) * a;
  }

  public static void main(String[] args) {
    System.out.println(slowExp(2, 3));
  }
}

Complexidade
A implementação acima possui complexidade linear. Ou seja, T(n) = T(n-1) + O(1),onde n é o expoente da potência. Podemos fazer melhor?

@inductioncode

domingo, 8 de setembro de 2013

Participe da nossa enquete

Participe da nossa enquete e diga qual linguagem de programação você quer ver aqui no Inductioncode. Faremos uma série especial de posts com implementações na linguagem escolhida.