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

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

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

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.

Seguir @inductioncode

Prova Indutiva: $2^n$ > $n^2$, para n $\geq$ 5

Continuando nossa série de posts sobre provas por indução, vamos mostrar que: $2^n$ > $n^2$, para n $\geq$ 5.

Prova por indução em n:

• Caso Base: Para n = 5, $2^5 > 5^2$.
• Hipótese de Indução: Vamos assumir que a inequação é valida para n-1, ou seja, $2^{n-1} > (n-1)^2$.
• Caso Geral: Agora vamos utilizar a hipótese de indução e estender a solução, esta etapa também é conhecida como "passo indutivo".

                                                  $2 * 2^{n-1} > 2*(n-1)^2$     {multiplicando ambos os lados por 2}
                                                  $2^n > 2(n^2 - 2n + 1)$
                                                  $2^n > n^2 + n^2 - 4n + 2$    {como $-4n > -n^2$, vamos subtituí-lo por $n^2$}
                                                  $2^n > n^2 + n^2 - n^2 + 2$     {substituindo $n^2 + n^2 - n^2 + 2$ por $n^2 + n^2 - n^2$}
                                                  $2^n > n^2 + n^2 - n^2$
                                                  $2^n > n^2$                               C.Q.D.

Neste post, apresentamos a prova por indução de uma inequação. É interessante observar que a prova de inequações é um pouco diferente da prova de equações, pois ao trabalharmos com desigualdades podemos realizar algumas substituições que não seriam permitidas em equações com operador de igualdade.

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.

Seguir @inductioncode

[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