quinta-feira, 26 de setembro de 2013

Inserindo elementos em uma sequência ordenada

Neste post, vamos descrever indutivamente um algoritmo para inserir um elemento em uma sequência ordenada. Utilizaremos a linguagem Haskell, e em posts posteriores apresentaremos implementações em Python e Scala.

Descrição indutiva:

  • Caso Base: Inserir um elemento em uma sequência vazia é trivial.
  • Hipótese de Indução: Vamos assumir que sabemos como inserir um elemento em uma sequência com n-1 elementos.
  • Caso Geral: Simples, basta verificar se o elemento que desejamos inserir é maior ou menor que o primeiro elemento da lista, caso seja maior, entregamos o elemento e o restante da lista para a hipótese de indução, caso seja menor que o primeiro elemento, basta colocá-lo no início da lista ordenada.
A implementação em Haskell segue exatamente a descrição indutiva apresentada acima.

  • Implementação em Haskell
insert :: [Int] -> Int -> [Int]
insert [] a = [a]
insert (x:xs) a 
  | (a < x)   = a:(x:xs)
  | otherwise = x:(insert xs a)

Como podemos perceber, utilizar uma linguagem funcional ajuda no processo de abstração e resolução dos problemas. Inductioncode disponibilizará em breve um editorial que fará um comparativo entre os paradigmas funcional e imperativo.

Prova Indutiva: $F{\tiny 1}^2 + F{\tiny 2}^2 + F{\tiny 3}^2 + ... + F{\tiny n}^2 = F{\tiny n} \times F{\tiny n+1}$

A sequência 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, .... é conhecida como série de Fibonacci e foi definida formalmente aqui. Os números de Fibonacci possuem várias propriedades interessantes, agora vamos apresentar uma delas, provando por indução que

                                                           $F{\tiny 1}^2 + F{\tiny 2}^2 + F{\tiny 3}^2 + ... + F{\tiny n}^2 = F{\tiny n} \times F{\tiny n+1}$

A prova é por indução em n:

  • Caso Base: Para n = 1, $F{\tiny 1}^2 = F{\tiny 1} \times F{\tiny 2}$.
  • Hipótese de Indução: Vamos assumir que $F{\tiny 1}^2 + F{\tiny 2}^2 + F{\tiny 3}^2 + ... + F{\tiny n-1}^2 = F{\tiny n-1} \times F{\tiny n}$.
  • Caso Geral: No passo indutivo, basta adicionarmos o valor de $F{\tiny n}^2$ a soma dos primeiros n-1 elementos que definimos na hipótese de indução, ou seja
                                                     $F{\tiny n} \times F{\tiny n+1} = \overbrace{\underbrace{(F{\tiny n-1} \times F{\tiny n})}_\text{Hipótese de Indução} + F{\tiny n}^2}^{Caso Geral}$

                                                    $F{\tiny n} \times F{\tiny n+1} = F{\tiny n} \times (F{\tiny n-1} + F{\tiny n})$

                         {Por definição, sabemos que $F{\tiny n} = F{\tiny n-1} + F{\tiny n-2}$, logo $F{\tiny n-1} + F{\tiny n} = F{\tiny n+1}$}

                                                   $F{\tiny n} \times F{\tiny n+1} = F{\tiny n} \times F{\tiny n+1}$      C.Q.D.

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